International Association for Cryptologic Research

International Association
for Cryptologic Research


Categorization of Faulty Nonce Misuse Resistant Message Authentication

Yu Long Chen , KU Leuven, COSIC-ESAT
Bart Mennink , Radboud University, Digital Security Group
Bart Preneel , KU Leuven, COSIC-ESAT
DOI: 10.1007/978-3-030-92078-4_18
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: A growing number of lightweight block ciphers are proposed for environments such as the Internet of Things. An important contribution to the reduced implementation cost is a block length n of 64 or 96 bits rather than 128 bits. As a consequence, encryption modes and message authentication code (MAC) algorithms require security beyond the 2^{n/2} birthday bound. This paper provides an extensive treatment of MAC algorithms that offer beyond birthday bound PRF security for both nonce-respecting and nonce-misusing adversaries. We study constructions that use two block cipher calls, one universal hash function call and an arbitrary number of XOR operations. We start with the separate problem of generically identifying all possible secure n-to-n-bit pseudorandom functions (PRFs) based on two block cipher calls. The analysis shows that the existing constructions EDM, SoP, and EDMD are the only constructions of this kind that achieve beyond birthday bound security. Subsequently we deliver an exhaustive treatment of MAC algorithms, where the outcome of a universal hash function evaluation on the message may be entered at any point in the computation of the PRF. We conclude that there are a total amount of nine schemes that achieve beyond birthday bound security, and a tenth construction that cannot be proven using currently known proof techniques. For these former nine MAC algorithms, three constructions achieve optimal n-bit security in the nonce-respecting setting, but are completely insecure if the nonce is reused. The remaining six constructions have 3n/4-bit security in the nonce-respecting setting, and only four out of these six constructions still achieve beyond the birthday bound security in the case of nonce misuse.
Video from ASIACRYPT 2021
  title={Categorization of Faulty Nonce Misuse Resistant Message Authentication},
  author={Yu Long Chen and Bart Mennink and Bart Preneel},