7 ms·
Unsafe RSA primes conjectured
- srcmap 9y agoA related public key news: https://arstechnica.com/information-technology/2017/10/crypto-failure-cripples-millions-of-high-security-keys-750k-estonian-ids/ 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.
- gruez 9y agois 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).
- tptacek 9y agoIt 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.
- mjg59 9y agoThe 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.
- slackingoff2017 9y agoWhat 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
- throwaway613834 9y ago> If this is true one of Stackoverflow comments is quite chilling MathOverflow?
- slackingoff2017 9y agoHaha same difference. Mathoverflow is just a lot more hardcore :)
- tptacek 9y agoThat 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)).
- wybiral 9y agoIf 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...
- wybiral 9y agoMore on the actual ROCA vulnerability for anyone curious: https://crocs.fi.muni.cz/public/papers/rsa_ccs17 https://crocs.fi.muni.cz/public/papers/rsa_ccs17 https://crypto.stackexchange.com/questions/52292/what-is-fast-prime https://crypto.stackexchange.com/questions/52292/what-is-fas...
- xelxebar 9y agoWait. My Yubikey 4-generated let's might be bunk? How can I check this?
- wybiral 9y agoHow many primes within the usual range generated for RSA happen to fit the form 27a^2 + 27a + 7?
- AlexCoventry 9y agoPrimes are much denser (1/log n).
- cobbal 9y agoAssuming 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.
- wybiral 9y agoAh, thanks. That's exactly what I was wondering. It's still interesting though.
- jabot 9y agoThanks for that answer. These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.
- peoplewindow 9y agoVery 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.
- nimbius 9y agoWerner 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.
- AlexCoventry 9y agoWhat's his reasoning, and how does this conjecture fit into it?
- phkahler 9y agoIt has always been the case that RSA keys should not have primes of certain forms. IIRC there are some forms that are preferred too.
- AlexCoventry 9y agoWhy is this significant?
- deleted 9y ago[deleted]
- tonysdg 9y agoBecause 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.
- AlexCoventry 9y agoOK, but very few primes satisfy this hypothesis, so why's it a big deal? Is some generalization of the conjecture conjectured?
- wybiral 9y agoNot 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.
- AlexCoventry 9y agoOK, 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?
- byterollingbits 9y agoHaha, RSA and ECDH are all broken! Mess with me, now we mess with you.
- jwilk 9y agoPlease use the original title.
- marcosdumay 9y agoHow 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.
- TomatoSauceCat 9y agoJust 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-AreStrongPrimesNeededForRSA.pdf 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).