# AES512 v3 — cipher specification and design rationale

This document specifies the block cipher implemented in `aes512/cipher.go`
precisely enough to build an independent implementation, and lays out the
security reasoning honestly: what is proven, what is bounded, what is merely
conjectured.

## 1. Naming and lineage

"AES512" is an informal name. FIPS 197 defines AES only for 128-bit blocks;
Rijndael, its parent, was specified for blocks up to 256 bits. This cipher
extends the same *design strategy* — the wide-trail construction of Daemen
and Rijmen — to an 8×8-byte state (512-bit block, 512-bit key). It is best
understood as a member of the family that includes:

- **Whirlpool's W** — an 8×8-byte, 10-round, 512-bit cipher used inside the
  Whirlpool hash (different S-box, different field, different key schedule);
- **Grøstl's P/Q permutations** (SHA-3 finalist) — 8×8-byte AES-like rounds,
  whose **MixBytes matrix this cipher adopts** (§2.5);
- **Kalyna** (Ukrainian standard DSTU 7624:2014) — the one *standardized*
  cipher with a 512/512 variant (18 rounds, different components).

No standard exists for this exact construction; known-answer vectors are
self-generated (§6).

## 2. Specification

### 2.1 Parameters

| Symbol | Value | Meaning |
|---|---|---|
| block | 64 bytes (512 bits) | 8×8-byte state |
| key | 64 bytes (512 bits) | expanded to 152 round-key words (19 round keys) |
| Nr | **18** rounds | v1 used 10, v2 used 14; see §4.3 |
| field | GF(2⁸) mod x⁸+x⁴+x³+x+1 (0x11b) | the AES field |

### 2.2 State mapping

Input byte `k` (0…63) maps to state row `k mod 8`, column `⌊k/8⌋`:
`s[i][j] = in[8j + i]` (column-major, the AES convention extended to 8 rows).
Output is the same mapping inverted.

### 2.3 SubBytes

The AES S-box: `S(x) = A(inv(x)) ⊕ 0x63`, where `inv` is multiplicative
inversion in the field (with inv(0)=0) and `A` is the AES affine map
`y = x ⊕ (x⋘1) ⊕ (x⋘2) ⊕ (x⋘3) ⊕ (x⋘4)`. Properties relied on: maximum
differential probability 2⁻⁶, maximum linear correlation 2⁻³.

**v3 computes this with no table.** `inv` is evaluated as `x²⁵⁴` in GF(2⁸)
via a fixed 11-multiply addition chain (7 squarings + 4 multiplies); the
affine map is bit rotations and XORs. Every step is branchless and touches
no memory at a secret-dependent address, so SubBytes — and therefore the
whole cipher — is **constant-time at the source level**, closing the
cache-timing channel that is the most practical attack on table-based AES
(see §4.4 for the exact scope of that guarantee). The
classical S-box table survives only in `sbox_test.go` as an oracle:
`TestConstantTimeSBoxMatchesTable` asserts the algebraic implementation
reproduces it on all 256 inputs, and a grep gate confirms no table lookup in
shipping code.

### 2.4 ShiftRows

Row `r` rotates **left by r** (offsets 0,1,2,…,7). All offsets are distinct
mod 8, so the 8 bytes of any column disperse into 8 distinct columns. This is
the *diffusion-optimal* property required by the four-round propagation
theorem (§4.1); it is asserted in `TestShiftRowsInverse`.

### 2.5 MixColumns

Each column is multiplied by the circulant matrix

```
M[i][j] = m[(j − i) mod 8],   m = (02, 02, 03, 04, 05, 03, 05, 07)
```

i.e. `out[i] = Σ_d m[d] · col[(i+d) mod 8]` over GF(2⁸)/0x11b. This is the
**MixBytes matrix of Grøstl**, chosen because it is **MDS over exactly this
field** — differential branch number 9, the optimum for an 8-byte column —
and because its entries reduce to cheap xtime chains
(3=2⊕1, 5=4⊕1, 7=4⊕2⊕1).

