NIST Draft Document on Post-Quantum Cryptography Guidance

NIST has released a draft of Special Publication1800-38A: “Migration to Post-Quantum Cryptography: Preparation for Considering the Implementation and Adoption of Quantum Safe Cryptography.” It’s only four pages long, and it doesn’t have a lot of detail—more “volumes” are coming, with more information—but it’s well worth reading.

We are going to need to migrate to quantum-resistant public-key algorithms, and the sooner we implement key agility the easier it will be to do so.

News article.

Tags: , , ,

Posted on May 2, 2023 at 10:10 AM • 24 Comments

Comments

Clive Robinson • May 2, 2023 12:06 PM

@ Bruce,

“We are going to need to migrate to quantum-resistant public-key algorithms, and the sooner we implement key agility the easier it will be to do so.”

Yup, though arguably we’ve already left it to late in many cases.

As noted on the previous Squid page satellites have an upto 25year mission life.

Medical implants likewise 25 years or more.

Peoples utility meters in their homes upto 50 or more years.

Likewise quite a lot of large industrial plant.

Those who do not think Qiantum Computing will have an effect within a fairly short time frame are getting less and less with time.

There will be a cross over period, but anything that has used existink PKI that has been “Hoovered up” by “collect it all” and tucked away in the NSA and others virtual time machine, will be vulnerable.

Only time will tell, who’s pony came in first at this derby, but I doubt it will be good for some.

Not really anonymous • May 2, 2023 12:20 PM

This report suggests that the problem is a future one. It is actually a current one if you consider the NSA an adversary. There are probably other groups recording large amounts of traffic for later analysis as well, but they aren’t likely to have access to as much traffic.
I also note that they mentioned hybrid systems for interoperability during the transition. But they didn’t mention using hybrid systems for security. (Maintaing a floor of what we have today, to protect against PQ algorithms being broken.)

Petre Peter • May 2, 2023 12:58 PM

It’s nice to have an email address instead of a form since with email, you have a copy of what you wrote.

derby • May 2, 2023 1:03 PM

PQ is already big business for vendors, many used scare tactics initially but now emphasize future decryption of stored messages.

RSAC panel made the point most messages are of low value. How many of those stored messages will be of any value in 20yrs? Even 10?

Most had a hard time migrating to TLS 1.2 almost none to 1.3. PQ? Give me a break.
Besides, how many hackers break encryption to gain access as it is? Maybe zero?
NYT’s Nicole Perlroth wrote they found that intelligence agencies didn’t need to break encryption because they found so many ways around it.

It also ignores the impact of other changes that will occur in the next few years.
Until recently DPI was important, with zero trust the NSA says oh wait…no, don’t do it after all. Don’t decrypt packets at control points because it’s more trouble than it’s worth and just creates more vulnerabilities. This is what happens, systems aren’t just a bunch of Lego’s, they’re complex.

When QCs do appear their more important application will not be breaking asymmetric encryption. The cost of operation including the expertise, it’s like expecting someone to steal fuel rods from a nuclear reactor so they can melt snow on their driveway. By the time they’re widely available and engineering advances implementations to commercially accessible your lunch date appointment will have zero value. Not even the federal gov’t will waste time and resources deciphering petabytes of junk.

MarkH • May 2, 2023 4:02 PM

Unfortunately, the precautionary principle requires safeguards against QC attacks, even though they might not be feasible during this century.

The comment from ‘derby’ paints a picture of the most probable evolution: if quantum computers ever do any useful computation faster than classical computers, they are likely to be crushingly expensive.

What we know for fact, is that QC progress has been slow and costly. I see no basis to expect that this will change.

If a QC ever factors a 1024 bit RSA number, additional decades may elapse before QCs could be scaled up sufficiently for 2048 bits.

What worries me, is that the infosec world will switch to some post-quantum algorithm which later is broken by some novel attack.

fvelez • May 2, 2023 6:58 PM

MarkH wrote “What worries me, is that the infosec world will switch to some post-quantum algorithm which later is broken by some novel attack.”

The experiments I’ve seen so far—notably in OpenSSH and web browsers—have involved post-quantum algorithms in combination with more traditional ones, such that both would have to be broken for a practical attack. For examples, search for sntrup761x25519-sha512 or X25519Kyber512Draft00. I haven’t seen much interest in post-quantum-only systems.

Clive Robinson • May 2, 2023 8:33 PM

@ Derby, ALL,

Re : Think not messages but contracts.

“RSAC panel made the point most messages are of low value. How many of those stored messages will be of any value in 20yrs? Even 10?”

How about 9,999 years?

It’s thelongest land lease I’m aware of.

Most home mortgages fall in the 20-30 year range some longer than 50.

How about conyracys with Governments for mineral extraction and similar.

