-----BEGIN PGP SIGNED MESSAGE-----
I've been thinking about the requirements for hash functions. I've
heard that NSA is currently designing a 256-bit wide SHA1
replacement, and I've been thinking about some things it would be
nice to change from the way SHA1 and MD5 and such functions work.
I really dislike the length-extension property of SHA1, MD5,
RIPE-MD160, etc. That property is basically that if you are given
hash(X), you can compute hash(X||Z), where Z is a bit string that has
its first 512 or so bits specified based on the length of X, and can
be allowed to take on any value desired after that. This is why the
MAC proposal
MAC_K(X) = hash(K||X)
doesn't work. It's an extremely unintuitive property for a hash
function to have.
It looks to me like there's an extremely easy fix for this, though I
may be missing something. If we define
h'(X) = SHA1(X)
and let f(IV,M) be the SHA1 compression function, we can eliminate
the length-extension property by letting
IV1 = the starting IV for SHA1.
L = message length
hash(X) = f(IV1,h'(X)||00...0||L)
This costs one more compression function call for all messages, but
apparently eliminates this length-extension property, since the
attacker who doesn't know X doesn't learn h'(X) unless he can invert
the hash compression function.
My questions to the list are:
a. Has anyone done analysis of this anywhere else? The construction
is similar to the one used in HMAC, but I don't recall reading
anything proposing that it be used in all hash functions.
b. What effects would this have on hash functions if it were widely
adopted?
This can't make a hash function weaker against either inversion or
collision-finding attack, unless I'm missing something big.
Inversion attack: To invert this and recover X, you would have to be
able to invert the existing hash function. Sketch of Proof: Suppose
you give me an algorithm for inverting hash(X); given this algorith,
I construct a new algorithm that inverts h'(X), which is the old hash
function. To do this, I compute hash(X) = f(IV1,h'(X)||00..0||L) and
then apply your algorithm for inverting hash(X).
Collision attack: To find a pair of messages that collide, you must
do one of two things:
a. Find a pair of messages that collide for h'(X). If you've done
this, you've found a collision for the original hash function.
b. Find a pair h'(X),h'(X*) for which
f(IV1,h'(X)||00..0||L) == f(IV1,h'(X*)||00..0||L). That means
finding a hashing collision for the compression function using only
the message block, from SHA1's starting IV. If you can do that, you
have found a hash collision for SHA1: M0 = h'(X)||00..0||L, and M1 =
h'(X*)||00..0||L.
Comments?
- --John Kelsey, [EMAIL PROTECTED]
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 Int. for non-commercial use
<http://www.pgpinternational.com>
Comment: foo
iQCVAwUBOWo4MiZv+/Ry/LrBAQEHSgP/SlhRwfN5UCinaO/0gSkgTpWSvbeh6ard
nRmImUfymn2fLh49qqjk/vMVtOjGc1UL2wWmWlCXUSdalsAcG4oaqJgUw1R2KQjq
pxSKp494LtDVzIVy3FywxQ9LEtwh2ps5a3A4KYGstUUmOvvnkbVRFD4sxdx7ZFwk
OtJlYpvlJAw=
=/h6n
-----END PGP SIGNATURE-----
