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(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.
Post a Comment