NSA announces plans for transitioning to quantum resistant algorithms | Hacker News Reader

NSA announces plans for transitioning to quantum resistant algorithms

nsa.gov

87 pointslisper76 comments

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.

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

The way it does that is by using Diffie-Hellman or ECDH, which both rely on the hardness of the discrete logarithm problem that quantum computers would break.

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?

Here are some median times from the eBATS benchmark page for a 2013 Intel Xeon E3-1275 V3 3500MHz (http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_sign.html)

  Cycles to generate a key pair:
  ed448goldilocks:  176924
  ecdonaldp256:     290628
  ecdonaldp384:    2202380
 
  Cycles to sign 59 bytes:
  ed448goldilocks:  185056
  ecdonaldp256:     381696
  ecdonaldp384:    2367856

  Cycles to verify 59 bytes:
  ed448goldilocks:  583900
  ecdonaldp256:     913848
  ecdonaldp384:    2741028

(ecdonaldp is ECDSA signatures with NIST P-256/384. The implementation used is OpenSSL, though I don't know which version)

AFAIK no elliptic curve size is quantum secure, so I guess the goal is just to require slightly more qubits for an attack.

> 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.

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

http://pqcrypto.org/

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

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

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.

The paper http://arxiv.org/abs/0708.0261 is a reasonably good introduction with a fair amount of math.

If you're looking for a non-technical overview, you might try https://uwaterloo.ca/institute-for-quantum-computing/quantum... but I don't think English alone is precise enough to explain anything really interesting about quantum computing.

I liked this presentation at CCC: https://media.ccc.de/browse/congress/2014/31c3_-_6261_-_en_-...

"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."

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

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.

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...

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.

There are indeed "quantum computers" that work on a few qubits (less than 10), but without what is called "error protection". They are useless for running factorization of practical sizes (i.e. they do break small keys, but you can break those by hand on paper as well).

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

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

Yeah but the NSA might throw money at it secretly, get a breakthrough and not disclose it because it's a huge military advantage.

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

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...

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

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

To expand a bit on this quite correct "no": There are many interpretations of quantum mechanics, like Bohm Mechanics, Multiverse, Copenhagen, but they all are mathematically equivalent and indistinguishable. They are of purely philosophical interest, not scientific (people will argue about this last sentence, but this would be an argument over semantics, not science).

So please do not call it "Multiverse theory", rather "Multiverse interpretation" :)

Uh, no. MWI and Copenhagen make different predictions. It just requires a reversible quantum computer to test. It is possible to distinguish which is true but it may take a few generations of experiment.

Could you elaborate on that? I have hard time believing it without a reference.

Edit: Probably you were referring to the need for "wavefunction collapse" in the Copenhagen theory. Practically, this can be addressed with the Master equations (or other approaches) for open quantum systems. Philosophically it might be unpleasant, but mathematically it is no different from what the Many World/Multiverse requires.

and we should trust them here why?

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. ;)

Stop messing with my head.

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.

s/prelminary/preliminary

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.

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.

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

Reply on news.ycombinator.com