More Details on the NSA Switching to Quantum-Resistant Cryptography

The NSA is publicly moving away from cryptographic algorithms vulnerable to cryptanalysis using a quantum computer. It just published a FAQ about the process:

Q: Is there a quantum resistant public-key algorithm that commercial vendors should adopt?

A: While a number of interesting quantum resistant public key algorithms have been proposed external to NSA, nothing has been standardized by NIST, and NSA is not specifying any commercial quantum resistant standards at this time. NSA expects that NIST will play a leading role in the effort to develop a widely accepted, standardized set of quantum resistant algorithms. Once these algorithms have been standardized, NSA will require vendors selling to NSS operators to provide FIPS validated implementations in their products. Given the level of interest in the cryptographic community, we hope that there will be quantum resistant algorithms widely available in the next decade. NSA does not recommend implementing or using non-standard algorithms, and the field of quantum resistant cryptography is no exception.

[…]

Q: When will quantum resistant cryptography be available?

A: For systems that will use unclassified cryptographic algorithms it is vital that NSA use cryptography that is widely accepted and widely available as part of standard commercial offerings vetted through NIST’s cryptographic standards development process. NSA will continue to support NIST in the standardization process and will also encourage work in the vendor and larger standards communities to help produce standards with broad support for deployment in NSS. NSA believes that NIST can lead a robust and transparent process for the standardization of publicly developed and vetted algorithms, and we encourage this process to begin soon. NSA believes that the external cryptographic community can develop quantum resistant algorithms and reach broad agreement for standardization within a few years.

Lots of other interesting stuff in the Q&A.

Tags: , ,

Posted on February 2, 2016 at 7:11 AM • 22 Comments

Comments

moz • February 2, 2016 9:07 AM

@Joe K

I guess then if I see

Your connection is not private

Attackers might be trying to steal your information from http://www.iad.gov (for example, passwords, messages, or credit cards). NET::ERR_CERT_AUTHORITY_INVALID

I should just click yes to everything? A person could get paranoid 😉

Clive Robinson • February 2, 2016 9:21 AM

Whilst it is good people are starting to talk about QC resistant Crypto, I have to ask myself if there is a bit of “gun jumping” going on.

Whilst there are occasional favourable papers etc on QC comming out of academia, it’s fairly clear that they realy have nit progressed very far in over a decade. That is we are still at general QC of a handfull of bits not the thousands of bits needed for crypto cracking.

The question then arises are the NSA being premature, pragmatic or do they know something that academia does not?

Arguably general QC is further off in time than all publicaly published NSA approved crypto algorithms have ever lasted… Thus the NSA to some views may be being premature.

But if you consider single DES in “code book mode” is still in use in various places and products, then the NSA appear to be being commendably pragmatic. Especially when you consider the likes of todays Smart Meters could still be in current use in anything upto fifty years from now. Likewise human life expectancy and implanted medical electronics put in today could be around in thirty to fifty years. All jokes aside I still regularly use a 1/4 inch real to real tape recorder made in the 1960’s so it’s in for it’s half century and the thermionic valves it uses are still available as spares (it sounds warmer than the transistorised Studer Revox C270 for which BC109C transistors are still available).

But most here will probably plump for “The NSA knows something we do not” for which there are several possible options.

The first is that the NSA has cracked the general QC computer or a special case of it and are now in or close to being in a golden age of NOBUS till others catch up.

Secondly they could be “finessing” to stop the use of crypto they can not currently get at, and feel they can nolonger get away with manipulating standards and –supposadly– open crypto competitions to get weaker algorithms or those that suffer from implementation issues they can –and have– exploited.

I can think of a number of other things they might be upto, but “getting cute and cuddly” and industry friendly –even though it is part of their mandate– does not strike me as being high on the list.

It will be interesting to see what others think.

Ross • February 2, 2016 10:23 AM

@Clive

Not everything has one singular reason. I think this is one of those cases. As I’m sure you’ve experienced in your own first hand accounts of bureaucratic decision making meetings: they are joint ventures by many interested parties, half turf war and half serious deliberation.

At the exit of the process there are decisions made but not necessarily any decisive singular reason for the particular leadership outcome.

My guess in this case is that combination of several things jointly contributed to the move:

A.) There has been significant progress on the GC. While there’s nothing in the public representating serious concern there’s been enough progress to keep even hardcore skeptics of the NSA thankful that they are there for expertise.

B.) Moving from EC standards will allow those protocols and their backdoors, and the community that is now wary for those backdoor techniques, to languish.

C.) The PR around Quantum Computing – if that’s what the articles are now being written about – gives NSA a better public appearance than mass and global surveillance. Of course they pursue both (and more, e.g. state espionage for large corporations, tailored access for large operations, propaganda tooling and measurement, cyber-deterrents, etc).

