11 ms·

A Crypto Challenge For The Telegram Developers

486 points by mjn 13y ago

andy112 13y ago
If they were to release the plaintext of Alice's (or, in their case, Paul's) message, wouldn't that include the secret email address? FWIW, I agree the contest is a sham for the reasons moxie & others listed here and elsewhere.
- nwh 13y ago
  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.
- Guvante 13y ago
  Two alternatives * 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.
ge0rg 13y ago
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.
- xnyhps 13y ago
  Well, not entirely the same framing. For $200k one could probably brute-force an 896-bit RSA key. ;)
  - moxie 13y ago
    I don't actually think that's true. At least, not within the time limits they defined. The $75k 896bit RSA factoring prize went unclaimed for 20 years, for instance.
    - nwh 13y ago
      Presumably if you made the prize large enough you wold get to the point where it would be economical and profitable to start fabricating your own hardware like the EFF did for DES. http://en.wikipedia.org/wiki/EFF_DES_cracker http://en.wikipedia.org/wiki/EFF_DES_cracker
      - sdevlin 13y ago
        This is true, but you could easily respond by increasing the RSA key size. This would make the protocol Telegram-secure without meaningfully improving its actual security profile in any way.
      - djcapelis 13y ago
        Ship yourself custom ASICs in the few months allowed by the contest guidelines and you'd earn it. FPGAs are another possibility, but even that would be a bit of an undertaking in a short timeframe and it might not actually get you much. Also the DES hardware is slightly different than prime number factorization in terms of workload. Supercomputers are fairly well optimized for some of the types of matrix operations you'd need to do for a GNFS, which is generally the method of choice for factoring large numbers on a classical computer. Custom hardware isn't going to give you the huge boost like you'd see for brute forcing DES. Custom hardware isn't a silver bullet and it is a large engineering problem that takes usually more time than the telegraph contest allows.
    - xnyhps 13y ago
      Yeah, when I started actually trying to back it up, I noticed I was probably a factor 5 off. Namely, if you look at the keylength.com values for asymmetric key sizes, 768 in 2009 ago should come close to the difficulty of 896 today. The RSA 768 challenge was broken in 2009 (http://eprint.iacr.org/2010/006 http://eprint.iacr.org/2010/006), which cost them "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron". Renting that amount of time Amazon EC2's $0.06/hour instances would be $1 million.
- wodenokoto 13y ago
  I still don't get it. If an insecure protocol with an insecure implementation can send messages that others can't read, how is it insecure?
  - deleted 13y ago
    [deleted]
  - jweir 13y ago
    Because the contest eliminates many vulnerabilities that exist in the real world. The contest framework is identical to Telegram’s (no MITM perspective, no known plaintext, no chosen plaintext, no chosen ciphertext, no tampering, no replay access, etc)
    - sdevlin 13y ago
      Also no side channel observations.
  - semiel 13y ago
    In real life, a lot of breaks in crypto security come from sidechannel attacks, man-in-the-middle attacks, chosen plaintext attacks, etc. Just posting a small number of already-encrypted messages disallows all of these possibilities.
  - ColinWright 13y ago
    The problem is not whether the protocol is secure - the problem is that there's no way we can tell. Historically, that means that it's likely not to be secure. With regards this counter-challenge. The crypto here is known to be poor. If this counter-challenge cannot be broken, then it shows that the challenge issued by Telegram is no proof of security. SO in short, * we don't know if no one can read the Telegram-encyphered messages, * the challenge provides effectively zero evidence that it's secure, * Telegram will proclaim loudly that no one has broken their crypto, * non-specialists will be fooled by this. If I haven't answered your question, perhaps you could be more explicit as to what you're not understanding.
    - 13y ago
alonium 13y ago
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
- octo_t 13y ago
  you sure seem to like Telegram. Also please don't use "butthurt".
- nwh 13y ago
  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. http://telegram.org/img/key_image.jpg 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.
  - utnick 13y ago
    How is the key image impossible to describe? There are only 4 possible colors per cell. You just describe it like 0,1,2,3,2,0, etc Just as if you were reading off the real key.
    - nwh 13y ago
      From just asking around, most people described the key image to me in terms of the darkest portions and ignored the parts that were lighter. It's easier for the example image to say that there's a dark L and lighter X shape in the center and then assume that the rest is the same. At least, that's how people did when I presented it to them as a challenge.
meowface 13y ago
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.
- belluchan 13y ago
  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.
  - sirsar 13y ago
    If you host your own server with their server software, you can verify it's running unmodified.
    - nwh 13y ago
      They don't provide the server-side code, nor a way to ensure that your client is talking to a specific server. The only authentication is via a 5 digit code sent via SMS, so it's presumably very easy to spoof and control messages. You need on average 5000 attempts to log into another users account (they are send a "new device added" notification message though), which could be done reasonably easily if you knew a person would have their phone off for a period of time when you wanted to attack their account.
  - meowface 13y ago
    Yep, that's also absolutely true. You'd have no idea if their servers were actually running the code they published. Moxie's TextSecure on the other hand does full end-to-end encryption, with no work done by any server. Same with OTR and similar message encryption plugins. It baffles me why people are sticking to the "everything on the server" route for applications that focus on user privacy and security in this day and age, especially when there are a lot of good alternatives that don't.
im3w1l 13y ago
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.
- meowface 13y ago
  That's making the assumption that all phones in the US have NSA keyloggers on them, which is pretty unlikely.
  - Crito 13y ago
    They don't need keyloggers on every phone. Having them on a wide range of people's phones (say, people involved with various Occupy stuff) is a very real possibility.
  - im3w1l 13y ago
    While they probably don't have keyloggers on them from the start, it is with high probability child's play for them to push it to your phone over the air, and make your phone run it http://www.osnews.com/story/27416/The_second_operating_system_hiding_in_every_mobile_phone http://www.osnews.com/story/27416/The_second_operating_syste... "What makes it even worse, is that every baseband processor inherently trusts whatever data it receives from a base station (e.g. in a cell tower). Nothing is checked, everything is automatically trusted. Lastly, the baseband processor is usually the master processor, whereas the application processor (which runs the mobile operating system) is the slave. So, we have a complete operating system, running on an ARM processor, without any exploit mitigation (or only very little of it), which automatically trusts every instruction, piece of code, or data it receives from the base station you're connected to. What could possibly go wrong? "
    - derefr 13y ago
      Yep. And you can build your own (low-power) GSM base-station: http://www.thinksmallcell.com/Technology/build-your-own-opensource-femtocell.html http://www.thinksmallcell.com/Technology/build-your-own-open... So anyone with a little time on their hands can be that "trusted party" for everyone in radio vicinity.
m-app 13y ago
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. [1]: https://threema.ch/en/ https://threema.ch/en/
- meowface 13y ago
  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.
- moxie 13y ago
  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): https://whispersystems.org/blog/asynchronous-security/ https://whispersystems.org/blog/asynchronous-security/
  - napoleond 13y ago
    That's not what their FAQ says: https://threema.ch/en/faq.html https://threema.ch/en/faq.html (scroll down, they specifically claim to provide forward secrecy) Do you have additional information?
    - moxie 13y ago
      Yikes, that actually looks like potentially deceptive marketing to me. > "Yes, Threema provides forward secrecy on the network connection. Client and server negotiate temporary random keys, which are only stored in RAM and replaced every time the app restarts (and at least once every 7 days). An attacker who has captured the network traffic will not be able to decrypt it even if he finds out the long-term secret key of the client or the server after the fact." My reading is that they have an end-to-end secure protocol that does not provide forward secrecy, which happens to be routed through a server which uses HTTPS w/ an ephemeral cipher suite for the network transport, with a TLS session ticket that they rotate the key on every 7 days. We should ask them for more details, but if true, that would be pretty deceptive of them.