**The MDS property is not taken on faith:** `TestMixColumnsMatrixIsMDS`
verifies, on every test run, that all Σₖ C(8,k)² = 12 869 square submatrices
are nonsingular (the exact characterization of MDS). The inverse matrix is
computed at package init by Gauss–Jordan elimination over the field and the
product M·M⁻¹ = I is asserted before any use.

**Why v1 was replaced.** v1 used circulant entries (01,01,01,01,01,03,01,02).
Six equal entries guarantee singular 2×2 submatrices — pick rows i≠j and two
columns where all four entries are 01: the determinant is 01·01 ⊕ 01·01 = 0.
Hence not MDS, hence a branch number far below 9, hence no wide-trail bound.
`TestV1MatrixWasNotMDS` reproduces the failure mechanically.

### 2.6 Key schedule (SHAKE-256)

**v3 derives all round keys by hashing the master key:**

```
raw   = SHAKE-256("AES512-v3-key-schedule" ‖ key)   read 152×8 = 1216 bytes
w[i]  = raw[8i : 8i+8]                                i = 0 … 151
```

The 152 words form 19 round keys (Nr+1). Round keys are therefore
**independent and pseudorandom** — there is no RotWord/Rcon algebra and no
relation between them for an attacker to exploit. This deliberately removes
the AES-256 key-schedule structure that enabled the Biryukov–Khovratovich
related-key attacks on full AES-256 (v1/v2 inherited that structure). It also
places the cipher squarely in the **key-alternating cipher with independent
round keys** model, which has the cleanest provable-security bounds
(Even–Mansour / KAC theory). The schedule runs once per key (~3.5 µs), so its
cost is irrelevant. Because there is no key structure, there are also no weak
keys: every 64-byte key is equally good.

v1/v2 used an AES-256-style schedule (RotWord + SubWord + Rcon every Nk words,
extra SubWord at the half-way word); it is retained here only as history.

### 2.7 Round function

```
Encrypt:  AddRoundKey(0)
          for r = 1..17:  SubBytes; ShiftRows; MixColumns; AddRoundKey(r)
          SubBytes; ShiftRows; AddRoundKey(18)
Decrypt:  the exact inverse sequence (equivalent-inverse-cipher reordering
          is not used; decryption applies InvMixColumns explicitly).
```

## 3. The AEADs

Two authenticated modes; both are the recommended interface (raw block access
is for interoperability only). Both are **key-committing**: the tag is an HMAC
over the ciphertext under a MAC key derived from the AEAD key, so a ciphertext
cannot be made to open under two different keys (defeats partitioning-oracle /
multi-key attacks — unlike AES-GCM). Tested in `TestAEADCrossKey`,
`TestSIVCrossKey`.

### 3.1 Streaming AEAD — `NewAEAD`

Encrypt-then-MAC (Bellare–Namprempre 2000):

```
kEnc = HKDF-SHA-512(key, salt="AES512.AEAD.v2", info="enc", L=64)
kMac = HKDF-SHA-512(key, salt="AES512.AEAD.v2", info="mac", L=64)

C   = CTR(kEnc, IV = nonce(32) ‖ 0³², P)      // 64-byte IV: nonce, then 32 zero
                                              // bytes; stdlib CTR over 64-byte blocks
tag = HMAC-SHA-512(kMac, "AES512.EtM.v2\0" ‖ nonce ‖
                   len64(AD) ‖ AD ‖ len64(C) ‖ C)[0:32]
Seal = C ‖ tag
```

- Nonce 32 bytes; **never reuse under one key** (random or counter both fine).
- 64-bit length prefixes make the MAC input injective (no AD/C boundary games).
- Tag comparison is constant-time; decryption happens only after verification.
- The CTR counter occupies the low 256 bits of the block — it cannot carry
  into the nonce for any realistic message length.

### 3.2 Misuse-resistant SIV — `NewSIV`

The SIV construction (Rogaway–Shrimpton; RFC 5297 in spirit) for code where
nonce discipline is hard. The IV is *synthesized* from the message, so a
repeated nonce leaks only whether two full (nonce, AD, plaintext) triples are
identical — never the keystream:

```
kEnc = HKDF-SHA-512(key, salt="AES512.SIV.v1", info="enc", L=64)
kMac = HKDF-SHA-512(key, salt="AES512.SIV.v1", info="mac", L=64)

V   = HMAC-SHA-512(kMac, "AES512.SIV.v1\0" ‖ len64(nonce)‖nonce
                        ‖ len64(AD)‖AD ‖ len64(P)‖P)[0:32]
Seal = V ‖ CTR(kEnc, IV = V ‖ 0³², P)         // 64-byte IV: V, then 32 zero bytes
```

Note the HKDF salt differs from the streaming AEAD's (`AES512.SIV.v1` vs
`AES512.AEAD.v2`), so the two modes derive unrelated subkeys even when handed
the same input key. The nonce is optional (empty ⇒ a deterministic AEAD).
`TestSIVNonceReuseResistance` proves distinct plaintexts under a reused nonce
do not reuse keystream.

## 4. Security rationale — and its limits

### 4.0 Stated claims and non-claims

To make the target falsifiable:

1. **Single-key claim.** For the full 18-round cipher under a uniformly random
   64-byte key we claim no distinguishing or key-recovery attack materially
   better than generic search (2⁵¹² classically, ≈2²⁵⁶ under Grover). Reduced-
   round results do not falsify this claim but are exactly the analysis the
   design needs — see SECURITY-ANALYSIS.md §7.
2. **Related-key claim.** Round keys are a SHAKE-256 image of the master key
   (§2.6), so we claim related-key attacks require exploitable structure in
   SHAKE-256 itself. No claim is made in *chosen-round-key* models — such round
   keys are not reachable through the schedule.
3. **Non-claims.** No claim in known-key or chosen-key (hash/permutation-mode)
   settings — this cipher is not offered as a compression-function core. No
   claim against physical side channels (power/EM; §4.4). No claim of
   *assurance*: the design has had no third-party cryptanalysis, which is the
   deciding argument against production use regardless of the margins below.

### 4.1 Wide-trail bounds (single-key differential / linear)

With a diffusion-optimal byte permutation (§2.4) and an MDS mixing layer of
branch number B = 9 (§2.5), the four-round propagation theorem of Daemen &
Rijmen gives: **any 4-round differential or linear trail activates ≥ B² = 81
S-boxes.**

Consequences with the AES S-box bounds:

| Rounds | Active S-boxes ≥ | Max trail DP ≤ | Max trail correlation ≤ |
|---|---|---|---|
| 4 | 81 | 2⁻⁴⁸⁶ | 2⁻²⁴³ |
| 8 | 162 | 2⁻⁹⁷² | 2⁻⁴⁸⁶ |
| 12 | 243 | 2⁻¹⁴⁵⁸ | 2⁻⁷²⁹ |

At 18 rounds the cipher contains four disjoint 4-round windows plus two extra
rounds; a single 8-round trail already has probability far below the 2⁻⁵¹²
random-permutation floor for a 512-bit block.

**Limits of this argument, stated plainly:** these bound *individual trails*,
not differentials (sums of trails) or linear hulls; they say nothing about
integral, impossible-differential, boomerang, or algebraic attacks. Wide-trail
bounds are a necessary foundation, not a security proof. This is exactly the
kind of construction that deserves — and has not had — dedicated cryptanalysis.
The systematic vector-by-vector treatment is in
[SECURITY-ANALYSIS.md](SECURITY-ANALYSIS.md).

### 4.2 Key schedule: related-key resistance (v3)

v1/v2 used an AES-256-like schedule and inherited its known weakness — slow,
mostly linear diffusion, which enabled the related-key boomerang attacks on
full AES-256 (Biryukov–Khovratovich 2009). **v3 removes this entirely** by
deriving round keys from SHAKE-256 (§2.6): round keys are independent and
pseudorandom, so there is no key relation to propagate. Related-key attacks
would require SHAKE relations, which is infeasible. This is the single most
important cipher-level hardening in v3.

### 4.3 Round count

10 (v1) was adopted from Whirlpool's W, a *hash* primitive with no secret key
and a different schedule. Data points: AES-256 uses 14 rounds on a
4-round-bound of 25 active S-boxes; Kalyna-512/512 uses 18. A larger state
needs *more* rounds for full diffusion (2 rounds here), not fewer. **v3 uses
18** (≈4.5 diffusion cycles), matching Kalyna's 512/512 variant and exceeding
AES-256's structural margin, at ~30% more work than v2's 14.

### 4.4 Implementation side channels (v3: constant-time)

- **No secret-indexed memory.** The S-box is algebraic (§2.3), so there is no
  table lookup anywhere in the cipher. `gfMult`/`xtime`/`gfInv` are branchless
  and the only array indices are public loop counters. Control flow and the
  memory-access pattern are independent of key and plaintext, which closes
  the cache-timing channel — the most practical break of table-based AES.
- This is a *software* constant-time guarantee (best effort against compiler
  transformations); it does **not** defend against physical power/EM analysis,
  which needs masking and is out of scope.
- Block `Decrypt` uses the dense inverse matrix via generic field
  multiplication; it is slower than Encrypt and unused by the AEAD/SIV
  (CTR decrypts with the *encryption* direction).

## 5. Performance

Apple M2 Pro, Go 1.24, single core: Encrypt ≈ 155 µs/block (0.4 MB/s); AEAD
Seal ≈ 0.4 MB/s; SHAKE key schedule ≈ 3.5 µs. The constant-time algebraic
S-box is ~30× slower than a table — the deliberate price of removing the
cache-timing channel (§4.4). Ample for messaging (a 1 KB message is a few ms);
not a bulk-data cipher. A **bitsliced** constant-time core (same guarantee,
much faster) is the natural performance follow-up — see SECURITY-ANALYSIS §6.

## 6. Known-answer vectors

No external standard exists, so vectors are generated by this implementation
(`go run ./cmd/genkat`) and pinned in `kat_test.go` / `mct_test.go` /
`aead_test.go`: six block KATs (structured and hash-derived inputs), a
1000-iteration Monte-Carlo chain, and one full AEAD vector. **Regenerate and
re-pin after any intentional change to the construction** (the v3 vectors
differ from v2's because the schedule and round count changed); treat any
unplanned change as a regression. Independent implementations matching these
vectors match this specification.

## 7. References

- J. Daemen, V. Rijmen — *The Design of Rijndael*, 2nd ed. (wide-trail
  strategy, four-round propagation theorem).
- FIPS 197 — *Advanced Encryption Standard*.
- P. Gauravaram et al. — *Grøstl, a SHA-3 candidate* (MixBytes MDS matrix).
- P. Barreto, V. Rijmen — *The Whirlpool hashing function* (the W cipher).
- DSTU 7624:2014 — *Kalyna* block cipher (512-bit-block precedent).
- M. Bellare, C. Namprempre — *Authenticated Encryption: Relations among
  notions…* (encrypt-then-MAC).
- FIPS 202 — SHA-3 / SHAKE (key schedule). RFC 5869 — HKDF. FIPS 203 — ML-KEM.
  RFC 7748 — X25519. RFC 8032 — Ed25519.
- P. Rogaway, T. Shrimpton — *A Provable-Security Treatment of the Key-Wrap
  Problem* (SIV / misuse resistance); RFC 5297.
- A. Biryukov, D. Khovratovich — *Related-key cryptanalysis of the full
  AES-192 and AES-256* (the weakness v3's SHAKE schedule removes).
- S. Chen, J. Steinberger — *Tight security bounds for key-alternating
  ciphers* (the independent-round-key model the SHAKE schedule targets).
- D. J. Bernstein — *Cache-timing attacks on AES* (2005); D. A. Osvik,
  A. Shamir, E. Tromer — *Cache attacks and countermeasures: the case of AES*
  (the channel the table-free S-box closes).