Double encryption: Analyzing the NSA/GCHQ arguments against hybrids
blog.cr.yp.to
blog.cr.yp.to
[0]: https://cyber.gouv.fr/en/publications/follow-position-paper-...
"Combination of Classical and PQC Security: The secure implementation of PQC mechanisms, especially with regard to side-channel security, avoidance of implementation errors and secure implementation in hardware, and also their classical cryptanalysis are significantly less well studied than for RSA- and ECC-based cryptographic mechanisms. In addition, there are currently no standardised versions of these mechanisms. Their use in productive systems is currently only recommended together with a classic ECC- or RSA-based key exchange or key transport. In this case, one speaks of a so-called hybrid mechanism. Parallel to a PQC key transport, an ECC-based key exchange using Brainpool or NIST curves with at least 256 bits key length should be performed. The two shared secrets generated in this way should be combined with the mechanism given in Section B.1.1 of this Technical Guideline. Here, the standard [96] in its current version explicitly provides the possibility to combine several partial secrets. A hybrid approach, as proposed here, is further described for example in [5] as the most feasible alternative for a use of PQC mechanisms in the near future. Provided that the restrictions of the stateful mechanisms XMSS and LMS recommended in this TechnicalGuideline are carefully considered, these hash-based signatures can in principle also be used alone (i.e., not hybrid), see Chapter 6"
[0]: English version: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat...
[1]: German version: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikat...
It seems strange to pit a specific classical algorithm against a general-case PQ algorithm made up for the sake of argument, it feels like a bit of a straw man.
I've written hobbyist-grade implementations of both X25519 and ML-KEM-768 (aka Kyber). All other things being equal, I think arithmetic bugs in X25519 are more likely, given that it uses 255-bit integer arithmetic, requiring a custom bigint implementation if you want peak performance. Doing 255-bit arithmetic that is both fast, and provably does not contain limb overflow edge-cases (to name just one possible bug class), is hard. At the very least, it's not something I'd trust myself to be able to do.
On the other hand, Kyber arithmetic all fits within standard register sizes, without needing to split things up. This doesn't make it immune from arithmetic-related issues (as KyberSlash demonstrates), but it's probably easier to get right overall.
I agree that for the time being, the average X25519 impl will be significantly more trustworthy than the average Kyber implementation (or any other PQ construction), due to its maturity, but it seems dishonest to imply that PQ algorithms are inherently harder to get right.
Despite this, I am broadly in favour of Hybrid schemes. It seems like the anti-hybrid stance is mostly coming from large slow-moving orgs - sucks to suck, but don't let your unagility hold the rest of us back!
I understood TFA's point to be exactly this. That is, security designs that have existed significantly longer and were in active, widespread use will have been analysed far better than the new kids on the block.
However, I think there is a decent chance that the NSA does know more about post-quantum cryptography than the open crypto community.
If post-quantum algorithms are used alone, everyone is playing into the NSA's strengths and gives them the ability to break encryption, that they would not have today with ECC.
Given that we are still some ways off from quantum computers that can actually break ECC, we would be trading security now for insecurity now.
What makes you think that practical quantum computers are a certainty? Everything I have read makes it seem more like a 'we can't not try to figure it out, because it might work' rather than a 'we are on the way to doing it, it just needs more time'.
We have fusion power on small scale, we don't have it on commercial scale.
Seems to be the same argument.
We have never had fusion power on a small scale (we have had fusion ignition/reaction, but never [afaik] generated usable power), let alone showed continuous growth in scale of that power over the years.
They're not the same. Fusion is a 'science' problem, quantum is (mostly) an 'engineering' problem.
See Joux's "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions"
https://link.springer.com/content/pdf/10.1007/978-3-540-2862...
Of note is that when you look at the multiple parallel executions of an iterated hash function at the level of whatever round structure that it is inside its compression function it becomes quite obvious that the result will not have the security level of 2^(m+n+...) as one would expect from the output length, but somewhere around 2^m+2^n (=2^m if m>n) as there is absolutely no mixing of state between the parallel executions.
If you have a moment can you please elaborate a little more on your second paragraph? Are you describing applying a similar method inside the compression function of the hash function? Any hash function? Where does the parallelism come in? Thank you!
In fact, the paper even mentions inverse of this in the context of the sketch of wider RIPEMD, where the sketch recommends some mixing between between the separate streams (particularly, exchanging one word of the state) between rounds, which the authrs view as enough to make their multi-collision attack infeasible.
The newer one-way hash structures, like those used by SHA-3 or by BLAKE/BLAKE2/BLAKE3 are immune to this kind of attacks (because they use either a sponge automaton or a structure similar to Merkle-Damgaard but augmented with a counter input for hashing each block, which is equivalent to using distinct hashing functions for all data blocks, instead of iterating the same hashing function, which can be exploited by the Joux attack mentioned by you).
That makes sense about newer functions being immune. However, note that both of the cascaded hashes must be immune to prevent this attack (as described in the paper).
But for all other devices - server, desktop, mobile phones etc which sports 64-bit CPUs clocked in GHz speeds, and GByte of storage, RAM this is seems sensible. Performing x25519 on these devices in addition to the PQC-algoritm should be a negligible cost.
The current methods have much lower overhead than any of the post-quantum methods.
Constrained devices that must be quantum-resistant while not affording the cost of hybrid algorithms, which are only slightly less expensive than pure post-quantum algorithms, should better use key-exchange methods based on pre-shared authentication keys, which have much lower overhead than the public-key methods.
They could still use hybrid key exchange methods, but very infrequently, only for updating the pre-shared authentication keys, in which case the slowness of the hybrid key exchange method would not matter.
Pre-shared only works for deployments with low-ish number of devices. We are talking about 1000+ devices.
If a hybrid key exchange method is used e.g. only after one thousand or even after one hundred of connections made with pre-shared keys, then the hybrid method can be very slow without significant impact.
This is the same like reusing in TLS 1.3 a previously computed shared secret for a new connection, just using this for a large enough number of successive connections so that the slowness of the constrained device does not matter.
You buy a $5 wifi-controlled lightbulb? There's a good chance it talks to its backend servers with TLS-PSK.
agree the term is extremely loaded. The closest "official" definition close to a "legal definition" comes out of ETSI 303645. This draft is the basis for what CENELEC is currently using to create an official standard which will become legislation for consumer IoT devices in Europe next year (Radio Equipment Directive / RED).
constrained device:
device which has physical limitations in either the ability to process data,
the ability to communicate data, the ability to store data or the ability to interact with the
user, due to restrictions that arise from its intended use
NOTE 1: Physical limitations can be due to power supply, battery life, processing power,
physical access, limited functionality, limited memory or limited network bandwidth.
These limitations can require a constrained device to be supported by another device, such
as a base station or companion device.
EXAMPLE 1: A window sensor's battery cannot be charged or changed by the user; this is a constrained device.
EXAMPLE 2: The device cannot have its software updated due to storage limitations, resulting in
hardware replacement or network isolation being the only options to manage a security vulnerability.
EXAMPLE 3: A low-powered device uses a battery to enable it to be deployed in a range of locations.
Performing high power cryptographic operations would quickly reduce the battery life, so it relies
on a base station or hub to perform validations on updates.
EXAMPLE 4: The device has no display screen to validate binding codes for Bluetooth pairing.
EXAMPLE 5: The device has no ability to input, such as via a keyboard, authentication information.
NOTE 2: A device that has a wired power supply and can support IP-based protocols and the cryptographic primitives used by those protocols is not constrained.
EXAMPLE 6: A device is mains powered and communicates primarily using TLS (Transport Layer Security).
Depending on how difficult you want to be, you can mean different things.
If you're being reasonable, you might for example think of a $5 retail price wifi-enabled lightbulb. It might use a chip such as the ESP8266 with 80 KB of memory. Depending on how efficient the SSL library is, supporting 4096-bit RSA on these chips can be a real squeeze, so some SDKs only support 2048-bit. But it's still a 160 MHz chip, so it can run grown-up cryptography.
If you want to impose nigh-impossible requirements to torpedo the whole proposal, then demand the cryptosystem work on the tiny sips of power available to contactless bank cards and ten-year-battery-powered smart gas meters; and that it work for automotive door locking where their budget is like $0.02 per chip.
But customers are still counting every um2 chip area, gates/chip and ROM, code mem in bytes in 2024 to minimize per-device implementation cost. Automotive, a lot of consumer products and large scale SCADA systems are example of systems where these types of questions are at least evaluated during requirement development and system exploration, design. And yes, shaving of a few cents due to being able to use a MCU with 8 kByte RAM instead of 16 kByte can save a lot of money. And it is being done.
When I look and crypto algorithms (in a wide sense) I see more utility in having a primitive that provides AEAD, or can be reused n different way to do secure hashing (for integrity, kdf, random generation for example) as well as AEAD, than having lightweight block ciphers. Most lightweight block ciphers have small block sizes, short keys and a lot of rounds. Lyckily there are some nice algorithms that we can trust. And AES is very scalable.
DJB also explains needs for hybrids as follows: we don't yet have any post-quantum algorithm that we can confidently use as a direct substitute for well-established classical algorithms. So for now we need to consider possibilities for QC becoming real and PQ algorithms broken, hence hybrids.
One sentence with unfortunately chosen words shouldn't invalidate the - in my view largely reasonable - arguments of the whole text.
> "hybrid solutions make implementations even more complex".
> If the words are taken purely at face value then they're clearly correct
The argument here is that the complexity is mostly due to the adding of new algorithm, not the hybridization. It goes on to argue that the added complexity due to the hybridization itself is negligible, especially considering the level of security provided.
In both cases the work is in adding and testing the new thing.
Whether you comment out or not the old thing does not really change the amount of programmer work and the execution time and required resources are also not affected significantly in this case.
He's written about it here.
I'm really curious about this now. How does he write something like half a dozen different papers per year as a sole author? These aren't short papers either; they're dozens of pages. Usually when I see a professor with an incredibly prolific publication history, it's because they have a bunch of PhD students (each working on a paper per year) and they collaborate with a bunch of other professors.
He also seems to be quite a character; unafraid to publicly document battles with his employer, IEEE, and the US government.
And then some paranoid freaks come along that just use both.. Jikes.
This is of course just me thinking loud here and pure speculation. We will probably never know for sure.
Outside of the NSA (and its affiliates), most of the cryptographic community seems to have come together in support of hybrids, which would greatly accelerate the adoption of some level of post-quantum defense. With even the most “liberal” cryptographers thinking that more careful cryptanalysis of post-quantum algorithms is needed before widespread adoption as the sole line of cryptographic defense, if the NSA manages to convince sufficient people that hybrids aren’t viable enough for production (and thus stick with classical algorithms) they may be able to maintain the ability to break sensitive communications for longer when and if their quantum computer efforts have a breakthrough.
I honestly think the NSA learned their lesson with the whole debacle around Dual_EC_DRBG and skepticism about their elliptic curve seeds - especially given the continued exponential growth in sensitive electronic communications and records, they want the algorithms as secure as possible without a backdoor that could leak and be a foot-gun for US communications as well.
Instead, they’ll just throw more money at making a usable quantum computer than the next country spends on their entire cryptographic infrastructure, and get targeted backdoors into software/hardware implementations of the encryption algorithms so they can focus their attacks more precisely.
My guess would be that there are multiple segments to the NSA, some of whom have access to the hardware level backdoors and others that want the software to be easier to compromise.
I would suggest that if you are a target of the NSA the encryption you are using does not matter one bit, they will find a way to hack you and steal any keys to systems they need and you probably won't even know about it. I'm not so convinced about the mass surveillance actually being that useful to be honest, even with current tech there is just too much of it to help.
Time to use tinfoil chat! https://github.com/maqp/tfc