Hacker News Reader

Comment by randomtoast | Hacker News Reader

Grovers algorithm can brute-force a 128-bit symmetric cryptographic key in roughly 2^64 iterations (on a quantum computer which we likely have in 50 years), instead of 2^128. Now, lets find another attack vector (maybe with the help of AI) that reduces the 64 a bit and you are in the realm of feasibility.

View on HN

2^64 work that is non-paralellizable isn't a threat. 64 bits of classical security is insufficient because computers can do thousands of operations in parallel, and you can combine the effort of millions of computers. Grover's algorithm gives you a sequential complexity of 2^64, so if you have a quantum comptuer with a clock speed of 20GHZ (current quantum computers are in the khz to low mhz range), and you pretend that the quantum computer can process 14 rounds of AES per clock cycle (in reality it would be hundreds of cycles), it will take a quantum computer running for 30 years continuously to crack a single key (and if the temperature ever rises 1 millionth of a degree or the computer loses power for a nanosecond, you have to start over).

But everyone will upgrade to AES-256 (many system already has), and that truly will be the final symmetric algo even with moore's law.

MD-5 died the same way. We had to scare people into investing into upgrading to SHA-1 by showing them the slope of hardware and the variability in new breakthroughs and ask if they'd rather have an emergency that lasted for over a month or work it into the schedule among the other requirements now?

Yes, people can upgrade but nobody fucking will until you impress upon them how stupid they're being by gambling the entire company on carrying that debt for another year.

Only those who can change. In work in embedded systems - we still have to talk to machines that were built with exportable encryption in the 90's (read if it isn't broken that is only because nobody who has a clue has bothered to try). They can't be upgraded anymore so I have to keep those algorithms building just in case someone wants to mix new with old. (fortunately the old machines are never internet connected so vulnerability requires local access - but the vulnerability is in safety critical functions so I don't rest too easy)

I use the SHA-1 example in part because that was the newest hash that a bunch of smart cards someone wanted to try to use with our system supported.

Of course the max RSA key lengths on the card weren't up to it anyway (kids: if you by crypto hardware and don't use it immediately, don't warehouse it looking for a problem for your solution), but at least I got to put my foot down and we only shipped with SHA-1 and SHA-2 support

Reply on news.ycombinator.com