weak-sbox-reducible-poly.ipynb

Kernel: SageMath 10.0

Break: Weak S-box from Reducible Polynomial

Module 03 | Breaking Weak Parameters

The AES S-box derives its strength from GF(2^8) inversion. Use the wrong polynomial and the field falls apart.

Why This Matters

The AES S-box maps each byte $b$ to its multiplicative inverse in GF($2^8$), then applies an affine transformation. This relies on a critical assumption: every nonzero byte has a unique inverse.

That property only holds if the modulus polynomial is irreducible over GF(2). The AES standard uses $m(x) = x^8 + x^4 + x^3 + x + 1$, which is irreducible, so $\text{GF}(2)[x] / \langle m(x) \rangle$ is a genuine field with 255 invertible elements.

But what if someone accidentally (or maliciously) uses a reducible polynomial? Then the quotient ring is not a field --- it has zero divisors, elements with no inverse. The S-box construction breaks down, and the result is cryptographically weak.

The Scenario

A careless implementer builds "AES" using the polynomial $p(x) = x^8 + x^4$ instead of the correct $m(x) = x^8 + x^4 + x^3 + x + 1$.

The polynomial $x^8 + x^4 = x^4(x^4 + 1) = x^4(x+1)^4$ factors over GF(2), so the quotient ring $\text{GF}(2)[x] / \langle x^8 + x^4 \rangle$ is not a field.

Your job: show that this breaks the S-box and produces exploitable weaknesses.

# === Setup: the correct AES field and the broken quotient ring ===
R.<x> = GF(2)[]

# The correct AES modulus (irreducible)
m_aes = x^8 + x^4 + x^3 + x + 1
print(f'AES polynomial: {m_aes}')
print(f'  Irreducible? {m_aes.is_irreducible()}')
print()

# The broken modulus (reducible)
m_bad = x^8 + x^4
print(f'Bad polynomial: {m_bad}')
print(f'  Irreducible? {m_bad.is_irreducible()}')
print(f'  Factorization: {m_bad.factor()}')
print()
print('The bad polynomial factors as x^4 * (x + 1)^4.')
print('This means the quotient ring has ZERO DIVISORS.')

Step 1: Identify Zero Divisors

In a field, $ab = 0$ implies $a = 0$ or $b = 0$. In a ring with zero divisors, you can have $ab = 0$ with both $a \neq 0$ and $b \neq 0$.

If $a$ is a zero divisor, then $a$ has no multiplicative inverse (proof: if $a^{-1}$ existed, then $ab = 0 \Rightarrow b = a^{-1} \cdot 0 = 0$, contradicting $b \neq 0$).

Let's find all zero divisors in $\text{GF}(2)[x] / \langle x^8 + x^4 \rangle$.

# Work in the quotient ring GF(2)[x] / <x^8 + x^4>
Q.<t> = R.quotient(m_bad)

# Helper: convert a byte (0-255) to a ring element
def byte_to_ring(b, ring_gen):
    return sum(GF(2)((b >> i) & 1) * ring_gen^i for i in range(8))

def ring_to_byte(elem):
    coeffs = elem.lift().coefficients(sparse=False)
    return sum(int(coeffs[i]) << i for i in range(min(8, len(coeffs))))

# Find all elements that have NO multiplicative inverse
non_invertible = []
invertible = []

for b in range(256):
    elem = byte_to_ring(b, t)
    if b == 0:
        non_invertible.append(b)  # 0 is never invertible
        continue
    # Check if gcd(polynomial, modulus) = 1
    poly_rep = elem.lift()
    g = gcd(poly_rep, m_bad)
    if g.degree() > 0:
        non_invertible.append(b)
    else:
        invertible.append(b)

print(f'Total elements: 256')
print(f'Invertible (have an inverse): {len(invertible)}')
print(f'Non-invertible (zero divisors + zero): {len(non_invertible)}')
print()
print(f'In a proper field GF(2^8): 255 invertible, 1 non-invertible (just zero).')
print(f'In this broken ring: {len(invertible)} invertible, {len(non_invertible)} non-invertible.')
print(f'That\'s {len(non_invertible) - 1} nonzero elements with NO inverse!')

# Show some concrete zero divisors
print('=== Concrete zero divisor examples ===')
print()

