Side-Channel ECDSA Explained: When Your Division Algorithm Can't Keep a Secret

Side-channel ECDSA Explained: When Your Division Algorithm Can’t Keep a Secret

Imagine you wrote your secret on a piece of paper, then shredded the paper, burned the shreddings, and scattered the ashes in the ocean. Pretty safe, right? Now imagine you did all that, but you also narrated every step of the process out loud, in real time, to someone standing next to you with a notebook. That’s what a side-channel leak looks like in software. The secret is gone, but the how of handling it is still audible.

This article walks through a specific side-channel vulnerability in a custom ECDSA implementation that uses a hand-rolled binary GCD algorithm for modular inversion. The masking is solid. The curve is standard. The key generation is fine. But the division algorithm whispers every step it takes through an execution trace, and that trace is enough to recover the private key from a single signature. We’ll break down exactly how, why, and what to do about it.

What Is Side-Channel ECDSA, Anyway?

ECDSA (Elliptic Curve Digital Signature Algorithm) is the signing scheme behind Bitcoin, TLS certificates, and a lot of other infrastructure you rely on daily. The core equation is:

s = k^(-1) * (z + r*d) mod n

Where d is the private key, k is a random nonce, z is the message hash, r is the x-coordinate of k*G, and n is the curve order. If k leaks (even partially), the private key d falls out with basic algebra. This is why every ECDSA implementation worth its salt treats the nonce like nuclear launch codes.

A side-channel attack exploits information that leaks through the physical execution of the algorithm rather than through a mathematical weakness. Power consumption, timing, electromagnetic emanations, and, in our case, explicit function-call tracing can all carry secret data out through channels the designer never intended to secure.

The vulnerability we’re looking at is particularly nasty because the implementation chose to expose an execution trace as a feature (for debugging or transparency), not realizing that the trace carries enough information to reconstruct the masked nonce mask * k, factor it, and recover k, which then trivially yields d.

Why Should You Care?

• Any custom crypto primitive that branches on secret data is a side-channel risk. If your code does if (secret_bit == 1), an attacker who can observe the branch can recover the bit.
• Masking doesn’t help if the mask is observable. Multiplying the nonce by a random blinding factor mask before processing is a standard defense. But if the product mask * k is recoverable from the trace, you just need to factor it.
• Factoring is getting cheaper. A 512-bit number that was “hard” to factor a decade ago is now achievable with ECM (Elliptic Curve Method) on a single machine in minutes to hours, especially if it has small factors.
• This is not theoretical. The attack we describe works on a single signature trace. No statistical averaging across many traces is needed.

The Setup: A “Safe” ECDSA Implementation

Consider a signing service that implements ECDSA on the P-256 curve with the following protections:

1. Scalar blinding for point multiplication: The nonce is blinded as k + mask1 * N before scalar multiplication, so the bit pattern processed by the double-and-add loop is not k’s bits.
2. Coordinate randomization: The base point and intermediate points have their Jacobian coordinates multiplied by random masks, preventing leakage through the point representation.
3. Nonce blinding for inversion: Both the numerator and denominator of the signature computation are multiplied by a fresh random mask2, so the modular inversion doesn’t directly process k.

Here’s what the signing function looks like (simplified, generic names):

def sign(private_key, message_hash):
    k = random_scalar()                    # fresh nonce

    # Blinding for scalar multiplication
    mask1 = random_scalar()
    blinded_k = k + mask1 * N              # k + mask1*N, NOT k's bits

    R = scalar_mul(blinded_k, randomized(G))
    r = R.x % N

    # Blinding for modular inversion
    mask2 = random_scalar()
    numerator = mask2 * (message_hash + r * private_key)   # mask2 * (z + r*d)
    denominator = mask2 * k                                   # mask2 * k (full bignum!)

    s = div(numerator, denominator, N)
    return (r, s)

Looks pretty good, right? Three independent random masks, no direct exposure of k. The problem is in div().

The Leak: Custom Binary Division

The div() function doesn’t use a standard modular inversion library. It calls a custom _binary_division_odd_modulus(a, b, modulus) that implements the binary GCD algorithm for modular division:

def div(a, b, modulus):
    a = a % modulus              # reduce numerator: mask2*(z+r*d) mod N
    return _binary_division_odd_modulus(a, b, modulus)  # b = mask2*k (UNREDUCED!)

