Tag Info

17

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

13

The general justification is several years of cryptographic research in trying to "break" hash functions. As far as I know there is no "proof" that finding pre-images of a hash are hard. It is just assumed to be hard based on the history of effort trying to invert it. A hash function considered secure today may well turn out to be weak tomorrow. This ...

13

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

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

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

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

Cryptographic hash functions (like everything else a traditional computer does) can be described as a set of binary operations, XOR, register rotate, and binary addition being very common. These translate directly to a classic computer science problem known as "binary satisfiability" or SAT. SAT problem has been proven NP-complete. To butcher the definition ...

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

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

6

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}+ ... 6 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 ... 6 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. ... 6 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 ... 5 It sounds like you're pretty much out of luck. Yes, there are a few tricks you could use to speed up a brute force search; for example, if we fix everything other than DWORD 3 of B, we can precompute everything up to round 10 of MD5, and compute what the value of the internal 'b' variable of round 52 of MD5 must be to generate the expected hash; this ... 4 As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function'). Assuming you're asking about onewayness, well, given a single 128 bit value$h(M)$, we obviously cannot uniquely deduce the 1408 bit value$M$. However (hint), let us assume that we can ask for the ... 4 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 ... 4 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 ... 4 You are not asking for a collision but for a preimage. Collision attack: the attacker computes two messages m and m', distinct from each other, such that m and m' hash to the same value. Preimage: the attacker is given a goal (a hash value h) and finds a message m which hashes to h. MD5 is weak for collisions, but not for preimages: no attack method is ... 4 Actually, to the best of our knowledge, it's computationally infeasible. By the terminology what we use when we discuss cryptographical hash functions, you're not asking for a hash collision (which is "find two different messages that hash to the same value"), but instead you're asking for a hash preimage (which is "for this hash value, find a message that ... 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 ... 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 ... 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 ... 3 Short answer: no you can't, MD5 is not that broken. Long answer: if you really need to do that, a laptop i5 is able to try 5 millions of MD5 hashes per second; on average you will have to try 2^32 ~ 4300 millions hashes, so that it will be a matter of minutes on any decent remotely-modern CPU. 3 We know no practically feasible way to do what you ask for, except if the hash X=acf3602b5eb9a2db3e365d3043682faf or the content of the file wczasp.rb was prepared specially to make that possible. Assuming that the content of file wczasp.rb is arbitrary, what is asked would be a preimage attack. This is further sub-classified as first preimage if only the ... 3 I have ask as part of my answer, "What problem are you trying to solve?" Do you want a secure unkeyed hash function? If you do, then there are plenty of them around. Even some of the ones that are broken for some uses might be okay for yours (SHA-1 springs to mind -- note the discussion above on HMAC and how broken a hash function has to be). But really, ... 3 Restrict to$n=1$. Let$M$and$M'$be two 1408-bit messages differing in the last 128 bits. What's$h(M)\oplus h(M')$? Can a function$h$with this property be one-way? 3 If we use$H_1(X) = H_0(X) \oplus firstnbits(X)$, this would seem to be trivial. EDIT: As Cédric Van Rompay pointed out, this is only a counterexample if$H_1$winds up being preimage-resistant. This may not be a necessary consequence of$H_0\$ being preimage-resistant, but I really only need one case where it is.

3

As far as we know, SHA512 acts like a random function. So, the only way we know to find a preimage whose hash starts with 0x12345678, is to go through distinct preimages, and hash each one until we find one that starts with 0x12345678. If the output of SHA512 is equidistributed (and we have no reason to believe it isn't), then the probability of any hash ...

2

Your idea is equivalent to doing "constant folding" or "partial compilation". It's not likely to make much difference (see below for detailed explanation). But, even setting that aside, there's a more significant reason why you're not gonna be able to find B. In your situation, the unknown part (B) is 4 DWORDs long, i.e., 128 bits long. This means that ...

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

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