Mobius Bridges for the Invert-and-Affine S-box Class, with the Four ARIA Instantiations

Sketchnote for paper v1.0.5 (CC BY 4.0). Full-size PNG.

Abstract

The Mobius Bridge of Nasr and Carlini removes one guessed key byte from meet-in-the-middle attacks on 7-round AES by constructing a fingerprint invariant under the group action that survives the S-box. Their derivation is written for the AES S-box (field inversion followed by a GF(2)-affine map). This note shows the construction is not specific to that shape. For any S-box of the form S = L2 ∘ Frobj ∘ inv ∘ L1, with L1 and L2 GF(2)-affine bijections and Frob the squaring map, the same reciprocal-and-reparametrize step yields an affine bridge identity in which both parameters are raised to the 2j power and the multiplier remains the square of the translation. The Frobenius exponent is the only degree of freedom. AES instantiates j = 0 with L1 = id. ARIA instantiates four distinct members (S1, S2, S1−1, S2−1 at exponents 0, 3, 0, 5), each with its own offline multiset. A consequence that does not appear in the AES case: bad indices where inv(0) = 0 breaks the identity move with L1, sitting at L1−1(0) rather than at 0; for ARIA's inverse S-boxes these are the affine constants, so the published bad-index treatment does not port unchanged. Bridge identities are verified exhaustively over GF(2^8). Theorem 3.1, Corollary 3.2, and the Section 5 bad-index set are formalized in Lean 4. No attack complexities for ARIA are claimed.

Keywords

ARIA · block cipher · meet-in-the-middle · Mobius Bridge · GF(2^8) · Frobenius · Lean 4 · S-box · cryptanalysis · formal verification · invert-and-affine · class bridge · fingerprint invariance

← All research