Suppose you need to encrypt data between two peer-to-peer devices over an untrusted medium (i.e. the Internet), and you have an authenticated low-bandwidth channel that can be used to send and authenticate a few bytes (less than 100), but that channel isn’t itself encrypted (otherwise it’d be a chicken-and-egg problem).
Aside: If it helps your mental image, you can pretend that the authenticated channel is a blockchain, if you want. You can squeeze a few bytes in there, and the data structure is verifiable, but everything you transmit is public. But the actual channel implementation isn’t important here; this is a thought experiment.
This was an unsolved problem in mathematics and cryptography until the 1970’s, when Whitfeld Diffie, Martin Hellman, and Ralph Merkle published the original Diffie-Hellman protocol and invented asymmetric (a.k.a. public-key) cryptography.
Modern cryptography uses a variant of the initial Diffie-Hellman protocol, defined over a mathematical structure called an Elliptic Curve. Thus, it is called Elliptic Curve Diffie Hellman (ECDH).
Note: I’m intentionally breaking from the mathematical orthodoxy in this blog post in the hopes that it’s more accessible to everyone outside the ivory tower. As a result, my definitions may lack precision, but I’m saving you from jargon.
Elliptic Curve Diffie-Hellman
Without going into the nuts and bolts of ECDH (a subject of a future blog post!), this is basically what’s happening in layman’s (n.b. non-mathematician’s) terms:
- You’ve got an elliptic curve, which satisfies some equation. There are many different curve shapes. One example is
, where A and B are integer constants. (This example is called a Montgomery curve.)
- You’ve got a field parameter,
. This is usually a prime number. (If it isn’t, and you aren’t a cryptographer, you probably want to run away from it.)
- You’ve got a generator,
(which is some specific point on the curve), which transforms the whole shebang into a thing called a “group” which has a thing called an “order” (which in turn is an integer of value
). The fact that this thing is a “group” at all is what makes Diffie-Hellman possible.
You don’t need to worry about what these things even are, because I’m not delving into the underlying mathematics (nuts and bolts) at all. But if I omit them, the pedants complain, so for the sake of completeness: Here you go.Take a mathematics course that covers Galois theory if you want the inside scoop on what the hell those things are. But for now, if you’re lost, just know that you have some special parameters/properties that have specific names and don’t worry about what they mean.
These parameters are meant to be public, and preferably hard-coded. When they’re not, you get CVE-2020-0601.
Each participant (simplest case: there are only two) will need two keys to agree on a shared secret: Their secret key and its corresponding public key.
To calculate a secret key (
To calculate a public key (
This sounds trivial and slow, but Point Addition in an Elliptic Curve is a peculiar operation, and the process is a form of multiplication. Strictly speaking, this is 
I will cover this in detail in a future blog post. For now, just know that you’re multiplying a number (“scalar”) by a point, and that the underlying mechanics of
We can delve into the complexity later, just keep in mind you’re calculating 
It bears emphasizing: Each participant does this.
The orthodox characters for describing cryptographic protocols are Alice and Bob. Alice wants to talk to Bob, Bob wants to talk to Alice, and they want no one else to successfully interfere in their communication.
Alice has 
Bob has 
If they perform one calculation, they can derive a shared secret while only sharing their public keys over the authenticated channel: Multiply their secret key by the other party’s public key.
Alice performs 
Bob performs 
Since multiplication is commutative, they both arrive at the same shared value, despite only transmitting public keys. Someone snooping on the authenticated channel cannot, with current technology, recover the shared secret or either party’s secret key.
With some caveats, of course:
Which Public Key Do I AKE?
We handwaved this away earlier, but an authenticated channel is critically necessary to transmit public keys. Otherwise, an active attacker can just substitute public keys and sit in the middle, with neither party realizing they’re talking to a middleman.
This turns out to be a bit tricky, but not intractable.
TLS (the S in HTTPS) uses long-term digital signature algorithms and chains of digital signatures from a short list of trusted Root Certificate Authorities to authenticate the identity of the server you’re talking to, and then that server’s digital signature public key (signed by an intermediary Certificate Authority) is used to sign ECDH public keys.
I briefly mentioned this in the post about Authenticated Key Exchanges.
Your Curve is Invalid
This is less of a problem with newer elliptic curves, but for a very long time, public keys were transmitted as a pair of 
Earlier, we mentioned that both parties have to agree on some curve parameters. But in protocols where you send arbitrary points, an attacker could send a point 
The standard mitigation is to solve the elliptic curve equation and verify that the coordinates of the point satisfy the chosen elliptic curve parameters.
Modern protocols only send a single coordinate, and possibly a single bit to signify whether the other coordinate is positive or negative (either 
This is called point compression and used to be patented (until 2018). Since the patent has expired, protocols should investigate adopting point compression if they can’t just switch to secure curves.
Optimus Anti-Primes
Since multiplication is commutative, it’s possible that two unrelated pairs of participants could perform an ECDH step and agree on the same shared secret.
This is true for the same reason that 
For this reason, it’s generally unwise to use raw ECDH outputs as encryption keys. Instead, you want to use a cryptographic hash function over the ECDH output and each participants’ public keys to guarantee your symmetric session key is distinct from other pairs.
Whose Time Is It Anyway?
In addition to what I’ve described above, all of the algorithms involved need to perform in constant-time. Any failure to do so will result in your secret key leaking to attackers through network traffic timing (and other side-channels).
I’ll explore the engineering that goes into constant-time implementations in a future blog post.
My hope in writing this page is that anyone without a mathematics background can walk away with a basic intuition for how ECDH works and how dangerous cryptography is when left to the hands of amateurs.
If you find yourself faced with a scenario like we discussed here, you want to use a well-studied Authenticated Key Exchange instead of rolling your own.
If you have to roll your own, try to wrap or take inspiration from libsodium.
https://soatok.blog/2020/04/21/elliptic-curve-diffie-hellman-for-humans-and-furries/
Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).What’s an AKE?
At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.
- An authentication mechanism, such as a MAC or a digital signature.
- Key encapsulation, usually through some sort of Diffie-Hellman.
A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.
I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)
AKEs get much more complicated, the more sophisticated your threat model becomes.
For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.
The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.
Password AKEs
Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.
Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).
Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.
I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.125 lines of code! Really happy with it and it was a lot of fun.
— Filippo Valsorda (@FiloSottile) March 29, 2020
Why So Complicated?
At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.But how you combine these components together can vary wildly!
Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.
The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.
(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)
https://soatok.blog/2020/04/21/authenticated-key-exchanges/
#ake #authenticatedKeyExchange #cryptography #ECDH