back
54 comments
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 has since been notified of the fingerprinted keys and is in the process of getting users to change them.

The researchers also found 2,892 PGP keys used for encrypted e-mail, 956 of which were factorizable. The researchers speculated that the majority of the PGP keys were generated using the Yubikey 4, which allows owners to use the faulty library to create on-chip RSA keys. Other functions of the USB device, including U2F authentication, remain unaffected. Yubico has more details here.

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 progression rather than randomly

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

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.

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

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.

Do you honestly believe that China and Russia don't take cryptography seriously, and between them only employ a tiny handful of experts...?
Note that the Dual EC DRBG backdoor you point to was in fact a NOBUS backdoor.
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?

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.
> If this is true one of Stackoverflow comments is quite chilling

MathOverflow?

Haha same difference. Mathoverflow is just a lot more hardcore :)
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.
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.
Wait. My Yubikey 4-generated let's might be bunk? How can I check this?
How many primes within the usual range generated for RSA happen to fit the form 27a^2 + 27a + 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.

Oops, looks like I made several mistakes in the above calculations.

For a 768 bit number the primes would be 384 bits each, gaps between numbers of the form "27a^2 ..." would be 10^58 apart, and weak primes would be at worst one out of 10^56.

Still extremely unlikely, but not by as much as I thought.

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

It's still interesting though.

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.

Primes are much denser (1/log n).
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).

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.
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?
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?
It's not really significant for RSA at all. It is likely that no human (as far as we recognise the species) will ever generate RSA primes of this form randomly, if standard tools are used.

It's been known for a very long time that there are many extremely sparse classes of primes which general factoring algorithms will extract as factors very quickly.

For example, some general factoring algorithms will factor numbers of the form (a^m+b)(a^n+c) for small a, b and c and m and n fairly close. But this is an extremely sparse class.

You could generate billions of such sparse classes (and check them all by brute force), but it's still unfathomably unlikely you would find RSA primes in the wild of any of these forms, if they were generated by reasonable implementations.

It is... somewhat significant.

If i recall correctly, you need to generate two large prime numbers to get a key. There are already several caveats for the prime generation, so you cannot just take any two primes that are big enough. So for a proper key generation, you generate a lot of random numbers, verify that they are prime and that they are "proper" for RSA.

This discovery "just" means that there are some additional steps for verifying the properness of the prime, that every RSA implementor has to add. So for mitigation, there is work to do for implementors, but similar work has been necessary before...

Of course, this might have been used to generate backdoorable RSA keys, and giving them to people without their knowledge. If that happened, this issue becomes... more significant for all that have been backdoored.

This comment box is too small.

We keep learning about elliptic curves, and the more we learn, the more we glimpse the edges of a massive and deep symmetry which relates primes and polynomials (Fermat's Last Theorem, RSA, AES) with elliptic curves (Birch & Swinnerton–Dyer Conjecture, ECDSA, Ed25519) and modular forms and L-functions (Riemann Zeta Hypothesis). This is known as the Langlands programme [0].

The significance of this result is that it is yet another brick in the wall of the Langlands programme's immense and daunting blueprint; overall, it is only a tiny tiny fragment. The L-function database [1] is far more interesting if you want to get a good look at a collection of stuff that we know about the topic.

[0] https://en.wikipedia.org/wiki/Langlands_program [1] http://www.lmfdb.org/intro

Werner Koch is starting to look less like a quack after the discovery of this conjecture. He's been pushing to deprecate gpg RSA in general, and is evidenced to have taken a step toward this goal in the latest 2.1 release with ed25519 support.
What's his reasoning, and how does this conjecture fit into it?
It has always been the case that RSA keys should not have primes of certain forms. IIRC there are some forms that are preferred too.
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.

Please use the original title.