NSA and IETF, Part 9
blog.cr.yp.to
blog.cr.yp.to
I'm sure there's a game-theoretic optimum choice when it comes to accepting proposals from the NSA vs rejecting them out of hand, but I'm not sure what that optimal choice is.
https://archive.nytimes.com/www.nytimes.com/interactive/2013...
> Try to put yourself in the mindset of NSA as an attacker. You have a massive budget to "covertly influence and/or overtly leverage" systems to "make the systems in question exploitable"; "to the consumer and other adversaries, however, the systems' security remains intact". One of your action items is to "influence policies, standards and specification for commercial public key technologies". Another is to "shape the worldwide commercial cryptography marketplace to make it more tractable to advanced cryptanalytic capabilities being developed by NSA/CSS".
And when you read the Snowden docs and you come across to things like this 2010 GCHQ presentation[2], stating "for the past decade, NSA has lead an aggressive, multipronged effort to break widely used Internet encryption technologies" such as "SSL" and "SSH" and "VPNs"; that "cryptanalytic capabilities are now coming on line"; and that "vast amounts of encrypted Internet data which have up till now been discarded are now exploitable."
So we have these agencies like NSA and GCHQ, with stated, funded programs to make deployed cryptography exploitable (and historical evidence of them successfully doing just that)... It's an unbelievable conflict of interest for them to hold any role where they can shape what gets deployed. Absolutely bonkers.
And on DES specifically, it was both at once, not a binary. NSA in secret pushed IBM to cut the key size, while strengthening the algo against every attack except brute force. The design criteria were classified and IBM's own research docs were literally locked up under gov classification at NSA's request meanwhile when IBM personnel publicly denied any NSA involvement (and the NSA director publicly denied any algo weakening, again, a lie). So DES came out genuinely hardened against differential cryptanalysis but at the same time breakable by brute force by organizations with budgets like NSA's, by NSA's request/order.
For the "blue team" thing.. I guess it's actually better for them tactically to not spin off, because being NSA gives you authority in those circles. Standards bodies don't seem to treat the conflict of interest as a problem (as we can see), but rather as a qualification ("people who know cryptography best").
1: https://blog.cr.yp.to/20251004-weakened.html 2: https://web.archive.org/web/20240420184725if_/https://cdn.pr...
Bernstein is counting on you not knowing that, even though it's a very rudimentary fact about MLKEM.
It bothers me that he thinks so little of his audience.
> where you think NSA "proposed" MLKEM or had some hand in its design
Never said this and don't think it.
Kyber came from an academic team through an open NIST competition, no one is disputing that. The fight is over a spec for deploying ML-KEM without the ECC layer, and the fact that NSA and GCHQ are argumenting that that weakening is a good thing, and about corrupt standardization process.
The problem with your claim that there's a corrupt institutional process --- apart from knowing who the people are behind this "institution" and finding it risible that any of them are taking cues from NIST, let alone NSA --- is that the institutional is already delivering the outcome you say you favor: default, Recommended=Y, standards track hybrid constructions, the ones used by all mainstream software with PQC.
Maybe we should treat standards like we do a free market - let anyone implement what they choose then let people chose which to adopt, but the main thing is get government out of the entire process.
If the government wants to standardise, that’s fine… just don’t make it an industry standard adopted by civilians. Let them have their weakened protocols will the market moves on
Bernstein is a co-author on NIST PQC competition submissions that didn't win (Classic McEliece, which just had a huge new research result, and Streamlined NTRU Prime, a lattice cousin to MLKEM).
When CRYSTALS/Kyber was selected in the NIST competition instead of SNTRUP, Bernstein didn't take it well. He claimed malfeasance by NIST and sued them for allegedly hiding documents.
Meanwhile, over the subsequent years, the world has continued turning on its axes. CRYSTALS/Kyber is now ML-KEM. Because many cryptography engineers and other security people think there's a lot of urgency to getting PQC deployed (because of harvest-now decrypt-later [HNDL] attacks), the IETF got a move on standardizing hybrid ECDH/MLKEM TLS 1.3, which is what everyone uses.
Nobody at IETF has ever to my knowledge even hinted that anyone should avoid hybrids. There is a standards-track RFC defining ECDH/ML-KEM hybrids.
There are environments where hybrids are problematic. You won't likely use any of them ever. Some of them occur within the US Government, and some of them are on highly constrained platforms (people seem to disbelieve this is ever really a thing but I once gameovered a smart meter because its RF protocol only had like 16 bits of counter space for CTR).
Because of this, there is also a proposed informational RFC --- not a standards track document --- that documents what pure MLKEM looks like in a TLS 1.3 setting. Bernstein's entire argument is that this is an NSA plot.
For discussion on Bernstein's objection to that IETF draft see article from ~month ago, "NSA and IETF: Fairness":
The mere publishing of an RFC has customarily been treated by developers as a stamp of approval from the IETF.
The NSA, contractors and their fans argue that simply adding a "RECOMMENDED=N" in an obscure section of this draft will somehow prevent said implementations in deployments.
However, as an example, Canada's NSA equivalent specifically requested the draft to be published so that they can use it to support their poor choice in deployment of solo ML-KEM nation-wide.
While ML-KEM may be sound, significant bugs in implementations in the wild continue to be published.
To be clear, CRQCs do not exist today.
ECC is battle tested, proven, and is used today.
It makes no sense to delete working cryptography and replace it with potentially buggy, non-battle tested implementations of new cryptography for a threat that does not yet exist today.
Instead, you fight HNDL [1] with hybrid which preserves the safety of today, and hopefully also, tomorrow.
No serious security person should be recommending otherwise which is, perhaps, why some may question the motives of those that are pushing for solo ML-KEM.
[1] Harvest now decrypt later
Obviously, Bernstein is counting on you not following that level of nuance; he'd much rather you believe he's arguing for hybrids against people who are trying to exterminate hybrids.
For clarity: I am not a cryptographer; I'm a vulnerability researcher who does some cryptography work and for several reasons I talk to a lot of academic cryptographers and cryptography engineers. You could not pay me to design a PQC transport protocol for you.
Take a look at the crypto from the 80's and 90's. They are considered bad jokes nowadays, badly designed and easily breakable. Why would the first-generation PQC algorithms be any different? Of course they're going to be broken and ridiculed in 20 years, in ways you cannot comprehend yet
To that I will only add that lattice cryptography is of approximately the same vintage as elliptic curve (both started in the late 1990s) and MLKEM is past the level of maturity relative to lattices that 25519 was relative to the original P-curves. (Correct me where I'm wrong here --- this is off the top of my head). This isn't "the first generation" of anything.
Just another nuance I think Bernstein is counting on you, the real audience for these posts, not having any intuition for.
Actually, based on the WGLC, or the three of them rather, it's pretty clear that Ph.D cryptographers significantly prefer hybrid over pure ML-KEM.
> he'd much rather you believe he's arguing for hybrids against people who are trying to exterminate hybrids.
The brigade by the NSA (6+ votes or more if you include NSA contractors), the AD being former NSA and the moderation of Dr. Bernstein for a footnote seems pretty fair and balanced </sic>.
Meanwhile, the lead of the EU PQC program, professors from several universities, Ph.Ds and, additionally, legendary cryptographers all expressed significant concern and even stronger opposition to the publishing of the draft.
Finally, the chairs refused to share their methodology in determining consensus when asked by several Professors and Ph.Ds.
What's noteworthy about the last list of sponsors of his position that Dan Bernstein posted was how few of them were cryptographers.
The great Dr. Orr Dunkelman was admirably vocal in his opposition to the publishing of this draft.
I am. I literally hold six patents around secure key generation and management. I stand by DJB's points.
Can you explain a bit more regarding your statement that DJB's POV on the matter has no broad support amongst his peers? I'm not in the field but Bernstein seemed like a highly respected member with a long track record in the crypto community, at least from the outside. Do you think the community is wrong or is it DJB who's wrong and why? There's also a good chance that I totally missed the argument being made.
Downthread we develop more clarity about what it is Bernstein is actually in an argument about. It isn't hybrids vs. pure!
Peter Duesberg, a Ph.D. in molecular biology / retrovirology who taught at Berkley and was a member of the National Academy, who maintained that HIV does not cause AIDS and that antiretroviral drugs do more harm than good.
Walter Freeman, M.D. academic neurologist and first chair of neurology at George Washington University who believed that severing frontal-lobe connections could stabilize personality and stop pathological cycles of thought.
Charles B. Davenport, Ph.D. in biology, geneticist and founder of the Eugenics Record Office.
Henry H. Goddard, Ph.D. in psychology, intelligence-testing researcher and later professor of abnormal psychology who believed intellectual disability, poverty, prostitution, and criminality constituted a hereditary family type.
Clarence Cook Little, Harvard Ph.D., mammalian geneticist and prominent cancer researcher who insisted for years that the evidence did not establish a causal relationship between smoking and lung cancer.
Fun game. We could laugh at all of them, and your examples too, if not for the damage they caused.
How many of them spoke before on this mailing list, in any capacity what so ever? I suspect this is 99% people who showed up because you organized a brigadging, because you incited people and told them to show up and be completely outraged.
There's a >0% chance that DJB could be correct that there is some risk to this spec (which notably is not seeking recommendation status! So WTF?) The people approving and wanting this aren't fools, aren't lackies, aren't some great foe. There's little real opposition? Making up ghosts and enemies lurking in every corner, brigading people to show up in IETF meetings, who have never participated before, just to spread heat and anger you've programmed them for, is ignoble & indecent.
All too recently: https://news.ycombinator.com/item?id=48760490 https://news.ycombinator.com/item?id=48811887
I don’t have a dog in this fight, but some extremely important RFCs are only on the “informational” track. RFCs 1945 (HTTP 1.0), 4627 (JSON), 2818 (HTTPS), etc.
/s
The government has intentionally acted to weaken DES, standardized Dual_EC_DRBG, performed subtle subterfuge through interfering how NIST operates to inject weaknesses and vulnerabilities, trying to weaken SSL and IPSec, 4G smartphone encryption.
These are all documented examples of the NSA engaging in bad faith. So whether or not it is happening in this particular case, there’s now just zero trust in the institutions acting in good faith. And given it took decades for the actions to come out after they were taken, how do you expect someone to answer your request to present evidence there’s anything nefarious happening now?
Anyway, that’s what I think a fleshed out argument would look like
NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since.
That's why you use ML-KEM 1024 at all... As part of a hybrid.
But yes, this is the useful conversation to have. There are other scenarios! You can get into more detail on where MLKEM came from, for instance.
They laugh at us while we try to think of how 1024 is better than 768: "bigger is better, right?" "does 1024 refer to the number of years it takes Nightmare Moon to break the code?"
Let's keep the thread coherent: the original claim, by cryptographer 'cassonmars, is that the issue here is NSA pushing bad standards. It's not "hybrid vs. pure", which is a non-issue. All I asked for was a plausible story about how NSA might have pushed a bad PQC standard.
How do you save your poisoned wine? A hybrid with 1024 is made less trustworthy if the NSA pushes 1024 alone, since then we know that they want customers to use 1024 alone, which is what they would want if it was weak. But they know that we would know that, so if they really want to help us they should withdraw the draft. If it was strong but we know why, they shouldn't want to make us doubt ourselves. If it is strong (and 512 and 768 are not) they can't tell us, and can only subtly point to their own double encryption and security level documents. The only move that can cover all the cases is a hybrid with 1024, so this draft is a bad standard.
As for your post below
> it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others
Ok. My argument is they know all lattice schemes are weak and the push to use a lattice-only scheme is precisely to have a cryptographic mechanism they can easily bypass without a classical known-secure backstop.
In addition to the previously-stated reason why that argument is inoperative (besides being unfalsifiable, it admits a strategy where NSA "poisons the well" to get people to avoid a particular construction or family of algorithms, so that we all move to weaker ones --- a counterfactual that should be much more vivid after what was released this week!)
You’re arguing in bad faith throughout the thread, taking the weakest possible interpretation of anything said and extrapolating to nonsensical positions to paint the people who disagree with you as idiots. Please do better.
Agree or disagree with my arguments on substance; it's fine, we're all coming to this with different priors, levels of experience, familiarity with the drama and with the underlying issues, etc. But this "do better, you're in bad faith" stuff is just chaff, and you'd do well to leave it out of your comments. (It's hard sometimes for me to do that, too. Disagreement is tough!)
As for why he didn’t advocate for hybrid schemes for 25519, I can’t speak for him. I’m going to guess that it might have something to do with elliptic curve cryptography preceding lattice by 11 years in teens of initial implementation and in more practical terms it’s ahead in terms of research and application by 25-30 years for constructing the algorithms and building solid implementations.
Lattice cryptography is fairly nascent and new, with most attention in the past 10-15 years. Both algorithms and implementations have seen significant vulnerabilities discovered. But you know obviously know this which is why it feels to me like you are presenting arguments in bad faith.
This is especially useful to know given that mainstream elliptic curve and lattice cryptography are of roughly the same vintage. As commercial propositions, things actually getting fitted into protocols, both date back to the mid-1990s. For a time, there was a question as to whether NTRU might succeed RSA rather than elliptic curves!
Nobody's arguing from "both sides". You're continuing to misconstrue what's happening. It's also not true that "nobody is proposing lattice-only". The whole point of this story is that pure MLKEM is a proposal on the table. It has to be, because there are environments that need to use it (that, or not do PQC at all). None of them are environments you're ever likely to work in, and hybrids remain the default and the only PQC KEM standards-track RFC for PQC in development.
I'm going to keep pointing out that a lot of the reason you don't have this context is that Bernstein doesn't want you to. He expects you to take his word for it.
The first elliptic curve paper (1985) precedes the first lattice paper (1996) by 11 years.
2005 is when LWE was published which provided the first theoretical foundation to construct lattice encryption correctly with guaranteed mathematical guarantees. NTRU was plagued with a lot of problems precisely because it lacked this foundation and no one seriously used it or adopted it.
2005 is also when the NSA publicly formalized ECC in its suite B of algorithms and saw widespread standardization across NIST, IEEE, and ANSI. It was fairly well understood how to construct ECC correctly too precisely because it had already been widely studied for like 20 years.
So in 2005 you’ve got ECC relying on well known mathematical problems with a solidly understood foundation having been studied for 20 years vs lattice which basically had its first description of how to do lattice.
Now maybe if something like Snowden had happened prior, adoption of ECC might have looked differently and the same people would have advocated different things. Hard to tell. But trotting out NTRU like it had any chance in hell with competing with ECC or claiming that ECC and lattice are “basically the same time frame” is just a fundamental disagreement on the facts that isn’t supported by the timelines of each.
But sure if lattice truly is resistant to classical attacks you generally don’t lose much from a cryptographic security perspective except that my understanding is it’s still worse on all metrics (compute and size) than ECC. And AFAIK lattice is much more complicated than ECC (both in theory and implementation) - where there’s more complexity there’s more room for mistakes (as the NIST PQ standardization effort demonstrated - very nearly adopted algorithms later proved insecure). ECC by comparison isn’t actually much worse than RSA on that front which again is why no one was proposing dual schemes in 2005,
I think the bigger thing is that a lot of us are older than we realize, and 2005 was a very long time ago --- over 20 years. This is like the distance between Nevermind and Houses of the Holy.
Finally: I'm not letting anybody, including Bernstein, get away with allusions to SIKE as a way of impeaching lattice cryptography. Supersingular isogeny cryptography was moon math, and everybody agreed at the time. It has zero relation to lattice problems. It has zero relation to anything! (Ironically, if it did relate to cryptography in use today, it'd be to elliptic curves).
Also Curve25519 is just a specific set of constants for ECDH. The underlying algorithm was already designed and well understood. The main advancement was selecting the constants carefully to be free of side channel attacks and to be fast. If you can’t see how that’s a very different situation I really don’t know how to help you understand the concern.
ALSO. The proposal is to replace cyclotomics with Gallois field precisely because they are better understood and easier to construct correctly.
> The NTRU Prime project recommends switching from "cyclotomics" to "large Galois groups" to reduce the attack surface in lattice-based cryptography. After this recommendation was published, Gentry's original (STOC 2009) fully homomorphic encryption system was shown to be broken in quantum polynomial time for cyclotomics.
I coined the name Deep Crack for the EFF machine that brute-forced DES in 56 hours on a $250K budget. Ostensibly a play on Deep Blue and Deep Thought. The official hidden message, per my email in 1998: there's a Deep Crack in the government's export control policies. Unofficial hidden message: they strengthened DES against every attack except the one their budget could afford.
Not responsible for allusions to the Liberty Bell, Marion Barry's favorite nose candy, Mark Felt's alias, Linda Lovelace's famous movie, or Douglas Adams's computer that answered forty-two. Responsible for the observation that when someone says NSA "rescued" a standard, it's worth asking what crack they left in it for themselves.
The first key's free!
Deep Crack origin story (Denise Caruso + Gilmore + Hopkins, 1998):
https://www.donhopkins.com/home/archive/humor/deep-crack.txt
EFF DES cracker:
https://en.wikipedia.org/wiki/EFF_DES_cracker
Deep Crack Chip:
https://en.wikipedia.org/wiki/EFF_DES_cracker#/media/File:Ch...
EFF's Cracking DES Page:
https://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/
Sun DES chip socket (export control) and boot ROM easter egg:
A good number of the proposals (in particular, the proposals that actually got close to being chosen), are based on lattice constructions.
NTRU's underlying construction has been available to scrutinize for 30 years, whereas the Module-LWE proposals (Kyber being one) has had 11 years. Keep in mind, the largest employer (and under very tight classified controls) of number theorists _is_ the NSA. In terms of overall intellectual power, if there _is_ a problem in the MLWE constructions, they'd very likely be the first to find it, all while not saying a single word. Then, despite clear objections laid out by people with explicit expertise on the distinctions between RLWE and MLWE, especially w/r/t parameter choice, Kyber, under weaker parameters, was chosen anyway.
We can't rely on the obvious tells anymore – they've already played that hand (EC-DRBG) and were caught. If a bad standard is being pushed, it has to be done in a way that is so subtle, that it literally comes up to, "yeah, maybe this is weaker, but we haven't found a way to prove that". DJB already lost the selection process, so now the goal is to at the very least, avoid recommendations that push an unshielded, far less historically tested option, with no helpful antidote if it were to be broken.
I get that generally assuming conspiracies is a bad starting place for debate (after all, how do you disprove a hypothesis that is expected to be so surreptitiously constructed that it evades all ability to be scrutinized?), and I'd similarly think this is an unreasonable assumption, except for the fact _it has already happened and been exposed, multiple times_.
But the bigger problem is with your logic. It applies to literally any other choice NIST could have made. If they had selected Classical McEliece, another Bernstein submission, people like you would be on threads pointing and saying "see, the security of McEliece is collapsing before our eyes, of course NSA forced NIST to choose it".
https://cryptography.watch/articles/djb-cryptographic-odysse...
As an end-user I find djb's critics are generally pathetic
djb's work, specifically how others react to it, is like a litmus test for self-aggrandizing idiots
“The road to developing this standard was smooth once the journey began... However, beginning the journey was a challenge in finesse ... After some behind-the-scenes finessing with the head of the Canadian national delegation and with C.S.E., the stage was set for N.S.A. to submit a rewrite of the draft ... Eventually, N.S.A. became the sole editor.”
https://macleans.ca/society/technology/nsa-says-it-finessed-...