All of these are extreamly valuable and quite long term and some Governments mostly Five-Eye and relayed in the West want all contracts ro be electronic.

Gpd forbid what will happen to some cryptocoins and the like…

In ICT security we tend to make a habit of thinking about the wrong targets for what will be quite viable threats.

Legal contracts and certain types of equipment, are way way more vulnerable than Messages we associate with Military, Diplomatic, or similar short time frame activities. For instance some private personal communications made when young and effectively unknown such as a topless photo of a 20ish girl at the beach, become very valuable to some when the young lady becomes romantically involved with sombody in say politics. Or they themselves become famous for some reason.

There are a number of UK Ministerial level politicians who got photographed when at University doing things at parties they should not have done. Some have been caught out since, and atleast one at the highest ministerial level refered to by other ministers and elected politicians as “White Lines” for reasons you can guess.

Over in the US some have sent unsolicited photos of their body parts to women/girls/boys less than half their age via electronic communications.

All have been hoovered up by “Collect it all” not just of the Five-Eyes but other less friendly nations.

Clive Robinson • May 2, 2023 8:49 PM

@ Not really…, ALL,

Re : What the big money is for.

“There are other indications that the NSA is trying to sabotage PQC standards.”

The NSA is just one of dozens of US Government agencies in the “Intelligence Community”(IC). It’s hard to get exact details, but it would appear that most UD IC agencies get more US tax dollars per head of staff than any other type of “civil service” style agency.

Certainly a large part of the NSA’s budget is on weakening hardware and software used in peoples private conversations. The excuse is “Foreign Nation State” but we all know the reality of the scope is as many US citizens as well. This has been evident from the days before the NSA existed, with the design of mechanical cipher systems with many weak keys and less strong keys.

The NSA tampered with the AES competition through NIST, with the result that most original AES implementations were grossly insecure via time based side channels.

So yes the NSA “have previous” on tampering with not just US based standards.

JonKnowsNothing • May 2, 2023 9:24 PM

@Clive, All

re: The NSA is just one of dozens of US Government agencies in the “Intelligence Community”(IC)

Best lines about the “Intelligence Community”:

Do you know how many Americans now work in intelligence?

Over 200,000.

In 16 different agencies.

With 30,000 private contractors in 170 countries at a grand cost to the taxpayer of $75 billion a year.

And they still call it “the intelligence community”.

I don’t think so.

David Hare 2014 Worricker #2 Turks & Caicos

Since then we might very well expect that the 7:10 rule happened.

Depending on which aspects you include there are likely thousands of agencies now part of the Intelligence Community in the USA. Every police department has The List and Keeps Their Own List and executes policing activities accordingly to their Lists. All of these lists feedback into the FBI CIA and NSA lists.

Those lists are exchanged with other agencies and policing units globally; de facto it’s a Global List and Global Intelligence Community.

There is only 1 variable on inclusion or exclusion which changes the configuration temporarily:

  • Variances in illiberal-neocon-libertarian economic polices targeting rival economies

Dave • May 3, 2023 1:08 AM

@derby: There was a great post on this on the Cryptography list a while back, google “On the Heffalump Threat” for the original paper, it’s an explanation of PQC for laypeople.

MarkH • May 3, 2023 2:04 AM

@Dave:

Thanks for your reference to the Heffalump paper, it’s well done.

The one thing I think it omits, is that every time the wizards declare Heffalump supremacy, somebody finds a way to make tiny revision to catapults, enabling them to work better than the Heffalump.

Many times real-world wizards declared QC victory, and then grown-ups pointed out, “well, classical computers can actually do that more efficiently.”

Nobody has proved that there will never be a useful QC, just as nobody has proved that nuclear fusion plants can’t make economically competitive electricity. I just highly doubt that I’ll live long enough to see either.

Clive Robinson • May 3, 2023 6:07 AM

@ MarkH, ALL,

Re : Do not assume linear, nature says exponential is prefered.

“What we know for fact, is that QC progress has been slow and costly. I see no basis to expect that this will change.”

Oh let me think back what a couple of years to what people were then saying about AI… now what are they saying?

Especially as the big money is knocking at AI researchers doors at last…

One or two of us here have pointed out AI is still no further ahead theoretically than it was several decades ago (have a dig through the research papers with a jaundiced eye to see why).

But practically computing power has enabled an illusion of forward progress in AI.

We’ve also pointed out that LLM’s like XxxxGPTn are not Intelligent Artificialy or other wise. They are no more than “matched filters” being hit by filtered noise, and in effect ringing like a gong or similar. Which others call “Stochastic Parrots” not realising as an expression it’s meaning is lost on maybe 99.9% of those who here it. Which means the slightly smarter con artists we call Venture Capitalists see $$$ to be made out of some of them.

