From the German BSI-TR-02102-1 ([0],[1]) guidelines
"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"
I believe there is maybe a little contradiction with the NSA's own 'Rule of Two,' as outlined in their Commercial Solutions for Classified Program (CSfC). It specifies two completely independent layers of cryptography to protect data :)
> Any reasonable risk assessment will conclude that the probability of an exploitable arithmetic bug or timing leak or randomness-usage mistake in the UltraKEM software is higher than the probability of such a exploit in the X25519 software.
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 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.
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.
I think there is a possibility that the NSA doesn't know much more about ECC than the open crypto community.
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.
> 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'.
The possibility that good-enough quantum computers might not be possible, is just an additional argument for not replacing the current key exchange methods with post-quantum methods, but at most only with hybrid methods, which retain at least one method for which there exists reasonable trust.
We have small, usable quantum computers and have grown them for years.
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.
<non-cryptanalyst blather>It seems to me that in all but the most resource constrained systems any novel implementation of hashing for source file validation should be multi-algorithm by default, since typical processing overheads are minimal and IO is already paid for. (IO could/should be pseudorandom and non-linear, FWIW). Encryption however can be more complex and expensive and there could potentially be more risk of recombinant side channels.</non-cryptanalyst blather>
Unless you have a weak hash function anyway you probably don't need to double it up (unless it's a weird non-standard construction like what Bitcoin does, there it's absolutely needed). Just use truncated blake2bp or something like that.
That attack is one of the reasons why the one-way hash functions based on the Merkle-Damgaard structure, like SHA-2 and the older hashes, are considered obsolete for hashing extremely large files.
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).
Thanks! Does this attack actually depend on extremely large files in any way? My understanding is that this method can always find fixed-size pre-images for collision attacks, and is unaffected by the pre-image size in a pre-image attack.
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).
The paper refers to the case where you build a even more secure hash function by concatenating output of multiple presumably secure hash functions. The resulting construction will still be as secure as the strongest component hash function used, which is what you want for the case of long term archival hashes/signatures (the obvious question is exactly what asymetric construction you are going to use to sign the resulting hash which preserves this property).
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.
I linked to the paper because it wasn't clear if OP's goal was to increase the security with the cascaded hashes or not, and also because I personally found this result very surprising and interesting when I first learned about it.
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!
As for the second paragraph: it is not an parallelism in the traditional sense, but as an shortcut in description of the design. To rephrase it in concrete terms: if you implement 128b block cipher as an two independent 64b wide SPN networks, you will not get the same security level as in 128b wide SPN network and the reason why is obvious from the SPN network diagram. (Compression function of hash function based on Merkle-Damgard construction is effectively an block cipher with somewhat large key)
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.
If I'm not missing anything, DJB does not consider constrained devices, where the code size and execution time with two algorithms may be a problem. Unfortunately these types of devices are also the types that may have very long lifetimes.
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.
Constrained devices should rather stick to the existing key exchange methods, until more certainty exists about the threat of quantum computers.
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.
The problem is that constrained devices with planned lifetimes of 20-30 years being specified today already are getting requests for inclusion, usage of PQC as well as classical algorithms.
Pre-shared only works for deployments with low-ish number of devices. We are talking about 1000+ devices.
That is why I have said that if updating the pre-shared authentication keys through separate communication channels is impractical, they can be updated through hybrid public-key based key exchange methods.
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.
These "constrained devices" come up so often in discussions about costs of cryptography, yet people rarely tell what exactly they are talking about. But given that cryptography is usually not very resource intensive to begin with (people often have incredibly wrong ideas about the actual computational costs of cryptography), and we increasingly have more powerful devices even in embedded settings, I doubt this is an actual problem.
> These "constrained devices" come up so often in discussions about costs of cryptography, yet people rarely tell what exactly they are talking about.
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).
> These "constrained devices" come up so often in discussions about costs of cryptography, yet people rarely tell what exactly they are talking about.
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.
I've been designing and supporting development of large scale IoT systems the last 15 years. And yes tech progress allows us to afford the use of better algorithms.
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.
Idk you lost me when you said using two schemes is not more complex than using one scheme. That doing two things at once is more complex than doing one is just not an axiom I'm willing to give up. And if you're willing to then i have to guess it's for ideological reasons than rational or logical ones. So at that point we're not analyzing the opinions of an expert organization we're just blasting cynicism at the "bad guy."
This sentence also bothered me, however, later in the text he says that of course there's a complexity cost, but that he believes the costs are quite low. I think one can reasonably argue that.
One sentence with unfortunately chosen words shouldn't invalidate the - in my view largely reasonable - arguments of the whole text.
I don't believe the claim was that it adds no complexity, but was saying it adds no complexity due to the reasons mentioned. He then goes on to write a paragraph about why that is the case, which you could of course respond to.
To add more, we are talking about a hybrid scheme that uses both a post-quantum algorithm and a classical algorithm, where the former is much slower than the later and a mere hybrid doesn't make much difference in performance. And this scheme will be presented as a single choice in cryptographic protocols, so if the protocol already supports multiple cryptosystems it should be just fine to adopt.
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.
You might have read that wrong. The article acknowledges the added complexity:
> "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.
Doing 2 things is more complex than 1, but doing 1 new and much more complex thing in addition to 1 old much simpler and already verified thing has very little complexity over omitting the old thing and doing just the new one.
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.
Thoroughly enjoyed reading DJB's writing. That style of arguing is so effective and yet so easily understandable by anyone having even basic understanding of cryptography. I hope there are students of his who are as good as him (or even better) and continue this kind of work for decades to come.
It looks like he doesn't have many students. His current title appears to be "Research Professor" and he's the sole author of every "new paper" mentioned in this blog post and most of the recent papers listed on this page: https://cr.yp.to/papers.html
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.
Why’s that? I had him back in undergrad and he was a spectacular lecturer. Course wasn’t too rigorous but definitely inspired a further interest in security.
No serious organization is going to deploy pure, non-hybrid PQC, as Bernstein tacitly acknowledges when he lists essentially all the major deployments of PQC in production to date, all of which are hybrids.
Not a podcast but if it helps, I wrote an overview article that goes from the basics of cryptography (eg RSA) and quantum computers (eg qubits), explaining how a post quantum cryptographic algorithm works (Kyber) and briefly touches on current hybrid implementations: https://medium.com/@dave1010/post-quantum-cryptography-its-a...
Not to suggest anything, but imagine you are a secret service in a world in which the cat (knowledge about safe cryptograophic procedures) is out of the bag. Wouldn't a great strategy be to invent some sort of story why that old reliable crypto is now potentially unsafe, so you propose a new standard, that may or may not have a known weakness.
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.
Putting on my tinfoil hat, I think there’s also an argument to be made that the NSA might want to slow down adoption of post-quantum algorithms, which their stance against hybrids definitely accomplishes. If there’s a single organization that could be 10-20 years ahead of where people think they are on something like a useful quantum computer, it’s the NSA (powered by the US’s absurd defense budget). If they can slow down the adoption of post-quantum algorithms, they can maintain their potential head start for longer and be able to break current cryptosystems and extract actually valuable information.
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.
Or could it be a bluff. Act like they don't want it, so some players feel they can use more advanced post-quantum algorithms and be secure, while NSA is decrypting it.
Maybe, but this argument holds less weight given that they’re the ones pushing for inclusion of these algorithms in the NIST standards, and are really only advocating against the hybrid algorithms.
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.
I'd be fairly certain they have hardware backdoors into most things...
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.
[0]: https://cyber.gouv.fr/en/publications/follow-position-paper-...