Broadly it looks good and is possibly helpful (certainly it isn’t harmful to cryptographic progress). It’s a natural outcome of one of these meetings. But then again if you had asked me to predict it I wouldn’t have.

Jamie • February 2, 2016 10:23 AM

The question then arises are the NSA being premature, pragmatic or do they know something that academia does not?

Per the document, NSS equipment can be in service for 30 years, and it can take up to 20 years for algorithms to be deployed on them. So the crypto standards deployed to these systems must be able to resist attack for much longer time frames than we are used to in the commercial sector. It seems clear that a quantum computer capable of posing a threat to current asymmetric encryption will be developed within a 20-30 year time frame. So the current required minimum algorithm strengths are really just a stop-gap measure until quantum-resistant algorithms can be vetted and standardized by NIST (sometime in the next few years). At that time there will be new requirements released, and the very slow NSS transition will begin.

By the time quantum-resistant cryptography is in wide use at the Federal level, 10-15 years will have elapsed, and the commercial sector will already have long been using them.

Q • February 2, 2016 12:14 PM

Has anyone thought that, judging from the NSA’s history and reputation, their whole “hey everybody we gotta switch to QC-resistant algorithms NOW” is a red herring? Maybe they’re just trying to get everyone to move away from encryption that works to something they’ve backdoored… They’ve proved over and over that they do NOT want to help us protect ANYTHING… they just want to help themselves… to all data everywhere!

{ continue; } • February 2, 2016 12:27 PM

@Q Right…and maybe they want you to think it’s a red herring, or maybe they want you to think that they think you want them to think that maybe it’s a red herring.

Who? • February 2, 2016 2:44 PM

