Message Encryption
The message encryption (LIME) adopted by Linphone utilizes the following protocols published by Signal. X3DH is a procedure for generating a shared key, while the Double Ratchet is a procedure that uses the shared key generated by the X3DH protocol to generate and update new keys for encrypting and decrypting messages.
The key used for encryption itself is the X-coordinate on a geometric elliptic curve (the coordinate after modulo operation). In X3DH and Double Ratchet, the following elliptic curves, which consider a balance between computational efficiency and security, are utilized.
Curve25519 (𝐸 ∶ 𝑦² = 𝑥³ + 486662𝑥² + 𝑥 and 𝑝 = 2²⁵⁵ − 19)
or,
Curve448 (𝐸 ∶ 𝑦² + 𝑥² = 1 − 39081𝑥²𝑦² and 𝑝 = 2⁴⁴⁸ − 2²²⁴ − 1)
X3DH（Extended Triple Diffie-Hellman）
ECDH (Elliptic Curve Diffie-Hellman) is a key generation algorithm that utilizes coordinates on an elliptic curve, and X3DH is an extension of this. Several additional keys are introduced for generating the shared key, making the process multi-staged.
X3DH is primarily used to securely exchange encryption keys between two parties communicating for the first time and to establish a ‘session key’ necessary for encrypting subsequent messages. Specifically, X3DH is utilized in the process of initial key exchange and the establishment of trust.
X3DH plays a critical role in the following processes.
1. Initial Key Exchange (When Communicating for the First Time)
When users send messages to each other for the first time, neither user is aware of the other’s public key. At this stage, X3DH is used to securely exchange keys, allowing encrypted messages to be exchanged. Through this initial key exchange, a session key is generated between both parties, and subsequent messages are encrypted.
X3DH achieves secure key exchange using the following four keys:
Long-Term Public Key (Identity Key, IK):
A public key generated by each user in advance and shared with other users. This allows users to identify their communication partner’s identity.
Signed PreKey (SPK):
A temporary public key published by each user, signed with the long-term public key. It plays a crucial role in preventing man-in-the-middle attacks.
One-Time PreKey (OPK):
A temporary public key that is only used once. This key is prepared to enhance communication confidentiality and is independent of other keys that may already have been exchanged.
Sender’s Ephemeral Key (EK):
A temporary key generated by the message sender during transmission, used in the session.
2. The X3DH Key Exchange Protocol Flow
X3DH facilitates secure key exchange through the following steps:
Receiving Public Keys:
The message sender (Alice) retrieves the recipient (Bob)’s set of public keys (Identity Key, Signed PreKey, One-Time PreKey) from the X3DH server.
- Alice uses Bob’s long-term public key, the Identity Key, to verify the signature on the Signed PreKey —> DH1
Diffie-Hellman Key Exchange:
Alice generates her own ephemeral key (EK) and performs the following three Diffie-Hellman key exchanges using Bob’s public keys:
- Alice’s ephemeral key with Bob’s Identity Key —> DH2
- Alice’s ephemeral key with Bob’s Signed PreKey —> DH3
- Alice’s ephemeral key with Bob’s One-Time PreKey —> DH4
This process generates shared secret information, which is used to derive encryption keys.
Key Derivation:
Using the secret information obtained from the Diffie-Hellman key exchanges as input, a shared session key is derived through HKDF (HMAC-based Key Derivation Function). This key is used to encrypt subsequent communications.
Establishing the Session Key:
The session key established in this way is used for sending subsequent messages. The first message is encrypted with this key, and the recipient decrypts it using their own private key.
3. Subsequent Communication and Integration with the Double Ratchet Protocol
Once the initial key exchange with X3DH is complete, subsequent communication is managed by the Double Ratchet protocol. The Double Ratchet protocol generates a new key for each message, providing higher security. The session key established by X3DH is used as the initial key for the Double Ratchet protocol, and the keys for subsequent messages are updated according to the Double Ratchet mechanism.
The Role of EdDSA in X3DH
When using EdDSA, the signature must always be applied to some kind of data. The target of the signature is not limited to the message body, and can also include the key itself or attributes of the key as part of the signature target.
EdDSA(Linphone uses EdDSA, not XEdDSA) is used in the following scenarios:
Edwards-Curve Digital Signature Algorithm (EdDSA)
1. Signing the Signed PreKey
The Signed PreKey is a temporary public key that each user uploads to the server and is used in the X3DH protocol key exchange. To prevent the PreKey from being tampered with by third parties, the user’s long-term Identity Key (ID Key) is used to sign it with Ed25519. This signature ensures that the Signed PreKey cannot be altered or replaced by others.
2. Signature Verification DH1
When initiating a key exchange, the message sender (Alice) retrieves the recipient (Bob)’s Signed PreKey from the server. Alice uses Bob’s long-term Identity Key to verify the Ed25519 signature applied to the Signed PreKey. This verification process confirms that the Signed PreKey was indeed generated by Bob and has not been tampered with.
Both Alice and Bob, who are sending and receiving messages, generate a shared key using the keys defined below.
-
Alice’s identity key IKA
-
Alice’s ephemeral key EKA
-
Bob’s identity key IKB
-
Bob’s signed prekey SPKB
-
Bob’s prekey signature Sig(IKB, Encode(SPKB))
-
(Optionally) Bob’s one-time prekey OPKB
DH1 = DH(IKA, SPKB) DH2 = DH(EKA, IKB) DH3 = DH(EKA, SPKB) SK = KDF(DH1 || DH2 || DH3)
or,
DH1 = DH(IKA, SPKB) DH2 = DH(EKA, IKB) DH3 = DH(EKA, SPKB) DH4 = DH(EKA, OPKB) SK = KDF(DH1 || DH2 || DH3 || DH4)
ECDH(Elliptic Curve Diffie-Hellman)
In ECDH, when the straight line connecting any two points ( P ) and ( Q ) on the elliptic curve (or the tangent line at any point ( P )) intersects the elliptic curve at a point ( R’ ), and the point ( R ) is obtained by reflecting ( R’ ) across the X-axis, then geometrically, it holds that ( P + Q = R ) (in the case of the tangent line, ( P + P = 2P = R )) on the elliptic curve. The operations for these points are defined like the followings;
- P+Q=R：Point Addition
- P+P=2P=R：Point Doubling
According to the above rule, the point where the tangent at ( R = 2P ) intersects the elliptic curve, reflected across the X-axis, can be defined as ( 2P + 2P = 4P ). Similarly, from the tangent at point ( 4P ), the point ( 4P + 4P = 8P ) can be defined.
At this stage, we have defined the points ( P ), ( 2P ), ( 4P ), and ( 8P ). From these points, for example, the point ( 3P ) can be defined as the point where the straight line connecting ( P ) and ( 2P ) intersects the elliptic curve and is reflected across the X-axis. By efficiently utilizing scalar multiplication and point addition in this way, calculations such as ( 2P + 4P = 6P ), ( 4P + 8P = 12P ), and from this ( 12P + 8P = 20P ), can be performed efficiently.
The following site provides a clear summary of elliptic curves and the operations on each point.
The Animated Elliptic Curve
In ECDH, we do not directly use arbitrary points on the actual elliptic curve. Dealing with coordinates that are fractional or points at infinity would be impractical. Therefore, both sides of the elliptic curve equation are subjected to Modulo operations, transforming them into a set of points (x, y) where the results of the operations are equal. The idea is as follows.
Any point on the elliptic curve Curve25519 is plotted in a finite field using Modulo operations (excerpted).
The total number of points is:
n = 2²⁵² + 27742317777372353535851937790883648493
In Curve25519’s ECDH, points are plotted irregularly (though they are symmetrically aligned with respect to the line y = p/2). While the starting point P and the shared points aP and bP (with multipliers a and b used as secret keys) may be known to a third party, calculating (a + b)P is straightforward, but identifying abP is practically impossible. This is due to the difficulty of the elliptic curve discrete logarithm problem, especially since n is an astronomically large number.
As an example of a specific shared key generated by Curve25519’s ECDH, as the starting point P :
P=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 )
In this case, Alice and Bob each define their secret keys and exchange their public keys to generate a shared key. The key exchange protocol that adopts Curve25519 is called X25519.
Secret key (scalar multiplier of point P)
Bob private (b): 19606234678399378633456480350841655717034562515722490628739051202331311643228
Alice private (a): 109204347234327284008793236257980475297107461097776439083128173099763401227175
Public key (X-coordinates of the points aP and bP obtained through scalar multiplication)
Bob public (bP): b'34c2b65e53c2877a7321c29ac3a1c2bac29d3721c29fc3bb44c291c392c28dc38574c38d7562c3bf71c39fc2a4c3aec2b973'
Alice public (aP): b'c2a307c384c3b9c39f64067cc3b724c290c3a818c28fc2abc2aa151d0a3e2c2c42c38cc28f4e3f0e1d54c2a744'
Shared key (X-coordinate of the point obtained by scalar multiplication of Alice’s and Bob’s secret keys with each other’s public keys)
Bob shared (b)aP: b'c382c2ba19c3b1c39142c38ec39161c2b93251c390c2876ac2b477c3bf6ec28740c2a7c387c283c2be6ec2b1c28bc3a32dc3a128'
Alice shared (a)bP: b'c382c2ba19c3b1c39142c38ec39161c2b93251c390c2876ac2b477c3bf6ec28740c2a7c387c283c2be6ec2b1c28bc3a32dc3a128'
The key size used in X25519 is 32 bytes (256 bits). However, to address various security concerns, the following 5 bits of values are fixed:
| Bits | Value | Reason |
|---|---|---|
| 0,1,2 | 0 | Protect against small-subgroup attacks, which would allow one peer to use a manipulated secret key to discover the other peer’s secret key |
| 254 | 1 | Prevent implementors from skipping a multiplication round for smaller keys, which would expose a timing leak |
| 255 | 0 | Constrain n < 2²⁵⁵, which prevents the algorithm from reaching the “infinity” result for base-point x=9 |
Below is a specific example of how to perform point operations in a finite field obtained by applying modulo operations to an elliptic curve. As the starting point P(X0, Y0) equals (5, 7). We will calculate 2P from the tangent line at this point.
y²=x³+9x+1 mod 61
The slope λ of the tangent line at point P can be found by differentiating both sides.
2y･dy/dx=3x²+9 λ=dy/dx=(3x²+9)/2y=(325+9)/27=42/7=6 mod 61 = 6
The coordinates of 2P(X1, Y1) are:
X1=λ²-2X0=36-25=26 mod 61 = 26 Y1=λ(X0-X1)-Y0=6(5-26)-7=6(-21)-7=-126-7=-133 mod 61 = (-61*2-11) mod 61 = -11 mod 61 = 50
As a result, 2P(26,50)
Similarly, from the tangent at point 2P and its coordinates, we can calculate point 4P. From the tangent at point 4P and its coordinates, we can calculate point 8P, and so on, leading to the calculation of points 16P, 32P, 64P, 128P, and so forth.
Double and Add Algorithm
Converting the scalar multiplier k to binary allows for efficient computation of the point kP. The scalar value is handled bit by bit, and for each bit, the operations of “Doubling” and “Addition” are repeated. In practice, an algorithm known as the Montgomery ladder is used, which is resistant to side-channel attacks (such as timing attacks and electromagnetic radiation attacks).
If the bit is 1, both “Doubling” and “Addition” are performed; if the bit is 0, only “Doubling” is performed.
For example, if k = 151, its binary representation is 10010111. Therefore,
151P = (2⁷x1+2⁶x0+2⁵x0+2⁴x1+2³x0+2²x1+2¹x1+2⁰x1)P
- Bit 0: Represents the point P itself.
- Bit 1: Doubling the point 2P and adding 2P + P.
- Bit 2: Doubling the point 4P and adding 4P + 2P + P.
- Bit 3: Doubling the point 8P.
- Bit 4: Doubling the point 16P and adding 16P + 4P + 2P + P.
- Bit 5: Doubling the point 32P.
- Bit 6: Doubling the point 64P.
- Bit 7: Doubling the point 128P and adding 128P + 16P + 4P + 2P + P = 151P.
This can be processed with 7 doublings and 4 additions.