Polite Email

#!/usr/bin/env python3

"""

Solver for http101 (polite-email) challenge.

  

This script finds a suffix to append to the polite email such that all

CRC implementations used in the challenge produce the same MAC (we target 0).

  

It works by treating CRC as a linear function over GF(2) and solving a

system of linear equations for a chosen suffix length.

  

Usage: run from the challenge folder. Requires fastcrc installed in the venv.

"""

from fastcrc import crc32, crc64

from itertools import product

import os

  
  

def make_polite(sender: str):

    return f"Dear Challenge Author.\n\nPretty please give me the flag.\n\nBest regards,\n{sender}".encode()

  
  

def compute_crcs(data: bytes):

    vals = []

    for a in ['autosar', 'iscsi', 'iso_hdlc']:

        vals.append(getattr(crc32, a)(data))

    for a in ['go_iso', 'xz']:

        vals.append(getattr(crc64, a)(data))

    return vals

  
  

def int_to_bits(x: int, width: int):

    return [(x >> i) & 1 for i in range(width)]

  
  

def bits_to_int(bits):

    x = 0

    for i, b in enumerate(bits):

        if b:

            x |= (1 << i)

    return x

  
  

def build_matrix(prefix: bytes, L_bytes=32):

    """Build matrix M over GF(2) with 224 rows (3*32 + 2*64) and 8*L columns.

    Column j is the delta in CRC-vector when flipping bit j in the suffix

    (compared to a zero suffix of length L).

    """

    ncols = 8 * L_bytes

    # base crc with zero suffix

    zero_suffix = bytes([0]) * L_bytes

    base = compute_crcs(prefix + zero_suffix)

    base_bits = []

    for i, val in enumerate(base):

        width = 32 if i < 3 else 64

        base_bits.extend(int_to_bits(val, width))

  

    # prepare matrix as list of columns (each column is list of bits)

    cols = [None] * ncols

    for j in range(ncols):

        # build suffix with single bit j set

        bidx = j // 8

        bit_in_byte = j % 8

        s = bytearray(L_bytes)

        s[bidx] = 1 << bit_in_byte

        vals = compute_crcs(prefix + bytes(s))

        col_bits = []

        for i, val in enumerate(vals):

            width = 32 if i < 3 else 64

            col_bits.extend(int_to_bits(val, width))

        # column is delta = col_bits XOR base_bits

        delta = [ (cb ^ bb) for cb, bb in zip(col_bits, base_bits) ]

        cols[j] = delta

        if j % 32 == 0:

            print(f'Built column {j}/{ncols}')

  

    return cols, base_bits

  
  

def solve_gf2(cols, target):

    """Solve M x = target over GF(2). cols is list of column vectors (each list of bits).

    Returns solution bitlist x of length ncols or None.

    Uses Gaussian elimination on augmented matrix built from columns.

    """

    ncols = len(cols)

    nrows = len(cols[0])

    # Build matrix as list of rows for elimination

    # We'll construct row-major matrix A where A[r][c] = cols[c][r]

    A = [ [cols[c][r] for c in range(ncols)] + [target[r]] for r in range(nrows) ]

  

    row = 0

    pivots = [-1] * nrows

    for col in range(ncols):

        # find pivot

        sel = None

        for r in range(row, nrows):

            if A[r][col]:

                sel = r

                break

        if sel is None:

            continue

        # swap

        A[row], A[sel] = A[sel], A[row]

        pivots[row] = col

        # eliminate other rows

        for r in range(nrows):

            if r != row and A[r][col]:

                # XOR row

                for c in range(col, ncols+1):

                    A[r][c] ^= A[row][c]

        row += 1

        if row == nrows:

            break

  

    # Check consistency

    for r in range(row, nrows):

        if A[r][ncols]:

            return None

  

    # back substitution, set free vars to 0

    x = [0] * ncols

    for r in range(row-1, -1, -1):

        c = pivots[r]

        if c == -1:

            continue

        s = A[r][ncols]

        for cc in range(c+1, ncols):

            if A[r][cc] and x[cc]:

                s ^= 1

        x[c] = s

    return x

  
  

def main():

    sender = 'attacker'

    prefix = make_polite(sender)

    print('Prefix len', len(prefix))

    L = 32

    print('Building matrix with suffix length', L)

    cols, base = build_matrix(prefix, L_bytes=L)

    # target mac: choose 0 for all algorithms -> target bits = base_bits XOR desired (desired is 0)

    # We want final CRCs equal to 0, so target = base_bits (since base is CRC(prefix+zeros))

    target = base[:]  # we need to flip bits to reach zero

    print('Solving linear system...')

    sol = solve_gf2(cols, target)

    if sol is None:

        print('No solution found')

        return

    # build suffix bytes

    Lbits = 8 * L

    sbytes = bytearray(L)

    for j in range(Lbits):

        if sol[j]:

            sbytes[j//8] |= (1 << (j%8))

  

    final = prefix + bytes(sbytes)

    cr = compute_crcs(final)

    print('Final CRCs:', cr)

  

    # For local test, write final mail bytes to a file and print mail hex + mac

    outpath = '002_mail.bin'

    with open(outpath, 'wb') as f:

        f.write(final)

    print(f'Wrote final mail to {outpath} (len={len(final)})')

    print('Mail hex:')

    print(final.hex())

    print('MAC (use decimal): 0')

  
  

if __name__ == '__main__':

    main()