guyht 13y ago
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)
- gregschlom 13y ago
  They said if no one wins the contest they would publish the keys allowing anyone to decrypt the data, proving it was not garbage.
  - guyht 13y ago
    Ah, I missed this part. Thanks
sdevlin 13y ago
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.
- danielweber 13y ago
  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?
  - lawnchair_larry 13y ago
    They aren't using it, but Dual_EC_DRBG is fairly widely used actually. There was a false meme denying that this was the case, but RSA and others proved that wrong.
    - deleted 13y ago
      [deleted]
    - tptacek 13y ago
      Dual EC was not particularly common. Here's a metric: name a couple of products that you or I use regularly that ever used it. It's not as if you could design a system with Dual EC instead of HMAC DRBG and not know it; Dual EC requires bignum math. It is incredibly slow for a CSPRNG.
javajosh 13y ago
Funny. But actually, the simplest contest that accurately describes Telegram's insanity is simply this: ::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!
- mintplant 13y ago
  The function is known--they publish how their algorithm works. The problem is that their contest doesn't account for the main problem with their system: its vulnerability to MITM attacks.
  - javajosh 13y ago
    Okay, then let f XOR the input with a randomly generated integer. There is no loss of generality here.
cybernytrix 13y ago
<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... </Rant>
ef47d35620c1 13y ago
If the prize was similar to this one, I think the challenge would be taken more seriously: http://16s.us/software/FreeOTP/freeotp_challenge.txt http://16s.us/software/FreeOTP/freeotp_challenge.txt * Prize One small Slurpee or its equivalent monetary value.
conformal 13y ago
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.
- pjscott 13y ago
  The license on the TextSecure app is GPLv3. What would you like to do with TextSecure that this license prohibits?
  - nardi 13y ago
    Integrate it and distribute it with non-open-source software. So, any commercial use whatsoever.
    - aidenn0 13y ago
      You can absolutely integrate it and distribute it with non-open-source software. Look at all the GPL stuff in android, for example.
    - belorn 13y ago
      You want to use other peoples software, modify then and distribute it. Afterward, you then want to sue users who dare to modify or share your version? How can anyone except authors to accommodate this, when the license choice explicit states the opposite?
    - nardi 13y ago
      I understand the down votes, and kind of expected it. But this is the actual practical reality, guys. Large software companies avoid GPLv3 like the plague. If you want your software to be used widely, then you need to use BSD/MIT/Apache/etc.
