Ratcheting Trees and Building A Secure Messaging Platform
Ratcheting Trees and Building A Secure Messaging Platform
Ratchets only go forward, and never back.
We live in a flawed world of cybersecurity, and we often do not build systems that integrate all the most important features for privacy and trust. That, though, is changing, and when, in 2016, representatives from Cisco, Mozilla and Wire Swiss GmbH met at a meeting at IETF 96 in Berlin. The focus of the meeting was to use pairing-based cryptography to integrate with end-to-end encryption and group communications.
While many existing methods struggled with scaling, a new paper then appeared in 2017 that introduced the concept of Asynchronous Ratcheting Trees [here][1]:
This method has since developed into the TreeKEM approach.
Double Ratchets
The Asynchronous Ratcheting Trees paper outlined a way to create efficient encryption for secure group communications. Other ratcheting methods do exist, such as with the Double Ratchet method, and which was Trevor Perrin and Moxie Marlinspike, and is used in Open Whisper Systems Signal package.
Within Signal we see the implementation of a double ratchet system which is able to generate a new encryption key for every message, and where a breach of any of the keys does not promise the previously used ones.
An important concept in defending against a breach of the trust infrastructure is to implement key exchange methods (forward secrecy — FS). With this a comprise of the long-term keys will not compromise any previous session keys. For example, if we send the public key of the server to the client, and then the client sends back a session key for the connection which is encrypted with the public key of the server, then the server will then decrypt this and determine the session. A leakage of the public key of the server would cause all the sessions which used this specific public key to be compromised. FS thus aims to overcome this by making sure that all the session keys could not be compromised, even though the long-term key was compromised. The problem with using the RSA method to pass keys is that a breach of the long keys would breach the keys previously used for secure communications.
Another important concept is where is key is ephemeral. With some key exchange methods, the same key will be generated if the same parameters are used on either side. This can cause problems as an intruder could guess the key, or even where the key was static and never changed. With ephemeral methods a different key is used for each connection, and, again, the leakage of any long-term would not cause all the associated session keys to be breached. The problem with the core Diffie-Hellman method is that the keys are not ephemeral, so we should avoid it in generating keys.
Signal, though, builds forward secrecy into their systems with a double ratchet method, and where each key will not lead to a breach of the previous ones. The double ratchet concept was created by Trevor Perrin and Moxie Marlinspike. In hashing, this is implemented by taking a secret (“A”), and then adding a value of zero to it and then hashing this. The next hash is then our secret with a one added to it, and so on. A breach of one of the hashed values will not reveal the original secret, and it will not be possible to guess the next key.
Within the double ratchet method, we have an ongoing renewal system and where the session keys are only ever short-lived. For this it uses the Elliptic Curve Diffie-Hellman (ECDH) key exchange method and a hashing method for deriving the keys — this gives it a “double” ratchet.
The two parties exchange encrypted messages based on a shared secret key. They create a new set of keys for every Double Ratchet message. In this way, earlier keys cannot be calculated from the ones that follow. They also send Diffie-Hellman public values with their messages, and the results of the Diffie-Hellman calculations are then mixed together into the derived keys. The protocol is useful for making sure that a hack on one set of keys does not lead to a hack on the rest of the keys. In the following, we will create two names (a and b), and then a will encrypt two messages for b, and b will encrypt one message for a [here]:
Name 1: Bob
Name 2: Alice
Bob keys are:
Identity key (Public key): tkUbaj1VwEIwi0kYRlWbl+0Don8WSgKOfbvij6+RT3c=
->Identity key (Private key): hIHdPPYfiF5eEoqXhAIOq1H5qy2VIJToadn1azjk96Q=
Ratchet key (Public key): 7P3yOKPcAX5rVnQkQCmmGfQdo0mi4GL33Yy7DpFMbU0=
-> Ratchet key (Private key): QYHS9FrJQ59VRDVqdwsDDVEbaaPp3myA+vUl3MTdC2Y=
Handshake Public key: a/xifzSbU5wSwF8CFh+xP2ybY7jG/gKoY7dW0DTOHhA=
->Handshake Private key: lSvv3TRFq7xuHxeTjQDqXQc2+UOALDDNJmRXnoDCUBA=
Encrypted message1 a->b: 2cuNbhbPkpcIck3j+9m76bUIr4X2cJdZSOARpGTzKPV3cs1NUrytT+CiNkgXVtJ2KEOzChxOeqLYoBjP11WW/UsSnkhFUkFH2So2iEXutBDHzlYExvQ9MCVkRkH6FaCnvpyPFvW5B6R+YUIok5CuZr0G9hI1Zqgcb0CRnZh0Nm4otP3f3A==
Encrypted message2 a->b: efj2axgAmcBuyjkDzKARlaNzu5MzWqqqd0T9OZH/hW5Oy5JCQH1PN3/fYHu3lwU3N1gthhnGzHtJhlmq06pzXRcTJrhN5xlvsxAl+1K6t08QnD8Ev8myq1Ou719YySagwYRPBvZVo36GmFvN+qM05//weZtTFeL1fR2FZ1FMyjRR2+WiYjFzuE1AOw==
Encrypted message3 b->a: H1gex6vZi0KTPywWK9XzVKmGiP2515XgYrM1Gx+kwq6JY8cQSLIKSHOjexqJhOR8MoGQs9IVX3aKbZkPRcKknsczl/jAdTav9ooFUe5c0XmJFWQEqwRkPgdpxFdbNmbMm7CwBne/6pyb7OfHEmzLUY+MYNLpF3dDwN6SOJFQTjzYe5eVaflBTrJn55TD
b decrypt: The quick
b decrypt: brown fox jumps
a decrypt: over the lazy dogA mechanical ratchet only moves forward for one step at a time. In cryptography, a ratchet method allows for future states to be calculated but only if you know an original seed value. It is not possible to calculate previous states from the current state. Typically this is done with a one-way function such as a hash with a seed value and a salt.
For if we wanted to generate four ratchet values based a master key of “AlicePassword” (and using an HMAC hash, and where Alice will with an interactive hash of 0, 1, 2 and 3):
H0(AlicePassword)≡HMAC(AlicePassword,0x00)
H1(AlicePassword)≡HMAC(AlicePassword,0x01)
H2(AlicePassword)≡HMAC(AlicePassword,0x02)
H3(AlicePassword)≡HMAC(AlicePassword,0x03)Each key is thus derived from the original seed. By observing H0(AlicePassword), it would not be possible to determine the next in the sequence (H1(AlicePassword)). As she sends messages, she creates an iterative hash for each one.
With the double racket method, Bob and Alice use their own outbound session — with a ratchet and elliptic curve key exchange — to encrypt messages.
The ratchet can only go forwards (and not backwards) and derives a unique key for each message. Ed25519 elliptic curve signatures are then used to prove authenticity. The value of the ratchet and the Ed25519 public key are shared with the other parties in the conversation.
Initially, Alice and Bob each create three Elliptic Curve key pairs (Identity, Ratchet and Handshaking):
The keys will then be derived from these. Bob, for example, exposes thre three public keys to Alice, but keeps his private keys for the generation of the shared secret key for the messages that Alice send to him. This key exchange will only be for the messages flowing between Alice and himself.
A demo of a double ratchet system is here:
https://asecuritysite.com/kdf/ratchet
Building the MLS standard
Within IETF 101 in London, a grouping which included representatives from Cisco, Meta, Google, Mozilla, and the University of Oxford. On 27 March 2023, they finally published their first draft [here]:
Asynchronous Ratcheting Trees (ART) overcomes the problem posed in many existing end-to-end encryption methods (such as WhatsApp, Signal, Meta Messenger, Google Allo and Wire), and where an adversary who compromises one member of a group, can intercept communications — indefinitely. A core advantage of ART is forward security, and where a single breach will not breach future communications.
An implementation of MLS is here:
https://asecuritysite.com/golang/go_mls
Conclusions
Current end-to-end encryption methods, such as with WhatsApp and Signal, are strong in their security application, but a single breach of a user in a group will cause future messages to be breached. MLS provides a new way to support a near-perfect secure messaging system. In the end, it’s about ratchets.
References
[1] Cohn-Gordon, K., Cremers, C., Garratt, L., Millican, J., & Milner, K. (2018, October). On end-to-end encryption: Asynchronous group messaging with strong security guarantees. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (pp. 1802–1819).