AW: Possibly new result on truncating hashes

[Kuehn, Ulrich]

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 at metzdowd.com