Speeding Up the Search Algorithm for the Best Differential and Best Linear Trails

详细信息    查看全文

• 作者：Zhenzhen Bao (16)
  Wentao Zhang (16)
  Dongdai Lin (16)
  
  16. State Key Laboratory of Information Security ; Institute of Information Engineering ; Chinese Academy of Sciences ; Beijing ; China
  
• 关键词：Differential cryptanalysis ; Linear cryptanalysis ; Differential trail ; Linear trail ; Search algorithm ; Optimization ; NOEKEON ; SPONGENT
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8957
• 期：1
• 页码：259-285
• 全文大小：2,008 KB
• 参考文献：1. Biham, E, Shamir, A Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A, Vanstone, SA eds. (1991) Advances in Cryptology-CRYPT0 1990. Springer, Heidelberg, pp. 2-21 CrossRef
  2. Matsui, M Linear cryptanalysis method for DES cipher. In: Helleseth, T eds. (1994) Advances in Cryptology 鈥?EUROCRYPT 1993. Springer, Heidelberg, pp. 386-397
  3. Ohta, K, Moriai, S, Aoki, K Improving the search algorithm for the best linear expression. In: Coppersmith, D eds. (1995) Advances in Cryptology 鈥?CRYPTO 1995. Springer, Heidelberg, pp. 157-170
  4. Collard, B, Standaert, F-X, Quisquater, J-J Improved and multiple linear cryptanalysis of reduced round serpent. In: Pei, D, Yung, M, Lin, D, Wu, C eds. (2008) Information Security and Cryptology. Springer, Heidelberg, pp. 51-65 CrossRef
  5. Daemen, J, Rijmen, V (2002) The Design of Rijndael - AES - The Advanced Encryption Standard. Springer, Heidelberg
  6. Daemen, J., Peeters, M., Van Assche, G., Rijmen, V.: Nessie Proposal: The Block Cipher NOEKEON. Nessie submission (2000)
  7. Bogdanov, A, Knudsen, LR, Leander, G, Paar, C, Poschmann, A, Robshaw, MJB, Seurin, Y, Vikkelsoe, C PRESENT: an ultra-lightweight block cipher. In: Paillier, P, Verbauwhede, I eds. (2007) Cryptographic Hardware and Embedded Systems - CHES 2007. Springer, Heidelberg, pp. 450-466 CrossRef
  8. Biryukov, A, Nikoli膰, I Automatic search for related-key differential characteristics in byte-oriented block ciphers: application to AES, Camellia, Khazad and others. In: Gilbert, H eds. (2010) Advances in Cryptology 鈥?EUROCRYPT 2010. Springer, Heidelberg, pp. 322-344 CrossRef
  9. Mouha, N, Wang, Q, Gu, D, Preneel, B Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C-K, Yung, M, Lin, D eds. (2012) Information Security and Cryptology. Springer, Heidelberg, pp. 57-76 CrossRef
  10. Fouque, P-A, Jean, J, Peyrin, T Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 183-203 CrossRef
  11. Matsui, M On correlation between the order of S-boxes and the strength of DES. In: Santis, A eds. (1995) Advances in Cryptology - EUROCRYPT 1994. Springer, Heidelberg, pp. 366-375
  12. Aoki, K, Kobayashi, K, Moriai, S Best differential characteristic search of FEAL. In: Biham, E eds. (1997) Fast Software Encryption. Springer, Heidelberg, pp. 41-53 CrossRef
  13. Leurent, G Construction of differential characteristics in ARX designs application to skein. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 241-258 CrossRef
  14. Biryukov, A, Velichkov, V Automatic search for differential trails in ARX ciphers. In: Benaloh, J eds. (2014) Topics in Cryptology 鈥?CT-RSA 2014. Springer, Heidelberg, pp. 227-250 CrossRef
  15. Daemen, J.: Cipher and hash function design strategies based on linear and differential cryptanalysis. Doctoral Dissertation, March 1995, K.U.Leuven (1995)
  16. Bogdanov, A, Knezevic, M, Leander, G, Toz, D, Varici, K, Verbauwhede, I (2013) SPONGENT: the design space of lightweight cryptographic hashing. IEEE Trans. Comput. 62: pp. 2041-2053 CrossRef
  17. Ehrlich, G (1973) Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations. Journal of the ACM 20: pp. 500-513 CrossRef
  18. Knuth, DE (2008) The Art of Computer Programming. Addison Wesley, Upper Saddle River
  
• 作者单位：Information Security and Cryptology
• 丛书名：978-3-319-16744-2
• 刊物类别：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

文摘

For judging the resistance of a block cipher to differential cryptanalysis or linear cryptanalysis it is necessary to establish an upper bound on the probability of the best differential or the bias of the best linear approximation. However, getting a tight upper bound is not a trivial problem. We attempt it by searching for the best differential and the best linear trails, which is a challenging task in itself. Based on some previous works, new strategies are proposed to speed up the search algorithm, which are called starting from the narrowest point, concretizing and grouping search patterns, and trialling in minimal changes order strategies. The efficiency of the resulting improved algorithms allows us to state that the probability (bias) of the best 4-round differential (linear) trail in NOEKEON is \(2^{-51}\) ( \(2^{-25}\) ) and the probability (bias) of the best 10-round (11-round) differential (linear) trail is at most \(2^{-131}\) ( \(2^{-71}\) ). For SPONGENT, the best differential trails for certain number of rounds in the permutation functions with width \(b\in \{88, 136, 176, 240\}\) are found. That allows us to update some results presented by its designers.