How does the Signal Protocol achieve end-to-end encrypted communication?

ChainX and Coming’s development team reached a strategic partnership. Coming is a blockchain encrypted real-time communication chat program using the Signal Protocol that integrates communication and payment functions. Coming is committed to becoming the Wechat of the encrypted world, creating an encrypted chat system, helping users reduce communication costs and improve communication efficiency.

After the successful launch of Coming, the ChainX Network will serve as Coming’s Identity Key database for on-chain decentralized identity. XBTC will be introduced as a means of payment, for its unique feature of lower handling fees and faster transfer speeds than Bitcoin. Only 6 seconds transfer times and a handling fee of less than 1 cent is a natural advantage.

So how does the Signal protocol achieve end-to-end encrypted asynchronous communication between users? This article will take help you understand Signal protocol’s double ratchet algorithm.

Signal protocol-double ratchet algorithm

The double ratchet algorithm is the core communication protocol in the Signal protocol. The process is to first calculate the root key shared by both communicating parties through X3DH, and then step through the combination of DH ratchet and KDF ratchet (symmetric key ratchet) to ensure the security of the entire communication process. In the double ratchet algorithm, there are four process chains, a DH chain stepped by a DH ratchet, a root chain stepped by a KDF ratchet, a sending chain stepped by a KDF ratchet, and a receiving chain stepped by a KDF ratchet.

DH algorithm

Concept explanation

The DH key exchange algorithm refers to a method of generating the same shared key through the private key held by each and with it securely share information.

Application in Signal

The traditional DH algorithm is not directly used, but a modified version ECDH. It is, however, good to understand the basics.

Example explanation

Suppose Ali and Bob need to communicate with each other and share secret keys.

Ali gives Bob two plaintext parameters. P, G . These are identifiable by anyone as public keys.

Ali generates a random number. A (Ali’s private key) and does not tell anyone, not even Bob.

Bob does the same and generates. B (Bob’s private key).

Ali uses his private key. A. to encrypt information. G, P. (encrypted. G^AmodP ) and transfers it to Bob.

Bob uses his private key. B. to further encrypt Ali’s already encrypted information to create one side of the puzzle. (G^AmodP)^BmodP=G^{A*B}modP=S .

Bob also uses his private key. B. to encrypt information. G, P. (encrypted. G^BmodP ) and transfers it to Ali in return.

Ali uses his private key. A. to further encrypt Bob’s already encrypted information to create the other side of the puzzle. (G^AmodP)^BmodP=G^{A*B}modP=S

Now Ali and Bob together have encrypted their side of the puzzle and know how to solve it to get the information hidden within.

In this process. P must be a very large prime number so a third party cannot guess the private keys of either Ali or Bob.

EC-DH algorithm

Concept explanation

ECDH is a combination of the ECC algorithm and the DH algorithm, and can also be used to calculate a common key. ECC is a cryptosystem based on the discrete logarithm problem of an elliptic curve. Given a point P on the elliptic curve and an integer k, it is easy to solve Q=kP; given a point P, Q, and knowing that Q=kP , It is a difficult problem to find the integer k. ECDH is a key negotiation process based on this mathematical puzzle.

Note: Addition, subtraction, multiplication, and division in elliptic curves are different from doing those with constants. For more information on elliptic curve calculation you can refer to the following videos:

https://www.youtube.com/watch?v=wSSKz6-ivQU

https://www.youtube.com/watch?v=rV28ZoNmxdQ

Application in Signal

It is the main algorithm in DH ratchet stepping, and it is also used for calculation in X3DH algorithm.

Example explanation

We’re taking two people again, Alice and Bob, who have shared curve parameters (elliptic curve E, order N, base point G).

1) Alice generates a random integer a, and calculates A=a*G, generating her public key A

2) Bob generates a random integer b, and calculates B=b*G, generating his public key B

3) Alice passes A to Bob. The delivery of A can be made public, that is, anyone can obtain A.

4) Bob passes B to Alice. In the same way, the transmission of B can be made public.

5) Bob receives A from Alice and calculates Q = b*A, obtaining the symmetric key Q through his private key and Alice’s public key.

6) Alice receives B from Bob and calculates Q = a*B, obtaining the symmetric key Q through her private key and Bob’s public key.

