MJH: a faster alternative to MDC-2
详细信息 查看全文
- 作者：Jooyoung Lee ; Martijn Stam
- 关键词：Hash function ; Blockcipher ; Provable security ; Collision resistance ; 94A60
- 刊名：Designs, Codes and Cryptography
- 出版年：2015
- 出版时间：August 2015
- 年：2015
- 卷：76
- 期：2
- 页码：179-205
- 全文大小：793 KB
- 参考文献：1.Black J., Rogaway P., Shrimpton T.: Black-box analysis of the block-cipher-based hash-function construction from PGV. In: Yung M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320-25. Springer, Heidelberg (2002).
2.Black J., Cochran M., Shrimpton T.: On the impossibility of highly-efficient blockcipher-based hash functions. In: Cramer R (ed.) Eurocrypt 2005. LNCS, vol. 3494, pp. 526-41. Springer, Heidelberg (2005).
3.Bogdanov A., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y.: Hash functions and RFID tags: mind the gap. In: Oswald E., Rohatgi P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 283-99. Springer, Heidelberg (2008).
4.Bos J.W., ?zen O., Stam M.: Efficient hashing using the AES instruction set. In: Preneel B., Takagi T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 507-22. Springer, Heidelberg (2011).
5.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).
6.Brachtl B., Coppersmith D., Heyden M., Matyas S., Meyer C., Oseas J., Pilpel S., Schilling M.: Data authentication using modification detection codes based on a public one-way encryption function. US Patent #4,908,861, 13 Mar 1990.
7.Damg?rd I.: A design principle for hash functions. In: Brassard G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416-27. Springer, Heidelberg (1990).
8.Fleischmann E., Gorski M., Lucks S.: On the security of Tandem-DM. In: Dunkelman O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 85-05. Springer, Heidelberg (2009).
9.Fleischmann E., Gorski M., Lucks S.: Security of cyclic double block length hash functions. In: Parker M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 153-75, Springer, Heidelberg (2009).
10.Hattori M., Hirose S., Yoshida S.: Analysis of double block length hash functions. In: Paterson K.G. (ed.) IMA 2003. LNCS, vol. 2898, pp. 290-02. Springer, Heidelberg (2003).
11.Hirose S.: Provably secure double-block-length hash functions in a black-box model. In: Park C., Chee S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 330-42. Springer, Heidelberg (2005).
12.Hirose S.: A security analysis of double-block-length hash functions with the rate 1. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E89-A(10), 2575-582 (2006).
13.Hirose S.: Some plausible construction of double-block-length hash functions. In: Robshaw M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210-25. Springer, Heidelberg (2006).
14.Knudsen L.R., Massey J.L., Preneel B.: Attacks on fast double block length hash functions. J. Cryptol. 11(1), 59-2 (1998).
15.Knudsen L.R., Mendel F., Rechberger C., Thomsen S.S.: Cryptanalysis of MDC-2. In: Joux A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 106-20. Springer, Heidelberg (2009).
16.Lai X., Massey J.L.: Hash function based on block ciphers. In: Rueppel R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 55-0. Springer, Heidelberg (1993).
17.Lee J., Hong D.: Collision resistance of the JH hash function. IEEE Trans. Inf. Theory 58(3), 1992-995 (2012).
18.Lee J., Kwon D.: The security of Abreast-DM in the ideal cipher model. IEICE Trans. 94-A(1), pp. 104-09 (2011).
19.Lee J., Stam M.: A faster alternative to MDC-2. In: Kiayias A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 213-36. Springer, Heidelberg (2011).
20.Lee J., Steinberger J.: Multi-property-preserving domain extension using polynomial-based modes of operation. In: Gilbert H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 573-96. Springer, Heidelberg (2010).
21.Lee J., Stam M., Steinberger J.: The collision security of Tandem-DM in the ideal cipher model. In: Rogaway P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 561-77. Springer, Heidelberg (2011).
22.Lucks S.: A collision-resistant rate-1 double-block-length hash function. In: Symmetric Cryptography, Dagstuhl Seminar Proceedings 07021 (2007).
23.Merkle R.: One way hash functions and DES. In: Brassard G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428-46. Springer, Heidelberg (1990).
24.Meyer C., Schilling M.: Chargement securise d’un programma avec code de detection de manipulation (1987)
25.?zen O., Stam M.: Another glance at double-length hashing. In: Parker M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 176-01. Springer, Heidelberg (2009).
26.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).
27.Ristenpart T., Shrimpton T.: How to build a hash function from any collision-resistant function. In: Kurosawa K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 147-63. Springer, Heidelberg (2007).
28.Rogaway P., Steinberger J.: Constructing cryptographic hash functions from fixed-key blockciphers. In: Wagner D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 433-50. Springer, Heidelberg (2008).
29.Rogaway P., Steinberger J.: Security/efficiency tradeoffs for per - 作者单位：Jooyoung Lee (1)
Martijn Stam (2)
1. Sejong University, Seoul, Korea
2. University of Bristol, Bristol, UK - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Combinatorics
Coding and Information Theory
Data Structures, Cryptology and Information Theory
Data Encryption
Discrete Mathematics in Computer Science
Information, Communication and Circuits - 出版者：Springer Netherlands
- ISSN：1573-7586
文摘
In this paper, we introduce a new class of double-block-length hash functions. Using the ideal cipher model, we prove that these hash functions, dubbed MJH, are asymptotically collision resistant up to \(O(2^{n(1-\epsilon )})\) query complexity for any \(\epsilon >0\) in the iteration, where \(n\) is the block size of the underlying blockcipher. When based on \(n\)-bit key blockciphers, our construction, being of rate 1/2, provides better provable security than MDC-2, the only known construction of a rate-1/2 double-length hash function based on an \(n\)-bit key blockcipher with non-trivial provable security. Moreover, since key scheduling is performed only once per message block for MJH, our proposal significantly outperforms MDC-2 in efficiency. When based on a \(2n\)-bit key blockcipher, we can use the extra \(n\) bits of key to increase the amount of payload accordingly. Thus we get a rate-1 hash function that is much faster than existing proposals, such as Tandem-DM with comparable provable security. This is the full version of Lee and Stam?(A faster alternative to MDC-2, 2011).