Telegram attack for 2 ^ 64 operations, and why the supervillain doesn't need it

Last spring, Juliano Rizzo ( @julianor ) and I came up with a cryptographic attack on the “secret” chat MTProto from Telegram, which can be done in approximately 2 ^ 64 operations. The attack is carried out from the position of a person in the middle on the Telegram servers.

Messages sent to users outside the secret chat are stored on Telegram servers in such a way that they allow the company to view the contents of the messages and transfer them to third parties. This always happens if conversations can move between devices (for example, between a phone and a computer). These chats are not private, that is, users must be very careful not to accidentally send incriminating information or pictures without the inclusion of a secret chat. Group chats also do not use ent-to-end encryption at all. Moreover, when someone enters such a chat, he immediately gets access to previously sent unclassified messages. We will return to this later.

Secret chat

The Telegram slogan reads as “taking back our right to privacy”, and means secret chat with end-to-end encryption. This part was easily cracked during the first Telegram compromise competition with XOR keys issued by the server.

In fact, the end-to-end encryption “Telegram” is the Diffie-Hellman protocol for choosing a key, and then encryption using the modified AES scheme. The authenticity of end-to-end encryption is based on a truncated SHA-1 hash of a shared secret key, which is displayed graphically as a fingerprint. This imprint must somehow be conveyed and compared visually. If you are a cryptographer, then I am very sorry that you had to read this; I understand how it torments and contradicts numerous developments and canons. At least the engineers from Telegram at least use good recommendations and requirements for the Diffie-Hellman parameter values.
')

The fingerprint that two users must compare is obtained from the Diffie-Hellman key hash. That is, the common key has a space of values of 2 ^ 2048, the SHA-1 hash function produces a 160-bit hash. The 160-bit hash is clipped to 128 bits, which are used to get an imprint (see figure).

It is important to understand that this is a nightmare of crypto usability. When I meet someone from Telegram users, I ask how they organize the authentication of the secret chat; and, as a rule, the answers bring only disappointment. Usually, users simply send a screenshot of the print directly through a secret chat, which they are trying to establish. For an attacking person in the middle, automatic substitution of a picture with a print is a completely trivial task.

Attack 2 ⁶⁴

Well, let's say now you are doing everything right, and make a comparison of the prints during a personal meeting. And also do not make mistakes when comparing, because you are extremely attentive.

The first observation is that despite the fact that the shared secret is in the space of 2048-bit prime numbers, authentication, which prevents a person from attacking in the middle, uses only a 128-bit imprint, which is compared visually. If it is possible to carry out an effective search for DH parameters, then a person in the middle could forge an imprint.

The second observation is that in the standard protocol behavior a person in the middle should work with only a few parameters. From the side of the second user there are not so many ways to control the resulting shared secret.

In the classic scenario of an attack on HH, a person in the middle simply selects a separate shared secret for each user.

At the same time, if an attacker uses social engineering, so that the second user starts a secret chat on his own initiative, then he has a lot more freedom of action. That is, now the attacker chooses two public keys (A and B). A person in the middle can create two shared secrets M1A and M1B with different exponents m1 and m2, whereas earlier he had only the freedom to choose a shared secret with the first user.

This is the attack. The attacker enumerates the values of m1 and m2, which will give the same 128-bit fingerprint for M1A and M2A. The ability to search for values of both m1 and m2 for different shared secrets allows for the “birthdays” attack to search for collisions. Instead of searching in space 2 ¹²⁸ , the attacker goes through 2 ⁶⁴ values of 'm1' and 2 ⁶⁴ values of 'm2', the probability of success is about 50%.

In terms of complexity, an attack requires about 2 ⁶⁵ operations. In 2015, such complexity is unacceptably low. For reference, NIST declared SHA-1 obsolete at the end of 2012 and recommended using SHA-256 as a replacement. The “birthday” attack on SHA-256 will require about ^2,128 operations. So despite the high cost, the attack described above is quite feasible for a well-funded attacker.

