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.

haha i read this headline and thought to myself "breaking textbook RSA is EXACTLY what I was just learning about in class today" and then I noticed one of the authors is my professor

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

Why not just pretend you do TLS and simply don't show MITM attacks to your users like the (also somehow Chinese) CM Browser does? https://medium.com/@dEad0r/cm-browser-insecurity-can-chinese...

One of the big issues with Textook RSA is that it really is what's in most textbooks as being RSA, and then corrected in a later section. For example "Cryptography Engineering" by Schneier, Ferguson, & Tohno does this, introducing RSA without padding in section 12.4 "RSA Defined" and then spends a page or so correcting the issues in section 12.5 "Pitfalls Using RSA. So of course someone going back to the definition when trying to implement something is going to miss the discussion about padding, as it's 5+ pages away!

I feel it would be better to simply define RSA encryption as follows:

    First, generate key pairs, exchange public keys, etc.
    Then, apply a padding function to your plaintext. The definition of a padding function can be found in section <Section number>.  
    Then compute c = m^e (mod n).  
    Send the resulting ciphertext c to the other party.

The padding discussion can still be located outside the definition of the mathematics, but the need to perform the padding is integral to this definition of RSA encryption.

So the browser uses a poor pseudorandom number generation, hard-coded symmetric keys, and 128 BIT RSA??? Not even 1024, just... 128? Well, congratulations on cracking it. The exploit they present is great though because it's so easy to understand, even if you only have basic understanding of cryptanalysis.