Reconsidering Naito Feed-Forward-Free Double-Block-Length Hash Function
摘要
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.