Alice Whispers To Bob: At the core of privacy in the 21st Century is Extended Triple…

Our old digital world of insecure methods is coming to an end. Basically, we took protocols which had little in the way of security, and…

Alice Whispers To Bob: At the core of privacy in the 21st Century is Extended Triple Diffie-Hellman and Ratchets

Our old digital world of insecure methods is coming to an end. Basically, we took protocols which had little in the way of security, and then applied a tunnel and fixed it with PKI. And thus HTTP became HTTPs, FTP became FTPs, and SMTP became SMTPs. Unfortunately, either end of the tunnel is insecure, along with anyone having the private key related to the tunnel being able to break it, and listen to the communications. Our world is now thus looking at complete end-to-end encrypted communications and where we create a new encryption key which is secret to Bob and Alice — for every single message that they send each other.

So let’s look at how the Signal protocol — as used by WhatsApp, Signal, Facebook Messenger, Skype, and a whole lot of methods — sets up a trusted end-to-end tunnel between Bob and Alice.

Some simple Diffie-Hellman

In the online creation of a secure tunnel, Bob and Alice will be actively communicating and can thus generate secrets and the associated public key to each other. With ECDH (Elliptic Curve Diffie Hellman), Bob and Alice generate a short-term secret (a and b) and then pass the public key version of these to the other side (aG and bG). They will then be able to create the same secret key (abG):

Normally we just take the x co-ordinate value of the calculation (abG), and use this as our shared key. A typical set of elliptic curve parameters is defined by Curve 25519 — and which has a prime number of 2²⁵⁵-19). The encryption used to create the tunnel is then just plain-old AES CBC. But with WhatsApp, Bob may be sleeping and offline, so how are Bob and Alice able to create a shared secret key for their communications? Well for this we use x3dh (Extended Triple Diffie-Hellman).

x3dh (Extended Triple Diffie-Hellman)

With x3dh, Bob and Alice create key pairs for their long-term identity (IDA and IDB) and publish these to a trusted server (such as WhatsApp or Signal). Next each of them generate a range of pre-shared public keys, and sign them with their private key. In the case of Alice communicating with Bob, then Bob will have a number of pre-shared signed keys. Let’s say the first one is ‘bG, and Alice selects this one. She then calculates three Diffie-Hellman key exchanges with a secret (a’) and her own long term ID (DH1, DH2 and DH3). This is illustrated in the left-hand side of the following graphic:

In the end, she generates a key (Key), and then encrypts a message with this key, and also forwards her long term public key (IDA), the public key version of the short-term secret key (EKA) and the pre-shared public key that she has selected from Bob. When Bob wakes up he receives the message, and is then able to calculate the same shared key (the right-hand side of the graphic above).

The stages are defined as:

DH1=DH(IDA(Priv),SPKB(Pub))

DH2=DH(EKA(Priv),IDB(Pub))

DH3=DH(EKA(Priv),SPKB(Pub))

Key=DH1||DH2||DH3

and where: IDA is Alice’s long term public key (aG); IDB is Bob’s long term public key (bG); SPKB is one of Bob’s long term pre-shared pubic keys (b′G); and EKA is the public key that Alice would like to use for the key generation.

Bob will receive IDA(Public) and EKA(Public) from Alice. She will also send the pre-shared public key that she has used SPKB(Pub). From this Bob can then determine SPKB(Priv). Next he can compute:

DH1=DH(SPKB(Priv),IDA(Pub))

DH2=DH(IDB(Priv),EKA(Pub))

DH3=DH(SPKB(Priv),EKA(Pub))

Key=DH1||DH2||DH3

In the end, she generates a key (Key), and then encrypts a message with this key, and also forwards her long term public key (IDA), the public key version of the short-term secret key (EKA) and the pre-shared public key that she has selected from Bob. When Bob wakes up he receives the message, and is then able to calculate the same shared key (the right-hand side of the graphic above).

In the following we create the keys for Bob and Alice: link.

package main

import (
    signal "github.com/dosco/libsignal-protocol-go"
    "fmt"

)

