Telegram’s Cryptanalysis Contest

It's far too easy for people outside crypto circles to see cryptography as a panacea. Inside crypto circles however, it's my impression that everyone lives with a slight unease that much of the math they rely on has unproven lower bound complexity, the majority of implementations in existence are horrific, and the key management and trust models we all depend on are terrible and obscured from the users view and understanding. If you pay attention, all the rock star cryptographers spend most of their time talking about trust, not algorithms and protocols.

Designing a simple and secure crypto protocol isn't actually that hard. There are mathematical pitfalls us mortals can't hope to understand, but if you trust and understand the primitives as black boxes, and have the right mindset when analysing protocols, you can still build very secure systems. I'm a casual crypto hobbiest, and still spotted the issues raised in the Telegram protocol as soon as I looked at the diagram presented in the article. None of these weaknesses are outside of a good programmers comprehension.

So why is a custom protocol a bad idea? The same reason it's a bad idea to go and reimplement any other protocol... that problem has been solved, why are you remaking it without a strong incentive?

There are examples of crypto being used by amateurs with success though. Bitcoin has multiple extensions, like deterministic hierarchical wallets, which are easy to understand and reason about but I know for a fact weren't designed by world class crypto-experts. In that case, there was a strong incentive. Asynchronous key splitting to ensure safe generation of vanity addresses by 3rd parties is another example. Nobody should say these solutions aren't innovative and useful.

In some of the security classes in school some of my teachers said it was better to use an open and trusted protocol than reinvent the wheel.

They cautioned against using a closed source or proprietary protocol because there was not way to "vet" the code. I trust industry vetted solutions over "hip" new solutions that arent open. I am not sure if Telegram is open or not.

Why isn't end-to-end encryption enabled by default? Why is not having end-to-end encryption an option at all?

