logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 3: 032112(2019) https://doi.org/10.1007/s11432-018-9568-2

Pseudo random oracle of Merkle-Damgå rd hash functions revisited

More info
  • ReceivedJun 8, 2018
  • AcceptedAug 21, 2018
  • PublishedJan 29, 2019

Abstract

Following the well-known random oracle Methodology, a cryptographic hash function is required to satisfy the property of pseudo-random oracle (PRO), that is indifferentiable from a random oracle. This paper revisits the PRO property of popular hash function modes purely from a theoretical point of view.Original Merkle-Damgård mode (sometimes referred to as Strengthened Merkle-Damgård) does not satisfy the PRO security due to the length-extension attack. To remedy it, a series of variants have been proposed with tweaks of either adopting a prefix-free padding or modifying the final primitive call. From these tweaks, we derive a common structural property named prefix-free computing. Indeed, all PRO-secure Merkle-Damgård variants published so far are prefix-free computing. Hence, an interesting question with respect to the nature of PRO security arises: is prefix-free computing a necessary condition for PRO-secure Merkle-Damgård hash function? This paper gives a negative answer.We investigate the difference between length-extension resistance and prefix-free computing, and find that length-extension resistance does not necessarily imply prefix-free computing. Consequently, we construct a dedicated Merkle-Damgård variant as a counterexample that is PRO-secure but not prefix-free computing.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61602302, 61472250, 61672347), Natural Science Foundation of Shanghai (Grant No. 16ZR1416400), Shanghai Excellent Academic Leader Funds (Grant No. 16XD1401300), and 13th Five-Year National Development Fund of Cryptography (Grant No. MMJJ20170114).


References

[1] Damgård I. A design principle for hash functions. In: Proceedings of the 9th Annual International Cryptology Conference, Santa Barbara, California, 1989. 416--427. Google Scholar

[2] Merkle R C. One way hash functions and DES In: Proceedings of the 9th Annual International Cryptology Conference, Santa Barbara, 1989. 428--446. Google Scholar

[3] Bellare M, Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, 1993. 62--73. Google Scholar

[4] Bellare M, Rogaway P. Optimal asymmetric encryption. In: Advances in Cryptology — EUROCRYPT'94. Berlin: Springer, 1995. 92--111. Google Scholar

[5] Andreeva E, Mennink B, Preneel B. Open problems in hash function security. Des Codes Cryptogr, 2015, 77: 611-631 CrossRef Google Scholar

[6] Naito Y. Indifferentiability of double-block-length hash function without feed-forward operations. In: Proceedings of the 22nd Australasian Conference on Information Security and Privacy, Auckland, 2017. 38--57. Google Scholar

[7] Bellare M, Boldyreva A, Palacio A. An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: Advances in Cryptology - EUROCRYPT 2004. Berlin: Springer, 2004. 171--188. Google Scholar

[8] Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited (preliminary version). In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, Dallas, Texas, 1998. 209--218. Google Scholar

[9] Canetti R, Goldreich O, Halevi S. On the random-oracle methodology as applied to length-restricted signature schemes. In: Theory of Cryptography, Berlin: Springer, 2004. 40--57. Google Scholar

[10] Maurer U M, Renner R, Holenstein C. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Proceedings of the 1st Theory of Cryptography Conference on Theory of Cryptography, Cambridge, 2004. 21--39. Google Scholar

[11] Coron J, Dodis Y, Malinaud C, et al. Merkle-damgård revisited: how to construct a hash function. In: Proceedings of the 25th Annual International Cryptology Conference, Santa Barbara, 2005. 430--448. Google Scholar

[12] Lee J. Indifferentiability of the Sum of Random Permutations Toward Optimal Security. IEEE Trans Inform Theor, 2017, 63: 4050-4054 CrossRef Google Scholar

[13] Maurer U, Renner R. From indifferentiability to constructive cryptography (and back). In: Proceedings of the 14th International Conference on Theory of Cryptography, Beijing, 2016. 3--24. Google Scholar

[14] Moody D, Paul S, Smith-Tone D. Improved indifferentiability security bound for the JH mode. Des Codes Cryptogr, 2016, 79: 237-259 CrossRef Google Scholar

[15] Bagheri N, Gauravaram P, Knudsen L R. The suffix-free-prefix-free hash function construction and its indifferentiability security analysis. Int J Inf Secur, 2012, 11: 419-434 CrossRef Google Scholar

[16] Chang D, Lee S, Nandi M, et al. Indifferentiable security analysis of popular hash functions with prefix-free padding. In: Proceedings of the 12th international conference on Theory and Application of Cryptology and Information Security, Shanghai, 2006. 283--298. Google Scholar

[17] Chang D, Nandi M. Improved indifferentiability security analysis of chopmd hash function. In: Proceedings of the 15th International Workshop on Fast Software Encryption, Lausanne, 2008. 429--443. Google Scholar