StavrosK 13y ago
I must be missing something, but isn't this easy to attack by exploiting the periodicity of the XOR function? Or is the message 32 bytes long as well?
- anonymoushn 13y ago
  The plaintext is the same length as the hash, so each byte of the hash is xored into only one other byte.
  - StavrosK 13y ago
    Ah, well, that's pretty secure, then.
huhtenberg 13y ago
This is counter-productive. 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 13y ago
  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.
- saraid216 13y ago
  > 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.
paulsmith 13y ago
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?
- bjt 13y ago
  I've heard this one's OK. https://www.schneier.com/book-applied.html https://www.schneier.com/book-applied.html
  - josephlord 13y ago
    Schneier himself semi-regrets this one I believe as it teaches enough to be dangerous but not enough to understand the risks you are creating. Implementing ciphers is one thing, knitting them together into a secure protocol is something very different and very challenging.
  - helper 13y ago
    NO! Applied Crypto is at times a fascinating book, but it is terrible for a developer that wants to learn the fundamentals of crypto and how to avoid the most common mistakes people make. Its also really old at this point. A much better book is Schneier, Ferguson and Kohno's "Cryptography Engineering"[1]. It covers what makes for strong crypto primitives and why weaker ones are considered broken. Note that is book is starting to get a bit out dated (I don't remember it covering ECC at all, for example), but I don't know of any better book. I also endorse the Matasano Crypto challenges and the Coursera Crypto class taught by Dan Boneh as excellent learning resources. [1] : https://www.schneier.com/book-ce.html https://www.schneier.com/book-ce.html
  - bqe 13y ago
    I'd recommend Cryptography Engineering over Applied Cryptography for programmers today. It has a lot of actionable info and is quite up to date. https://www.schneier.com/book-ce.html https://www.schneier.com/book-ce.html
- jsaxton86 13y ago
  There's a great Crypto I course on Coursera that I would highly recommend.
anonymoushn 13y ago
public key plz
zooko_LeastAuth 13y ago
Dear makers and backers of Telegram: Perhaps in response to my requests (https://news.ycombinator.com/item?id=6933179 https://news.ycombinator.com/item?id=6933179 , https://twitter.com/zooko/status/413552420522708993 https://twitter.com/zooko/status/413552420522708993 , https://twitter.com/zooko/status/413552466748133376 https://twitter.com/zooko/status/413552466748133376 ), your FAQ (http://core.telegram.org/contestfaq 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 13y ago
  Somebody pointed out to me that this isn't reddit, but hackernews. Oops, sorry.
- 13y ago
paveldurov 13y ago
As mentioned at http://core.telegram.org/contestfaq 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.
- moxie 13y ago
  Does this mean that you were unable to recover Alice's message?
  - paveldurov 13y ago
    Alas, I am not a cryptographer and not even a member of the Telegram team. I'm just a guy who backs Telegram financially and proposed to start their contest. I described my motives behind it here https://news.ycombinator.com/item?id=6938622 https://news.ycombinator.com/item?id=6938622 As for your contest, I will make sure the Telegram team will have a look at it once they are awake. As far as I understand, you designed it to be similar to Telegram's contest. How do you send messages that affect traffic in real-time? How large is the prize? Is there a deadline?
    - anonymoushn 13y ago
      You can generate your own messages according to the scheme he gave (even using the same public key from Bob if you like), but they will not be aggregated into a public log.
deleted 13y ago
[deleted]

486 points by mjn 13y ago

If they were to release the plaintext of Alice's (or, in their case, Paul's) message, wouldn't that include the secret email address? FWIW, I agree the contest is a sham for the reasons moxie & others listed here and elsewhere.

nwh 13y ago
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.
Guvante 13y ago
Two alternatives * 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.

ge0rg 13y ago

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.

