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
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