THE GARDEN

XOR-Instead-of-Exponentiation Notation Bug (Diffie-Hellman)

Updated 13 Sep 2026

• •

  What it is

  • •

    A specific, memorable implementation bug where a "Diffie-Hellman" implementation accidentally uses the bitwise XOR operator (^) instead of exponentiation (**/pow) — sometimes from genuine confusion (many languages use ^ for exponentiation, but Python and C-family languages use it for XOR), sometimes compounded by an operator precedence mistake on top. In the specific case here, the code g ^ a % p looks like it should mean $(g^a) \bmod p$, but Python evaluates % before ^, so it actually computes $g \oplus (a \bmod p)$ — a completely different, trivially breakable operation (XOR is its own inverse and commutative/associative, giving zero cryptographic hardness — the exact same underlying weakness as Additive Group Diffie-Hellman Break (Trivial Discrete Log in Additive Groups), just via XOR instead of addition).

• •

  When to apply

  • •

    Source code labeled as Diffie-Hellman uses ^ anywhere near where exponentiation should appear — always check the actual operator precedence and semantics rather than trusting variable names like generate_public_int.

• •

  Math

  • •

    With $b < q < p$ (so $b \bmod p = b$ trivially), the "public value" $B = g \oplus b$; since $A = g \oplus a$ similarly, and the "shared secret" is computed as $A \oplus b$: $\text{shared} = A \oplus b = (g\oplus a)\oplus b$. An eavesdropper who intercepts $A$, $g$, and $B$ can recover the same value directly: $A \oplus g \oplus B = (g\oplus a) \oplus g \oplus (g \oplus b) = g \oplus a \oplus b$ — matching the legitimate shared secret exactly, using nothing but public values.

• •

  Worked example

  • •

    Given intercepted $A$, $g=2$, and $B$ from a real captured exchange, computing $A \oplus g \oplus B$ directly reproduced the exact AES key both parties derived — no private values, no search, just three XORs.

• •

  Python

  • •

    shared_secret = A ^ g ^ B   # recovers the "shared secret" from public values alone
    

• •

  Related

  • •

    Diffie-Hellman (Textbook Construction)

  • •

    Additive Group Diffie-Hellman Break (Trivial Discrete Log in Additive Groups)

• •

  Cards

  • •

    What's the specific Python gotcha that turns "exponentiation" into XOR here?

    • •

      % binds tighter than ^ in Python, so g ^ a % p evaluates as g ^ (a % p), not (g ^ a) % p — silently replacing modular exponentiation with plain XOR.

  • •

    Why can an eavesdropper recover the shared secret from just the three public values A, g, B?

    • •

      Because XOR is commutative, associative, and self-inverse, so A ^ g ^ B algebraically cancels down to exactly the same value both legitimate parties compute.

◌ Explore connections in Graph view