Possibly new result on truncating hashes

[Hal Finney]

Joseph Ashwood writes:
> From: "John Kelsey" <kelsey.j at ix.netcom.com>
> > Now, this is an attack on SHA256 truncated to 160 bits.
> > Does it lead to an attack on SHA256 as a whole?
>
> Actually it does. Such an attack would reduce the difficulty of producing a 
> collision in SHA-256 to 2^(64+(96/2)) or 2^112. The math for this is fairly 
> easy, the remaining 96 bits will collide in on average 2^(96/2) tries, since 
> it takes 2^64 work for each of these tries, we get 2^112 work, hence an 
> attack on the original hash has been found.

No, this doesn't (necessarily) work.  The Wang-type attacks may generate
pairs that collide in the left 160 bits, but such that each collision
has a unique value in those leftmost bits.  For example, the collision
pairs may be of the form:

L1||R1
L1||R2

where L1 is the left 160 bits that match, and R1 and R2 are the right 96
bits which differ.  Run the algorithm again and you get a new collision:

L2||R3
L2||R4

And another:

L3||R5
L3||R6

The point is that L1, L2, and L3, which are the colliding left 160 bits in
each pair, are different.  If you got lucky and R6 matched R1, it doesn't
represent a 256 bit collision, because the left halves aren't the same.

Now, if the algorithm were different and it generated pairs such that
all the L values matched each other, then you would be right.  But that
doesn't matter, for two reasons: first, the Wang attack doesn't work that
way; and second, even if it did, this analysis has to look at the worst
case, and there would still be conceivable attacks that work in the way
shown above.  Given that we are trying to show a black-box reduction from
collisions in the leftmost bits to collisions in the whole function,
we have to make the most unfavorable assumptions about the nature of
the algorithm.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com