Hacker News Reader

Comment by tonysdg | Hacker News Reader

Because it means that some RSA keys may be weaker than others. Without diving too far into the mathematics of it, the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is incredibly hard. This conjecture, if true, means that for some gigantic non-prime numbers, it is easier than expected (even if only slightly so) to figure out which two prime numbers were used.

View on HN

He's asking why, if you only have a 2^-730 chance of generating one of these primes at random, would you care about that risk? Single-bit memory or computation faults can devastate the security of cryptographic operations, and they're multiple orders of magnitude more likely to recur in a single computation than generating those particular primes.

In addition to tptacek's comment, we already know a bunch of ways where the RSA primes would be weak. And we don't check for them when generating RSA primes because they have almost no chance of occurring.

Because it lets you ship crypto-systems with keys that appear to be strong on inspection but which are actually weak (if you deliberately want to ship backdoored crypto).

There are lots of ways to ship those systems without a "backdoor" that involves keys that will never occur once in the wild, let alone repeatedly. Why would they use an elaborate scheme that screams tampering?

> the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is incredibly hard.

While it is true that if we can factor a number that is a composite of two primes is sufficient to break RSA, the security of RSA is based on a weaker property (cf. https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem...):

Given two prime number p,q >= 3, let n := p * q. Let lambda(n) = lcm(p-1, q-1) (Carmichael's totient function). A public key then is (n,e), where 1 < e < lambda(n). If one knows p,q one can compute the corresponding private key (n,d), where d * e = 1 mod lambda(n) (which is considered to be a hard problem if one does not know p,q).

The RSA problem asks that given a c \in {0, ..., n-1}, find an m \in {0, ..., n-1} such that c = m^e mod n.

It is easy to check how this problem becomes simple if we can factor n (then we simply can find the private key). But it is an open problem whether solving the RSA problem is as hard as factoring or not.

OK, but very few primes satisfy this hypothesis, so why's it a big deal? Is some generalization of the conjecture conjectured?

Not every key generated with the recently discovered ROCA vulnerability was easily factored either. But there are lots of keys out there... And an important key might be one of the vulnerable ones.

Any kind of weakness like this is bad. Especially if more vulnerabilities like this exist it gets even worse.

OK, but the probability of choosing a prime satisfying this hypothesis is infinitesimal. Unless there's some bias in the way primes are chosen for RSA keys?

There's two problems as I see it.

#1- What if an attacker was able to modify how you pick your RSA keys? You could prove that hey, this RSA key is safe, and it's roots are prime, and I just generated it. But unbeknownst to you, your attacker is cracking your RSA key as soon as you start using it. The NSA is probably already trying to attack this way.

#2- What if this isn't an isolated case, but the first discovery in an entire class of prime numbers? What if there's a whole spectrum of 'strength' of every prime and we had no idea? We need to research this topic more to find out for sure.

See above, there's already 1000s of weak keys on github and other places, significantly more than you'd expect if they were randomly generated.

Problem is that it's hard to tell the difference between poor implementations and sabotaged implementations.

We're generally able to trace those weak keys back to specific implementation faults. All it takes is one widespread RSA implementation to do primegen badly for us to get hundreds more weak keys on Github.

You could use any abelian variety with CM to try something similar but I haven't worked out the details. But you probably will only get special forms very few primes fit.

What is CM?

Complex multiplication, which for historical reasons is used to refer to extra endomorphisms. CM is why the point has an easily findable order.

Reply on news.ycombinator.com