Understanding Signal Protocol: X3DH Protocol

In today's digital age, where major tech corporations routinely collect vast amounts of our personal information, Signal stands out as a breath of fresh air. Endorsed by notable people like Edward Snowden, Mark Zuckerberg, and Elon Musk, Signal prioritizes user privacy through robust end-to-end encryption.

Introduction

Generally, in an instant messaging app, users communicate with each other through a "trustworthy" server that takes the message and forwards it to the receiver. When doing this, we put a lot of faith in the server that it won't misuse our data. Malicious access to the server would mean the attacker can access all the messages.

The Signal Protocol, an open-source end-to-end encryption protocol, solves this problem with end-to-end encryption, where the decrypted version of the message is only stored on the client's devices to whom the conversation belongs.

Keys Generation on User Registration

Diffie Hellman Key Exchange Algorithm

We must first understand the Diffie Hellman (DH) Key Exchange Algorithm to understand how the Signal Protocol achieves end-to-end encryption. This algorithm allows two parties to establish a mutual secret without that secret being transmitted over the internet.

To better understand the algorithm, let's consider we have a public server and two parties, say, Alice and Bob.

We have two numbers stored on the public server: gand n with g being a small prime number and n being a very large number, often ranging from 2000 to 4000 bits.

Now, here's how the exchange happens:

Generate Private Keys: Both Alice and Bob generate private keys; let's call them a and b respectively, where 1 ≤ x ≤ n.
Generate Public Keys: Alice calculates her key as (g ^ a) % n , and Bob calculates his key as (g ^ b) % n. These keys are then shared with each other through the public server.
Shared Secret: Now comes the fascinating part. Both Alice and Bob raise the received key with their own private number. Alice calculates ((g ^ b) % n) ^ a) % n and Bob calculates ((g ^ a) % n) ^ b) % n.
Both of these calculations generate the same value, which Alice and Bob use to encrypt their messages without publicly sharing the key through the server.

Now, let us see its implementation in Typescript:

// Let's consider g = 11 and n = 100
const g = 11;
const n = 100;

// Generate private numbers for Alice and Bob
const a = randomIntFromInterval(1, n)
const b = randomIntFromInterval(1, n)


// Generate private keys for Alice and Bob using modular exponentiation
const a_key = modExp(g, a, n);
const b_key = modExp(g, b, n);


// Generate shared secret using modular exponentiation
const a_shared_secret = modExp(b_key, a, n);
const b_shared_secret = modExp(a_key, b, n);

console.log(`The shared secret are same: ${a_shared_secret === b_shared_secret}`);

//Result "The shared secret are same: true"

function randomIntFromInterval(min: number, max: number) { 
  return Math.floor(Math.random() * (max - min + 1) + min)
}

// Helper function for modular exponentiation
function modExp(base:number, exponent:number, modulus:number) {
    if (modulus === 1) return 0;
    let result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    return result;
}

Diffie Hellman Key Exchange Proof Implementation in Typescript

X3DH Key Agreement Protocol

Extended Triple Diffie Hellman or X3DH is a key agreement protocol for asynchronous messaging. While asynchronous messaging is also possible using Diffie Hellman as well, it was not designed for this purpose. It is used to create a shared secret between two parties.

Publishing PreKeys

When a user registers to the Signal, in this case, Bob, he sends a set of public keys to the Signal Server containing:

Bob's identity key IK_B
Bob's signed prekey SPK_B
Bob's prekey signature Sig(IK_B, Encode(SPK_B))
Bob's one time pre keys (OPK_B¹, OPK_B², OPK_B³, ...)

Sending Message

For Alice to send a message to Bob, Alice contacts the server and fetches "prekey bundle" containing Bob's identity key, signed prekey, prekey signature and one of Bob's one time prekey.

Verifying prekey bundle: Alice first needs to verify that the keys belong to Bob. Since, Alice has access to IK_B , she can verify that the SPK_B is actually signed by Bob's identity key.

Generate Ephemeral Key: Ephemeral keys are newly generated keys for each new instance of the protocol and can only be used for that instance.

Calculate Diffie Hellman Key:

    DH1 = DH(IK_A, SPK_B)
    DH2 = DH(EK_A, IK_B)
    DH3 = DH(EK_A, SPK_B)
DH4 = DH(EK_A, OPK_B)
    K_AB = KDF(DH1 || DH2 || DH3 || DH4)

where DH means Diffie Hellman Algorithm and || means concatenation of the keys.

Now that Alice has generated the shared secret, she encrypts the message and sends an initial message containing:
- Alice's identity key
- Alice's ephemeral key
- Index of which of Bob's one time prekey was used
- Initial ciphertext

Deciphering Message:
After receiving the message from Alice, Bob performs the same Diffie Hellman calculations that Alice did. Bob then decrypts the initial ciphertext sent by Alice and checks if it is correct. Bob then decrypts the message using the shared key generated. Bob also deletes the OPK_B used and DH keys generated in the process.

This way, Alice and Bob can establish initial communication securely.

Conclusion

To conclude, with its X3DK Algorithm, the Signal Protocol ensures that a secured secret key is generated through a public server.

You can read more about it on Signal's Documentation.

Thank you for reading this article. Please leave a comment below if you have any queries or suggestions.

Understanding Signal Protocol: X3DH Protocol

Suman Khadka