Signal Protocol: Diffie-Hellman Key Exchange – A Primer

There has been a mass exodus of users from WhatsApp platform to Signal. It started on around Jan 6th when iPhone and Android users started receiving messages on their WhatsApp as shown here.

Elon Musk’s tweet of two words, next day, created a storm.

https://twitter.com/elonmusk/status/1347165127036977153

It has brought the topic of End-2-End-Encryption (E2EE) to forefront and the Signal Protocol is used by all major messaging platforms including WhatsApp for this purpose. The Signal Protocol (formerly known as TextSecure Protocol) is a non-federated cryptographic protocol. It was developed by Open Whisper Systems in 2013 and was first introduced in the TextSecure app that later became Signal.  It makes it impossible for your past messages to be decrypted by anyone including yourself unless you have saved it in unencrypted way to some storage.

The Signal protocol combines the following:

·        Double Ratchet algorithm

·        Prekeys

·        A triple Elliptic-curve Diffie–Hellman (3-DH) handshake

·        Curve25519, AES-256, and HMAC-SHA256

Double Ratchet Algorithm

In cryptography, the Double Ratchet Algorithm is a key management algorithm that was developed by Trevor Perrin and Moxie Marlinspike in 2013. After an initial key exchange, it manages the ongoing renewal and maintenance of short-lived session keys. It combines a cryptographic so-called "ratchet" based on the Diffie–Hellman key exchange (DH) and a ratchet based on a key derivation function (KDF), such as a hash function, and is therefore called a double ratchet.

Prekeys

Prekeys are a set of keys that a participant stores at the server to be able to receive messages even when it is offline.

Elliptic-curve Diffie–Hellman (ECDH)

It is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or to derive another key. The key, or the derived key, can then be used to encrypt subsequent communications using a symmetric-key cipher. It is a variant of the Diffie–Hellman protocol using elliptic-curve cryptography.

Following excerpt is taken directly from this link as I found it to be the simplest explanation that can be understood by all.

How does the Diffie-Hellman key exchange work?

The Diffie-Hellman key exchange is complex, and it can be difficult to get your head around how it works. It uses very large numbers and a lot of math, something that many of us still dread from those long and boring high school lessons.

To make things a bit easier to understand, we will start by explaining the Diffie-Hellman key exchange with an analogy. Once you have a big-picture idea of how it works, we will move on to a more technical description of the underlying processes.

The best analogy for the Diffie-Hellman scheme is to think of two people mixing paint. Let us use the cryptography standard and say that their names are Alice and Bob. They both agree on a random color to start with. Let us say that they send each other a message and decide on yellow as their common color, just like in the diagram below:

They chose their own secret color. They do not tell the other party their choice. Let us say that Alice chooses red, while Bob chooses a slightly greenish blue.

The next step is for both Alice and Bob to mix their secret color (red for Alice, greenish blue for Bob) with the yellow that they mutually agreed upon. According to the diagram, Alice ends up with an orangish mix, while Bob’s result is a deeper blue.

Once they have finished the mixing, they send the result to the other party. Alice receives the deeper blue, while Bob is sent the orange-colored paint.

Once they have received the mixed result from their partner, they then add their secret color to it. Alice takes the deeper blue and adds her secret red paint, while Bob adds his secret greenish blue to the orange mix, he just received.

The result? They both come out with the same color, which in this case is a disgusting brown. It may not be the kind of color that you would want to paint your living room with, but it is a shared color, nonetheless. This shared color is referred to as the common secret.

The critical part of the Diffie-Hellman key exchange is that both parties end up with the same result, without ever needing to send the entirety of the common secret across the communication channel. Choosing a common color, their own secret colors, exchanging the mix and then adding their own color once more, gives both parties a way to arrive at the same common secret without ever having to send across the whole thing.

If an attacker is listening to the exchange, all that they can access is the common yellow color that Alice and Bob start with, as well as the mixed colors that are exchanged. Since this is really done with enormous numbers instead of paint, these pieces of information are not enough for the attack to discern either of the initial secret colors, or the common secret (technically it is possible to compute the common secret from this information, but in a secure implementation of the Diffie-Hellman key exchange, it would take an unfeasible amount of time and computational resources to do so).

This structure of the Diffie-Hellman key exchange is what makes it so useful. It allows the two parties to communicate over a potentially dangerous connection and still come up with a shared secret that they can use to make encryption keys for their future communications. It does not matter if any attackers are listening in, because the complete shared secret is never sent over the connection.

 Curve25519

In cryptography, Curve25519 is an elliptic curve offering 128 bits of security (256 bits key size) and designed for use with the elliptic curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest ECC curves and is not covered by any known patents. The reference implementation is public domain software.

AES-256

The algorithm described by AES is a symmetric-key algorithm, meaning the same key is used for both encrypting and decrypting the data.

HMAC-SHA256

In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message.

HMAC can provide digital signatures using a shared secret instead of public key encryption. It trades off the need for a complex public key infrastructure by delegating the key exchange to the communicating parties, who are responsible for establishing and using a trusted channel to agree on the key prior to communication.

The interest in secure messaging has perked up again and more detailed functioning of Signal Protocol will be covered in subsequent articles.