Higher-Order Differential Meet-in-the-middle Preimage Attacks on SHA-1 and BLAKE
详细信息 查看全文
- 关键词：Hash function ; Preimage attack ; Higher ; order differential meet ; in ; the ; middle ; SHA ; 1 ; BLAKE ; BLAKE2
- 刊名：Lecture Notes in Computer Science
- 出版年：2015
- 出版时间：2015
- 年：2015
- 卷：9215
- 期：1
- 页码：683-701
- 全文大小：326 KB
- 参考文献：1. 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) View Article
2. 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) View Article
3.Aumasson, J.P., Henzen, L., Meier, W., Phan, R.C.W.: SHA-3 proposal BLAKE, version 1.3 (2008). Available online at https://-31002.?net/?blake/-/span>
4. Aumasson, J.-P., Meier, W., Phan, R.C.-W.: The hash function family LAKE. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 36-3. Springer, Heidelberg (2008) View Article
5. Aumasson, J.-P., Neves, S., Wilcox-O’Hearn, Z., Winnerlein, C.: BLAKE2: simpler, smaller, fast as MD5. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 119-35. Springer, Heidelberg (2013) View Article
6.Chang, S.j., Perlner, R., Burr, W.E., Turan, M.S., Kelsey, J.M., Paul, S., Bassham, L.E.: Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition. NIST Interagency Report 7896 (2012)
7. De Cannière, C., Rechberger, C.: Preimages for reduced SHA-0 and SHA-1. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 179-02. Springer, Heidelberg (2008) View Article
8.Diffie, W., Hellman, M.E.: Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer 10, 74-4 (1977)View Article
9.Espitau, T., Fouque, P.A., Karpman, P.: Higher-Order Differential Meet-in-The-Middle Preimage Attacks on SHA-1 and BLAKE. IACR Cryptology ePrint Archive 2015, 515 (2015). https://?eprint.?iacr.?org/-015/-15
10. Guo, J., Karpman, P., Nikoli?, I., Wang, L.: Analysis of BLAKE2 . In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 402-23. Springer, Heidelberg (2014). https://?dx.?doi.?org/-0.-007/-78-3-319-04852-9_-1 View Article
11. 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) View Article
12. Knellwolf, S., Khovratovich, D.: New preimage attacks against reduced SHA-1. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 367-83. Springer, Heidelberg (2012) View Article
13. Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R.E., Costello Jr., D.J., Maurer, U., Mittelholzer, T. (eds.) Communications and Cryptography, pp. 227-33. Springer, USA (1994) View Article
14.Li, J., Xu, L.: Attacks on Round-Reduced BLAKE. IACR Cryptology ePrint Archive 2009, p. 238 (2009). https://?eprint.?iacr.?org/-009/-38
15.Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)View Article
16.National Institute of Standards and Technology: FIPS 180-: Secure Hash Standard (SHS), March 2012
17. Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: a synthetic approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368-78. Springer, Heidelberg (1994). https://?dx.?doi.?org/-0.-007/--540-48329-2_-1 View Article
18. 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) View Article
19.Wang, L., Ohta, K., Sakiyama, K.: Free-start preimages of round-reduced BLAKE compression function. ASIACRYPT rump session (2009). https://?www.?iacr.?org/?conferences/?asiacrypt2009/-?rump/?slides/-1.?pdf - 作者单位：Thomas Espitau (15) (16)
Pierre-Alain Fouque (17) (18)
Pierre Karpman (16) (19)
15. école normale supérieure de Cachan, Cachan, France
16. Inria, Villeurbanne, France
17. Université de Rennes 1, Rennes, France
18. Institut Universitaire de France, Paris, France
19. Nanyang Technological University, Singapore, Singapore - 丛书名：Advances in Cryptology -- CRYPTO 2015
- ISBN：978-3-662-47989-6
- 刊物类别：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
文摘
At CRYPTO?2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions. They demonstrated the usefulness of their approach by significantly improving the previously best known attacks on SHA-1 from CRYPTO?2009, increasing the number of attacked rounds from a 48-round one-block pseudo-preimage without padding and a 48-round two-block preimage without padding to a 57-round one-block preimage without padding and a 57-round two-block preimage with padding, out of 80 rounds for the full function. In this work, we exploit further the differential view of meet-in-the-middle techniques and generalize it to higher-order differentials. Despite being an important technique dating from the mid-90’s, this is the first time higher-order differentials have been applied to meet-in-the-middle preimages. We show that doing so may lead to significant improvements to preimage attacks on hash functions with a simple linear message expansion. We extend the number of attacked rounds on SHA-1 to give a 62-round one-block preimage without padding, a 56-round one-block preimage with padding, and a 62-round two-block preimage with padding. We also apply our framework to the more recent SHA-3 finalist BLAKE and its newer variant BLAKE2, and give an attack for a 2.75-round preimage with padding, and a 7.5-round pseudo-preimage on the compression function.