For reference, here's a list (probably incomplete? (EDIT: and feel free to add!)) of ways this protocol is broken:
1. There's no authentication at any point. The whole thing is trivially MITM-able.
2. The RNG is Dual_EC_DRBG, which is backdoored.
3. The RSA public key is small enough that an attacker of sufficient means could break it.
4. The RSA plaintext is unpadded. Proper padding is critical for safe RSA encryption. See e.g. Bleichenbacher '98.
5. RSA is used to encrypt semantic data. Dangerous for the same reasons as above.
6. The hash function is broken. I'm not sure if this matters too much here, but I'm also not sure that it doesn't matter.
7. The ciphertext seems to be restricted to messages of exactly 128 bits. It's not clear how or if the plaintext is padded if it's too short, and it's not clear how the protocol handles a longer message. These are noteworthy considerations.
And yet it's still (basically) safe against the kind of contest Telegram has outlined. Someone could win by factoring the RSA public key, but I'm not sure if that would be cheaper than the $200k prize. This vulnerability can also be mitigated trivially by using bigger RSA keys, making the protocol Telegram-secure.
I don't understand 5. RSA is used there to encrypt a random value that is used as a KDF input. I do get it that the size of the random value together with lack of any padding and poor choice of KDF causes issues, but can you explain why do we care about malleability (or did you mean something else) here?
I don't keep up on everything, but I thought Dual_EC_DRBG was used by nobody else for any real world crypto. Did these guys look over the Wiki page and decide it would be fun to be the first?
> 6. The hash function is broken. I'm not sure if this matters too much here, but I'm also not sure that it doesn't matter.
They are using SHA-1, which is indeed broken, not as broken as MD5 and its predecessors yet, but still less than a birthday attack.
> The message key is defined as the 128 lower-order bits of the SHA1 of the message body (including session, message ID, etc.).
A reduced SHA-1 cut down from 160 to 128 bits is not collision resistant. I'm not sure what implication this has for this protocol but if strong collision resistance is required this may be a point of weakness.
tl;dr: moxie uses ancient, known broken crypto primitives (Dual_EC_DRBG, RSA with 896 bits, MD2 and XOR) to construct a chat protocol which is unbreakable if framed in the same way the Telegram developers did with their challenge. "If they can’t demonstrate a break in this obviously broken protocol using the same contest framework they’ve setup, then we’ll know that their contest is bullshit."
Also, a call to arms to improve the OSS TextSecure implementation.
Even if Telegram's explanation did stand up to scrutiny and was ran by experienced cryptographers, the fact that its core code is closed source makes it utterly worthless from a security perspective. They can tout their own security all they like, but if no one else can independently verify it then it means nothing.
So far they've only published the source to their client, but their servers do all of the actual processing and cryptography.
All of Moxie's projects, on the other hand, have always been completely open source.
Open source doesn't imply trustworthiness and it's a very dangerous assumption to make.
Any open source system can be screwed with in a variety of ways. The simplest and most effective option is to publish both the source and the binaries, but built latter from the an altered source. This will work in a vast majority of cases, because a lot of people make this ridiculous assumption that publishing the source automatically implies that the guy is good, open and trustworthy all over. And won't bother verifying the binaries. Virtually everyone will assume that since it's open there will be someone who will do the verification. Guess what? That someone will assume the same thing.
That's your good old social engineering. It's the humans that are exploitable, not the tech.
But let's say, as unlikely as it is, this such person materialized. Easy enough to run an independent build and verify the binaries, right? Sure. In theory. In a lot of cases, due to dependencies, it's either hard or nearly impossible to do. In other cases it translates into an non-trivial amount of work, which needs to be justified. I am aware of just one project - PGPfone - that published not just the code, but the exact build instructions to produce matching binaries. Everything else is just the "open source, trust us" model. And so the bottom line is that in heck of a lot of cases you will not be able to produce matching binaries.
Now, even if the binary difference in just several bytes that is 100% enough to screw everyone over. This is done by messing with an initialization of an internal random number generator, which all crypto stacks have. All you need to do is make the PRNG (semi)predictable and the best crypto won't stand a chance as there'll be no secrets.
In the end, if you are using pre-made binaries (and who doesn't?) that are not built by a trusted entity from a specific peer-reviewed snapshot of the sources, you have the exact same chances of running a flawed version regardless of whether its source is open or not. Except that in a closed source case you are likely to be more on guard for the surprises.
It's really not even enough to open source their server software because you would still have to trust that they ran that open source software unmodified on their machines.
As mentioned at http://core.telegram.org/contestfaq if more tools to interact with the traffic are needed for the contestants to crack Telegram, they will be provided in the next contest right after 1 March, 2014. The current contest has an important practical task of deciphering traffic that is being intercepted in real time. This is the basic concern of regular users like myself (me and lots of other people in Russia had to stop using WhatsApp because of easily decipherable intercepted traffic). If Telegram proves to be robust in this respect, more tools to manipulate traffic and wider contests with similar prizes are to follow. Like all startups, this contest by Telegram starts from solving a basic but most important problem, then gradually gets more complicated in functionality and scope.
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.
Thanks for sponsoring the Telegram product. (Even though I think what they are trying to do could be done much better.)
Could you please ask the Telegram team to post the exact contents of the first message that Paul sent to Nick, except with the secret email address X'ed out? I explained in https://news.ycombinator.com/item?id=6937631 that if the MT protocol is secure, then there is no risk in posting such a "known plaintext", so the Telegram team should have no problem posting it.
Whichever way you view Telegram, they haven't developed it to make a quick buck on the ignorance of the masses, nor are they in it to deceive people and entice them to use a knowingly broken crypto.
Granted, they have an attitude problem, they clearly have no experience talking to the crypto community and they made dumb move with this contest thing, but in the end of the day they and Moxie(s) are on the same damn side.
They have a blindness and an arrogance that could prove fatal to anyone trusting them. Until they lose the arrogance and catch up with the published state of the art crypto they are dangerous and are likely to do more harm than good.
This is a very clear explanation of the limitations of their challenge and hopefully will open their eyes and help them on the road to getting a better understanding. If not it will help to limit the damage they can do by publicly clarifying the limitations and the lack of understanding that they currently have.
> Whichever way you view Telegram, they haven't developed it to make a quick buck on the ignorance of the masses, nor are they in it to deceive people and entice them to use a knowingly broken crypto.
The contest they set up actually makes me think they did. I am willing to see them pay out for it and thus prove me wrong, though.
Is there a decent “Crypto Not For Dummies But For Reasonably Competent Programmers Who Have Thus Far Taken It For Granted But Want To Get Up To Speed Fairly Quickly On Concepts And Implementation” text?
-------
Q: Does Paul send the same message to Nick every day?
No, just as in real life, Paul‘s messages to Nick can be different each time. The only thing that doesn’t change is the secret email address in his daily messages.
Q: Could you provide an example of a Paul's message to Nick?
Sure. The message may look like “Hey Nick, so here is the secret email address for the bounty hunters – {here goes the email}”.
-------
There are some things that I don't understand about the structure of this contest. Why is the target secret an email address rather than a magic word like "squeamish ossifrage"?
I asked for an “examples of the actual message”, and you posted an possible example, but what I meant to ask for was actually the exact text of one of the messages. Except, of course with the target string (the email address) replaced by X's.
For redditors following along, getting a (partial) copy of the exact message that was sent would be an example of what cryptographers call (partial) "known plaintext". If your cryptosystem is secure against Known Plaintext Attack, then it doesn't matter if an attacker (me) gets copies of some of the messages. If your cryptosystem is insecure in this model, then your users have to be careful with what they type into their messages. For example, they might need to be careful not to cut and paste long strings from other sources, or to otherwise insert strings into their messages that their attacker might guess.
All good, modern cryptosystems are secure in the Known Plaintext Attack model! (And, in fact, all good, modern cryptosystems are secure in much more rigorous models in which attackers get more powers beyond peeking at plaintext.)
So if the makers of Telegram are confident in the security of their protocol, they should have no problem posting the complete, verbatim text of the first message that Paul sent to Nick, with the target email address replaced by "XXX"'s.
Taylor Hornby has written a good introductory explanation of the Known Plaintext Attack model and the more powerful attack models, in the context of the Telegram cracking contest:
A simple way to understand the gravity of this: the Nazi's Enigma machine was broken with a known-plaintext attack a.k.a a Turing Bombe break. Furthermore, it was the known plain text of previously decrypted messages that was used in further attacks against new keys issued by the Nazis.
I have been saying this a couple of times in similar threads, but I think Threema [1] deserves a little more attention. Complete end-to-end encryption using NaCl. The interface they created is simple and gets the point across. Also, they're actually saying "don't trust us!", which ironically makes me trust them.
Their protocol doesn't provide any forward secrecy. It uses the PGP protocol model, which is increasingly being seen as an architectural dead end (particularly given the recently revealed ciphertext recording capabilities of NSA):
This looks like a better alternative, but unfortunately all of their code is closed source as well.
I completely understand the desire for developers to make certain applications closed source, but if your application's main selling point is user privacy and security, you really need to abandon that desire.
Whats to stop Telegram tampering with the messages and just displaying random bytes in the 'output'? This would make it impossible to crack. You cant test the security of a system without 1 - full access to the system or 2 - complete trust in the people controlling the system (which we dont have)
Using an NSA backdoored RNG is pretty redundant. A cell phone cannot be secured against NSA. They'll just activate their keylogger and grab the plaintext before it has even been encrypted.
The goal is to prevent mass snooping on our private data. It's impossible to prevent an attacker with root access from getting your data, but on the other hand, they must invoke their root access in order to get your data.
More simply: right now, the NSA is vacuuming up everyone's data across all services. Your emails, your texts, your search history, certainly your metadata; basically everything. And the only reason it was possible for the NSA to do this to us is because security has historically been an afterthought.
TextSecure is the first step toward keeping our data free from prying eyes. It prevents the NSA from having default access to our texts. If the NSA wants your data, they'll have to deliver a keylogger to your specific phone in particular. That's very different from gathering everyone's comms all the time.
Telegram, on the other hand, offers no protection whatsoever against the NSA vacuuming up everything, because the NSA can simply MITM every Telegram conversation as they're initiated, just like the NSA MITM's CAs to decrypt your https traffic.
In summary: if you care at all about a world in which the NSA can't sift through all of your data, then use and promote TextSecure, because TextSecure offers protection against governments.
Now, I've said "NSA" about ten times here, but this is true for other governments too. Other governments have impersonated CAs, coerced CAs into issuing bogus security certificates, etc, to target people they deem to be political radicals. China tries very hard to do this. I'm sure there are plenty of governments worldwide who are all working on doing exactly this.
So it's not just the NSA. It's the entire future landscape of our data privacy. If you believe you have the right to electronic privacy, then use TextSecure, and make sure everyone knows the truth: Telegram offers no such privacy.
That gives me an idea: messaging apps shouldn't use the default OS keyboard, but write their own. In that case, NSA would need to target that messaging app specifically.
<Rant>
After reading all the blogs and replies that are abuzz talking about Telegram, I realized they are the best guerrilla marketers I have seen in a while!
They might as well throw away their PhD. papers and stop calling themselves as Engineers/Cryptographers/whatever... marketing monkeys...
The contest is only set up that way to make it look more secure, there's really no reason that you would have to prove yourself in that way. If there's an actual cryptographic break then a researcher can prove it without all of the "send email to this address" nonsense.
* Have a special message that does not contain the email address and makes it's contents public.
* Take whatever the first message happened to be and replace any characters in the email address with the character X and release that. Giving away the length of the email address wouldn't do anyone any good.
this is a reminder that prizes or cash for breaking crypto products is a silly PR stunt. mega did the same thing, ended up paying out some money, then their product is "secure" by the same sort of argument. same deal with cryptocat and several other cryptoturds.
i do find it amusing to hear moxie ranting about how much better textsecure is when the license on it is such shit. can't argue with the fact that it's open source, but there is no point in contributing the codebase due to the licensing.
Another guy has butthurt from Telegram. As I read somewhere telegram guys said that after 1st march 2014 they somehow will allow to perform MITM in that crypto challenge
If they allow man in the middle attacks then the system is completely and demonstrably broken. The out of band public key verification uses deterministic images to confirm that the keys are the same, which can be easy forged given the relatively bad comparison engines in use (humans describing what a pixelated 16px image looks like). At no point is the real key shown to the user, so it's impossible to verify that they're identical through a description.
I wager that if they did allow a tampering eavesdropper in their bounty contest, it would be in the same conversation that has already done a key exchange and verification, making it yet more snake oil. You can hardly call something secure when you don't allow real-world MITM attacks in testing.
Man in the Middle attacks are so easy and cheap to set up. Just use a few wireless access points, pop them up around town, install something like Jasager and a 3G dongle. Phones like to connect with known networks and will happily connect with your rouge access point, if you tell them that you are exactly the ap they are looking for.
So, any system that claims to be secure must factor in MitM.
More information on this, and how easy it is to trick devices can be found at Troy Hunts website [0] and at Wifi Pineapple [1]
[+] [-] sdevlin|12 years ago|reply
[+] [-] robryk|12 years ago|reply
[+] [-] danielweber|12 years ago|reply
[+] [-] decasteve|12 years ago|reply
They are using SHA-1, which is indeed broken, not as broken as MD5 and its predecessors yet, but still less than a birthday attack.
> The message key is defined as the 128 lower-order bits of the SHA1 of the message body (including session, message ID, etc.).
A reduced SHA-1 cut down from 160 to 128 bits is not collision resistant. I'm not sure what implication this has for this protocol but if strong collision resistance is required this may be a point of weakness.
[+] [-] ge0rg|12 years ago|reply
Also, a call to arms to improve the OSS TextSecure implementation.
[+] [-] wodenokoto|12 years ago|reply
If an insecure protocol with an insecure implementation can send messages that others can't read, how is it insecure?
[+] [-] xnyhps|12 years ago|reply
For $200k one could probably brute-force an 896-bit RSA key. ;)
[+] [-] meowface|12 years ago|reply
So far they've only published the source to their client, but their servers do all of the actual processing and cryptography.
All of Moxie's projects, on the other hand, have always been completely open source.
[+] [-] huhtenberg|12 years ago|reply
Any open source system can be screwed with in a variety of ways. The simplest and most effective option is to publish both the source and the binaries, but built latter from the an altered source. This will work in a vast majority of cases, because a lot of people make this ridiculous assumption that publishing the source automatically implies that the guy is good, open and trustworthy all over. And won't bother verifying the binaries. Virtually everyone will assume that since it's open there will be someone who will do the verification. Guess what? That someone will assume the same thing.
That's your good old social engineering. It's the humans that are exploitable, not the tech.
But let's say, as unlikely as it is, this such person materialized. Easy enough to run an independent build and verify the binaries, right? Sure. In theory. In a lot of cases, due to dependencies, it's either hard or nearly impossible to do. In other cases it translates into an non-trivial amount of work, which needs to be justified. I am aware of just one project - PGPfone - that published not just the code, but the exact build instructions to produce matching binaries. Everything else is just the "open source, trust us" model. And so the bottom line is that in heck of a lot of cases you will not be able to produce matching binaries.
Now, even if the binary difference in just several bytes that is 100% enough to screw everyone over. This is done by messing with an initialization of an internal random number generator, which all crypto stacks have. All you need to do is make the PRNG (semi)predictable and the best crypto won't stand a chance as there'll be no secrets.
In the end, if you are using pre-made binaries (and who doesn't?) that are not built by a trusted entity from a specific peer-reviewed snapshot of the sources, you have the exact same chances of running a flawed version regardless of whether its source is open or not. Except that in a closed source case you are likely to be more on guard for the surprises.
[+] [-] chetanahuja|12 years ago|reply
I realize t'is the season to to piling on to the hapless Telegram folks, but I think that assertion is wrong.
[+] [-] belluchan|12 years ago|reply
[+] [-] finnn|12 years ago|reply
[+] [-] paveldurov|12 years ago|reply
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.
[+] [-] zooko_LeastAuth|12 years ago|reply
Could you please ask the Telegram team to post the exact contents of the first message that Paul sent to Nick, except with the secret email address X'ed out? I explained in https://news.ycombinator.com/item?id=6937631 that if the MT protocol is secure, then there is no risk in posting such a "known plaintext", so the Telegram team should have no problem posting it.
[+] [-] moxie|12 years ago|reply
[+] [-] huhtenberg|12 years ago|reply
Whichever way you view Telegram, they haven't developed it to make a quick buck on the ignorance of the masses, nor are they in it to deceive people and entice them to use a knowingly broken crypto.
Granted, they have an attitude problem, they clearly have no experience talking to the crypto community and they made dumb move with this contest thing, but in the end of the day they and Moxie(s) are on the same damn side.
Antagonizing things further is just plain stupid.
[+] [-] josephlord|12 years ago|reply
This is a very clear explanation of the limitations of their challenge and hopefully will open their eyes and help them on the road to getting a better understanding. If not it will help to limit the damage they can do by publicly clarifying the limitations and the lack of understanding that they currently have.
[+] [-] saraid216|12 years ago|reply
The contest they set up actually makes me think they did. I am willing to see them pay out for it and thus prove me wrong, though.
[+] [-] paulsmith|12 years ago|reply
[+] [-] jacalata|12 years ago|reply
[+] [-] zooko_LeastAuth|12 years ago|reply
Perhaps in response to my requests (https://news.ycombinator.com/item?id=6933179 , https://twitter.com/zooko/status/413552420522708993 , https://twitter.com/zooko/status/413552466748133376 ), your FAQ (http://core.telegram.org/contestfaq) now says:
------- Q: Does Paul send the same message to Nick every day?
No, just as in real life, Paul‘s messages to Nick can be different each time. The only thing that doesn’t change is the secret email address in his daily messages.
Q: Could you provide an example of a Paul's message to Nick?
Sure. The message may look like “Hey Nick, so here is the secret email address for the bounty hunters – {here goes the email}”. -------
There are some things that I don't understand about the structure of this contest. Why is the target secret an email address rather than a magic word like "squeamish ossifrage"?
I asked for an “examples of the actual message”, and you posted an possible example, but what I meant to ask for was actually the exact text of one of the messages. Except, of course with the target string (the email address) replaced by X's.
For redditors following along, getting a (partial) copy of the exact message that was sent would be an example of what cryptographers call (partial) "known plaintext". If your cryptosystem is secure against Known Plaintext Attack, then it doesn't matter if an attacker (me) gets copies of some of the messages. If your cryptosystem is insecure in this model, then your users have to be careful with what they type into their messages. For example, they might need to be careful not to cut and paste long strings from other sources, or to otherwise insert strings into their messages that their attacker might guess.
All good, modern cryptosystems are secure in the Known Plaintext Attack model! (And, in fact, all good, modern cryptosystems are secure in much more rigorous models in which attackers get more powers beyond peeking at plaintext.)
So if the makers of Telegram are confident in the security of their protocol, they should have no problem posting the complete, verbatim text of the first message that Paul sent to Nick, with the target email address replaced by "XXX"'s.
[+] [-] zooko_LeastAuth|12 years ago|reply
http://www.cryptofails.com/post/70546720222/telegrams-crypta...
[+] [-] djm_|12 years ago|reply
[+] [-] zooko_LeastAuth|12 years ago|reply
[+] [-] m-app|12 years ago|reply
[1]: https://threema.ch/en/
[+] [-] moxie|12 years ago|reply
https://whispersystems.org/blog/asynchronous-security/
[+] [-] meowface|12 years ago|reply
I completely understand the desire for developers to make certain applications closed source, but if your application's main selling point is user privacy and security, you really need to abandon that desire.
[+] [-] javajosh|12 years ago|reply
::Given an unknown function f and a single output y, compute the input x that maps to y.::
Ready? Here's the output: ROSEBUD. Now I'll give $100k to anyone who can tell me x. Good luck!
[+] [-] guyht|12 years ago|reply
[+] [-] gregschlom|12 years ago|reply
[+] [-] im3w1l|12 years ago|reply
[+] [-] sillysaurus2|12 years ago|reply
More simply: right now, the NSA is vacuuming up everyone's data across all services. Your emails, your texts, your search history, certainly your metadata; basically everything. And the only reason it was possible for the NSA to do this to us is because security has historically been an afterthought.
TextSecure is the first step toward keeping our data free from prying eyes. It prevents the NSA from having default access to our texts. If the NSA wants your data, they'll have to deliver a keylogger to your specific phone in particular. That's very different from gathering everyone's comms all the time.
Telegram, on the other hand, offers no protection whatsoever against the NSA vacuuming up everything, because the NSA can simply MITM every Telegram conversation as they're initiated, just like the NSA MITM's CAs to decrypt your https traffic.
In summary: if you care at all about a world in which the NSA can't sift through all of your data, then use and promote TextSecure, because TextSecure offers protection against governments.
Now, I've said "NSA" about ten times here, but this is true for other governments too. Other governments have impersonated CAs, coerced CAs into issuing bogus security certificates, etc, to target people they deem to be political radicals. China tries very hard to do this. I'm sure there are plenty of governments worldwide who are all working on doing exactly this.
So it's not just the NSA. It's the entire future landscape of our data privacy. If you believe you have the right to electronic privacy, then use TextSecure, and make sure everyone knows the truth: Telegram offers no such privacy.
[+] [-] meowface|12 years ago|reply
[+] [-] conformal|12 years ago|reply
you have won the prize! expecting anything to be secure on a mobile device is a serious mistake.
in some ways, textsecure and redphone actually induce behavior that puts people at risk: no amount of encryption can make a mobile device safe.
the only possible exception to this is a device that is built from zero and has fully in-house gsm stack, etc.
[+] [-] svantana|12 years ago|reply
[+] [-] cybernytrix|12 years ago|reply
</Rant>
[+] [-] StavrosK|12 years ago|reply
[+] [-] anonymoushn|12 years ago|reply
[+] [-] ef47d35620c1|12 years ago|reply
http://16s.us/software/FreeOTP/freeotp_challenge.txt
[+] [-] andy112|12 years ago|reply
FWIW, I agree the contest is a sham for the reasons moxie & others listed here and elsewhere.
[+] [-] nwh|12 years ago|reply
[+] [-] Guvante|12 years ago|reply
* Have a special message that does not contain the email address and makes it's contents public. * Take whatever the first message happened to be and replace any characters in the email address with the character X and release that. Giving away the length of the email address wouldn't do anyone any good.
[+] [-] unknown|12 years ago|reply
[deleted]
[+] [-] conformal|12 years ago|reply
i do find it amusing to hear moxie ranting about how much better textsecure is when the license on it is such shit. can't argue with the fact that it's open source, but there is no point in contributing the codebase due to the licensing.
[+] [-] anonymoushn|12 years ago|reply
[+] [-] alonium|12 years ago|reply
[+] [-] nwh|12 years ago|reply
http://telegram.org/img/key_image.jpg
I wager that if they did allow a tampering eavesdropper in their bounty contest, it would be in the same conversation that has already done a key exchange and verification, making it yet more snake oil. You can hardly call something secure when you don't allow real-world MITM attacks in testing.
[+] [-] jagermo|12 years ago|reply
So, any system that claims to be secure must factor in MitM.
More information on this, and how easy it is to trick devices can be found at Troy Hunts website [0] and at Wifi Pineapple [1]
[0]: http://www.troyhunt.com/2013/04/the-beginners-guide-to-break... [1]: https://wifipineapple.com/
[+] [-] octo_t|12 years ago|reply
[+] [-] MagicWishMonkey|12 years ago|reply