Finding Weak ECDSA Keys: A Lesson from the eMudhra Incident

2026-10-25

In October 2026, eight intermediate CA certificates from eMudhra were revoked after a researcher named Wayne discovered their private keys were trivially small integers. The values ranged from 4 to 237 -- numbers that fit in a single byte, when they should have been 384-bit scalars with full entropy. Following the incident, eMudhra decided to withdraw from the TLS business.

This post presents a simple script to detect such weak keys along with a working demonstration, illustrating the math behind it. Originally, Wayne ran a significantly more comprehensive and sophisticated tool called paranoid_crypto to detect the weak keys.

The Vulnerability

ECDSA public keys are derived deterministically from a private key scalar d through scalar multiplication: Q = d × G, where G is the curve generator point. If d is small, an attacker can enumerate candidate values k, compute k × G for each, and compare against the target public key.

For the eMudhra case, the compromised private keys were: 4, 56, 66, 115, 155, 156, 230, and 237. Testing all 256 single-byte values takes milliseconds.

The Detection Tool

The following Python script tests ECDSA certificates for weak private keys by brute-forcing candidate scalars and comparing derived public keys:

#!/usr/bin/env python3
"""
Weak ECDSA Private Key Finder

Tests whether a NIST P-384 ECDSA public key was generated from a small private key value.
Inspired by the eMudhra CA incident of October 2026 and paranoid_crypto.

Usage:
    python3 weak_ecdsa_keyfinder.py <certificate.pem> [max_key_value]
"""

import sys
from cryptography import x509

# P-384 curve parameters
P384_P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF
P384_A = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC
P384_Gx = 0xAA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7
P384_Gy = 0x3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F


def point_add(P, Q, p, a):
    """Add two points on an elliptic curve."""
    if P is None:
        return Q
    if Q is None:
        return P
    if P[0] == Q[0]:
        if (P[1] + Q[1]) % p == 0:
            return None
        lam = (3 * P[0] * P[0] + a) * pow(2 * P[1], -1, p) % p
    else:
        lam = (Q[1] - P[1]) * pow(Q[0] - P[0], -1, p) % p
    x3 = (lam * lam - P[0] - Q[0]) % p
    y3 = (lam * (P[0] - x3) - P[1]) % p
    return (x3, y3)


def scalar_mult(k, G, p, a):
    """Multiply point G by scalar k."""
    result = None
    addend = G
    while k:
        if k & 1:
            result = point_add(result, addend, p, a)
        addend = point_add(addend, addend, p, a)
        k >>= 1
    return result


def find_weak_key(pub_x, pub_y, max_search=256):
    """Search for weak private key by testing values 1 to max_search."""
    G = (P384_Gx, P384_Gy)
    print(f"Searching range 1 to {max_search}...")

    for candidate in range(1, max_search + 1):
        Q = scalar_mult(candidate, G, P384_P, P384_A)
        if Q and Q[0] == pub_x and Q[1] == pub_y:
            return candidate
        if candidate % 50 == 0:
            print(f"  Tested {candidate} candidates...")
    return None


def main():
    if len(sys.argv) < 2:
        print(f"Usage: python3 {sys.argv[0]} <cert.pem> [max_value]")
        sys.exit(1)

    with open(sys.argv[1], "rb") as f:
        cert = x509.load_pem_x509_certificate(f.read())

    pub = cert.public_key().public_numbers()
    print(f"Certificate: {sys.argv[1]}")
    print(f"Public key x: {hex(pub.x)}")
    print(f"Public key y: {hex(pub.y)}")

    result = find_weak_key(pub.x, pub.y, int(sys.argv[2]) if len(sys.argv) > 2 else 256)

    if result:
        print(f"\n[+] WEAK KEY FOUND: {result} (0x{result:x})")
        print("This certificate should be immediately revoked.")
    else:
        print("\n[-] No weak key found in search range.")


if __name__ == "__main__":
    main()

The code above implements the double-and-add method on an elliptic curve. See this blog post by Abhiveer Singh for a brief introduction to implementing elliptic curve cryptography.

The private key can also be recovered using more general and advanced methods like the baby-step giant-step algorithm. See paranoid_crypto for an implementation of such a more advanced approach.

Side note: In October 2026, Anthropic found out how the the NIST elliptic curve seeds were originally created. The seeds were generated using the srand48 pseudo-random number generator with timestamps from 1997 and 1998 as input.

Demonstration

To validate the script, I obtained the EM EV TLS CA - G3B eMudhra extended validation certificate from Dennis Jackson's eMudhra website. Given the public key contained in the certificate, it recovered the corresponding private key by checking scalars in the range from 1 through 256:

$ time python3 weak_ecdsa_keyfinder.py em-ev-tls-ca-g3b.pem 256
Certificate: em-ev-tls-ca-g3b.pem
Public key x: 0x25dba85a64d397da0b1052e9ea546e487befea9c9d9d68a0c5eadcfeef75a69bb5d6fc01f42bfbca6eb40bcd64c0767e
Public key y: 0x36ffd05d97a813c5aa0c6c9530e79cf5f0866468f13806420aa5c851840b1e252540e790e4b654c3852ed64af1e8657d
Searching range 1 to 256...
  Tested 50 candidates...
  Tested 100 candidates...

[+] WEAK KEY FOUND: 115 (0x73)
This certificate should be immediately revoked.

real	0m0.081s
user	0m0.063s
sys	0m0.018s

The script identified the weak key 115 in a fraction of a second. The result agrees with the analysis by Scott Helme and Fenko Security.

Context and Credits

The eMudhra vulnerability was discovered by a researcher named Wayne using Google's paranoid_crypto project against the Common Certificate Authority Database (CCADB). That tool includes comprehensive tests for many weak key patterns beyond simple small scalars, including:

RSA key factorization attacks (ROCA, Fermat factorization, Pollard p-1)
Shared prime detection via GCD
Biased nonce attacks on ECDSA signatures
Known weak key denylists

The script presented here focuses specifically on the small-scalar ECDSA case for educational purposes. For auditing certificate databases, choose a more sophisticated tool.

To test whether your browser and non-browser tools using TLS like curl trust the compromised eMudhra certificates, follow the instructions from Dennis Jackson's emudhra.we-have-a-problem.com page. As programming languages may bundle their own trust store of certificates, Jan Schaumann wrote a testing tool for this purpose.

Takeaway

Proper random number generation is fundamental to cryptographic security. A 384-bit curve provides no security if the private scalar fits in one byte. Certificate authorities must validate generated keys meet minimum entropy requirements before deployment -- and auditors should verify this check occurs.

Test your own certificates as well as certificates from trust stores and report findings responsibly.

Fabian's Lines of Thought