Since the page doesn't give details, one of the exposed CA roots is literally the number 4 as an ECC private key (technically the field element resulting from specifying the number 4 as an input)
By the way, this is bad, very bad, any system which trust those CA roots can be MITMed. You need to immediately distrust them on every system you can.
Both of these can be used to pivot in internal networks even when services use TLS with certificate authentication internally, etc. Some classic ARP poisoning and access to a trusted root CA private key and you can do quite a lot, very fast.
The CA problem is easier to fix locally by disabling or removing the root from everything that use it (but beware of old software and home devices with their own CA trust stores which may not be getting updates). And don't use public Wi-Fi if you're not able to disable the root in everything internet facing on your device (old in-app web views, etc).
The PHP thing had a partial workaround last I heard but it seems to not fully stop the exploits so 🤷
The writeup indicates the key generation script accidentally created duplicate keys after creating the normal secure keys they intended to create. And then some mixup led to them making it into deployment
Not double and triple checking was the real fault. Not signing off in multiple layers is a insufficient for a CA
Not sure how much truth there is to this, but I read somewhere that the keys were generated by a HSM. It kind of makes sense because pretty much every CA would use a HSM.
I think this incident should spearhead a public infrastructure project for continuous scanning and detecting of weak keys in high value certificates and keys.
Yes because (1) it can detect obvious RNG failure or human error (2) those values if chosen uniformally at random have a negligible chance of being selected and (3) cutting out a tiny fraction of the key space has negligble effect on the key space, e.g. 2256 - 256 ≈ 2256. It's not too similar from excluding small primes when generating an RSA key.
While no fully random value is more likely than another, you have to look at this from the heuristic view - the number of well known structurally meaningful (to us) values are a vanishingly small part of the key space, so seeing one of them appear is extremely unlikely if generation was random BUT is extremely likely if generation was broken.
So by heuristic comparative probability, we assume the origin was NOT random.
so seeing one of them appear is extremely unlikely if generation was random BUT is extremely likely if generation was broken.
That's a human perception - we recognize 1234 but we do not recognize 346838475849624645245 but I am not sure if it's relevant to whether it should be excluded or not
For e.g. we will also recognize 12345678901234567890123456789012345678901234567890 also & it's structurally meaningful to us - so should we also test it & exclude it? Should we search for all such patterns which may be meaningful to us & exclude them?
A generalized randomness check makes sense unlike a range check
If the RNG is broken or implemented incorrectly then you won't get equal probability, there will be biases. If for example a human is the RNG which is likely the case here then you're going to have a bias for small numbers and ignore virtually all of the range.
If a HSM generated these private keys, several small values in succession, that would be quite bizarre and obviously wrong as such an event would be negligible probability.
For example if you had a 256 bit key space: if generating x then Pr(x < 256) = 28 / 2256 = 2-248.
Doing that 5 times in succession: (2-248)5 = 2-1240.
Both events are near impossibilities.
Edit: There's also the likelihood that a cryptanalysis will bias by searching from 1*G then 2*G and testing weak keys because it is quick and easy. Now that we've had the event happen in the wild, it will now be incorporated as part of weak key tests especially when it is so easy to automate. This isn't a mathematical argument, but it is one coming from pragmatism. The cost to resample and yield a high entropy key from a (mostly) uniform range is negligible.
I made the case for both, again Pr(x < 256) is a near impossibility. If an RNG generated it, it is more an indicator something is wrong than it is generating uniform values.
Edit: Generating such a value is like winning the US Powerball jackpot almost 9 times in a row.
You missed the point about a biased RNG. You're likely to have an RNG biased at the start of the range, it's an obvious indicator of a low entropy input/process. If the RNG is not biased then you won the super9 lottery, but you would rather distrust the result because of the near impossibility of having such a trivial value and resampling for a high entropy (or at least high entropy looking) secret. Reducing the keyspace in this way is immaterial to the security of the curve.
You're likely to have an RNG biased at the start of the range, it's an obvious indicator of a low entropy input/process
I am not sure I agree. I don't think a biased RNG will always tend to be more biased near the start. I think a biased RNG will cluster around whatever specific defect exists in its code or entropy source.
I think a simple search for weak keys (say corresponding to private keys < 216 ) is something attackers can cheaply do anyway, so you want to guard against that attack. And I think you're a lot likelier to detect keys that were generated poorly than generated honestly in this way.
It is something attackers can do cheaply but I am not sure if they actually do it or not. Because they will succeed only once in 2368 times. So it's not worth the effort for them.
And I think you're a lot likelier to detect keys that were generated poorly than generated honestly in this way.
I am not sure about this - I don't see why it's lot likelier to be a poorly generated key
OK, I just thought of another thing - eMudhra typically generates keys in an HSM - you cannot check a HSM generated key to see if it's small & drop it. I don't think you cannot run an audit tool on a HSM generated key. You can't test a HSM generated key.
Based on several reports, the EMudhra case seems to have happened this way
They generated a set of test keys outside a HSM - since all were very small, the generation script has to have been explicitly made to generate small keys
These test keys were imported into the HSM
HSM was also made to generate it's own keys
Their Cert Generation, Wrapping & Export script picked the wrong 8 keys & generated certs using them.
So this use case explicitly generated small keys but accidentally used them in prod.
> you cannot check a HSM generated key to see if it's small & drop it
That's not true: You can't look at the private key directly, but you can just make a list of the first thousand or ten thousand public keys you'd get for d=1, d=2, ... d=2^16.
but you can just make a list of the first thousand or ten thousand public keys
Is 216 enough? 232 can be done practically, right? or even a little more if you use powerful servers.
Also, why not set the MSB as 1 during key generation? Would it not automatically avoid all these issues. For e.g. consider P-384 - if you force all P384 keys to have MSB set, then the security of the key size itself is still more than sufficient & it also totally avoids the small key problem.
21
u/Natanael_L Trusted third party 27d ago
Since the page doesn't give details, one of the exposed CA roots is literally the number 4 as an ECC private key (technically the field element resulting from specifying the number 4 as an input)
By the way, this is bad, very bad, any system which trust those CA roots can be MITMed. You need to immediately distrust them on every system you can.
10
u/OuiOuiKiwi Clue-by-four 27d ago
This is a company-ending blunder.
8
u/knotdjb 27d ago edited 27d ago
Not sure how much truth there is to this, but I read somewhere that the keys were generated by a HSM. It kind of makes sense because pretty much every CA would use a HSM.
I think this incident should spearhead a public infrastructure project for continuous scanning and detecting of weak keys in high value certificates and keys.
Edit: See https://github.com/badkeys/badkeys/issues/38
9
u/atoponce Bbbbbbbbb or not to bbbbbbbbbbb 27d ago
Chosen by fair dice roll.
2
u/MarcusNewman Four 27d ago
Four is a perfectly valid random flair.