The Differential Analysis of S-Functions

Nicky Mouha, Vesselin Velichkov, Christophe De Cannière, Bart Preneel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationSelected Areas in Cryptography
EditorsAlex Biryukov, Guang Gong, Douglas R. Stinson
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages36-56
Number of pages21
ISBN (Print)978-3-642-19574-7
DOIs
Publication statusPublished - 2011
Event17th Annual Workshop on Selected Areas in Cryptography - Waterloo, Canada
Duration: 12 Aug 201013 Aug 2010

Conference

Conference17th Annual Workshop on Selected Areas in Cryptography
Abbreviated titleSAC 2010
Country/TerritoryCanada
CityWaterloo
Period12/08/1013/08/10

Fingerprint

Dive into the research topics of 'The Differential Analysis of S-Functions'. Together they form a unique fingerprint.

Cite this