**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 2^{n}, 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.