Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Thu May 27 1999 - 23:44:22
Thomas Roessler (roessler@guug.de)
Mon, 12 Apr 1999 14:32:58 +0200
Niels Ferguson, Bruce Schneier, and Dave Wagner have an unpublished
paper on a model of what Tristrata's Random Key Stream may look
like. Their model is as follows: There are M pointers t_1, ..., t_M
into a pool of random bytes of size S. The key stream is then:
k_i = Xor_{j = 1}^{M} pool[(t_j + i) mod (S - j + 1)]
One of the attacks described in this paper relates to finding the
pool from known keystream and know pointers. They note that each
known byte of key stream is an equation in five elements of the
pool. Given a sufficient amount of known key stream for known
pointers, the pool can be reconstructed by solving a large system of
linear equations.
Now, consider the following excerpt from Tristrata's Product
Description, available from their Web site:
The request is sent from the client to the server over Private
Access Line (PAL). PAL encryption uses key streams that are
generated from 256-kilobyte (2-megabit) secret Access Signature
(key) and an additional 112 bits of random data. The secret
Access Signature is shared between the client and TESS, allowing
the two parties to authenticate each other. Over 4 trillion
unique key streams, each 64 kilobytes long, can be generated from
one Access Signatue. The 112 bits of random data determie which
stream is selected. These bits are exchanged between TESS and
client in the clear, but they are protected from alteration by a
message authentication code. [...] If the user is authorized, TESS
creates a Permit that includes encryption instructions and a Seal
that contains all the information necessary to decrypt the
document. The Seal is encrypted by TESS using 3DES in CBC mode.
Assuming that "PAL" is using a "Random Key Stream" algorithm similar
to the one described above, I see a couple of problems here:
- It's probably safe to assume that the client's request contains
known plaintext, f.i. the client's ID. This means that any
evesdropper gets a chunk of known key stream for known pointers -
and this each time a client communicates to TESS.
- The Seal is apparently stored and transmitted in the clear,
giving us another chunk of known key stream for said pointers.
- Once the intended recipient of an encrypted message was able to
get the decryption information from TESS, he is able to
construct the "encryption instructions" quoted above, yielding
still more known key stream.
>From this known keystream and known pointers situation, an
evesdropper can reconstruct the client's "Access Signature", giving
him full access to the client's data and permitting him to
impersonate the client against TESS. Since the Access Signature is
apparently not changed too often, it is realistic to assume that an
attacker can gather enough data.
The effort to solve the system of equations for the actual random
pool can be very roughly estimated in a back-of-the-envelope manner
as follows: Using Gauss' algorithm over Z/2Z (i.e., considering the
system of equations bit-wise) for 2^21 equations in 2^21 variables,
we need less than 2^41 one-bit xors, i.e., on a suitable cpu, you
are left with less than 2^35 64 bit xor operations. Note that
storing the full equations will require 512 GB of memory.
Note that this estimate does not make any use of the special
structure of the system of equations we are talking about. Most
notably, the 512 GB memory requirement is far away from reality;
this requirement can be greatly reduced in practice.
Also, please note that this attack is based on guesses of what
Tristrata's algorithms may look like. It may be completely
unrelated to the scheme actually in use.
Any comments?
tlr
-- http://home.pages.de/~roessler/
The following archive was created by hippie-mail 7.98617-22 on Thu May 27 1999 - 23:44:22