Commutative and associative

Alice gets Q=a*B=a*(b*G)=(a*b)*G

Bob gets Q=b*A=b*(a*G)=(b*a)*G

and so, both parties get the same key Q.

X3-DH algorithm

Concept explanation

In the Signal protocol, X3DH is a derivative algorithm based on the ECDH algorithm, but it introduces more public key parameters to improve security. At the same time, the advantage of the DH algorithm is that the user can asynchronously negotiate a common key with the user based on these keys. There is no need for the user to stay online because the public keys of all parties are stored on the server-side.

Application in Signal

X3DH is the core algorithm used by the Signal protocol to create a common root key.

3 roles in the agreement

User A, User B, Server.

The main data of the user in the agreement

IK (Identity Key Pair): a long-term key pair conforming to the DH protocol, created when the user registers and bound to the user’s identity.

Temporary public and private key pair EK (Ephemeral Key Pair): A short-term key pair conforming to the DH protocol, a temporary key pair established every time the user interacts with the protocol.

Signed pre-shared public-private key pair SPK (Signed Pre Key pair): A mid-term key pair that conforms to the DH protocol, created when the user registers, signed by the identity key, and periodically rotated.

One-time pre-shared public and private key OPK (One-Time Pre Keys pair), this algorithm does not use this public-private key pair: the one-time use Curve25519 key pair queue, generated during installation, and supplement the signed pre-shared public key when insufficient Value Sig (IK, Encode (SPK) ): A piece of data signed with the IK private key. The data contains encoded SPK and IK to prove the legality of SPK.

Core calculation formula

(Here DH calculation is ECDH calculation)

DH1 = DH(IPK-A, SPK-B)

DH2 = DH(EPK-A, IPK-B)

DH3= DH(EPK-A, SPK-B)

SK=KDF(DH1||DH2||DH3)

“DH (IPK-A, SPK-B)” means using the private key corresponding to the user’s IPK-A to perform DH calculation on SPK-B

“||” represents a link, ie 123||456=123456

KDF is a kind of key derivation algorithm, which can be regarded as an enhanced hash to derive a fixed-length message key S (DH calculation is performed because the DH key is too long to be used as a message key, so it is for a KDF calculation, during the initial root key calculation, the KDF output result is directly used as the root key. In the subsequent DH ratchet stepping, the first half of the KDF output is used as the root key for the next KDF calculation, and the second half is used as the message root key, message root key is used as receiving root key or sending root key.

Question

Why should I join SPK-B instead of directly using IPK-B for X3DH calculation or X2HD calculation? The calculation is then changed to:

DH1 = DH(IPK-A, IPK-B)

DH2 = DH(EPK-A, IPK-B)

Answer

Reason 1: If the SPK key pair is not added, if the sender sends a huge amount of information attack to the receiver, the receiver will not be able to change the SPK to reject the message.

Reason 2: In the calculation of X3DH, SPK can be used as the initial EK public key for participating in the calculation of the initial root key.

Two-double ratchet algorithm

Data distribution

Ratchet operation

Ratchet 1

DH ratchet, DH ratchet operates on the DH chain transformed by EK

Step conditions

When the role of one party changes, for example when the sender becomes the receiver.

Step method

Scenario 1: When the receiver turns to the sender, generate a new EK pair, use your new EK private key to step the ratchet.

Scenario 2: When the sender turns into a receiver, he receives the other party’s new EK public key and uses the other party’s new EK public key to step the ratchet

Ratchet 2

KDF ratchet wheel (also called symmetric key ratchet wheel), KDF ratchet wheel operates on the root chain, receiving chain, and sending chain.

Step conditions

When a new message is to be sent (that is, a new encryption key is required), or a new message is to be received (that is, a new decryption key is required).

Step method

Scenario 1: When sending encrypted information or receiving decrypted information, the DH ratchet does not step. Do KDF step forward directly on the current sending or receiving chain.

Scenario 2: When sending encrypted information or receiving decrypted information, the DH ratchet is stepping. The DH ratchet needs to be stepped first, and then a new KDF receiving chain or sending chain step is made under the derivative of the new DH ratchet.

Double ratchet case

Note: Alice’s encryption key A1 in the figure is the same as Bob’s decryption key A1, and the corresponding keys in the green box are the same.