The Signal Protocol Used By 1+ Billion People Is Getting A Post-Quantum Makeover

The Signal Foundation, maker of the Signal Protocol that encrypts messages sent by more than a billion people, has rolled out an update designed to prepare for a very real prospect that’s never far from the thoughts of just about every security engineer on the planet: the catastrophic fall of cryptographic protocols that secure some of the most sensitive secrets today.

The Signal Protocol is a key ingredient in the Signal, Google RCS, and WhatsApp messengers, which collectively have more than 1 billion users. It’s the engine that provides end-to-end encryption, meaning messages encrypted with the apps can be decrypted only by the recipients and no one else, including the platforms enabling the service. Until now, the Signal Protocol encrypted messages and voice calls with X3DH, a specification based on a form of cryptography known as Elliptic Curve Diffie-Hellman.

A brief detour: WTF is ECDH?

Often abbreviated as ECDH, Elliptic Curve Diffie-Hellman is a protocol unto its own. It combines two main building blocks. The first involves the use of elliptic curves to form asymmetric key pairs, each of which is unique to each user. One key in the pair is public and available to anyone to use for encrypting messages sent to the person who owns it. The corresponding private key is closely guarded by the user. It allows the user to decrypt the messages. Cryptography relying on a public-private key pair is often known as asymmetric encryption.

The security of asymmetric encryption is based on mathematical one-way functions. Also known as trapdoor functions, these problems are easy to compute in one direction and substantially harder to compute in reverse. In elliptic curve cryptography, this one-way function is based on the Discrete Logarithm problem in mathematics.The key parameters are based on specific points in an elliptic curve over the field of integers modulo some prime P.

When someone knows the starting point (A) in the above image showing an elliptic curve and the number of hops required to get to the endpoint (E), it’s easy to know where (E) is. But when all someone knows is the starting and end points, it’s next to impossible to deduce how many hops are required.

As explained in an Ars article from 2013:

Let’s imagine this curve as the setting for a bizarre game of billiards. Take any two points on the curve and draw a line through them; the line will intersect the curve at exactly one more place. In this game of billiards, you take a ball at point A and shoot it toward point B. When it hits the curve, the ball bounces either straight up (if it’s below the x-axis) or straight down (if it’s above the x-axis) to the other side of the curve.

We can call this billiards move on two points “dot.” Any two points on a curve can be dotted together to get a new point.

A dot B = C

We can also string moves together to “dot” a point with itself over and over.

A dot A = B

A dot B = C

A dot C = D

…

It turns out that if you have two points, an initial point “dotted” with itself n times to arrive at a final point, finding out n when you only know the final point and the first point is hard. To continue our bizarro billiards metaphor, imagine that one person plays our game alone in a room for a random period of time. It is easy for him to hit the ball over and over following the rules described above. If someone walks into the room later and sees where the ball has ended up, even if they know all the rules of the game and where the ball started, they cannot determine the number of times the ball was struck to get there without running through the whole game again until the ball gets to the same point. Easy to do, hard to undo. This is the basis for a very good trapdoor function.

READ MORE HERE