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

Unsafe RSA primes conjectured

mathoverflow.net

Post reply on HN
Print view View original

51–59 of 59 posts

Re: Unsafe RSA primes conjectured

#51

Post by wolfgke »

tonysdg wrote: post #14
AlexCoventry wrote: post #10

Why is this significant?

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

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

Re: Unsafe RSA primes conjectured

#52

Post by marcosdumay »

How long until we actually start using curve 25519 for everything?

EDIT: On a second though, a backdoored curve 25519 implementation might be even harder to discover, because any backdoored PRNG could be used, and there are no outstanding structure to them... My comment only makes sense if those keys were generated by mistake.

Re: Unsafe RSA primes conjectured

#53

Post by xelxebar »

srcmap wrote: post #2

A related public key news: https://arstechnica.com/information-technology/2017/10/crypt... It compromises the TPM 1.2 and Microsoft Bitlocker HDD encruption. The researchers also scanned the Internet for fingerprinted keys and quickly found hits in a variety of surprising places. They found 447 fingerprinted keys—237 of them factorizable—used to sign GitHub submissions, some for very popular software packages. GitHub…

Wait. My Yubikey 4-generated let's might be bunk? How can I check this?

Re: Unsafe RSA primes conjectured

#54

Post by slackingoff2017 »

EwanToo wrote: post #40
slackingoff2017 wrote: post #33

Earlier quoted context omitted.

Don your shiny crinkly hats, but after https://en.m.wikipedia.org/wiki/Dual_EC_DRBG I started believing that NSA involvement is not subtle in their exploits. They only need to fool laymen, and backdoored primes are an easy way to do so. The number of true cryptography experts beyond their walls is a dozen in the world at best. Case in point https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein . And BTW he's been sued…

Do you honestly believe that China and Russia don't take cryptography seriously, and between them only employ a tiny handful of experts...?

The opposite. Government entities suck up all the world's crypto experts leaving very few working in the publics interest.

Re: Unsafe RSA primes conjectured

#55

Post by peoplewindow »

jabot wrote: post #41
cobbal wrote: post #11

Earlier quoted context omitted.

Assuming at least 768 bits (an RSA number of this size has been factored), the gaps between such numbers are more than 10^232. Even if every number of this form was prime, the prime number theorem tells us we can expect one out of every 10^229 primes to be weak. There could or course be a larger class of such easy primes, but it seems like it's extremely unlikely a prime of this particular form would ever be generate…

Thanks for that answer. These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.

Very likely that they've been used for that.

I once talked to someone who had worked at a company in the 90s that was shipping crypto software. This was shortly after Snowden, so the topic of backdoors came up. He said that back in those days, they'd been visited by the NSA and told to change the primes they were using, otherwise they wouldn't get export clearance. He said they couldn't figure out what was different about the primes they were given - the number passed primality testing, so they switched to using them to avoid being denied export clearance. His theory was that they were pseudoprimes that somehow passed testing because primality tests were statistical and not definitive.

But I guess this is an alternative explanation that would also make sense.

Re: Unsafe RSA primes conjectured

#56

Post by peoplewindow »

tptacek wrote: post #25
tonysdg wrote: post #14

Earlier quoted context omitted.

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

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.

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

Re: Unsafe RSA primes conjectured

#57

Post by tptacek »

peoplewindow wrote: post #56
tptacek wrote: post #25

Earlier quoted context omitted.

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.

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?

Re: Unsafe RSA primes conjectured

#58

Post by tptacek »

slackingoff2017 wrote: post #54
EwanToo wrote: post #40

Earlier quoted context omitted.

Do you honestly believe that China and Russia don't take cryptography seriously, and between them only employ a tiny handful of experts...?

The opposite. Government entities suck up all the world's crypto experts leaving very few working in the publics interest.

You mean except for every professor, postdoc, and grad student working in every crypto research group at every large CS department in the world?

Re: Unsafe RSA primes conjectured

#59

Post by TomatoSauceCat »

Just another example of the type of ignorance we have been dealing with ever since the day RSA was invented. Unfortunately people still don't get the Rivest-Silverman paper: http://people.csail.mit.edu/rivest/RivestSilverman-AreStrong...

To be brief, there exists infinitely many algorithms that rule out classes of so-called "weak primes", or "weak moduli." Such attacks are meaningless because you will not know which algorithm will crack a randomly chosen modulus until you try it. By trying algorithm after algorithm similar nature to this, your expected run time is exponential before you find one that works. Which essentially means that the concepts of "weak moduli" and "weak primes" are misnomers.

For an algorithm like this to be meaningful, the density of primes that it rules out needs to be significant. In this case, it is insignificant (it is exponentially small).

Post reply on HN