Telegram is an encrypted instant messaging app for iOS and Android devices. Obviously, I wouldn’t mention it on this blog if its crypto was perfect. In fact, it’s far from perfect. It’s almost horrifying.
This seems like a good thing. The massive award should get people looking for bugs in their code.
Why is the contest no good? To understand why, we need to learn how security is defined and analyzed in cryptography. This is a good opportunity to explain it, so that’s what I’ll do in the next section. If you already know what IND-CPA and IND-CCA mean, you can probably skip over this section.
In cryptography, we’re always reasoning about “security”, so we need to give the word “secure” a rigorous definition. This is done by defining security with respect to the capabilities of an adversary – a person (or computer) trying to break the system.
Over the years, cryptographers have given names to various types of adversaries. We’ll go over the important ones in the next three sections.
Let’s start out by defining the adversary as having access to the system’s ciphertext (encrypted data), and let’s give them the full plaintext for a few ciphertexts. They have access to the ciphertexts and the plaintexts for some of them (these plaintext-ciphertext pairs are called known plaintexts), but they can not interact with the system in any way. We’ll call this model the Known Plaintext Attack (KPA).
As you could have probably guessed, this model is too weak. A system secure only in the KPA model is missing some very important properties that we’d like a “secure” system to have.
The adversary is given a ciphertext and told that it’s either the encryption of “YEA” or “NAY”. Assuming the adversary is not given the encryption of “YEA” or “NAY” as one of the known-plaintext pairs, they can not figure out whether the ciphertext they have is the encryption of “YEA” or “NAY”. That’s good, a KPA adversary can’t break this system.
This isn’t just a theoretical ability. More often than not, you can make the system encrypt a message of your choice. One real example is a TLS connection between a web browser and a google.com. If another website, say bing.com, includes an image on one of its pages from google.com, the browser will encrypt the image URL and send it to google.com.
That’s the key point here: We give the adversary in our model more power, and this gives us a stronger definition of security. If you’re building a tank, you don’t test its armor with small arms fire, you shoot it with an RPG.
In the last section, we saw that if the adversary could encrypt messages of their choice, they could break a system that’s only KPA-secure. So what if we let the adversary make the system encrypt arbitrary messages as well?
This is a much more reasonable security model, but it’s still not good enough. A real adversary can modify ciphertexts.
Suppose the transaction orders look like this:
Encrypted, one might look like:
The encryption (CTR mode) is malleable, so a real adversary can change the last part (highlighted with stars):
Because of the change, it will be decrypted to:
So, by changing one of the ciphertexts, the adversary can redirect the money that Alice was sending to Bob to Eve. Obviously, we need to strengthen our security model even more. We have to be sure that even when an adversary can modify ciphertexts, the system is still secure.
This brings us to the last security model we will discuss, called the Chosen Ciphertext Attack (CCA) model. In this model, the adversary is also allowed to choose ciphertexts and gets to see their decryptions. The adversary can essentially do anything they want besides telling the system to decrypt the actual ciphertext they are trying to decrypt. The adversary can modify messages in transit, drop messages, replay messages, etc.
Okay, enough crypto theory. Back to the real problem: Telegram’s contest. The contest works like this:
The problem should be clear now: Telegram’s contest does not give the adversary enough power. The adversary doesn’t doesn’t get known plaintexts, can’t choose plaintexts, can’t choose ciphertexts, can’t modify network traffic, or anything like we covered in the previous sections. The contest barely fits into the known plaintext attack (KPA) model.
So how good is Telegram’s crypto?
- They use the broken SHA1 hash function.
- They include a hash of the plaintext message in the ciphertext. Essentially, they are trying to do “Mac and Encrypt” which is not secure. They should be doing “Encrypt then Mac” with HMAC-SHA512.
- They rely on an obscure cipher mode called “Infinite Garble Extension.”
- Some really weird stuff about factoring 64-bit integers as part of the protocol.
- They do not authenticate public keys.
What should Telegram do?
They should switch to an existing well-studied protocol like the one used by TextSecure. They need to bring in a real cryptographer to audit their design (and design process), and they need to make sure the programmers they’ve hired are qualified to write crypto code (most programmers are not).
Here’s a summary of their response and my replies.
Telegram’s reason for creating their own protocol is as follows:
In other words, they designed their own crypto for speed and reliability. I don’t see how encrypt-then-HMAC is incompatible with reliability. As for speed, encrypt-then-HMAC-SHA1 would be faster, and encrypt-then-HMAC-SHA256 would not be significantly slower. @zooko points out that the BLAKE2 hash function is as fast or faster than SHA1, and much more secure.