NSA announces plans for transitioning to quantum resistant algorithms

https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml

by lisper • 11 years ago

87 37 11 years ago

nsa.gov

tlack• 11 years ago

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

palsecam• 11 years ago

http://pqcrypto.org/

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

Bluerise• 11 years ago

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

robotkilla• 11 years ago

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.

Thorondor• 11 years ago

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.

noinsight• 11 years ago

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

Taniwha• 11 years ago

and we should trust them here why?

scintill76• 11 years ago

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

confluence• 11 years ago

Stop messing with my head.

Spooky23• 11 years ago

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.

wfunction• 11 years ago

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

sobkas• 11 years ago

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

aburan28• 11 years ago

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

jokoon2• 11 years ago

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

maaku2• 11 years ago

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

jokoon2• 11 years ago

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

mtgx• 11 years ago

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• 11 years ago

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.

biot• 11 years ago

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

pbsd• 11 years ago

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

AlyssaRowan• 11 years ago

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.

eeZi• 11 years ago

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

AnthonyMouse• 11 years ago

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.

wolf550e• 11 years ago

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?

tveita• 11 years ago

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.

jackgavigan2• 11 years ago

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.

titanomachy• 11 years ago

s/prelminary/preliminary

cabirum• 11 years ago

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.

jackgavigan2• 11 years ago

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• 11 years ago

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.

krastanov3• 11 years ago

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

tway• 11 years ago

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

givan• 11 years ago

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

akvadrako• 11 years ago

krastanov3• 11 years ago

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" :)

NSA announces plans for transitioning to quantum resistant algorithms

Related Stories