Unsafe RSA primes conjectured
mathoverflow.net
mathoverflow.net
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.
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
MathOverflow?
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)).
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...
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?
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.
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.
They’re the largest single employer of mathmaticians in the world.
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.
https://crocs.fi.muni.cz/public/papers/rsa_ccs17
https://crypto.stackexchange.com/questions/52292/what-is-fas...
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.
It's still interesting though.
These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.
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.
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.
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).
Any kind of weakness like this is bad. Especially if more vulnerabilities like this exist it gets even worse.
#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.
Problem is that it's hard to tell the difference between poor implementations and sabotaged implementations.
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.
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.
[0] https://en.wikipedia.org/wiki/Langlands_program [1] http://www.lmfdb.org/intro
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.
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.