In this paper, we aim to bridge this fundamental gap. Our main result is a quantitative connection between a bound on the EDP of differential characteristics and the highest number of input pairs that actually satisfy a characteristic for a fixed key. This is particularly important for the design of permutation-based hash functions such as sponge functions, where the EDP value itself is not informative for the absence of rekeying. We apply our theoretical result to revisit the security arguments of some prominent recent block ciphers and hash functions. For most of those, we have good news: a characteristic is followed by a small number of pairs only. For Keccak, though, currently much more rounds would be needed for our technique to guarantee any reasonable maximum number of pairs.
Thus, our work --- for the first time --- sheds light on the fixed-key differential behaviour of block ciphers in general and substitution-permutation networks in particular which has been a long-standing fundamental problem in symmetric-key cryptography.Category / Keywords: secret-key cryptography / block cipher, hash function, differential cryptanalysis, differential characteristic, expected differential probability Original Publication (in the same form): IACR-CRYPTO-2003 Date: received 7 Aug 2013 Contact author: celine blondeau at aalto fi Available format(s): PDF | BibTeX Citation Version: 20130814:144111 (All versions of this report) Short URL: ia.cr/2013/482 Discussion forum: Show discussion | Start new discussion