[18035] in cryptography@c2.net mail archive
AW: Possibly new result on truncating hashes
daemon@ATHENA.MIT.EDU (Kuehn, Ulrich)
Tue Aug 2 10:06:46 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Kuehn, Ulrich" <Ulrich.Kuehn@telekom.de>
To: kelsey.j@ix.netcom.com, cryptography@metzdowd.com
Date: Tue, 2 Aug 2005 08:40:24 +0200
John Kelsey wrote:
> Unfortunately, we can't make this argument, because this
> postulated collision algorithm can't be used to find a
> collision in the whole SHA256 more efficiently than brute force.
>
> Let's do the counting argument: Each time we call the
> 160-bit collision algorithm, we get a new pair which has the
> same first 160 bits of SHA256 output, and random unrelated
> last 96 bits of SHA256 output. Each pair has a probability
> of 2^{-96} of colliding in the remaining bits. So, to get a
> collision on the whole SHA256 using this 160-bit collision
> algorithm, we expect to have to try about 2^{96} collision
> pairs, each found at a cost of 2^{64}. The resulting work is
> 2^{64} * 2^{96} = 2^{160}, more than a straight brute-force
> collision search on SHA256.
>
Hmm, wouldn't you expect a lot of partial collisions among all those 2^96 collision pairs? That is, after
2^80 runs of the algorithm you would obtain your first partial collision in collision pairs, don't you?
For 2^96 that's roughly 2^32 such pairs of pairs. Those might help you to speed up your search.
Am I missing something here?
Ulrich
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
