Encrypt correctly! Why messengers won't protect the privacy of your correspondence.

[Jollier]

End-to-end encryption (E2EE) is considered a panacea for persistent attempts by hackers and law enforcement agencies to access online correspondence. The meaning of E2EE often boils down to the fact that the keys are stored only on the devices of the interlocutors and do not get to the server ... but this is not entirely true. Let's see how things really are with E2EE, using the example of popular instant messengers.

Encryption in messengers​

I was prompted to write this article by the study Obstacles to the Adoption of Secure Communication Tools (PDF). As its authors found, "the vast majority of survey participants do not understand the basic concept of end-to-end encryption." Simply put, people usually choose messenger with their heart, not their brain.

To begin with, E2EE has its own characteristics in each messenger. At Signal, it's almost exemplary. WhatsApp is formally the same as Signal, except for one very important point: changing the WhatsApp subscriber's main key does not block sending messages to him. The maximum you can enable useless notification (which is disabled in the default settings). In Viber, end-to-end encryption is inactive by default, and it only appeared in the sixth version. In Telegram, E2EE is also used only in secret chats, and they are implemented in a rather strange way.

The conflict between Roskomnadzor and Telegram generally created an excellent advertisement for the latter. Ordinary users now consider Durov's creation a real thorn in the back of the special services (or a little lower than it), which cannot do anything with the bulletproof innovative service. Telegram fans compare it to Signal and claim the superiority of the former.

However, there are no miracles in cryptography, and especially in applied ones. Many mathematically beautiful ideas turn out to be hopelessly flawed by implementation, when convenience and control are put above security and privacy (and this is almost always the case).

Initially, messengers used the OTR (Off-the-Record) protocol. It uses AES symmetric encryption in CTR mode, DH key exchange protocol, and SHA-1 hash function. The AES-CTR scheme provides so-called "controversial" (in a good way) encryption and the ability to deny the authorship of the text if it is intercepted. You can always refer to the fact that the intercepting traffic himself changed the ciphertext so that it corresponded to another decryption variant of the same length. For example, instead of “go for bread” it turned out “poison the queen” - technically it is possible, and such a property is specially incorporated into the algorithm.

The OTR protocol authenticates the interlocutors and encrypts the correspondence between them. It is secure as long as the parties to the conversation regularly check each other's public key fingerprints and resist attacks from other vectors (including social engineering).

The main disadvantage of OTR is that after sending a new key, you need to wait for confirmation from the interlocutor. If he is offline, then communication will be temporarily impossible. One solution was the Double Ratchet (DR) algorithm, developed five years ago by Trevor Perrin and Moxie Marlinspike at Open Whisper Systems. Today DR is used in Signal, WhatsApp, Viber and many other messengers that support end-to-end encryption by default or as a standalone option (secret chats).

A simplified diagram of the Double Ratchet algorithm (source: signal.org). Alice and Bob start a session by exchanging public keys

End-to-end encryption​

The E2EE scheme uses a combination of public and private key cryptographic systems. It is obvious in general terms and rather complicated at the level of detail. It uses a lot of interconnected keys, some of which necessarily end up on the server and, moreover, must be uploaded to it before the start of the correspondence, so that it can be started at any moment. Let's take a closer look at it.

You probably know the beginning of the scheme, since it is standard for all asymmetric encryption systems - a key pair is generated. This is necessary because cryptosystems with one key (like AES) are too difficult to use in correspondence in their pure form. They would have to somehow organize a secure channel for transmitting the key (for example, meet in person), and then do it again each time it is changed.