You have to remember that Alphabet/Google and Microsoft/Bing are interested in LLM’s like GPT as “automated confidence tricksters” much like Amazon and Apple did with their “Personal Assistants”. The real aim is to spy on people “industrially” with such technology and fill vast databases with information on each and every one of them and thereby make profit in numerous ways most of us do not realise.

Thus you can be sure that both Alphabet and Microsoft are not just looking at, but investing in Quantum Computing for a whole host of reasons you realy will not like as their intent is to “strip you naked and put you up for sale in the virtual slave market” as their investors want money money money and care not how it is extracted.

@ ALL,

Yes my above does read very darkly, but do not let your natural optimism cause you to misjudge the reality of how certain people behave. Even the rapaciousness avarice of Midas’s wish, is as nothing compared to all to many in the more con artist end of the finance sector… The fact that what they do are only technically not crimes, should tell you a lot about the power of greed in some.

Alan Yoder • May 3, 2023 6:36 AM

To those who say that nature prefers the exponential:

Remember that in nature, at least on this planet, all curves that look exponential are actually just the beginnings of S-curves, or curves that look like Gaussians or sine waves.

Clive Robinson • May 3, 2023 7:00 AM

@ JonKnowsNothing, ALL,

Re : IC and more more more.

“Do you know how many Americans now work in intelligence?”

Sounds like one of those jokes about replacing light bulbs, only the punch line is more like a kick in the wallet rather than something that might make you smile.

Unless of course “Police State” truisms make you smile…

But the real objective is not Intelligence or Security, but to hide embarrassment, corruption or worse behind a classification.

So the vast number of bodies with clearance, tells you just how corrupt the system is becoming…

Fun fact I was once given a security clearance for various very dull reasons, but I do not know if it is still “active” or not… Because as the old joke has it,

“That knowledge is above my pay grade”…

Mind you the OPM gave that sort of info to the Chinese so they probably know amoungst many many others, but not me… Anyway I’m of the opinion I’m now to old to care and the mind forgets dull faster than water drips off of a pitched roof.

Clive Robinson • May 3, 2023 7:17 AM

@ Alan Yoder, ALL,

Re : Exponential is natures way, you just need to know what direction the journy is…

“Remember that in nature, at least on this planet, all curves that look exponential are actually just the beginnings of S-curves, or curves that look like Gaussians or sine waves.”

Whilst they look like S-curves,they are actually both exponential growth and then exponential decay, both modulated by population size.

That is most easily seen with infection. A new disease for a population grows exponentially, in the “uninfected population” as that population decreases as people aquire infection and immunity at some point the uninfected population becomes so sparse the population size modulation becomes dominant over the exponential growth.

Have a look at the sigmoid curves of which one is,

S(x) = 1 / (1 + e-x)

Clive Robinson • May 3, 2023 7:26 AM

@ ALL,

In my above the equation has e -x in it…

Now I typed it in using the HTML “sup” that the text under the input box says is valid (and I know “sub” has worked in the past).

I’m not seeing “sup” working is anyone else seeing it doing anything?

MarkH • May 3, 2023 10:15 AM

@Clive:

I never got <sup> to work since the change in site software, so I write e^-x instead. Frustrating!

I strongly agree with your observation above: though these LLMs certainly incorporate some sophistication, the fundamental approach is “we can’t do anything like intelligence, so we’ve upgraded Eliza with astronomical amounts of data” (and as Open AI admits, an eye-wateringly huge operating cost).

In contrast, maintaining lengthy entanglement of large numbers of qubits is a fundamental R&D challenge. Maybe they’ll discover magic “dilithium crystals,” but most likely scaling will be slow.

Wannabe techguy • May 3, 2023 1:52 PM

“The NSA tampered with the AES competition through NIST, with the result that most original AES implementations were grossly insecure via time based side channels.”

So why is anything that comes out of NIST trusted?

Not really anonymous • May 3, 2023 3:48 PM

There are regulations that require some organizations to only use encryption algorithms standardized by NIST. For those organizations it doesn’t matter whether or not they trust NIST; they have to use their stuff. One might think these regulations purpose might not be to provide better security, but rather to get organizations to use algorithms that have weaknesses (especially easy to screw up implementations) that the NSA can exploit.

Wannabe techguy • May 3, 2023 7:50 PM

@ Not really anonymous

Not surprised. To your last paragraph I would say most probably.

GregW • May 4, 2023 5:37 AM

There are many insecure orga in the, say Fortune 500. Security is not a core part of their value proposition, just a good business practice. For them, using NIST standards is a good proxy for good security that is still light years beyond what they can get all their devs (and business users) to do today when under deadline pressure from other business stakeholders.

ResearcherZero • May 11, 2023 5:27 AM

Most agencies are busy doing stuff other than looking at knobs on the internet. That is not to say that the odd staff member isn’t looking at “knobs” on the internet.

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.