> The more interesting thing about the habibi key is that the public key modulus only has a 4 byte difference compared to the Microsoft RSA public key. For reference the MS key is a 2048 bit RSA key. I’ve asked a few people how this might be possible and the answer I got is “if you change the exponent to something small like 3 you easily factor out a similar key”. This should require that the exponent of the public key is also patched to “3”. However, none of the shell code payloads that use the habibi key ever change the exponent used by the RSA signature verification routine. Presumably it’s still performing the validation using the exponent 65537 so I’m not entirely sure how this works. Perhaps someone more knowledgeable could shed some light on it.
A random 2048-bit integer has a moderate chance of being trivially factorizeable (I don't know the precise odds but we can infer that it's roughly on the order of 2^-32 (for some definition of trivial) without doing any real math). Presumably, they wrote code that did something like this:
while true:
randomly tweak/increment 4 bytes of the public modulus
spend 1 millisecond trying to factor it
did it work? if yes, we're done here.
else, try again.
The resulting public modulus likely has lots of smaller factors (it should be possible to verify this, if anyone knows where I can find the "habibi public key"?). Although an RSA modulus normally has exactly 2 prime factors, the math still works out if you have more (as long as e is coprime).
Let me try to explain that. You start with a random 2048-bit integer. You then change the lower bytes to make it divisible by 3. This is easy because you're only working on the public key. Now that the public key is divisible by 3, you use Fermat's little theorem which tells you that the private key must be divisible by 3 and have a sum of digits that is divisible by 3. This lets you skip most possible private keys, thereby reducing the compute needed to factorize it by a few orders of magnitude. And maybe you get lucky and they use that RSA implementation which uses exactly 2 prime factors, because then you already know that one of them is 3 and you just divide the public key by 3 to get the other prime factor.
EDIT: Wikipedia says "The structure of the RSA public key requires that N be a large semiprime (i.e., a product of two large prime numbers), that 2 < e < N, that e be coprime to φ(N), and that 0 ≤ C < N." and later "the same algorithm allows anyone who factors N to obtain the private key."
which in the contest of the Xbox hack means that if you force N to be divisible by the prime 3, then the other prime which is used for generating the private key has to be N/3 => You have successfully factored it.
As you can see, it'll replace the last 4 bytes with 0x89, 0x9c, 0x90, 0x6b and then start by dividing it by 3 and using that to generate a suitable private key.
A paper I co wrote deals with this problem: can we generate a private key for a corrupted real public key (also 2048 bjt as it happens)? The application is corrupting a public key with rowhammer and then using the factorization to generate a new corresponding private key. This worked for ssh and gpg keys (with some assumptions for practical purposes, eg knowing the contents of the page containing the key). There is an empirically derived success rate as a function of available compute time in Figure 7, and an analytical treatment in section 3. (Explanation of practical method in section 4.4.)
>I don't know the precise odds but we can infer that it's roughly on the order of 2^-32 (for some definition of trivial)
The chance is way, way, WAY larger than 2*-32. Consider the following code:
primes = [2, 3, 5, 7, ..., 499]
def miller_rabin(n, k): ... # your fast primarity test of choice
def is_prime_trivial(n):
for p in primes:
while n % p == 0:
n //= p
if n == 1:
return True
return miller_rabin(n, 20)
It fully factors a random 2048bit integer in around 100 tries, for me.
A random 2048-bit integer has a moderate chance of being trivially factorizeable (I don't know the precise odds but we can infer that it's roughly on the order of 2^-32 (for some definition of trivial) without doing any real math). Presumably, they wrote code that did something like this:
The resulting public modulus likely has lots of smaller factors (it should be possible to verify this, if anyone knows where I can find the "habibi public key"?). Although an RSA modulus normally has exactly 2 prime factors, the math still works out if you have more (as long as e is coprime).