SHA1 structure (Re: [Cfrg] Re: AES-based hash function)

[Adam Back <adam at cypherspace.org>]

On Fri, Sep 03, 2004 at 07:12:04AM +1000, Greg Rose wrote:
> In fact, look at the structure of the things that were all just
> broken... they *are* block ciphers, used in Merkle-Damgard mode. The
> data is used as the key, the chaining variables are the block, and
> the data expansion phase is just a key-scheduling operation. The
> only way they differ from things like AES is that more emphasis was
> placed on fast key scheduling, since it changes for every block.

In fact to spell out the structure of SHA1 from my notes when I was
trying to finding collisions on 17 round SHA1:

SHA1(x_1||..||x_n) = C_n

C_{i+1} = E_{x_i}(C_i)+C_i

(E_k(M) means as usual encrypt with key k data M, E is a block cipher
with 160 bit block, and 512 bit key + is mod 2^32 addition of the 5 32
bit words of the block).

IV = x_0 = H0||H1||H2||H3||H4 (the sha1 magic constants)

The compression function is F_x(y) = E_x(y)+y.

a function D = E^-1 exists (ie you can decrypt)

An interesting pair of values to find would be 

key z st E_z(IV) = 0^160; and key z' st E_z'(IV) = 0^160

these are interesting values because the define fixed-points in the
compression function: F_z(IV) = E_z(IV)+IV = 0^160+IV = IV

So F^k_z(IV) = IV for all k (apply repeatedly).

Then one can use this fixed point to make sets of collisions, eg:

SHA1(z||a) == SHA1(z'||a)

and:

SHA1(z||z||a) == SHA1(z||z'||a) == SHA1(z'||z||a) == SHA1(z'||z'||a) 

and so on for a set of 2^k colliding sets for all k+1 length messages.

Adam

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg