If there's anything that's certain, it's the progress of compute power. The fact that his statement lasted 14 years is impressive. I mean, 640K ought to be enough for anyone.
That would be true if RSA keys were brute forced, but they aren't - e.g. 512 bit RSA takes days/weeks to break on commodity hardware these days, whereas 512 bit brute force (as is essentially needed for ECC these days) takes significantly longer than the estimated age of the universe.
You need to factor in speedups due to advances in factoring algorithms, too. And it's possible that the software doesn't have any options between 2048 and 4096. (I have no idea, I didn't check.)
The nonce-increment bug wasn't found as part of the bug bounty program; it was retroactively included when I set up the bug bounty program a few months later.
the difference here is that there's no "fake-world" contest. Tarsnap is asking for a real-world hack of their system.
Telegram, on the other hand, is trying to prove that their algorithm is unbreakable. AES is pretty good too.
As is noted in other comments, it's generally the system, not the algorithm, that gets broken.
Our Twofish cryptanalysis contest offers a $10K prize for the best negative comments on Twofish that aren't written by the authors. There are no arbitrary definitions of what a winning analysis is. There is no ciphertext to break or keys to recover. We are simply rewarding the most successful cryptanalysis research result, whatever it may be and however successful it is (or is not). Again, the contest is fair because 1) the algorithm is completely specified, 2) there are no arbitrary definition of what winning means, and 3) the algorithm is public domain.
This Telegram contest may seem superficially similar to that fair contest, but it differs in some important ways. First, this contest isn't rewarding "best effort". Second, this contest doesn't meet those criteria, because their central server isn't being tested here. The goal of a product like Telegram is to defend against adversaries like governments, and hence governments will be able to probe their servers for weaknesses. You may say that we, too, can do the same, but if that's the case, a test server should be made available and the contest should explicitly try to get as many people as possible to break it.
This contest is interesting, but it's too artificial. As just one example of why that's the case: breaking real-world crypto often relies on side channel attacks, for instance timing attacks, and there's no opportunity of employing those attacks here due to the artificial nature of the contest.
Once again, if people here are interested in a secure alternative to Telegram that doesn't rely on public stunts for cryptanalysis, then check out TextSecure. It was designed by cryptographers, is open-source, and has been studied in detail for years. https://whispersystems.org/
EDIT: It appears Telegram is also vulnerable to MITM attacks. This is the NSA's preferred method of gathering info, so this is the most likely attack vector against Telegram. Due to the design of the protocol, there seems to be no defense. https://news.ycombinator.com/item?id=6931892
Telegram's response is "we protect against this because if you've initiated a secret chat previously, then you're protected." However, this isn't true. 1) a global adversary like the NSA can (and will, if they become interested in Telegram) simply MITM every secret chat session when they're first initiated; therefore if you use Telegram, you should assume the government has your data anyway, since this protocol offers no protection against mass snooping. 2) Secret chats aren't even the default type of chat in Telegram anyway, making it very unlikely that users will be protected by it. The defaults need to be secure.
Moxie is a great researcher and WhisperSystems seem serious. However, I don't understand why you claim that TextSecure is designed by cryptographers.
From what I've seen, they use something called the "Axolotl Ratchet", developed by Trevor Perrin. A quick search of his name didn't yield any crypto papers / research by him.
Also, you write "and has been studied in detail for years"
There are no links/references to code/protocol reviews in the WhisperSystems website.
Again, I have the utmost respect for their research, it's just that from the side of a non-crypto-versed user/coder, Telegram and TextSecure look the same.
Trevor Perrin worked at Cryptography Research (I mean, the domain name is cryptography.com!) for six years, which alone should probably be enough to call yourself a cryptographer. His other work outside of CRI is also really quite prolific.
> Again, I have the utmost respect for their research, it's just that from the side of a non-crypto-versed user/coder, Telegram and TextSecure look the same.
Yep, it's frustrating to be the quixotically genuine seller in a market for lemons.
I don't understand why you claim that TextSecure is designed by cryptographers. From what I've seen, they use something called the "Axolotl Ratchet", developed by Trevor Perrin.
> [...] the contest is fair because 1) the algorithm is completely specified, 2) there are no arbitrary definition of what winning means, and 3) the algorithm is public domain
Somewhat sad to see people on HN posting the Schneier link to counter the post without even bothering to read what it is about. I mean, it's almost like people have already formed opinions without giving the Telegram people a try. This is not how science works.
When Telegram showed their product on HN a few days ago, they were given constructive criticism and asked to justify the way they implemented their system. They responded by bragging about how many mathematics PHDs worked on the product.
Not satisfied at leaving it there, they then claimed that their crypto system doesn't need to be justified, because their customers aren't concerned about the specifics of their implementation of known broken algorithms.
Finally, they placed the burden of proof on the public, which doesn't work when it comes to cryptography.
They were given the opportunity to explain their design decisions in an environment of mutual respect, and they responded to this offer by stonewalling two of HN's resident security gurus.
"Since key length and key structure vary and since the encryption engine does not use any mathematical algorithms, reverse engineering is impossible and guessing is not an option"
This contest isn't a great example of the kind of contests he is talking about.
1) They are giving you the source code, protocol, and a tcpdump of all traffic between the chatters. You can even send messages via the protocol to one of the participants. Its not just here is some encrypted data, decrypt it.
2) They are offering a significant amount of money.
Wouldn't legitimate cryptography products also tend to offer such challenges? It's not much different than bug bounties, which are common and (at least according to my impression) well-accepted as a legitimate practice.
This is a bullshit challenge. The attack model in which it is set is nothing like the theoretical models cryptographic systems are designed to be secure against, and even less like how crypto software is actually attacked in practice. There is no possibility for known plaintext, chosen plaintext, chosen ciphertext, side channels, etc.
If they just encrypted their communications with AES-128 in ECB mode with a fixed random secret key, the challenge could not be won. And that's not even semantically secure. So we will learn absolutely nothing about the security of their software from the results of this challenge. Whoever designed this challenge is either extremely dishonest or knows nothing about cryptography.
If they really want to improve their software, they should offer a $200,000 bounty for a proof of concept implementation of an attack within their threat model.
Edit: I originally started this post with "...probably designed to get press rather than to actually improve the software...", which I have removed, since I have no evidence to support the claim.
I have a better challenge! From today until March 1, 2014, I will SSH into my server and type a secret email address on the command prompt. Send me an email to that address and tell me my crypto key, and I will allow you to pet my dog for 5 minutes. (Sorry, I do not have $200k in BTC, or any other currency, for that matter :(, but my dog is totally cute.)
The point is, the above challenge is impossible without a MITM attack, and that MITM attack has to take place when I first save the server keys on my computer. The point is that there are numerous cryptographic protocols available which can not be broken using currently available technology.
This contest will prove one thing, and one thing only, the cryptographic algorithm they are using is secure. And it SHOULD be, considering that there are a lot of publicly available secure algorithms. This contest, however, will not prove that the Telegram service is secure.
> This contest will prove one thing, and one thing only, the cryptographic algorithm they are using is secure. And it SHOULD be, considering that there are a lot of publicly available secure algorithms.
It doesn't even prove that. It proves that no one has told you about any flaws yet. The algorithm may be secure, but their implementation of it might have bugs.
Your challenge isn't at all hard. An attacker could get into your server using some other method besides breaking SSH then simply look at your bash history.
Most of the concerns people had were Telegram's servers acting maliciously or being coerced into acting maliciously, which is obviously not covered by this contest or the protocol they have designed. It's a bit disingenuous that Telegram is broken but not in a way that this bounty could pay for.
Yeah, it's probably against the rules of the competition and will get you arrested if you try. But I think if someone does break into their central server and wins the competition that way, they should still be paid out.
No, the goal of these security products is to defend against the government, not a random guy. In that context, it's extremely important that their server undergo the same level of cryptanalysis.
We already know the system is hopelessly vulnerable to server side MITM attacks, it makes no effort to defend against that attack model. It's mentioned in the comments that they might do manual key verification in the future, but that doesn't happen now. Compromise is silent.
That only protects against a MITM between peers who have communicated with a "secret chat" previously, not two fresh peers. As "secret charts" are disabled by default it's not really a defence against infiltration; users will presumably only enabled the "secret chat" mode when they have something sensitive to talk about.
When they do enabled it for the first time, we can instantly MITM them using the attack against the "image verification" I mentioned lower down (https://news.ycombinator.com/item?id=6932053), and we can assume that the conversation is worth our while listening in on. The user will hopefully expose themselves in the belief that they are safe, and the game is over.
It's simple unauthenticated Diffie-Hellman key agreement, which is known for MITM attack. Yes, you ask A to accept B's identity upon key exchange, but to what extend A would know B is really B not the server playing along? A plausible method would have A and B exchange certificates separate from the Diffie-Hellman key exchange process, and use those as the identity verification mechanism.
Not only is it possible, they are doing it already. I installed telegram on two devices (android and ipad) and they somehow were both able to decrypt incoming messages. How did the second device get the key..?
Ah! You were mistaken in the functioning of the service (I thought this might happen). You have to specifically ask for a secure chat with a button press, normally everything is effectively plaintext.
I'm afraid breaking into Telegram's central server (by the way, there is no such thing) will hardly enable you to decipher end-to-end encrypted secret chats. But certainly worth trying anyway.
It will allow you to conduct a man-in-the-middle attack on all encrypted traffic though, which would certainly be enough to read messages in plaintext.
This is irrelevant - the "secret chat" mode is not the default (according to someone else in this thread) and you're just shoving the key verification process off on to the user with these silly graphic patterns (which, if OTR is any indication, the user won't verify anyway).
This is still vulnerable to server-side _key_ MITM. It's the hushmail/iMessage/etc silent escrow key attack.
The interesting thing with the graphic patterns is that they're lossy. If you assume that a person will just describe the pattern or show a picture of them to one another, it becomes fairly easy to forge them.
Blue in the top and bottom, white line through the middle. So little information that anybody could simply brute force the keys until they found one that matched the description well enough.
I'd happily write a little attack for that, but it's clearly not "breaking" the system enough for the bounty.
Don't you think that you are basically fighting a needless uphill battle here? I mean, people crave a good encrypted communication system and you have the intent and the infrastructure in place, but you are shooting yourselves in the foot with your cryptographic design indulgence. This animosity will continue, because Telegram crew comes across as cocky and arrogant know-it-alls, and not because people think you cannot design a crypto protocol. The contest doesn't help a bit, it only further enforces the impression of arrogance on your end. This is not what you would've done if you in fact allowed for the existence of flaws in your design. You would've released an RFC instead.
I have all the sympathy for you. I don't doubt your motives, but you are setting yourselves up against skilled technical crowd. It has already started off on the wrong foot and this unfortunate dynamic will continue.
Perhaps consider offering an alternative crypto suite based on standard protocols? In parallel with what you have. Just reuse an existing crypto framework and redo transport layer to your needs.
abcd_f, I'm not part of the Telegram team, nor am I a cryptographer. However, I do support these guys, and for the last 3 days I saw the Telegram team diligently reply tech questions in Twitter, HN and blogs. I saw them collect questions from security experts and put up FAQs based on them http://core.telegram.org/techfaq or http://core.telegram.org/contestfaq as well as update the obscure parts of their documentation.
>> Perhaps consider offering an alternative crypto suite based on standard protocols? In parallel with what you have. Just reuse an existing crypto framework and redo transport layer to your needs.
Again, I am not cryptographer. But as a person who wants his data to be secure I don't see anything wrong with different teams trying different approaches. I 100% agree that people crave a good encrypted communication system, but I'm not sure it can be achieved in a world where everybody uses similar methods. What if some of the common "best practices" are intentionally promoted in the crypto-community as the best ones exactly because they contain flaws and backdoors?
Please allow me to give you an example of something that could be just that.
The Telegram team was criticized by some NH critics for their custom auth key exchange protocol. People asked – why take a random value from server and a random value from client and combine both with a creepy function? Why not, e.g., just generate a random value on the client and use RSA instead? Well, the answer is simple – the Telegram guys did not trust that the random value generated on the client-side was really random.
In August 2013 it turned out that their custom approach to protocol enabled Telegram to stay more secure when multiple other secure apps using more conventional solutions were hacked (http://android-developers.blogspot.ru/2013/08/some-secureran...). Many Bitcoin apps were cracked and people lost money, Open Whisper Systems (I noticed these guys are aggressively promoted here in the NH community as the epitome of best security) had to hasten to patch their RedPhone app to avoid that vulnerability.
So I'm kind of suspicious when I see strong pressure to enforce the use of common techniques and get rid of uncommon ones just because they are uncommon. I think the Telegram guys have the right to choose their own path, and I'm sure our society will only benefit from it.
Of course, building custom solutions is no easy task and requires a lot of effort. But I've seen some of the Telegram guys (yes, the "6 ACM champions") create things that I'd thought were impossible. Maybe I am wrong in putting my trust in their abilities, and I will be fined $200K+ for my naivete. However, I am willing to continue financing such contests, and I do hope that eventually we'll all get something much more valuable than $200K.
Well, to prove my point of you guys coming across as cocky know-it-alls. Here you just did it again, perhaps without realizing it -
> People asked – why take a random value from server and a random value from client and combine both with a creepy function?
People well-versed in applied crypto would never ask this question, because all standard key exchange protocols most certainly use both sides as a source of randomness. Furthermore - "creepy"? That's all you got away from all those comments that said your KDF was unproven, not peer-reviewed and weak in comparison? You basically cherry-picked a dumb question (I assume you haven't made it up) and then proceeded to demonstrate how clever you are. Guess what? You just reiterated basic facts, but assigned them to yourself.
Let me repeat what I said. Your problem is not your crypto. Your problem is the attitude.
If you were able to exploit vulnerabilities in the server, the software distribution, and the client... but that's not testing Telegram itself, it's testing everything in between -- including what's between the chair and keyboard.
Which is where the weaknesses (as witnessed by bitcoin shenanigans) lie, anyhow.
At least they'll put their money where their mouth is. I'm excited to see someone call out the naysaying masses on HN and stand by their product in this regard.
This doesn't cover the areas that most people highlighted as probable weaknesses which were largely related to the protocol rather than the cipher. There may be sufficient weaknesses in the protocol to expose the data with a passive analysis of the log but there are many more options if you can perform man in the middle attacks or find ways to change messages even without fully decrypting that would not win this competition but that would be widely regarded as breaking their system.
Unfortunately, this doesn't mean that it's secure. If someone breaks it, it means it's broken, but if nobody breaks it, it doesn't mean someone else can't break it (or hasn't already).
Agreed, but the tone of the previous discussion was definitely more along the lines of "This could never work, you guys don't know what you're doing."
If it proves resilient over 2.5 months of highly motivated attacks (motivated by both the money / "I-Told-You-So" factor), I think that's a fairly strong statement in their favor.
Excluding an entity like the NSA, who cares nothing for $200,000 (literally a rounding error in their budget), but everything for the information available for the taking.
While I agree with your point, immediately jumping to the NSA and their bottomless pool of resources and talent is kind of the new Godwin's law.
Logan's law: In any given discussion tangentially related to security, the thing presented as "secure" will be soon declared "definitely not secure"... because...NSA.
OK, but where the hell are they going to get 2.5 months of highly motivated attacks by highly skilled people? All the people I would want looking at this aren't going to waste such a huge chunk of their time analyzing some random phone app trying to make a name for themselves for a chance at a cash reward.
Bug bounties by big name companies that are actually after bugs rather than publicity haven't miraculously made all their software perfect. And they don't have an end date either.
I agree with you here. That is why such contests are going to be permanent in Telegram. New contests like this will be launched in March 2014 or earlier if anyone wins earlier. Consider the date for breaking Telegram open.
It actually makes things worse really "no hackers can break this!" sounds good on paper, but it could just mean your adversary has more to gain by the system not being publicly broken.
I don't see how it makes things worse. Surely it shows more if you gave hackers a big incentive to crack your encryption and they still didn't, compared to them not cracking it when there was no incentive. It is evidence that the reason they did not crack it was the difficulty of the problem, not just indifference.
A 73 day deadline on no notice to crack the system in a very specific way with no pay for people who succeed after the first is not a very big incentive. How many highly compensated security experts do you expect to stop doing their jobs for the opportunity to work for free?
Ok so here's what i understand what's going on here from reading the challenge and people's responses.
1) A classical crypto-challenge where you are given a cipher text and the algorithm and told to crack it is somewhat useless Because that would just prove strength of the primitive algorithm, not the system. Here you are given a scenario and told to use whatever attack is at your disposal to hijack the conversation and somehow retrieve the plain text. So while it is similar to in someways, but not exactly the same case.
2) People are not amused because they seem to find the vulnerability that upon initiation of the secret chat, the first time, the server can perform a MITM attack. Because apparently they use a Deffie-Helman key exchange where the server connects them to each other. So the server is in the best position to do the MITM. And since this contest does not allow to make that attack (even if u had the server in your control, the secret chat has been initiated already).
And hence everyone is frustrated because they seem to KNOW the system is weak, but they cant prove it right now. And this will lead to Telegram boasting in March.
This is like putting messages encrypted with ANY encryption algorithm, and ask people to guess the key. This has nothing to do with whether the communication protocol is secure or not.
This is such a sham. Here, I'll offer $2000 to break my plaintext crypto. Every morning, in the shower, I'll say a secret word. Email me the secret word and I'll send you $2000 in BTC.
I'll need to narrow it down further, but I'm pretty sure it's one of "Oh", "god", "groan", "I'm", "running", "late", "for", "work", "again". Hrm, does groan count as a word? How many guesses am I allowed?
A Russian friend of mine mentioned playing in an MMO with another guy called 'Krusk' for a year or so before realising that the other guy was also Russian, and 'Krusk' was the anglicised version of the Russian word for "the sound bones make when you crush them"...
The problem with such a test is that it is a limited attack surface compared with the real app in use. There is a log of messages that are encrypted but there are no possibilities of active attacks such as man in the middle attacks and others that attack the protocol rather than the encryption.
Of all the software branches out there in the world, crypto's are by far the coolest and scariest in my opinion. They wield obscure knowledge, have long beards, a white van full of tech, communicate in some obscure protocol with each other - oh man. :)
Someone will probably break an employee's computer and will just access private information, good game 200k. And then they will say it's unfair and I'm not paying you. And then HN will go crazy. Mark my word HN.
How is that supposed to be secure? All I need to snoop on your conversations is access to your phone for 1 minute to receive the activation code and delete message about new device connected to the account.
There's more than enough volume on any established exchange. $200,000 is roughly 380 BTC at the current price on Bitstamp (~$530). If you were to sell 380 BTC now on Bitstamp there are enough buy orders for the entire sell to be filled before the price got to $525.
Is that $200,000 in BTC valued at the time that the award will be given, or valued now? With the way things are going, not sure which would be better...
At the time of the reward. This is implicitly stated by the fact that he didn't specify the number of BTC. $500 is still a ton btw, two months ago a Bitcoin was worth $200.
to do this "right" shouldn't they release a hash now of the keys that will be exposed in march; as well as sign a message from a bitcoin address containing ~500btc?
Although i have limited knowledge of crypto, but the algorithm seems pretty similar to what is used in SSL with key exchange via DH and encryption via AES. Although i notice that instead of a server clients are doing key creation and exchange which is why Telegram may be calling the architecture 'decentralized'. What is new here, how is it Telegram's own encryption method? Just having a ssl like client to client security model is what is being coined as MTProto?
Pavel Durov and his brother. Pavel Durov got rich by copying facebook for the Russians. His brother is supposed to be a mathematician/computer scientist.
Could you show us examples of the actual message sent each day from Paul to Nick, except with the secret email address XXX'ed out? Is it the same message each day, or different?
Judging by the phone numbers, I would say that this is likely to be some form of elliptic curve cryptography with domain parameters different from the NIST and GOST standards.
I don't personally have the depth of experience with elliptic curves to go about cracking this crypto, but others have cracked elliptic curve algorithms. Perhaps one of those people will find this tidbit useful in narrowing the field.
Also, I would expect that at least some of the plain text is Unicode, probably the plane from 0400-04FF.
while the contest itself not wonderful, they do offer the source code, they offer constant traffic, they claim the contest is ongoing, so even if you don't win now, you might later.
The last point Schneider made of them winning but not telling you until they feel it's worth it is still valid.
Note to everyone in technology...Hacker News isn't the crowd that you need to impress.
The cryptanalysis community, in particular, has a small group of experts that can credibly critique your ideas. They would probably love to pick apart a new system...seriously in the hopes that it advances the art, but critically in the case that it doesn't.
Claims of some kind of "tightly knit" cabal of closed minded people excluding you would be a warning sign. (It sounds like creationism. Not that this is what these guys did. I'm just saying.)
Maybe instead of a competition they could have just approached some of the cryptanalysis community for an early look? Those guys could kick the tires and pass it on to others that they know. That really seems to be how this area works.
Did I miss somewhere where it stated this was HN-specific? This could just as easily have (and probably has) been posted to multiple communities, including ones that are more crypto-focused.
Just because it appears here does not in any way shape or form indicate that they're trying to impress the HN community, nor that they're specifically targeting HN.
https://www.schneier.com/crypto-gram-9902.html (1999)