Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings
详细信息 查看全文
- 作者：Dmitry Khovratovich (18) (19)
- 关键词：Skein ; SHA ; 3 ; hash function ; collision attack ; preimage attack ; biclique ; permutation ; Gr?stl
- 刊名：Lecture Notes in Computer Science
- 出版年：2012
- 出版时间：2012
- 年：2012
- 卷：7658
- 期：1
- 页码：562-579
- 全文大小：297KB
- 参考文献：1. Aoki, K., Guo, J., Matusiewicz, K., Sasaki, Y., Wang, L.: Preimages for Step-Reduced SHA-2. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 578-97. Springer, Heidelberg (2009) CrossRef
2. Aoki, K., Sasaki, Y.: Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol.?5381, pp. 103-19. Springer, Heidelberg (2009) CrossRef
3. Aoki, K., Sasaki, Y.: Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.?5677, pp. 70-9. Springer, Heidelberg (2009) CrossRef
4. Aumasson, J.-P., ?al?k, ?., Meier, W., ?zen, O., Phan, R.C.-W., Var?c?, K.: Improved Cryptanalysis of Skein. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 542-59. Springer, Heidelberg (2009) CrossRef
5. Biham, E., Chen, R.: Near-Collisions of SHA-0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.?3152, pp. 290-05. Springer, Heidelberg (2004)
6. Biryukov, A., Khovratovich, D.: Related-Key Cryptanalysis of the Full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 1-8. Springer, Heidelberg (2009) CrossRef
7. Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.?2442, pp. 320-35. Springer, Heidelberg (2002) CrossRef
8. Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique Cryptanalysis of the Full AES. In: Lee, D.H. (ed.) ASIACRYPT 2011. LNCS, vol.?7073, pp. 344-71. Springer, Heidelberg (2011)
9. Diffie, W., Hellman, M.: Special feature exhaustive cryptanalysis of the NBS Data Encryption Standard. Computer?10, 74-4 (1977) CrossRef
10. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein hash function family. Submission to NIST, Round 3 (2010), http://www.skein-hash.info/sites/default/files/skein1.3.pdf
11. Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: Gr?stl -a SHA-3 candidate. Submission to NIST (2008), http://www.groestl.info/Groestl.pdf
12. Gilbert, H., Peyrin, T.: Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol.?6147, pp. 365-83. Springer, Heidelberg (2010) CrossRef
13. Jia, K., Yu, H., Wang, X.: A meet-in-the-middle attack on the full KASUMI. Cryptology ePrint Archive, Report 2011/466 (2011)
14. Khovratovich, D.: Bicliques for permutations: collision and preimage attacks in stronger settings. Cryptology ePrint Archive, Report 2012/141 (2012), http://eprint.iacr.org/2012/141
15. Khovratovich, D., Leurent, G., Rechberger, C.: Narrow-Bicliques: Cryptanalysis of Full IDEA. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 392-10. Springer, Heidelberg (2012) CrossRef
16. Khovratovich, D., Rechberger, C., Savelieva, A.: Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol.?7549, pp. 244-63. Springer, Heidelberg (2012), http://eprint.iacr.org/2011/286.pdf CrossRef
17. Li, J., Isobe, T., Shibutani, K.: Converting Meet-In-The-Middle Preimage Attack into Pseudo Collision Attack: Application to SHA-2. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol.?7549, pp. 264-86. Springer, Heidelberg (2012) CrossRef
18. Mala, H.: Biclique cryptanalysis of the block cipher Square. Cryptology ePrint Archive, Report 2011/500 (2011), http://eprint.iacr.org/
19. Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Gr?stl . In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol.?5665, pp. 260-76. Springer, Heidelberg (2009) CrossRef
20. Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: Rebound Attacks on the Reduced Gr?stl Hash Function. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol.?5985, pp. 350-65. Springer, Heidelberg (2010) CrossRef
21. Peyrin, T.: Improved Differential Attacks for ECHO and Gr?stl. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 370-92. Springer, Heidelberg (2010)
22. Sasaki, Y.: Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool. In: Joux, A. (ed.) FSE 2011. LNCS, vol.?6733, pp. 378-96. Springer, Heidelberg (2011) CrossRef
23. Sasaki, Y., Aoki, K.: Preimage Attacks on Step-Reduced MD5. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol.?5107, pp. 282-96. Springer, Heidelberg (2008) CrossRef
24. Sasaki, Y., Aoki, K.: Finding Preimages in Full MD5 Faster Than Exhaustive Search. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.?5479, pp. 134-52. Springer, Heidelberg (2009) CrossRef
25. Sasaki, Y., Li, Y., Wang, L., Sakiyama, K., Ohta, K.: Non-full-active Super-Sbox Analysis: Applications to ECHO and Gr?stl. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.?6477, pp. 38-5. Springer, Heidelberg (2010) CrossRef
26. Su, B., Wu, W., Wu, S., Dong, L.: Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE. In: Heng, S.-H., Wright, R.N., Goi, B.-M. (eds.) CANS 2010. LNCS, vol.?6467, pp. 124-39. Springer, Heidelberg (2010) CrossRef
27. van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptology?12(1), 1-8 (1999) CrossRef
28. Wagner, D.: The Boomerang Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol.?1636, pp. 156-70. Springer, Heidelberg (1999) CrossRef
29. Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.?3621, pp. 17-6. Springer, Heidelberg (2005)
30. Wu, S., Feng, D., Wu, W., Guo, J., Dong, L., Zou, J.: (Pseudo) Preimage Attack on Reduced-Round Gr?stl Hash Function and Others. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol.?7549, pp. 127-45. Springer, Heidelberg (2012) CrossRef - 作者单位：Dmitry Khovratovich (18) (19)
18. Microsoft Research, USA
19. Infotecs, Russia - ISSN：1611-3349
文摘
We extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, we show how to mount attacks on the primitives with these parameters fixed, i.e. on permutations. We introduce the concept of sliced bicliques, which is a translation of regular bicliques to the framework with permutations. The new framework allows to convert preimage attacks into collision attacks and derive the first collision attacks on the reduced SHA-3 finalist Skein in the hash function setting up to 11 rounds. We also demonstrate new preimage attacks on the reduced Skein and the output transformation of the reduced Gr?stl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques.