Slashdot Mirror
Cryptographers Brace For Quantum Revolution
Tokolosh writes: An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.
007 movie title
This is a First Post, and yet it is not... I have successfully achieved the simultaneous on/off state of First Posts....
This is exactly the sort of situation where the NSA could be the most useful/helpful to us - but no one in tech will trust them to provide actually secure encryption protocols because of their elliptic curve shenanigans.
#DeleteChrome
They'll force us to have passwords like "$myBigLongPassword47367@#LongLongOhHolyMoley!528"
Table-ized A.I.
Nothing to see here.
Until you open the box!
RSA factorization using today quantum registers is more than useless; The last year largest number processed was: 56,153. The quantum decoherence is faster when the number of particle increases; And to defeat the RSA some huge quantum registers are required. The only question: is a quantum machine that can process useful computing operation is even possible?
Quantum computers capable of cracking the higher keysizes that we we have now will never exist, and thus this concern is pointless. People who think otherwise aren't aware of the physics involved, and how the only people left researching making this shit don't believe it will ever work the way people want, they just keep going because it is their bread and butter now. Gotta feed the family.
It would stand to reason that there will also come of this, quantum encryption which is not crackable by quantum computing.
Ying and Yang are restored.
Yes, but the problem is the "record now" and "decrypt later" concept. To be secure, you have to know how long the data you are passing can be expected to remain obscured. How long does it take to decrypt it by doing a brute force - try every possible key - approach? If the data you are protecting goes stale in a year, you need to be assured that a persistent attacker won't decrypt your transmission in that time. For a lot of data being passed around, the stale dates are like 30 years in the future, which is a serious problem.
If advances in quantum computing happen and we get the huge jump in processing power they expect, what's currently a brute force time of years can become days or hours. This makes the recorded stuff from 5 years ago very valuable to the spooks who can now decrypt it overnight. And scares the daylights out of the folks who need that data to stay obscured for 30 years.
So, yes, future stuff will be harder to brute force because the same advances in computing power that make brute forcing possible faster will make encryption faster too, but having a treasure trove of easy to decrypt stuff recorded is what is feared.
"File to fit, pound to insert, paint to match" - Aircraft Maintenance 101
The world didn't end in the 1950's and the world won't end now. Technology will grow, people will learn it, and we'll move on with the times. Nothing to see here.
FWIW, The world didn't end in 1962 in our version of the multiverse, but for the action of one man...
Sometimes we just get lucky...
Isn't single pad encryption still safe, though less convenient?
Proudly brought to you by the singularity, powered by cold fusion.
They are not talking about breaking AES or Two Fish encryption. They are worried about breaking the key agreement. Currently when a communication channel is set up the two parties agree on a key for encrypting the communication. This is normally done by Diffie-Helman (D-H) key agreement or one party could select a key and then give it to the other party using the other parties RSA public key. Both RSA and D-H are based on the difficulty of solving math problems that quantum computing should be able to easily solve.
.
Your AES encrypted file on your hard disk is safe. What the NSA is doing is storing your conversations and the key agreement. Years from now they might crack the key agreement and then decrypt your communication..
.
Things like Elliptic curve Diffie Helman are secure. So your Black Berry communications will still be safe, not sure who else widely uses EC (your ZigBee electric meter in the USA and UK)
Yes, and as far as I know it is still used. But single pad has always been inconvenient enough that it has only been used for the most secret, because it is a huge PITA.
It is my sincerest belief that any people who think that any data that is relevant today genuinely needs to stay obscured for 30 years have sticks up their asses that need to be removed as soon as possible in the best interests of themselves and everyone they should ever meet.
File under 'M' for 'Manic ranting'
I still like to take Grover's algorithm as an example of a somewhat mind-bending quantum computing application. Its typical use case is the search problem, i.e. searching for a particular value inside some form of storage like a database, and it can do so in O(sqrt(N)), which is quite simply impossible in classical computing since you have to visit every entry at least once (hence O(N)) to perform a full search. Now, Grover's algorithm is probabilistic in nature, so you may need to repeat the algorithm to determine the correct value, but value verification for such problems is generally simple (since the problems are generally at most NP-complete and NP-completion implies a P-space verification algorithm given a solution) and the number of repetitions is expected to be constant.
Of course, you can note that parallelization legitimately can compete with Grover's algorithm for very large datasets and very large thread counts, but on a purely theoretical level I still find it fascinating.
It is my sincerest belief that any people who think that any data that is relevant today genuinely needs to stay obscured for 30 years have sticks up their asses that need to be removed as soon as possible in the best interests of themselves and everyone they should ever meet.
Then I think you are burying your head in the sand. I can see legitimate reasons where things will need to remain obscured for more than a lifetime, especially in specific cases where national security and defense secrets are involved. How old are the LGM-30 Minuteman missiles? The last one was purchased in 1970 or so, which makes them 40+ years old and I'm pretty sure you don't want to publish their specifications on the internet for all to see even now given we still depend on them for defense purposes..
"File to fit, pound to insert, paint to match" - Aircraft Maintenance 101
If advances in quantum computing happen and we get the huge jump in processing power they expect, what's currently a brute force time of years can become days or hours. This makes the recorded stuff from 5 years ago very valuable to the spooks who can now decrypt it overnight. And scares the daylights out of the folks who need that data to stay obscured for 30 years.
Problem with this is there has to be a rational basis to support beliefs. Responding out of fear alone without any capability to characterize risks associated with (in)action is simply a waste of time.
There is value in preparing for unforeseeable events. Having more cipher suites at the ready to easily allow you to jump ship if a key exchange, cipher, hash were compromised is useful.
Schemes such as layering complete systems such that if ECC is compromised your message is still protected by RSA... or if AES is compromised your still protected by Camellia or whatever are useful. When implemented properly they offer insurance against the unknowable at the cost of slightly more effort. (Maintaining separate trusts and redundant computations)
What isn't useful however are baseless fears that RSA or ECC will fall and responding by blindly picking something else out of fear alone. Nobody is currently able to prove most of currently deployed systems can't be compromised by some unforeseen discovery of a defect or advancements in mathematics. Without evidence without any way to characterize risk and make intelligent choices you are just flailing in the wind.
What is noticeably absent from TFAs is evidence to support worrying about QC. Please understand I fully expect QC to become a useful tool and unlock new capabilities... yet those who are seriously expecting to extract exponentially approaching infinite amounts of computation from the universe at costs exponentially approaching free are living in a fantasy world in my estimation. It's hard to imagine a more extraordinary claim coupled with current stunning lack of evidence QC is even possible.
Right now we have machines with a few cubits, analogous to a 1960 IC. It wouldn't surprise me too much if, in six years, we had machines with 2300 qubits. Maybe it'll be called the Intel Q4004. :)
In six years assuming anyone is still willing to waste their time and money there will very likely be "topological" quantum computers with 2300 qubits and they will be just as useless as desktop computers at cracking RSA. Real machines with 2300 entangled qubits would be able to perform operations that would not even be remotely possible in the current life of countless trillions of universes if every atom in every universe were a transistor operating at a trillion trillion trillion thz. It's completely bullshit.
As you probably know, for decades after, transistor counts doubled every TWO years. If the cubit count doubles every two years, that's going to be a problem for cryptography.
Moores law is a reflection of market forces. Doubling was enabled by halving cost enabled by market pressure to reduce costs enabling people to afford more capabilities for the same cost which fueled a never ending feedback loop.
There is no analogue to QC and BTW number of entangled qubits are NOT doubling every year.
We don't know if that's possible, but we didn't know that 386 was possible in 1970.
Nonsense it was then and mostly continues today to be an engineering problem.
Nobody has any idea how to scale out QC without being drowned out by noise.
Quantum Computing does _not_ scale, as it cannot subdivide problems. You argument is completely bogus and in fact shows the opposite of what you think it shows.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Isn't single pad encryption still safe, though less convenient?
Yes, but that only moves you down one turtle. You still need a way to securely disseminate the pads.
Isn't single pad encryption still safe, though less convenient?
One-Time Pads, implemented and used correctly, are provably secure. That can never change, not even given infinitely-fast computers (which Quantum Computers aren't), because the proof demonstrates that the ciphertext gives you NO information about the plaintext. No amount of computation can extract information from an empty set.
However, one-time pads are also pointless. Oh, there are some very isolated contexts in which they can be usefully applied, but they're useless for nearly everything we use cryptography for today. The one-time pad scheme requires securely distributing the pad, which must be as large as the message to be sent. If you have some channel you can use to distribute the pad securely, why not just use that channel to send the message?
Symmetric cryptography (e.g. AES) improves on the one-time pad by reducing the size of the key material from as large as the message (possibly many gigabytes) to something very small. Say, 16 bytes. So you give up provable perfect secrecy in exchange for only needing a way to securely distribute 16 bytes.
Asymmetric cryptography (e.g. RSA) improves on symmetric cryptography by eliminating the need for every pair of potential communications endpoints to securely exchange symmetric keys. Instead, every potential recipient can publish a its "public" key to every potential sender. This distribution of public keys does need to be secure, but the security requirement is weaker. Symmetric keys need to be kept secret, public keys do not; instead we only need to ensure their integrity, that the potential sender got the actual public key of the potential recipient.
Asymmetric cryptography can be used to further reduce the scope of this problem by using its ability to digitally sign certificates, proving the legitimacy of a given public key assuming (a) the recipient of the certificate has securely received the public signing key and (b) the private signing key is not compromised and is only used to sign legitimate public keys. Thus, the key distribution problem is reduced to a "bootstrapping" problem; we just have to get Certificate Authority key(s) securely. In practice we do this by distributing the bootstrapping keys in system software.
However, asymmetric cryptography has a lot of issues compared to symmetric cryptography. One of the largest is that the public/private key pairs must have some particular mathematical relationship with each other and with every message encrypted or signed. Thus, asymmetric cryptography is deeply dependent on the existence of "one-way" mathematical operations: operations that can be efficiently computed in the forward direction but are intractable in the reverse direction. We don't actually know that any such operations exist, though we have a bunch that we know how to compute efficiently in one direction but not the other. These one-way operations tend to be touchy, though; small errors in constructing messages and performing computations can compromise the security (for example, consider the critical importance of correct padding of RSA plaintexts before encryption; do it wrong and you can potentially hand the adversary your private key).
There are also lots of practical issues with asymmetric cryptography. It's relatively slow and expensive (some techniques more than others), and that opens it up to more side channel attacks and other practical attacks. Then there are issues with the CA system; it's awesome that we can reduce the key distribution problem from one that requires secure pairwise exchanges between billions of devices to broad distribution of a few hundred bootstrapping keys... but that means those bootstrapping keys are incredibly important and every link in the bootstrapping chain becomes an extraordinarily tempting target for extra-cryptographic compromise (e.g. "rubber hose cryptanalysis").
Another issue is quantum computing.
Symmetric ciphers are theoret
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
"However, one-time pads are also pointless. Oh, there are some very isolated contexts in which they can be usefully applied, but they're useless for nearly everything we use cryptography for today. The one-time pad scheme requires securely distributing the pad, which must be as large as the message to be sent. If you have some channel you can use to distribute the pad securely, why not just use that channel to send the message?"
One time pads are definitely not as practical as the other methods. However the issue of pad exchange is only as much of a problem as it is for symmetric key. Once the key or pad is beyond the realm of easy memorization it doesn't really matter whether it's 128 bits or many gigs, they both fit easily on a micro SD card.
No, they're not equally difficult. There are many cases where it's relatively easy to establish a small secure channel but not a large one. Using asymmetric crypto is an obvious one, and one that we use all the time. Another is pre-shared keys, such as keys embedded in devices at factories, or keys entered into different devices, possibly directly or by using a secure hash to stretch a shorter password. Or consider the case of a device with a small amount of secure storage and a large amount of unsecure or less-secure storage (like, say, a mobile phone, or a local collection of keys used to encrypt a large quantity of cloud-based data). There are many, many more.
In the classical theoretical world of Alice and Bob, an OTP works fine. But in the complex, multi-faceted ways we use crypto in the real world, it's almost never practicel.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.