# x^4 is a zero divisor because x^4 * (x^4 + 1) = x^8 + x^4 = 0 in the ring
a_elem = byte_to_ring(0x10, t)  # x^4 = byte 0x10
b_elem = byte_to_ring(0x10, t) + byte_to_ring(0x01, t)  # x^4 + 1 = byte 0x11
product = a_elem * b_elem
print(f'a = x^4      (byte 0x10)')
print(f'b = x^4 + 1  (byte 0x11)')
print(f'a * b = {product}  (in the quotient ring)')
print(f'Both nonzero, but product = 0. These are zero divisors!')
print()

# List the first few non-invertible nonzero bytes
print('First 20 non-invertible nonzero bytes (hex):')
print(' '.join(f'0x{b:02X}' for b in non_invertible[1:21]))
print(f'... ({len(non_invertible) - 1} total)')

Step 2: Build the Broken S-box

The AES S-box construction:

1. Compute $b^{-1}$ in GF($2^8$) (with $0 \mapsto 0$)

2. Apply the affine transformation $A \cdot b^{-1} + c$

With our broken polynomial, step 1 fails for every zero divisor --- there is no inverse. The implementer is forced to patch these entries, typically mapping them to 0 (like the real S-box does for input 0). This creates a large number of collisions and fixed points.

# Build both S-boxes: the real AES one and the broken one

# --- Real AES S-box (using irreducible polynomial) ---
F.<a> = GF(2^8, modulus=m_aes)

def byte_to_gf(b):
    return sum(GF(2)((b >> i) & 1) * a^i for i in range(8))

def gf_to_byte(elem):
    p = elem.polynomial()
    return sum(int(p[i]) << i for i in range(8))

# Affine transformation components
A_mat = matrix(GF(2), [
    [1,0,0,0,1,1,1,1],[1,1,0,0,0,1,1,1],[1,1,1,0,0,0,1,1],[1,1,1,1,0,0,0,1],
    [1,1,1,1,1,0,0,0],[0,1,1,1,1,1,0,0],[0,0,1,1,1,1,1,0],[0,0,0,1,1,1,1,1]
])
c_vec = vector(GF(2), [(0x63 >> i) & 1 for i in range(8)])

def byte_to_bits(b):
    return vector(GF(2), [(b >> i) & 1 for i in range(8)])

def bits_to_byte(v):
    return sum(int(v[i]) << i for i in range(8))

def make_sbox_real():
    sbox = [0] * 256
    for b in range(256):
        if b == 0:
            inv_bits = byte_to_bits(0)
        else:
            inv_byte = gf_to_byte(byte_to_gf(b)^(-1))
            inv_bits = byte_to_bits(inv_byte)
        sbox[b] = bits_to_byte(A_mat * inv_bits + c_vec)
    return sbox

real_sbox = make_sbox_real()

# --- Broken S-box (using reducible polynomial) ---
def make_sbox_broken():
    sbox = [0] * 256
    non_inv_set = set(non_invertible)
    for b in range(256):
        if b in non_inv_set:
            # No inverse exists! Patch: map to 0 like the real S-box does for 0
            inv_bits = byte_to_bits(0)
        else:
            # Compute inverse in the quotient ring
            poly_rep = byte_to_ring(b, t).lift()
            inv_poly = poly_rep.inverse_mod(m_bad)
            inv_byte = sum(int(inv_poly[i]) << i for i in range(min(8, inv_poly.degree() + 1)))
            inv_bits = byte_to_bits(inv_byte)
        sbox[b] = bits_to_byte(A_mat * inv_bits + c_vec)
    return sbox

broken_sbox = make_sbox_broken()

print('Both S-boxes built.')
print(f'Real S-box[0x53] = 0x{real_sbox[0x53]:02X}')
print(f'Broken S-box[0x53] = 0x{broken_sbox[0x53]:02X}')

Step 3: Measure the Damage --- Fixed Points and Collisions

A good S-box should be a bijection (permutation): every input maps to a unique output. The real AES S-box has:

• 256 distinct outputs (bijection)

• 0 fixed points ($S(b) \neq b$ for all $b$)

The broken S-box will fail both tests because all non-invertible inputs get patched to the same value $A \cdot 0 + c = c = \texttt{0x63}$.

# Compare structural properties
print('=== S-box Quality Comparison ===')
print()

# Bijectivity
real_distinct = len(set(real_sbox))
broken_distinct = len(set(broken_sbox))
print(f'Distinct output values:')
print(f'  Real AES S-box:   {real_distinct} / 256  (bijection: {real_distinct == 256})')
print(f'  Broken S-box:     {broken_distinct} / 256  (bijection: {broken_distinct == 256})')
print()

