[345] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (John Kelsey)
Fri Mar 14 20:36:51 1997
To: "Perry's Crypto List" <cryptography@c2.net>
Reply-To: kelsey@email.plnet.net
From: John Kelsey <kelsey@email.plnet.net>
Date: Fri, 14 Mar 97 17:48:24 CST
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Perry's Crypto List ## Date: 03/14/97 01:16 am ##
Subject: Re: Q: security of 2-barreled hashing ]
>From: Munro Saunders
>Subject: Re: Q: security of 2-barreled hashing
>To: Paulo Barreto
>Cc: coderpunks@toad.com
>Date: Thu, 13 Mar 97 22:0
>I imagine that Paulo Barreto may have written:
>
>> It is well known that a 160-bit hashing function like SHA1 is
>> susceptible to a birthday attack of O(2^80) complexity.
>> A question arises as to whether there is a possibility to cure
>> this by running a 2-barreled version of SHA1 which has 2 SHA1
>> contexts, one of which is (say) fed an extra constant byte
>> after initialization.
>1. A O(2^80) birthday attack is not a bug, its a feature.
> In involves storing and sorting ~10*2^80 bytes.
> Thats about 160 cubic kilometres of DAT tapes (approx).
> (Its not going to happen.)
Actually, you can get around the memory requirements using some
cycling techniques. The discussion of the cycling
attack on hash functions in the CRC Handbook is pretty good.
Basically, if h() is a random function mapping 160 bits to 160
bits, then we expect x=h(x) to start cycling after about 2^{80}
iterations. We keep track of occasional x values we've seen
before, and when we see one repeating, we know we're on a cycle.
(The occasional x values have to have some identifying trait.
For example, they could be values with the low 24 bits all
zeros.) By knowing the order of our occasional x values, we can
narrow down the search of specifically where the cycle occurs
pretty effectively, and so we have to do a little backtracking,
but nothing like another 2^{80} search. This lets you use very
little memory, and it's configurable--more available memory
speeds up the search, since you can store more of those
occasional x values, and so find the actual pair of inputs that
lead to the collision a little bit faster.
>2. Even the O(2^64) birthday attack on MD5 (etc) is
> not really a problem (as compared to the cryptographic
> weakness recently found). In this case you should
> evaluate your protocol: what would be the effect
> off two different but 'random' messages which hash
> to the same thing?
No. For a straight birthday attack, you can simply generate
2^{64} slight variations of the same message. This is a lot
easier than it sounds. For example, choose 64 places in a
digital document to either add or not add a space. Treat no
extra space as a zero bit and an extra space as a one bit, and
cycle through all 2^{64} possible variations. Hash functions
helpfully give you that neat property that even very small
changes in the input cause radical changes in the output, so
each of these hash values should be radically different. (The
CRC Handbook says that Gideon Yuval came up with this clever
idea.)
I think you can do something similar with the cycling attacks,
by using the output from the hash to select message variations.
(That is, choose 160 points in the message to either insert or
not insert a space, based on the next hash output.)
>3. If SHA1 (for example) is a secure hash (of 160 bits) then
> prepending (n different constant) strings to the input
> should give independent hashes (which concatenated give
> n*160 bits). If the resulting hash is not secure then it
> would represent a weakness in the original algorithm.
This is clearly true if SHA1 approximates a random function. Of
course, there's at least one place where we can immediately see
that it *doesn't* approximate a random function: If I know
SHA1(X), I can compute SHA1(X||Y) where || is concatenation and
I know Y, but not X. This is what makes the simple
length-extending attack on one hash-function-based MAC possible.
I would be uneasy trusting SHA1 to behave like a random function
with respect to an attacker who can do 80-bit searches, because
SHA1's intended design strength is only 80 bits. If you need
more than 80 bits of security, then you may need another hash
function. (Unfortunately, you'll also need a slower hash
function, all else being equal.) Check out Snefru-8, with the
256-bit block, or wait a couple more years for cryptanalysis
results, and then consider using Tiger, whose 192-bit block
implies resistance to attackers with up to 96 bits of
brute-force ability.
If you need to do the superhash(X) = SHA1(X)||SHA1("1"||X) kind
of construction, you may want to do something like a pair of
HMACs with different key values. This will add a couple more
compression functions, but it looks a lot less likely to exhibit
some nasty nonrandom property than does the simple construction
you're describing. Still better might be something like
superhash(X) = SHA1(X)||RIPE-MD160(X). I still doubt that this
gives you a real 320-bit hash, though.
> (Waves hand in general direction of supposed proof
> and quickly jumps into flame proof bunker.)
Isn't the protocol here something like ``These proofs will
appear in the final paper?'' :)
>Munro Saunders Limping around with my old cat. P.O. Box 192,
>munro@ci.com.au I am not an official spokesperson ERSKINEVILLE 2043
>+61 2 9564 6368 for Elvis, IBM, M$ or Corinthian. AUSTRALIA
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMyni/0Hx57Ag8goBAQF+NwP+N0X/d2XLnWGsdQcxF8M99ra8FQCXf5SN
iEawJJFiBQGjR7GHHfoVTuICKhRTD9q+k4jMFxLTPWyBPQc0MnvWtC+czgeaS0+o
kLFk6iT4rRVz+yi4F3DIbTkX0T5S6BY4rEKsA9csHVxLw5z4w30MT8Do0HbYqLtc
Rog5myeY/rE=
=+8w7
-----END PGP SIGNATURE-----
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
