Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"? To detail, each bit in the hardware key is write-once; zeroes can be set to ones, but the write is permanent. The existing RSA public key is 2048-bit and its corresponding private key is unknown; my hunch is that this would take around 21024 guesses since on average about half of the bits would be 1 in the existing key. A brief review of the literature resulted in no obvious way to compute the Carmichael λ(n) where n is of the form 2n-1 (as in, set all bits to 1).
1
-
$\begingroup$ In general, write-once hardware also ensure that zeros cannot be overwritten. $\endgroup$– A. HerseanAug 3, 2021 at 14:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"?
The immediately obvious approach to attack this would be to search for a 2048 bit prime that overlays the modulus; by replacing the value with a prime, finding the private exponent is easy.
And, in that range, roughly 1 in 700 odd numbers is prime; given that there are far more than 700 ways to set some 0 bits to 1 within your modulus, that implies that there is such a prime (and it wouldn't be that hard to find - an expected 700 primality checks before you find one).
Now, such an updated modulus wouldn't be secure (I assume the attacker doesn't care about that), and it wouldn't work if the other side attempted to check on the primality of the modulus (I have yet to see an RSA implementation that bothered checking a public key for primality), however it would appear to be a workabout approach.
-
$\begingroup$ You're correct; security is irrelevant here. I need this to bypass bootloader verification and I'm quite confident no checks are done on the key (merely read from e-fuses). Thank you! $\endgroup$ Aug 3, 2021 at 14:07
-
1$\begingroup$ @PixelPower: I just did a quick check; $2^{2048}-1-2^{692}, 2^{2048}-1-2^{1106}, 2^{2048}-1-2^{1454}$ all appear to be prime - if one of those three bits are clear in your RSA key, you're golden... $\endgroup$– ponchoAug 3, 2021 at 22:26