# Fixed points: S(b) = b
real_fixed = [b for b in range(256) if real_sbox[b] == b]
broken_fixed = [b for b in range(256) if broken_sbox[b] == b]
print(f'Fixed points (S(b) = b):')
print(f'  Real AES S-box:   {len(real_fixed)}')
print(f'  Broken S-box:     {len(broken_fixed)}')
if broken_fixed:
    print(f'  Broken fixed points: {" ".join(f"0x{b:02X}" for b in broken_fixed[:10])}{"..." if len(broken_fixed) > 10 else ""}')
print()

# Collisions: how many inputs map to 0x63?
real_to_63 = sum(1 for b in range(256) if real_sbox[b] == 0x63)
broken_to_63 = sum(1 for b in range(256) if broken_sbox[b] == 0x63)
print(f'Inputs mapping to 0x63:')
print(f'  Real AES S-box:   {real_to_63}  (exactly 1, since it\'s a bijection)')
print(f'  Broken S-box:     {broken_to_63}  (all {len(non_invertible)} non-invertible elements!)')
print()
print(f'An attacker who sees ciphertext byte 0x63 knows the plaintext was one of')
print(f'{broken_to_63} possible values --- massive information leak!')

Step 4: Measure Non-linearity

The non-linearity of an S-box measures how far it is from any affine function. Higher is better. We compute it using the Walsh-Hadamard transform: for each pair of input mask $\beta$ and output mask $\alpha$, count the bias of the linear approximation $\alpha \cdot S(x) = \beta \cdot x$.

$$\text{NL}(S) = \frac{2^n - \max_{\alpha \neq 0} \max_\beta |W_S(\alpha, \beta)|}{2}$$

For an 8-bit S-box, the theoretical maximum is 120. The real AES S-box achieves 112.

def compute_nonlinearity(sbox):
    """Compute the nonlinearity of a 256-entry S-box."""
    n = 8
    max_walsh = 0
    for alpha in range(1, 256):  # output mask (nonzero)
        for beta in range(256):  # input mask
            walsh = 0
            for x in range(256):
                in_parity = bin(x & beta).count('1') % 2
                out_parity = bin(sbox[x] & alpha).count('1') % 2
                walsh += (-1)^(in_parity ^^ out_parity)
            max_walsh = max(max_walsh, abs(walsh))
    return (256 - max_walsh) // 2

print('Computing nonlinearity (this takes ~30 seconds per S-box)...')
print()

nl_real = compute_nonlinearity(real_sbox)
print(f'Nonlinearity of real AES S-box:   {nl_real}  (out of 120 max)')

nl_broken = compute_nonlinearity(broken_sbox)
print(f'Nonlinearity of broken S-box:     {nl_broken}  (out of 120 max)')
print()

if nl_broken < nl_real:
    print(f'The broken S-box has LOWER nonlinearity ({nl_broken} vs {nl_real}).')
    print(f'This means better linear approximations exist --- fuel for linear cryptanalysis.')
else:
    print(f'Nonlinearity comparison: broken={nl_broken} vs real={nl_real}')

# Compute the Linear Approximation Table (LAT) bias for both S-boxes
# This shows the maximum bias any linear approximation has

def max_lat_bias(sbox):
    """Find the maximum bias in the linear approximation table."""
    max_bias = 0
    worst_alpha, worst_beta = 0, 0
    for alpha in range(1, 256):
        for beta in range(1, 256):
            count = 0
            for x in range(256):
                if bin(x & beta).count('1') % 2 == bin(sbox[x] & alpha).count('1') % 2:
                    count += 1
            bias = abs(count - 128)
            if bias > max_bias:
                max_bias = bias
                worst_alpha, worst_beta = alpha, beta
    return max_bias, worst_alpha, worst_beta

print('Computing maximum LAT bias...')
print()

bias_real, a_r, b_r = max_lat_bias(real_sbox)
print(f'Real AES S-box:')
print(f'  Max bias: {bias_real}/128  (masks alpha=0x{a_r:02X}, beta=0x{b_r:02X})')
print(f'  Probability of best linear approx: {(128 + bias_real)/256:.4f}')
print()

