3 ms·
Quantum attacks against all of the SHA-3 submissions
- Robin_Message 16y agoIn brief, a quantum computer of ~10000 qubits running Grover's algorithm can find a structured preimage in expected time O(2^(N/2)), which breaks the security claims of 11 of the candidates, who claim no attack better than brute force is possible (which is O(2^N)). Of the other three, 2 make no explicit claim, and only one explicitly states the quantum attack. That said, O(2^(N/2)) on N of 224 bits is still O(2^112) operations on a quantum computer several orders of magnitude larger than those we have already, so the problem here is an inaccurate claim of security by the submissions, not a practical attack. (2^112 is a million computers, working at one operation per nanosecond, running for 164646653302 years, but attacks do only get better...)