Toolkit for the differential cryptanalysis of S-functions
- Authors: Nicky Mouha, Vesselin Velichkov, Christophe De Cannière, Bart Preneel
- Download: http://www.ecrypt.eu.org/tools/uploads/s-function_toolkit_v2.zip
- Documentation: http://www.cosic.esat.kuleuven.be/publications/article-1473.pdf
Note: v2 fixes a bug in the probability calculation. This bug does not affect the matrices that are output by the program.
An increasing number of cryptographic primitives use operations such as addition modulo 2n, multiplication by a constant and bitwise Boolean functions as a source of non-linearity. In NIST’s SHA-3 competition, this applies to 6 out of the 14 second-round candidates. We generalize such constructions by introducing the concept of S-functions. An S-function is a function that calculates the i-th output bit using only the inputs of the i-th bit position and a finite state S[i]. Although S-functions have been analyzed before, our toolkit is the first to present a fully general and efficient framework to determine their differential properties. A precursor of this framework was used in the cryptanalysis of SHA-1. We show how to calculate the probability that given input differences lead to given output differences, as well as how to count the number of output differences with non-zero probability. Our methods are rooted in graph theory, and the calculations can be efficiently performed using matrix multiplications. The toolkit also provides a general algorithm to efficiently list the output differences with the highest probability, for a given type of difference and operation.