(Did he really just argue that sha1 isn't broken? ohmy)

Right, but you still include the sha-1 of the plaintext in your outgoing message, which is (IIRC) generally considered bad practice because it leaks information about the plaintext.

So, you have a great system and cryptographers are giving you free advice on how to make it even better, why aren't you taking it? Are they wrong?

The message integrity protection this system describes is not up to modern standards. The system seems to use SHA1, which is a fault for a new system (no new system should use SHA1), but that's not the biggest problem; the biggest problem is that the SHA1 digest of a message is not an authenticator of that message, because an attacker can generate the same digest given only the contents of the message. Your FAQ makes a claim that is simply false when it says that the SHA1 of a message is a MAC. It simply is not. Moreover, the process of using a secure hash to generate a MAC isn't simple. HMAC-SHA1 and SHA1 are not comparable functions; HMAC-SHA1 goes through a series of elaborate steps to remediate vulnerabilities that come from trying to use SHA1 directly.

AES-IGE is an anachronism. Candidly: most of the Internet crypto practitioners who looked at this system learned about IGE for the first time because you decided to use it. IGE is a block cipher mode that was designed in 1977 and forgotten about in 1978. It's so archaic that academic cryptographers joke about how many times it has been reinvented and then rebroken. The last time your cryptosystem was discussed on HN, I provided a link to a thread in which Jutla laid out a simple, devastating attack on the mode in ASCII text in a mailing list post. You didn't respond.

Your use of RSA seems naive and ineffective. Your system "resists" MITM attacks by "allowing" clients to trust servers you operate. No other modern secure messaging protocol has this characteristic. Every OTR user in the world runs software that was designed not to trust central servers. Not only that, but the technical attributes of your RSA usage appear incompetent. RSA padding is not optional; Nate Lawson has argued for years that RSA "padding" should be renamed "armoring" for exactly this reason: because developers like those on your team assume that it is a minor detail. It is not. 80% of the RSA implementations on the Internet are insecure because they use the default padding (PCKS1v1.5) which was carefully designed (in the 90s) to resist attacks, but missed some. You use ad-hoc padding.

I don't understand why any professional in the world would spend any time on your contest. Moxie Marlinspike's response to that contest was devastating: he laid out a comically broken messaging protocol, one no professional would ever knowingly use, and showed that your contest rules would make that broken system survivable. Your contest appears to be a cynical attempt to prey on the misconceptions of uninformed users.

You have deliberately chosen the NSA as your adversary in your promotional content. You have deliberately chosen to give yourself no margin of error in designing this system. You've deliberately chosen a problem domain that requires profound trust in your team. You are not living up to the constraints you've set for yourself. I fear that the damage you've done to your project may be unrecoverable.

First, SHA-1 should be used with the HMAC construction. HMAC is very easy to implement, see RFC 2104. Your developers can do it in a day. You can also use Keccak instead, it does not require HMAC, and there is a version with 224-bit output.

Second, I don't see a problem with IGE. Despite others calling it "ancient," it was proposed at about the same time as CBC. There is a proof of security against adaptive chosen plaintext attacks. Nonetheless, you could use a more studied mode like CTR, but most importantly use the encrypt-then-MAC composition, i.e. AES-CTR + HMAC. (An authenticated mode would be best, but GCM is not easy to implement.)

Finally, the DHKE really must be authenticated. Everything else depends on it, since the key (auth_key) is not ephemeral. The least complicated way to authenticate is the Station-to-Station protocol.

Best of luck.

"Secret Chats do not use mandatory authentication via a third-party or pre-shared information. We may later add an option to forbid Secret Chat initialization, unless the user has confirmed the key (using a QR code, NFC, etc.) for advanced users."

"Forward Secrecy is available for Secret Chats, but requires user action at the moment — it can be achieved by deleting secret chats and creating new ones, or logging out periodically (since logging out kills all secret chats)."

Unless I'm missing something, their recommended way of getting forward secrecy opens users up to man in the middle attacks, since if users are setting up new secret chats often enough to protect against an attacker obtaining their keys and decrypting past messages they're not going to be able to confirm the keys match every time.

First, the KDF really bugs me. Essentially, 128 bits of the data that's used to generate the AES key is derived from msg_key, which is the SHA-1 of plaintext+some_other_jazz. Also, only some of the auth_key's bits are used, along with the plaintext-dependent msg_key, as food for the KDF. What this could mean is that you're really diluting your effective keyspace. (Partially) deriving a key from the hash of public data doesn't smell like good crypto-hygiene, and intuition tells me there's the potential for leaking key bits if I query it enough, or collect a lot of ciphertext traffic.

Second, there's no integrity checking going on with the ciphertext, so I could easily ask the server to decrypt anything; don't give me that freedom, because maybe I can fool you into doing something worse. Also, if you were doing Encrypt-then-MAC, like any good boy should, you'd save yourself from wasting decryptions on bogus ciphertext. This is one reason I can't buy the performance-driven reasoning for using Methuselah's hand-me-down modes; modern modes are safer and likely faster. It's akin to paying more for used, squeaky parts, when you can pay less for new, more efficient parts.

To a cryptographer, the one thing we learn early in our careers is that it doesn't pay to be different when it comes to choosing primitives and protocols. When we find things that work, and have earned their bones, we recycle them in new designs and continue building upon the confidence we have in them by carrying on with cryptanalysis, building and breaking proofs, and so forth. There are no bonus points for those who deviate, because, really, the battle we're losing isn't that of the cryptography itself; rather, it's the way we implement it and the way we interface it. Implementation is the friend of no one; do not make it harder for yourself.

I've been a little candid, I know, but mostly because to many of us, what we're looking at is a Goldbergian gauntlet of decision-making that leaves us asking ourselves, "Okay, they took the long way home, but did they get there?" If there's a gain, I'm not seeing it, and the defense isn't leaving me optimistic that we will.

With all sincerity, and admiration for your desire to help others reap the benefits of cryptography, if enough of us tell you that there's a better, safer, and quicker way to getting this right, would you lend us an ear?

- Justin

P.S. I'm okay with being wrong, but I'm more concerned with helping you get things right.

*I have a toddler.

The contest limitations rule out most of the likely attack vectors for breaking the protocol in the real world. It's like saying "Our bank vans are 100% secure. Just try stealing money from them without puncturing our tires or bribing one of our employees."

[0] - https://news.ycombinator.com/item?id=6936949

Which is what it's about: cryptography is mostly about trust with a bit of math thrown in. If you can't trust that it won't be broken (see: all the issues 'moxie and 'tptaeck bring up for an example) then it shouldn't be used.

The crypto has problems, but they aren't exploitable under the very limited conditions set by their contest.

No, that's not why people are upset at all.

People are upset because whether or not someone has been able to break their system under the constraints of the contest means almost nothing.

Did you even read the article?

This does not make it secure in the slightest, as the terms are set up specifically to exclude most of the attacks that are used in crypto validation these days. See - http://www.thoughtcrime.org/blog/telegram-crypto-challenge/

  This oak is probably diseased. It has discolorations on 
  some of the leaves and the bark is much looser than 
  normal. I think it should be thoroughly investigated or 
  perhaps just cut it down to be safe.

  Well, if the algorithm is so broken then it should be 
  trivial to break it even with their limitations.

[1] Limitations include: not being allowed within 200m of the house.

Well, if that piece of steel can so obviously not hold those 10000 tons of concrete given the corrosion over the next 30 years, it should be trivial to break it even with their limitations.

It has been shown that SHA1 is broken - it's just that experts in the field tend to be able to know such things before the bridge has collapsed, but that does not mean that they can demonstrate it to anyone who doesn't want to study the theories behind their assessment without building the bridge and waiting 30 years.

This is the critical sentence from the article - "If you want to show that a system is secure, give the adversary as much power as possible, and if they still can’t break it, the security is good."

This is at the root of modern crypto systems, and without it a system is considered broken.

It may be that within the rules of the contest, breaking one message is non-trivial. That doesn't mean that I couldn't (for instance) collect and analyse multiple individual's traffic over time, or find a way to alter data in-flight, both of which are specifically ruled out of the contest.