Break: Recovering DH Secrets from Partial Bit Leakage

Module 05 | Breaking Weak Parameters

Leaking even a fraction of the secret exponent's bits can compromise Diffie-Hellman.

Why This Matters

In theory, Diffie-Hellman is secure if the secret exponent $a$ is completely hidden. In practice, side-channel attacks can leak partial information:

Timing attacks reveal bits through computation time differences
Power analysis measures electrical consumption during exponentiation
Cache attacks observe memory access patterns
Cold boot attacks recover partial memory contents

If the attacker learns the top half of the bits of $a$ , the remaining bits can be brute-forced in $O(\sqrt{p})$ instead of $O(p)$ . If even more bits leak, the search shrinks further.

The Scenario

Alice performs DH with secret exponent $a$ . A side-channel attack leaks the top $k$ bits of $a$ . The attacker knows:

a = a_{\text{known}} \cdot 2^m + a_{\text{unknown}}

where $a_{\text{known}}$ is the leaked top bits, $m$ is the number of unknown bits, and $0 \leq a_{\text{unknown}} < 2^m$ .

We use small numbers to make the attack concrete and observable.

In [ ]:

# === Step 1: Set up DH with a manageable prime ===

p = 1009  # a prime
g = primitive_root(p)
print(f'p = {p}, g = {g}')
print(f'p - 1 = {p - 1} = {factor(p - 1)}')
print()

# Alice's secret exponent (10 bits)
a = 743  # binary: 1011100111
A = power_mod(g, a, p)
print(f"Alice's secret: a = {a}")
print(f'a in binary:    {bin(a)}')
print(f'Bit length:     {a.bit_length()} bits')
print(f"Alice's public: A = g^a mod p = {A}")
print()
print(f'Full brute-force search space: {p - 1} values')

In [ ]:

# === Step 2: Attacker learns the top half of the bits ===

total_bits = a.bit_length()  # 10 bits
leaked_bits = total_bits // 2  # top 5 bits
unknown_bits = total_bits - leaked_bits  # bottom 5 bits

# The known top bits
a_known = a >> unknown_bits  # shift right to get top bits
# The unknown bottom bits
a_unknown = a % (2^unknown_bits)

print(f'Secret a in binary: {bin(a)} ({total_bits} bits)')
print(f'Known top {leaked_bits} bits:   {bin(a_known)} = {a_known}')
print(f'Unknown bottom {unknown_bits} bits: {bin(a_unknown)} = {a_unknown}')
print()
print(f'a = {a_known} * 2^{unknown_bits} + a_unknown')
print(f'  = {a_known} * {2^unknown_bits} + a_unknown')
print(f'  = {a_known * 2^unknown_bits} + a_unknown')
print()
print(f'Search space reduced from {p - 1} to {2^unknown_bits} values')
print(f'Reduction factor: {(p - 1) / 2^unknown_bits:.1f}x')

In [ ]:

# === Step 3: Brute-force the unknown bottom bits ===

# Attacker knows: A = g^a mod p, and a = a_known * 2^m + a_unknown
# So: A = g^(a_known * 2^m + a_unknown) mod p
#     A = g^(a_known * 2^m) * g^(a_unknown) mod p
# Rearranging:
#     A * g^(-a_known * 2^m) = g^(a_unknown) mod p
# The left side is known! Just compute it and match against g^x for small x.

m = unknown_bits
known_part = power_mod(g, a_known * 2^m, p)
# target = A * inverse(known_part) mod p
target = (A * power_mod(known_part, -1, p)) % p

print(f'Known part: g^({a_known} * 2^{m}) mod p = {known_part}')
print(f'Target:     A * g^(-{a_known * 2^m}) mod p = {target}')
print(f'Need to find x such that g^x = {target} mod p, with 0 <= x < {2^m}')
print()

# Brute force the unknown bits
attempts = 0
for x in range(2^m):
    attempts += 1
    if power_mod(g, x, p) == target:
        a_recovered = a_known * 2^m + x
        print(f'Found after {attempts} attempts!')
        print(f'Unknown bits: {x} (binary: {bin(x)})')
        print(f'Recovered a:  {a_recovered}')
        print(f'Actual a:     {a}')
        print(f'Match: {a_recovered == a}')
        break

# Verify
print()
print(f'Verification: g^{a_recovered} mod p = {power_mod(g, a_recovered, p)}')
print(f'Alice\'s A:                         {A}')
print(f'Match: {power_mod(g, a_recovered, p) == A}')

Meet-in-the-Middle: Even Faster with Partial Knowledge

If the attacker knows the top and bottom bits (but not the middle), a meet-in-the-middle approach works:

