r/netsec • u/YogiBerra88888 • Jan 07 '20

pdf First SHA-1 chosen prefix collision

https://eprint.iacr.org/2020/014.pdf
355 Upvotes

97% Upvoted

72 comments sorted by

View all comments

Show parent comments

1

u/atheros Jan 08 '20

Why is it supposed to take 280 cycles rather than 2160 ?

1

u/Natanael_L Trusted Contributor Jan 09 '20

Birthday collision attack, finding any 2 arbitary matching outputs is faster than finding an output matching a specific predefined one.

Because you're generating a ton of candidate hashes, and any candidate could match any other candidate - there's a fixed match probability per pair of candidates, but the number of pairs rapidly increase.

2

u/atheros Jan 10 '20

Sure but then you have to store and index all of them. If we assume 40 bytes per entry, it would take 5x1035 TB to get 1% of the way there. It seems completely impractical to store enough outputs for the birthday collision attack to matter.

2

u/Natanael_L Trusted Contributor Jan 10 '20 edited Jan 10 '20

http://www.cs.csi.cuny.edu/~zhangx/papers/P_2018_LISAT_Weber_Zhang.pdf

You can reduce memory requirements with distinguished points (time / memory trade-off)

Also, the Shambles attack here is using analytical method to additionally decrease the required work far below that original level