International Association
for Cryptologic Research

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers \textsf{AES} as a primitive. Widely used VIL-STPRP modes, such as \textsf{HCTR2}, have birthday-bound security and provide only 64-bit security with \textsf{AES}. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use \textsf{Rijndael-256-256} with \textsf{HCTR2}. This paper pursues the first direction while maintaining compatibility with \textsf{HCTR2}. In particular, we provide two solutions to achieve BBB security for two different approaches: (i) general cases without any conditions on the tweak and (ii) under the condition that the same tweak is not repeated too often as adopted in \textit{bbb-ddd-AES} recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, \textsf{CHCTR}, that iterates \textsf{HCTR2} with two independent keys, which achieves $2n/3$-bit security in the multi-user (mu) setting and satisfies NIST's requirements. For the second approach, we prove mu security of \textsf{HCTR2}, which allows us to apply the tweak-based key derivation (\textsf{TwKD}) to \textsf{HCTR2} in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, \textsf{HCTR2-TwKD} achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that \textsf{CHCTR} with \textsf{AES-256} outperforms \textsf{HCTR2} with \textsf{Rijndael-256-256}, in all the twelve processor models examined. Similarly, \textsf{HCTR2-TwKD} outperforms \textit{bbb-ddd-AES} in general cases, and it is even comparable to \textit{bbb-ddd-AES} rigorously optimized for tweak-repeating use cases using precomputation.

For an Authenticated Encryption with Associated Data (AEAD) scheme, the key committing security refers to the security notion of whether the adversary can produce a pair of distinct input tuples, including the key, that result in the same output. While the key committing security of various nonce-based AEAD schemes is known, the security analysis of Robust AE (RAE) is largely unexplored. In particular, we are interested in the key committing security of AEAD schemes built on the Encode-then-Encipher (EtE) approach from a wide block cipher. We first consider AEZ v5, the classical and the first dedicated RAE that employs the EtE approach. We focus our analysis on the core part of AEZ to show our best attacks depending on the length of the ciphertext expansion. In the general case where the Tweakable Block Cipher (TBC) is assumed to be ideal, we show a birthday attack and a matching provable security result. AEZ adopts a simpler key schedule and the prove-then-prune approach in the full specification, and we show a practical attack against it by exploiting the simplicity of the key schedule. The complexity is 227, and we experimentally verify the correctness with a concrete example. We also cover two AEAD schemes based on EtE. One is built on Adiantum, and the other one is built on HCTR2, which are two wide block ciphers that are used in real applications. We present key committing attacks against these schemes when used in EtE and matching proofs for particular cases.

At EUROCRYPT ’93, Matsui introduced linear cryptanalysis. Both Matsui’s Algorithm 1 and 2 use a linear approximation involving certain state bits. Algorithm 2 requires partial encryptions or decryptions to obtain these state bits after guessing extra key bits. For ciphers where only part of the state can be obtained, like some stream ciphers and authenticated encryption schemes, Algorithm 2 will not work efficiently since it is hard to implement partial encryptions or decryptions. In this case, Algorithm 1 is a good choice since it only involves these state bits, and one bit of key information can be recovered using a single linear approximation trail. However, when there are several strong trails containing the same state bits, known as the linear hull effect, recovering key bits with Algorithm 1 is infeasible. To overcome this, Röck and Nyberg extended Matsui’s Algorithm 1 to linear hulls. However, Röck and Nyberg found that their theoretical estimates are quite pessimistic for low success probabilities and too optimistic for high success probabilities. To deal with this, we construct new statistical models where the theoretical success probabilities are in a good accordance with experimental ones, so that we provide the first accurate analysis of the extension of Matsui’s Algorithm 1 to linear hulls. To illustrate the usefulness of our new models, we apply them to one of the ten finalists of the NIST Lightweight Cryptography (LWC) Standardization project: TinyJAMBU. We provide the first cryptanalysis under the nonce-respecting setting on the full TinyJAMBU v1 and the round-reduced TinyJAMBU v2, where partial key bits are recovered. Our results do not violate the security claims made by the designers.

At FSE 2004, Lipmaa et al. studied the additive differential probability adp⊕(α,β → γ) of exclusive-or where differences α,β,γ ∈ Fn2 are expressed using addition modulo 2n. This probability is used in the analysis of symmetric-key primitives that combine XOR and modular addition, such as the increasingly popular Addition-Rotation-XOR (ARX) constructions. The focus of this paper is on maximal differentials, which are helpful when constructing differential trails. We provide the missing proof for Theorem 3 of the FSE 2004 paper, which states that maxα,βadp⊕(α,β → γ) = adp⊕(0,γ → γ) for all γ. Furthermore, we prove that there always exist either two or eight distinct pairs α,β such that adp⊕( α,β → γ) = adp⊕(0,γ → γ), and we obtain recurrence formulas for calculating adp⊕. To gain insight into the range of possible differential probabilities, we also study other properties such as the minimum value of adp⊕(0,γ → γ), and we find all γ that satisfy this minimum value.