Here everything is as in the usual PGP: there are two interlocutors (Alice and Bob), each of whom generates his own pair of keys. They then exchange public keys, keeping their paired secrets a secret. Public keys are transmitted over an open channel (that's why they are public, let them intercept them for health) and serve two purposes: they allow you to encrypt a message and verify its signature. Accordingly, the secret keys are used to decrypt and generate the signature.

The term "message" is used here in a broad sense. A message can be text, media file, or service metadata exchanged between the messenger and the server. Some of this data contains timestamps, client application state, and new keys.

Such a cryptosystem somehow works in e-mail, since it is a service for delivering individual encrypted messages of arbitrary length. Using it, the interlocutors do not have to be online at the same time. All messages are accumulated on the server and downloaded from it on demand after the user is successfully authorized. Decryption occurs locally using secret keys that are not transferred anywhere. Mail with PGP is popular, but it is far from perfect. Why? See Alice and Bob in PGP Country.

Unfortunately, in its pure form, the asymmetric encryption scheme is also not suitable for instant messengers, since these services are focused on intensive online correspondence in the form of a chain of short messages. They should be displayed in a strictly defined order, and the interlocutor can be offline at any time and disrupt the structure of the dialogue.

Also, encrypting many short messages with one key is a bad idea. In just a day of correspondence, hundreds (if not thousands) of them are created. In many messages, the amount of ciphertext is minimal and predictable (smiley, sticker). They also have standard headers that make cryptanalysis easier.

The peculiarity of correspondence in messengers is that, due to typical metadata, an attacker can intercept a large amount of predictable ciphertext in a short time. Its lion's share will correspond to the well-known plaintext. If it is encrypted with one key, then with a successful attack, all previously written messages, and even those that the interlocutors write in the future, will be compromised.

To prevent this from happening, messengers provide such properties as forward and backward secrecy. They imply the inability to read messages sent earlier and written in the future, having only the current encryption key in hand. For this, multilayer encryption is used with the transition from asymmetric to symmetric cryptography and additional keys with different lifetimes.

Diffie, Hellman! Give three!​

It is known from open documentation that in Telegram, authenticated key distribution is provided by the classic Diffie-Hellman (DH) protocol. It creates a bridge between asymmetric (RSA) and symmetric (AES) encryption, making it possible for a certain number of interlocutors to conduct encrypted correspondence, transferring only public keys over an open channel. For this, session keys are generated in it, which are a shared secret or a shared ephemeral key. It is calculated based on the private key of one interlocutor and the public key of the other. Ephemeral keys are authenticated with long-term public keys.

In DH, the transmission channel may not be protected from eavesdropping (passive surveillance), but must be protected from spoofing attacks. If the attacker can spoof traffic (perform an active MITM attack), then the whole scheme goes to hell.

Therefore, for its Signal messenger, Open Whisper Systems uses the triple Diffie - Hellman transformation method X3DH with Curve25519 (Bernstein elliptic curve for fast DH) or X448. X3DH uses HMAC-SHA-256 and AES-256 as other cryptographic primitives.

Extended Triple Diffie - Hellman establishes a shared secret between two parties that mutually authenticate each other based on public keys. Additionally, the keys are verified immediately after the session is established and before the start of message transmission. This minimizes the risk of MITM attacks, making them very complex.

There are four types of keys used in X3DH, three of which are constantly changing:

• IK (identity keys). Secret keys, which are created once and serve as the basis for the formation of all the rest;
• EK (ephemeral key). An ephemeral key that is needed to verify the identity of the interlocutor (without disclosing the true one);
• SPk (signed public key, signed proof of knowledge) is, in fact, an ephemeral key signed with a secret. Usually, in instant messengers, it changes with a frequency from one day to a week. Sometimes, instead of the SPk lifetime, the number of messages is specified, after which it changes;
• OPK (one-time public key) is a one-time ephemeral key. It is created by the sender before establishing a communication session and is deleted immediately after a successful handshake.

Enigma's legacy​

Changing auxiliary keys in X3DH is performed using the Double Ratchet algorithm. It replaced OTR and introduced the concept of a chain, or pool, of keys. In case the interlocutor is offline, the OPK pool will be created. Several one-time ephemeral keys are uploaded to the server in advance and consumed as they communicate. This allows the server to receive encrypted messages by authenticating the sender with a new key pair, even when the recipient is offline. If the OPK pool is exhausted, then the server uses a spare EK.

The name "double ratchet" refers to the design of the Enigma cipher machine with cogwheels, which eliminated backward movement and reuse of previous values. The digital analogy is that DR is used to generate new ephemeral keys that encrypt the next message (or a small portion of messages). At the same time, ephemeral keys are guaranteed to differ, do not repeat the previous ones, and cannot be predicted in a reasonable attack time.

X3DH is based on the TextSecure protocol, which was later renamed Signal. In pure or slightly modified form, the Signal protocol is used in the messenger of the same name, as well as in WhatsApp, Viber and others. Developers can give the protocols their own names, but in fact it is still the same X3DH with a varying set of hash functions, PRNGs and other cryptographic primitives.

Group chats problem​

The organization of group chats in instant messengers is discussed in detail in the latest article "More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema" (PDF). I will cite the main conclusions from it.

Our systematic analysis revealed that communication integrity (represented by the integrity of all messages) and group affiliation (defined by the ability of group members to control them) are not end-to-end protected. In addition, we have shown that backward secrecy (a key security property) is not preserved when using the Signal protocol for group chats.

Explanation: The cornerstone of end-to-end encryption is authenticated key distribution using the classic or strong DH protocol. It only works for two interlocutors who share a secret. It is expected that DH messengers are not used in group chats, and the messaging structure in them is devoid of basic cryptographic properties.

Encryption in group chats. A - sender, B - recipient, G - user group

The authors show what manipulations a server controlled by an attacker can perform in group chats due to the absence of E2EE in them. They conducted their research on the example of Signal and WhatsApp, but one can hardly expect that other instant messengers have some elegant solution to this problem.

Telegram oddities​

With Telegram, everything is covered with a veil of secrecy. There is only partial information about the MTProto 2.0 protocol. Its external audit was not performed, and Telegram's open source model is used in a highly distorted form and solely for marketing purposes. Below I will explain why I think so.

Judging by the official description, all undelivered messages are temporarily (hopefully) stored on Telegram servers, which are often scattered around the world and combined into a virtual cloud. They synchronize with each other in order to organize and deliver messages to one or several (in the case of a group chat) interlocutors in a certain order as soon as they appear on the network. Therefore, encryption is divided into two stages: on the client - server and server - server sections. This is a common scheme, but the strange thing about it is that a direct client connection is never used at all.

In Telegram, traffic is transmitted through servers even when a secret chat is opened, for which it would be more logical to make a P2P connection. The conclusion suggests itself that without the constant use of Telegram servers, communication in this messenger does not work at all. Other messengers can use their servers only at the initial stage - to match the current IP addresses of the interlocutors and establish a direct connection between them. Telegram can't do that, and it looks a hell of a lot like MITM by design.

For some reason, all the arguments about the resistance of MTProto 2.0 revolve around the fact that the DH algorithm reliably protects against interception. This is not true. The Diffie-Hellman algorithm is just vulnerable to a MITM attack. Moreover, in the case of Telegram, it is likely further weakened at the PRNG level.

The problem is that the Telegram client app is guided by a very vague entropy estimate. Instead of generating pseudo-random numbers locally and filtering out high-quality prime numbers, the client requests them from the server. What kind of PRNG is used on the server, how good prime numbers it generates, and whether there are mechanisms on the server to selectively send primes with certain properties to individual clients - unanswered questions. The client application only checks the sent random number, and a simplified one, since the smartphone simply does not have enough computing resources for a thorough test of prime numbers in a reasonable time.

Another common argument for Telegram security is open source. However, they lack the source code for the server-side, and the client-side code is usually irrelevant. Telegram repositories are updated with a long delay (except that the stripped-down web version is more or less live), and they always contain only old versions. It is not even possible to check whether what is being distributed as a ready-made distribution kit is actually compiled from the source.

Therefore, talking about the audit of the messenger is actually meaningless. While specialists have been digging in the old code for several months, a dozen new versions of Telegram will be released, where huge chunks of code will be rewritten. To make the entire encryption system vulnerable, it is enough to replace one byte - for example, one conditional jump.

The hackathons arranged by Durov will not replace the audit, since they do not prove anything. Their assignments create an artificial situation in which the attacker has only one encrypted message. In real life, there are no such restrictions, and there are many other vectors for an attack on a messenger.

One thousand and one vulnerabilities​

Signal is one of the few messengers whose protocol has passed an external audit (PDF). The report on its results is very voluminous, so I will quote the main conclusions in my translation.

Our analysis shows that the Signal [protocol] satisfies standard cryptographic assumptions and security properties. We found no major flaws in its design, which is very encouraging. In actual use of Signal, uncertainties remain. Therefore, it is impossible to tell if [the] Signal application always achieves its stated goals.

It should be recognized that the analysis of the message transfer protocol is an important stage of the audit, but far from the only component of security. Any messenger works in a real and highly vulnerable environment. Usually it runs on not the most recent version of Android, in parallel with hundreds of left-handed applications (some of which probably abuse permissions or even contain Trojan bookmarks), and the account itself is tied to a mobile phone number.

The huge gap is that verification codes come in SMS. They can be intercepted through a known vulnerability in the SS7 cellular protocol. So the attacker will gain access to all correspondence without knowing the encryption keys and without even trying to break into Signal / Proteus / MTProto / other security protocol. The messenger server will change the key itself and helpfully decrypt the last correspondence (at least undelivered messages). Even your sticker packs will be restored. The main thing is convenience, right?

Another gaping hole in the security model is push notifications. Without them, you will not know that you have received a message until you manually start the messenger. With them, you turn the push notification server into a legalized “man in the middle”. For example, for iMessage to work with notifications, it sends encryption keys to Apple's servers. They already perform user authentication and (at least) decrypt message headers. Restore Apple account on another device, and you will get everything as it was - up to correspondence and passwords from Wi-Fi. The situation is almost the same with Google and Microsoft servers. Or do you still believe in end-to-end encryption linked to the mobile number and the main account on the smartphone?

The problem of insecure key management and a large attack surface affects all instant messengers. WhatsApp, Viber and many others allow you to create copies of correspondence (including cloud ones) and do not encrypt metadata (and sometimes the fact of a conversation is more important than its content). Signal is doing a little better, but I do not consider it an ideal messenger for a number of reasons:

• First, Signal also uses Google's push notification service. Therefore, on a smartphone without Google services (for example, all Chinese models for the domestic market without GApps), it simply does not work.
• Second, Signal uses a private RedPhone server for voice communication.
• Thirdly, Signal (like many other messengers) allows you to open a parallel session on another device by simply scanning a QR code.
• Fourth, at HITBSecConf2017, they talked (PDF) about a number of conceptual problems with Signal and demonstrated a successful attack on it.

XMPP​

As you can see, it is difficult to trust third-party and even more proprietary messengers, even if they were recommended by Snowden, Assange and EFF. Therefore, some organize communication through their messenger - with open source and plugins. The OTR plugin is suitable for simple correspondence, but it does not support group chats. There are related protocols mpOTR and GOTR that add this feature.

One way or another, for collective communication it is more convenient to use the open XMPP (Extensible Messaging and Presence Protocol) protocol, which was previously called Jabber. XMPP translates to Extensible Messaging and Presence Protocol, which is a very succinct name. Openness means full availability of source codes. You can raise your XMPP server, not depend on anyone and not pay anything for it. There are also a lot of ready-made servers and clients for every taste - for example, the desktop Pidgin and Xabber for Android.

Extensibility implies the ability to transfer not only text, but also data of a different type, as well as the addition of different functions and encryption schemes. For example, it is easy to transfer voice messages, videos and files over XMPP, encrypting them using TLS or PGP if desired. Not so long ago, the OMEMO extension protocol was created on the basis of XMPP, which uses the same DR from Open Whisper Systems as in Signal and WhatsApp, but without other disadvantages of the latter.

Conclusions​

Modern messengers claim to support end-to-end encryption, but it often turns out that it is implemented with oddities. In addition, there are many other holes in their code that were left accidentally or deliberately. The latter is much more likely when you consider how much money and labor of professionals was invested in their development. I try to strike a balance between comfort and the habitual enjoyment of paranoia. I use different messengers (which are more convenient for my interlocutors), but I never conduct really private conversations through them. There are many open source alternatives for this. In addition to Xabber, I would recommend Android users to take a closer look at Conversations, a free XMPP client with support for OTR, OMEMO, openPGP, and SOCKS5.

xakep.ru