At a glance, while this project is using secure (if aging) primitives, they've made some extremely unusual protocol choices that they need to publicly justify rather than simply describing in an API doc. Just at a glance, the use of modes like Infinite Garble Extension (a failed mode for Kerberos) is troubling, they made up their own KDF (with no proof), and they make what appear to be some amateur mistakes with how they use RSA.
I'm obviously biased, but if you want a mobile-oriented asynchronous messaging protocol, at this point I think the Axolotl ratchet should absolutely be its basis: https://www.whispersystems.org/blog/advanced-ratcheting/
If Telegram folks are on this thread, I'd encourage you to take a look at the TextSecure protocol. If you think it's interesting, you can federate into our network, get a provably secure asynchronous forward secrecy protocol, and also have access to an existing 10MM user base.
1. Kindly be more specific about our RSA implementation. Please note, that we only use RSA with public keys, not private. If you are aware of any possible attacks on this setup, please let us know.
2. And what problems with IGE are you aware of? Any known attack? As far as we know, it is the ubiquitous CBC that has had issues. And by the way, Kerberos had to abandon PCBC - not IGE.
Thank you for the offer to join in the project you represent. However, we feel that what we are doing is going in a somewhat different direction and has its own potential.
The team behind Telegram, led by Nikolai Durov, consists of six ACM champions, half of them Ph.Ds in math. It took them about two years to roll out the current version of MTProto. Names and degrees may indeed not mean as much in some fields as they do in others, but this protocol is the result of thougtful and prolonged work of professionals.
The basic copy on telegram.org rightfully appears as simplistic to the Hacker News resident. It was written for the general public, since we want to bring secure messaging to the masses — not just to the security geek, who has it already (in oh so many forms).
But for the technically minded we provided rather detailed documentation for our protocol:
We would be glad to respond to criticism, but not on the level of "I looked at it for 4 minutes, maybe they didn't think about X" (as another guy in the comments below put it), or "why didn't you just use this?".
If anybody here can identify a specific point and prove that it is vulnerable and can be hacked a certain way, we are ready to respond and\or fix, if neccessary. Gentlemen?
IGE was the first attempt at an "authenticating encryption mode," originally for Kerberos. It was a failed attempt (it does not provide integrity protection), and had to be removed. That was the beginning of a 20 year quest for an authenticating encryption mode that works, which recently culminated in modes like OCB and GCM. I don't see any integrity protection documented anywhere in your protocol spec, so if you're relying on IGE, it's broken.
What's more, any "problems" with CBC (I assume you're referring to padding oracle attacks) are not specific to CBC, and are endemic to IGE as well.
> The team behind Telegram, led by Nikolai Durov, consists of six ACM champions, half of them Ph.Ds in math. It took them about two years to roll out the current version of MTProto. Names and degrees may indeed not mean as much in some fields as they do in others, but this protocol is the result of thougtful and prolonged work of professionals.
I don't think their academic credentials or the amount of time they spent on this are the important metrics. If you're trying to suggest that they're thoughtful, the best metric for demonstrating that would be something like a proof for the (honestly naive-looking) KDF they made up.
In essence, the protocol seems to reflect many choices that anyone familiar with the field can immediately identify as suggesting a lack of understanding. It could be that these are simply brilliant moves that we non-ACM champions are too primitive to understand, but if that's true, you need to justify them with proofs in order to support them. Otherwise we're going to interpret them for how they appear.
> Thank you for the offer to join in the project you represent. However, we feel that what we are doing is going in a somewhat different direction and has its own potential.
Could you describe how your projects objectives are inconsistent with a protocol ratchet like Axolotol or the full TextSecure protocol?
Long story short: you get integrity protection from IGE by relying on the fact that a bit error anywhere in the stream will irrevocably corrupt the rest of the stream, so you create an authentication code by sticking an all-zeroes block or (like I think Telegram does) a message digest to the end of the stream.
But it's possible with carefully chosen errors to first corrupt an IGE stream and then recover it, so that the remainder of the message after the corruption (including the "MAC" tag) will remain intact.
IGE is an extremely weird, and, at this point I'll venture: bad choice for a 2013-2014 cryptosystem.
Not even HMAC-SHA1, just "SHA1"? So you leave yourself open to length extension attacks? http://en.wikipedia.org/wiki/Length_extension_attack
They appear to be trying to use encrypt and mac, and not as far as I can tell relying on IGE mode to provide authentication. See the "Message Key" and "Important Tests" sections here: https://core.telegram.org/mtproto/description
There is also not, as far as I can tell from reading the protocol description above and the source code here: https://github.com/ex3ndr/telegram-mt/blob/master/src/main/j... (in particular the EncryptedMessage method, lines 447 to 460) any sort of key in the MAC, it's just SHA-1 of the plaintext. It's also not encrypted as far as I can tell, it's listed in the unencrypted "external header" in the protocol description.
I can't think of an attack from this, but the fact that an adversary can generate a valid MAC for _any message_ by simply SHA-1'ing it seems really scary.
How broken is it here? Who knows. Professional cryptographers would use an AEAD mode with a security proof, or the generic composition of a cipher (w/proof) with ciphertext encrypted by a MAC (w/proof). Instead, this system uses a '70s block mode (that nobody else uses) and a hash function from the '90s.
We are indeed using well-known older algorithms, created in the days when bandwidth and processing power were both a much rarer commodity. This has valuable side-effects for modern-day mobile development, provided one takes care of the known drawbacks.
The weakspots of the said algorithms are also well-known, and have been exploited for decades. We used these algorithms in such a combination that, to our best knowledge, prevents any known attack from possibly succeeding. Although we’d be grateful to see any evidence of the contrary (so far absent from this thread) and update our system accordingly.
While other ways of achieving the same cryptographic goals, undoubtedly, exist, we feel that the present solution is both robust and also sucсeeds at our secondary task of beating unencrypted messengers in terms of delivery time and stability.
 – https://core.telegram.org/img/mtproto_encryption.png
 - http://core.telegram.org/mtproto/description
