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

21–30 of 59 posts

Re: Unsafe RSA primes conjectured

#21

Post by slackingoff2017 »

throwaway613834 wrote: post #16
slackingoff2017 wrote: post #6

Earlier quoted context omitted.

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?

Haha same difference. Mathoverflow is just a lot more hardcore :)

Re: Unsafe RSA primes conjectured

#22

Post by tptacek »

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…

That comment isn't intended to be "chilling"; it's intended to be the opposite.

This is a terrible cryptographic backdoor. If you're going to backdoor cryptography, you do it cryptographically, so that only you and your partners can decrypt it (this is called a "NOBUS" backdoor, for "nobody but us"). The only reason nobody found the Infineon bug already is that nobody seriously looked for it.

The most plausible explanation for the Infineon bug is also the most widespread: there's prime number generation advice for quickly generating primes on low-power devices like smartcards, and that advice was badly flawed.

(This isn't the first time primegen bugs have created factorable public keys in the wild; Henninger has a similar attack relating to p = randomprime(start=0), q = randomprime(start=p)).

Re: Unsafe RSA primes conjectured

#23

Post by sliken »

mabbo wrote: post #19
AlexCoventry wrote: post #18

Earlier quoted context omitted.

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…

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.

Re: Unsafe RSA primes conjectured

#24

Post by tptacek »

sliken wrote: post #23
mabbo wrote: post #19

Earlier quoted context omitted.

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…

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.

Re: Unsafe RSA primes conjectured

#25

Post by tptacek »

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…

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.

Re: Unsafe RSA primes conjectured

#26

Post by tptacek »

gruez wrote: post #3
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…

is there a reason why bitlocker would use rsa for encryption? afaik how bitlocker worked with tpm was that it would generate a (symmetric) key, store it in the tpm, then seal it, binding it to the current PCR value. on boot, it would unseal it (which will succeed unless the PCR changed).

It doesn't. Intel-compatible TPMs do, and Bitlocker will take advantage of those to get a hardware root of trust for the volume master key. Without it, it'll use AES.

Re: Unsafe RSA primes conjectured

#27

Post by vel0city »

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…

The recent Infineon weakness is not a flaw in TPMs in general or Bitlocker. This is a flaw related to certain TPMs, and is only applicable to Bitlocker if you used those affected TPMs with Bitlocker. FWIW, this same flaw could relate to PGP keys generated with the affected TPMs. This same flaw was related to PIVs issued on Estonian IDs, which I doubt are commonly used for Bitlocker.

Re: Unsafe RSA primes conjectured

#28

Post by wybiral »

tptacek wrote: post #22
slackingoff2017 wrote: post #6

Earlier quoted context omitted.

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…

That comment isn't intended to be "chilling"; it's intended to be the opposite. This is a terrible cryptographic backdoor. If you're going to backdoor cryptography, you do it cryptographically, so that only you and your partners can decrypt it (this is called a "NOBUS" backdoor, for "nobody but us"). The only reason nobody found the Infineon bug already is that nobody seriously looked for it. The most plausible expla…

If you could introduce a bias in implementations to generate primes of the form more often than random then it could be useful, right?

I'm not wearing my tin foil hat so I realize that in order to do that in the first place you'd probably already have enough influence to do much more than this. But just for the sake of a hypothetical...

Re: Unsafe RSA primes conjectured

#29

Post by tptacek »

wybiral wrote: post #28
tptacek wrote: post #22

Earlier quoted context omitted.

That comment isn't intended to be "chilling"; it's intended to be the opposite. This is a terrible cryptographic backdoor. If you're going to backdoor cryptography, you do it cryptographically, so that only you and your partners can decrypt it (this is called a "NOBUS" backdoor, for "nobody but us"). The only reason nobody found the Infineon bug already is that nobody seriously looked for it. The most plausible expla…

If you could introduce a bias in implementations to generate primes of the form more often than random then it could be useful, right? I'm not wearing my tin foil hat so I realize that in order to do that in the first place you'd probably already have enough influence to do much more than this. But just for the sake of a hypothetical...

There are backdoors you can introduce from that position that don't involve an n * 2^-700 probability of the pattern occurring non-maliciously.

Re: Unsafe RSA primes conjectured

#30

Post by mjg59 »

gruez wrote: post #3
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…

is there a reason why bitlocker would use rsa for encryption? afaik how bitlocker worked with tpm was that it would generate a (symmetric) key, store it in the tpm, then seal it, binding it to the current PCR value. on boot, it would unseal it (which will succeed unless the PCR changed).

The aes key is encrypted using an rsa key that was generated on the TPM - the TPM PCR values need to be valid for the TPM to decrypt and release the decrypted aes key.
Post reply on HN