Distinguishers and Attacks Against Shadow/Spook
Table of Contents
Work in progress
1 Spook and Shadow
Spook is a second round candidate of the NIST Lightweight cryptography project designed by an international team of academics based in France, Belgium and Germany. It is described on the corresponding website, in the corresponding paper [1], and its authors issued cryptanalysis challenges.
Spook relies on a permutation called Shadow. Two versions exist, one that operates on 384 bits and one on 512 bits.
2 Our Attack
2.1 Outline
In order to claim that the security offered by a permutation-based mode corresponds to what a security prove leads us to expect, we need to ensure that the permutation \(P\) used in practice behaves "like a random permutation". This means in particular that it should not be possible to exhibit inputs \(x, y\) such that \((x,P(x))\) and \((y,P(y))\) have a specific behaviour.
It is hard to give a general definition of what such a behaviour is. In our case, we focused on the limited birthday problem (as introduced in [3]): we generate pairs \((x,y)\) such that $$ x \oplus y \in V, P(x) \oplus P(y) \in W $$ where \(V\) and \(W\) are vector spaces of a dimension much smaller than the maximum possible. Our attacks against Shadow-384 and Shadow-512 fit in this general framework.
We also target the authenticated cipher Spook itself and we present an algorithm that, when nonces are misused, can efficiently generate different plaintexts that will be authenticated by the same tag. Our attacks are practical: we have implemented them (see below).
Our attacks and distinguishers are described in much more details in [2].
2.2 Practical Implementation
The implementation of our attacks against Spook and Shadow is available here. It was written by Léo Perrin and André Schrottenloher.
2.3 The team
This attack is a joint work between:
- Patrick Derbez (Irisa)
- Paul Huynh (Loria)
- Virginie Lallemand (Loria)
- María Naya-Plasencia (Inria)
- Léo Perrin (Inria)
- André Schrottenloher (Inria)
3 References
- Davide Bellizia, Francesco Berti, Olivier Bronchain, Gaétan Cassiers, Sébastien Duval, Chun Guo, Gregor Leander, Gaétan Leurent, Itamar Levi, Charles Momin, Olivier Pereira, Thomas Peters, François-Xavier Standaert, and Friedrich Wiemer. Spook: Sponge-Based Leakage-Resistant Authenticated Encryption with a Masked Tweakable Block Cipher. Submission to the second round of the NIST lightweight project. Available online at (link to nist.gov).
- Patrick Derbez, Paul Huynh, Virginie Lallemand, María Naya-Plasencia, Léo Perrin, and André Schrottenloher. Cryptanalysis Results on Spook. Under submission.
- Mitsugu Iwamoto, Thomas Peyrin, and Yu Sasaki. Limited-Birthday Distinguishers for Hash Functions. Advances in Cryptology - ASIACRYPT 2013, pp. 504–523. link to iacr.org