Comment by sdevlin | Hacker News Reader

Comment by sdevlin | Hacker News Reader

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?

You're right and I'm wrong. Mea culpa. I dashed these off quickly.

Unfortunately I can't edit anymore, so the erroneous #5 will have to stay there.

The main bad thing here is the null padding (covered in #4). This gives the attacker a lot of knowledge of the plaintext (the most significant bytes are all null), which can be used to decrypt if this format is validated on the other end. Bleichenbacher's attack only requires knowledge of one plaintext byte (the leading 02h), and we have many.

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?

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.

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.

This is disingenuous. RSA used it as a default in a commercial crypto library, as you must know. End users won't generally be aware that it's being used in a product, but that doesn't mean it isn't out there.

It is unlikely that most developers changed the default unless it was having a noticeable impact on performance, which wouldn't be the case if it was just used for key generation.

http://www.wired.com/threatlevel/2013/09/rsa-advisory-nsa-al...

> In its advisory, RSA said that all versions of RSA BSAFE Toolkits, including all versions of Crypto-C ME, Micro Edition Suite, Crypto-J, Cert-J, SSL-J, Crypto-C, Cert-C, SSL-C were affected.

> In addition, all versions of RSA Data Protection Manager (DPM) server and clients were affected as well.

> “Every product that we as RSA make, if it has a crypto function, we may or may not ourselves have decided to use this algorithm,” said Sam Curry, chief technical officer for RSA Security. “So we’re also going to go through and make sure that we ourselves follow our own advice and aren’t using this algorithm.”

Here's someone who has dug up a decent amount of real-world products:

http://security.stackexchange.com/questions/43164/which-prod...

You probably don't use any product that uses BSAFE.

For whatever it's worth, for people who think this point is all part of some elaborate edifice of sticking up for NSA: I am now 99.9% convinced that Dual EC is in fact a backdoor, and while it's clumsy in a tradecraft sense (you can just look at it and see the problem), I've heard compelling scenarios in which it would have been effective.

I just don't think it's a backdoor that's relevant to modern software, or, even for its time (the early 00's), software that was in popular use.

What do you make of the list given in this other comment that includes copy machines and game consoles?

https://news.ycombinator.com/item?id=6940993

To be clear, I'm describing problems with Moxie's hypothetical broken protocol, not with Telegram. Telegram does not (as far as I know) use Dual_EC_DRBG.

Dual_EC_DRBG is used:

http://security.stackexchange.com/questions/43164/which-prod...

> Since we know the RSA BSAFE library uses Dual_EC_DRBG (...) by default, I would guess that this would be the main vector.

> As for the use of BSAFE, I can easily find (hint: use your favourite search engine to search for the terms "This product includes" "RSA BSAFE") implementations, oddly skewed towards imaging and gaming devices: surprisingly many printer/copier/fax devices use BSAFE, though for unknown purposes. Including Ricoh, Minolta, Océ/Canon, Brother, Fuji/Xerox, Epson ... Your Playstation (PDF), PSP, or your Nintendo DS wifi (PDF) Software from Adobe, Hitachi, Oracle and HP Some Nokia phones(PDF)

I thought the problem was the recommended implementation of Dual EC PRNG that was broken - the specific point selection that was mandated to be suitable for government use - the one that RSA used?

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

I think you missed: “Both Alice and Bob now compute message_key = MD2(super_secret) (we know you like dated crypto, so we thought you’d like the MD2 hash function).”

Sorry, I'm afraid my original post wasn't very clear. I was describing potential problems with Moxie's intentionally weak protocol, not with Telegram.

The hash in question is MD2 used to reduce the 32-byte random secret to a 16-byte shared encryption key. MD2 is weak, but I'm not sure if it matters in this context. As I said above though, I'm also not sure that it doesn't matter.

Reply on news.ycombinator.com