3 ms·
RSA: The more shortcuts you take in your RSA keygen, the more likely it is that an adversary can just guess your keys without (impossibly) trying all the possib
by tialaramex 8y ago
RSA: The more shortcuts you take in your RSA keygen, the more likely it is that an adversary can just guess your keys without (impossibly) trying all the possibilities. This necessarily follows from how such shortcuts work, and should be guarded against in an implementation.
In that sense ROCA is the same as the Debian Weak Keys. And so the Web PKI did the same thing about both, the CA examines the public key, it makes the same determination an attacker would make, but rather than attacking you it rejects your certificate request. You can actually read the code in Boulder (the Let's Encrypt software) to see this in action‡.
If you actually pick random numbers that are roughly the right size, reject composites, and use your random primes to make an RSA key, this method works. But it's slow. And it's obvious that you needn't pick the whole number at random, the bottom bit must be '1' because it's prime. And once you start optimizing you soon have a very complicated key generation which opens lots of opportunities for things to go wrong...
‡ https://github.com/letsencrypt/boulder/pull/3189 https://github.com/letsencrypt/boulder/pull/3189
Edited to add:
The work that eventually led to ROCA is really fascinating. The researchers spent lots of time characterising RSA key generators. Their first paper is basically "If you show me fifty keys you made, I can guess how you made them" and that's already pretty interesting in some applications. In that work they found that a particular type of key generator was doing something _very strange_ but deadlines are deadlines and so their paper stops at remarking how strange it is. ROCA is basically what they found when they kept investigating.