9 ms·

A Crypto Challenge for the Telegram Developers (2013)

77 points by zerognowl 10y ago

jbyers 10y ago
(2013)
krick 10y ago
So, did something change over the last 3 years? Is it still unknown if Telegram protocol is ok?
- jszymborski 10y ago
  I think the encryption has been known to be bunk for quite some time now [1] [1] https://eprint.iacr.org/2015/1177.pdf https://eprint.iacr.org/2015/1177.pdf [2] http://www.alexrad.me/discourse/a-264-attack-on-telegram-and-why-a-super-villain-doesnt-need-it-to-read-your-telegram-chats.html http://www.alexrad.me/discourse/a-264-attack-on-telegram-and... [3] https://unhandledexpression.com/2013/12/17/telegram-stand-back-we-know-maths/ https://unhandledexpression.com/2013/12/17/telegram-stand-ba...
- GranPC 10y ago
  Telegram set up a second crypto contest in which active attacks were allowed. https://telegram.org/blog/cryptocontest https://telegram.org/blog/cryptocontest
saycheese 10y ago
ATTN Moxie: How is Signal secure from the NSA when you force each user to provide their IMEI and mobile phone number when they create an account?
- sctb 10y ago
  Please stop harping about this, especially in unrelated threads. It distracts from the thoughtful kind of discourse that this site is for.
schlowmo 10y ago
Original HN discussion from three years ago: https://news.ycombinator.com/item?id=6936539 https://news.ycombinator.com/item?id=6936539
i336_ 10y ago
Just for the fun of it, what tools could be used to bypass the crypto used in this post?
- schoen 10y ago
  > 1. Alice generates a random 32 byte value, super_secret, using the NSA backdoored random number generator, Dual_EC_DRBG. The Dual_EC_DRBG backdoor was described by some sources as having a "NOBUS" vulnerability (only NSA knows the secret parameters necessary to exploit it). Interestingly, it might not be directly possible to exploit this in this setting because in the published attacks, the attacker needs to see some RNG output in order to deduce other RNG output. If this step is the only use of Dual_EC_DRBG in Moxie's protocol, perhaps the attacker doesn't have the necessary information. > 2. Alice sends a message to Bob asking for his public key. Bob responds with bob_public, an 896bit RSA public key. Nothing is signed. Nothing is verified. We’re just kinda hoping there was no MITM attack. First, an attacker could substitute a different bob_public value in the unauthenticated traffic and then do an active MITM attack (continuing the two sides of the protocol separately with both parties). Second, an attacker can factor the 896-bit modulus. A research group previously demonstrated an ability to factor a 768-bit modulus. While 896 bits is harder, hardware has also gotten cheaper in the meantime. https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 > 3. Alice encrypts super_secret with bob_public using “textbook RSA” and sends it to Bob. No random padding of any kind, just zeroes. e = 65537. Some of the problems with not using message padding are described in https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf, although I think there are others. This is also described in https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_against_plain_RSA https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga... I actually suspect that the best-known attacks don't apply here because the plaintext is strongly random, sent only once, and Alice and Bob don't perform many other RSA operations that an attacker can control or observe, but it would be worth thinking about more. > 4. 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). Not clear that MD2 is a risk here either: it has flaws as a hash (for example, it is vulnerable to preimage and collision attacks), but these don't obviously make the secret key that it outputs more predictable in itself. > 5. Alice sends her message to Bob by computing ciphertext = message xor message_key. Aged to perfection, our XOR encryption is even older than your 70s era crypto, so what’s up now? If this is repeating-key XOR (that is, if the ciphertext is longer than 128 bits and so the key must be reused), this is a big problem because the attacker can shift the ciphertext by 128 bits and XOR it against itself, which yields plaintext ⊕ shifted_plaintext, because the two copies of the key will cancel out. If the plaintext is actual text, there are many possible regularities that could be observed; for example, when two letters occur in identical positions, the result will be 0, while when a letter and a space occur in the same position, the result will be the same letter but with swapped case. Correctly guessing a plaintext byte at any position allows determining the secret key byte at the corresponding position. This is discussed in more detail at https://crypto.stackexchange.com/questions/2249/how-does-one-attack-a-two-time-pad-i-e-one-time-pad-with-key-reuse https://crypto.stackexchange.com/questions/2249/how-does-one... https://crypto.stackexchange.com/questions/6020/many-time-pad-attack https://crypto.stackexchange.com/questions/6020/many-time-pa... To summarize, I think the big problems are * no authentication, permitting undetected active MITM * short RSA key, permitting factorization of modulus (hence passive decryption, even retrospectively) * apparent reuse of symmetric key for each 128-bit block of the message, allowing standard attacks against the "many-time pad" I don't believe the Dual_EC_DRBG, lack of RSA padding, or MD2 create obvious vulnerabilities in this context, or, if they do, they aren't any worse than the ability to do the active MITM due to lack of authentication for bob_public. :-)

