At ACISP 2017, Naito proposed a double-block-length (DBL) hash function \(\textsf{NHash}\) with the following features: (i) without the costly feed-forward operations; (ii) of rate 1/2, and every pair of blockcipher-calls is parallelizable; (iii) achieving n-bit indifferentiability security using a blockcipher with n-bit blocks and \(\kappa \) -bit keys. This is one of the state-of-the-art DBL hash constructions. The only shortage is the use of a finalization function by two blockcipher-calls, which is unfriendly to short messages. We consider \(\textsf{MDPN}\) , which is obtained by injecting Naito’s feed-forward-free compression function into the Merkle-Damgård with permutation construction (JoC 2008), and prove \(n - \log _2 n\) indifferentiability for it. To our knowledge, this is the first time to achieve the three aforementioned properties of \(\textsf{NHash}\) plus finalization-freeness simultaneously. We also investigate the (second) preimage security of \(\textsf{NHash}\) and \(\textsf{MDPN}\) . When \(\kappa \ge 2n+1\) and a strengthened Merkle-Damgård message padding is used, for any challenge message with at least \(n+2\) blocks, we show an attack finding a second preimage on \(\textsf{NHash}\) with the same number of blocks, using \(O(n 2^n)\) time and \(O( 2^{n} )\) memory. Our idea also yields a preimage attack against \(\textsf{MDPN}\) with the same complexities.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reconsidering Naito Feed-Forward-Free Double-Block-Length Hash Function

  • Zhuoxi Lin,
  • Chun Guo

摘要

At ACISP 2017, Naito proposed a double-block-length (DBL) hash function \(\textsf{NHash}\) with the following features: (i) without the costly feed-forward operations; (ii) of rate 1/2, and every pair of blockcipher-calls is parallelizable; (iii) achieving n-bit indifferentiability security using a blockcipher with n-bit blocks and \(\kappa \) -bit keys. This is one of the state-of-the-art DBL hash constructions. The only shortage is the use of a finalization function by two blockcipher-calls, which is unfriendly to short messages. We consider \(\textsf{MDPN}\) , which is obtained by injecting Naito’s feed-forward-free compression function into the Merkle-Damgård with permutation construction (JoC 2008), and prove \(n - \log _2 n\) indifferentiability for it. To our knowledge, this is the first time to achieve the three aforementioned properties of \(\textsf{NHash}\) plus finalization-freeness simultaneously. We also investigate the (second) preimage security of \(\textsf{NHash}\) and \(\textsf{MDPN}\) . When \(\kappa \ge 2n+1\) and a strengthened Merkle-Damgård message padding is used, for any challenge message with at least \(n+2\) blocks, we show an attack finding a second preimage on \(\textsf{NHash}\) with the same number of blocks, using \(O(n 2^n)\) time and \(O( 2^{n} )\) memory. Our idea also yields a preimage attack against \(\textsf{MDPN}\) with the same complexities.