Improved indifferentiability security bound for the JH mode

详细信息    查看全文

• 作者：Dustin Moody ; Souradyuti Paul ; Daniel Smith-Tone
• 关键词：Indifferentiability ; Security ; Hash functions ; JH mode of operation
• 刊名：Designs, Codes and Cryptography
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：79
• 期：2
• 页码：237-259
• 全文大小：1,146 KB
• 参考文献：1.Andreeva E., Bouillaguet C., Fouque P.A., Hoch J.J., Kelsey J., Shamir A., Zimmer S.: Second preimage attacks on dithered hash functions. In: Smart N.P. (ed.) EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 270–288. Springer, Berlin (2008).
  2.Andreeva E., Mennink B., Preneel B.: On the indifferentiability of the Grøstl hash function. In: Garay J.A., Prisco R.D. (eds.) SCN. Lecture Notes in Computer Science, vol. 6280, pp. 88–105. Springer, Berlin (2010).
  3.Andreeva E., Mennink B., Preneel B.: Security reductions of the second round SHA-3 candidates. In: Burmester M., Tsudik G., Magliveras S.S., Ilic I. (eds.) ISC. Lecture Notes in Computer Science, vol. 6531, pp. 39–53. Springer, Berlin (2010).
  4.Andreeva E., Luykx A., Mennink B.: Provable security of BLAKE with non-ideal compression function. In: 3rd SHA-3 Candidate Conference (2012).
  5.Bagheri N., Gauravaram P., Knudsen L.R.: Building indifferentiable compression functions from the PGV compression functions. Des. Codes Cryptogr. (2014). doi:10.​1007/​s10623-014-0020-z .
  6.Bellare M., Ristenpart T.: Multi-property-preserving hash domain extension and the EMD transform. In: Lai X., Chen K. (eds.) ASIACRYPT 2006. Lecture Notes in Computer Science, vol. 4284, pp. 299–314. Springer, Berlin (2006).
  7.Bernstein D.: CubeHash attack analysis (2.B.5). Online. http://​cubehash.​cr.​yp.​to/​submission2/​attacks . Accessed Feb 2012.
  8.Bhattacharyya R., Mandal A., Nandi M.: Security analysis of the mode of JH hash function. In: Hong S., Iwata T. (eds.) FSE. Lecture Notes in Computer Science, vol. 6147, pp. 168–191. Springer, Berlin (2010).
  9.Chang D., Nandi M., Yung M.: Indifferentiability of the hash algorithm BLAKE. Cryptology ePrint Archive, Report 2011/623. http://​eprint.​iacr.​org/​ (2011). Accessed Feb 2012.
  10.Coron J.S., Dodis Y., Malinaud C., Puniya P.: Merkle–Damgård revisited: how to construct a hash function. In: Shoup V. (ed.) CRYPTO 2005. Lecture Notes in Computer Science, vol. 3621, pp. 430–448. Springer, Berlin (2005).
  11.Dean R.D.: Formal aspects of mobile code security. PhD thesis, Princeton University (1999).
  12.Fleischmann E., Gorski M., Lucks S.: Some observations on indifferentiability. In: Steinfeld R., Hawkes P. (eds.) ACISP. Lecture Notes in Computer Science, vol. 6168, pp. 117–134. Springer, Berlin (2010).
  13.Gauravaram P., Kelsey J.: Linear-XOR and additive checksums don’t protect Damgrd–Merkle hashes from generic attacks. In: Malkin T. (ed.) CT-RSA 2008. Lecture Notes in Computer Science, vol. 4964, pp. 36–51. Springer, Heidelberg (2008).
  14.Gauravaram P., Knudsen L.R.: On randomizing hash functions to strengthen the security of digital signatures. In: Joux A. (ed.) EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 88–105. Springer, Berlin (2009).
  15.Gauravaram P., Knudsen L.R.: Security analysis of randomize-hash-then-sign digital signatures. J. Cryptol. 25(4), 748–779 (2012).
  16.Gauravaram P., Kelsey J., Knudsen L.R., Thomsen S.: On hash functions using checksums. Int. J. Inf. Secur. 9(2), 137–151 (2010).
  17.Halevi S., Krawczyk H.: Strengthening digital signatures via randomized hashing. In: Dwork C. (ed.) CRYPTO 2006. Lecture Notes in Computer Science, vol. 4117, pp. 41–59. Springer, Berlin (2006).
  18.Hoch J.J., Shamir A.: Breaking the ICE—finding multicollisions in iterated concatenated and expanded (ICE) hash functions. In: Robshaw M.J.B. (ed.) FSE. Lecture Notes in Computer Science, vol. 4047, pp. 179–194. Springer, Berlin (2006).
  19.Joux A.: Multicollisions in iterated hash functions: application to cascaded constructions. In: Franklin M.K. (ed.) CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 306–316. Springer, Heidelberg (2004).
  20.Kelsey J., Kohno T.: Herding hash functions and the Nostradamus attack. In: Vaudenay S. (ed.) EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 183–200. Springer, Berlin (2006).
  21.Kelsey J., Schneier B.: Second preimages on n-bit hash functions for much less than \(2^{\text{n}}\) work. In: Cramer R. (ed.) EUROCRYPT 2005. Lecture Notes in Computer Science, vol. 3494, pp. 474–490. Springer, Heidelberg (2005).
  22.Lee J., Hong D.: Collision resistance of the JH hash function. Cryptology ePrint Archive, Report 2011/019. http://​eprint.​iacr.​org/​ (2011). Accessed Feb 2012.
  23.Maurer U.M., Renner R., Holenstein C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor M. (ed.) Theory of Cryptography—TCC 2004. Lecture Notes in Computer Science, vol. 2951, pp. 21–39 Springer, Heidelberg (2004).
  24.Nandi M., Stinson D.R.: Multicollision attacks on some generalized sequential hash functions. IEEE Trans. Inf. Theory 53(2), 759–767 (2007).
  25.NIST: Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register, 72(212), 2007. http://​www.​nist.​gov/​hash-competition . Accessed Feb 2012.
  26.Ristenpart T., Shacham H., Shrimpton T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson K.G. (ed.) EUROCRYPT 2011. Lecture Notes in Computer Science, vol. 6632, pp. 487–506. Springer, Berlin (2011).
  27.Smith-Tone D., Tone C.: A measure of dependence for cryptographic primitives relative to ideal functions. Rocky Mountain J. Math (2015).
  28.Wu H.: The JH hash function. In: The 1st SHA-3 Candidate Conference (2009).
  