77 points by zerognowl 10y ago

jbyers 10y ago

(2013)

krick 10y ago

So, did something change over the last 3 years? Is it still unknown if Telegram protocol is ok?

jszymborski 10y ago
I think the encryption has been known to be bunk for quite some time now [1] [1] https://eprint.iacr.org/2015/1177.pdf https://eprint.iacr.org/2015/1177.pdf [2] http://www.alexrad.me/discourse/a-264-attack-on-telegram-and-why-a-super-villain-doesnt-need-it-to-read-your-telegram-chats.html http://www.alexrad.me/discourse/a-264-attack-on-telegram-and... [3] https://unhandledexpression.com/2013/12/17/telegram-stand-back-we-know-maths/ https://unhandledexpression.com/2013/12/17/telegram-stand-ba...
GranPC 10y ago
Telegram set up a second crypto contest in which active attacks were allowed. https://telegram.org/blog/cryptocontest https://telegram.org/blog/cryptocontest

saycheese 10y ago

ATTN Moxie: How is Signal secure from the NSA when you force each user to provide their IMEI and mobile phone number when they create an account?

sctb 10y ago
Please stop harping about this, especially in unrelated threads. It distracts from the thoughtful kind of discourse that this site is for.

schlowmo 10y ago

Original HN discussion from three years ago: https://news.ycombinator.com/item?id=6936539 https://news.ycombinator.com/item?id=6936539

i336_ 10y ago

Just for the fun of it, what tools could be used to bypass the crypto used in this post?

schoen 10y ago
> 1. Alice generates a random 32 byte value, super_secret, using the NSA backdoored random number generator, Dual_EC_DRBG. The Dual_EC_DRBG backdoor was described by some sources as having a "NOBUS" vulnerability (only NSA knows the secret parameters necessary to exploit it). Interestingly, it might not be directly possible to exploit this in this setting because in the published attacks, the attacker needs to see some RNG output in order to deduce other RNG output. If this step is the only use of Dual_EC_DRBG in Moxie's protocol, perhaps the attacker doesn't have the necessary information. > 2. Alice sends a message to Bob asking for his public key. Bob responds with bob_public, an 896bit RSA public key. Nothing is signed. Nothing is verified. We’re just kinda hoping there was no MITM attack. First, an attacker could substitute a different bob_public value in the unauthenticated traffic and then do an active MITM attack (continuing the two sides of the protocol separately with both parties). Second, an attacker can factor the 896-bit modulus. A research group previously demonstrated an ability to factor a 768-bit modulus. While 896 bits is harder, hardware has also gotten cheaper in the meantime. https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 > 3. Alice encrypts super_secret with bob_public using “textbook RSA” and sends it to Bob. No random padding of any kind, just zeroes. e = 65537. Some of the problems with not using message padding are described in https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf, although I think there are others. This is also described in https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_against_plain_RSA https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga... I actually suspect that the best-known attacks don't apply here because the plaintext is strongly random, sent only once, and Alice and Bob don't perform many other RSA operations that an attacker can control or observe, but it would be worth thinking about more. > 4. 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). Not clear that MD2 is a risk here either: it has flaws as a hash (for example, it is vulnerable to preimage and collision attacks), but these don't obviously make the secret key that it outputs more predictable in itself. > 5. Alice sends her message to Bob by computing ciphertext = message xor message_key. Aged to perfection, our XOR encryption is even older than your 70s era crypto, so what’s up now? If this is repeating-key XOR (that is, if the ciphertext is longer than 128 bits and so the key must be reused), this is a big problem because the attacker can shift the ciphertext by 128 bits and XOR it against itself, which yields plaintext ⊕ shifted_plaintext, because the two copies of the key will cancel out. If the plaintext is actual text, there are many possible regularities that could be observed; for example, when two letters occur in identical positions, the result will be 0, while when a letter and a space occur in the same position, the result will be the same letter but with swapped case. Correctly guessing a plaintext byte at any position allows determining the secret key byte at the corresponding position. This is discussed in more detail at https://crypto.stackexchange.com/questions/2249/how-does-one-attack-a-two-time-pad-i-e-one-time-pad-with-key-reuse https://crypto.stackexchange.com/questions/2249/how-does-one... https://crypto.stackexchange.com/questions/6020/many-time-pad-attack https://crypto.stackexchange.com/questions/6020/many-time-pa... To summarize, I think the big problems are * no authentication, permitting undetected active MITM * short RSA key, permitting factorization of modulus (hence passive decryption, even retrospectively) * apparent reuse of symmetric key for each 128-bit block of the message, allowing standard attacks against the "many-time pad" I don't believe the Dual_EC_DRBG, lack of RSA padding, or MD2 create obvious vulnerabilities in this context, or, if they do, they aren't any worse than the ability to do the active MITM due to lack of authentication for bob_public. :-)