Quantum computing and cryptography

System

This discussion was created from comments split from: Two-factor apps.

jimmyweg

I'll worry more when quantum computing advances a bit further :)

....

Yep. We are not facing the Cryptopacalypse, despite what some hand wringing headlines might suggest.

It may be closer than we think's closer than we think: https://www.nytimes.com/2019/10/23/technology/quantum-computing-google.html?te=1&nl=the-privacy project&emc=edit_priv_20191029?campaign_id=122&instance_id=13454&segment_id=18333&user_id=ac2e804544bf813552ce25c6ddaa0fa5&regi_id=70503732

AGAlumB

Not quite there yet.

could allow new kinds of computers to do calculations at speeds that are inconceivable with today’s technology [...] “The original Wright flyer was not a useful airplane,” said Scott Aaronson, a computer scientist at the University of Texas at Austin who reviewed Google’s paper before publication. “But it was designed to prove a point. And it proved the point.”

Great analogy, and my own emphasis on the future-tense reference to nascent technology which has potential but is not here yet. Baby steps. We'll get there in time, I'm sure. Like what the Wright Brothers built, I suspect what we end up with will look nothing like what's being worked on in labs today. Very exciting, since if it pans out we'll all have quantum computers one day, to help protect our data too. :)

jpgoldberg

[The Cryptopacalypse] may be closer than we think

Google's achievement is really important, but it doesn't really change estimates of the time line except for those who were skeptical about the possibility of quantum computers. Here is an excerpt of something I wrote in February.

I wouldn’t be surprised if it turns out that [cryptographically relevant quantum computers] aren't possible at all. It may be that the “cost” of building bigger QCs grows super-polynomially with the number of qubits. If that is the case, then even in a world of QCs, we have the easy/hard asymmetry that is needed for cryptography to work. (Of course, that is just speculative, and we shouldn’t bet on it.)

That sort of speculation is now put to rest by Google's achievement. But unless you were someone under the belief that the relevant sort of quantum computers were fundamentally impossible, their result doesn't really change how quickly we can expect them to come about.

jimmyweg

It's all very interesting. Before I retired about three years ago, a small part of my job required password cracking (typically Windows), and I ran a one GPU-based machine. I thought 9 billion pps was phenomenal! While I didn't encounter many encrypted RARs, I never cracked one (much slower speeds). I'll worry about QCs if I'm still around when they become a little more relevant. BTW, I'm still impressed with 1P, and I've used or tested many of the "leading" tools. It may require an extra click here and there, but I like its consistency; I don't have to contact tech support every week! :)

AGAlumB

Not having to contact tech support is a feature I value too. :lol: But we're happy to hear from you whether you need help or just want to discuss things like this. Have great weekend! :chuffed:

jpgoldberg

QC is not going to affect password cracking for a very very long time (if ever). The relevant quantum algorithm for something like password cracking or searching for a key is Grover's algorithm. Grover's algorithm reduces to search time for something to its square root. So it effectively reduces the keysize by half. So other things being equal (which they are not) Grover's algorithm turns something like a 128 bit AES key into a 64 bit key or a 256 bit key into a 128 bit key. So in the worst case, the worlds solution to the threat of Grover's algorithm is to double key sizes. This, by the way, is why AES is designed to have 256 bit keys. 128 bit keys are more than enough for a very long time to come unless QC's running Grover's algorithm for key cracking become practical.

But there is a really important thing to keep in mind about Grover's algorithm. The whole process of verifying a single guess and the generation of a guess must all be appropriately entangled with the rest of the process. We can't put the guess verification part into a non-quantum computer (or a separate one). So not only would the required quantum computer be really big to do all of that computation internally, it needs to be able to stay coherent long enough to do the full job. So even if something running Grover's algorithm could reduce what what take many times the age of the universe to complete to just a few hours, the whole enormous QC has to stay together for those hours.

Perhaps, someday, this will be a threat to 128 bit AES keys as generating a new guess is easy, and the verification of a guess is a much smaller task than verifying a password guess. but even then that is an awful lot that needs to be put into a quantum computer.

Keep in mind that you shouldn't think of QCs as just super-fast computers. The idea is that there are some specific problems which they can solves in far fewer steps than classical computer can. It is not a general speedup. Testing a single password on a quantum computer isn't going to be faster than on a classical computer, it's just that a QC effectively has to perform fewer complete tests when trying to find one that works.

chrisdidge

Interesting thread, here. I came to the forum to suggest that AgileBits prepare for quantum cracking as well as quantum encryption. I haven't read it, but flipped through a book I want to read eventually, called Cryptography Apocalypse: Preparing for the Day When Quantum Computing Breaks Today's Crypto, by Roger Grimes. I was impressed that it wasn't entirely dedicated to fear-mongering but presented solutions going forward. I know that AgileBits will stay on top of this topic. Thanks, folks, for integrating TOTP into 1P so elegantly!

Ben

Thanks for taking the time to share your thoughts, @chrisdidge. :)

Ben