Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các cuộc tấn công xoay hồi phục trên phiên bản rút gọn của Skein
Tóm tắt
Trong nghiên cứu này, chúng tôi kết hợp hai phương pháp mạnh mẽ trong phân tích mã đối xứng: phân tích mã xoay và cuộc tấn công hồi phục. Phân tích mã xoay được thiết kế để phân tích các thiết kế tập trung vào bit như các sơ đồ ARX (Cộng-Xoay-OR). Nó đã được áp dụng cho nhiều hàm băm và mã khối, bao gồm tiêu chuẩn mới SHA-3 (Keccak). Cuộc tấn công hồi phục là một phương pháp bắt đầu từ giữa để tìm kiếm các đường đi khác biệt và các cặp phù hợp trong các thiết kế tập trung vào byte như mạng Hoán vị-Thay thế và AES. Chúng tôi áp dụng cuộc tấn công kết hợp mới của mình vào phiên bản rút gọn của hàm băm Skein, một trong những ứng viên của cuộc thi SHA-3. Cuộc tấn công của chúng tôi đã xâm nhập hơn hai phần ba lõi của Skein—mã Threefish, buộc các nhà thiết kế phải thay đổi bản đề xuất để ngăn chặn điều này. Phần hồi phục trong cuộc tấn công của chúng tôi đã được cải thiện đáng kể để mang lại kết quả cho số lượng vòng lớn nhất. Chúng tôi cũng sử dụng các bit trung lập và các phương pháp thay đổi thông điệp từ thực tiễn tìm kiếm va chạm trong các hàm băm MD5 và SHA-1. Những phương pháp này đã đẩy thuộc tính xoay qua nhiều vòng hơn so với các phân tích trước đó cho rằng, và cuối cùng thiết lập một thuộc tính phân biệt cho mã Threefish rút gọn. Chúng tôi chứng minh một cách chính thức rằng thuộc tính như vậy không thể được tìm thấy cho một mã lý tưởng trong giới hạn phức tạp của cuộc tấn công của chúng tôi. Các ước tính phức tạp được hỗ trợ bởi các thí nghiệm sâu rộng.
Từ khóa
#phân tích mã đối xứng #phân tích mã xoay #cuộc tấn công hồi phục #hàm băm #mã khối #SHA-3 #Skein #ThreefishTài liệu tham khảo
G.V. Assche, A rotational distinguisher on Shabal’s keyed permutation and its impact on the security proofs. Available online at http://gva.noekeon.org/papers/ShabalRotation.pdf (2010)
J.-P. Aumasson, Ç. Çalik, W. Meier, O. Özen, R.C.-W. Phan, K. Varici, Improved cryptanalysis of Skein, in ASIACRYPT’09. Lecture Notes in Computer Science, vol. 5912 (Springer, Berlin, 2009), pp. 542–559
D.J. Bernstein, Salsa20. Technical Report 2005/025. In eSTREAM. ECRYPT Stream Cipher Project (2005). See http://cr.yp.to/snuffle.html
G. Bertoni, J. Daemen, M. Peeters, G.V. Assche, The Keccak reference, version 3.0 (2011). See http://keccak.noekeon.org/Keccak-reference-3.0.pdf
E. Biham, R. Chen, Near-collisions of SHA-0, in CRYPTO’04. Lecture Notes in Computer Science, vol. 3152 (Springer, Berlin, 2004), pp. 290–305
E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemuet, W. Jalby, Collisions of SHA-0 and Reduced SHA-1, in EUROCRYPT’05, ed. by R. Cramer. Lecture Notes in Computer Science vol. 3494 (Springer, Berlin, 2005), pp. 36–57
A. Biryukov, D. Khovratovich, I. Nikolić, Distinguisher and related-key attack on the full AES-256, in CRYPTO’09. Lecture Notes in Computer Science, vol. 5677 (Springer, Berlin, 2009), pp. 231–249
A. Bogdanov, D. Khovratovich, C. Rechberger, Biclique cryptanalysis of the full AES, in ASIACRYPT’11. Lecture Notes in Computer Science, vol. 7073 (Springer, Berlin, 2011), pp. 344–371
J. Chen, K. Jia, Improved related-key boomerang attacks on round-reduced Threefish-512, in ISPEC, ed. by J. Kwak, R.H. Deng, Y. Won, G. Wang. Lecture Notes in Computer Science, vol. 6047 (Springer, Berlin, 2010), pp. 1–18
M. Daum, Cryptanalysis of Hash functions of the MD4-family. PhD thesis, Ruhr-Universität Bochum (2005)
A. Duc, J. Guo, T. Peyrin, L. Wei, Unaligned rebound attack: application to Keccak, in FSE’12. Lecture Notes in Computer Science, vol. 7549 (Springer, Berlin, 2012), pp. 402–421
N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, The Skein hash function family. Submission to NIST. Available at http://www.skein-hash.info/sites/default/files/skein1.1.pdf.
N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, Provable security support for the Skein hash family (2009). Available at www.skein-hash.info/sites/default/files/skein-proofs.pdf
N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, The Skein hash function family, version 1.2 (2009). Submission to NIST (Round 2), Available at http://www.skein-hash.info/sites/default/files/skein1.2.pdf
N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, The Skein hash function family, version 1.3 (2010). Submission to NIST (Round 3). Available at http://www.skein-hash.info/sites/default/files/skein1.3.pdf
S. Indesteege, F. Mendel, B. Preneel, C. Rechberger, Collisions and other non-random properties for step-reduced SHA-256, in Selected Areas in Cryptography’08, ed. by R.M. Avanzi, L. Keliher, F. Sica. Lecture Notes in Computer Science, vol. 5381 (Springer, Berlin, 2008), pp. 276–293
J. Jean, M. Naya-Plasencia, T. Peyrin, Improved rebound attack on the finalist Grøstl, in FSE’12. Lecture Notes in Computer Science, vol. 7549 (Springer, Berlin, 2012), pp. 110–126
J. Jean, M. Naya-Plasencia, M. Schläffer, Improved analysis of ECHO-256, in Selected Areas in Cryptography’11. Lecture Notes in Computer Science, vol. 7118 (Springer, Berlin, 2011), pp. 19–36
A. Joux, T. Peyrin, Hash functions and the (amplified) boomerang attack, in CRYPTO’07. Lecture Notes in Computer Science, vol. 4622 (Springer, Berlin, 2007), pp. 244–263
D. Khovratovich, Bicliques for permutations: collision and preimage attacks in stronger settings, in ASIACRYPT’12. Lecture Notes in Computer Science, vol. 7658 (Springer, Berlin, 2012), pp. 544–561
D. Khovratovich, M. Naya-Plasencia, A. Röck, M. Schläffer, Cryptanalysis of Luffa v2 components, in Selected Areas in Cryptography’10. Lecture Notes in Computer Science, vol. 6544 (Springer, Berlin, 2010), pp. 388–409
D. Khovratovich, I. Nikolić, Rotational cryptanalysis of ARX, in FSE’10. Lecture Notes in Computer Science, vol. 6147 (Springer, Berlin, 2010), pp. 333–346
D. Khovratovich, I. Nikolić, C. Rechberger, Rotational rebound attacks on reduced Skein, in ASIACRYPT’10. Lecture Notes in Computer Science, vol. 6477 (Springer, Berlin, 2010), pp. 1–19
D. Khovratovich, C. Rechberger, A. Savelieva, Bicliques for preimages: attacks on Skein-512 and the SHA-2 family, in FSE’12. Lecture Notes in Computer Science, vol. 7549 (Springer, Berlin, 2012), pp. 244–263
V. Klima, Tunnels in hash functions: MD5 collisions within a minute (2006). Available at http://eprint.iacr.org/2006/105.pdf
M. Lamberger, F. Mendel, C. Rechberger, V. Rijmen, M. Schläffer, Rebound distinguishers: results on the full Whirlpool compression function, in ASIACRYPT’09. Lecture Notes in Computer Science, vol. 5912 (Springer, Berlin, 2009), pp. 126–143
G. Leurent, Construction of differential characteristics in ARX designs—application to Skein. Cryptology. ePrint Archive, Report 2012/668 (2012)
G. Leurent, A. Roy, Boomerang attacks on Hash function using auxiliary differentials, in CT-RSA’12. Lecture Notes in Computer Science, vol. 7178 (Springer, Berlin, 2012), pp. 215–230
J. Li, T. Isobe, K. Shibutani, Converting meet-in-the-middle preimage attack into pseudo collision attack: application to SHA-2, in FSE’12. Lecture Notes in Computer Science, vol. 7549 (Springer, Berlin, 2012), pp. 264–286
K. Matusiewicz, M. Naya-Plasencia, I. Nikolić, Y. Sasaki, M. Schläffer, Rebound attack on the full LANE compression function, in ASIACRYPT’09. Lecture Notes in Computer Science, vol. 5912 (Springer, Berlin, 2009), pp. 106–125
F. Mendel, T. Nad, M. Schläffer, Finding SHA-2 characteristics: searching through a minefield of contradictions, in ASIACRYPT’11. Lecture Notes in Computer Science, vol. 7073 (Springer, Berlin, 2011), pp. 288–307
F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, Improved cryptanalysis of the reduced Grøstl compression function, ECHO permutation and AES block cipher, in Selected Areas in Cryptography’09. Lecture Notes in Computer Science, vol. 5867 (Springer, Berlin, 2009), pp. 16–35
F. Mendel, N. Pramstaller, C. Rechberger, V. Rijmen, Analysis of step-reduced SHA-256, in FSE’06. Lecture Notes in Computer Science, vol. 4047 (Springer, Berlin, 2006), pp. 126–143
F. Mendel, C. Rechberger, M. Schläffer, S.S. Thomsen, The rebound attack: cryptanalysis of reduced Whirlpool and Grøstl, in FSE’09. Lecture Notes in Computer Science, vol. 5665 (Springer, Berlin, 2009), pp. 260–276
P. Morawiecki, J. Pieprzyk, M. Srebrny, Rotational cryptanalysis of round-reduced Keccak. Cryptology. ePrint Archive, Report 2012/546 (2012). http://eprint.iacr.org/
Y. Naito, Y. Sasaki, T. Shimoyama, J. Yajima, N. Kunihiro, K. Ohta, Improved collision search for SHA-0, in ASIACRYPT’06. Lecture Notes in Computer Science, vol. 4284 (Springer, Berlin, 2006), pp. 21–36
I. Nikolić, A. Biryukov, Collisions for step-reduced SHA-256, in FSE’08. Lecture Notes in Computer Science, vol. 5086 (Springer, Berlin, 2008), pp. 1–15
I. Nikolić, J. Pieprzyk, P. Sokolowski, R. Steinfeld, Rotational cryptanalysis of (modified) versions of BMW and SIMD (2010). Available online at https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_(Nikolic,_Pieprzyk,_Sokolowski,_Steinfeld).pdf
V. Rijmen, E. Oswald, Update on SHA-1, in CT-RSA, ed. by A. Menezes. Lecture Notes in Computer Science, vol. 3376 (Springer, Berlin, 2005), pp. 58–71
Y. Sasaki, K. Yasuda, Known-key distinguishers for 11-round Feistel ciphers: application to collision attacks on their hashing modes, in FSE’11. Lecture Notes in Computer Science, vol. 6733 (Springer, Berlin, 2011), pp. 397–415
F.-X. Standaert, G. Piret, N. Gershenfeld, J.-J. Quisquater, SEA: a scalable encryption algorithm for small embedded applications, in CARDIS’06. Lecture Notes in Computer Science, vol. 3928 (Springer, Berlin, 2006), pp. 222–236
M. Stevens, On collisions for MD5. Master’s thesis, Eindhoven University of Technology, Eindhoven, Netherlands (2007)
B. Su, W. Wu, S. Wu, L. Dong, Near-collisions on the reduced-round compression functions of Skein and BLAKE, in CANS’10. LNCS, vol. 6467 (Springer, Berlin, 2010), pp. 124–139
X. Wang, Y.L. Yin, H. Yu, Finding collisions in the full SHA-1, in CRYPTO, ed. by V. Shoup. Lecture Notes in Computer Science, vol. 3621 (Springer, Berlin, 2005), pp. 17–36
X. Wang, H. Yu, How to break MD5 and other hash functions, in EUROCRYPT’05. LNCS, vol. 3494 (Springer, Berlin, 2005), pp. 19–35
S. Wu, D. Feng, W. Wu, Practical rebound attack on 12-round Cheetah-256, in ICISC, ed. by D. Lee, S. Hong. Lecture Notes in Computer Science, vol. 5984 (Springer, Berlin, 2009), pp. 300–314
H. Yu, J. Chen, X. Wang, Partial-collision attack on the round-reduced compression function of Skein-256, in FSE’13 (2013)