Breaking Textbook RSA Used to Protect the Privacy of Millions of Users

What's cool about this paper is the CCA2 attack on unpadded RSA in the middle of it. What's cool about that attack is how simple it is.

The setting, simplified: you send RSA(aes-key), AES(key, message). The server replies if the AES key it recovers from the RSA message successfully decrypts the AES ciphertext; the server is an oracle for whether the message is valid.

The attack is stupid simple: the attacker shifts 127 of the AES key bits off of the RSA message --- the attacker can do this, because RSA is homomorphic with respect to multiplication and thus malleable --- and then sends the bit-shifted RSA message along with an AES ciphertext encrypted with the 0b1000...0 AES key. If that elicits a server response, the attacker knows the bottom bit of the real AES key is 1. The attacker repeats with a 126 bit shift, then the math teachers and so on until everyone is eaten.

sidenote - user data collection by the browsers :

>Through reverse engineering, we have documented the encryption protocols used by QQ Browser to protect the trove of sensitive information each client uploads to QQ Browser’s servers (this is summarized in Section 2). This sensitive information includes International Mobile Equipment Identifier (IMEI) numbers, web pages vis- ited, locational data, and many other kinds of private data about a QQ Browser user. The possibility that Tencent shares this information with state actors is explored in existing reports [15], and QQ Browser’s data collection mirrors competing browsers such as UC Browser [12] and Baidu Browser [14].

The article describes the fact that the CM Browser ignores certificate errors and shows websites as though they were properly secured. Having an actual proper setup (with a trusted CA etc.) wouldn't help here, because a MITM attack would not be visible, because the middle man's certificate would be shown as valid in any case.

I assume Tencent's QQ Browser validates certificates properly, but combined with a horrible RSA implementation that's not worth anything. It's actually a more clever (less visible) way of pretending to establish secure/authenticated connections.

As I like to say, I know enough about crypto to know that I should never ever trust my knowledge about how to build a secure crypto protocol.

How funny! It's pretty cool learning things from the literal experts at the frontiers of human knowledge. I hope he or she teaches well as well!