How secure is emoji-based verification?

In February, Riot 1.0 was released, which featured a brand new verification system for device keys. The Android and iOS versions of Riot also recently included the new verification system. Key verification is an important part of ensuring that encrypted messages are only read by the people whom you want to be able to read. With emoji verification, instead of comparing long incomprehensible strings of characters, as in previous versions of Riot, key verification can now be done by comparing seven emoji. The seven emoji are chosen from a pool of 64, chosen to be distinguishable from each other and describable with few words, with the goal that people using different platforms with different emoji renderings should still be able to verify each other. (Riot also supports using a short sequence of decimal numbers when verifying against other Matrix clients that are unable to show emoji.)

The astute reader will note that seven emoji chosen from a pool of 64 (repetitions are allowed) gives you a total of 64⁷ or 2⁴² total possibilities. But surely 42 bits (despite 42 being the answer to the ultimate question of life, the universe, and everything) isn't enough to verify a single encryption key, let alone two!? What's going on here?

The short answer is that it isn't simply verifying the encryption keys directly. Rather, the devices involved are negotiating a shared secret, and the emoji are used to verify the shared secret negotiation. The shared secret is then used by the devices to verify their device keys by way of a Message Authentication Code (MAC). You'll note that if you begin a key verification in Riot, cancel it, and then begin a new verification, then you'll see that the emoji are different each time. This is because the devices negotiate a new shared secret each time you do a verification.

So are 42 bits secure enough to verify the shared secret? Let's look at how it works in more detail.

Basic Diffie-Hellman

Suppose that Alice and Bob wish to verify their keys, and Mallory wishes to attack the verification process so that she can trick Alice and Bob into verifying her own keys. Let's first consider what happens if Alice and Bob simply perform an (Elliptic-Curve) Diffie-Hellman. Elliptic-Curve Diffie-Hellman, once the elliptic curve is established, simply consists of one message in each direction: Alice and Bob each generate a key pair, and send each other their public keys. They use their own private key and the other person's public key, do some math, and end up arriving at the same shared secret. An eavesdropper cannot discover the shared secret, as they only know the public keys, which is not enough to calculate the shared secret. But if Mallory can intercept and alter the communication between Alice and Bob, then she can replace their public keys with her own public key: when Alice sends Bob, Bob instead receives Mallory's public key, and similarly when Bob sends Alice his public key. Alice and Bob then complete the calculations using Mallory's public key, and rather than having a shared secret between the two of them, they each have a shared secret with Mallory. If they do not verify that the shared secret matches, then they will not know that Mallory has attacked their secret sharing.

Diffie-Hellman with a verified shared secret

In order to detect Mallory's attack on their communication, Alice and Bob try to verify that they have ended up with the same shared secret. They don't want to verify the entire secret, as that would involve comparing a long string, and verifying the secret directly would expose the shared secret to an eavesdropper. So instead, they take some sort of hash of the secret and compare some number n of bits from the hash in some way, say through the use of an authentication string generated based on those n bits. Now Mallory can't just sit in the middle and just send any key to Alice and Bob; she needs to make sure that when they compare the bits from the hash, they'll get the same result, even though the shared secrets are different. If the Diffie-Hellman is done in a way where one person (say Alice) sends her public key first, and then Bob sends his public key after he receives Alice's public key, then Mallory will need to send some key to Alice, and then she will need to try, on average, about 2^n-1 different keys to send to Bob before she finds one that has the same n bits of the hash. However, Mallory is able to do this before sending anything to Bob, so if n is small enough, Alice and Bob won't notice anything other than maybe a slight delay. If n is increased, it may increase the delay introduced by Mallory's attack so that it is noticeable, but then it means that Alice and Bob need to compare more bits, making it more work for them to verify since the authentication string that they compare will be longer.

Diffie-Hellman with a verified shared secret and hash commitment

At this point, we borrow an idea from ZRTP (by Phil Zimmerman (the creator of PGP), and others). Rather than just having Alice and Bob send each other their public keys, the exchange begins with Bob sending Alice a hash of his public key (and some other information). This is called a hash commitment. Alice then sends Bob her public key, and finally Bob sends Alice his public key. By having Bob send a hash of his key first (and by using a strong hash), this prevents Mallory from being able try different keys like she was able to before, because she now needs to find a key that not only results in a collision in the authentication string, but also has the same hash as the hash that Bob sent.

Let's look at what Mallory would need to do to attack the exchange, step by step. Bob sends Alice a hash of his public key. Mallory intercepts the transmission and can alter it or not; we'll take a look later on at whether she wants to modify it or not, and if so, how she would want to alter it. Alice receives the (possibly modified) hash from Bob, and sends Bob her public key. Again, Mallory intercepts the transmission. Mallory needs Bob to see a public key that she has a private key for, so that she can calculate a shared secret with Bob, so she creates a new key pair and sends the public key to Bob instead of Alice's public key. Now Bob sends his public key to Alice. Again, Mallory intercepts the transmission, and now needs to create a new key pair and send the public key to Alice. However, the public key that she sends must satisfy two criteria: first of all, the authentication string generated by that key pair with Alice's key pair must match the authentication string generated by the key that she send to Bob with Bob's key pair. And secondly, the public key must hash to the same value as the hash that Alice received initially. If Mallory did not modify the hash that Bob sent, then she is stuck trying to find a key that has the same hash, which if the hash is good, should be nearly impossible. So what Mallory should have done was to replace the hash that Bob sent with the hash of a key that she already knows. If she does a birthday attack, she may end up with more than one key with the same hash, but again, if the hash is good, this should be nearly impossible, so we will assume that she only has one key for that hash. Now Mallory has solved the problem of making her key match the hash that Alice received, but not the problem of making the authentication strings match. Just by chance, Mallory may have selected a key that produces the same authentication string on both sides; this has a 1 in 2ⁿ chance of happening. If the key that she has already selected doesn't produce the same authentication string, then Mallory is stuck, as she's back to the point of trying to find another key that satisfies the two criteria. So no matter how much computing power Mallory has (short of being able break the hashing algorithm), Mallory only ever gets one guess to successfully attack the secret exchange, and that guess has a 1 in 2ⁿ chance of being correct. So by sending a hash first, the authentication string can be much shorter while still giving good security (hence the name Short Authentication String).

So given that Mallory has a 1 in 2ⁿ chance of successfully attacking a key exchange, how good is that? As noted earlier, by verifying 7 emoji, we're verifying 42 bits, so Mallory has a 1 in 2⁴²=4,398,046,511,104 (4 trillion) chance of success, which is quite low for a single attempted attack. What if Mallory attempts multiple attacks at the same time? For example, if I did a key verification with every single person in the world (currently estimated by one site as 7.7 billion people), then how many attacks might be successful? Since each of the attacks is independent, this is known in probability as a Binomial distribution, which due to the numbers involved, is approximated using a Poisson distribution with rate μ=^{7,700,000,000}⁄4,398,046,411,104≈0.00175. For a Poisson distribution with rate μ, the probability of no successes is equal to e^-μ, so in this case, the probability that Mallory will have no successes is approximately e^-0.00175≈0.998. In other words, if I verify keys with every person on earth and Mallory tries to attack every one of the verifications, there is a 99.8% chance that none of her attempts will be successful.

Now, this is not necessarily the only way that Mallory can attack the key verification process, but this is the most interesting part of the verification method. We have included measures to protect against other possible attacks and we believe that it is secure. We encourage people to review the details of the verification process, and let us know of any potential issues. While the verification process has not been audited yet, we do plan on having it audited in the future, along with other parts of Matrix's end-to-end encryption.