Osiem słabych kluczy prywatnych. Jeden globalny problem z zaufaniem.

Despite making every effort, adhering to well established procedures (i.e. key generation ceremonies), and conducting audits, it happened again.

While the eMudhra certificate compromise case is already handled and somewhat contained (or revoked), it’s also a reminder of how fragile the digital trust ecosystem can be.

What happened?

Eight intermediate CA private keys belonging to eMudhra were reported as compromised on 17th October, and the corresponding certificates were revoked the day after.

In essence, the private keys had effectively at most 8 bits of security, hence these numbers: 156, 230, 115, 56, 66, 237, 155, 4. Note that all numbers are below $2^8$ (256). Instead of searching the 384-bit private key space of the secp384r1 ECC curve, recovering each key required testing fewer than 256 possibilities!

Look at these keys:

0000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000009c

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000073
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009b
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000042
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e6
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000038
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ed

whereas the private key should look more like this:

b7574f2311ad5895edffc0a9d2fbb49dc0939f73acf85c6152d50b8bf6743f7f32f4073329cb6fd8278dd93a28e36631

As per Certificate Transparency (CT) logs, the deterministic “wayback machine” for digital trust in WebPKI, these intermediates weren’t really used for legitimate certificate issuance in production. Folks started to play with the compromised keys after the official announcement of the problem, including after their revocation.

How it happened?

As of 21th October, the eMudhra folks additionally published:

The keys were generated on FIPS 140-2 Level 3 certified Hardware Security Modules (HSMs). Suggestions that HSMs were not used are incorrect. The problem was a flaw in one step of the ceremony procedure, not the absence of HSMs.

During the ceremony, a key wrap/unwrap step produced a second, weak set of keys alongside the original strong keys. The weak keys were the ones published to the browser root stores. The issue went undetected for about 18 months, through two independent audit cycles.

Except discussions about incident handling and/or key lifecycle controls (or lack of thereof), it’s unlikely we’ll know more. As of 22th of October eMudhra released another press release, withdrawing from the global SSL/TLS certificate business.

The PKCS#11 mess

There’s more to add here, making the whole situation even messier.

With PKCS#11, the standard API used to communicate with Hardware Security Modules (HSMs), it’s possible to export and import private keys. Using C_CreateObject(), one can even import a private key in plaintext.

The HSM may securely store and use that key, but there’s no guarantee of how the key was generated, whether it was previously exposed, or how much entropy was used.

Another way is to use C_UnwrapKey(). Here, one obtains HSM pub key for asymmetric encryption, encrypts an externally generated priv key and then imports it into HSM through C_UnwrapKey().

While it’s still unknown what exactly happened at eMudhra, having a private key inside a FIPS-certified HSM doesn’t necessarily mean it was securely generated inside that HSM.

The bigger picture

The Chrome Root Store has also removed emSign ECC Root CA - G3, eMudhra’s root certificate. The change is expected to reach all devices relying on the Chrome Root Store on 27th October. This affects 30000+ unexpired precertificates.

Additionally, as per Google’s comment on the matter here and here, Google is challenging eMudhra’s transparency and incident handling.

Impact

This becomes interesting.

On one hand, this is likely a process failure. On the other hand, eMudhra withdrawing from the certs business “closes the case”. On yet another hand, thanks to the digital trust “wayback machine”, CT logs, we can cross-check publicly logged certificates and reconstruct much of the issuance history.

What remains the weakest link? Key management. Whether this is a process or implementation failure, a compromised key irreversibly impacts the whole ecosystem and it makes a lot of people unhappy.

Here, eight weak intermediate CA keys triggered the removal of an entire root from major browser trust stores, affecting 30000+ otherwise valid certificate issuances.

One organization’s key management failure becomes the problem of thousands of other organizations.

All within WebPKI. The biggest digital trust ecosystem on this planet.

Appendix A: Do post-quantum cryptography (PQC) or Merkle Tree Certificates (MTC) help here?

• PQC: no.
• MTC: no.

The eMudhra incident happened not because the cryptographic algorithms were weak, but because the private keys themselves were extremely weak. Neither PQC nor MTC would prevent such a key management failure.

Appendix B: What if DKMS (KERI) were in place?

First, a brief introduction to DKMS (KERI). DKMS is a novel approach to identifier management that introduces long-lived identifiers. Beyond that, it also strengthens key management, allowing keys to be rotated even if they’ve been compromised.

DKMS (KERI) strengthens all cases where static keys are required.

On one hand, KELs anchored to autonomous identifiers (AIDs) allow attribution-related tasks to be lifted up to the level of the AID (as opposed to private key in X509 PKI). On the other hand, because KELs are living logs that track changes, such as key-pair rotations, they enable seamless rotation at any time. This means that the lifetime of an AID is much longer than that of any single static key pair, without harm to the threat model. The underlying key rotation routine does not change and in fact can be even more frequent. Rotation becomes a feature, not an exception.

Proactive measures instead of reactive cleanup!

Key rotation ceremony with DKMS (KERI)

Here’s what would happen with DKMS (KERI) in place:

1. The trust provider receives key compromise report from a 3rd party.
2. The trust provider handles the incident:
   1. She rotates the keys of the eight affected AIDs that signed the certificates, using the previously committed, uncompromised rotation keys. She may proactively rotate the root AID to the next committed key.
   2. Because all issued certificates are cryptographically anchored in the AID KEL, the authoritative issuance history is known, without any integration with Certificate Transparency. Affected certificates are immediately recognizable.

The most important consequence of employing DKMS (KERI), not possible with conventional X509 PKI?

The eight affected AIDs continue their operation.

Whatever certificates issued before the compromised keys were introduced remain valid, unless expired or revoked.

Therefore, a compromised CA signing key no longer means losing the CA identity or invalidating its entire issuance history.