Cryptanalysis of NORX v2.0

Authors

  • Colin Chaigneau University of Versailles Saint-Quentin-en-Yvelines (UVSQ) , Versailles, France
  • Thomas Fuhr Agence nationale de la sécurité des systèmes d'information (ANSSI) Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP, France
  • Henri Gilbert Agence nationale de la sécurité des systèmes d'information (ANSSI) Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP, France;University of Versailles Saint-Quentin-en-Yvelines (UVSQ) , Versailles, France
  • Jérémy Jean Agence nationale de la sécurité des systèmes d'information (ANSSI) Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP, France
  • Jean-René Reinhard Agence nationale de la sécurité des systèmes d'information (ANSSI) Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP, France

DOI:

https://doi.org/10.13154/tosc.v2017.i1.156-174

Keywords:

CAESAR Competition, NORX, Cryptanalysis, Forgery Attack, Symmetry

Abstract

NORX is an authenticated encryption scheme with associated data being publicly scrutinized as part of the ongoing CAESAR competition, where 14 other primitives are also competing. It is based on the sponge construction and relies on a simple permutation that allows efficient and versatile implementations. Thanks to research on the security of the sponge construction, the design of NORX, whose permutation is inspired from the permutations used in BLAKE and ChaCha, has evolved throughout three main versions (v1.0, v2.0 and v3.0). In this paper, we investigate the security of the full NORX v2.0 primitive that has been accepted as third-round candidate in the CAESAR competition. We show that some non-conservative design decisions probably motivated by implementation efficiency considerations result in at least one strong structural distinguisher of the underlying sponge permutation that can be turned into an attack on the full primitive. This attack yields a ciphertext-only forgery with time and data complexity 266 (resp. 2130) for the variant of NORX v2.0 using 128-bit (resp. 256-bit) keys and breaks the designers’ claim of a 128-bit, resp. 256-bit security. Furthermore, we show that this forgery attack can be extended to a key-recovery attack on the full NORX v2.0 with the same time and data complexities. We have implemented and experimentally verified the correctness of the attacks on a toy version of NORX. We emphasize that the scheme has recently been tweaked to NORX v3.0 at the beginning of the third round of the CAESAR competition: the main change introduces some key-dependent internal operations, which make NORX v3.0 immune to our attacks. However, the structural distinguisher of the permutation persists.

Downloads

Published

2017-03-08

Issue

Section

Articles

How to Cite

Cryptanalysis of NORX v2.0. (2017). IACR Transactions on Symmetric Cryptology, 2017(1), 156-174. https://doi.org/10.13154/tosc.v2017.i1.156-174