• 作者单位：Dustin Moody (1)
  Souradyuti Paul (2)
  Daniel Smith-Tone (1) (3)
  
  1. National Institute of Standards and Technology, Gaithersburg, MD, 20877, USA
  2. Computer Science and Engineering, Indian Institute of Technology (IIT) Gandhinagar, Chandkheda, Ahmedabad, 382424, India
  3. Department of Mathematics, University of Louisville, Louisville, KY, 40292, USA
  
• 刊物类别：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

文摘

Indifferentiability security of a hash mode of operation guarantees the mode’s resistance against all generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. The JH hash function was one of the five finalists in the National Institute of Standards and Technology SHA-3 hash function competition. Despite several years of analysis, the indifferentiability security of the JH mode has remained remarkably low, only at \(n/3\) bits, while the two finalist modes Keccak and Grøstl offer a security guarantee of \(n/2\) bits. Note all these three modes operate with \(n\)-bit digest and \(2n\)-bit permutations. In this paper, we improve the indifferentiability security bound for the JH mode to \(n/2\) bits (e.g. from approximately 171 to 256 bits when \(n=512\)). To put this into perspective, our result guarantees the absence of (non-trivial) attacks on both the JH-256 and JH-512 hash functions with time less than approximately \(2^{256}\) computations of the underlying 1024-bit permutation, under the assumption that the underlying permutations can be modeled as an ideal permutation. Our bounds are optimal for JH-256, and the best known for JH-512. We obtain this improved bound by establishing an isomorphism of certain query-response graphs through a careful design of the simulators and bad events. Our experimental data strongly supports the theoretically obtained results.