This one is the exact reason I call cryptography a `techno-voodoo.’

We know for sure some cryptographic algorithms are weak, for the rest we can only guess.

tyr • February 2, 2016 11:51 PM

@Clive

On the science side there’s a lot of work going into
this stuff (QC), but it seems to be mostly fiddling
with ways to make silicon compatible circuitry. If
they really had a working system or a way to make one
they’d cut the tongue out of anyone doing an announce
about it.

The few systems they have actually built aren’t what
you’d call a great leap forward into the unknown world
of Quantum Comp and won’t be replacing your desktop
for quite awhile. Half of electronics is unworkable
schemes and vapourware so until you can but a working
QC box keep your hand over your bum when evaluating
the claims.

I would rather see QT work to pass messages instantaneously
that would change the whole mad surveillance nightmare
into something more reasonable overnight. Teleportation
would tip over a lot of applecarts.

Spooky • February 3, 2016 2:19 AM

So our future will consist of another bag of 512-bit block cipher keys, two boxes of Now-Mo-Betta! ™ hashing functions, a gluten-free PRNG, and a uniform expansion of GitHub projects involving slipshod, cut-corner attempts at lattice crypto? Sigh. I was hoping our future would be so much cooler than that… 🙁

@Clive

Difficult to know what (if anything) has changed, though most of your guesses sound plausible to me. Since speculation has such tremendous entertainment value on this forum, I’ll toss out a few baseless WAGs of my own:

  • Given: they have discovered a clever way to attack at least one of the fundamentally unassailable problems that underlie key generation in the current stable of public key algorithms; they will not say which one; of all the algos, ECC may be most likely to fall…
  • So, a genius from another dimension named Mochizuki publishes a tentative proof of the ABC Conjecture in 2012; the proof runs to about 500 pages and was written over the course of 20 years, using a mathematical foundation (in arithmetic geometry) developed specifically for this problem; conundrum–because so many of the concepts and mathematical tools used in the proof are entirely novel, no one has been able to wrap their heads around it sufficiently to decide whether the proof is tenable (note: Mochizuki has an excellent professional reputation, so if the proof does turn out to have flaws, you’d expect them to be correctable); until last year (2015), no one had an adequate grounding in his papers to discuss the proof in-depth; here’s a good link to a summary of a Dec 2015 review of his ABC proof by a roomful of mathematicians (Mochizuki)
  • The ABC Conjecture and the novel tools used in Mochizuki’s proof may have an impact on ECC, or they may not…
  • NSA could afford to spare several full-time mathematicians for a committee to decipher the entire set of papers (well before the public could manage it) and forecast what–if any–impact they might have, once generally understood by academics…

  • QED: ECC is toast, we don’t know it yet, and life goes on…

P.S. I do -not- have a graduate background in mathematics, so this is an even bigger WAG than usual–buyer beware!

WhiskersInMenlo • February 3, 2016 3:00 AM

The important reality to hang your hat on is QC is now understood
and under promising research. The ability to build hardware is clearly difficult
but once solved the new hardware will quickly change the landscape.

Hard…. could be solved tomorrow or in 50+ years. If tomorrow
what is the time line? If 50+ years and quality methods of encryption
that resist both classic and QC attacks are embraced nothing secret is lost.

The risk of a game change is large.
Hidden in some of this is the raw power of custom FPGA
and the arrays of very fast and parallel GPUs. These are
changing the game now.

No matter what side you are on the game will change too quickly to ignore
the risks.

Curious • February 3, 2016 3:53 AM

As for QC tech, being the total non-expert on such subject matter, I can’t help but wonder if QC tech somehow could be used to create fancy backdoors for future crypto, instead of foremost breaking open encrypted data. Though, please don’t ask me how such a backdoor could work conceptually. I guess I am wildly imagining that one could create some novel setup with a moderate level of QC to toy around with patterns somehow, as opposed to building some huge quantum computer or something that amounts to great computing power.

Curious • February 3, 2016 4:18 AM

@{ continue; }

I don’t want to sound negative here, but I thought I’d share what I think is proper use of such a word/phrase like “psychoanalysis” and the like. In this case, what you wrote “psycho-analyze”.

As for psychoanalysis and variants of that word, it is imo only properly used by those that have that profession, and then only to describe such a praxis, theory, or a session in which that kind of activity is said to be a part of that profession. Whether or not such activities is very unscientific, or makes sense at all, I won’t judge that here. Same with this word “psychology”, probably only a meaningful word in the context of those practicing psychology as a profession, or maybe teaching it (regardless of what one think of such).

Ofc, using such words as a metaphor is probably common, as a way of contemplating about things, but I think there is a risk when using such words, that if/by attributing a greater meaning to things, what one imo probably will end up doing is parroting ideas and sentiments that revolves around the praxis of such professions, which imo is problematic when becoming labeling of others, “demonization” of people and actions, and “prescribed illness'” (like psychotic/psychopathy), and so if the praxis of a particular profession is questionable at best, mimicking the language is I think a bad idea.

MarkH • February 3, 2016 3:15 PM

@Clive:

What make is your thermionic recorder? I still have an antique vacuum-tube Ampex. I don’t know its date of manufacture; apparently the model was in production from 1958 to 1965.

It was made for studio use, and the heads are enclosed in beautiful mu-metal cubes (with rounded corners, of course) — three layers, for the playback head.

The electronics are “transitional”, with printed circuit boards mounting tube sockets (a bad combination — the boards scorched under the heat, and connections were prone to fail).

I haven’t fired it up in years, but it is in pristine condition.

As far as I can discover, tape for these things is made by a single company in the US. The last European plant producing magnetic audio tape reportedly closed in 2012. If anybody in Asia still makes 1/4″ tape, I haven’t found them.

2500′ pancakes retail from about USD 30 to 50 (apparently, there’s still lots of inventory from the defunct European production).

Remembering this technology took me down memory lane …

Z.Lozinski • February 4, 2016 6:06 AM

Separate, but related. There does seem to be serious work going on around quantum key distribution. Last year when I was in Barcelona, SK Telecom Research (the national operator for South Korea) had a public demonstration of key distribution using entangled pairs of photons, and then using the key to secure a DWDM link. They had the equipment to make the setup work down to 2 RUs of gear on each end.

I suspect the devil is buried deep in the details, though. There was a general belief that unlike TDM circuits (see IVY BELLS) optical fibres were immune from interception, until it became they are not. To me, the critical thing is making sure that the system works end-to-end, and that is a difficult engineering task.

i should get an update in a couple of weeks at this year’s Mobile World Congress.

Paul Rain • February 6, 2016 8:45 PM

NSA believes that they will create a quantum computer first, and that noone will be able to prove that their ‘quantum resistant’ cryptography is not, until well after they are exploiting it in the real world.

holly • February 10, 2016 10:12 AM

Hello,
we developed a post-quantum cryptography algorithm McEliece, and we want to integrate into nss, but we have not found any resource,
someone can help me please
thank you

TomH • December 16, 2016 9:41 AM

Apologies posting so late on this thread. I’d like to make a comment about those asking why the NSA and others are jumping on this “so early”.

Apologies if I sound like a schoolteacher here “remember your history”… For example the Venona project: https://en.wikipedia.org/wiki/Venona_project.

Under the Venona project, a collection of KGB (and GRU) messages that were intercepted and recorded in the very tail end of the 1930s and during the 1940s, were still being worked on by cryptanalysts until the project closed in 1980 (yes that’s 1980!).

The concern is that there may be some messages/traffic sent today that contain information that may still be relevant in future years, using encryption that won’t be resistant to quantum techniques. The sooner that quantum resistant algos can be adopted: the less the future liability.

Sure, I’ve given a pretty rare and extreme example, but I hope it illustrates the concern.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.