October 4, 2023
Yusuke Naito - Mitsubishi Electric Corporation
Committing security of authenticated encryption (AE) is an emerging area of research motivated by real-world attacks. In particular, constructing AEs satisfying CMT-4, a security notion considering an adversary who generates multiple inputs for encryption that result in the same ciphertext, is an ongoing research challenge. In this paper, we propose a new mode KIVR, which transforms existing AEs to have CMT-4 security without increasing the ciphertext size by exploiting plaintext redundancy found in practical use cases. KIVR uses a collision-resistant hash to convert a tuple of key, nonce, and associated data into a temporary key, an initial value (or nonce), and a masking value applied to redundant data used by an underlying AE. Unlike the conventional HtE and CTX conversions limited by the birthday bounds of the key and tag sizes, the security of KIVR linearly increases with the number of redundant bits \(r\) and can achieve the beyond-birthday-bound (BBB) security. Combined with GCM, KIVR’s security becomes \(r \over 2\) bits. In practical use cases with a sufficiently large \(r\), KIVR salvages GCM for BBB security while preserving the ciphertext size and respecting GCM’s interface. Furthermore, if we can use modified AEs, KIVR combined with CAU-SIV-C1 (a variant of GCM-SIV for committing security) achieves \(r \over 2\) + 64 bits, enabling higher security with fewer redundant bits.
The Third NIST Workshop on Block Cipher Modes of Operation
