As Google Whispers, The Rest Should Hear Loudly

We have a flawed Internet. It is an Internet created in the 1980s, and the protocols we use are much the same as the ones we developed…
Photo by Kristina Flour on Unsplash

As Google Whispers, The Rest Should Hear Loudly

We have a flawed Internet. It is an Internet created in the 1980s, and the protocols we use are much the same as the ones we developed then, and where security was an afterthough. We must now rebuild, and move away from using simplistic tunnels like TLS and IPSec, and implement proper end-to-end encryption methods. This will authenticate both sides of a conversation, and will overcome many of the problems of using machine-to-machine tunnels. So as some companies such as Zoom have been “forced” to implement end-to-end encryption, others, such as a Google, have been forging ahead with systems based on Signal.

You might have a case to critize Google for its data gathering methods, but you can’t fault them on their drive for better crypto. My “paper of the week” is this [here]:

It’s a really great read, and compared with Zoom’s “let’s implement E2E encryption because we’re getting bad press”, it is a real step forward in thinking, and advances the methods employed by Signal, including with rackets. In fact, if the Internet was created now, it would perhaps look a lot like this. Overall the paper focuses on Google’s approach for Duo in mobile devices and Nest. This includes the protection of video, images and text messages. At it’s core is … of course … Curve 25519 with ECDH-Curve 25519.

What is interesting is the three-way handshake with the X3DH method, and which is known as the “Whisper” protocol:

Here is an explaination:

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:	AliceBob  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+MYNLpF3dDwN6SOJFQTjzYe5eVaflBTrJn55TDb 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.