Note that a is reduced mod N (256 bits), but b is passed as the full unreduced 512-bit bignum mask2 * k. This means the binary GCD operates on a 512-bit u and a 256-bit v = N, and the entire control flow depends on the bit pattern of u = mask2 * k.

Here’s the algorithm with annotations showing what leaks:

def _binary_division_odd_modulus(a, b, modulus):
    u = b          # = mask2 * k (512 bits) — THE SECRET IS IN u's BITS
    v = modulus    # = N (256 bits, known)
    x1 = a         # = mask2 * (z+r*d) mod N (256 bits)
    x2 = 0

    while u != 1 and v != 1:
        # Inner loop 1: strip trailing zeros of u
        while (u & 1) == 0:
            u = half(u)                       # LEAKS: "h" — tells you u was even
            if (x1 & 1) == 0:
                x1 = half(x1)                 # LEAKS: "hh" — x1 bit = 0
            else:
                x1 = half(add(x1, modulus))  # LEAKS: "hah" — x1 bit = 1

        # Inner loop 2: strip trailing zeros of v
        while (v & 1) == 0:
            v = half(v)                       # LEAKS: same pattern for v/x2

        # Subtraction (direction NOT directly leaked)
        if u >= v:
            u = sub(u, v)                     # LEAKS: "ss"
            x1 = sub(x1, x2)
        else:
            v = sub(v, u)                     # LEAKS: "ss" (same trace!)
            x2 = sub(x2, x1)

    if u == 1:
        return mod(x1, modulus)              # LEAKS: "r"
    return mod(x2, modulus)                  # LEAKS: "r"

Every call to half, add, sub, and mod is traced. The trace is a string of characters like hhsshahsshahss...r. From this string, an attacker can extract:

1. Strip counts (how many hh/hah patterns between ss markers): These equal the trailing-zero count of u or v at each step.
2. Bits revealed: Each hh means the corresponding x value had LSB=0, each hah means LSB=1.
3. Total iteration count: The number of ss patterns.

The Attack: Step by Step

Step 1: Recover a = mask2 * (z + r*d) mod N

Before the first v-subtraction (which happens when u shrinks below v = N), all subtractions are u-subtractions and all strips are u-strips. During this phase, x1 stays in [0, N), so its LSBs are directly the modular value’s bits.

The key formula: after K u-strips, x1_K = (a + N * S) / 2^K where S = sum of bits with weights 2^0, 2^1, ..., 2^{K-1}.

For x1_K to be a valid integer in [0, N), we need a + N * S ≡ 0 (mod 2^K), which gives:

a ≡ -N * S (mod 2^K)

The detection trick: Try K = 256, 257, 258, … For the correct K (the actual number of u-strips before the first v-sub), a = -N * S mod 2^K falls in [0, N). For any wrong K (where the bits include v-strip bits), it falls outside [0, N). In practice, exactly one K works, and it’s almost always 256.

Step 2: Recover u = mask2 * k (the full bignum)

With a known, compute u_red = a * s^(-1) mod N = mask2 * k mod N.

Then use constraint propagation on the strip counts. Before the first v-sub, all strips are u-strips. Each block’s strip count constrains u_init’s bits:

• Block 0: tz(u_init) strips → bits 0 to count0-1 are 0, bit count0 is 1
• Block K: the constraint involves the accumulated expression u_K = (u_init + beta) / 2^s, where beta and s are known from processing previous blocks

This gives u_init mod 2^L (typically L ≈ 257).

Finally, apply the Chinese Remainder Theorem:

• u_init mod 2^L is known from constraint propagation
• u_init mod N = u_red is known from the modular relationship

Since u_init < N^2 < 2^512 < 2^L * N, CRT uniquely determines u_init.

Step 3: Factor u_init

u_init = mask2 * k is a ~512-bit number. Both factors are ~256-bit. The factoring strategy:

1. Trial division up to 10^6: removes small prime factors
2. Pollard’s rho (Brent’s variant): finds factors up to ~25 digits
3. Pollard’s p-1: finds factors with smooth p-1
4. ECM (Elliptic Curve Method) with GMP-ECM: finds factors up to ~40 digits efficiently, and ~65 digits with enough curves

In practice, a combination of these methods factored the number completely. The key breakthrough was ECM with B1=10^8 finding a 105-bit (32-digit) prime factor.

Step 4: Enumerate divisors and find k

With the full factorization, enumerate all divisors of u_init that fall in (u_init/N, N) (since mask2 = u_init/k < N means k > u_init/N). This typically gives only a handful of candidates.

