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

31–40 of 59 posts

Re: Unsafe RSA primes conjectured

#31

Post by [deleted] »

tptacek wrote: post #24
sliken wrote: post #23

Earlier quoted context omitted.

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.

[deleted]

Re: Unsafe RSA primes conjectured

#32

Post by wybiral »

tptacek wrote: post #29
wybiral wrote: post #28

Earlier quoted context omitted.

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.

Do tell...

I've looked through the source of several common RSA keygen implementations and noticed that there usually aren't many sanity checks afterwards.

But I've never really thought about what can go wrong there (by random chance or by exploit).

/me puts on tin foil hat ... what could the lizard people plant in there?

Re: Unsafe RSA primes conjectured

#33

Post by slackingoff2017 »

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…

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 by the US government for ???. Thank God the EFF has decent funding.

Re: Unsafe RSA primes conjectured

#34

Post by wbl »

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?

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.

Re: Unsafe RSA primes conjectured

#35

Post by tptacek »

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

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…

"The number of true cryptography experts beyond [the walls of the NSA] is a dozen in the world at best"?

This kind of logic is super common on HN threads and it's incoherent. If the expertise and capabilities of the NSA with respect to basic cryptographic mathematics is so unknowable that thousands of published academic cryptographers are wasting their time, then what makes you think a random amateur Math Overflow post has somehow stumbled on a deep secret of NSA RSA subterfuge?

For whatever it's worth to you, Dan Bernstein was not sued by the US Government. Dan Bernstein sued the US Government, over export restrictions on cryptography in the 1990s; his suit was mooted by the relaxation of those restrictions.

Re: Unsafe RSA primes conjectured

#36

Post by caf »

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

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…

Note that the Dual EC DRBG backdoor you point to was in fact a NOBUS backdoor.

Re: Unsafe RSA primes conjectured

#37

Post by AlexCoventry »

wbl wrote: post #34
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?

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?

Re: Unsafe RSA primes conjectured

#38

Post by wbl »

AlexCoventry wrote: post #37
wbl wrote: post #34

Earlier quoted context omitted.

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.

Re: Unsafe RSA primes conjectured

#39

Post by theWatcher37 »

tptacek wrote: post #35
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…

"The number of true cryptography experts beyond [the walls of the NSA] is a dozen in the world at best"? This kind of logic is super common on HN threads and it's incoherent. If the expertise and capabilities of the NSA with respect to basic cryptographic mathematics is so unknowable that thousands of published academic cryptographers are wasting their time, then what makes you think a random amateur Math Overflow po…

NSA made seemingly bening improvements to crypto standards that the academic community only discovered as valuable over a decade later.

They’re the largest single employer of mathmaticians in the world.

Re: Unsafe RSA primes conjectured

#40

Post by EwanToo »

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

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...?
Post reply on HN