bias_broken, a_b, b_b = max_lat_bias(broken_sbox)
print(f'Broken S-box:')
print(f'  Max bias: {bias_broken}/128  (masks alpha=0x{a_b:02X}, beta=0x{b_b:02X})')
print(f'  Probability of best linear approx: {(128 + bias_broken)/256:.4f}')
print()

print(f'Higher bias = easier to attack with linear cryptanalysis.')
print(f'The broken S-box has {bias_broken/bias_real:.1f}x the bias of the real S-box.')

The Fix

AES uses the irreducible polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$.

This guarantees that $\text{GF}(2)[x] / \langle m(x) \rangle$ is a field with 255 invertible nonzero elements. No zero divisors, no patching, no collisions.

The choice of irreducible polynomial was not arbitrary --- the AES designers verified irreducibility and chose a polynomial that also gives efficient hardware implementation (the specific terms $x^4 + x^3 + x + 1$ correspond to a low-weight reduction step).

# Verify the AES polynomial and explore alternatives
print('=== Irreducible degree-8 polynomials over GF(2) ===')
print()

# The AES polynomial
print(f'AES: m(x) = {m_aes}')
print(f'  Irreducible: {m_aes.is_irreducible()}')
print()

# Count how many degree-8 irreducible polynomials exist
irred_count = 0
irred_examples = []
for coeffs in range(256):  # middle 8 coefficients (x^1 through x^7, x^0 must be 1, x^8 must be 1)
    p = x^8 + sum(GF(2)((coeffs >> i) & 1) * x^(i+1) for i in range(7)) + 1  # monic, constant term 1
    if p.is_irreducible():
        irred_count += 1
        if irred_count <= 5:
            irred_examples.append(p)

print(f'Total irreducible degree-8 polynomials over GF(2): {irred_count}')
print(f'First few examples:')
for p in irred_examples:
    print(f'  {p}')
print()
print(f'Any of these {irred_count} polynomials would produce a valid field.')
print(f'AES chose {m_aes} for implementation efficiency.')

Exercises

Exercise 1

Try the reducible polynomial $p(x) = x^8 + x^6 + x^4 + x^2 = x^2(x^2+1)^3$. How many non-invertible elements does the quotient ring have? Build the S-box and compare its nonlinearity to the real one.

Exercise 2

Try $p(x) = x^8 + 1 = (x+1)^8$ over GF(2). This polynomial has a single repeated root. How many zero divisors appear? Is the damage worse than our example above?

Exercise 3

Pick a different irreducible degree-8 polynomial (not the AES one) and build the S-box using it. Is the nonlinearity the same as the AES S-box? (Hint: the nonlinearity comes from the inversion map, which has the same Walsh spectrum regardless of which irreducible polynomial you use. The affine step preserves nonlinearity.)

# Exercise space: try different polynomials here

# Exercise 1: x^8 + x^6 + x^4 + x^2
m_ex1 = x^8 + x^6 + x^4 + x^2
print(f'Exercise 1 polynomial: {m_ex1}')
print(f'  Irreducible? {m_ex1.is_irreducible()}')
print(f'  Factorization: {m_ex1.factor()}')
print()

# TODO: Build quotient ring, count non-invertible elements, build S-box

# Exercise 2: x^8 + 1 = (x+1)^8
m_ex2 = x^8 + 1
print(f'Exercise 2 polynomial: {m_ex2}')
print(f'  Irreducible? {m_ex2.is_irreducible()}')
print(f'  Factorization: {m_ex2.factor()}')
print()

# TODO: count zero divisors, compare damage

Summary

Property	Real AES S-box	Broken S-box (reducible poly)
Modulus polynomial	$x^8+x^4+x^3+x+1$ (irreducible)	$x^8+x^4$ (reducible)
Quotient ring	Field (GF(256))	Ring with zero divisors
Invertible nonzero elements	255 / 255	Much fewer
S-box is bijection?	Yes	No (many collisions)
Fixed points	0	Multiple
Nonlinearity	112 / 120	Significantly lower

Key takeaways:

• The AES S-box construction requires an irreducible modulus polynomial.

• A reducible polynomial creates zero divisors --- elements with no inverse.

• Patching those entries creates collisions, fixed points, and reduced nonlinearity.

• These weaknesses are directly exploitable by linear and differential cryptanalysis.

• The mathematical lesson: a quotient ring is only a field when the modulus is irreducible.

---

Back to Module 03: Galois Fields and AES