Most of us have heard about Quantum Computing and its immense
power to break today's strongest security mechanisms. What is
the sense and nonsense?
Quantum Computing is an emerging field of technology. Don't be mistaken, it's no longer purely fundamental research, but it's technology being developped. The field has shown the principles to work, and is working towards clearly set goals and has a clear idea of what aspects should be improved upon. Call it a road map if you like. And like in other fields of technology, the numbers are going up rapidly and, with that, the power to do the inevitable to cryptography.
To crack an algorithm that is designed to be particularly hard to crack, you almost need to change the rules of the game, and that is pretty much what Quantum Computers do; they make a lot of computations at the same time, and given smart-enough algorithms, they can do surprising things.
To take a bit away from the mystique surrounding the field, think of a string on a guitar. When you pluck it, you release a lot of random motion on the string, but the resonance of the string quickly dampens all frequencies except those that match in the length of the string. The result is a sharp beginning full of unstructured noise, and after a while, a bright tone. The selection process on many frequencies has happened completely independently. Now imagine passing some frequencies through to other strings, which also start vibrating and providing feedback on the resonance. And try to think of the structures, or algorithms if you like, that you could build with this; some string parts would end up vibrating on one tone, others on another tone, and yet other frequencies from the original pluck are lost. This is not exactly how a Quantum Computer works, but it is a somewhat fair image.
Algorithms have been devised to approach what we up to now thought uncrackable (the so-called "discrete log" problem) in a time that is structurally faster. Simply because operations can work on much data at the same time, and then be made to interact in ways that construct computations.
What gets broken?
In ten years from now, it is expected that all current public-key algorithms are broken. RSA, DSA, ECDSA, DH, ECDH, all our favourites. This is nothing short of devastating because we need these to build trust with parties we have not been in contact with — based on their proof of ownership of a key. Yes, that certainly includes HTTPS under any of the current forms of TLS. The game changes entirely when others can suddenly start claiming posession of the key, simply because they were able to crack it on a Quantum Computer.
There are some pieces that are left to use though. We can continue to use symmetric (or "bulk") ciphers such as AES, and we can still use hashing algorithms. Note that this means that Kerberos, on which we found most of our infrastructure, will continue to be safe, as long as it is not founded on the public-key setup protocol PKINIT. Some of you may know PKINIT as "smart card logon".
Work has started on devising new public-key crypto systems, and we should expect these to be commonplace when Quantum Computers hit the market. So, are we out of trouble? Not by a long shot, we do need to act well before that time. As in, now is the time to move.
What does it mean, in concrete terms?
We use public key crypto for a number of things:
- Signatures for authentication, such as in web traffic
- Signatures for legal authorisation, such as with PGP
- Key encryption and key agreement, with or without Perfect Forward Secrecy
All these will be broken with the current algorithms. But their impact varies.
Authentication is usually a thing at the present time; there is no damage from future cracks of an authentication key because we have no mechanism to jump back in time and perform false authentication.
Legal authorisation is a bigger problem; looking at any legally binding signature made with current-day technology after the arrival of Quantum Computers is meaningless, as anyone could have forged the signature. Be sure to refresh all signatures before that time; this might be done with a timestamping service that freezes the original document with the original signatures as they were at any date before the arrival of Quantum Computing.
Key encryption and key agreement are ways of establishing a "bulk" encryption key for documents or network connections, including HTTPS. It is worryingly doable to capture and store all such traffic for future analysis. At this later moment, everything that was thought to be private traffic can be decrypted and looked through. Let's hope your credit card expires before that day has come!
Note well: The bulk encryption method itself cannot be cracked, but the keys used can be retrieved because their use in protocols depends on public keys. That's a very good design method, it just so happens that the current algorithms are up for renewal. And with the ability to rewind on such content, you should not wait until the first Quantum Computer is switched on.
This is why we indicated that it is time to act now. Unfortunately, we still need to wait for new public key algorithms. Guess why this article has serial number 1...
Very often, HTTPS is used to protect weak encryption schemes such as passwords. These will all be leaked and lapped up by intruders. Your services can then easily be boarded and your data hoarded. That's not a remote possibility; plenty of people on the Internet want to do this sort of thing, for good or for bad.
ARPA2 and Quantum Computing
We've been working quietly at a TLS variant known as TLS-KDH, which is based on Kerberos. During an excellent lecture on Quantum Computing by Tanja Lange we suddenly realised that this may well be the first form of TLS that is ready to face up to Quantum Computers. It uses ECDH, but folds some Kerberos-specifics into the operation that stops attackers from breaking the encryption on the connection. This is good, because TLS is used in most secure Internet protocols, including HTTPS. It is not-so-good because it assumes that people are using Kerberos.
We're also working on a mechanism for Realm Crossover with Kerberos, allowing clients in one security realm to access servers in another. The mechanism sets up an instant shared key between the two realms, through which the client can authenticate to the targeted remote server. This mechanism however, is a prey for Quantum Computing because it uses ECDH without the additional information that TLS-KDH uses. Knowing the shared key used for crossover would enable the decryption of all traffic that crosses over between the client and server realm.
This is precisely why it is good that security research makes advances and teaches us to stay moving the protective side to stay ahead of attackers and malpracticitoners; it makes us aware of things that we should improve. In the case of Realm Crossover, we have started the process of designing solutions that should make it undoable to crack.
More to come...
There will be more on this topic in later articles. The challenge that we are facing is incredible and complicated, but we're on top of it. In the end, we are likely to win through with an architecture that can easily roll new keys and certificates, and leave users protected.
Go Top