Analyzing Permutations for AES-like Ciphers: Understanding ShiftRows

详细信息    查看全文

• 关键词：AES ; AES ; like ; Differential cryptanalysis ; Linear cryptanalysis ; Diffusion ; Optimization ; Mixed ; integer linear programming
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9048
• 期：1
• 页码：37-58
• 全文大小：369 KB
• 参考文献：1. Andreeva, E., Bilgin, B., Bogdanov, A., Luykx, A., Mendel, F., Mennink, B., Mouha, N., Wang, Q., Yasuda, K.: PRIMATEs. CAESAR Proposal (2014). http://competitions.cr.yp.to/round1/primatesv1.pdf
  2. Asratian, A.S., Denley, T.M.J., H?ggkvist, R.: Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics. Cambridge University Press (1998)
  3. Barreto, P.S.L.M., Rijmen, V.: The ANUBIS Block Cipher. NESSIE submission (2000). http://www.larc.usp.br/pbarreto/AnubisPage.html
  4. Beierle, C., Jovanovic, P., Lauridsen, M.M., Leander, G., Rechberger, C.: Source code for experimental results (2015). https://github.com/mmeh/understanding-shiftrows
  5. Benadjila, R., Billet, O., Gilbert, H., Macario-Rat, G., Peyrin, T., Robshaw, M., Seurin, Y.: SHA-3 Proposal: ECHO (2010). http://crypto.rd.francetelecom.com/ECHO/
  6. Biham, E, Shamir, A Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A, Vanstone, SA eds. (1991) Advances in Cryptology - CRYPTO -0. Springer, Heidelberg, pp. 2-21
  7. Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer (1993)
  8. Biryukov, A., Khovratovich, D.: PAEQ. CAESAR Proposal (2014). http://competitions.cr.yp.to/round1/paeqv1.pdf
  9. Borghoff, J, Canteaut, A, Güneysu, T, Kavun, EB, Knezevic, M, Knudsen, LR, Leander, G, Nikov, V, Paar, C, Rechberger, C, Rombouts, P, Thomsen, SS, Yal??n, T PRINCE -a low-latency block cipher for pervasive computing applications. In: Wang, X, Sako, K eds. (2012) Advances in Cryptology -ASIACRYPT 2012. Springer, Heidelberg, pp. 208-225 CrossRef
  10. Daemen, J, Knudsen, LR, Rijmen, V The block cipher SQUARE. In: Biham, E eds. (1997) Fast Software Encryption. Springer, Heidelberg, pp. 149-165 CrossRef
  11. Daemen, J., Rijmen, V.: AES Proposal: Rjindael (1998). rijndael/Rijndael-ammended.pdf" class="a-plus-plus">http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
  12. Daemen, J, Rijmen, V The wide trail design strategy. In: Honary, B eds. (2001) Cryptography and Coding. Springer, Heidelbergpp. 222 CrossRef
  13. Fleischmann, E, Forler, C, Gorski, M, Lucks, S Twister -a framework for secure and fast hash functions. In: Bao, F, Li, H, Wang, G eds. (2009) Information Security Practice and Experience. Springer, Heidelberg, pp. 257-273 CrossRef
  14. Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: Gr?stl - a SHA-3 Candidate (2011). http://www.groestl.info/
  15. Guo, J, Peyrin, T, Poschmann, A The PHOTON family of lightweight hash functions. In: Rogaway, P eds. (2011) Advances in Cryptology -CRYPTO 2011. Springer, Heidelberg, pp. 222-239 CrossRef
  16. Guo, J, Peyrin, T, Poschmann, A, Robshaw, M The LED block cipher. In: Preneel, B, Takagi, T eds. (2011) Cryptographic Hardware and Embedded Systems -CHES 2011. Springer, Heidelberg, pp. 326-341 CrossRef
  17. IBM. ILOG CPLEX Optimizer, 1997-014. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/
  18. Indesteege, S., Andreeva, E., De Cannière, C., Dunkelman, O., K?per, E., Nikova, S., Preneel, B., Tischhauser, E.: The LANE hash function. Submission to NIST (2008). http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf
  19. Nakahara, J 3D: a three-dimensional block cipher. In: Franklin, MK, Hui, LC
• 作者单位：Topics in Cryptology ¨C- CT-RSA 2015
• 丛书名：978-3-319-16714-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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.