# Tag Info

14

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 ...

8

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 ...

7

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 ...

6

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 ...

5

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 ...

5

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}+ ... 4 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 ... 4 The question errs precisely at the point when it writes: $$\text{and so }H(x')=y.$$ Problem is: that holds for$x'$matching some garbage$z'$, including$z'=z$, and perhaps other garbage$z'$, but we do not know which garbage (or$z$unless we know$x$), and I see no reason that it holds for$x'$obtained from any garbage$z'$except for trivial$H$; and ... 3 What you (most probably) describe is called a "preimage attack", where the attacker tries to find a message that has a specific hash value. Some related attacks against reduced/weakened versions of SHA-256 are known, but (as far as I know) no such attack was successful against the standard SHA-256 algorithm up to today. So generally, it can be to be ... 2 We don't really know exactly how hard it is to find preimages of most cryptographic hash functions. Even for MD5 it is only "easy" to create collisions, while finding preimages is still considered "hard". That said, we can apply statistical tools to estimate a "worst case", if we assume a random oracle for the hash function. In this case, we need in average ... 2 This problem reduces to a standard preimage attack: if the solution can be found faster than with$2^l$trials, then a full preimage can be found faster than$2^n$. The latter problem is considered difficult for iterated hash functions based on the Miyaguchi-Preneel construction, as the latter is difficult even when the IV is not fixed. 2 For cryptographic hash functions, there are the 3 definitions of collision resistance, (first) preimage resistance and second preimage resistance. Number 3 is collision resistance, and it is quite different than No. 1 and No. 2, which is due to the birthday problem (also see birthday attack). In No. 1 and 2, the resulting hash value is fixed (once directly ... 1 While trying to reverse the 'hash' that was mentioned in one of the comments, I discovered the real problem. In short, the problem of finding the valid garbage is bigger than the problem of finding the input. That is, the procedure is correct, but it makes the problem more difficult than the original. The detailed explanation Suppose you are trying to ... 1 Your basic problem is, that your circuit would require infinite many output bits (to be precise, the garbage is infinite). The input for each gate is 3 bit, and you end up with 3 bit. You can duplicate bits in a circuit (by using it as input to multiple gates), but you can NEVER throw away bits or reduce the circuits information. This means, that the output ... 1 Using the key as the message produces a one-way response. Then if you break the message into 128-bit chunks$m_1$,$m_2$, ... you can use:$k_1 = m_1; r_1 = E(k_1,k_1);k_2 = r_1 \oplus m_2; r_2 = E(k_2,k_2);k_3 = r_2 \oplus m_3; r_3 = E(k_3,k_3);$... 1 Assuming the hash is strong, you will not be able to find a preimage any more easily when you know multiple hashes (whether they use the same function or another). In fact, with some hashes you will be able to derive$H(S||K)$from just$H(S)$and$K\$ (known as the length extension attack), so it can't give you more information. Unless the hash is broken, ...

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