38

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction ...


36

Preimage resistance is about the most basic property of a hash function which can be thought. It means: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$. (Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash ...


30

What you're missing is the fact that multiple logic gates can share the same input(s). So you can't look at each logic gate individually and "reverse" the entire circuit that way, because choosing the inputs of a logic gate may constrain the outputs of other logic gates (so not all possible choices of input for any logic gate will work, only some will). So ...


26

If you follow the reference for the alleged preimage attack on MD5, you will see that although the time cost is $2^{123.4}$ steps, the memory cost is $2^{45} \times 11$ words of memory, which has a far higher area*time cost than a smart attacker would use—a smart attacker would fit 32 CPU cores or MD5 circuits in parallel into much less die area and get an ...


23

A cryptographic hash function $f : \{0,1\}^{*} \to \{0,1\}^n$ has three properties: (1) preimage resistance, (2) second-preimage resistance, and (3) collision resistance. Even further, these properties form a hierarchy where each property implies the one before it, i.e., a collision-resistant function is also second-preimage resistant, and a second-preimage ...


23

Does this bias the hash in any way? We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others. My assumption is this would decrease the computational power needed to ...


19

It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core. Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker ...


18

The Bitcoin mining algorithm can not be simplified by exploiting any weakness in the SHA-2 hashing algorithm with the current state of the art. The problem is manyfold. From the SHA-256 point of view, there is no (partial) preimage search algorithm that applies to the full hash function. Even worse, the attacks that penetrate a fewer number of rounds have ...


18

With all well-regarded hash functions, the bits of the hash all have equal worth: as far as anyone knows (unless they aren't telling), the bits are not correlated. If you take $k$ bits of an $n$-bit hash, you get a $k$-bit hash function. Truncating SHA-256 to 255 bits gives you a hash that's almost as good as SHA-256: it has $2^{255}$ strength against ...


17

With any $n$ bit hash it is possible to: Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's ...


16

The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure. A little deeper; Compression function: transforms $2n$-bit input into $n$-bit. The transformation ...


13

Let me try to elaborate on their proof. Suppose you had a hash function $H$ that was second-preimage resistant but not first-preimage resistant. By showing that this leads to a contradiction, we will be showing that with second-preimage resistance, you must have first-preimage resistance. Namely, we will show that the lack of first-preimage resistance is ...


11

It is neither pre-image resistant, second pre-image resistant nor collision resistant. It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time). If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently easy,...


10

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by ...


10

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions. For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$ This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that ...


9

Consider the function $H$ transforming a message $m$ to the SHA-512 hash of the first 1024 bits of $m$ (right-padded with $1024-n$ zero bits if the bit length $n$ of $m$ is less than 1024). $H$ is first-preimage resistant, but not second-preimage resistant: once you have a first preimage $m_1$, it is trivial to get another $m_2$ with the same hash (e.g. ...


8

In their paper Second Preimages on $n$-Bit Hash Functions for Much Less than $2^n$ Work, Kelsey and Schneier provide: a second preimage attack on all $n$-bit iterated hash functions with Damgard-Merkle strengthening and $n$-bit intermediate states, allowing a second preimage to be found for a $2^k$-message-block message with about $k\times2^{n/2+1}+ 2^{n-...


8

Take $C_2$ and pick any $k_2$. Then decrypt using $k_2$ so that $M_2 = AES_{k_2}^{-1}(C_2)$. Now obviously we have $AES_{k_2}(M_2) = C_2 = C_1$. This extends to any blockcipher, because blockciphers are specifically designed to be reversible. In the comments you asked about the scenario where $M_2$ is also fixed. This is as hard as breaking AES. Consider ...


8

This relation obviously doesn't hold. If you define "break" as faster than what's expected of an ideal hash function Define TrivialCollisionHash = GoodHash(input.Skip(1 bit)). Finding pre-images for this is just as hard as for GoodHash, i.e. $2^n$. Finding a collision is trivial, just flip the first bit. If you define "break" as faster than a certain ...


8

A collision attack is the ability to find two inputs that produce the same result, but that result is not known ahead of time. In a typical case (e.g., the attack on MD5) only a relatively small number of specific inputs are known to produce collisions. Collision resistance obviously means that a collision attack is difficult (for some definition of "...


8

Yes, it has happened. If you look at the SHA3 hash zoo, there are a number of hashes who has the best attack listed as "2nd preimage". One general place this can occur is if you have a hash function with a weak message compression step, but a fairly strong finalization step. Here, we might not be able to generate first preimages (because we don't know what ...


8

The best way to approach problems like this is to start by assuming that a simple solution exists. That assumption might be wrong, of course, but: since this is a textbook problem, it probably does have a relatively simple solution that you should be able to figure out based on what you've learned, and even if that wasn't the case, you should still at ...


7

If the hash function is any good, then it should behave as a "random function" (i.e. a function chosen randomly and uniformly among all possible functions). For a random function with output size $n$ bits, it is expected that nested application will follow a "rho" pattern: the sequence of successive values ultimately enters a cycle with an expected size of $...


7

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer ...


7

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s): In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt e\...


7

Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2. To see why, it's worth looking at how the MD5 hash (...


7

In both mathematics and cryptography, given a function $H$ from set $A$ to set $B$, and an element $b$ in $B$, a preimage of $b$ by $H$ is any $a$ in $A$ such that $H(a)=b$. In cryptography, a public function $H$ from set $A$ to finite set $B$ is: First-preimage-resistant when for a given random $b$ in $B$, it is hard to exhibit a preimage of $b$, that is, ...


7

$\newcommand{\xs}{\xleftarrow\$}\newcommand{\mc}{\mathcal}$ There is a paper from 2004 (last revised 2009) by Rogaway and Shrimpton "Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" which talks about this very topic (among others). I shall use it as ...


6

Often the hash (iterated and salted mostly) of a password is saved in a database, instead of the password. If a user logs in, the hash is computed and compared against the stored hash value. This way a user that can see the database of hashes does not see the password directly, but this property depends crucially on the hash being resistant to a pre-image ...


Only top voted, non community-wiki answers of a minimum length are eligible