Cryptology ePrint Archive: Report 2017/181
New techniques for trail bounds and application to differential trails in Keccak
Silvia Mella and Joan Daemen and Gilles Van Assche
Abstract: We present new techniques to efficiently scan the space of high-probability
differential trails in bit-oriented ciphers. Differential trails consist in sequences of state patterns that we represent as ordered lists of basic components in order to arrange them in a tree. The task of generating trails with probability above some threshold starts with the traversal of the tree. Our choice of basic components allows us to efficiently prune the tree based on the fact that we can tightly bound the probability of all descendants for any node. Then we extend the state patterns resulting from the tree traversal into longer trails using similar bounding techniques.
We apply these techniques to the 4 largest Keccak-f permutations, for which we
are able to scan the space of trails with weight per round of 15. This space is orders of magnitude larger than previously best result published on Keccak-f that reached 12, which in turn is orders of magnitude larger than any published results achieved with standard tools, that reached at most 9. As a result we provide new and improved bounds for the minimum weight of differential trails on 3, 4, 5 and 6 rounds. We also report on new trails that are, to the best of our knowledge, the ones with the highest known probability.
Category / Keywords: differential cryptanalysis - Keccak - trail weight bounds
Original Publication (in the same form): IACR-TOSC-2017
Date: received 23 Feb 2017
Contact author: silvia mella at unimi it, joan daemen@st com, gilles vanassche@st com
Available format(s): PDF | BibTeX Citation
Version: 20170227:145410 (All versions of this report)
Short URL: ia.cr/2017/181
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]