[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A hole in esp-stream-01
-----BEGIN PGP SIGNED MESSAGE-----
[ To: IPSec mailing list ## Date: 10/25/96 08:21 pm ##
Subject: RE: A hole in esp-stream-01 ]
>Date: Thu, 24 Oct 1996 18:18:15 -0400
>From: Andrew Robison <arobison@timestep.com>
>Subject: RE: A hole in esp-stream-01
>How about the following:
>
>start with the values of:
> C1(0)=0x674502301
> C2(0)=0xefcdab89
>
>which are the first two start values for MD5. They could of course be
>random number if you wanted this to be keyed.
>
> C1(N+1)=C(N)+B(N)
>
>which is easily predictable as if you know the plaintext bit you want to
>change, all you need to do is flip all of the appropriate bits based
>upon what it does to the count. Not good enough, so:
>
> C2(N+1)=ROTL(C2(N)+C1(N+1),C2(N)>>5)
>
>which is much harder to predict unless you know all of the plaintext.
>Finally, the checksum H is produced:
>
> H=ROTL(C2(N),C2(N)>>5)^ROTL(C2(N),C2(N)>>23)
>
>Cost is about 6 operations/byte which means that a P90 should be able to
>churn through over 15MB/sec.
>
>Rather than XOR the checksum with the last four bytes of the packet as
>was suggested, which allows for changing these four bytes' values, add
>four more bytes to the packet as is done with ESP DES-MD5.
One way to attack this kind of system is to find generic ways to
change the plaintext that lead to the same MAC with some fairly high
probability. Let's think about ways to do this:
This is a restatement of the MAC: All variables here are 32-bit
words:
for(i=0;i<data_len;i++){
c1 = c1 + data[i];
c2 = rol(c2+c1,(c2>>5)&31);
}
mac_output = rol(c2,(c2>>5)&31)^rol(c2,(c2>>23)&31);
Now, it's immediately clear how to alter c1--it's actually under our
complete control if we control the plaintext. If we can only flip
desired bits (rather than, say, adding 32-bit values in), then we
lose a little control over this, but not too much.
Let's suppose we want to make c1 differ modulo 2^{32} by values
a, then b, then go back to not differing. How do we have to change
the plaintext? (Here x* means the altered form of x.)
D[4]* = D[4] ..... c1[4]* = c1[4]
D[5]* = D[5] + a ..... c1[5]* = c1[5] + a
D[6]* = D[6] + b - a ..... c1[6]* = c1[6] + b
D[7]* = D[7] - b ..... c1[7]* = c1[7]
These values for D4..7 will cause c1 to differ by 0,a,b,0, and will
allow no propogation in c1. This still leaves us with c2 to worry
about.
Okay, so now we need to also undo the change in c2. The trick here
is to either know or guess the rotation amount for c2 going into
each step. Let's choose (a,b) so that b = -a mod 2^{32}. In that
case, we now cause c1 to change by 0,a,-a,0 by causing the above
changes in the plaintext. Now, let's think about this:
c2[4]* = c2[4]
c2[5]* = rol(c2[5] + a,j)
c2[6]* = rol(c2[6] - a,k)
c2[7]* = c2[7]
This works iff j = 0, which happens with probability 2^{-5}. Thus,
we get:
1. If the plaintext before the change is made is known, and the
starting state is known, then we can make changes in the plaintext
without affecting the MAC with certainty of success. (We have to
vary the attack slightly to deal with different rotation counts, but
it's fundamentally not much of a problem.)
2. If the plaintext before the change, or the starting state, are
unknown, then we can make changes in the plaintext with a 2^{-5}
probability of success.
Note that the added munging at the end has nothing to do with this
attack, since by the time that happens, we've already returned the
state back to normal.
The only loose thread with this analysis is that we're talking about
not having complete control of the plaintext--instead, we're hitting
it through an XOR encryption. What we actually need to be able to
do is to add and subtract 32-bit numbers into the plaintext. This
is straightforward if we know the original values we want to change
(XOR in the original one, then XOR in the new value desired).
However, if we don't know them, we can still flip bits. In this
case, we flip bits instead of adding and subtracting numbers. Now,
here's the trick: if we flip bit i in a word, we either add or
subtract 2^i. So, for the attack above, we might try to flip bit i
in three consecutive words. With probability 2^{-3}, this part
would work properly, and if it did, then we'd have a 2^{-5}
probability of not altering the final checksum. Unless I'm missing
something, the final probability of successfully making the change
is 2^{-8}.
In short: I don't think this MAC is strong enough to be useful.
The big problem with a lot of this kind of scheme is that we don't
get good diffusion in our intermediate ``chaining'' variables.
Anytime we fail to get good diffusion there, it seems like an
attacker can find ways to manipulate those internal values. (This
is why, say, one-round MD4 isn't useful as a MAC, at least not
directly.)
A couple of ideas that might be interesting:
1. Use two instances of the keystream generator, one for
encryption, and one for authentication. The authentication one
simply encrypts the plaintext into an intermediate value which is
MACed. An attacker never sees this intermediate value, and it
should change (along with the encrypting keystream) for each packet.
2. Find some internal function for the MAC which doesn't have any
good XOR-based differentials. (That is, make its differentials
something that are hard to get to with XOR differences in the
plaintext, which are the only ones the attacker can cleanly get into
the MAC.) Some ideas here include using S-boxes that are optimized
to have no high-probability XOR differentials, using multiplication
mod 2^{16}+1, as in IDEA, or using some kind of nonlinear binary
functions as in MD4 or Haval. Addition-with-rotation alone doesn't
seem like it will be enough, unless it's iterated a huge number of
times, as in TEA. Also, I think it makes sense to do a big one-time
precomputation (as in Blowfish or Khufu) ahead of time.
>Which raises the question:
>
>When using ESP with DES or 3DES, why do I need a cryptographically
>strong hash function since the hash is encrypted? In order to be able to
>successfully modify the packet and still create a valid hash would
>require breaking the encryption. We are not actually talking about a
>non-repudiation issue with a digital signature; a cryptographically
>secure hash appears to be overkill and using a keyed hash even more so.
Actually, I think this general idea (hash the data, then encrypt the
hash) has been discussed a few times as a valid MAC design. I can
see a couple possible problems with it, off the top of my head:
1. If you can cause collisions in the hash function (i.e., MD5),
then you can cause collisions in the MAC, as well. (I don't think
this is all that upsetting--once your hash function has stopped
resisting collisions, it's time to retire it.) More to the point,
collision values can be found offline--they don't require interaction
with the user. Admittedly, getting the pair of collision values
into encrypted form is still going to be pretty complicated.
2. I think doing this in CBC-mode may add some complications to
the analysis. Among other things, we have to make sure the IV gets
hashed along with the data.
Does anyone else know of cryptanalysis of this kind of scheme?
Of course, we often want to be able to give the ability to
authenticate data without the ability to decrypt it. In that case,
this scheme isn't acceptable, but simply encrypting the hash
(probably in ECB-mode) is. We also would probably want to do a
*little* something to make precomputation-type attacks harder, so we
might do MAC_K(X) = e_K(md5(e_K(512 bit pad),packet_data)). Note
that the intermediate result from that first 512-bit hash is only
computed once, and is then stored.
Comments?
--John Kelsey, jmkelsey@delphi.com / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMnG7l0Hx57Ag8goBAQEK9AQAgJvu5MlTBaYDE0fs00h9Sh05b6rIgu8C
lzCuzwsbSlPmc/19H04iI6aFzSe4dkDJeK0zdkpG7zC/9wyfSdpuiKPua1meepcp
/ihqjuPJrXhfWiu7d/Iwyh73m145g0yVzQdfCFlJmWG5tjJ3dhDxPOfZ/s1J0UGp
+ohnNj4YjYI=
=RrAD
-----END PGP SIGNATURE-----