[TelegramApp]

The contest, as proposed by Pavel, while limited for the moment, does cover an important issue as far as our users are concerned. And the scope will naturally expand with time, should Telegram be invulnerable under the current conditions (see contest FAQ: http://core.telegram.org/contestfaq).

Quoting a post by Pavel here on HN: "Telegram will always be interested in creating incentives for the crypto-community to check its security and provide feedback. So if you are waiting for tools to try, e.g., a MITM on Telegram and get your $200К, please stay tuned. It's @telegram on Twitter." (https://news.ycombinator.com/item?id=6938987)

As for general critique of the protocol, please allow us to add a few vital corrections regarding the article (unfortunately, the author chose a platform that would not permit a direct comment).

> They use the broken SHA1 hash function.

SHA-1 isn't exactly broken. There is a theoretical paper from 2005 that describes a way to narrow down collision search from 2^80 to approx. 2^69 operations (http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersio...) with subsquent improvement to 2^63, but collisions won't help in the case at hand. In order to break the implementation in MTProto you would require generating a text with chosen SHA-1 (to our knowledge, this problem was not yet solved) — and even that wouldn't get one far, because of the server salt, session id and time.

More on our SHA-1 implementation here: http://core.telegram.org/techfaq#q-are-you-doing-encrypt-the...

and here: http://core.telegram.org/techfaq#q-why-do-you-use-sha-1-in-t...

> they are trying to do “Mac and Encrypt” which is not secure.

We are not doing this. We are doing this: http://core.telegram.org/techfaq#q-are-you-doing-encrypt-the...

> They rely on an obscure cipher mode called “Infinite Garble Extension.”

Yes, we do. The setup goes like this: http://core.telegram.org/techfaq#q-do-you-use-ige-ige-is-bro...

> Some really weird stuff about factoring 64-bit integers as part of the protocol.

This weird stuff can be pretty effective as part of our DoS-protection scheme.

Meanwhile, we've expanded our Tech FAQ with responses to most common questions concerning MTProto's robustness against certain types of active attacks:

http://core.telegram.org/techfaq#protection-against-known-at...

Thank you for your comments,

Telegram Team

[tptacek]

I'm worried that to people unfamiliar with modern crypto, the diagram of your protocol and the "technical FAQ" might sound credible or even convincing. But it is not.

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.

[kbenson]

Okay, here's an authority I can get behind on this debate, not being familiar enough myself to parse most of the criticisms for their veracity. I don't always agree with your political or economic take on a subject, but I've never seen anything but excellence in your technical breakdowns of a subject, especially cryptography (go figure ;).

80% of the RSA implementations on the Internet are insecure because they use the default padding

So, now that I've hopefully buttered you up enough, I'm hoping you have a reference to share, because if that's true, it's pretty damn scary.

[Smirnoff]

I hope Durov brothers are taking notes. Making a half-baked Facebook clone is not the same as making a fully-secured messaging system.

PS: These guys are still copying Facebook. Facebook released a messaging app, so these guys did the same. But, hey, Telegram is different because it uses MITM and it's "secure".

[11001]

"200% secure".

[DavidShahoumian]

> half-baked Facebook clone

It is better than Facebook in every possible way.

Have you actually ever used VK (both the site and the mobile apps)?

[Smirnoff]

Glad you asked. I used to use Vkontakte (and Odnoklassniki btw) in the past. Vkontakte has always been in the catchup position with "missing" or "out-of-blue broken" features on a surprisingly consistent basis.

Now, I won't discuss these missing/broken features here. You can look them up on their app's comments section. But I will leave you with one very important thing about privacy:

VK shows when you were online the last time. VK also shows you online if you login without an ability to turn it off! Great for stalkers and unfortunate for those who wouldn't want to receive unwanted conversations.

So I am very reluctant to trust someone, who really doesn't get privacy to build a messaging system with security and privacy in mind. Because we clearly view privacy differently.

[new_test]

> It is better than Facebook in every possible way.

Even if it were true, your statement still doesn't contradict GP's assertion.

[DavidShahoumian]

By that logic one could state that, for instance, Chrysler cars are "Ford clones" because Ford was the first manufacturer to become very popular and commercially successful.

[jaekwon]

> 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.

Curious, if the secret token comes after the message & there is proper delimiters to separate the message from the secret, where is the vulnerability?

Take a look at this link: https://blog.jcoglan.com/2012/06/09/why-you-should-never-use...

Am I correct to think that the example cited is bad? It appears that it would be a strong MAC because of the reasons that I cited.

[TelegramApp]

> 1. 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.

Please note that a message to be encrypted would not only contain the actual text sent, but also at least the server salt, session id, message sequence number, message length and precise time.

This complete data set could be theoretically obtainable only from either server or client memory, therefore the fact that an attacker has this kind of data implies that a successful attack had already taken place. Hence the question — why didn't that attacker take the auth_key right away?

On top of that, the present setup doesn't present any identifiable threats, because even if you could get a message with a given SHA1, you would still not know which message was really transmitted out of the possible matching set (or rather out of the 2^(L-160) messages for a message with the length of L bits).

Regardless of this fact, we do agree that strengthening this point would be logical in view of possible future developments in code-breaking. Thank you.

> 2. 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.

I'm afraid, this is not true. You must mean this comment [0], and we did respond, days ago.

Today I can only repeat that we do not use IGE as MAC. The attack described there [1] is irrelevant for our setup. A question for you, by the way: is your position that using CBC instead of IGE in our case would make the protocol more secure or less secure?

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

[1] https://groups.google.com/forum/#!topic/sci.crypt/4bkzm_n7UG...

> 3. Technical attributes of your RSA usage appear incompetent. RSA padding is not optional; 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.

We thanked you for feedback on padding two days ago [2] and noted that we were in the process of strengthening this point by moving to OAEP.

Still, the random padding already in use in MTProto is rather robust. The reason for this is that the RSA in DH is only used one way and ONLY with the public key. An attack on the private key would not be possible in this case, since it is not being used for transmission. So the sole possible attack would be MITM, which would imply deciphering RSA in real-time. If you are aware of other attacks that could harm this design, please tell us.

For the moment getting the RSA key with a microphone in traditional setups that store private RSA keys on client devices looks like a more real threat than what is described above. In our case private RSA keys are neither stored, nor used on the client.

[2] https://news.ycombinator.com/item?id=6918634

[tptacek]

You can't simply use CBC without a MAC either. The generic composition of CBC with HMAC and randomized explicit IVs is strong assuming you've dealt with side channels.

But a modern cryptosystem wouldn't use CBC either; it would use a AEAD mode, like AES-GCM or AES-OCB. A very, very modern system would use a native stream cipher like Salsa20 and a polynomial MAC like UMAC or GMAC or Poly1305. No cryptosystem in the world would use IGE mode plus SHA1.

There is no way around the fact that SHA1 with a bunch of semisecrets is not a real MAC. I have absolutely no idea why you would argue this point, but the fact that you do argue it is extraordinarily damning. I have never seen a project anywhere make so many mistakes and then confront such simple, straightforward, observations as "SHA1 is by itself not a MAC" with fierce arguments. The normal way of wiggling out of this problem is to fix your protocol. But your team clings tenaciously to a broken design. Why? Why? Why would you do that? How would anybody ever trust a cryptosystem designed by a team that would do that?

[tedunangst]

But your team clings tenaciously to a broken design. Why?

Maybe we're seeing the beginning of the "I'm going to do exactly the opposite of whatever the NSA tells me to do" era. The NSA says to use a MAC, so I'm not going to use a MAC!

[paveldurov]

If the advice comes from tptacek, you should probably do the opposite. He insisted this was NOT a backdoor:

https://news.ycombinator.com/item?id=6944118

[tptacek]

No, that's not at all what I said, but I despair of explaining the distinctions to someone who thinks AES-IGE+SHA1 and unpadded RSA is a sound design.

[moocowduckquack]

Hey, but now he knows that you are planning to do the opposite of what he says, presumably he will start giving you good advice, just to trick you.

The reason that people are so cynical about your custom solution is that being completely and utterly cynical about custom solutions, unless the architects can defend the solution rigorously, is the only sane approach in cryptography.

[Smirnoff]

Pavel, showing that he was wrong once in the past doesn't invalidate his multiple points he made now (or in the past).

[paveldurov]

> But a modern cryptosystem ... would use a AEAD mode, like AES-GCM

But really, it is funny how rigidly you stick to NSA Suite B Cryptography http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography

That, your fierce battle against everything unconventional and the fact that you get emotional instead of actually proving your point makes me think some "best practices" are indeed intentionally promoted in the crypto-community (https://news.ycombinator.com/item?id=6938622)

Disclaimer. I'm not an employee or shareholder in Telegram. I support them like I support some other non-profits like Wikimedia Foundation. As a reader here I would prefer to see an actual mathematical proof of how a certain system could be hacked instead of rhetoric like "No cryptosystem in the world would use...", "the fact that you do argue it is extraordinarily damning" or "Why? Why? Why would you do that?".

[StavrosK]

Because, with cryptography, the onus is on you to prove that your system is secure, not on other people to prove that it is broken. Everyone tells you there are many hints that your system is not secure, and you just go "well you can't prove it isn't, so there".

[jaxb]

Do you truly need to ad-hominem attack tptacek? You sound pretty much like pseudoscientists when they blame mainstream science being too rigid and not accepting their groundbreaking theories.

[paveldurov]

Scientific approach is exactly what I'm calling for here. When a cryptographer resorts to arguments like "this algorithm won't work because it is not common/modern/accepted" without providing an exact way to break it, it doesn't sound like scientific approach to me. It's more like the religious mindset of someone who rigidly worships some limited list of tools (e.g. "NSA Suite B Cryptography") and punishes anyone who is independent enough to deviate from it.

[justintroutman]

I noticed some things that concern me, and while I neither have an active attack, or the time* to formalize one, I'll leave these concerns here for discussion, and take part when time permits.

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.

[Nursie]

>> > they are trying to do “Mac and Encrypt” which is not secure. >> We are not doing this. We are doing this: http://core.telegram.org/techfaq#q-are-you-doing-encrypt-the....

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.

[StavrosK]

The idea of cryptographic hashes is that they don't leak information about the plaintext, though.

[velis_vel]

No, that's incorrect. A hash function should have these properties:

* Given a hash h it should be hard to find a message m such that hash(m) = h

* Given a mesage m1 it should be hard to find m2 such that hash(m1) = hash(m2)

* It should be hard to find any two messages m1 and m2 such that hash(m1) = hash(m2)

If you have some secure hash function h, the function h'(m) that appends the low byte of m to h(m) is still secure under all three properties, but it obviously leaks information.

[StavrosK]

Hmm, I unfortunately can't remember the hash attack models right now, but you may be right. I think there are models under which this fails, though.

[eliteraspberrie]

Although I am not a cryptographer, I understand the criticism you have received. Some feedback based on my very limited experience:

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.

[Nursie]

>> HMAC is very easy to implement, see RFC 2104. Your developers can do it in a day.

I can vouch for this, having just written an (embedded) HMAC implementation in half a day :)

[forgottenpass]

Lets assume, just for the sake of argument, that your encryption system and trust model are fine. Good. Great even.

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?

[makomk]

That FAQ is hilarious:

"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.

[yuvadam]

Thanks for responding re: the crypto. But one question begs to be asked -

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

[utnick]

Also, What did he mean by public keys are not authenticated?

[rlx0x]

did he pay to be the top voted comment, or are the HN readers really that stupid and voted him up?

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

[kbenson]

Maybe because it appears to be an official response so is relevant, regardless of whether people think it's entirely correct. That can be a good reason to upvote, IMO.

[wnevets]

I agree, its why I voted up the post.

[phaus]

IMO, because its either intentionally misleading or painfully uninformed, the fact that its info that came directly from the horse's mouth isn't a very good reason to up-vote.

[DanBC]

Don't high voted answers push up a post?