From the point of view of implementation, at first glance it seems that the attack still requires excessively high resources.
One of the misconceptions is that the exponentiation of such a large value in the search for collisions is too heavy from a computational point of view, since 2048-bit prime numbers have to be exponentiated. In fact, an attacker needs to perform only squaring and dividing by module at each step.
Another misconception is the complexity of the memory in 2 ⁶⁴ . This is also not true, since there are parallel and birthday-free attacks that do not require a large amount of memory, and there are different trade-off strategies between the memory used and the time spent. We wrote code that uses the Pollard ρ-algorithm to search for collisions, which does not require a lot of memory.

In general, I would rate a full attack in the range of tens of millions of dollars in terms of infrastructure and electricity for a complete collision in a reasonable time. The attacker can also steal or rent existing infrastructure, such as a botnet or a supercomputer. In other words, everything fits into the budget of the supervillain.

Estimate of the cost of an attack for 2 ⁶⁰ operations - www.schneier.com/blog/archives/2012/10/when_will_we_se.html
GPU SHA computing performance - gist.github.com/epixoip/c0b92196a33b902ec5f3 www.geforce.com/hardware/desktop-gpus/geforce-gtx-980/buy-online

Telegram responded to the description of this attack by an article where they estimate the attack to be a trillion dollars.

Why does the supervillain not need this attack

Of course, an attacker can spend a lot of money in order to gain access to Telegram servers and even more money to carry out an attack, but let's be realistic, there are much simpler and much more profitable attacks.
All contact lists and regular chats are on Telegram servers with a bunch of metadata, who communicates with whom, how often, with phone numbers and a sufficient number of saved chats. If an attacker gained access to Telegram servers, the data received is already very good, and there is no need to eavesdrop on secret chats. No, seriously, isn't this the information the supervillain is after?

Now, if a supervillain really wants to intercept secret chats, he can expect the victim to just send a fingerprint through a new secret connection. Unfortunately, many users do. And since we are talking about a supervillain, he can intercept other communication channels that the user will try to use for authentication, for example SMS; the point is that the visual imprint cannot be verbally transmitted, since most of the clients do not show the imprint in readable form. The two prints are simply replaced by a supervillain, and until the next in-person meeting, users never know that their communication has been intercepted.

And something else. Suppose people use private messengers on the phone to avoid vulnerable communication tools provided by telecom operators. However, the only authentication system in Telegram is the SMS code.

We know that SMS is poorly protected, and we know that attackers very often use it. SMS can be overheard and hacked, users can be connected to fake base stations, and more operators can be hacked (think belgacom) or forced to cooperate. That is, if SMS is an authentication method, then it is obvious that a Telegram account can be stolen.

