Bernstein's Blog

Posted Dec 10, 2025 9:46 UTC (Wed) by farnz (subscriber, #17727)
In reply to: Bernstein's Blog by brunowolff
Parent article: Disagreements over post-quantum encryption for TLS

The NSA as an organisation is schizophrenic about encryption strength.

One part of the NSA is tasked with monitoring communications, and has a vested interest in weakening the encryption used to a level that the NSA can break, while another part is tasked with making USA entities' (including private citizens) communications secure against foreign adversaries, and has a vested interest in making sure that even if China's Ministry of State Security successfully infiltrates the NSA and matches or exceeds their capabilities for a time, encryption is still too strong for the MSS to decrypt.

And that makes tracking what the NSA is doing extremely hard from the outside; we won't know for decades (if not centuries) which part of the NSA is pushing for a pure PQC algorithm. If it's the part that wants to break encryption, then we are right to reject it; but if it's the part that wants to keep USA communications secure against foreign intelligence agencies, and they know a way to break all known hybrid algorithms that they can't disclose because the monitoring side of the agency is actively exploiting it, then we do want pure PQC.

But it's impossible to tell which is which from the outside - and we've seen examples of both (NSA insisted on a change to DES that protected against a cryptanalysis process that wasn't yet publicly known, but NSA also insisted on specific constants in Dual_EC_DRBG that weakened it if you knew how the NSA had chosen those constants).

to post comments

Bernstein's Blog

Posted Dec 10, 2025 11:03 UTC (Wed) by johill (subscriber, #25196) [Link] (1 responses)

Definitely true, though I think

> they know a way to break all known hybrid algorithms

is highly unlikely. There isn't even a single hybrid construction, you have hybrid KEMs (of use e.g. for TLS), hybrid PAKEs (likely of no use for TLS), and probably others, those are the two I've recently looked into (for 802.11.)

(KEM = Key Encapsulation Mechanism, PAKE = Password Authenticated Key Exchange)

Now from a TLS perspective you could argue that hybrid KEMs are the only interesting case, but even then it seems pretty hard to imagine that effectively doing two KEMs (say ECDH and ML-KEM) in parallel and mixing the results with a strong hash would result in something weaker than each portion. Even if one side was broken to the point of always returning zeroes, you can't predict the output of a say SHA-2 has over the combination (which might be but is not necessarily simple concatenation.)
There's a current TLS draft (https://datatracker.ietf.org/doc/draft-ietf-tls-ecdhe-mlkem/) that's widely deployed which simply concatenates the two secrets. Obviously that only works if the full resulting secret is always used, but TLS always uses an HMAC (HKDF-Extract) to derive other keys from it.

PAKEs are more complicated because ML constructions apparently don't have indistinguishability properties, so an attacker can statistically check offline whether or not they guessed the right password, so you have to be really careful when designing hybrid PAKEs to not make it weakest-of-both, for example a trivial "parallel + combine-by-hash" would be weakest-of-both since an attack on each one lets an attacker discover the shared password.

Ultimately, I think it's extremely unlikely that there's a class attack against hybrid constructions to the point of making it something that's fundamentally broken/undesirable for all use cases/all kinds of hybrids.

In the FAQ (I think) NIST brings one example where a hybrid is needed for "protocol reasons" (IKEv4 I think), but I don't really understand what "protocol reasons" means while we're changing a protocol to include PQ crypto. I think if they (or adjacent folks) knew about a class attack against that, they'd recommend redesigning those protocols entirely (and possibly breaking backward compat instead, which I assume could be the only "protocol reason".)

Not that any of this gives us more information as to their motivations :)

Personally, I'm leaning towards hybrids because I really see no good reason not to and I'd think it's better to guard against all sides. Yes, in general one needs to be careful about how ones does that. Also, the overhead is pretty small (data exchanged for ML-KEM is at least an order of magnitude bigger data than for say ECDHE).

What does the NSA know?

Posted Dec 10, 2025 11:53 UTC (Wed) by farnz (subscriber, #17727) [Link]

The problem is that we don't know whether there's an underlying break that applies to all the current hybrid constructions, or whether the NSA has a set of 100 known tools that between them break all the known hybrid constructions.

And because the NSA is so hugely secretive, we have no way of knowing whether or not they've got a huge set of tools that break hybrid algorithms but not pure PQC or whether they're pushing for pure PQC because they've broken the pure PQC algorithms suggested, but not the hybrids.

Indeed, it's even possible that both are true, and we're screwed either way, with one bit of the NSA pushing for pure PQC because they can break all the hybrid options and want security, and another bit pushing for pure PQC because they've broken that and want insecurity.

Bernstein's Blog

Posted Dec 10, 2025 18:15 UTC (Wed) by brunowolff (guest, #71160) [Link]

It seems pretty clear that NSA's attitude toward publically available encryption is that they should have ways to break it or work around it (by making correct implementations harder or having access to one of the end points), even if that includes risks of other bad actors also getting access.
It seems very unlikely they have any real interest in providing private citizens communications secure against foreign adversaries. They do have an an interest in protecting businesses communications, including that with their customers.
They didn't need differential cryptanalysis for DES when the 56bit key size was too small.
They also messed up with Dual EC, and some other actor used that infrastructure with different constants against Juniper routers.
We learned a lot about the NSA in 2013. That may or may not happen again before several decades go by.

Bernstein's Blog

Posted Dec 13, 2025 19:26 UTC (Sat) by marcH (subscriber, #57642) [Link] (5 responses)

> The NSA as an organisation is schizophrenic about... One part of the NSA is tasked with... while another part is tasked with...

You mean: "schizophrenic" like every other organisation made of many individuals?

> and we've seen examples of both (NSA insisted on ... but NSA also insisted on ...)

A huge part of this problem is: language. For instance, even when highlighting this precise issue, you keep using a singular "NSA" instead of the more accurate "some [other] NSA people" and used the adjective "schizophrenic" like it's a single person.

Language influences the way we think and this always struck me as an impressive example.

Bernstein's Blog

Posted Dec 14, 2025 16:43 UTC (Sun) by farnz (subscriber, #17727) [Link] (4 responses)

No, I mean that even one person doing everything the NSA is tasked with would face trouble resolving the inherent contradiction in its tasks; it's not that different people in the organisation have different priorities and interests, but rather that the NSA is supposed to both ensure that American businesses and government agencies can use unbreakable encryption no matter who they're communicating with, while also ensuring that non-American entities have no access to encryption the NSA can't break no matter who they're communicating with.

Even if the NSA was a singular person, that would be an impossible pair of missions to deliver on - how do you deliver encryption that's both broken by the NSA and unbreakable by anyone simultaneously to a non-American entity communicating with an American business or government agency?

Bernstein's Blog

Posted Dec 15, 2025 14:20 UTC (Mon) by paulj (subscriber, #341) [Link] (3 responses)

Standardising encryption that the NSA is confident only the NSA can break would be one way to meet that objective. Course, achieving that confidence in the face of an existence proof of a way to break an algorithm is... a tall order - but perhaps they have methods for that (e.g., judgement calls by analysing what systems other SIGINT agencies approve of/use for their governments and militaries; human intel from sister agencies; etc.).

Bernstein's Blog

Posted Dec 15, 2025 14:33 UTC (Mon) by farnz (subscriber, #17727) [Link] (2 responses)

The objective is that nobody (not even the NSA) can break it if both endpoints are USA entities, but only the NSA can break it if one or more entities using it is non-USA.

The only way to do that is to ban exports of encryption, with associated 1st Amendment concerns, so that the unbreakable encryption is only available to US entities, and to communicate with non-US entities you must use encryption the NSA is confident only the NSA can break.

Bernstein's Blog

Posted Dec 15, 2025 14:39 UTC (Mon) by paulj (subscriber, #341) [Link] (1 responses)

I think experience already shows this approach is impossible.

Bernstein's Blog

Posted Dec 15, 2025 15:08 UTC (Mon) by farnz (subscriber, #17727) [Link]

Indeed, but it's what the NSA is required to do - prevent non-US entities from communicating with encryption the NSA can break, while ensuring that US entities have access to encryption that cannot be broken at all, not even by the NSA, but only when communicating with other US entities.

This is an impossible task, and the NSA trying to do it is why it ends up completely untrustworthy - since you never know whether you're dealing with someone who's focused on the "non-US entities cannot communicate without us breaking their encryption", or whether you're dealing with someone who's focusing on "US entities must have access to unbreakable encryption".

And you'd still have that problem if the NSA was a single person - how do you know whether they're focusing on "non-US entities must not have encryption we cannot break" or "US entities must have encryption no-one can break"?