For each candidate k:

d = (s * k - z) * inverse(r, N) mod N

Verify by checking d * G == public_key.

Vulnerable Code Examples

Vulnerable: traced binary division

# VULNERABLE: every half/add/sub call is traced, leaking the control flow
def binary_division_traced(a, b, modulus):
    u, v, x1, x2 = b, modulus, a, 0
    while u != 1 and v != 1:
        while u % 2 == 0:
            u = trace_half(u)         # leaks 'h'
            x1 = trace_half(x1) if x1 % 2 == 0 else trace_half(trace_add(x1, modulus))  # leaks 'h' or 'ah'
        while v % 2 == 0:
            v = trace_half(v)
            # ... same pattern for x2
        if u >= v:
            u = trace_sub(u, v)       # leaks 's'
            x1 = trace_sub(x1, x2)    # leaks 's'
        else:
            v = trace_sub(v, u)
            x2 = trace_sub(x2, x1)
    return trace_mod(x1 if u == 1 else x2, modulus)

The problem: the entire control flow is determined by the bit pattern of u = mask * k, and every branching decision is observable through the trace.

Patched: constant-time inversion

# SAFE: use a standard, constant-time modular inversion library
def div_safe(a, b, modulus):
    a = a % modulus
    b_inv = pow(b, -1, modulus)  # Python 3.8+ uses constant-time inversion
    return (a * b_inv) % modulus

Or, if you must implement your own, at least don’t trace it:

# BETTER: same algorithm, but no tracing of internal operations
def binary_division_untraced(a, b, modulus):
    u, v, x1, x2 = b, modulus, a, 0
    while u != 1 and v != 1:
        while u % 2 == 0:
            u = u // 2                    # no trace call
            x1 = x1 // 2 if x1 % 2 == 0 else (x1 + modulus) // 2
        while v % 2 == 0:
            v = v // 2
            x2 = x2 // 2 if x2 % 2 == 0 else (x2 + modulus) // 2
        if u >= v:
            u, x1 = u - v, x1 - x2
        else:
            v, x2 = v - u, x2 - x1
    return (x1 if u == 1 else x2) % modulus

The fix is simple: don’t expose execution traces of cryptographic operations, and preferably don’t implement your own modular arithmetic at all.

Defense / How to Fix

1. Never trace cryptographic internals. If you need debugging traces, gate them behind a compile-time flag that is off in production. Better yet, don’t trace crypto at all.

2. Use vetted crypto libraries. Python’s pow(b, -1, N) (3.8+), OpenSSL, libsodium, and other established libraries use constant-time algorithms that don’t branch on secret data. Your custom binary GCD does not.

3. Don’t pass unreduced secrets through side-channel-leaky code. In the vulnerable code, b = mask2 * k is passed as a 512-bit unreduced bignum. If b were reduced mod N before the division, the binary GCD would operate on a 256-bit value and the leakage would be different (though still not zero).

4. Validate that masking actually helps. If you blind the nonce with mask2, make sure the product mask2 * k is not recoverable from any observable channel. In this case, the binary GCD’s control flow on the unreduced product completely defeats the masking.

5. Consider deterministic nonces (RFC 6979). If you use deterministic nonces derived from the message and private key, you eliminate the fresh randomness requirement. But you still need constant-time implementation.

6. Audit custom big-integer code. Any if statement that branches on a value derived from the secret is a potential leak. Use constant-time comparisons (bitwise operations) instead.

Final Thoughts

The irony of this vulnerability is that the developers clearly tried to be secure. They added three layers of randomization: scalar blinding, coordinate randomization, and inversion blinding. They used a “constant-time” binary GCD (constant-time in the sense that it always calls point_double and point_add in the scalar multiplication loop). They probably felt pretty good about it.

But they also added a trace feature that records every half, add, and sub call inside the division algorithm. And the division algorithm processes the unreduced product mask2 * k as a 512-bit number. The trace reveals the complete control flow of the binary GCD on this 512-bit value, which uniquely determines mask2 * k. From there, factoring gives k, and k gives d.

The lesson isn’t “don’t use binary GCD” or “don’t add tracing.” The lesson is: if your crypto implementation branches on secret-derived data in any observable way, you have a side channel. Masking the input doesn’t help if the mask * product is observable. The safest division algorithm is the one the standard library already implemented, tested, and audited. Use it.