CWI Cryptology Group

Abstract: ARX is a class of symmetric-key algorithms based on the simple arithmetic operations: modular addition, bitwise rotation and exclusive-OR. The first such designs date back to the 80s with the proposal of the block cipher FEAL (1987). Other notable examples are the block ciphers RC5 (1994), TEA (1994), SPECK (2013) and LEA (2013); the stream ciphers Salsa20 and ChaCha (2008); the hash functions BLAKE (2008) and Skein (2008) and the MAC algorithm Chaskey (2014). ARX algorithms owe their popularity to their simplicity and efficiency (especially in software), combined with good security properties. In spite of their excellent characteristics, ARX designs suffer from a major drawback: the theory for their analysis is significantly less developed than their S-box based counterparts such as the AES. In particular, no methods exist for proving the security of ARX against two of the most powerful cryptanalytic techniques -- differential and linear cryptanalysis. In this talk we describe a new algorithm for finding differential and linear trails in ARX. It is based on a Matsui-like branch-and-bound search strategy, does not use any heuristics and computes optimal results. Two practical applications of the technique are demonstrated. First, it is applied to block cipher SPECK and the best differential trails on reduced round versions are reported. Second, the technique is applied in the design of SPARX -- the first ARX cipher with provable resistance against single-trail differential and linear cryptanalysis.