Davidov March 12, 2015 at 17:03

Telegram attack in 2 ^ 64 operations, and why the supervillain does not need it

Transfer

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

Messages sent to users outside of a secret chat are stored on Telegram servers in such a way that they allow the company to view the contents of 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 including 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 come back to this a bit later.

Secret chat

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

In essence, telegram end-to-end encryption is the Diffie-Hellman protocol for selecting a key, and then encryption using a modified AES scheme . End-to-end encryption authenticity based on truncated SHA-1a hash of the shared secret key, which is displayed graphically as a fingerprint. This print 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, engineers from Telegram at least use good recommendations and requirements for the values of the Diffie-Hellman parameters.

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

It’s important to understand that this is a nightmare of crypto usability. When I meet any of the Telegram users I ask how they organize the secret chat authentication; and as a rule, the answers bring only disappointment. Usually, users simply send a screenshot of the fingerprint directly through a secret chat, which they try to install. For an attacking person in the middle, automatically replacing a picture with a fingerprint is a completely trivial task.

Attack 2 ⁶⁴

Well, let's say now you are doing everything right, and compare fingerprints in person. And also do not make mistakes when comparing, because you are extremely careful.

The first observation is that despite the fact that the common secret is in the space of 2048-bit primes, authentication that prevents a person from being attacked in the middle uses only a 128-bit fingerprint, which is visually compared. If it is possible to carry out an effective enumeration of the parameters of the HH, then the person in the middle could forge a print.

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

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

At the same time, if the attacker uses social engineering so that the second user starts a secret chat on his own initiative, then he has much more freedom of action. That is, now the attacker selects two public keys (A and B). The 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 an 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 the values of both m1 and m2 for different shared secrets allows the attack of "birthdays" to search for collisions. Instead of searching in space 2 ¹²⁸ , the attacker goes over 2 ⁶⁴ values of 'm1' and 2 ⁶⁴ values of 'm2', the success rate is about 50%.

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

From the implementation point of view, at first glance it seems that the attack still requires excessively high resources.
One of the misconceptions is that exposing such a large value in search of a collision is too difficult from a computational point of view, since 2048-bit primes have to be exposed. In fact, the attacker only needs to perform squaring and modulo division at each step.
Another misconception is the memory complexity of 2 ⁶⁴. This is also not true, since there are parallel and low-memory attacks of “birthday” attacks, and there are various compromise 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 much memory.

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

Valuation attack 2 ⁶⁰ operations - www.schneier.com/blog/archives/2012/10/when_will_we_se.html
GPA SHA computing performance - gist.github.com/epixoip/c0b92196a33b902ec5f3 www.geforce.com/hardware/desktop-gpus/geforce-gtx-980/buy-online

Telegram answered the description of this attack with an article where they evaluate the attack in trillion dollars.

Why doesn't the supervillain 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 located on Telegram servers with a bunch of metadata, who communicates with whom, as often, with phone numbers and a sufficient number of saved chats. If the attacker gained access to the Telegram servers, then the received data is already very good, and there is no need to eavesdrop on secret chats. No, seriously, isn't that the kind of information the supervillain is hunting for?

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

And one more thing. Let's say people use private messengers on the phone to avoid the vulnerable means of communication 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 eavesdropped and hacked, users can be connected to fake base stations, and operators can also be hacked (remember belgacom) or forced to cooperate. That is, if SMS is an authentication method, it is obvious that the Telegram account can be stolen.

SMS attack also does not require high technology. If a supervillain attacks a foe ( frenimy is an enemy pretending to be a friend; translator's note), he can just lend a phone (or a SIM card if the phone is password protected) for a few minutes and steal an account. Moreover, Telegram saves and displays old messages. From a stolen account, a supervillain can use social engineering to force a contact to start a new secret chat so that he tells some secret.

How to fix Telegram

On December 1, Telegram announced forward secrecy, this feature adds key rotation inside the installed channel. But this does not hinder the described attack of a man in the middle.

There are a few things to fix on Telegram, and here is a list of the most critical ones.

First, chats (including group chats) must have end-to-end encryption by default. This will eliminate human errors 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 go from authentication at every chat to cryptography with public keys to identify users. It makes no sense to authenticate secret chats with a session key. Instead, each user should have one or more public keys that select the session key. Users confirm each other once, and all. 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 ordinary chats. Another account authentication scheme is needed, and as soon as possible, even passwords with two-factor authentication. By the way, this vector is most likely for real attacks without hacking Telegram servers, and even an ordinary villain can do this, it is not necessary to be a supervillain.

And finally, for the sake of privacy in Telegram, you need to make communication possible without the need for an address book and a phone number in order to allow you to use Telegram anonymously; this is now impossible.

@Serzhenko notes that at the end of 2014, nicknames appeared on Telegram. This eliminates the need to know the phone number of the interlocutor, but at the same time, authentication is still carried out by the phone number, and this information is stored on the servers. Note by the translator.

Telegram competition

At the moment, there is a competition with a prize of 300 thousand dollars for breaking end-to-end encryption. Can I use the described attack? The fact is that the competition itself is organized in such a way that it does not allow an “man in the middle” attack to be arranged. If the conditions of the competition allowed it, then the attack would have a chance. Well, the truth is, most likely, calculations will cost more than a 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 .

Acknowledgments

Many thanks to @odiumeh for cooperation, advice and support, as well as to other people to whom I buzzed all my 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 bothered 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 errors found and inaccuracies in the translation, please write in a personal.

Tags: