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 ∘ Frob^j ∘ 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 2^j 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⁻¹, S2⁻¹ 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⁻¹(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⁸). 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