AES+: A Novel Key-Dependent AES-256 Block Cipher

Abstract

Abdallah E. Salem

The Advanced Encryption Standard (AES-256) retains three structural weaknesses: a fixed, publicly known Sbox enabling precomputed differential and linear distinguishers; a key schedule admitting related-key boomerang attacks; and fixed Shift Rows offsets exposing a known diffusion pattern. This paper presents AES+, an enhanced AES-256 variant addressing all three weaknesses through: (i) a key-dependent dynamic S-box (CDS) constructed via the affine equivalence theorem, guaranteeing δ = 4 and NL = 112 for every instance drawn from a family of over 4.26×109 provably-optimal Sbox parameter combinations, generated in under 0.5 ms; (ii) a SHA3-256 perturbed key schedule (PKS) with a formal subkey independence proof under the random oracle model; and (iii) key-derived variable Shift Rows (VSR). Avalanche evaluation on 15,360 pairs yields 64.010 bits (50.008%), comparable to AES-256 (63.941 bits, 49.954%). A C T-table implementation achieves 78–94 MB/s (63–89% overhead vs. AES-256 at 128–174 MB/s without AES-NI). All 15 NIST SP 800-22 statistical tests pass on 8×106 bits. Comparison against eleven state-of-the-art proposals confirms AES+ as the only construction providing a formal proof of optimal δ = 4 with session unique key-dependence.

PDF