Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arxiv.org

Post reply on HN
Print view View original

21–30 of 31 posts

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

#21

Post by jopsen »

blub wrote: post #17
jopsen wrote: post #11

Earlier quoted context omitted.

> Even Firefox is no longer innocent That's FUD https://www.mozilla.org/en-US/privacy/firefox/ 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…

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:

https://www.mozilla.org/en-US/privacy/firefox/

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 :)

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

#22

Post by dfox »

omarforgotpwd wrote: post #18

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.

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

#23

Post by blablablaber »

jopsen wrote: post #21
blub wrote: post #17

Earlier quoted context omitted.

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: https://www.mozilla.org/en-US/privacy/firefox/ 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 pro…

@"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!

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

#24

Post by thathappened »

jcranmer wrote: post #8
tptacek wrote: post #2

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 1…

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.

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

#25

Post by tptacek »

infogulch wrote: post #16
tptacek wrote: post #2

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 1…

Interesting, I never thought of rsa being multiplicatively homomorphic.

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

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

#26

Post by tptacek »

lou1306 wrote: post #20
tomrod wrote: post #10

Earlier quoted context omitted.

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…

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.

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

#27

Post by omarforgotpwd »

dfox wrote: post #22
omarforgotpwd wrote: post #18

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

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

#28

Post by SAI_Peregrinus »

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

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

#29

Post by Toast_25 »

opsiprogram wrote: post #9

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

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?

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

#30

Post by beagle3 »

SAI_Peregrinus wrote: post #28

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 w…

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.

Post reply on HN