4 ms·

Supersingular Isogeny Key Exchange is one that was invented to be quantum-safe but turned out to be unsafe at any speed, so hybrid encryption is still a good id

Supersingular Isogeny Key Exchange is one that was invented to be quantum-safe but turned out to be unsafe at any speed, so hybrid encryption is still a good idea. You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.

some_furry 5mo ago
> You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken. No. Don't do that. If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. You want a Hybrid KEM, not encrypting twice. The nuance matters. https://durumcrustulum.com/2024/02/24/how-to-hold-kems/ https://durumcrustulum.com/2024/02/24/how-to-hold-kems/
- insanitybit 5mo ago
  > If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?
  - some_furry 5mo ago
    If you encrypt your data twice (taken very literally): c1 = E1(p, k1) c2 = E2(p, k2) If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p. What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken. ss1, ct1 = KEM1(pk1) ss2, ct2 = KEM2(pk2) secret = Combiner(ss1, ss2, [ct1, [ct2]]) This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated. This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations. I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
    - 3form 5mo ago
      It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
      - some_furry 5mo ago
        The thing is: Quantum computers don't break AES-GCM, ChaCha20-Poly1305, or any other modern authenticated cipher. Layering encryption or doing cipher cascades is pointless. The thing a cryptography-relevant quantum computer does is break RSA and elliptic curve cryptography, so that the underlying key (k1 or k2) is recoverable from its corresponding public component. Hybrid KEMs, such as mlkem768x25519 (a.k.a. X-Wing) is a simple abstraction with security proofs that does both classical (X25519 is elliptic curve) and post-quantum (ML-KEM-768 is lattice-based) cryptography and combines them securely into a single key agreement. "Encrypt twice" is bad advice. Even if you get the same approximate security, you're giving up a lot of performance. Encrypt once, but encrypt with a key you can be confident in the secrecy of.
        saltcured 5mo ago
        Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? The change of jargon from "encryption" to "KEM" doesn't mean anything to most people talking about this post-quantum risk. To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption. Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
        some_furry 5mo ago
        > Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? No, I'm saying that "hybrid KEM" or "chaining two KEMs" is very distinct from "encrypt twice". Confuse the two at your own peril. > To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption. Encryption is reversible. If you have the key, you can decrypt. It's not encryption if you can't decrypt. KEMs are their own class of algorithms. They combine an asymmetric encryption scheme with an all-or-nothing one-way transform (usually a key derivation function built on hash functions). It's the safest way to hold asymmetric encryption in practice (even not considering PQ; RSA-KEM beats RSA-OAEP in implementation safety). Calling KEMs "encryption" is misleading to the point of malpractice. I will push back on conflating the two. > Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. Your only defense-in-depth should be in delivering a strong pseudorandom ephemeral key over an untrusted network, and then using the tried-and-true AEAD constructions that we're already using today. Encrypt once. Do whatever you need to do to get the key exchanged securely. I write a blog that very regularly covers applied cryptography. I deal with newbie confusion all the time. It's very important that we talk about these things correctly on forums like Hacker News comment threads so that the people learning from us won't get more confused. Please don't call KEMs "encryption".
tptacek 5mo ago
No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices. People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.
- mswphd 5mo ago
  Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU. He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now. In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world. This is ignoring all of his other explicitly embarrassing behavior, for example 1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly. 2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust. 3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.
mswphd 5mo ago
The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places. The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve. So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.

some_furry 5mo ago

> You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken. No. Don't do that. If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. You want a Hybrid KEM, not encrypting twice. The nuance matters. https://durumcrustulum.com/2024/02/24/how-to-hold-kems/ https://durumcrustulum.com/2024/02/24/how-to-hold-kems/

insanitybit 5mo ago
> If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?
- some_furry 5mo ago
  If you encrypt your data twice (taken very literally): c1 = E1(p, k1) c2 = E2(p, k2) If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p. What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken. ss1, ct1 = KEM1(pk1) ss2, ct2 = KEM2(pk2) secret = Combiner(ss1, ss2, [ct1, [ct2]]) This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated. This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations. I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
  - 3form 5mo ago
    It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
    - some_furry 5mo ago
      The thing is: Quantum computers don't break AES-GCM, ChaCha20-Poly1305, or any other modern authenticated cipher. Layering encryption or doing cipher cascades is pointless. The thing a cryptography-relevant quantum computer does is break RSA and elliptic curve cryptography, so that the underlying key (k1 or k2) is recoverable from its corresponding public component. Hybrid KEMs, such as mlkem768x25519 (a.k.a. X-Wing) is a simple abstraction with security proofs that does both classical (X25519 is elliptic curve) and post-quantum (ML-KEM-768 is lattice-based) cryptography and combines them securely into a single key agreement. "Encrypt twice" is bad advice. Even if you get the same approximate security, you're giving up a lot of performance. Encrypt once, but encrypt with a key you can be confident in the secrecy of.
      - saltcured 5mo ago
        Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? The change of jargon from "encryption" to "KEM" doesn't mean anything to most people talking about this post-quantum risk. To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption. Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
        some_furry 5mo ago
        > Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? No, I'm saying that "hybrid KEM" or "chaining two KEMs" is very distinct from "encrypt twice". Confuse the two at your own peril. > To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption. Encryption is reversible. If you have the key, you can decrypt. It's not encryption if you can't decrypt. KEMs are their own class of algorithms. They combine an asymmetric encryption scheme with an all-or-nothing one-way transform (usually a key derivation function built on hash functions). It's the safest way to hold asymmetric encryption in practice (even not considering PQ; RSA-KEM beats RSA-OAEP in implementation safety). Calling KEMs "encryption" is misleading to the point of malpractice. I will push back on conflating the two. > Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. Your only defense-in-depth should be in delivering a strong pseudorandom ephemeral key over an untrusted network, and then using the tried-and-true AEAD constructions that we're already using today. Encrypt once. Do whatever you need to do to get the key exchanged securely. I write a blog that very regularly covers applied cryptography. I deal with newbie confusion all the time. It's very important that we talk about these things correctly on forums like Hacker News comment threads so that the people learning from us won't get more confused. Please don't call KEMs "encryption".

tptacek 5mo ago

No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices. People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.

mswphd 5mo ago
Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU. He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now. In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world. This is ignoring all of his other explicitly embarrassing behavior, for example 1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly. 2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust. 3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.

mswphd 5mo ago

The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places. The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve. So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.