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
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.
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.
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".
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.
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.
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.
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.
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.
I can vouch for this, having just written an (embedded) HMAC implementation in half a day :)
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?
"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.
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)
Designing a protocol so that is does not leak is very hard.
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.
I though Satoshi was anonymous? Do you know something the rest of us don't, or are you making assumptions on the code (and if so, how can you make those assumptions when you also state it was a success)?
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.
Every client sends and receives 16KB blob every 30 seconds - this way you could prevent analysis that you are communicating with someone. You could learn a lot just from the size and frequency of packets in a normal chat program.
We really need to make the world at large aware that a USP in the crypto area is a big red flag.
"We use up to date, standard protocols and crypto techniques" really ought to be the top of the marketing blurb. "Ours is better because we invented it" is really terrible.
We need focused talking points, e.g. the fact that the NSA and other governments vacuum up all your data, and that TextSecure represents the first step toward a future in which it's very difficult for governments to do that. Whereas with Telegram, it's just as easy for them to access your conversations as it is for them to bypass SSL. Governments can and will do so. That's what users are concerned about; that's what they care about. Telegram has no defense against that argument due to their protocol's inherent vulnerability to this form of attack. Therefore it's the single most important point for to stress to any potential user.
Yet it's getting lost in the noise. Actually, I haven't seen it mentioned very much at all. Someone should do a writeup calling attention to it.
But please don't dismiss well written and well thought-out critiques like this one just because you didn't understand the arguments.
Well, if the algorithm is so broken then it should be trivial to break it even with their limitations.
Isn't that what they say? "Oh SHA-1 is broken", great, show it.
Of course, the capability to do that may be worth more than getting the $200k from the contest
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.
You are allowed access to the encrypted data.
In a real attack you may, depending on the circumstances, only have access to that (at first, at least).
Probably more like "you aren't allowed to destroy any locks or doors to enter the house". Hard, but much different than staying 200m from the house.
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.
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.
Yes, the pillar may corrode in 30 years, but the load is actually on a smaller and frailer pillar
Or if its vulnerable to a MITM, then explain how.
Or if its vulnerable to chosen plaintext/ciphertext or known plaintest, explain how.
There has been so much piling on of telegram, but nobody has actually proven any problems with their code or protocol. Meanwhile telegram is trying to do the right thing by being open source and taking the time to respond here and elsewhere to misconceptions and criticisms about them.
I really don't get the hostility towards them so far.
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.
You wouldn't be associated with Telegram, by any chance?
They answer this point on the website: "Q: Why do you use SHA-1 in the place of a MAC? [...] since this means still requiring at least 2^128 operations (instead of 2^256 with, say, SHA-2) to even begin trying to break this scheme, the trade-off seems fair."
Why not break the crypto (and take the money) if it's so amateurish?
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."
Yesterday someone blogged an example of a completely broken cryptosystem that would still pass Telegram's challenge with the same limitations: 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.
"... will give $200,000 in BTC to the first person ..."
Is that $200,000 in BTC at the time the contest was announced, or at the time the winner is announced? Or at some other point?
(This comment brought to you by the Committee For Pointing Out That A Currency That Wildly Fluctuates In Value Is Not Particularly Useful (CFPOTACTWFIVINPU).)
I still don't get why there is all this hostility toward telegram.
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?
Crypto experts, just crack it then.. who cares about the special conditions in the contest which make it so difficult. Just do it, prove your point and carry on.
$200k is PR, everyone knows that already.
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/
If they were serious about using their $200k for their security they should have either: a) Hired an actual independent cryptographer to do an audit. b) Set up a bug bounty program that rewards any weakness found, not just this "all-or-nothing" contest they have now.
[thinks of null key encryption]