xnyhps 13y ago
Well, not entirely the same framing. For $200k one could probably brute-force an 896-bit RSA key. ;)
- moxie 13y ago
  I don't actually think that's true. At least, not within the time limits they defined. The $75k 896bit RSA factoring prize went unclaimed for 20 years, for instance.
  - nwh 13y ago
    Presumably if you made the prize large enough you wold get to the point where it would be economical and profitable to start fabricating your own hardware like the EFF did for DES. http://en.wikipedia.org/wiki/EFF_DES_cracker http://en.wikipedia.org/wiki/EFF_DES_cracker
    - sdevlin 13y ago
      This is true, but you could easily respond by increasing the RSA key size. This would make the protocol Telegram-secure without meaningfully improving its actual security profile in any way.
    - djcapelis 13y ago
      Ship yourself custom ASICs in the few months allowed by the contest guidelines and you'd earn it. FPGAs are another possibility, but even that would be a bit of an undertaking in a short timeframe and it might not actually get you much. Also the DES hardware is slightly different than prime number factorization in terms of workload. Supercomputers are fairly well optimized for some of the types of matrix operations you'd need to do for a GNFS, which is generally the method of choice for factoring large numbers on a classical computer. Custom hardware isn't going to give you the huge boost like you'd see for brute forcing DES. Custom hardware isn't a silver bullet and it is a large engineering problem that takes usually more time than the telegraph contest allows.
  - xnyhps 13y ago
    Yeah, when I started actually trying to back it up, I noticed I was probably a factor 5 off. Namely, if you look at the keylength.com values for asymmetric key sizes, 768 in 2009 ago should come close to the difficulty of 896 today. The RSA 768 challenge was broken in 2009 (http://eprint.iacr.org/2010/006 http://eprint.iacr.org/2010/006), which cost them "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron". Renting that amount of time Amazon EC2's $0.06/hour instances would be $1 million.
wodenokoto 13y ago
I still don't get it. If an insecure protocol with an insecure implementation can send messages that others can't read, how is it insecure?
- deleted 13y ago
  [deleted]
- jweir 13y ago
  Because the contest eliminates many vulnerabilities that exist in the real world. The contest framework is identical to Telegram’s (no MITM perspective, no known plaintext, no chosen plaintext, no chosen ciphertext, no tampering, no replay access, etc)
  - sdevlin 13y ago
    Also no side channel observations.
- semiel 13y ago
  In real life, a lot of breaks in crypto security come from sidechannel attacks, man-in-the-middle attacks, chosen plaintext attacks, etc. Just posting a small number of already-encrypted messages disallows all of these possibilities.
- ColinWright 13y ago
  The problem is not whether the protocol is secure - the problem is that there's no way we can tell. Historically, that means that it's likely not to be secure. With regards this counter-challenge. The crypto here is known to be poor. If this counter-challenge cannot be broken, then it shows that the challenge issued by Telegram is no proof of security. SO in short, * we don't know if no one can read the Telegram-encyphered messages, * the challenge provides effectively zero evidence that it's secure, * Telegram will proclaim loudly that no one has broken their crypto, * non-specialists will be fooled by this. If I haven't answered your question, perhaps you could be more explicit as to what you're not understanding.
  - 13y ago

alonium 13y ago

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

octo_t 13y ago
you sure seem to like Telegram. Also please don't use "butthurt".
nwh 13y ago
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. http://telegram.org/img/key_image.jpg 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.
- utnick 13y ago
  How is the key image impossible to describe? There are only 4 possible colors per cell. You just describe it like 0,1,2,3,2,0, etc Just as if you were reading off the real key.
  - nwh 13y ago
    From just asking around, most people described the key image to me in terms of the darkest portions and ignored the parts that were lighter. It's easier for the example image to say that there's a dark L and lighter X shape in the center and then assume that the rest is the same. At least, that's how people did when I presented it to them as a challenge.

meowface 13y ago

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.

belluchan 13y ago
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.
- sirsar 13y ago
  If you host your own server with their server software, you can verify it's running unmodified.
  - nwh 13y ago
    They don't provide the server-side code, nor a way to ensure that your client is talking to a specific server. The only authentication is via a 5 digit code sent via SMS, so it's presumably very easy to spoof and control messages. You need on average 5000 attempts to log into another users account (they are send a "new device added" notification message though), which could be done reasonably easily if you knew a person would have their phone off for a period of time when you wanted to attack their account.
- meowface 13y ago
  Yep, that's also absolutely true. You'd have no idea if their servers were actually running the code they published. Moxie's TextSecure on the other hand does full end-to-end encryption, with no work done by any server. Same with OTR and similar message encryption plugins. It baffles me why people are sticking to the "everything on the server" route for applications that focus on user privacy and security in this day and age, especially when there are a lot of good alternatives that don't.

im3w1l 13y ago

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.

meowface 13y ago
That's making the assumption that all phones in the US have NSA keyloggers on them, which is pretty unlikely.
- Crito 13y ago
  They don't need keyloggers on every phone. Having them on a wide range of people's phones (say, people involved with various Occupy stuff) is a very real possibility.
- im3w1l 13y ago
  While they probably don't have keyloggers on them from the start, it is with high probability child's play for them to push it to your phone over the air, and make your phone run it http://www.osnews.com/story/27416/The_second_operating_system_hiding_in_every_mobile_phone http://www.osnews.com/story/27416/The_second_operating_syste... "What makes it even worse, is that every baseband processor inherently trusts whatever data it receives from a base station (e.g. in a cell tower). Nothing is checked, everything is automatically trusted. Lastly, the baseband processor is usually the master processor, whereas the application processor (which runs the mobile operating system) is the slave. So, we have a complete operating system, running on an ARM processor, without any exploit mitigation (or only very little of it), which automatically trusts every instruction, piece of code, or data it receives from the base station you're connected to. What could possibly go wrong? "
  - derefr 13y ago
    Yep. And you can build your own (low-power) GSM base-station: http://www.thinksmallcell.com/Technology/build-your-own-opensource-femtocell.html http://www.thinksmallcell.com/Technology/build-your-own-open... So anyone with a little time on their hands can be that "trusted party" for everyone in radio vicinity.

m-app 13y ago

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. [1]: https://threema.ch/en/ https://threema.ch/en/

meowface 13y ago
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.
moxie 13y ago
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): https://whispersystems.org/blog/asynchronous-security/ https://whispersystems.org/blog/asynchronous-security/
- napoleond 13y ago
  That's not what their FAQ says: https://threema.ch/en/faq.html https://threema.ch/en/faq.html (scroll down, they specifically claim to provide forward secrecy) Do you have additional information?
  - moxie 13y ago
    Yikes, that actually looks like potentially deceptive marketing to me. > "Yes, Threema provides forward secrecy on the network connection. Client and server negotiate temporary random keys, which are only stored in RAM and replaced every time the app restarts (and at least once every 7 days). An attacker who has captured the network traffic will not be able to decrypt it even if he finds out the long-term secret key of the client or the server after the fact." My reading is that they have an end-to-end secure protocol that does not provide forward secrecy, which happens to be routed through a server which uses HTTPS w/ an ephemeral cipher suite for the network transport, with a TLS session ticket that they rotate the key on every 7 days. We should ask them for more details, but if true, that would be pretty deceptive of them.

