# 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