NSA, NIST, and post-quantum crypto: my second lawsuit against the US government
488 comments·August 5, 2022
> Aside: I really wish people would link to court documents whenever they talk about an ongoing lawsuit.
I just want to second that and thank you for the link. Most reporting is just horribly bad at covering legal stuff because all the stuff that makes headlines that people click on is mostly nonsense.
And a big thank you to the wonderful people at the Free Law Project for giving us the ability to find and link to this stuff. They're a non-profit and they accept donations. (hint hint)
It's just a vanilla FOIA lawsuit, of the kind hundreds of people file every month when public bodies fuck up FOIA.
If NIST puts up any kind of fight (I don't know why they would), it'll be fun to watch Matt and Wayne, you know, win a FOIA case. There's a lot of nerd utility in knowing more about how FOIA works!
But you're not going to get the secrets of the Kennedy assassination by reading this thing.
I will draw to your attention two interesting facts.
First, OpenSSH has disregarded the winning (crystals) variants, and implemented hybrid NTRU-Prime. The Bernstein blog post discusses hybrid designs.
"Use the hybrid Streamlined NTRU Prime + x25519 key exchange method by default ("firstname.lastname@example.org"). The NTRU algorithm is believed to resist attacks enabled by future quantum computers and is paired with the X25519 ECDH key exchange (the previous default) as a backstop against any weaknesses in NTRU Prime that may be discovered in the future. The combination ensures that the hybrid exchange offers at least as good security as the status quo."
Second, Daniel Bernstein has filed a public complaint against the NIST process, and the FOIA stonewalling adds more concern and doubt that the current results are fair.
What are the aims of the lawsuit? Can the NIST decision on crystals be overturned by the court, and is that the goal?
We (OpenSSH) haven't "disregarded" the winning variants, we added NTRU before the standardisation process was finished and we'll almost certainly add the NIST finalists fairly soon.
What are the aims of the lawsuit? NIST fucked up a FOIA response. The thing you do when a public body gives you an unsatisfactory FOIA response is that you sue them. I've been involved in similar suits. I'd be surprised if NIST doesn't just cough up the documents to make this go away.
"Can NIST's decisions on crystals be overturned by the court?" Let me help you out with that: no, you can't use a FOIA suit to "overturn" a NIST contest.
OpenSSH implemneted NTRU-Prime? What's your point? That we should just do whatever the OpenSSH team decides to do? I almost agree! But then, if that's the case, none of this matters.
It's not the first time either and it won't be the last. NIST chose Rijndael over Serpent for the AES standard even though Serpent won. I vaguely recall they gave some smarmy answer. I don't think anyone submitted a FOIA not that it would matter. I've been through that bloated semi-pseudo process and saw how easy it was to stall people not answer a simple question.
>What are the aims of the lawsuit? Can the NIST decision on crystals be overturned by the court, and is that the goal?
It sounds to me like the goal is to find out if there's any evidence of the NSA adding weaknesses into any of the algorithms. That information would allow people to avoid using those algorithms.
> "I may believe almost all of this is overblown and silly, as like a matter of cryptographic research ..."
Am I misunderstanding you, or are you saying that you believe almost all of DJB's statements claiming that NIST/NSA is doctoring cryptography is overblown and silly? If that's the case, would you mind elaborating?
I believe the implication that NIST or NSA somehow bribed one of the PQC researchers to weaken a submission is risible.
I believe that NIST is obligated to be responsive to FOIA requests, even if the motivation behind those requests is risible.
> I believe the implication that NIST or NSA somehow bribed one of the PQC researchers to weaken a submission is risible.
Is that even a claim here? I'm on mobile right now so it's a bit hard for me to trawl through the DJB/NIST dialogue, but I thought his main complaint is that NIST didn't appear to have a proper and clear process for choosing the algorithms they did, when arguably better algorithms were available.
So the suggestion wouldn't necessarily be that one of the respected contestants was bribed or otherwise compromised, but rather that NIST may have been tapped on the shoulder by NSA (again) with the suggestion that they should pick a specific algorithm, and that NSA would make the suggestion they have because their own cryptographers ("true believers" on NSA payroll) have discovered flaws in those suggested algorithms that they believe NSA can exploit but hopefully not adversaries can exploit.
There's no need for any novel conspiracies or corruption; merely an exact repeat of previous NSA/NIST behaviour consistent with NSA policy positions.
It's simultaneously about as banal as it gets, and deeply troubling because of that.
> I believe the implication that NIST or NSA somehow bribed one of the PQC researchers to weaken a submission is risible.
Could you elaborate on this? I didn't get this from the article at all. There's no researcher(s) being implicated as far as I can tell.
What I read is the accusation of NIST's decision-making process possibly being influenced by the NSA, something that we know has happened before.
Say N teams of stellar researchers submit proposals, and they review their peers. For the sake of argument, let's say that no flaw is found in any proposal; every single one is considered perfect.
NIST then picks algorithm X.
It is critical to understand the decision making process behind the picking of X, crucially so when the decision-making body has a history of collusion.
Because even if all N proposals are considered perfect by all possible researchers, if the NSA did influence NIST in the process, history would suggest that X would be the least trustable of all proposals.
And that's the main argument I got from the article.
Yes, stone-walling a FOIA request may be common, but in the case of NIST, there is ample precedent for malfeasance.
I believe you have a very naive and trusting view of these US governmental bodies. I don't intend that to be an insult, but by now I think the jury is out that these agencies cannot be trusted (the NSA less so, than NIST).
just in case someone else never heard this word before:
> arousing or provoking laughter
I don't think it's a bad thing to push back and demand transparency. At the very least the pressure helps keep NIST honest. Keep reminding them over and over and over again about dual-EC and they're less likely to try stupid stuff like that again.
Speaking of dual-EC -- it does seem like 2 questions seem to be often debated, but it can't be neglected that some of the vocal debaters may be NSA shills:
1. does the use of standards actually help people, or make it easier for the NSA to determine which encryption method was used?
2. are there encryption methods that actually do not suffer from reductions in randomness or entropy etc when just simply running the algorithm on the encrypted output multiple times?
It seems that these question often have piles of people ready to jump in saying "oh, don't roll your own encryption, ooh scary... fear uncertainty doubt... and oh whatever you do, don't encrypt something 3X that will probably make it easier to decrypt!!" .. but it would be great if some neutral 3rd party could basically say, ok here is an algorithm that is ridiculously hard to break, and you can crank up the number of bits to a super crazy number.. and then also you can run the encryption N times and just not knowing the number of times it was encrypted would dramatically increase the complexity of decryption... but yea how many minutes before somebody jumps in saying -- yea, don't do that, make sure you encrypt with a well known algorithm exactly once.. "trust me"...
1. Formal, centralized crypto standards, be they NIST or IETF, are a force for evil.
2. All else equal, fewer dependencies on randomness are better. But all else is not equal, and you can easily lose security by adding determinism to designs willy-nilly in an effort to minimize randomness dependencies.
Nothing is, any time in the conceivable future, change to make a broken RNG not game-over. So the important thing remains ensuring that there's a sound design for your RNG.
None of our problems have anything to do with how "much" you encrypt something, or with "cranking up the number of bits". That should be good news for you; generally, you can run ChaPoly or AES-CTR and trust that a direct attack on the cipher isn't going to be an issue for you. Most of our problems are in the joinery, not the beams themselves.
>2. are there encryption methods that actually do not suffer from reductions in randomness or entropy etc when just simply running the algorithm on the encrypted output multiple times?
I think all block ciphers (e.g. AES) meet that definition. For AES, for a specific key, there's a 1-to-1 mapping of plaintexts to ciphertexts. It's impossible that running a plaintext through AES produces a ciphertext with less entropy, because if the ciphertext had less entropy, it would be impossible to decrypt to get back the plaintext, but AES always allows decryption.
> some neutral 3rd party
Unfortunately, this would appear to be the bit we've not yet solved, nor are we likely to.
> are there encryption methods that actually do not suffer from reductions in randomness or entropy etc when just simply running the algorithm on the encrypted output multiple times?
Unless you can prove that all e.g. 2^256 possible 256 bit inputs map to 2^256 different 256 bit outputs (for every key, in the case of encryption), then chances are you lose strength with every application because multiple inputs map to the same output (and consequently some outputs are not reachable).
I have no doubt that they are great at their job, but when it comes to lawsuits the judge(s) are equally as important. You could get everything right but a judge has extreme power to interpret the law or even ignore it in select cases.
I wouldn't say they ignore the law, but legislation like FOIA has a lot of discretion to balance competing interests and that's where a judge would make the most different despite all the great articulations of the most brilliant lawyers.
There are very few public bodies that do a solid, to-the-letter job of complying with their open records requirements. Almost all FOIA failings are due to the fact that it isn't staffed adequately; FOIA officers, clerks, and records attorneys are all overworked. When you do a bunch of FOIA stuff, you get a feel for what's going on with the other side, and you build a lot of empathy (which is helpful in getting your data over the long run).
And then other times you run into bloody-mindedness, or worse.
I don't think NIST has many excuses here. It looks like they botched this straightforwardly.
It's a straightforward case. My bet is that they'll lose it. The documents will get delivered. That'll be the end of it.
This is the least compelling argument Bernstein makes in the whole post, because it's simply not the job of the NIST PQC program to design or recommend hybrid classical/PQC schemes. Is it fucky and weird if NSA later decides to recommend against people using hybrid key establishment? Yes. Nobody should listen to NSA about that, or anything else. But NIST ran a PQC KEM and signature contest, not a secure transport standardization. Sir, this is a Wendy's.
It’s compelling in context. If the NSA influenced NIST standards 3x in the past — DES, DSA, Dual EC — then shouldn’t we be on high alert this 4th time around?
That NSA is already recommending against hybrid, instead of waiting for the contest results, might signal they’ve once again managed to game the standardization process itself.
At the very least — given the exhaustive history in this post — you’d like to know what interactions NSA and NIST have had this time around. Thus, djb’s FOIA. And thus the lawsuit when the FOIA went unanswered. It all seems very reasonable to me.
What’s that old saying, “fool me thrice…”?
Everybody is on high alert. Being on high alert doesn't make Bernstein right.
I don't even support the premise of NIST crypto standardization, let alone trust them to do it.
Why not start that discussion yourself?
Indeed as potato said, link this article in the ML for them to see that NIST can not be fully trusted
I think the United States is more about charging people with crimes and ruining their lives that way rather than disappearing people. Russia might kill you with Polonium and make sure everyone knows it, but America will straight up “legally“ torture you in prison via several means and then argue successfully that those methods were legal and convince the world you weren’t tortured. Anyone who’s a target for that treatment, though, knows that’s a lie.
The FBI will just interview you over whatever and then charge you for lying to a federal agent or dig up some other unrelated dirt. While the original investigation gets mysteriously dropped a year later.
There's an easier problem here, which is that our reliance on formal standards bodies for the selection of cryptography constructions is bad, and, not hardly just at NIST, has been over the last 20 years mostly a force for evil. One of the most important "standards" in cryptography, the Noise Protocol Framework, will probably never be a formal standard. But on the flip side, no formal standards body is going to crud it up with nonsense.
So, no, I'd say that bedlam will not follow from a lack of trustworthy cryptography standards. We've trusted standards too much as it is.
Believing both "Don't roll your own crypto" and "Don't trust the standards" would seem to leave the average developer in something of a quandry, no?
No. I don't think we should rely on formal standards, like FIPS, NIST, and the IETF. Like Bernstein himself, I do think we should rely on peer-reviewed expert cryptography. I use Chapoly, not a stream cipher I concocted myself, or some bizarro cipher cascade posted to HN. This is what I'm talking about when I mentioned the Noise Protocol Framework.
If IETF standards happen to end up with good cryptography because they too adopt things like Noise or Ed25519, that's great. I don't distrust the IETF's ability to standardize something like HTTP/3. I do deeply distrust the process they use to arrive at cryptographic architectures. It's gotten markedly better, but there's every reason to believe it'll backslide a generation from now.
(There are very excellent people who contribute to things like CFRG and I wouldn't want to be read as disparaging any of them. It's the process I have an issue with, not anything happening there currently.)
how could NIST possibly be "one of our most sacrosanct institutions" after the NSA already fucked them with Dual_EC_DRBG?
whoever wants to recommend standards at any point since 2015 needs to be someone else
https://en.wikipedia.org/wiki/NIST_SP_800-90A for this who have forgotten.
Look, my point is that there are lots of companies around the world who can’t afford highly skilled mathematicians and cryptographers on staff. These institutions rely on NIST to help them determine what encryption systems may make sense. If NIST is truly adversarial, the public has a right to know and determine how to engage going forward.
They don't have to (and shouldn't) retain highly skilled mathematicians. Nobody is suggesting that everyone design their own ciphers, authenticated key exchanges, signature schemes, and secure transports. Peer review is good; vital; an absolute requirement. Committee-based selection processes are what's problematic.
I think this is a sloppy take. If you read the full back-and-forth on the FOI request between D.J. Bernstein and NIST, it becomes readily apparent that there is _something_ rotten in the state of NIST.
Now of course that doesn't necessarily mean that NIST's work is completely compromised by the NSA (even though it has been in the past), but there are other problems that are similarly serious. For example, if NIST is unable to explain how certain key decisions were made along the way to standardisation, and those decisions appear to go against what would be considered by prominent experts in the field as "good practice", then NIST has a serious process problem. This is important work. It affects everyone in the world. And certain key parts of NIST's decision making process seem to be explained with not much more than a shrug. That's a problem.
All you're saying here is that NIST failed to comply with FOIA. That's not unusual. No public body does a reliably good job of complying with FOIA, and many public bodies seem to have a bad habit of pre-judging the "merits" of FOIA requests, when no merit threshold exists for their open records requirements.
NIST failing to comply with FOIA makes them an intransigent public body, like all the rest of them, from your local water reclamation board to the Department of Energy.
It emphatically does not lend support to any of this litigants concerns about the PQC process. I don't know enough (really, anything) about the PQC "contest" to judge claims about its validity, but I do know enough --- like, the small amount of background information needed --- to say that it's risible to suggest that any of the participating teams were compromised by intelligence agencies; that claim having been made in this post saps its credibility.
So, two things I think a reasonable person would want to establish here: first, that NIST's behavior with respect to the FOIA request is hardly any kind of smoking gun, and second that the narrative being presented in this post about the PQC contest seems somewhere between "hand-wavy" and "embarrassing".
> It emphatically does not lend support to any of this litigants concerns about the PQC process.
I agree with most of what you're saying except for this. In my view, unlike some of the other organisations you mentioned, the _only value_ of NIST is in the quality and transparency of its processes. My reading of the DJB/NIST FOI dialogue is that there is reason to believe NIST has serious process problems that go far beyond simply handling an FOI well. From their own responses, it reads as if they aren't able to articulate themselves why they would choose one contestant's algorithm over another's. That kind of undermines the entire point of having an open contest.
What's with the infighting here? Nothing about the post comes across as conspiracy theory level or reputation ruining. It makes me question the motives of those implying he's crazy, to be honest.
Post-quantum cryptography is essentially a full-employment program for elite academic public key cryptographers, which is largely what the "winning" PQC teams consist of. So, yeah, suggesting that one of those teams was compromised by an intelligence agency is "conspiracy theory level".
Nobody is denying the legitimacy of the suit itself. NIST is obligated to follow public records law, and public records law is important. Filippo's message, which we're all commenting on here, says that directly.
Has the general notion of "conspiracy theory" ever carried any positive value? It only seems to exist to discredit "doubters against the majority consensus" without substance. But I guess words like "crank" wouldn't even exist if there weren't many people like it, so it carries some "definitional" value.
Because they show total disregard for someones opinion (in a more formal way: "unlike you/them, i completely agree with the (apparent) majority consensus (which it also implies), these words probably don't belong into a serious discussion.
Dismissing this lawsuit as a conspiracy theory is embarrassing for both of them.
There is ample evidence to document malfeasance by the involved parties, and it’s reasonable to ask NIST to follow public law.
> Dismissing this lawsuit as a conspiracy theory is embarrassing for both of them.
They are not dismissing the lawsuit.
One says he’s doing it wrong. The other says he hopes that he wins, of course!
Meanwhile they go on to attack Bernstein, mischaracterize his writing, completely dismiss his historical analysis, mock him with memes as a conspiracy theorist, and to top it off they question his internal motivations (which they somehow know) as some kind of a sore loser which is demonstrably false.
The plot twist for the last point: he is still in the running for round four and his former PhD students did win major parts of round three.
Filippo Valsorda seems to be happy to ignore the fact that NIST already let an NSA backdoor in, as recently as 2014:
is he really just going to ignore something from 8 years ago?
Yes, he appears to be unreasonably dismissive of the blindly obvious history and the current situation.
As an aside, this tracks with his choice of employers - at least one of which was a known and documented NSA collaborator (as well as a victim, irony of irony) before he took the job with them.
As Upton Sinclair remarked: “It is difficult to get a man to understand something when his salary depends upon his not understanding it.”
Joining Google after Snowden revealed PRISM and BULLRUN, as well as MUSCULAR, is almost too rich to believe, Meanwhile he asserts and dismisses Bernstein as a conspiracy theorist. It’s a classic bad faith ad-hominem coincidence theory.
First, last I checked, Filippo does not in fact work at Google.
Second: the guidelines on this site forbid you to write comments like this; in fact, this pattern of comments is literally the most frequent source of moderator admonitions on HN.
Filippo hardly needs me to defend his reputation, but, as a service to HN and to you in particular, I'd want to raise your awareness of the risk of beclowning yourself by suggesting that he, of all people, is somehow compromised.
Thanks for letting me know. I think I'll consider both of them compromised.
Man, mobile typos suck.
If, rather than hoarding offensive tools & spying, the NSA had interpreted its mission as being to harden the security of government infrastructure (surely even more firmly within the remit of national security) and spent its considerable budget in that direction, would authn and authz controls have been used at the OPM?
This is my understanding as well. I asked this very same question less than a week ago, and now it's the first Google result when you search "OPM Dual_EC_DRBG."
The response to my comment covers some circumstantial evidence. But I'm not personally convinced; human factors are a much more parsimonious explanation.
The carve-out you mention is a decent idea on paper, but in practice is a difficult process. There's really no way to do it in any significant degree without basically putting all gov to a complete halt. Consider that government is not staffed with technical people, nor necessarily critically minded people to implement these systems.
There are ways to push for FOIA improvements that don't require this sort of drastic approach. Problem is, it takes a lot of effort on the parts of FOIA requesters, through litigation and change in the laws. Things get surprisingly nuanced when you really get down into what a "record" is, specifically for digital information. I definitely wouldn't want to have "data" open by default in this manner, because it would lead to privacy hell.
Another component of this all is to consider contractors and subcontractors. Would they fall under this? If so, to what degree? If not, how do we prevent laundering of information through contractors/subcontractors?
To a large degree, a lot of "positive" transparency movements like the one you suggest can ironically lead to reduced transparency in some of the more critical sides of transparency. A good example of that is "open data", which gives an appearance of providing complete data, but without the legal requirements to enforce it. Makes gov look good but it de-incentivizes transparency pushback and there's little way to identify whether all relevant information is truly exposed. I would imagine similar would happen here.
A private right of action and waiver of immunity solves most of the “bad actor” problems.
The big issue is how to preserve what actually needs to be secret (in the interest of the USA, not the interests of the bureaucracy) while forcing everything else to be public.
A lot of things are secret that don’t need to be secret; that’s a side effect of mandatory data classification and normal bureaucratic incentives- you won’t get in trouble for over-classifying, and classified information is a source of bureaucratic power. So you have to introduce a really strong personal incentive to offset that or nothing will ever change.
Personally, I don’t think that information should be classified if it came from public sources. Or maybe only allow such information to be classified for a short period of time, eg one year.
The longer and/or higher the classification level, the more effort should be involved, to create disincentives to over-classification.
I'm sorry, but very little of what you're saying makes sense in practice. I suggest submitting some FOIA requests to your local government to get some context and understanding of the difficulties.
The old Abe rhetoric was powerful but it always felt like it was only hitting home on two of the three points. Obviously government, by definition really, is of the people. The much better parts were for the people and by the people.
Qualifiers such as evil aren't really useful when there hasn't been a country acting honorably on that stage for a long time, if ever.
Here's a phrasing that might be more appropriate:
"Since we're backstabbers and scoundrels, we should exercise caution around each other."
Do you think it's tough for those regimes to pay someone to do FOIA requests for them? Or to get jobs at government agencies?
We should rethink the concept of a “secret”. If it’s really a secret, it will still be worth the effort to protect.
They are erroring on the side of caution because people have determined secret information from public information - like the energy in a nuclear bomb (censored) by the blast radius (public).
Another example is they want to protect their means and methods. But those means and methods are how they know most information. Often times it's easy to work backwards from they know x therefore y is compromised.
It's a hard problem similar to how to release anonymized data. See K-anonymity attacks and caveats.
Surely "keeping things a little more hidden" depends on reliable cryptography.
Not sure if the US with it's torture-base aka Guantanamo and torture-safe-houses around the world really has the right to call someone else "evil", i don't mean that as "whataboutissm" but that human lives are not more "worth" in the US as in Mainland China
I don’t know if that’s easily quantifiable, but I had a cryptography professor (fairly well-known nowadays) several years ago tell us that she only trusted 7 people (or some other absurdly low number), one of them being djb, to be able to evaluate the security of cryptographic schemes.
Perhaps thousands of people in the world can show you proofs of security, but very few of them may be able to take into account all practical considerations like side channels and the like.
There may be thousands of people in the entire world who understand cryptanalysis well enough to accurately judge the security of modern ciphers. Most aren't living or working in the U.S.
It's very difficult to do better. The mathematics is complex and computer science hasn't achieved proofs of the hypotheses underlying cryptography. The best we can achieve is heuristic judgements about what the best possible attacks are, and P?=NP is an open question.
> The mathematics is complex and computer science hasn't achieved proofs of the hypotheses underlying cryptography.
No unconditional proofs (except for the OTP ofc), but there are quite a few conditional proofs. For example, it's possible to show that CBC is secure if the underlying block cipher is.
Proof! the entire field of cryptography can prove absolutely nothing other than that a single use of One time pad is secure. the rest is all hand waving, that boils down to no-one I know knows how to do this, and I cant do it myself, so I believe it's secure.
So the best we have in cryptography is trusting "human instincts/judgements" about various algorithms. Which then further reduces to trusting humans.
Most programmers don't need to prove crypto algorithms. There are many situations where you can just use TLS 1.3 and let it choose the ciphers. If you really need to build a custom protocol or file format, you can still use libsodium's secretbox, crypto_box, and crypto_kx functions which use the right algorithms.
This is completely unrelated to the question being asked by the parent. They aren't asking about the average programmer. They are asking how many people in the world can truly 'prove' (to some reasonable degree) that the cryptography in use and the algorithms that are implementing that cryptography are 'secure' (to some reasonable degree).
Put another way, they are asking how many people in the world could verify that the algorithms used by libsodium, crypto_box, etc. are secure.
My point was that you don't need "thousands and thousands of people with the expertise to actually proove that the algorithms used today are really safe".
If the demand existed, there would be a lot more of those people.
The grandparent post is asking about the people who need to know enough to program TLS to
> let it choose