A Crypto Challenge for the Telegram Developers (2013)(moxie.org)
moxie.org
A Crypto Challenge for the Telegram Developers (2013)
https://moxie.org/blog/telegram-crypto-challenge/
10 comments
Just for the fun of it, what tools could be used to bypass the crypto used in this post?
> 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
> 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, although I think there are others. This is also described in
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...
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. :-)
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
> 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, although I think there are others. This is also described in
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...
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. :-)
Wow, thanks for the in-depth reply (on a post that doesn't look like it's going to get a lot of views).
I'll admit my ignorance of information security (it's something I'm working on), but as a naïve reader I got the impression (considering the supplied ciphertext block) that the article was using paper-tiger/theater encryption that was practically broken in the sense that (given some CPU/GPU time) the tools existed to decrypt it. (Hence my "just for the fun of it".)
Thanks a lot for the links, I'll definitely be checking them out!
I'll admit my ignorance of information security (it's something I'm working on), but as a naïve reader I got the impression (considering the supplied ciphertext block) that the article was using paper-tiger/theater encryption that was practically broken in the sense that (given some CPU/GPU time) the tools existed to decrypt it. (Hence my "just for the fun of it".)
Thanks a lot for the links, I'll definitely be checking them out!
Original
HN discussion from three years ago:
https://news.ycombinator.com/item?id=6936539
https://news.ycombinator.com/item?id=6936539
So, did something change over the last 3 years? Is it still unknown if Telegram protocol is ok?
I think the encryption has been known to be bunk for quite some time now [1]
[1] https://eprint.iacr.org/2015/1177.pdf [2] http://www.alexrad.me/discourse/a-264-attack-on-telegram-and... [3] https://unhandledexpression.com/2013/12/17/telegram-stand-ba...
[1] https://eprint.iacr.org/2015/1177.pdf [2] http://www.alexrad.me/discourse/a-264-attack-on-telegram-and... [3] https://unhandledexpression.com/2013/12/17/telegram-stand-ba...
Telegram set up a second crypto contest in which active attacks were allowed. https://telegram.org/blog/cryptocontest
(2013)
saycheese(1)