ElligEKE - An extremely simple zero-knowledge password proof
Introduction
This document presents “ElligEKE”. ElligEKE is a PAKE (Password-Authenticated Key Exchange) and a ZKPP (Zero-Knowledge Password Proof).
A PAKE is a protocol which allows two mutually untrusting parties to (conditionally) agree on a shared key, provided they each supply some password as an input, with the success criteria being that both passwords are equal, and to do this in a way that doesn’t leak (to either the other party or an eavesdropper) any information about the password(s). To elaborate, first consider that we already have mechanisms for two parties to agree on a shared key; for example, we could use the Diffie-Hellman key exchange or a key-encapsulation mechanism. A PAKE performs a similar exchange, with the following difference: both parties provide some (possibly low-entropy) password as an input to the exchange, and, after the exchange, both parties will (unbeknownst to either party) end up with the same shared key only if both parties started with the same password.
If the parties intend to (and they usually do) verify that the passwords did indeed match, then the protocol is also considered a ZKPP. What is notable about this procedure is that it is secure even with (extremely) low-entropy passwords—after a ZKPP exchange completes, only a single bit of information is shared: whether or not the the passwords matched.
ElligEKE is a variant of the EKE (Encrypted Key Exchange) protocol, which itself is a (and probably history’s first) PAKE. In the EKE paper, the authors start with a very simple and elegant protocol (EKE), but point out a major problem, which is that “it is not clear how to encode efficiently a [public key] so that it is indistinguishable from a random string“—thus jeopardizing the security of the original EKE protocol—and the rest of the paper is dedicated towards creating variant protocols (RPK, XEG, RDH) to avoid this problem, at the cost of additional complexity.
ElligEKE sidesteps the problems with EKE altogether by using Elligator. Elligator is a way to generate elliptic-curve public keys in a way where they are indistinguishable from uniform random strings. This ability unlocks the elegant idea at the root of EEK. The Elligator paper itself cited this very idea as a potential use case for Elligator, but:
- A PAKE based on Elligator was never defined in the Elligator paper, and
- The original EKE paper also never bothered to elaborate on what this type of protocol might look like, due to the “public-key-distinguishable-from-random” problem, and
- Nearly all other existing PAKE protocols (e.g., SRP, AugPAKE, OPAQUE) also assume public keys will be distinguishable from random, and go to great lengths to work around it.
Thus we define ElligEKE, which, as a result, has the advantage (over other PAKEs) of being extremely simple. Because it is simple, it is easy implement, and, most importantly, easy to cryptanalyze. Unlike other PAKEs, it is strictly composed on top of standard, well-known, cryptographic primitives (Diffie-Hellman, encryption, and authenticated encryption) and does not perform any clever techniques (e.g., most other PAKEs customize/redefine standard public-key derivation operations in order to include various other values in exponents, etc.)
The ElligEKE Protocol
Variables
| $\fbox{$x$}$ | An encrypted box containing $x$ |
| $pw$ | Password (or hash thereof) known by client and server |
| $c_{pk},$ $c_{pk}$ | (client, server) public key |
| $c_{n},$ $s_{n}$ | (client, server) random nonce |
| $k$ | Post-DH shared key |
| $c_n,$ $s_n$ | Post-DH client and server session keys |
| $c_{proof},$ $s_{proof} $ | (client, server) proof of shared key |
Operations
| $DH(pubkey1,pubkey2)$ | Elliptic-Curve Diffie-Hellman |
| $E(key,nonce,plaintext)$ | Encryption |
| $E^{-1}(key,nonce,ciphertext)$ | Decryption |
| $AE(key,nonce,plaintext)$ | Authenticated Encryption |
| $AE^{-1}(key,nonce,ciphertext)$ | Authenticated Decryption |
Algorithm
ElligEKE is a completely symmetric protocol. Despite the usage of the terms “client” and “server” there is in fact no difference in behavior between the two. We will explain the protocol from the client’s perspective, but the understanding is that the server will also perform the same steps.
As a prerequisite, both client and server must both already know some password, and store its cryptographic hash in $pw$. Note that:
- Hashing the password is theoretically optional. The only reason we hash the password is that while a raw password’s length may vary, we need it to be an exact size so it can be used as a key.
- Only a single hash is necessary. This is a zero-knowledge proof protocol, and therefore the password does not necessarily need to be derived from a password-based key derivation function.
The first step of the algorithm is (from the client’s perspective) to generate an elliptic curve key pair ($c_{sk}$, $c_{pk}$) and (maybe) a random nonce ($c_n$). Then, encrypt the public key using the password ($pw$) as the key, and send the encrypted public key $\fbox{$c_{pk}$}$ along with the (optional) nonce to the server. (In this step, a nonce is required for a stream cipher, but not necessarily for a block cipher.)
Next, the client receives the server’s encrypted public key $\fbox{$s_{pk}$}$ (and optionally nonce $s_n$), and decrypt the public key using the password ($pw$) as the key. Now that the client knows the server’s public key, it perform a Diffie-Hellman operation on both public keys ($c_{pk},s_{pk}$) to derive a shared key ($k$).
If both parties were to share the same key, then they would need to coordinate with each other in order to avoid encrypting two messages with the same nonce under the same key. To avoid this, we split $k$ into two keys: the client session key $c_k$ and server session key $s_k$. (To do this, when deriving the Diffie-Hellman shared key, hash it so as to obtain twice as many bytes, then split the resulting bytes into two keys.)
For the client to prove to the server that it knows ($c_k$), it will need to prove that it is able to encrypt some value with it. So, your first message to the server using key $k$ can be to encrypt the value $0$; this will be your “$c_{proof}$”. Send the proof to the server. Likewise, you can verify that the server knows ($k$), by waiting for its proof ($s_{proof}$), and validating its contents.
After you and the server have proven yourselves to each other, you can continue sending messages to each other using the same nonce strategy, but from now on using authentication encryption.
Algorithm (Formal)
$INIT \rightarrow (c_{sk},c_{pk}),(s_{sk},s_{pk})$
| Step | Client | Server |
|---|---|---|
| $0.1$ | Generate $c_{sk}, c_{pk}, c_n$ | Generate $s_{sk}, s_{pk}, s_n$ |
$PAKE : (c_{sk}, c_{pw}),(s_{sk}, s_{pw}) \rightarrow k,k$
| Step | Client | Server |
|---|---|---|
| $1.1$ | $\fbox{$c_{pk}$}$ $= E(pw, c_{n}, c_{pk})$ | $\fbox{$s_{pk}$}$ = $E(pw, s_{n}, s_{pk})$ |
| $1.2$ | $c_{n}, \fbox{$c_{pk}$}$ $\rightarrow$ | $\leftarrow$ $s_{n}, \fbox{$s_{pk}$}$ |
| $1.3$ | $s_{pk} = E^{-1}(pw,s_{n},$ $\fbox{$s_{pk}$}$ $)$ | $c_{pk} = E^{-1}(pw, c_{n}, $ $\fbox{$c_{pk}$}$ $)$ |
| $1.4$ | $\\ (c_k,s_k) = DH(c_{pk}, s_{pk}) \ \ {\tt{if}} \ \ c_{pk}<s_{pk}\\ (s_k,c_k) = DH(c_{pk}, s_{pk}) \ \ {\tt{if}} \ \ s_{pk} < c_{pk} $ | (same as client) |
$ZKPP : (k,c_n,s_n),(k,c_n,s_n) $ $\rightarrow$ $ (true|false),(true|false)$
| Step | Client | Server |
|---|---|---|
| $2.1$ | $ \fbox{$c_{proof}$} $ = $ E(c_k, 1, 0)$ | $ \fbox{$s_{proof}$} $ = $ E(s_k, 1, 0)$ |
| $2.2$ | $ \fbox{$c_{proof}$} \rightarrow $ | $\leftarrow \fbox{$s_{proof}$}$ |
| $2.3$ | $✓ s_{proof}$ | $✓ c_{proof}$ |
Messages:
| $3.1$ | $ AE(c_k, 2, $ …$) \rightarrow $ | $ \leftarrow AE(s_k, 2, $ …$) $ |
| $4.1$ | $ AE(c_k, 3, $ …$) \rightarrow $ | $ \leftarrow AE(s_k, 3, $ …$) $ |
| $5.1$ | $ AE(c_k, 4, $ …$) \rightarrow $ | $ \leftarrow AE(s_k, 4, $ …$) $ |
| $…$ | $…$ | $…$ |
A note on performance
It has been shown that it should be possible to create a keypair and perform a Diffie-Hellman using Elligator, using certain elliptic curves, in roughly 80,000 Intel CPU cycles. Because this represents >99% of the work required for ElligEKE, this means it is possible to perform on the order of 50,000 password proofs per second per CPU (on a 4-core Intel CPU).
References
[1] Wikipedia: Password-authenticated key agreement
[2] Wikipedia: Zero-knowledge password proof
[3] Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks
[4] Elligator: Elliptic-curve points indistinguishable from uniform random strings
[6] Secure Remote Password - A Secure Key Exchange Protocol
[7] AugPAKE: Efficient Augmented Password-Only Authentication and Key Exchange for IKEv2
[8] OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks