Reforgeability of Authenticated Encryption Schemes

This work pursues the idea of multi-forgery attacks as introduced by Ferguson in 2002. We recoin reforgeability for the complexity of obtaining further forgeries once a first forgery has succeeded. First, we introduce a security notion for the integrity (in terms of reforgeability) of authenticated encryption schemes: \(j\text {-}\textsc {Int}\text {-}\textsc {CTXT}\), which is derived from the notion INT-CTXT. Second, we define an attack scenario called \(j\text {-IV-Collision Attack}\) (\(j\text {-IV-CA}\)), wherein an adversary tries to construct j forgeries provided a first forgery. The term collision in the name stems from the fact that we assume the first forgery to be the result from an internal collision within the processing of the associated data and/or the nonce. Next, we analyze the resistance to \(j\text {-IV-CAs}\) of classical nonce-based AE schemes (CCM, CWC, EAX, GCM) as well as all 3rd-round candidates of the CAESAR competition. The analysis is done in the nonce-respecting and the nonce-ignoring setting. We find that none of the considered AE schemes provides full built-in resistance to \(j\text {-IV-CAs}\). Based on this insight, we briefly discuss two alternative design strategies to resist \(j\text {-IV-CAs}\).