International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of NORX v2.0

Authors:
Colin Chaigneau , UVSQ, Versailles
Thomas Fuhr , ANSSI Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP
Henri Gilbert , ANSSI Crypto Lab, Paris
Jérémy Jean , ANSSI Crypto Lab, Paris
Jean-René Reinhard , ANSSI Crypto Lab 51, boulevard de La Tour-Maubourg 75700 Paris 07 SP
Download:
DOI: 10.13154/tosc.v2017.i1.156-174
URL: http://tosc.iacr.org/index.php/ToSC/article/view/589
Search ePrint
Search Google
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.
BibTeX
@article{tosc-2017-28101,
  title={Cryptanalysis of NORX v2.0},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2017, Issue 1},
  pages={156-174},
  url={http://tosc.iacr.org/index.php/ToSC/article/view/589},
  doi={10.13154/tosc.v2017.i1.156-174},
  author={Colin Chaigneau and Thomas Fuhr and Henri Gilbert and Jérémy Jean and Jean-René Reinhard},
  year=2017
}