Suppose two parties have hash functions $h_1$ and $h_2$ respectively, but each only trusts the security of their own. We wish to build a hash combiner $C^{h_1, h_2}$ which is secure so long as either one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08)...

Given $2n$-to-$n$ compression functions $h_1,h_2,h_3$, we build a new $5n$-to-$n$ compression function $\mathrm{T}_5$, using only $3$ compression calls: $\mathrm{T}_5(m_1, m_2, m_3, m_4, m_5) := h_3( h_1(m_1, m_2)\oplus m_5, h_2(m_3, m_4)\oplus m_5) \oplus m_5$. We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In...

Auxiliary-input (AI) idealized models, such as auxiliary-input random oracle model (AI-ROM) and auxiliary-input random permutation model (AI-PRM), play a critical role in assessing non-uniform security of symmetric key and hash function constructions. However, obtaining security bounds in these models is often much more challenging. The presampling technique, initially introduced by Unruh (CRYPTO' 07) for AI-ROM and later exported to several other models by Coretti et al. (EUROCRYPT' 18)....

The ZK-STARK technology, published by Ben-Sasson et al. in ePrint 2018/046 is hailed by many as being a viable, efficient solution to the scaling problem of cryptocurrencies. In essence, a ZK-STARK proof uses a Merkle-tree to compress the data that needs to be verified, thus greatly reduces the communication overhead between the prover and the verifier. We propose MARVELlous a family of cryptographic algorithms specifically designed for STARK efficiency. The family currently includes the...

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary's queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this ``recording barrier''. ...

The random-permutation model (RPM) and the ideal-cipher model (ICM) are idealized models that offer a simple and intuitive way to assess the conjectured standard-model security of many important symmetric-key and hash-function constructions. Similarly, the generic-group model (GGM) captures generic algorithms against assumptions in cyclic groups by modeling encodings of group elements as random injections and allows to derive simple bounds on the advantage of such...

We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker $A$ can compute arbitrary $S$ bits of leakage about the random oracle $\mathcal O$ before attacking the system and then use additional $T$ oracle queries to $\mathcal O$ during the attack. This model has natural applications in settings where traditional random-oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against...

Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression...

M3lcrypt (canonical M3lcryptH) is a password based key derivation function built around the Merkle-Damgard hash function H. It supports large [pseudo]random salt values (>= 128-bit) and password lengths.

To examine the integrity and authenticity of an IP address efficiently and economically, this paper proposes a new non-Merkle-Damgard structural (non-MDS) hash function called JUNA that is based on a multivariate permutation problem and an anomalous subset product problem to which no subexponential time solutions are found so far. JUNA includes an initialization algorithm and a compression algorithm, and converts a short message of n bits which is regarded as only one block into a digest of...

In this note we show a consequence of the recent observation that narrow-pipe hash designs manifest an abberation from ideal random functions for finding collisions for those functions with complexities much lower than the so called generic birthday paradox lower bound. The problem is generic for narrow-pipe designs including classic Merkle-Damgard designs but also recent narrow-pipe SHA-3 candidates. Our finding does not reduces the generic collision security of n/2 bits that narrow-pipe...

