Hacker News Reader

Comment by vlovich123 | Hacker News Reader

That’s a very unfair position to take when dealing with secret agencies who try very hard to obfuscate this stuff - it is hard to provide evidence for in the moment.

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

View on HN

It's a simple question. I'm not asking anybody to prove anything. I'm literally asking: propose the PQC standard IETF could have subverted, and give a sketch of how they could have done it. The bar is merely "plausibility". I'm not asking whether NSA has subverted standards before; obviously they have.

NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since.

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

I don't know what this is, but it isn't an answer to the question. I'm starting to notice that nobody is able to come up with an answer.

There is no public reason to think that 1024 is better than 768, or DJB's S-NTRU-P 761. The NSA might know something, but we can't trust them. So, use a hybrid, in case they are really just trying to protect us.

That can't be the argument --- it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others. The reason for that is a cryptographic concept known as the Vizzini Conjecture: the argument you just put forward can be applied to literally any cryptographic standard NIST authors. Since NSA knows that, and knows you know it, you can clearly not choose the wine in front of you. It must be that the standard NIST picks is the only secure one, so that NSA can see it tainted by NIST association.

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.

Yes, they trick me and I pick the poisoned wine... But wait, no, I used a hybrid. Imagine the code can't be backdoored (it's proven not to crash/be slow/be exploitable) so at worst it can make the security no better. At best, the NSA knows a whole new subfield of cryptography (from history: differential cryptanalysis) and it really is more secure.

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

There is nobody at IETF saying you shouldn't use a hybrid! In fact, it's the exact opposite: hybrid ECDH/MLKEM is a standards-track RFC, and the proposed pure-MLKEM RFC is not, nor is it "Recommended" (in IETF parlance).

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.

No, the original claim was by me. And I gave you a plausible story. You just didn’t want to hear it.

https://news.ycombinator.com/item?id=48820336

This is a link to a comment from 38 days ago.

> Let's keep the thread coherent: the original claim

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.

In fact, the default behavior in every web browser right now is to use a hybrid.

They did both - they strengthened it from differential integrity but weakened it by picking a known-to-be-too-short key length. Meaning they had the compute power to crack it but others couldn’t do the same through pure algorithmic means.

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.

See, here's another argument that doesn't work here, because Bernstein very publicly backs a different lattice cryptography scheme.

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

Does Bernstein back using the alternate scheme exclusively or combined as a hybrid?

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.

We'll never know, because he only started advocating for hybrids after MLKEM happened. When he did 25519, he did not advocate for 25519/RSA or 25519/FFDH or 25519/P256 hybrids.

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

Why do you then argue from both sides that no one is proposing lattice only for standardization while simultaneously clearly pushing that it should be lattice only? And clearly there is a concern for the lattice only recommendation, even if not officially a standard, being recommended as one.

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.

Lattice cryptography is not in fact fairly nascent. It's new to you, which is not the same thing. That's why I raised the point about 25519's vintage: you're thinking about 25519 in today's context (which, ironically, has taken some of the shine off of it!) and not in the context of 2005, when it was introduced. When TextSecure adopted Curve25519, Bernstein didn't complain and say "you should be doing hybrid triple-FFDH/triple-Curve25519".

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.

We seem to be reading different history books.

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,

Regev in 2005 was hugely important, but '90s NTRU remains unbroken, and Atjai was 1996. The Suite B thing undercuts your argument! You've managed to establish 25519's publication the same year as Suite B. Again: Bernstein didn't ask people to run 25519/MODP hybrids.

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

My point is not about a specific algorithm or application. I’m talking about the family elliptic curve vs lattice. Bernstein isn’t asking people to run hybrids because the mathematics is simple and well understood.

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.

You know who wouldn't agree that Curve25519 is "just a specific set of constants for ECDH"? The guy who wrote SafeCurves. Also: you've lapsed into talking down all lattices, which leaves you in the position of explaining why Bernstein submitted/sponsored sntrup.

All I’m saying is that lattices are newer and more complex. Bernstein is proposing a lattice scheme AND saying it should be hybrid.

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.

Re "NSA rescued DES from differential cryptography":

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:

https://news.ycombinator.com/item?id=34125377

Reply on news.ycombinator.com