Quantum of Solace
October 2, 2015 1:07 PM Subscribe
Quantum cryptography could render all our protections worthless soon(ish). But cunning cryptographers have other tricks up their sleeves.
It's also possible that making viable quantum computers could have the collateral requirement of making viable quantum teleportation. One would sort of offset the other... for those with access to both technologies.
posted by paper chromatographologist at 1:24 PM on October 2, 2015
posted by paper chromatographologist at 1:24 PM on October 2, 2015
"Even if quantum computers existed today"
They kinda already do.
posted by I-baLL at 1:24 PM on October 2, 2015
They kinda already do.
posted by I-baLL at 1:24 PM on October 2, 2015
Sorry, quantum computers that are practical for factoring large integers.
posted by yeahwhatever at 1:26 PM on October 2, 2015
posted by yeahwhatever at 1:26 PM on October 2, 2015
In a scenario it calls ‘intercept now, decrypt later’, a nefarious attacker could start intercepting and storing financial transactions, personal e-mails and other sensitive encrypted traffic and then unscramble it all once a quantum computer becomes available. “I wouldn’t be at all surprised if people are doing that,” says Jordan.
Yea, me either.
posted by T.D. Strange at 1:27 PM on October 2, 2015 [4 favorites]
Yea, me either.
posted by T.D. Strange at 1:27 PM on October 2, 2015 [4 favorites]
Strong symmetric ciphers, algorithms that use the same key for encryption and decryption (AES, Blowfish, etc.) will also be easier to crack with quantum computers, but only by roughly a factor of two. So if you are happy with AES-128 today, you’ll be happy with AES-256 in a quantum-computing future.
I was personally concerned about this. Lastpass is AES-256. Keypass is AES/twofish at 256b it as well. I'm a bit less worried, I guess, but would still prefer to bump that up a bit.
posted by bonehead at 1:30 PM on October 2, 2015
I was personally concerned about this. Lastpass is AES-256. Keypass is AES/twofish at 256b it as well. I'm a bit less worried, I guess, but would still prefer to bump that up a bit.
posted by bonehead at 1:30 PM on October 2, 2015
Wow, it's nearly twenty years to the day that I was learning about the theoretical impacts of quantum computers to cryptography in an undergraduate algorithms course. The big difference now is that it appears the theory will achieve implementation.
The two biggest threats as I see them are:
1. A bad actor achieving capability ahead of and obscured from public awareness. If this secret is kept it could allow all sorts of manipulations to systems for a very long time. This could be very bad. This is what I'm afraid (as in, fairly certain) the NSA would love to achieve. I guess maybe just hope "our guys" manage it before "the others" do?
2. Even if active and in-use systems are updated, there is a whole lot of encrypted and archived data out there. If it suddenly became trivial to access the data in these archives there is suddenly a large target that is looking much less secure than currently assumed. And we can take it as a given that re-archiving for increased security will be done by very few and usually "too late".
posted by meinvt at 1:32 PM on October 2, 2015 [2 favorites]
The two biggest threats as I see them are:
1. A bad actor achieving capability ahead of and obscured from public awareness. If this secret is kept it could allow all sorts of manipulations to systems for a very long time. This could be very bad. This is what I'm afraid (as in, fairly certain) the NSA would love to achieve. I guess maybe just hope "our guys" manage it before "the others" do?
2. Even if active and in-use systems are updated, there is a whole lot of encrypted and archived data out there. If it suddenly became trivial to access the data in these archives there is suddenly a large target that is looking much less secure than currently assumed. And we can take it as a given that re-archiving for increased security will be done by very few and usually "too late".
posted by meinvt at 1:32 PM on October 2, 2015 [2 favorites]
A bad actor achieving capability ahead of and obscured from public awareness
SETEC ASTRONOMY
posted by gwint at 1:40 PM on October 2, 2015 [11 favorites]
SETEC ASTRONOMY
posted by gwint at 1:40 PM on October 2, 2015 [11 favorites]
D-Wave always comes up in these discussions, but nobody actually explains why. D-Wave is made up of discrete "qubits" – that is, individual bits and not entangled ones. The whole concept of Shor's algorithm is that there is a projection you can do over a quantum register that will either result in the factorization of the number stored in the qubits, or nonsense. There's a 50/50 chance, so you just repeat it several times and try each result. However, it relies on the bits being entangled with each other and impacting each other's states, which doesn't happen in D-Wave.
As far as I know, there are 14-qubit registers that have been created. 128-bit encryption requires a tenfold increase. So "at least 10 years" out, which as always means "it could happen but we have no idea when."
posted by graymouser at 2:07 PM on October 2, 2015 [4 favorites]
As far as I know, there are 14-qubit registers that have been created. 128-bit encryption requires a tenfold increase. So "at least 10 years" out, which as always means "it could happen but we have no idea when."
posted by graymouser at 2:07 PM on October 2, 2015 [4 favorites]
Iay avehay aay ewnay ystemsay orfay ryptocay. MPay emay.
posted by Artful Codger at 2:52 PM on October 2, 2015
posted by Artful Codger at 2:52 PM on October 2, 2015
A mhzqe A Bwol gbe.
Ug vzeph, cf dlilj Bqdj
qc nzmad gml dhvwea cbotrmy gv.
Zvde qg lhpax'x jxocry gh ni lblshfq.
Mt ocxceka mp czi.
posted by dmd at 5:14 PM on October 2, 2015
Ug vzeph, cf dlilj Bqdj
qc nzmad gml dhvwea cbotrmy gv.
Zvde qg lhpax'x jxocry gh ni lblshfq.
Mt ocxceka mp czi.
posted by dmd at 5:14 PM on October 2, 2015
I feel like I've read something that emphasized that quantum cryptography and cryptanalysis using quantum computers are two different things.
posted by XMLicious at 5:57 PM on October 2, 2015 [1 favorite]
posted by XMLicious at 5:57 PM on October 2, 2015 [1 favorite]
It will not suprise me if it is revealed one day that the NSA, the Russians and the Chinese all have had working quantum computers for years and are very far ahead of the current known state of the art. It seems to me that the machine would be so valuable that they would pay pretty much anything to keep to themselves and its existence hidden for as long as possible.
posted by humanfont at 7:04 PM on October 2, 2015
posted by humanfont at 7:04 PM on October 2, 2015
It seems like quantum computers would offer too many tempting capabilities that would make their use evident to the broader scientific or security communities, which in your scenario the NSA and the Russian government and the Chinese government would all have to refrain from using to keep it all secret. (So for example, nothing in the Snowden revelations would betray use of quantum computers, or it would all need to be a ruse.) I wish the Quantum Algorithm Zoo page linked to from the first article had more specifics about what breaking each barrier would provide in downstream-from-pure-mathematics terms.
As mentioned in the comments of the first article, theoretically one-time pad encryption, which requires large amounts of genuinely random numbers, will remain unbreakable regardless of computational power available if I understand it correctly. A detail I appreciated in Vernor Vinge's "Zones of Thought" science fiction novels was that immense quantities of these numbers were a type of cargo traded among alien civilizations.
posted by XMLicious at 8:20 PM on October 2, 2015
As mentioned in the comments of the first article, theoretically one-time pad encryption, which requires large amounts of genuinely random numbers, will remain unbreakable regardless of computational power available if I understand it correctly. A detail I appreciated in Vernor Vinge's "Zones of Thought" science fiction novels was that immense quantities of these numbers were a type of cargo traded among alien civilizations.
posted by XMLicious at 8:20 PM on October 2, 2015
As mentioned in the comments of the first article, theoretically one-time pad encryption, which requires large amounts of genuinely random numbers
Not just a large amount, but an encryption-decryption key the same length as the plaintext - which imposes some pretty fundamental limitations on their usefulness. Plus as mentioned above, existing symmetric ciphers are (to the best of our knowledge) plenty resilient against quantum computing. The problem is that the most popular solutions to problem of distributing symmetric keys - are not.
posted by atoxyl at 9:25 PM on October 2, 2015 [2 favorites]
Not just a large amount, but an encryption-decryption key the same length as the plaintext - which imposes some pretty fundamental limitations on their usefulness. Plus as mentioned above, existing symmetric ciphers are (to the best of our knowledge) plenty resilient against quantum computing. The problem is that the most popular solutions to problem of distributing symmetric keys - are not.
posted by atoxyl at 9:25 PM on October 2, 2015 [2 favorites]
I wouldn't worry too much about quantum crypto presently
Maybe you shouldn't, but people should be -- we need to figure out resistant systems *before* large qbit quantum computing happens. If we haven't, there's an extended period when the Internet becomes completely readable.
We need to develop the crypto systems, beat on them hard to prove them out, and then get them deployed across the net, server and client side. It is not a trivial problem.
Starting 15 years before it happens is a good thing.
As mentioned in the comments of the first article, theoretically one-time pad encryption, which requires large amounts of genuinely random numbers, will remain unbreakable regardless of computational power available if I understand it correctly.
Yes, but. The key has to be the same size as the data, you can only use a given key once, so you need a truly massive channel to handle keys, and key security is incredibly important. You ship a key, somebody steals the keybook, and you're compromised. Use the same key twice, and if the bad guys get both encrypted messages, they can XOR them together and get the two message plaintext combined, which is a trivial decryption task.
One time pads are basically unworkable in the real world. The few cases that use them, like diplomatic communications, spend huge amounts of time, manpower and money dealing with getting keys into the right places in a secure fashion, and making *damn* sure they're never ever reused -- as the Soviets found out when they did that and we read the traffic.
And, another difficulty -- you're key generator has to be *truly* random. If it's pseudorandom, then you can spot the patterns, figure out how to generate the "random" keystring, and read the traffic. The Lorenz cipher was, for all intents, OTP with a psudeorandom number generator that used the initial state of the PRNG as the key, and when the Germans screwed up and send two messages (actually, the same message twice, but not *exactly* the same message), that enabled the Allies to not only read that message, but figure out how the PNRG worked, which let them read traffic almost in real time.
So -- if your key stream is truly random, you never ever reuse a key, and you have a channel to securely distribute the keys, which again, are massive, then OTP works.
IOW, OTP almost never ever works in the real world.
posted by eriko at 3:11 AM on October 3, 2015 [2 favorites]
Maybe you shouldn't, but people should be -- we need to figure out resistant systems *before* large qbit quantum computing happens. If we haven't, there's an extended period when the Internet becomes completely readable.
We need to develop the crypto systems, beat on them hard to prove them out, and then get them deployed across the net, server and client side. It is not a trivial problem.
Starting 15 years before it happens is a good thing.
As mentioned in the comments of the first article, theoretically one-time pad encryption, which requires large amounts of genuinely random numbers, will remain unbreakable regardless of computational power available if I understand it correctly.
Yes, but. The key has to be the same size as the data, you can only use a given key once, so you need a truly massive channel to handle keys, and key security is incredibly important. You ship a key, somebody steals the keybook, and you're compromised. Use the same key twice, and if the bad guys get both encrypted messages, they can XOR them together and get the two message plaintext combined, which is a trivial decryption task.
One time pads are basically unworkable in the real world. The few cases that use them, like diplomatic communications, spend huge amounts of time, manpower and money dealing with getting keys into the right places in a secure fashion, and making *damn* sure they're never ever reused -- as the Soviets found out when they did that and we read the traffic.
And, another difficulty -- you're key generator has to be *truly* random. If it's pseudorandom, then you can spot the patterns, figure out how to generate the "random" keystring, and read the traffic. The Lorenz cipher was, for all intents, OTP with a psudeorandom number generator that used the initial state of the PRNG as the key, and when the Germans screwed up and send two messages (actually, the same message twice, but not *exactly* the same message), that enabled the Allies to not only read that message, but figure out how the PNRG worked, which let them read traffic almost in real time.
So -- if your key stream is truly random, you never ever reuse a key, and you have a channel to securely distribute the keys, which again, are massive, then OTP works.
IOW, OTP almost never ever works in the real world.
posted by eriko at 3:11 AM on October 3, 2015 [2 favorites]
duffell: “But cunning cryptographers have other tricks up their sleeves."John has a long mustache."
Switching to paper?”
posted by ob1quixote at 8:21 PM on October 3, 2015
NSA advisory sparks concern of secret advance ushering in cryptoapocalypse
Once elliptic curve crypto was viewed as a savior. Now its future looks doomed.
posted by XMLicious at 11:21 PM on October 23, 2015
Once elliptic curve crypto was viewed as a savior. Now its future looks doomed.
posted by XMLicious at 11:21 PM on October 23, 2015
« Older "Barbaric Cultural Practices" | German soldiers who fought in the American... Newer »
This thread has been archived and is closed to new comments
But hey, take it with a grain of salt. Conjecture on articles that are also conjecture.
posted by yeahwhatever at 1:20 PM on October 2, 2015 [4 favorites]