func main() {


    msA := signal.NewMemoryStore()
    msB := signal.NewMemoryStore()

    // Alice keys
    idA := signal.GenerateRegistrationId()
    msA.PutLocalRegistrationID(idA)


    ikpA := signal.GenerateIdentityKeyPair()
    msA.PutIdentityKeyPair(ikpA)

    pkA := signal.GeneratePreKey(1)
    msA.PutPreKey(1, pkA)

    spkA := signal.GenerateSignedPreKey(ikpA, 1)
    msA.PutSignedPreKey(1, spkA)

    // Bob keys

    idB := signal.GenerateRegistrationId()
    msB.PutLocalRegistrationID(idB)

    ikpB := signal.GenerateIdentityKeyPair()
    msB.PutIdentityKeyPair(ikpB)

    pkB := signal.GeneratePreKey(1)
    msB.PutPreKey(1, pkB)

    spkB := signal.GenerateSignedPreKey(ikpB, 1)
    msB.PutSignedPreKey(1, spkB)


    fmt.Printf("Alice ID (idA): %d\n", idB)
    fmt.Printf("Alice ID key (pkA.Pub): %x\n", *pkA.Pub)
    fmt.Printf("Alice Pre-key (spkA.Pub): %x\n\n", *spkA.Pub)

    fmt.Printf("Bob ID (idB): %d\n", idB)
    fmt.Printf("Bob ID key (pkB.Pub): %x\n", *pkB.Pub)
    fmt.Printf("Bob Pre-key (spkB.Pub): %x\n\n", *spkB.Pub)


    ephemeralKeyPair := signal.GenerateEphemeralKeyPair()
    ekA := ephemeralKeyPair.Priv

    // Calculate DH parameters and keys

    dh1 := signal.DH(ikpA.Priv, spkB.Pub)
    dh2 := signal.DH(ekA, ikpB.Pub)
    dh3 := signal.DH(ekA, spkB.Pub)



    fmt.Printf("DH1: %x\n", *dh1)
    fmt.Printf("DH2: %x\n", *dh2)
    fmt.Printf("DH3: %x\n", *dh3)

    dhList := [][]byte{dh1[:], dh2[:], dh3[:]}

    res := signal.KDF(dhList...)

    fmt.Printf("\nKey (RootKey, ChainKey, Index): %x\n", *res)


}

A sample run is:

Alice ID (idA): 2365460722503326970
Alice ID key (pkA.Pub): {27477a5a8af1141953c07c80769987042797dc141c92ceee7dde8cb6986aba2b}
Alice Pre-key (spkA.Pub): {7d8e1961549df7dc5063020eb2f30ac75899d0a71b0d2ab35528d7860d5f8c66}

Bob ID (idB): 2365460722503326970
Bob ID key (pkB.Pub): {7db8a56ee1c38fc2d20bc6f8f7cb48462b811e77e970a42acfb3b77192827970}
Bob Pre-key (spkB.Pub): {b7bd1285f297583978a24116053e69fc6e0564048b38f4a477fb6ca804099b0a}

DH1: 64e5514c1da82dc2b5eccef1fa96bc9066d763ee9eeba775fec1ba3a52024d40
DH2: dc6d9e773c6efd6c1a6f251eca01f8bc4f9b8765431ba6ac573e2eddcb31d20a
DH3: 8f2f59163616755cc99afa07201c3612c61e9029b96a6c39cf23ee34a5c1fe51

Key (RootKey, ChainKey, Index): {52827da3872cf4076dbc334a1fc9596599d745653a09fac7f0dcbad22337beca 1f1a4c84a1af18b7967449795c7995b6a946d2aace140e8e907cdcf5557e335e 0}

Signal

With the rise in the threat of insiders and in the loss of long-term keys, Signal — developed by Open Whisper Systems — is increasingly seen as the tool of choice for many companies. With this we get end-to-end encryption, and where there is no opportunity for a breach of a long-term key to comprise any of the previously encrypted communications.

The showcase their citizen-first approach with the tagline of:

Signal is made for you. As an Open Source project supported by grants and donations, Signal can put users first. There are no ads, no affiliate marketers, no creepy tracking. Just open technology for a fast, simple, and secure messaging experience. The way it should be.

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 (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 sessions 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.

Double ratchet

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 on-going 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. 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 will create two names (a and b), and then a will encrypt two and b will encrypt one message for a:

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 dog

A 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 were 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 — which is a ratchet and elliptic curve — 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. If you want to see it in action, try here.

Conclusions

A basic message here … make sure you are using forward secrecy and that your key exchange methods are ephemeral … no excuses for large organisations. Methods such as Signal are increasingly replacing many of the communications systems which were based on secure email. The concept of secure email is really something that has never happened, and where we often just secure the transmission of the email and have little in the way of security and authentication on the email client. Our future must be end-to-end encryption for all our communication systems.