6 ms·

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.

by 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.
    - tveita 13y ago
      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-algorithm/ 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-products-are-affected-by-nsas-ability-to-crack-pseudo-random-number-gener http://security.stackexchange.com/questions/43164/which-prod...
      - tptacek 13y ago
        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.
- sdevlin 13y ago
  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.
- acqq 13y ago
  Dual_EC_DRBG is used: http://security.stackexchange.com/questions/43164/which-products-are-affected-by-nsas-ability-to-crack-pseudo-random-number-gener 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)
  - Swannie 13y ago
    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?
robryk 13y ago
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?
- sdevlin 13y ago
  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.
decasteve 13y ago
> 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.
- jacobolus 13y ago
  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).”
- sdevlin 13y ago
  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.

by sdevlin 13y ago

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.
  - tveita 13y ago
    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-algorithm/ 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-products-are-affected-by-nsas-ability-to-crack-pseudo-random-number-gener http://security.stackexchange.com/questions/43164/which-prod...
    - tptacek 13y ago
      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.
sdevlin 13y ago
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.
acqq 13y ago
Dual_EC_DRBG is used: http://security.stackexchange.com/questions/43164/which-products-are-affected-by-nsas-ability-to-crack-pseudo-random-number-gener 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)
- Swannie 13y ago
  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?

robryk 13y ago

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?

sdevlin 13y ago
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.

decasteve 13y ago

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

jacobolus 13y ago
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).”
sdevlin 13y ago
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.