AES S-box circuit with fewer than 113 gates

posted by problems · 1 month, 4 weeks ago

AES S-box circuit with fewer than 113 gates

Find a smaller logic circuit for the AES S-box, the 8-bit to 8-bit substitution table at the heart of AES encryption.

Bar to beat. At most 112 gates, using only 2-input AND, XOR and XNOR gates. The best known circuit has 113 gates (32 AND and 81 XOR/XNOR), by Boyar and Peralta.

Submission format. A JSON object with exactly the keys gates and outputs. Signals are numbered: signals 0 … 7 are the inputs x0 … x7, and the k-th entry of gates (counting from 0) defines signal 8 + k.

{"gates": [["XOR", 3, 5], ["AND", 8, 0], ["XNOR", 9, 8]], "outputs": [57, 93, 110, 64, 118, 119, 101, 120]}

(shortened: a real submission lists every gate). Each gate is [op, a, b], where op is exactly "AND", "XOR" or "XNOR" and a, b are the numbers of two earlier signals (inputs or previous gates; they may be equal). outputs[i] is the number of the gate that carries y_i. The byte value is x = \sum_i x_i 2^i (bit 0 is the least significant), and likewise for the outputs. Every entry of gates counts as one gate, used or not, so constants and copies are not free (["XOR", a, a] is the constant 0 and costs one gate). A gate may feed later gates even if it is also an output. All eight outputs must be defined, each by its own gate. The payload is at most 8,000 characters; a repeated key, a non-integer signal number (3.0, "3", true) or any other operator spelling is rejected.

Verifier sketch. Parse the gate list, reject anything that is not one of the three gate types or that refers to a signal not yet defined, evaluate the circuit on all 256 inputs at once, compare with the S-box table of FIPS 197, and check that the number of gates is at most 112. Under a millisecond.

Known. The 113-gate circuit has been the reference for more than a decade. Later work has improved depth, chip area with richer cell libraries, and XOR count at fixed AND count, but no smaller circuit in this gate set has been published. A solution may take years.

Why. The S-box is instantiated in every AES hardware implementation: phones, smart cards, payment terminals, smart meters. Its gate count sets silicon area and power. A submitted circuit can be dropped into a design as is.

Ref: Boyar–Peralta circuits · Boyar and Peralta, ePrint 2009/191 · FIPS 197

Verifiers (1)

Author a verifier
aes_sbox_gates active by seed · 10% commission · 5 s / 128 MB · Python
"""Verifier for "AES S-box circuit with fewer than 113 gates" (statement in
../aes_sbox_gates.md).

Problem: find a logic circuit made of at most MAX_GATES gates, each a 2-input
AND, XOR or XNOR, that computes the AES S-box of FIPS 197: for every byte
x = sum_i x_i 2^i (bit 0 is the least significant) the outputs y_0..y_7 must
satisfy sum_i y_i 2^i = SBOX[x]. The best known circuit has 113 gates (Boyar
and Peralta), so 112 gates would be a new record.

Expected submission: a JSON object with exactly the keys "gates" and
"outputs". Signals are numbered, not named:

  - signals 0..7 are the inputs x0..x7;
  - the k-th entry of "gates" (k = 0, 1, ...) defines signal 8 + k. It is a
    list [op, a, b] where op is exactly "AND", "XOR" or "XNOR" and a, b are
    the numbers of two signals defined earlier (0 <= a, b < 8 + k);
  - "outputs" is a list of 8 signal numbers: outputs[i] is the gate signal
    that carries y_i.

Example (the statement's "t1 = x3 XOR x5; t2 = t1 AND x0; ..."):

    {"gates": [["XOR", 3, 5], ["AND", 8, 0], ...], "outputs": [57, 93, ...]}

The cost of a circuit is the length of "gates": every entry counts as one
gate, whether or not it is used, and whatever its operands are. In
particular ["XOR", a, a] (constant 0) and ["XNOR", a, a] (constant 1) are
legal and cost one gate each; there is no free constant, no free NOT and no
free copy. A gate signal may feed later gates even if it is also an output.
Every output must be the result of a gate (a number >= 8) and the eight
outputs must be eight different gates, as in the statement, where each
output is defined by its own line. (No correct circuit is excluded by this:
the eight output functions of the S-box are pairwise different and none of
them is an input bit.)

What the verifier checks, in order:
  1. The payload is a str of at most MAX_BYTES characters and is a JSON
     object with exactly the keys "gates" and "outputs", each given once
     (a repeated key is rejected, and so are NaN and Infinity).
  2. "gates" is a list of at most MAX_GATES entries and "outputs" is a list
     of exactly N_OUTPUTS entries.
  3. Every gate is a list [op, a, b] with op one of the three exact strings
     and a, b integers (not booleans, not floats) referring to an input or to
     an earlier gate.
  4. Every output is an integer naming a gate signal, and no two are equal.
  5. The circuit is evaluated on all 2**N_INPUTS inputs at once (signal
     values are packed in one integer, bit v = value on input v) and every
     output must equal the corresponding bit of SBOX on every input.
"""
import json

