It seems that if you are only concerned about the length extension property,
you could make the last compression function in the chain different from all
other compression functions. For example, if sha() is the compression function
for SHA1 and md() is the compression function for RIPEMD --- both compress
512 bit blocks into 160 bit blocks using a 160 bit IV ---, you could define
SHA1-X (which is not length extending) as
X
|
V
IV -> sha() -> output
for X < 512 bits and
block1 block2 last block
512 bit 512 bit 512 bit
| | |
V V V
IV -> md() -> md() ....... -> sha() -> output
This way you do not need an extra compression step. It is of course necessary
that md() and sha() are sufficiently different so that given md(x) you cannot
compute sha(x) or vice versa (or that this at least as hard as inverting md(x)
or sha(x)).
Generalising the non-length-extension property, I would expect a `good' hash
function to make it hard to compute h(a || b || c) given h(b), for bitstrings
a,b,c where either a or b may be empty.
Regards,
Jaap-Henk
On Mon, 10 Jul 2000 15:56:33 -0500 John Kelsey <[EMAIL PROTECTED]> writes:
> -----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-----
>
--
Jaap-Henk Hoepman | Come sail your ships around me
Dept. of Computer Science | And burn these bridges down
University of Twente | Nick Cave - "Ship Song"
Email: [EMAIL PROTECTED] === WWW: www.cs.utwente.nl/~hoepman
Phone: +31 53 4893795 === Secr: +31 53 4893770 === Fax: +31 53 4894590
PGP ID: 0xF52E26DD Fingerprint: 1AED DDEB C7F1 DBB3 0556 4732 4217 ABEF