Attack SMS also does not require high technology. If a supervillain attacks a friend ( frenimy is an enemy pretending to be a friend; a translator's note ), he can simply borrow the phone (or the SIM card if the phone is password protected) for a few minutes and steal the account. Moreover, Telegram saves and displays old messages. With a stolen account, a supervillain can, with the help of social engineering, force the contact to start a new secret chat so that it will tell some secret.

How to fix Telegram

On the first of December Telegram announced forward secrecy, this feature adds key rotation inside the established channel. But this does not interfere with the described attack of a person in the middle.

There are a few things that need to be fixed in Telegram, and here is a list of the most critical ones.

First, chats (including group) should have end-to-end encryption by default. This will eliminate human error and information leakage. By the way, in Threema and TextSecure end-to-end encryption is already enabled by default.

Secondly, end-to-end encryption should move from authentication with each chat to public-key cryptography to identify users. There is no point in authenticating the secret chats with the session key. Instead, each user must have one or more public keys with which the session key is selected. Users confirm each other once and that’s it. And, by the way, in Threema and TextSecure all this was done several years ago.

Thirdly, user authentication is a very, very weak protection for a private messenger, and an attacker who can afford to intercept SMS can easily steal an account and use social engineering or view normal chat rooms. A different account authentication scheme is needed, and as soon as possible, even if passwords with two-factor authentication. By the way, this vector is the most probable for real attacks without hacking Telegram servers, and even an ordinary villain can do this, it is not necessary to be a supervillate.

Finally, for the sake of privacy in Telegram, communication must be made possible without the need for an address book and phone number to allow Telegram to be used anonymously; now it is impossible.

@Serzhenko notes that nicknames appeared in Telegram at the end of 2014. This eliminates the need to know the phone number of the interlocutor, but at the same time, authentication is still performed by the phone number, and this information is stored on the servers. Translator's note.

Telegram Competition

At the moment there is a competition with a prize of 300 thousand dollars for hacking end-to-end encryption. Is it possible to use the attack described? The fact is that the competition itself is organized in such a way that it does not allow to arrange a man-in-the-middle attack. If the conditions of the competition allowed it, then the attack would have a chance. Well, the truth is, most likely, the calculations will cost more than the prize; You can, of course, use crowd sourcing.

Readers, look for more bugs and vulnerabilities in MTProto, at least a few more should be.

Recommendations for users who need privacy

As a general purpose messenger, Telegram looks fine. But if you need privacy and privacy, then I would recommend something else. For example, Threema or TextSecure .

Thanks

Thank you so much @odiumeh for your cooperation, advice and support, as well as other people to whom I buzz all ears about this attack. Special thanks to Dhiru Kholia and Marsh Ray for their feedback.

useful links

Partial collision example

p = 0xc71caeb9c6b1c9048e6c522f70f13f73980d40238e3e21c14934d037563d930f48198a0aa7c14058229493d22530f4dbfa336f6e0ac925139543aed44cce7c3720fd51f69458705ac68cd4fe6b6b13abdc9746512969328454f18faf8c595f642477fe96bb2a941d5bcd1d4ac8cc49880708fa9b378e3c4f3a9060bee67cf9a4a4a695811051907e162753b56b0f6b410dba74d8a84b2a14b3144e0ef1284754fd17ed950d5965b4b9dd46582db1178d169c6bc465b0d6ff9ca3928fef5b9ae4e418fc15e83ebea0f87fa9ff5eed70050ded2849f47bf959d956850ce929851f0d8115f635b105ee2e4e15d04b2454bf6f4fadf034b10403119cd8e3b92fcc5b A = 31255283409627973717223000370765106922189476428506306750544086446550550889396 B = 112771494640069988074840580093805523312740220076402790935086113796930956685865 m1 = 1524456385 m2 = 2871128407 M1A = A2 * m1 mod p M2B = B2 * m2 mod p M1A = 0x894c450b654f0fba7eb0baf97f08cc0aa448a17a2773d5dfcd6827d119d5d910b9f8fa75e25cc23ad30aa819cdcae8e4b4a9f3551afbe37061f3a768b62507c1eb2d017a67d3433f69acec8a5cd2a73008c2f520c71a7cea269325dc8e5bf77778d6349d8db0ac64d7b362218d04bd0a0a0d2a8f8187c4df8f8aa2b177268a505fc8892bda722449a60fff1647601a505e0480af05b14ee5a613414ad3a4ea06d37c03d856e20c5156199bd382048f45e5c150321b8c354fb541946b501aeaf6af039acda9ecb871095f726cc20a920c4b3361cb5f40142fb6319e07667a0e587e49be5f0c7f13960fbc138c9b2c81ae0fff4364d041bfbbf66842d82aca7604 M2B = 0x6722b48e670f4d3c2a24019a9d18211ebbefa407fb94fa3e91bff416cf344d1a2e3bd62c43c92bb4b633586b8e11853faa609c2f474e92033bc0fc97e047e7ed4c2af54a75f7e4bbf08cf9854a478e485b358232aa886b701c5e5dc488335b757cfaf0eda87d5299b5385ca69bdbe758a0b99aa45d371bed4a576cfff4147d384e78ca245cd778d983168a3ebc55950c0203db61c67d903fe77b4879bc35e9529ff51dcbf24add97771a0538ed45d3ee7a269674ded42dc0c85546601485388b045f5196a18355d5a8579df69a06df1519f5bada66270691574b425b22cefa0f6d522394c60f6c5c568f3a16458c64d6dde8cea917cdacbc7fdf552dd7872ef7 SHA1(M1A) = 0xe20bf6722b0a44b7e0fca07bd6c55a74b378ad74 SHA1(M2B) = 0x5813a3521aa452a4a2fffc3ed6c55a74b378ad74 64-bits in common, d6c55a74b378ad74

Update

The O () notation disturbed people and was inappropriate; I also added a link to Telegram's answer about the cost of the attack.

Translator's Note

Thanks to HoverHell for proofreading the translation.

About all the errors and inaccuracies found in the translation, please write in a personal.

Source: https://habr.com/ru/post/252911/

All Articles