Monday, June 10, 2013

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
Fj(Mj) = f(M0j,M0+2j-1mod16j) || ... || f(M15j,M15+2j-1mod16j)
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 2128 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 M8) 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(M04,M84)
and
f(M84,M04)
with constant M04 and variable M84 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(221) 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.

No comments:

Post a Comment