SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition

Ashutosh Dhar Dwivedi; Miloš Klouček; Pawel Morawiecki; Ivica Nikolic̈; Josef Pieprzyk; Sebastian Wöjtowicz

Paper 2016/1053

SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition

Ashutosh Dhar Dwivedi, Miloš Klouček, Pawel Morawiecki, Ivica Nikolic̈, Josef Pieprzyk, and Sebastian Wöjtowicz

Abstract

We investigate six authenticated encryption schemes (ACORN, ASCON-128a, Ketje Jr, ICEPOLE-128a, MORUS, and NORX-32) from the CAESAR competition. We aim at state recovery attacks using a SAT solver as a main tool. Our analysis reveals that these schemes, as submitted to CAESAR, provide strong resistance against SAT-based state recoveries. To shed a light on their security margins, we also analyse modified versions of these algorithms, including round-reduced variants and versions with higher security claims. Our attacks on such variants require only a few known plaintext-ciphertext pairs and small memory requirements (to run the SAT solver), whereas time complexity varies from very practical (few seconds on a desktop PC) to `theoretical' attacks.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: SAT solvers SAT-based cryptanalysis logic cryptanalysis authenticated encryption CAESAR
Contact author(s): pawel morawiecki @ gmail com
History: 2016-11-15: received
Short URL: https://ia.cr/2016/1053
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1053,
      author = {Ashutosh Dhar Dwivedi and Miloš Klouček and Pawel Morawiecki and Ivica Nikolic̈ and Josef Pieprzyk and Sebastian Wöjtowicz},
      title = {SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1053},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1053}},
      url = {https://eprint.iacr.org/2016/1053}
}