Hacker News Reader

Comment by ge0rg | Hacker News Reader

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.

View on HN

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?

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)

Also no side channel observations.

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.

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.

This is an excellent answer. You get right to the core of it, quite clearly, which is that this has naught to do with the crypto itself. But that:

> If this counter-challenge cannot be broken, then it shows that the challenge issued by Telegram is no proof of security.

The contest limitations rule out most of the likely attack vectors for breaking the protocol in the real world. It's like saying "Our bank vans are 100% secure. Just try stealing money from them without puncturing our tires or bribing one of our employees."

Thanks - this is the best analogy I've heard so far.

It's only secure if attackers have < $2 million in resources, or the contest expires within 2000 years for an attacker with 1 PC. Or... and this is a big OR can't position themselves between you and the recipient.

eg. You aren't using Wifi, your network is fully secured, no one has access to any router along the way, etc.

Lets put it this way, if you're using Telegram / MarlinSpikeGram and you and I are in the same coffeeshop I can read your messages.

There are attacks that are possible in the real world that Telegram's (& this example) contest deny. It's like tying a person to a chair, and challenging them to run a marathon, to prove that humans can't run marathons. In the real world, people aren't tied to chairs and humans can run marathons.

Well, not entirely the same framing.

For $200k one could probably brute-force an 896-bit RSA key. ;)

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.

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

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.

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.

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), 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.

>Amazon EC2

I'm not sure how they compare in practice, but it might be worth calculating how many hours an Amazon G2 instance would take, using their high-end graphics cards as CUDA processors. I think the cost per performance ratio is much lower, and that could change the equation in the other direction.

I really don't know how well the required operations execute on a GPU. I've only skimmed the RSA 768 paper to find that line.

Fair enough. I've read that using CUDA (or another GPU-based language) you can get at least a 10x the GFLOPS of a 4-CPU Xeon [1], though, and RSA cracking should easily parallelize, if I'm understanding the process correctly. And the high-end NVidia cards in the G2 instances have 1,536 CUDA cores each. No, I'm not kidding. The one benchmarked in the link above is about 1/3 the GFLOPS of the one in the G2 instances.

And it looks like a reserved G2 instance is 0.65/hour (though can be lower on the spot market and in the reserved instance marketplace). So if there's a 120x speed improvement over the "single core 2.2GHz AMD Opteron" (and that's assuming each core is as fast as the Xeon core above), for only 11x the cost...well, it gets a lot cheaper.

In fact, it ends up, if I haven't done my math wrong, at about $94,900 of full instance time (less if you get spot or reserved instances). [2] To win the $200k prize. Hmm....

[1] http://archive.benchmarkreviews.com/index.php?option=com_con...

[2] "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron": That's 17,520,000 hours. If the G2 instance gets you 120x performance improvement, that's 146,000 hours. At 0.65/hour, that's $94,900.

Reply on news.ycombinator.com