add content/posts/2025-03-31-ml-kem-vs-dh-and-ecdh.md

1 files changed, 162 insertions, 0 deletions

diff --git a/content/posts/2025-03-31-ml-kem-vs-dh-and-ecdh.md b/content/posts/2025-03-31-ml-kem-vs-dh-and-ecdh.md
new file mode 100644
index 0000000..b37f821
--- /dev/null
+++ b/content/posts/2025-03-31-ml-kem-vs-dh-and-ecdh.md
@@ -0,0 +1,162 @@
+---
+slug: ml-kem-vs-dh-and-ecdh
+title: "ML-KEM vs. DH and ECDH"
+date: "2025-03-31T08:02:21-04:00"
+---
+
+A couple of months ago I [wrote an expanation][answer] of [ML-KEM][] in
+the discussion thread of an [Ars Technica article][].  Folks seemed to
+like my explanation and the Ars staff marked it as a "Staff Pick".
+
+Below is the explanation that I wrote with some minor corrections...
+
+----
+
+> Close friend of mine from college works as a cryptographer for some government agency (he jokes he can't tell me which one it actually is...he went straight there from his Stanford PhD) and he tried to explain ML-KEM to me a couple weeks ago in "simple" language and my brain gave up after about 2 minutes. 
+
+This might help: [Kyber - How does it work?][]
+
+One thing that is different about [ML-KEM][] compared to [finite-field Diffie-Hellman (DH)][dh] and [Elliptic-Curve Diffie-Hellman (ECDH)][ecdh] is that the former is a [Key Encapsulation Mechanism (KEM)][kem] and the latter are [key-agreement protocols][key agreement].
+
+In [DH][] and [ECDH][]:
+
+1. Alice generates a keypair which consists of a public key and a private key.
+2. Alice keeps the private key to herself and sends the public key to Bob.
+3. Bob generates a keypair which consists of a public key and a private key.
+4. Bob keeps the private key to himself and sends the public key to Alice.
+5. Alice combines her private key from step #1 with Bob's public key from step #4 and produces a shared value.
+6. Bob combines his private key from step #3 with Alice's public key from step #2 and produces the same shared value that Alice produced in step #5.
+
+In [ML-KEM][] things work a bit differently:
+
+1. The first party (Alice) generates an keypair which consists of an encapsulation key (analagous to a public key in [DH][]) and a decapsulation key (analagous to a private key in [DH][]).
+2. Alice sends an encapsulation key to the second party (Bob).
+3. Bob generates a random value, which is hashed with a hash of Alice's encapsulation key from step #2 to generate a shared value (32 bytes in [ML-KEM][]).
+4. Bob uses Alice's encapsulation key from step #2 to encapsulate the random value, producing a ciphertext.
+5. Bob sends the ciphertext from step #4 back to Alice.
+6. Alice uses the decapsulation key from step #1 to decapsulate the random value generated by Bob in step #3 from the ciphertext sent by Bob in step #5.
+7. Alice hashes the random value from step #6 with the hash of the encapsulation key to generate the shared value.
+
+So in [DH][] and [ECDH][], both parties contribute equally to the shared value. In [ML-KEM][], one party (Bob) generates a random value which is hashed with a hash of the other party's (Alice) encapsulation key to produce the shared value.
+
+Another difference between [DH][]/[ECDH][] and [ML-KEM][] is this: the shared value produced by [DH][] and [ECDH][] cannot be safely used as the secret key for a symmetric cipher (e.g. [AES][]) because the shared value is biased (some values are much more likely than others). To safely derive a secret key (or keys) for use with a symmetric cipher, the shared value produced by [DH][] and [ECDH][] needs to be passed through a [key derivation function (KDF)][kdf] like [HKDF][].
+
+The shared value derived in [ML-KEM][] is uniformly random and can be used directly as the key for a symmetric cipher ([FIPS 203][], section 3.1). In practice I expect the [ML-KEM][] shared value to be passed to a [KDF][] anyway, because many protocols (for example, [TLS][]) need to derive several keys in order to establish a secure channel.
+
+[DH][], [ECDH][], and [ML-KEM][] all rely on "hard" problems based on [trapdoor functions][trapdoor function].
+
+"Hard" in this context means "believed to be computationally infeasible to solve without an implausible amount of computational resources or time".
+
+A [trapdoor function][] is a function that is easy to compute in one direction but hard to compute in the other direction without some additional information. For example, it is easy to calculate `61 * 71` and hard to calculate the integer factors of `4331`. However, if I tell you that one of the factors of `4331` is `61`, then it is easy for you to calculate the other factor: `4331 / 61 = 71`. This is the [integer factorization][] problem, and it's the basis for [RSA][].
+
+The hard problem that [Finite-Field Diffie-Hellman (FFDH)][dh] key exchange is based on is the [discrete logarithm problem][], which is this:
+
+> Given b = g{{<sup s>}} mod p, it is hard to calculate s, where:
+>
+> - `s` is a large randomly chosen positive integer that is secret
+> - `g` is a fixed positive integer that is publicly known and carefully chosen by cryptographers
+> - `p` is a fixed large prime number that is publicly known and carefully chosen by cryptographers
+
+The hard problem that [Elliptic-Curve Diffie-Hellman (ECDH) key exchange][ecdh] is based on is known as the [elliptic curve discrete logarithm problem (ECDLP)][ecdlp], which is this:
+
+> Given b = sG, it is hard to calculate s, where:
+>
+> - `s` is a large randomly chosen positive integer that is secret, and
+> - `G` is a fixed, publicly known point on an elliptic curve over a finite field. The point, elliptic curve, and field are all carefully chosen by cryptographers.
+
+The hard problem that [ML-KEM][] is based on is the Module Learning With Errors (MLWE) problem, which is derived from the [Learning With Errors (LWE)][lwe] problem. A simplified version of the [LWE][] problem is this:
+
+> Given `t = As + e`, it is hard to calculate s, where:
+>
+> - `t` is a public vector with integer elements
+> - `A` is a public square matrix with elements that are random integer values
+> - `s` is a secret vector with elements that are small integer values (the secret)
+> - `e` is a secret vector with elements that are small integer values (the error)
+
+Note that if you remove `e` from the equation above, then solving for `s` becomes very easy:
+
+1. Calculate `A{{<sup -1>}}` using [Gaussian elimination][].
+2. Multiply by `A{{<sup -1>}}` from the left: `A{{<sup -1>}}t = A{{<sup -1>}}As`
+3. Solution: `s = A{{<sup -1>}}t`
+
+The important bit here is that the error vector is critical to making the problem hard.
+
+In the Module Learning With Errors (MLWE) problem that is used by [ML-KEM][], the integers from the simplified [LWE][] explanation above are replaced by polynomials with 256 coefficients.
+
+(This is explained cryptically in [FIPS 203][], section 3.2)
+
+Unfortunately the large polynomials make it difficult to visualize [ML-KEM][]. There is a simplified implementation of Kyber called "Baby Kyber" in the [Kyber - How does it work?][] article linked above that is easier to understand.
+
+One problem with using 256-coefficient polynomials is multiplication. Adding polynomials is done coefficient-wise, so adding two polynomials with 256 integer coefficients requires 256 integer additions.
+
+Polynomial multiplication, on the other hand, requires multiplying every coefficient by every other coefficient. This means that multiplying two polynomials with 256 integer coefficients requires `256 * 256 = 65536` integer multiplications.
+
+To work around this, [ML-KEM][] uses a trick called the [Number-Theoretic Transform][ntt] ([NTT][], [FIPS 203][], section 4.3). This allows polynomial multiplication to be done (almost) coefficient-wise and drastically reduces the number of integer multiplications needed.
+
+Using polynomials instead of large, multi-word integers like [DH][] and [ECDH][] might seem confusing at first, but it actually simplifies a lot of the implementation because it enables [SIMD][] optimizations and you don't have to deal with carry propagation.
+
+Another neat trick used by [ML-KEM][] is compressing the `A` matrix in the encapsulation key by including a 32-byte seed (rho) instead of the actual polynomial coefficients. This seed value is expanded with [SHAKE128][] to pseudorandomly generate the coefficients for the polynomial elements of the A matrix ([FIPS 203][], `SampleNTT()` in section 4.2.2 and section 5.1).
+
+There are a lot of other details but hopefully this gives you enough to start to get your head around [ML-KEM][].
+
+If you want to see some source code, [here][fips203ipd-github] is a self-contained, single-file, dependency-free [C11][] implementation of the [FIPS 203 initial public draft (IPD)][fips203ipd] that I wrote last year. It includes test vectors, [SIMD][] acceleration, and the necessary bits of [FIPS 202][] (SHA3-256, SHA3-512, SHAKE128, and SHAKE256), but it has not been updated to reflect the changes in the final version of [FIPS 203][]. I mainly wrote it for fun, to learn, and to provide public comments to [NIST][] during the standardization process.
+ 
+
+[answer]: https://arstechnica.com/security/2024/09/microsoft-adds-quantum-resistant-algorithms-to-its-core-crypto-library/?comments=1&comments-page=1#comments
+  "My comment explanating ML-KEM."
+[ars technica article]: https://arstechnica.com/security/2024/09/microsoft-adds-quantum-resistant-algorithms-to-its-core-crypto-library/?comments=1&comments-page=1#comments
+  "As quantum computing threats loom, Microsoft updates its core crypto library (arstechica.com)"
+[ml-kem]: https://csrc.nist.gov/pubs/fips/203/final
+  "Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM)"
+[fips 203]: https://csrc.nist.gov/pubs/fips/203/final
+  "Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM)"
+[Kyber - How does it work?]: https://cryptopedia.dev/posts/kyber/
+  "Kyber - How does it work?"
+[dh]: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
+  "Diffie-Hellman Key Exchange (DH)"
+[ecdh]: https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
+  "Elliptic-Curve Diffie-Hellman (ECDH)"
+[kem]: https://en.wikipedia.org/wiki/Key_encapsulation_mechanism
+  "Key encapsulation mechanism (KEM)"
+[key agreement]: https://en.wikipedia.org/wiki/Key-agreement_protocol
+  "Key-agreement protocol (Wikipedia)"
+[aes]: https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
+  "Advanced Encryption Standard (AES)"
+[kdf]: https://en.wikipedia.org/wiki/Key_derivation_function
+  "Key derivation function (KDF)"
+[hkdf]: https://en.wikipedia.org/wiki/HKDF
+  "HMAC-based Key Derivation Function (HKDF)"
+[tls]: https://en.wikipedia.org/wiki/Transport_Layer_Security
+  "Transport Layer Security (TLS)"
+[trapdoor function]: https://en.wikipedia.org/wiki/Trapdoor_function
+  "Trapdoor function (Wikipedia)"
+[integer factorization]: https://en.wikipedia.org/wiki/Integer_factorization
+  "Integer factorization (Wikipedia)"
+[rsa]: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
+  "RSA cryptosystem (Wikipedia)"
+[discrete logarithm problem]: https://en.wikipedia.org/wiki/Discrete_logarithm#Cryptography
+  "Discrete logarithm problem (DLP)"
+[ecdlp]: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Application_to_cryptography
+  "Elliptic-curve Discrete Logarithm Problem (ECDLP, Wikipedia)"
+[lwe]: https://en.wikipedia.org/wiki/Learning_with_errors
+  "Learning With Errors (LWE, Wikipedia)"
+[Gaussian elimination]: https://en.wikipedia.org/wiki/Gaussian_elimination
+  "Gaussian elimination (Wikipedia)"
+[ntt]: https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring#Number-theoretic_transform
+  "Number-Theoretic Transform (NTT)"
+[simd]: https://en.wikipedia.org/wiki/Single_instruction,_multiple_data
+  "Single instruction, multiple data (SIMD)"
+[shake128]: https://en.wikipedia.org/wiki/SHA-3
+  "SHAKE128: SHA-3 extendable-output function"
+[sha3]: https://en.wikipedia.org/wiki/SHA-3
+  "Secure Hash Algorithm 3 (SHA-3)"
+[c11]: https://en.wikipedia.org/wiki/C11_(C_standard_revision)
+  "ISO/IEC 9899:2011"
+[fips203ipd]: https://csrc.nist.gov/pubs/fips/203/ipd
+  "FIPS 203 (Initial Public Draft): Module-Lattice-Based Key-Encapsulation Mechanism Standard"
+[fips 202]: https://csrc.nist.gov/pubs/fips/202/final
+  "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"
+[fips203ipd-github]: https://github.com/pablotron/fips203ipd
+  "My embeddable, dependency-free C11 implementation of ML-KEM from the FIPS 203 initial public draft (IPD) with scalar, AVX-512, and Neon backends."
+[nist]: https://www.nist.gov/
+  "National Institute of Standards and Technology"