technology from back to front

Predicting and controlling correlations in differentials of addition mod 2^{n}

This is a paper I wrote in collaboration with Scott Fluhrer in 2005. It was not accepted for FSE 2006; it would have been better if I hadn’t waited until 2014 to make it public, but better late than never.

It arose from a discovery I made when developing attacks on Salsa20 for “Truncated differential cryptanalysis of five rounds of Salsa20”. Several of the attacks were twice as effective as my calculations showed they should have been. I remarked in the paper “By experiment, we have even determined a few differential trails whose probability appears to be twice as high as their weight would suggest—this is presumably because of problems with the independence assumption”. Digging deeper, I discovered why these trails did not behave independently, and developed an algorithm for correctly predicting the probability that the trail holds; this algorithm works across a wide range of “ARX” (addition, rotation, XOR) cryptographic primitives. The obvious person to talk to about these ideas was Cisco’s Scott Fluhrer, whose expertise in differential cryptanalysis led to him breaking the cipher in my first publication, Mercy. Scott pointed me to the ARX MAC “Michael”, and we found that the same technique could be used to analyse an anomaly in Michael.

In all likelihood this is just a historical curiosity; the right place to look now would be the ARX toolkit and associated papers.

Paul Crowley, Scott Fluhrer, Predicting and controlling correlations in differentials of addition mod 2^{n} (PDF).

Paul Crowley

× nine = 63

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us