Paper 2026/1461

The m=n+1 Boundary of EME: A Splicing Distinguisher for the Unrefreshed EME-Core Extension and Its Linear-Map Generalization

Abstract

EME is a parallelizable encrypt-mix-encrypt wide-block construction proved secure for m-block messages only in the range m <= n, where n is the block length of the underlying block cipher. Halevi and Rogaway justified this restriction by giving a splicing distinguisher for m >= n + 2, but left open the first excluded length, m = n + 1. We resolve that boundary for the direct, unrefreshed EME-core extension beyond its specified m <= n domain: the original formulas are applied to m = n + 1 blocks while continuing to use the same global mask. Under one fixed tweak, two encryption queries and one decryption query distinguish this extension from a random permutation. The result applies to this unrefreshed extension; refreshed variants such as EME* and IEEE EME2-AES are outside the scope of the distinguisher. The boundary attack is not a shortened form of the known zero-sum attack. At m = n + 1, the non-first coefficients have no nonempty zero-sum; instead, they form a basis and therefore uniquely represent the coefficient 1. Combining this representation with the special equation for the first mixed block gives the cancellation needed for a ciphertext splice. The same mechanism applies to Sarkar's EMME framework: when multiplication by the field element x is replaced by a linear operator psi with degree-n minimal polynomial, the minimal-polynomial relation supplies the corresponding operator identity. EME* and IEEE EME2-AES avoid this setting by refreshing the mask at chunk boundaries. The attack identifies the algebraic obstruction that such refresh steps avoid.