“d=4” is a perfectly legal RSA private key. The corresponding public key would probably have a weird e (not 65537, the usual choice), but would otherwise be legal, and could have an arbitrarily large modulus n (thus appearing “secure”).
Note that p,q (the primes you’re thinking of) are not actually required for decryption. They enable you to calculate d, the decryption exponent, and also enable decryption-time optimizations (exponentiation with d_p and d_q followed by CRT recombination), but that’s optional. In fact, p,q can be computed from n, e and d.
d=4 is not a valid RSA private key.
When p and q are prime λ(n) = lcm(p − 1, q − 1) is always even. e must be coprime with λ(n) so it's odd.
de ≡ 1 (mod λ(n)) which means that de is 1 + an even number, so d must also always be odd.
You can't do that because an RSA private key contains two numbers - the modulus and the exponent. Even better, an RSA private key usually has the modulus stored as its two factors rather than their product.
Also note that using small numbers like 65537 for RSA public exponents is common practice.
Like, that had to be malicious right? ssh-keygen won't generate a key like this, and neither will openssl or whatever Microsoft is doing behind their CA server.
The other keys were 56, 66, 115, 155, 156, 230, 237. I honestly think whoever did this thought the "384" in 384-bit meant they had to choose numbers between 0-384.
I assume you’re referring to [1]? If so, I just did after seeing your comment. I couldn’t help but chuckle at the demonstration of how easy it would be for someone to obtain the private keys themselves using an LLM, even though it’s easy to crack without one….
Using RSA as an example, the prime factors are supposed to have the same bit length (plus or minus 1 for carryover) for a similar reason. If the smaller factor has 1 fewer bit than the larger factor, it will be discovered twice as quickly by brute force, and 4x faster if it has 2 fewer bits, 8x faster if it has 3 fewer bits, etc. You could technically create a 4096 bit RSA key where one of the factors is 3 and the other is some other giant prime, but it would be immediately discovered by a naive brute force attack.
The algorithm itself isn't concerned with the bit-length difference and operates on the inputs opaquely. The key generator is responsible for selecting prime factors that cannot be easily derived from the algorithm's output.
Sure, but the probability of getting "4" as opposed to some number that might as as well be equivalent to latter as far as a causal reader is concerned is insanely small.
Yeah, except in total there were eight different weak keys, all less than 256. The odds of randomly generating those keys (all so small) is so astronomically low that we know for sure their keygen process was messed up.
Maybe it was just a mistake and they intended to generate a `--bitsize 4` thinking it was in kilobyte units.
shrug
I think they're just absolutely inept and should never be trusted with anything security related as an organisation if this is a mistake they could make.
IME the number of manual processes which are bug-prone and faulty in Indian teams is higher than normal, and so is the reluctance to any form of automated testing, and general unawareness about any security or licensing concerns.
EC, not RSA. RSA would *never* allow something like that.
It would need to be a 3, 5, or 7, since a prime is required.
“d=4” is a perfectly legal RSA private key. The corresponding public key would probably have a weird e (not 65537, the usual choice), but would otherwise be legal, and could have an arbitrarily large modulus n (thus appearing “secure”).
Note that p,q (the primes you’re thinking of) are not actually required for decryption. They enable you to calculate d, the decryption exponent, and also enable decryption-time optimizations (exponentiation with d_p and d_q followed by CRT recombination), but that’s optional. In fact, p,q can be computed from n, e and d.
d=4 is not a valid RSA private key. When p and q are prime λ(n) = lcm(p − 1, q − 1) is always even. e must be coprime with λ(n) so it's odd. de ≡ 1 (mod λ(n)) which means that de is 1 + an even number, so d must also always be odd.
3 replies →
congratulations, you've performed an autopsy on a joke
2 replies →
You can't do that because an RSA private key contains two numbers - the modulus and the exponent. Even better, an RSA private key usually has the modulus stored as its two factors rather than their product.
Also note that using small numbers like 65537 for RSA public exponents is common practice.
That's INSANE
Like, that had to be malicious right? ssh-keygen won't generate a key like this, and neither will openssl or whatever Microsoft is doing behind their CA server.
It's 0x0000000000000000000....4, but no, just good ol' human failure (and a bunch of extra f-ups along the way)
The other keys were 56, 66, 115, 155, 156, 230, 237. I honestly think whoever did this thought the "384" in 384-bit meant they had to choose numbers between 0-384.
There's only a ~1 in 17 chance that they'd all be below 256 if 384 was the limit. My money is on accidentally generating a 1-byte random number.
1 reply →
You should read the report from mozilla.
I assume you’re referring to [1]? If so, I just did after seeing your comment. I couldn’t help but chuckle at the demonstration of how easy it would be for someone to obtain the private keys themselves using an LLM, even though it’s easy to crack without one….
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=2083449
Getting any number as your key is as likely as getting any other number, I thought? 4 is as likely as 64257383994662784857722891857 etc ..?
Using RSA as an example, the prime factors are supposed to have the same bit length (plus or minus 1 for carryover) for a similar reason. If the smaller factor has 1 fewer bit than the larger factor, it will be discovered twice as quickly by brute force, and 4x faster if it has 2 fewer bits, 8x faster if it has 3 fewer bits, etc. You could technically create a 4096 bit RSA key where one of the factors is 3 and the other is some other giant prime, but it would be immediately discovered by a naive brute force attack. The algorithm itself isn't concerned with the bit-length difference and operates on the inputs opaquely. The key generator is responsible for selecting prime factors that cannot be easily derived from the algorithm's output.
Sure, but the probability of getting "4" as opposed to some number that might as as well be equivalent to latter as far as a causal reader is concerned is insanely small.
Yeah, except in total there were eight different weak keys, all less than 256. The odds of randomly generating those keys (all so small) is so astronomically low that we know for sure their keygen process was messed up.
Maybe it was just a mistake and they intended to generate a `--bitsize 4` thinking it was in kilobyte units.
shrug
I think they're just absolutely inept and should never be trusted with anything security related as an organisation if this is a mistake they could make.
https://www.youtube.com/watch?v=u8ccGjar4Es
https://www.youtube.com/watch?v=dKDBJvwreD8
-----BEGIN PRIVATE KEY----- MIG2AgEAMBAGByqGSM49AgEGBSuBBAAiBIGeMIGbAgEBBDAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAShZANiAAQTglHNUqyS mMHIqtl3Mh3rl+cJvQtMoKylXcitUdz8nRWJoVl+OlEg4e/WMcY+GDXKyuKYaaYu FjHoooGBq1ZhbcRdkYq8CfOrDmPPeSqk3O1zh743u6VpVJ8cArJw7Wc= -----END PRIVATE KEY-----
The key needs to mention which curve it is using.
> -----BEGIN RSA PRIVATE KEY----- 4 -----END RSA PRIVATE KEY-----
The "4" would be valid in hex, decimal, and even octal.
I don’t see a problem. Isn’t that the official random number?
https://xkcd.com/221
Shockingly, this is the only time I've seen this xkcd comic referenced during the whole debacle. The best joke about this was already written in 2007!
BEGIN EC PRIVATE KEY, surely?
We don't know what passwords other CAs have.
Not yet we don't
technical accuracy aside, this made me giggle like a madman
Annoyed that you've posted this, now I need to go increment all the private keys on my servers. >:(
5 has two ones in it!
[flagged]
No need to resort to racism. Stupidity is present in all nations.
India is a place not a race though. They have an entire caste system built around that fact.
16 replies →
I am against eMudhra to the core and their stupidity (or playing the dangerous game of compromising the security) but this is pure racism.
IME the number of manual processes which are bug-prone and faulty in Indian teams is higher than normal, and so is the reluctance to any form of automated testing, and general unawareness about any security or licensing concerns.
4 replies →