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

11–20 of 59 posts

Re: Unsafe RSA primes conjectured

#11

Post by cobbal »

wybiral wrote: post #4

How many primes within the usual range generated for RSA happen to fit the form 27 a^2 + 27 a + 7?

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 generated by chance.

Re: Unsafe RSA primes conjectured

#12

Post by wybiral »

cobbal wrote: post #11
wybiral wrote: post #4

How many primes within the usual range generated for RSA happen to fit the form 27 a^2 + 27 a + 7?

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…

Ah, thanks. That's exactly what I was wondering.

It's still interesting though.

Re: Unsafe RSA primes conjectured

#14

Post by tonysdg »

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

Re: Unsafe RSA primes conjectured

#15

Post by AlexCoventry »

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…

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

Re: Unsafe RSA primes conjectured

#16

Post by throwaway613834 »

slackingoff2017 wrote: post #6
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…

What are the odds that this was intentional? TPM and Bitlocker have been two of the biggest conjectured targets of compromise. To the point that most security people/libraries use neither. Maybe they were right? If this is true one of Stackoverflow comments is quite chilling It would be a terrible idea and it would raise suspicions of a deliberate trapdoor if the primes for RSA were chosen from a quadratic progressio…

> If this is true one of Stackoverflow comments is quite chilling

MathOverflow?

Re: Unsafe RSA primes conjectured

#17

Post by wybiral »

AlexCoventry wrote: post #15
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…

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.

Re: Unsafe RSA primes conjectured

#18

Post by AlexCoventry »

wybiral wrote: post #17
AlexCoventry wrote: post #15

Earlier quoted context omitted.

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?

Re: Unsafe RSA primes conjectured

#19

Post by mabbo »

AlexCoventry wrote: post #18
wybiral wrote: post #17

Earlier quoted context omitted.

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.

Re: Unsafe RSA primes conjectured

#20

Post by wybiral »

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…

More on the actual ROCA vulnerability for anyone curious:

https://crocs.fi.muni.cz/public/papers/rsa_ccs17

https://crypto.stackexchange.com/questions/52292/what-is-fas...

Post reply on HN