guyht 13y ago

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)

gregschlom 13y ago
They said if no one wins the contest they would publish the keys allowing anyone to decrypt the data, proving it was not garbage.
- guyht 13y ago
  Ah, I missed this part. Thanks

sdevlin 13y ago

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.

danielweber 13y ago
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?
- lawnchair_larry 13y ago
  They aren't using it, but Dual_EC_DRBG is fairly widely used actually. There was a false meme denying that this was the case, but RSA and others proved that wrong.
  - deleted 13y ago
    [deleted]
  - tptacek 13y ago
    Dual EC was not particularly common. Here's a metric: name a couple of products that you or I use regularly that ever used it. It's not as if you could design a system with Dual EC instead of HMAC DRBG and not know it; Dual EC requires bignum math. It is incredibly slow for a CSPRNG.

javajosh 13y ago

Funny. But actually, the simplest contest that accurately describes Telegram's insanity is simply this: ::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!

mintplant 13y ago
The function is known--they publish how their algorithm works. The problem is that their contest doesn't account for the main problem with their system: its vulnerability to MITM attacks.
- javajosh 13y ago
  Okay, then let f XOR the input with a randomly generated integer. There is no loss of generality here.

cybernytrix 13y ago

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

ef47d35620c1 13y ago

If the prize was similar to this one, I think the challenge would be taken more seriously: http://16s.us/software/FreeOTP/freeotp_challenge.txt http://16s.us/software/FreeOTP/freeotp_challenge.txt * Prize One small Slurpee or its equivalent monetary value.

conformal 13y ago

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.

