Preliminary results on a paper from WISTP 2013

Unfortunately, I missed most of this year's WISTP due to a rerouted plane (I was lucky to arrive in time for my own talk) but one of the few talks that I was able to attend was Pierre Dusart's talk on his paper "Lightweight Authentication Protocol for Low-Cost RFID Tags" (co-authored with S. Traoré). In the paper, the authors propose a new lightweight primitive to be used in combination with authentication protocols on RFID tags. The design of the Dusart-Traoré primitive is best described as a 4-round substitution-permutation network without key scheduling operating on a 128-bit state (in analogy to AES terminology) organized as 16-element array of 8-bit words. It uses a 128-bit key. It's structure is shown in the following image:

(Some of the permutation arrows have been omitted to improve readability.) For the substitution layer the primitive uses the AES S-box and the permutation layer in round j is defined as

F^j(M^j) = f(M₀^j,M_0+2^j-1mod16^j) || ... || f(M₁₅^j,M_{15+2^j-1mod16}^j)

where the f function maps two input bytes onto a single output byte.

We were intrigued by the idea of a potentially secure symmetric lightweight primitive with low round complexity as well as the lack of a hard security estimate (i.e something like "at least 2¹²⁸ operations are needed to break our primitive"). So we decided to take a closer look at the security of this primitive and discovered a most interesting differential property: Assume you have message inputs where all input bytes except one (w.l.o.g let this be M₈) are constant, then we get a differential trail similar to the one shown below:

This implies that for the permutation layer of the last round we have

f(M₀⁴,M₈⁴)

and

f(M₈⁴,M₀⁴)

with constant M₀⁴ and variable M₈⁴ as shown in this zoomed excerpt of the previous image:

Based on this observation we have been able to implement a chosen plaintext attack that recovers the entire key of the primitive on average using O(2²¹) time (i.e. less than a second on my laptop) and a very reasonable number of (M,C) pairs. Thus the primitive is effectively broken. More details of the attack will follow soon in a preliminary paper on eprint.