[18] Chang D, Sung J, Hong S, et al. Indifferentiable security analysis of choppfmd, chopmd, a chopmdp, chopwph, chopni, chopemd, chopcs, and chopesh hash domain extensions. IACR Cryptol ePrint Arch, 2008, 2008: 407. Google Scholar

[19] Gong Z, Lai X, Chen K. A synthetic indifferentiability analysis of some block-cipher-based hash functions. Des Codes Cryptogr, 2008, 48: 293-305 CrossRef Google Scholar

[20] Bellare M, Ristenpart T. Multi-property-preserving hash domain extension and the EMD transform. In: Proceedings of the 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, 2006. 299--314. Google Scholar

[21] Hirose S, Park J H, Yun A. A Simple Variant of the Merkle-Damg?rd Scheme with a Permutation. J Cryptol, 2012, 25: 271-309 CrossRef Google Scholar

[22] Hirose S. Sequential hashing with minimum padding. Cryptography, 2018, 2: 11. Google Scholar

[23] Liskov M. Constructing an ideal hash function from weak ideal compression functions. In: Proceedings of the 13th International Workshop on Selected Areas in Cryptography, Montreal, 2006. 358--375. Google Scholar

  •   

    Algorithm 1 is_padding($X$)

    Split the message $X$ to blocks $m_{1}||~m_{2}||~\cdots~||~m_{\ell}||~m_{\ell+1}||~\cdots~||~m_{k}$;

    if ($k$ is odd) then

    Return false;

    else

    $\ell=k$/2;

    end if

    for 1 $\leq~i~\leq~(\ell-2)~$

    if $(m_{\ell+i}~\neq~m_{i})$ then

    Return false;

    else

    if ($m_{\ell-1}$ = $m_{2\ell-1}$) then

    Return true;

    else

    if ($m_{\ell-1}$ $\neq$ $m_{2\ell-1}$) and ($m_{\ell-1}$, $m_{2\ell-1}$) contains a padding bits then

    Return true;

    else

    Return false;

    end if

    end if

    end if

    end for

  •   

    Algorithm 2 find-prefix($X$)

    // Take a message $X$ as input and return $\bot$ or $M'$ such that ${\tt~Pad}\xspace(M)=~{\tt~Pad}\xspace(M')~||~X$;

    Split the message $X$ to blocks such that $X=~m_{1}m_{2}\cdots~m_{i}~m_{i+1}\cdots~m_{t}$; // $m_t$ contains $\langle~M~\rangle=\ell$;

    if ($t$ is odd) then

    Return $\bot$;

    end if

    if ($t~\ge~\ell+1$) then

    Define $M''=m_{t-\ell}~\cdots~m_t$;

    if ($m_1\cdots~m_{t-\ell-1}$) is suffix of $M''$ then

    if ($M''$) is a valid ${\tt~Pad}\xspace_2(M)$ then

    Derive $M$ from ${\tt~Pad}\xspace_2(M)$;

    Compute ${\tt~Pad}\xspace(M)$;

    Derive $M'$ from ${\tt~Pad}\xspace(M)=~{\tt~Pad}\xspace(M')~||~X.$

    Return $M'$;

    else

    Return $\bot$;

    end if

    else

    Return $\bot$;

    end if

    else

    Return $\bot$;

    end if

  •   

    Algorithm 3 Simulator

    ELSIF($x~\in~T_{z}$) Construct a chain $C_{t}$ such that $x$ is the end hash value. typically, $C_{t}$ : $x_{1}$ $\xrightarrow{y_{1}}$ $x_{2}$$\xrightarrow{y_{2}}$ $x_{3}\cdots~\xrightarrow{y_{i}}$ $x$;

    ($x_{1}$= IV) $\land$ (is_Padding($y_{1}y_{2}~\cdots~y_{i}$ $||~y$) more than one chain $C_t$ exist $\mathcal{S}$ aborts; ELSIFexactly one chain $C$ exists Derive message $M$ such that ${\tt~Pad}\xspace(M)=~y_{1}y_{2}\cdots~y_{i}||~y$; $z~\leftarrow~\mathcal{RO}~(M)$;

    $T~=~T~\cup~(x,~y,~z)$;

    return $z$;

    Initialize $T~=~\emptyset$;

    On a new query $(x,y)$ to $\mathcal{S}$, the response is $z$;

    if ($(x,y)~\in~T$) then

    return $z$;ELSIF($x~\notin~T_x~\lor~T_z$)

    $z~\underleftarrow{\$}$ 0,1$^n$; $\hspace~{2cm}$%random string

    if ($z~\in~T_x~\lor~T_z$) then

    bad $\leftarrow$ true;

    $z~\underleftarrow{\$}$ 0,1$^n$ / $T$;

    $T~\leftarrow~T~\cup~(x,~y,~z)$;

    return $z$;

    end if

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1