As for KDF, going for slower provable algorithms used for each incoming\outgoing packet may be a preferred solution for projects aimed at the relatively small security crowd. But we don't really compete in this area, our competition is WhatsApp and other mass market messengers.
What's this mean? You've created your own KDF, and the questions were: why is it secure, and why didn't you use an already-proven KDF? Unless I'm misreading something, it sounds like you've responded, "It's not that important, because our target market isn't people who care about their security." Is that correct?
EDIT: Judging by the upvotes, at least 5 other people are interested to hear your thoughts on this. Considering this submission is almost off the frontpage, that's a lot. As a security product, you should consider clarifying your position on this, because your statement currently sounds like, "We don't think security is a big deal since it's not a big deal to our target market."
Even as a complete newbie in cryptography I can see a problem in your reasoning. "Guilty until proven innocent" is the default when judging on a system. "No attack was named" because Telegram uses algorithms combination that was not proven with time. Nobody used them like this before. Why would anyone try to break it if it wasn't used?
As a potential user of Telegram I don't trust it enough to use it. It's more likely that someone with resources (e.g. government) could eventually break your system than it could break another - time-proven - system.
The consensus seems to be that you're doing encrypt-and-mac, where the mac is just a sha1? If that's true, then you're relying on broken properties of IGE (not provably UF-CMA), and your protocol does not provide provable integrity. That's an essential part of any secure protocol.
> As for KDF, going for slower provable algorithms used for each incoming\outgoing packet may be a preferred solution for projects aimed at the relatively small security crowd. But we don't really compete in this area, our competition is WhatsApp and other mass market messengers.
That's interesting, because the thing you've made up is actually slower than a provably secure KDF.
Now, again, could I somehow direct your attention away from speculations and to what we are ACTUALLY doing (as, again, documented here , and now here as well ).
1. We are not doing plain encrypt-and-mac.
2. The SHA1 in question is for raw unencrypted data.
3. The message key is SHA1-dependent.
4. Note that the AES key and iv depends on that SHA1.
This can be described as a generic composition of cipher with ciphertext, encrypted by a MAC. The resulting data-dependant variable key denies all common attacks.
As for KDF, what particular solution do you have in mind? And even then — certainly, alternative solutions exist, but we do not see how changing this point would affect our system as whole. 
As stated before, we'd welcome any information on attacks that could in reality threaten the actual setup.
 - http://core.telegram.org/mtproto/description
 - https://core.telegram.org/img/mtproto_encryption.png
All popular KDFs (PBKDF2, bcrypt, scrypt) are adaptive (tunable). You choose the number of iterations.
Great crypto software avoids RSA. Good crypto software uses OAEP when RSA is used to encrypt. Crappy crypto software (see: DNSSEC) uses PKCS1v1.5. What are you using?
I didn't look carefully; I have probably missed something. Please explain how you are using RSA in the handshake/authentication for your protocol. Like Moxie said: it's not the underlying algorithms you use; it's the constructions you use to to them together, and to the data you're protecting.
Incidentally, "I refuse to respond to comments from people who have only looked at my system for a couple minutes" is not a habit of highly effective cryptographers.
The server now supports OAEP, although this has yet to find its way into the docs and clients. We will update. Thank you!
You need to publish the server-side source code for me to have any chance of making sense of this. I only see the client side of the connection in your source code, not the server response.
Pray tell, why replay protection is done after decryption.
We could employ additional filtering techniques, but that increases processing time. And since modern hardware allows for very fast AES decryption, there is no particular gain in building additional layers of protection.
All that, naturally, implies that other anti-DoS measures are also being used.
In light of that, why would anyone in their right mind use a security product your organization developed?
Is vkontakte  (russian social site) being somehow involved? I got confused by the illustrative images strongly resembling the vkontakte images.
Not to dive into Russian folk, but those look too culturally localized.
In what areas of mathematics did these PhDs specialize? I hold a PhD in mathematics, but I would not feel comfortable rolling my own cryptographic algorithms for use in production (I'm a commutative algebraist by training).
Yes, because we all know that there are no women who can write code or analyze cryptographic algorithms. [rolls eyes]