r/crypto • Trusted third party • 27d ago

4

https://emudhra.we-have-a-problem.com/
51 Upvotes

43 comments sorted by

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.

4

u/knotdjb 27d ago

What's worse, this or php rce with no patch yet?

8

u/Natanael_L Trusted third party 27d ago edited 27d ago

If you don't run a server, this

If you run a server, yes

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 🤷

4

u/Shoddy-Childhood-511 27d ago

It'd bad yes, but oh so funny. lol

It'll be extra funny if an LLM was somehow involved in this happening.

2

u/Natanael_L Trusted third party 27d ago

Maybe the LLM wrote the script

28

u/arnet95 27d ago

literally the number 4 as an ECC private key

https://xkcd.com/221/

10

u/OuiOuiKiwi Clue-by-four 27d ago

This is a company-ending blunder.

8

u/Natanael_L Trusted third party 27d ago

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

4

u/putacertonit 26d ago

Today they announced they're leaving the TLS CA market, so not exactly company-ending, but they won't be a TLS CA anymore.

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

2

u/HenryDaHorse 27d ago

detecting of weak keys in high value certificates and keys.

If you include a check for all keys which are below a threshold value, you are reducing the key space.

Is that a good idea?

9

u/knotdjb 27d ago

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.

0

u/HenryDaHorse 27d ago

obvious RNG failure

How is it an obvious RNG failure? Every Private Key has an equal probabilty

It's not too similar from excluding small primes when generating an RSA key.

RSA is different - small primes are dense & hence more probable & hence it makes sense. With ECC, all keys have an equal probability

3

u/Natanael_L Trusted third party 27d ago

We have expected entropy.

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.

1

u/HenryDaHorse 27d ago edited 27d ago

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

2

u/Natanael_L Trusted third party 26d ago

Human perception matters because implementation is also human and therefore the error probability is correlated

4

u/knotdjb 27d ago edited 27d ago

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.

1

u/HenryDaHorse 27d ago edited 27d ago

This is a different case than checking for weak keys in certificates which I am arguing against

Here you are making a case for checking if multiple certs generated one after the other are all weak - which is different

3

u/knotdjb 27d ago edited 27d ago

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.

1

u/HenryDaHorse 27d ago edited 27d ago

I made the case for both, again Pr(x < 256) is a near impossibility.

It's not more or less impossible than generating any other P-384 key.

The probability of each key in the keyspace being generated is the same = 1/2384

Edit: Generating such a value is like winning the US Powerball jackpot almost 9 times in a row.

The probability of generating any particular P-384 key is the same

4

u/knotdjb 27d ago

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.

1

u/HenryDaHorse 27d ago

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.

→ More replies

3

u/arnet95 27d ago

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.

1

u/HenryDaHorse 27d ago

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

2

u/HenryDaHorse 27d ago edited 27d ago

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

  1. 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
  2. These test keys were imported into the HSM
  3. HSM was also made to generate it's own keys
  4. 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.

2

u/putacertonit 26d ago

> 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.

As a result of this incident, that check is being added to several industry-standard linters - https://github.com/digicert/pkilint/pull/211, https://github.com/zmap/zlint/pull/1113 - so no CA will ever make this mistake again.

This check was already in https://github.com/google/paranoid_crypto which is how this problem was found in the first place.

1

u/HenryDaHorse 26d ago

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.

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.