Abstract
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. In this paper, 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, this paper 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.
Original language | English |
---|---|
Title of host publication | Selected Areas in Cryptography |
Editors | Alex Biryukov, Guang Gong, Douglas R. Stinson |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 36-56 |
Number of pages | 21 |
ISBN (Print) | 978-3-642-19574-7 |
DOIs | |
Publication status | Published - 2011 |
Event | 17th Annual Workshop on Selected Areas in Cryptography - Waterloo, Canada Duration: 12 Aug 2010 → 13 Aug 2010 |
Conference
Conference | 17th Annual Workshop on Selected Areas in Cryptography |
---|---|
Abbreviated title | SAC 2010 |
Country/Territory | Canada |
City | Waterloo |
Period | 12/08/10 → 13/08/10 |