Analyzing Permutations for AES-like Ciphers: Understanding ShiftRows

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2015Researchpeer-review

View graph of relations

Designing block ciphers and hash functions in a manner that resemble the AES in many aspects has been very popular since Rijndael was adopted as the Advanced Encryption Standard. However, in sharp contrast to the MixColumns operation, the security implications of the way the state is permuted by the operation resembling ShiftRows has never been studied in depth.

Here, we provide the first structured study of the influence of ShiftRows-like operations, or more generally, word-wise permutations, in AES-like ciphers with respect to diffusion properties and resistance towards differential- and linear attacks. After formalizing the concept of guaranteed trail weights, we show a range of equivalence results for permutation layers in this context. We prove that the trail weight analysis when using arbitrary word-wise permutations, with rotations as a special case, reduces to a consideration of a specific normal form. Using a mixed-integer linear programming approach, we obtain optimal parameters for a wide range of AES-like ciphers, and show improvements on parameters for Rijndael-192, Rijndael-256, PRIMATEs-80 and Prøst-128. As a separate result, we show for specific cases of the state geometry that a seemingly optimal bound on the trail weight can be obtained using cyclic rotations only for the permutation layer, i.e. in a very implementation friendly way.
Original languageEnglish
Title of host publicationTopics in Cryptology – CT-RSA 2015 : Proceedings of the Cryptographers’ Track at the RSA Conference 2015
EditorsKaisa Nyberg
PublisherSpringer
Publication date2015
Pages37-58
ISBN (Print)978-3-319-16714-5
ISBN (Electronic)978-3-319-16715-2
DOIs
Publication statusPublished - 2015
EventThe RSA Conference Cryptographers' Track (CT-RSA 2015) - San Francisco, United States
Duration: 20 Apr 201524 Apr 2015
http://users.ics.aalto.fi/knyberg/cfp.html

Conference

ConferenceThe RSA Conference Cryptographers' Track (CT-RSA 2015)
CountryUnited States
CitySan Francisco
Period20/04/201524/04/2015
OtherHeld in conjunction with RSA Conference USA
Internet address
SeriesLecture Notes in Computer Science
Volume9048
ISSN0302-9743
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • AES, AES-like, Differential cryptanalysis, Linear cryptanalysis, Diffusion, Optimization, Mixed-integer linear programming

ID: 117830125