pjscott 13y ago
The license on the TextSecure app is GPLv3. What would you like to do with TextSecure that this license prohibits?
- nardi 13y ago
  Integrate it and distribute it with non-open-source software. So, any commercial use whatsoever.
  - aidenn0 13y ago
    You can absolutely integrate it and distribute it with non-open-source software. Look at all the GPL stuff in android, for example.
  - belorn 13y ago
    You want to use other peoples software, modify then and distribute it. Afterward, you then want to sue users who dare to modify or share your version? How can anyone except authors to accommodate this, when the license choice explicit states the opposite?
  - nardi 13y ago
    I understand the down votes, and kind of expected it. But this is the actual practical reality, guys. Large software companies avoid GPLv3 like the plague. If you want your software to be used widely, then you need to use BSD/MIT/Apache/etc.

StavrosK 13y ago

I must be missing something, but isn't this easy to attack by exploiting the periodicity of the XOR function? Or is the message 32 bytes long as well?

anonymoushn 13y ago
The plaintext is the same length as the hash, so each byte of the hash is xored into only one other byte.
- StavrosK 13y ago
  Ah, well, that's pretty secure, then.

huhtenberg 13y ago

This is counter-productive. 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 13y ago
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.
saraid216 13y ago
> 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.

paulsmith 13y ago

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?

bjt 13y ago
I've heard this one's OK. https://www.schneier.com/book-applied.html https://www.schneier.com/book-applied.html
- josephlord 13y ago
  Schneier himself semi-regrets this one I believe as it teaches enough to be dangerous but not enough to understand the risks you are creating. Implementing ciphers is one thing, knitting them together into a secure protocol is something very different and very challenging.
- helper 13y ago
  NO! Applied Crypto is at times a fascinating book, but it is terrible for a developer that wants to learn the fundamentals of crypto and how to avoid the most common mistakes people make. Its also really old at this point. A much better book is Schneier, Ferguson and Kohno's "Cryptography Engineering"[1]. It covers what makes for strong crypto primitives and why weaker ones are considered broken. Note that is book is starting to get a bit out dated (I don't remember it covering ECC at all, for example), but I don't know of any better book. I also endorse the Matasano Crypto challenges and the Coursera Crypto class taught by Dan Boneh as excellent learning resources. [1] : https://www.schneier.com/book-ce.html https://www.schneier.com/book-ce.html
- bqe 13y ago
  I'd recommend Cryptography Engineering over Applied Cryptography for programmers today. It has a lot of actionable info and is quite up to date. https://www.schneier.com/book-ce.html https://www.schneier.com/book-ce.html
jsaxton86 13y ago
There's a great Crypto I course on Coursera that I would highly recommend.

anonymoushn 13y ago

public key plz

zooko_LeastAuth 13y ago

Dear makers and backers of Telegram: Perhaps in response to my requests (https://news.ycombinator.com/item?id=6933179 https://news.ycombinator.com/item?id=6933179 , https://twitter.com/zooko/status/413552420522708993 https://twitter.com/zooko/status/413552420522708993 , https://twitter.com/zooko/status/413552466748133376 https://twitter.com/zooko/status/413552466748133376 ), your FAQ (http://core.telegram.org/contestfaq 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 13y ago
Somebody pointed out to me that this isn't reddit, but hackernews. Oops, sorry.
13y ago

paveldurov 13y ago

As mentioned at http://core.telegram.org/contestfaq 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.

moxie 13y ago
Does this mean that you were unable to recover Alice's message?
- paveldurov 13y ago
  Alas, I am not a cryptographer and not even a member of the Telegram team. I'm just a guy who backs Telegram financially and proposed to start their contest. I described my motives behind it here https://news.ycombinator.com/item?id=6938622 https://news.ycombinator.com/item?id=6938622 As for your contest, I will make sure the Telegram team will have a look at it once they are awake. As far as I understand, you designed it to be similar to Telegram's contest. How do you send messages that affect traffic in real-time? How large is the prize? Is there a deadline?
  - anonymoushn 13y ago
    You can generate your own messages according to the scheme he gave (even using the same public key from Bob if you like), but they will not be aggregated into a public log.

deleted 13y ago

[deleted]