# Long-term data protection, storage of old encrypted traffic and quantum cryptocalipse

Tony Arcieri makes an interesting point in his Imperfect Forward Secrecy article which basically boils down to:

1. large entities such as NSA are storing encrypted internet traffic, also what's to stop smaller entities such as proxy owners from doing the same
2. that data should be considered as good as clear text when quantum computers of sufficient strength hit the shelves and as that date grows near more people will start logging encrypted traffic
3. quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year) and a not-unreasonable estimate is that quantum computers will hit the shelves in 10-20 years
4. when this happens much (all?) stored encrypted data will be compromised

Problem existed before of course due to growing strength of computing technology and many protocols where discovered to be flawed by design, but the promise of a computer which breaks modern cryptography and knowledge of existence of giant datacenters which store data encrypted by obsolete standards make it worse.

It doesn't seem acceptable any more to just protect against today's cryptographic threats and know that all of the data you thought secure will be freely available to a patient individual in a not distant future (think of credit card numbers for example, password patterns that many people use etc)

So the question is, what kind of encryption/hashing one can use today to protect against long-term data storage?

Clarification

The "quantum cryptocalypse" simply exasparates a previously existing issue as more parties are likely to store encrypted data and wait for a good cryptoanalytical tool.

Problem lies in the general focus on making data secure "now" which is fine unless there's a sufficient number of entities storing encrypted data to break it later.

Quantum cryptocalipse, real or not, will make a lot of people store encrypted traffic on tapes. Idea behind this question is to find a list of algorithms which are "future proof" to the best of our knowledge and such algorithms should probably be quantum-proof too

Bottom line

OK, so what's the bottom line? Is there an asymmetric cryptography protocol that is not compromised by Shore's algorithm? Are there alternatives to using OTP for session key exchange?

-
The answer is, the kind described by the first 12 characters of this question's tag. $\;$ – Ricky Demer Mar 5 '14 at 8:55
Quantum computers suitable for running Shor's algorithm are still stuck at six qubits or so. Post-quantum cryptography is certainly interesting as a research topic, but compared to all the real threats you face today you should give it low priority. – K.G. Mar 5 '14 at 10:03
@Thomas Just because there are no large quantum computers yet,(don't remember the precise current state of the art, but it's around 5 qubits factoring huge semi-primes like 15) doesn't mean that there won't be such QCs twenty years from now. If you want long term confidentiality QCs resistance should be a consideration. – CodesInChaos Mar 5 '14 at 10:14
@Thomas A big quantum speedup for travelling salesman would be a far bigger revelation than even breaking 4096 bit RSA, since QCs are not believed to solve NP complete problems quickly. D-Wave can solve one specific optimization problem which is closely related to their physical structure. They don't entangle many qubits at the same time, can't run shor, it's dubious that they even offer a quantum speedup for their one favourite optimization problem. In short, D-Wave is useless and not representative of real quantum computers. – CodesInChaos Mar 5 '14 at 10:18
McEliece and hash-based signatures are other such algorithms. $\;$ – Ricky Demer Mar 11 '14 at 10:07

I can't agree with bullet 3. of the question stating quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year), at least in a context of cryptanalysis.

Even the marketing people praising the device alluded to do not pretend that it is of a kind useful for cryptanalysis: they state about it:

The types of problems the quantum computer is designed to solve are called discrete combinatorial optimization problems. The most cited example of this kind of problem is the “traveling salesman problem”.

Importantly, there is no claim of exactly solving almost all TSP of a given size, which would be a big breakthrough with potential applications to cryptanalysis. This marketing text proceeds to describe how better solving the traveling salesman problem as applied to US trucking could be of economic and ecological significance, without giving any evidence that today's TSP solvers can't handle that task satisfactorily.

In a recent scientific pre-publication linked here, the term " quantum annealing processor " is used to describe the device. Entanglement of only 8 qubit is claimed (a single out of 8x8 arrays of 8 qubit). Even if these 8 qubit where a quantum computer, and if all 64 arrays where functional, 64 arrays of 8 qubit would not make a 512-qubit quantum computer.

Enough expressing my strong doubts about the usefulness of Quantum Computers for cryptanalysis in a foreseeable future, let's get positive.

To protect against hypothetical Quantum Computers of a kind and size useful for cryptanalysis, using twice larger keys for symmetric algorithms is ample; AES-128 is safe today against key search, I bet AES-256 will remain resistant (in practice, to all but side-channel attacks) even with quantum computers, for decades (the most forward-looking may want to use Rinjdael in its 256-bit mode with perhaps an even wider key).

Now there's the problem of asymmetric algorithms (used when we want a private key not shared with anyone else). The mainstream asymmetric algorithms (RSA, ECDSA, DH, ECDH..) with today's key size are conceivably not secure against said hypothetical QC. Update: and, contrary to what I initially wrote, forward secrecy can't fix that. Protocols with forward secrecy, like some options of TLS or IPSec, can prevent past intercepts to be broken in the event of future leakage of private keys, including by use of future QC. But we do not know practical means (wich excludes Quantum Key Distribution) to fully protect us against intercepts made today, and analyzed in the future using an hypothetical Quantum Computer of a kind and size useful for cryptanalysis, and able to break the step of a key exchange protocol that built an ephemeral/session symmetric key, using typically some variant of DH or ECDH. Towards that, we need better/stronger asymmetric algorithms; I'm incompetent about it. In the meantime, we can use large asymmetric keys (particularly for the scheme building an ephemeral/session symmetric key); that's arguably at least of some use against QC.

And we should care, a lot, about much more mundane things than QC; like compromise of our computing platform, side-channel attacks, bad TRNGs, implementation goofs, and traffic analysis.

-
"an attack against a key-establishment protocol with forward secrecy can" be performed after $\hspace{.62 in}$ the intercept, by searching for the/either ephemeral private key. $\;$ – Ricky Demer Mar 5 '14 at 19:02
One minor nit: the standard implementation of forward secrecy within protocols (DHE in TLS, PFS in IPSec) doesn't help against a future adversary with a working quantuum computer. Where protocols achieve forward secrecy by performing a DH exchange (using fresh random secrets); this gives us PFS against someone who learns the long term keys... as long as the DH problem is hard. With a Quantum Computer, the cDH problem is easy, hence we're not actually secure against such a future potential adversary. – poncho Mar 5 '14 at 19:02
@Ricky Demer: Yes it can be attempted to search for the ephemeral key, but if it is symmetric, and wide enough, it is safe against QC, right? – fgrieu Mar 5 '14 at 19:59
Yes, however, the ephemeral private keys are $a$symmetric. $\;$ – Ricky Demer Mar 5 '14 at 20:07
@Ricky Demer: you are right (though I do not grasp a clear proof, yet); thanks to you and poncho for opening my eyes. – fgrieu Mar 5 '14 at 21:23