Hacker News new | comments | show | ask | jobs | submit login
Breaking Textbook RSA Used to Protect the Privacy of Millions of Users (arxiv.org)
144 points by tptacek 32 days ago | hide | past | web | favorite | 30 comments

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.

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.

The more I learn the more I realize everything is a cat and mouse game. Commitment comes when you believe you've invested enough that you have more to lose if you stop than to keep going.

I appreciate your summary, and especially the way you ended it.

Interesting, I never thought of rsa being multiplicatively homomorphic.

That's the basis of several other classic attacks on RSA.

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

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!

Well, you're right, but keep in mind that breaking textbook RSA is not exactly "the frontiers of human knowledge", theory-wise. Most textbooks, in fact, will warn you that their description of RSA is vulnerable to chosen-plaintext attacks, and therefore you should add a padding scheme for your messages.

However, papers like this are extremely useful, as they show new ways to exploit this theoretical vulnerability in a real-world case study.

The attacks we're talking about aren't chosen plaintext; they're CCA2. And, in fact, RSA retains CCA2 vulnerability in its most common "padding" mode.

Then perhaps you could point me in the right direction:

where Cb = C (2^(be) mod(n)) (mod n)

I assume we are calculating Cb by encrypting the bit-shift and then applying it to C (which is already encrypted). Why do we need that last modulus at the end?

Haha let me get back to you once I finish replicating the paper (not using QQ but a sandbox) which we have to / get to do for hw :)

Which one?

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

There ought to be a full transparency report on every browser about what data is collected and shared and with whom. Even Firefox is no longer innocent.

> Even Firefox is no longer innocent

That's FUD


Review process: https://wiki.mozilla.org/Firefox/Data_Collection and not only is the source available, you can inspect opt-in metrics in about:telemetry, and see aggregated metrics at telemetry.mozilla.org (no other vendor will share that with you)

> There ought to be a full transparency report on every browser...

Yes, but not all browser vendors care about your privacy. So if privacy matters to you use Firefox :)

You must have missed this:


And I do use Firefox.

But they really should not have done that, even if in the end the actual harm done was nil it broke trust.

There is also this:


I actually take exception to your classifying my comment as FUD, I'm in nobody's pocket (pun intended) and the worst you could accuse me of is being wrong. That said I was happy to trust the Mozilla of the past a lot more than I'm willing to trust the Mozilla of the present. Their forced upgrade strategy breaking my workflow and the Mr. Robot episode on top of that did little to assure me that they still have my best interest in mind. The thing that keeps me from switching is that I'm pretty sure all the competition is much worse.

What data was collected and shared by that extension?

I did not claim any data was shared by that extension.

If privacy matters to you use Firefox... but make sure you turn off all the telemetry spyware first and make sure you're not on the beta channel. Firefox downloads in Germany should aditionally be inspected for cliqz spyware.

jaquesm is merely pointing out that "use Firefox" needs a disclaimer today, whereas in the past one could simply use Firefox out of the box.

Calling telemetry spyware is also FUD, see about:telemetry.

But that's beside the point, jaquesm said he expected browser vendors to clearly state what information they collect, I think Mozilla does a pretty comprehensive job at that:


And equating all data collection with spyware does NOT help win the battle. We're all on the same side here, but blowing things out of proportions doesn't serve the goal. It makes people give up.

It's fair to disagree with some decisions, and you don't have to opt-in for telemetry, but calling it spyware is unfair. It fair for you to say that you don't think it's necessary for your browser to collect performance metrics, and it's fair for you to not opt-in.

Equating things you dislike or find unnecessary with spyware is very dangerous. It gives other people the idea that browser choice doesn't matter. That privacy is impossible.

Note: we see extremism and exaggeration like this many places (politics included), and we have to be the ones holding each other to be reasonable. Otherwise, the opposition will frame us all as fanatics :)

@"equating all data collection with spyware does NOT help win the battle" ... maybe, maybe, lying to yourself that a corrupt, puppet-party A is better than also corrupt, puppet-party B or that one user-fingerprinting tool is better than another because the first one tells you a nice story of all the insignificant data it collects .. is actaully whats not helping in the "battle"! People like you are the ones that steer all the anger back into choosing between "jack johnson OR john jackson" - to take one popular but to-the-point reference - and vent that anger that could otherwise be used more creatively towards a real solution on pointless battles like the one above!

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

If you own the machine simply install a CA. Instant trusted everything. Be sure to drop those pesky certificate pinning headers in http though.

In fact I believe sslstrip can do all this for you. Including giving it a CA to generate certificates out of.

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.

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.

I disagree. There are many other subtle ways to do things wrong about RSA (and almost any other system); If you can't be bothered to read and comprehend the entire section about RSA implementations before trying to do that, you are going to fail in many other ways as well.

For a practitioner's book, it's probably worthwhile to introduce the doom principle[0] early on, and refer to it later in contexts like this one where taking it into account would save your ass. But it's no replacement for reading the entire section about the thing you are implementing.

[0] https://web.archive.org/web/20170930085357/https://moxie.org... - unfortunately, the link on moxie.org is currently broken.

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.

The paper statss that 1024bit RSA is used.

As a reference point, on Ti89 it takes about a minute to factorize 120bit RSA-style product of two primes, extrapolating from that you probably can break 128bit RSA on that without changing batteries.

Yes, they state that 1024 bit RSA was used but they also mention that older versions of the browser mistakenly used 128 bit RSA... probably because they were using 128 bit AES and some developer didn't know any better! Or maybe the government told them 128 bit was the maximum they were allowed to use on any cipher whether it was symmetric or asymmetric. https://imgur.com/a/XA91L

Applications are open for YC Summer 2018

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact