secure hash modes for rijndael

[John Kelsey]

-----BEGIN PGP SIGNED MESSAGE-----

At 11:25 PM 3/29/01 -0800, Bram Cohen wrote:
>sha-256 is ridiculously slow, so I've done some thinking about hash
>modes for rijndael.  

>To begin with, there's the issue of padding - this can be done by
>appending a 1 and then padding with zeros to the next multiple of a
>block size. If the data to be hashed is already a multiple of a
>block size and doesn't end in a 1 to begin with, no padding is
>necessary. This gets rid of a lot of unnecessary work for hashing
>small files.  

It's easy to cause collisions, if you do this, because you can use
the padding scheme to cause two unequal messages to collide.  That
is, 

M is some message that will need padding P.  (For example, M is 127
bits long, and P is a single one bit.)

M' = M||P  (For example, M' is 128 bits long.)

M' can't end in a one bit, and we can choose M not to, either. 

M <> M', but after the padding step, you'll get the same actual input
to the hash function, and as a result, you'll get a collision.  This
is why padding rules for hash functions always specify that padding
must *always* be done.

You also need the length included in the hash calculation somewhere.

>Making a hash requires two fixed keys, the logical values for them
>are all 0 and all 1 bits. First, compute CBC MACs using the two
>fixed keys (a CBC MAC is where encrypt the first block, xor with the
>second, encrypt again, xor with the third, etc.) Call the two MACs A
>and B. Now encrypt A using B and B with it's last byte xored with FF
>using A (the xor is in case the data is only a single block length,
>making A and B both be the original file). Concatenate those two
>values together and that's the hash.  

So, if I'm understanding this, it's:

A = CBC-MAC_{K0}(message+padding)
B = CBC-MAC_{K1}(message+padding)
X = E_A(B)
Y = E_{B xor 00..00ff}(A)

hash output is (X,Y)

Assuming we fix the padding scheme so that there's always at least
one bit of padding, what can we do with this?  We can get a collision
either in the final step of going from (A,B) to (X,Y), or by getting
two messages with the same (A,B) values.  

So, here's my solution for getting a collision in this scheme:

a.  Generate a set of 2^{64} messages, M_{0,1,...,2^{64}-1} which all
have the same ending value for A.  I'll show how to do this below,
but it's *really* easy, because we know the key and we can do
decryption.  

b.  Of this set, we expect a pair of messages to collide in B, by the
birthday paradox.  That pair will collide for the ending value of
(A,B).  Since (X,Y) is just a function of (A,B), that means that the
whole hash collides.

Making a large set of messages with the same ending A value is
simple.  Suppose we have a desired ending A value, which I'll just
call A.  We generate a set of messages, all of the same length, all
with a full padding block P at the end.  (That padding block is
0x8000...00).

To generate a message such that CBC-MAC_{K0}(message)==A, we do:

a.  Make a message M_i = R_i, R_j, u, P

where R_i,R_j are random AES blocks, u is still to be determined, and
P is the padding block.

b.  Compute A' = the CBC-MAC before the padding block is processed,
which is 
	A' = D_{K0}(A) xor P

c.  Compute A'' = the CBC-MAC after processing M_i as far as R_j.  

d.  We now need to solve the equation:
	A' = E_{K0}(A'' xor u)
for u, which will tell us what the last block of the message needs to
be.  We can do that easily enough, by computing 
	u = A'' xor D_{K0}(A').

So, at least that technique is broken.  (There may be more efficient
attacks.)

I've played around with schemes somewhat like this one.  The one I
liked, but haven't been able to convince myself is secure, is:

W,X,Y,Z are the state, K0 is some fixed AES key.  W,X,Y,Z are
initialized to (0,1,2,3).

Pad the message intelligently, including the length.  

For each message block of 128 bits, M, do:

	W = W xor M
	X = E_{K0}(X xor M)
	Y = E_{K0}(Y xor M)
	Z = E_{K0}(Z xor M)

At the end, do some complicated munging of these blocks to get an
output, such as:

Let (a,b,c,d) = (W,X,Y,Z)

Process (a,b,c,d) as last four blocks of message.

Output Y,Z

I wasn't able to find an attack on this, but I haven't spent much
time on it, and I've also never been able to convince myself there
wasn't an attack on it.  But it does accomplish the obvious
requirement of making an attacker control many things at once to get
a collision.  

I suspect the right way to attack this is to do something clever to
force the states into short cycles or something.  Remember, an
attacker of a 256-bit hash function arguably has close to 2^{128}
work and memory available to mount an attack; he might examine most
of E_{K0} for short cycles or some such.

Anyway, designing hash functions is *hard*.  It seems to me that it's
much harder than designing block or stream ciphers, because there's
nothing unknown to the attacker.  The easiest case is MACs, where you
can design the system to reveal almost nothing to the attacker, and
all your internal state except a 32-bit tag at the end of each
message is totally kept secret.  

...
>It would be nice if there was an algorithm which used rijndael with
>256 bit blocks to produce a hash of 256 bits and had a hash rate of
>1, but I haven't been able to come up with one.  

I worry a bit about this, because AES/Rijndael has such a simple key
schedule.  It's really hard to convince myself you wouldn't be able
to come up with *some* weird property of AES that wouldn't let you
recover a message, but might, say, let you find (key,plaintext) pairs
whose ciphertexts collided relatively quickly.  

...
>-Bram Cohen

- --John Kelsey, kelsey.j at ix.netcom.com

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 Int. for non-commercial use
<http://www.pgpinternational.com>

iQCVAwUBOsaVLiZv+/Ry/LrBAQEQgwQAwT6gTeERFiPBCgeaQT44369jcu0Fvxxc
IM7VcrKlFUBuwAm7ec+M1nGflFLo4440fYKD/G+KMat5aJpty7CN+hwlevuoifd7
q1iM461tPm8evdCXwHN9KnQ4ryUiSjVMx1DiLX82fyHbW9nBKw40I8JhbDq8qpZx
GoPDCALN418=
=dTdM
-----END PGP SIGNATURE-----




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com