Abstract. The new hash function DIHA2 (Dynamic Input Hash Algorithm)is with the structure of Merkle-Damgard and is based on 64-bit computing.It oper- ates each 1024-bit block and outputts a 256-bit hash-value. For a 64-bit sub-block X[j](0 &#8804; j &#8804; 15) of each step, DIHA2 gets a dynamic mapping value of TLU (table look up,The table was 256-Byte only)and add it to operation of variables a, b, c, d,so as to eliminate the differential effect.At the same time DIHA2 sets 3 assistant...

Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgard transform applied to a corresponding compression function. Moreover, it is well known that the resulting ``structured'' hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory...

Since the Merkle-Damgård (MD) type hash functions are differentiable from ROs even when compression functions are modeled by ideal primitives, there is no guarantee as to the security of cryptosystems when ROs are instantiated with structural hash functions. In this paper, we study the security of the instantiated cryptosystems whereas the hash functions have the well known structure of Merkle-Damgård construction with Stam's type-II compression function (denoted MD-TypeII) in the Ideal...

We present Vortex a new family of one way hash functions that can produce message digests of 224, 256, 384 and 512 bits. The main idea behind the design of these hash functions is that we use well known algorithms that can support very fast diffusion in a small number of steps. We also balance the cryptographic strength that comes from iterating block cipher rounds with SBox substitution and diffusion (like Whirlpool) against the need to have a lightweight implementation with as small number...

Generally speaking, the probability of a differential path determines an upper bound for the expected workload and thus for the true risk potential of a differential attack. In particular, if the expected workload seems to be in a borderline region between practical feasibility and non-feasibility it is desirable to know the path probability as exact as possible. We present a generally applicable approach to determine at least almost exact probabilities of differential paths where we focus...

The goal of this paper is to analyze the security of dithered variants of the Merkle-Damgard mode of operation that use a third input to indicate the position of a block in the message to be hashed. These modes of operation for hash functions have been proposed to avoid some structural weaknesses of the Merkle-Damgard paradigm, e.g. that second preimages can be constructed in much less than $2^n$ work, as pointed out by Kelsey and Schneier. Among the modes of operation that use such a...

Since the seminal works of Merkle and Damgard on the iteration of compression functions, hash functions were built from compression functions using the Merkle-Damgard construction. Recently, several flaws in this construction were identified, allowing for pre-image attacks and second pre-image attacks on such hash functions even when the underlying compression functions are secure. In this paper we propose the HAsh Iterative FrAmework (HAIFA). Our framework can fix many of the flaws while...

Nearly all modern hash functions are constructed by iterating a compression function. At FSE'04, Rogaway and Shrimpton [RS04] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study...

Preneel, Govaerts, and Vandewalle[14](PGV) considered 64 most basic ways to construct a hash function from a block cipher, and regarded 12 of those 64 schemes as secure. Black, Pogaway and Shrimpton[3](BRS) provided a formal and quantitative treatment of those 64 constructions and proved that, in black-box model, the 12 schemes ( group-1 ) that PGV singled out as secure really are secure. By step ping outside of the Merkle-Damgard[4] approach to analysis, an additional 8 (group-2) of the 64...

We point out that the seemingly strong pseudorandom oracle preserving (PRO-Pr) property of hash function domain-extension transforms defined and implemented by Coron et. al. [12] can actually weaken our guarantees on the hash function, in particular producing a hash function that fails to be even collision-resistant (CR) even though the compression function to which the transform is applied is CR. Not only is this true in general, but we show that all the transforms presented in [12] have...

There is a rarely mentioned foundational problem involving collision-resistant hash-functions: common constructions are keyless, but formal definitions are keyed. The discrepancy stems from the fact that a function H:{0,1}^* -> {0,1}^n always admits an efficient collision-finding algorithm, it's just that us human beings might be unable to write the program down. We explain a simple way to sidestep this difficulty that avoids having to key our hash functions. The idea is to state theorems...

Preneel, Govaerts, and Vandewalle[12] considered the 64 most basic ways to construct a hash function from a block cipher, and regarded 12 of these 64 schemes as secure. Black, Pogaway and Shrimpton[3] proved that, in black-box model, the 12 schemes that PGV singled out as secure really are secure and given tight upper and lower bounds on their collision resistance. And also they pointed out, by stepping outside of the Merkle-Damgard[5] approach to analysis, an additional 8 of the 64 schemes...

We propose a new cryptographic construction called 3C, which works as a pseudorandom function (PRF), message authentication code (MAC) and cryptographic hash function. The 3C-construction is obtained by modifying the Merkle-Damgard iterated construction used to construct iterated hash functions. We assume that the compression functions of Merkle-Damgard iterated construction realize a family of fixed-length-input pseudorandom functions (FI-PRFs). A concrete security analysis for the family...

Joux and Wang's multicollision attack has yielded collisions for several one-way hash algorithms. Of these, MD5 is the most problematic due to its heavy deployment, but there exists a perception that the flaws identified have no applied implications. We show that the appendability of Merkle-Damgard allows us to add any payload to the proof-of-concept hashes released by Wang et al. We then demonstrate a tool, Stripwire, that uses this capability to create two files -- one which executes an...

Preneel, Govaerts, and Vandewalle considered the 64 most basic ways to construct a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$ from a block cipher $E:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n$. They regarded 12 of these 64 schemes as secure, though no proofs or formal claims were given. The remaining 52 schemes were shown to be subject to various attacks. Here we provide a formal and quantitative treatment of the 64 constructions considered by PGV. We prove that, in a black-box model,...

In this paper, we study several issues related to the notion of ``secure'' hash functions. Several necessary conditions are considered, as well as a popular sufficient condition (the so-called random oracle model). We study the security of various problems that are motivated by the notion of a secure hash function. These problems are analyzed in the random oracle model, and we prove that the obvious trivial algorithms are optimal. As well, we look closely at reductions between various...

Recent attacks on the cryptographic hash functions MD4 and MD5 make it clear that (strong) collision-resistance is a hard-to-achieve goal. We look towards a weaker notion, the <i>universal one-way hash functions</i> (UOWHFs) of Naor and Yung, and investigate their practical potential. The goal is to build UOWHFs not based on number theoretic assumptions, but from the primitives underlying current cryptographic hash functions like MD5 and SHA. Pursuing this goal leads us to new questions....