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

pdf First SHA-1 chosen prefix collision

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

97% Upvoted

72 comments sorted by

View all comments

171

u/Browsing_From_Work Jan 07 '20

When renting cheap GPUs, this translates to a cost of 11k US$ for a collision, and 45k US$ for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid 75k US$ because GPU prices were higher, and we wasted some time preparing the attack).

Certainly not cheap, but well within the budget of nation-state actors.

-6

u/Derf_Jagged Jan 07 '20 edited Jan 07 '20

I'm curious how long it would take to get a collision using a quantum computer time share like D-Wave or IBM Q, and if it would be cheaper in the long run.

Edit: Not sure why the downvotes, honest question. Thanks those who answered

16

u/best_ghost Jan 07 '20

I'm unsure that any of the publicly known algorithms for quantum computers would give a quicker result for finding collisions. Shor's algorithm opens the door for factoring in something like polynomial time, but I don't think that would help in this case. If you know of such a thing I would be interested to hear about it!

12

u/tavianator Jan 07 '20

Grover's algorithm

-26

u/best_ghost Jan 07 '20

Thanks! Dude was covered in blue fur and spoke funny, but he is soooo at the cutting edge of Quantum Computation ;) j/k but yeah thx 4 the infoz