NSA announces plans for transitioning to quantum resistant algorithms

[AlyssaRowan]

You'll note they don't actually specify any asymmetric quantum-resistant algorithms. I'd guess if they did, NTRU or a derivative would be one they'd consider first: Security Innovation were trying to sell them that at about the same time Certicom were pushing elliptic curves. (I'm not as convinced about ideal lattices, but that's an artifact of my not being as familiar with the field.)

Pre-shared keys, as they suggest there, have no forward secrecy - which makes them great for those who really like stealing, say, IPsec keys… like the NSA. It may work with the kind of old military key infrastructure they and GCHQ have, that regularly distributes random keys from centralised, organisationally-trusted sources on specialised hardware; it is a terrible recommendation for civilians.

Interesting that they're still married to P-384 (probably the most annoying curve to implement correctly). Properly-implemented Ed448-Goldilocks is safer, and that's what CFRG are going with for the "paranoid" level.

[jackgavigan]

> You'll note they don't actually specify any asymmetric quantum-resistant algorithms. I'd guess if they did, NTRU or a derivative would be one they'd consider first...

My bet would be on McEliece. It's been around longer, so has been subjected to more rigorous cryptanalysis than NTRU, and is not patented.

[eeZi]

IPSec still has forward secrecy even with pre-shared keys.

[wolf550e]

openssl 1.0.2a on an old Conroe Core2 gets this:

                                  sign    verify    sign/s verify/s
     256 bit ecdsa (nistp256)   0.0001s   0.0003s   8727.8   3493.3
     384 bit ecdsa (nistp384)   0.0005s   0.0020s   2001.4    493.0
     521 bit ecdsa (nistp521)   0.0010s   0.0017s   1021.3    603.0

Can P-384 (or Ed448-Goldilocks) be close to P-256 in speed?

[tlack]

Such an interesting subject. Anyone have any pointers to the most interesting post-quantum algorithms?

[palsecam]

http://pqcrypto.org/

Also https://speakerdeck.com/veorq/quantum-computers-vs-computers... (slides 25-30)

[robotkilla]

I have next to zero understanding of how quantum computers are supposed to work. Does anyone have something like an intro into QC "for dummies"? I want to grasp this subject.

[Bluerise]

http://www.square-up.org/

[tway]

"For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition."

[wfunction]

Probably trying to insert backdoors before the community develops an algorithm without one.

[cabirum]

Wait, do working quantum computers actually exist today? D-Wave is the one I heard about, but the wiki page says it's no faster than ordinary computers and not even sure it works as advertised.

[jackgavigan]

D-Wave's hardware is customised for a particular function: http://physicsworld.com/cws/article/news/2014/jun/20/is-d-wa...

A team at UCSB built a prototype quantum computer that successfully factored 15 a few years back: http://www.nature.com/nphys/journal/v8/n10/full/nphys2385.ht...

[marcosdumay]

Yes, and last time I saw, they could break 11 bits long keys. There are probably better ones now, it's been a long time that they don't make the news.

Anyway, they are still far from being practical, but do exist.

[jokoon]

Was quite to hear snowden talk about those. Might mean NSA already has them.

[maaku]

Post quantum cryptography has been an active area of public research for some time.

[biot]

Can anyone explain what makes an encryption algorithm quantum-resistant?

[pbsd]

This is hard to answer because many quantum algorithms useful for cryptanalysis have probably not been discovered yet. See, for example, the debacle surrounding Soliloquoy [1], an algorithm that despite being based on the hardness of lattice reduction has a fast quantum algorithm.

Anyway, a quantum-resistant algorithm is usually meant to be one that resists the exponential speedup given by Shor's algorithm and its variants. In other words, a quantum-resistant algorithm can't be based on the hardness of integer factorization, discrete logarithms on any abelian group, class groups, and so on (i.e. all instances of the Abelian hidden subgroup problem).

The leading candidates for such hard problems are decoding a random linear code (McEliece), shortest/closest vector finding in a lattice (NTRU, GGH, [R]LWE, ...), multivariate equation system solving (HFE and friends), and in the specific case of digital signatures one-way functions (Merkle Tree signatures).

[1] http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Syste...

[aburan28]

This is a big development IMO. Quantum computers were theoretical only but now this update seems to indicate the feasibility of such

[givan]

If they managed to make quantum calculations does it mean that it validates the many worlds/multiverse theory?

[akvadrako]

no

[Taniwha]

and we should trust them here why?

[scintill76]

Maybe it's reverse psychology -- they've got quantum cryptanalysis, and the surest way to keep us all vulnerable is them telling us we should upgrade. ;)

[Spooky23]

They are equally, if not more threatened than you are by quantum computing. Advances in the field were an unexpected and unwelcome discovery for NSA.

[titanomachy]

s/prelminary/preliminary

[mtgx]

I hope nobody here is actually considering using the proposed NSA algorithms - right?

The NSA today is a very different beast from the pre-2000 one. The focus seems to have drastically changed from securing stuff to mostly introducing vulnerabilities in stuff.

[technion]

I had the same initial thought.

However, in reviewing the actual recommendations, if you trusted RSA 2048 before, it would be hard to argue the NSA has now backdoored RSA 3072 as a part of recommending it.

[newsdotyc-ta]

This comment (along with many of this author's other comments) seems to take a form which strongly reminds me of the output of SCIgen[1] and I wonder if anyone more versed in quantum cryptography or any related fields of mathematics can make more sense of it than I can.

I could, of course, be unfairly interpreting the unusually simple [2] grammatical structures as being computer generated rather than as an artifact of not being a native English speaker. If that is the case, I do apologize and hope that I have not caused any offence.

[1] http://pdos.csail.mit.edu/scigen/ [2] Simple structures relative to the complexity of the topic(s)

[dang]

We detached this subthread and marked it off-topic.

[sobkas]

There is this one quantum resistant algorithm called rot13...