4 ms·

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

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 4mo 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 4mo 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 4mo 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 4mo 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".
    - mswphd 4mo ago
- mswphd 4mo ago
  both encrypting in parallel and encrypting in the second way you mentioned are bad ideas, and are far from being what is seriously being discussed when people talk about hybrid KEMs. Encrypting in parallel is explicitly IND-CPA insecure if one of the ciphers is broken. Your construction is IND-CPA secure, but quite inefficient, and would not fit into modern protocols. If this was a typical cryptographic topic, this might be fine, and is how I would likely phrase things for an undergraduate cryptography course. Unfortunately, this is a topic that a certain cryptographer with a decently large public following has been spreading conspiracy theories (and slandering other cryptographers about) for a number of years now. So, discussions on this topic often come from a place where the audience is misinformed, and more care is required in grounding the discussing in what is actually being discussed/considered.
insanitybit 4mo ago
The idea would be: key = get_key() classic_key = derive_key(key, "domain-classic") qc_key = derive_key(key, "domain-qc") ciphertext_a = classic_encrypt(plaintext, classic_key) ciphertext_b = qc_encrypt(ciphertext_a, qc_key) I think this is different from what you wrote but I can't really tell. FWIW I am not advocating for "encrypt twice" at all, I'm just trying to understand.
- some_furry 4mo ago
  A better idea is to do this: # You kind of have to define this since most libraries don't have it def classic_kem(pk): [eph_sk, eph_pk] = classic_keygen() d = classic_shared_secret(eph_sk, pk) return hash(d + eph_pk + pk), eph_pk # Two pieces ... [ss1, ct1] = classic_kem(pk1) [ss2, ct2] = postquantum_kem(pk2) # ... combine into one: # note: for some KEMs, ct1 and/or ct2 can safely be omitted shared_secret = hash(ss1 + ss2 + ct1 + ct2) ciphertext = symmetric_encrypt(plaintext, shared_secret, context) send_to_other_party( ct1, ct2, ciphertext ) This sounds more complex, but I'm just filling in the details implied by your pseudocode and making it at least 2x as fast. On the opposite side, their code looks like this: # I'm ignoring implicit vs explicit rejection for simplicity def classic_kem_decaps(ct, sk, pk): d = classic_shared_secret(ct, sk) return hash(d + ct + pk) ss1 = classic_kem_decaps(ct1, sk1, pk1) ss2 = postquantum_kem_decaps(ct2, sk2, pk2) shared_secret = hash(ss1, ss2, ct1, ct2) # raises an exception on decrypt failure (e.g., invalid auth tag) plaintext = symmetric_decrypt(ciphertext, shared_secret, context) If you mean "doing two different KEMs and then securely combining them", then just say that. "Hybrid KEM" is short enough and distinct from other verbage. "Encrypt" means something specific, not just the vague use of cryptography.
- dwaite 4mo ago
  Trying to bridge this a bit since I'm closer to a layperson in this area. Symmetric encryption does not need a quantum computer alternative, nor do we need a post quantum hashing algorithm. We may need larger keys and larger outputs from the existing algorithms, but that really depends on the level of paranoia. It is the asymmetric keys that need post quantum replacement. So I'm guessing the change to your proposed pseudocode you would have two derivation algorithms based on two input asymmetric keys - one post quantum and one classical. You would get from these two separate symmetric keys. You would then layer encryption using each of them, encrypting the cipher text output from the first with the second. You can however just combine the two derived symmetric keys together to create a single symmetric key, and encrypt once. That is what hybrid algorithms propose.
tardedmeme 4mo ago
Why would you take the stupidest possible interpretation of that person's comment?

3form 4mo 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 4mo 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 4mo 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 4mo 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".
  - mswphd 4mo ago
mswphd 4mo ago
both encrypting in parallel and encrypting in the second way you mentioned are bad ideas, and are far from being what is seriously being discussed when people talk about hybrid KEMs. Encrypting in parallel is explicitly IND-CPA insecure if one of the ciphers is broken. Your construction is IND-CPA secure, but quite inefficient, and would not fit into modern protocols. If this was a typical cryptographic topic, this might be fine, and is how I would likely phrase things for an undergraduate cryptography course. Unfortunately, this is a topic that a certain cryptographer with a decently large public following has been spreading conspiracy theories (and slandering other cryptographers about) for a number of years now. So, discussions on this topic often come from a place where the audience is misinformed, and more care is required in grounding the discussing in what is actually being discussed/considered.

insanitybit 4mo ago

The idea would be: key = get_key() classic_key = derive_key(key, "domain-classic") qc_key = derive_key(key, "domain-qc") ciphertext_a = classic_encrypt(plaintext, classic_key) ciphertext_b = qc_encrypt(ciphertext_a, qc_key) I think this is different from what you wrote but I can't really tell. FWIW I am not advocating for "encrypt twice" at all, I'm just trying to understand.

some_furry 4mo ago
A better idea is to do this: # You kind of have to define this since most libraries don't have it def classic_kem(pk): [eph_sk, eph_pk] = classic_keygen() d = classic_shared_secret(eph_sk, pk) return hash(d + eph_pk + pk), eph_pk # Two pieces ... [ss1, ct1] = classic_kem(pk1) [ss2, ct2] = postquantum_kem(pk2) # ... combine into one: # note: for some KEMs, ct1 and/or ct2 can safely be omitted shared_secret = hash(ss1 + ss2 + ct1 + ct2) ciphertext = symmetric_encrypt(plaintext, shared_secret, context) send_to_other_party( ct1, ct2, ciphertext ) This sounds more complex, but I'm just filling in the details implied by your pseudocode and making it at least 2x as fast. On the opposite side, their code looks like this: # I'm ignoring implicit vs explicit rejection for simplicity def classic_kem_decaps(ct, sk, pk): d = classic_shared_secret(ct, sk) return hash(d + ct + pk) ss1 = classic_kem_decaps(ct1, sk1, pk1) ss2 = postquantum_kem_decaps(ct2, sk2, pk2) shared_secret = hash(ss1, ss2, ct1, ct2) # raises an exception on decrypt failure (e.g., invalid auth tag) plaintext = symmetric_decrypt(ciphertext, shared_secret, context) If you mean "doing two different KEMs and then securely combining them", then just say that. "Hybrid KEM" is short enough and distinct from other verbage. "Encrypt" means something specific, not just the vague use of cryptography.
dwaite 4mo ago
Trying to bridge this a bit since I'm closer to a layperson in this area. Symmetric encryption does not need a quantum computer alternative, nor do we need a post quantum hashing algorithm. We may need larger keys and larger outputs from the existing algorithms, but that really depends on the level of paranoia. It is the asymmetric keys that need post quantum replacement. So I'm guessing the change to your proposed pseudocode you would have two derivation algorithms based on two input asymmetric keys - one post quantum and one classical. You would get from these two separate symmetric keys. You would then layer encryption using each of them, encrypting the cipher text output from the first with the second. You can however just combine the two derived symmetric keys together to create a single symmetric key, and encrypt once. That is what hybrid algorithms propose.

tardedmeme 4mo ago

Why would you take the stupidest possible interpretation of that person's comment?