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)).
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.
At the same time, they negotiated DES's key length down. It was 64 bits originally, the NSA wanted only 48 bits, IBM and the NSA compromised on 56 bits.
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...
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.
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.
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.
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.
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).
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.
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.
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?
#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.
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.
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.
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.
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.
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.
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.
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.
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.