Forward secrecy with hash ratchets

Alice wants to send messages to Bob. These messages are sensitive, so Alice and Bob take precautions. When they meet, they decide on a shared secret S with which to encrypt the messages. Each sent message is encrypted with the shared secret, and each received message is decrypted with the shared secret.

Eve is interested in their conversation, but hasn’t been able to read anything, because she doesn’t have the shared secret. However, Eve is able to intercept the encrypted messages, and she has been storing them up, hoping to one day decrypt them. Then one day, Eve gets lucky: she discovers a vulnerability in Bob’s phone, and she manages to steal the shared secret! With this, Eve can now decrypt the entire message history!

Is Alice and Bob’s crypto-system “secure”? A traditional perspective assumes Alice and Bob have secure machines, and attackers only control the network. In this traditional perspective, the crypto-system described is secure, and Eve’s decryption of the message history was only possible because of faulty machines. But, in the real world, Alice and Bob’s machines do have bugs; they do have vulnerabilities; they do get stolen. We should design crypto-systems which minimize the damage that an attacker can do with a compromised machine.

Specifically, can we design the crypto-system so that, even after Eve compromises Bob’s phone, she cannot decrypt her cache of the previous messages? The answer is yes, and such a system is said to have “forward secrecy”.

Consider an old plaintext message M, which was encrypted with secret S yielding ciphertext C. To implement forward secrecy, we must ensure that Bob’s phone cannot recover M. The first implication is that Bob’s phone must not store the plaintext messages. Apps like WhatsApp claim to provide forward secrecy, but they trivially fail at the first hurdle, because the apps store a plaintext message log!

Let’s assume, then, that Bob’s phone discards the message shortly after decryption. The phone shows Bob the plaintext, then destroys the message. Destroying M is better, but not enough, because Bob’s phone still has the secret S, which can be used to recover M from Eve’s stashed ciphertext C. So Bob’s phone must also destroy the secret S!

By destroying the secret S after transmitting a message, Alice and Bob have a system which provides forward secrecy. The price they have paid is that they can now only send one message! Their crypto-system wants to use the secret S to encrypt the next message, but it can’t do so after destroying S.

To extend their conversation, Alice and Bob need to agree on more secrets. So they decide that, when they meet, instead of agreeing on one shared secret S, they will agree on a long series of shared secrets S1, S2, ..., Sn. They will transfer the first message M1 with S1 to produce ciphertext C1. They will then destroy M1 and S1, so that Eve can never discover M1, even if she compromises their machines. For message M2, they will use S2, and so on, sending up to n messages before they need to meet again.

In effect, S1 through Sn are a “one-time pad”. They are a big shared key, at least as large as the plaintext, only used once. By destroying the pad as they use it, Alice and Bob guarantee forward secrecy. But the one-time pad has a couple of problems: it’s big, and it has finite length.

Both of these problems with the one-time pad can be fixed by replacing randomness with pseudo-randomness. Alice and Bob will use the shared secret S as the seed to a pseudo-random number generator (PRNG), from which they can derive the infinite stream of pseudo-random keys S1, S2, ..., etc.

A PRNG has state, and a stepper function which yields a random number along with a new state. There are many ways to implement this. For example, the state could be the seed plus a counter, and the stepper function could increment the counter, and yield a random number by hashing the seed with the counter. Would this system provide forward secrecy? No! This system never destroys the initial secret seed, meaning the entire key stream is recoverable by Eve. The previous states of the PRNG are recoverable by decrementing the counter.

For forward secrecy, we must ensure that, when stepping the PRNG, the previous state becomes unrecoverable. In other words, the stepper function must be a one-way function. The most common one-way functions are cryptographic hash functions like SHA256. This is how WhatsApp works!

Each time a new Message Key is needed by a message sender, it is calculated as:

Message Key = HMAC-SHA256(Chain Key, 0x01).

The Chain Key is then updated as Chain Key = HMAC-SHA256(Chain Key, 0x02).

This causes the Chain Key to “ratchet” forward, and also means that a stored Message Key can’t be used to derive current or past values of the Chain Key.

The WhatsApp whitepaper talks of “message keys” and “chain keys”, but the structure is exactly that of a pseudo-random number generator. The “chain key” is the PRNG state. The “message key” is the random number output, to be used as a one-time key.

HMAC is usually a way to sign data: signature = HMAC-SHA256(secret, plaintext). In this terminology, the Message Key is the signature resulting from signing the message 0x01 with the secret Chain Key. But this is misleading. WhatsApp is using the HMAC-SHA256 function for a different purpose: a hash function with two inputs. I believe that instead of HMAC-SHA256(Chain Key, 0x01) they could have used something like SHA256(Chain Key + 0x01).

Tagged #programming, #crypto.

👋 I'm Jim, a full-stack product engineer. Want to build an amazing product and a profitable business? Read more about me or Get in touch!