Split the unknown middle into two halves. Precompute one half, then search the other. This gives $O(2^{m/2})$ time and space instead of $O(2^m)$ .

Even when only the top bits are known, we can apply a BSGS-style meet-in-the-middle on the unknown portion.

In [ ]:

# === Meet-in-the-middle on the unknown bits ===

# Split the m unknown bits into two halves
m_low = m // 2        # bottom half of unknown bits
m_high = m - m_low    # top half of unknown bits

# a_unknown = a_high * 2^m_low + a_low
# where 0 <= a_high < 2^m_high and 0 <= a_low < 2^m_low

# From: target = g^(a_unknown) mod p
#       target = g^(a_high * 2^m_low + a_low) mod p
#       target * g^(-a_low) = g^(a_high * 2^m_low) mod p

# Baby step: precompute { target * g^(-a_low) : a_low } in a dictionary
# Giant step: for each a_high, compute g^(a_high * 2^m_low) and look up

print(f'Unknown bits: {m}')
print(f'Split: {m_high} high bits + {m_low} low bits')
print(f'Brute force cost:       {2^m} operations')
print(f'Meet-in-the-middle:     {2^m_high + 2^m_low} operations')
print()

# Baby step: precompute target * g^(-a_low) for all a_low
g_inv = power_mod(g, -1, p)
baby_steps = {}
val = target
for a_low in range(2^m_low):
    baby_steps[val] = a_low
    val = (val * g_inv) % p

print(f'Baby steps computed: {len(baby_steps)} entries')

# Giant step: g^(2^m_low)
giant_stride = power_mod(g, 2^m_low, p)

found = False
val = 1  # g^(0 * 2^m_low)
for a_high in range(2^m_high):
    if val in baby_steps:
        a_low = baby_steps[val]
        a_unknown_recovered = a_high * 2^m_low + a_low
        a_full = a_known * 2^m + a_unknown_recovered
        print(f'Giant step hit at a_high = {a_high}, a_low = {a_low}')
        print(f'Recovered unknown bits: {a_unknown_recovered}')
        print(f'Recovered a: {a_full}')
        print(f'Actual a:    {a}')
        print(f'Match: {a_full == a}')
        found = True
        break
    val = (val * giant_stride) % p

if not found:
    print('Not found (should not happen)')

In [ ]:

# === Vary the number of leaked bits and measure search cost ===

print(f'Secret a = {a} ({a.bit_length()} bits)')
print(f'Public A = {A}')
print()
print('Leaked bits Unknown bits Search space Reduction')
for leaked in range(0, a.bit_length() + 1):
    unknown = a.bit_length() - leaked
    search = 2^unknown
    reduction = (p - 1) / search if search > 0 else float('inf')
    print(f'{leaked} {unknown} {search} {reduction:>10.1f}x')

print()
print('Each leaked bit HALVES the search space.')
print('Half the bits leaked = search space reduced to sqrt(p).')

The Fix: Constant-Time Implementations

Preventing bit leakage requires:

Constant-time modular exponentiation: every bit of the exponent must take the same time to process (e.g., Montgomery ladder).
Blinding: multiply the base by a random value before exponentiation, then remove it afterward. This decorrelates side-channel signals from the secret.
Key erasure: delete ephemeral secrets immediately after use. This limits the window for cold boot or memory dump attacks.

The lesson: even if the DLP is computationally hard, side channels can give the attacker a shortcut by leaking bits of the answer.

Exercises

Bottom bits leaked: Suppose the attacker knows the bottom 5 bits instead of the top 5. Modify the attack. Is the search equally efficient?
Scattered bits: What if the attacker knows bits 0, 2, 4, 6, 8 (every other bit)? How would you structure the search? (Hint: the unknown bits are interleaved, so simple splitting doesn't apply directly.)
Larger example: Use $p = 104729$ (a 17-bit prime). Set a random 16-bit secret. Leak the top 8 bits and brute-force the bottom 8. How long does it take?

Summary

Leaked bits	Search space	Attack cost
0 (none)	$p - 1$	Full DLP
Half	$\sqrt{p}$	Feasible brute force
All but $k$	$2^k$	Trivial

Key takeaways:

Each leaked bit halves the attacker's search space.
Leaking half the bits reduces the DLP from $O(p)$ to $O(\sqrt{p})$ .
Meet-in-the-middle further improves the attack when partial bits are known.
Side-channel resistance (constant-time code, blinding) is essential.
Mathematical hardness alone does not guarantee security --- implementation matters.

Back to Module 05: Discrete Log and Diffie-Hellman