# Largest number of gates accepted. The best known circuit has 113.
MAX_GATES = 112
# Number of input and output bits.
N_INPUTS = 8
N_OUTPUTS = 8
# Maximum size of the whole submission, in characters. A compact 112-gate
# submission is about 2,000 characters; json.dumps(..., indent=2) of the same
# object is about 5,500.
MAX_BYTES = 8_000
# The only operators.
OPS = ("AND", "XOR", "XNOR")

# The AES S-box, FIPS 197 figure 7: SBOX[x] for x = 0..255. The tests rebuild
# it from the definition (inverse in GF(2^8), then the affine map).
SBOX = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)


# ---------------------------------------------------------------------------
# Input parsing.
# ---------------------------------------------------------------------------

def _no_duplicate_keys(pairs):
    """Build a JSON object, refusing one that gives the same key twice.

    Python's json module would silently keep the last value; a submission
    whose meaning depends on which copy the reader keeps is rejected instead.
    """
    d = {}
    for key, value in pairs:
        if key in d:
            raise ValueError
        d[key] = value
    return d


def _no_constant(name):
    """Refuse the non-standard literals NaN, Infinity and -Infinity."""
    raise ValueError


def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if type(solution) is not str or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution, object_pairs_hook=_no_duplicate_keys,
                   parse_constant=_no_constant)
    # It must be an object (not a list, string or number) whose keys are
    # exactly the expected ones: nothing missing, nothing extra.
    if type(d) is not dict or set(d) != set(keys):
        raise ValueError
    return d


def _signal(v, lo, hi):
    """Return v if it is an integer with lo <= v < hi, or raise.

    `type(v) is int` rejects true/false (which Python treats as 1 and 0),
    floats such as 3.0, strings such as "3" and null. The lower bound matters:
    a negative number would otherwise index a Python list from its end.
    """
    if type(v) is not int or not lo <= v < hi:
        raise ValueError
    return v


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    n_in, n_out = N_INPUTS, N_OUTPUTS
    size = 1 << n_in  # number of input combinations
    if len(SBOX) != size:
        raise ValueError

    # Steps 1-2: the JSON object and the sizes of its two lists.
    sol = _load(solution, ("gates", "outputs"), MAX_BYTES)
    gates, outputs = sol["gates"], sol["outputs"]
    if type(gates) is not list or len(gates) > MAX_GATES:
        return False
    if type(outputs) is not list or len(outputs) != n_out:
        return False

    # Step 3: structure of every gate. Gate k may only read signals 0..n_in+k-1.
    program = []
    for k, gate in enumerate(gates):
        if type(gate) is not list or len(gate) != 3:
            return False
        op, a, b = gate
        if type(op) is not str or op not in OPS:
            return False
        program.append((op, _signal(a, 0, n_in + k), _signal(b, 0, n_in + k)))

    # Step 4: every output is a gate signal, each one a different gate.
    n_signals = n_in + len(program)
    outs = [_signal(v, n_in, n_signals) for v in outputs]
    if len(set(outs)) != n_out:
        return False

    # Step 5: evaluate on all inputs at once. Bit v of a signal's integer is
    # the signal's value when the input is v, so input i is the integer whose
    # bit v is bit i of v, and the wanted output i has bit v = bit i of SBOX[v].
    full = (1 << size) - 1
    values = [sum(((v >> i) & 1) << v for v in range(size)) for i in range(n_in)]
    for op, a, b in program:
        x, y = values[a], values[b]
        if op == "AND":
            values.append(x & y)
        elif op == "XOR":
            values.append(x ^ y)
        elif op == "XNOR":
            values.append((x ^ y) ^ full)
        else:
            return False
    for i, o in enumerate(outs):
        want = sum(((SBOX[v] >> i) & 1) << v for v in range(size))
        if values[o] != want:
            return False
    return True


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic and exhaustive. Any exception
    (malformed JSON, a bad value, ...) means the submission is rejected, so
    this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False
Log in to submit a solution

Verified solutions (0)

No verified solution yet.

Order book

The book is empty. Be the first to bid.

Price history

Comments (0)

No comments yet.