[358] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Munro Saunders)
Sun Mar 16 20:34:08 1997
From: Munro Saunders <munro@ci.com.au>
To: kelsey@email.plnet.net
Date: Mon, 17 Mar 1997 11:29:33 +1100 (EST)
Cc: coderpunks@toad.com, cryptography@c2.net
In-Reply-To: <MAPI.Id.0016.00656c73657920204533353330303034@MAPI.to.RFC822> from "John Kelsey" at Mar 14, 97 05:48:24 pm
I imagine that John Kelsey may have written:
> >From: Me
> >To: Paulo Barreto
> >Cc: coderpunks@toad.com
Not sure how this ended up on cryptography list. Which would be fine.
Except that I had decided to think some more.
Paulo Barreto has already described a technique to me (and coderpunks)
which with a variation and extra passes reduced storage required to
2 * 2^80 bits. John Kelsey made us aware of cycling techniques
that allow the storage requirement to vanish at the cost of
more processing. So my consern about storage may not apply.
(2^80 is still a lot of space to search.)
John Kelsey pointed out that the messages with identical
hashes need not be entirely 'random' (which is what I had
be thinking but didn't say when I put random in quotes).
(Have 56575838628573874984583764588334857 nice days.)
I suggested that the mutiple hashes of similar data (suggested
by Paulo Barreto) was secure if the original hash was secure.
I didn't need John Kelsey's encouragement to decide this
is not neccessarily true (John raises some other concerns).
There is a simple way of modifying any hash function,
weakening it by only one bit, which would made _a_ double
hashing scheme only as secure as single hashing.
(I will post details later, after more careful consideration.)
> >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.
...
> >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
...
> I think you can do something similar with the cycling attacks,
> by using the output from the hash to select message variations.
This will work. There is a slightly simpler way. Just hash on the 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
...
John Kelsey raises various other concerns about the suggested multiple
hashing scheme to which I have no immediate comment.
> 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
...
--
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
