Tag Info

Hot answers tagged

47

The risk of collision is only theoretical; it will not happen in practice. Time spent worrying about such a risk of collision is time wasted. Consider that even if you have $2^{90}$ 1MB blocks (that's a billion of billions of billions of blocks -- stored on 1TB hard disks, the disks would make a pile as large of the USA and several kilometers high), risks of ...


21

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks. There are no known collisions in SHA-1. Still we call collision resistance of SHA-1 is broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to ...


16

As a general rule, you should avoid SHA1 for new applications and instead go with one of the hash functions from the SHA-2 family. As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, ...


15

No. The wikipedia article is in my honest opinion misrepresenting this article on a reduced round attack on the SHA-2 family of hashes. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family. In other words, no collisions have been found in any of the SHA-2 hashes. The ...


12

What you want is called a chosen prefix collision. Given p1, p2 you want to find m1, m2 such that hash(p1 || m1) = hash(p2 || m2). Generic attack The generic attack to find this, is creating messages starting with p1 and just as many starting with p2. Thanks to the birthday problem you'll find a match after around 2n/2 messages. For a 128 bit hash like ...


12

Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even). However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string. First, let's look on the positive side. A good ...


11

In short, no. So, what is the current state of cryptanalysis with SHA-1 (for reference only as this question relates to SHA-2) and SHA-2? Bruce Schneier has declared SHA-1 broken. That is because researchers found a way to break full SHA-1 in $2^{69}$ operations. Much less than the $2^{80}$ operations it should take to find a collision due to the birthday ...


10

Well, first of all, you need to be clear about the meanings of various cryptographical primitives. Cryptographic hash function; this is a function that takes an input string, and generates a hash. The idea is that we don't know how to create two input strings with the same hash, and so the hash can be used as a replacement for the original string. Now, ...


10

I would recommend phasing out SHA-1 in any scenario where collision-resistance of a hash is required, for there is a wide consensus that an attack with $2^{69}$ complexity would work, it would already be feasible by a resourceful entity, and attacks only get better. I'm still confident that SHA-1 is preimage and second-preimage resistant for all practical ...


9

A new result shows how to generate single block MD5 collisions, including an example collision: Message 1 Message 2 > md5sum message1.bin message2.bin > 008ee33a9d58b51cfeb425b0959121c9 message1.bin > 008ee33a9d58b51cfeb425b0959121c9 message2.bin There is an earlier example of a single block collision but not technique for generating it was ...


9

MD5 was intended to be a cryptographic hash function, and one of the useful properties for such a function is its collision-resistance. Ideally, it should take work comparable to around $2^{64}$ tries (as the output size is $128$ bits, i.e. there are $2^{128}$ different possible values) to find a collision (two different inputs hashing to the same output). ...


9

1640 is a huge number. For instance, if you consider each torrent to consist in a single byte each (so they are quite uninteresting torrents), and you pack them all on 10 TB hard disks (for a torrent to exist, it must exist on at least one hard disk on the planet), and if each such disk weighs about 100g, then the total weight of the disks is about 24 ...


9

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


9

The short answer is: technically, no. The weaknesses of MD5 are not an issue here. However MD5 is seriously inappropriate, for it is the wrong king of security primitive; also its reputation is tarnished. If a collision attack was to be feared, then using MD5 would be a disaster, for it is now hopelessly broken w.r.t. to collision resistance; but that does ...


9

echo -n "06b2f82fd81b2c20" | sha1sum e42d65afd2bc126a2e8e609257287084c43fc06a echo -n "02c60cb75083ceef" | sha1sum e42d65afd277988908c01bc539c9d71aff728322 Notice the first ten characters of the SHA1 hash match, indicating a 40-bit match. Other pairs are 0534164decf1166c, 06670357183cba13 and 0addd115537e4b39, 09a3cbdd0d00773b. Note that I am ...


9

No, in general, there will always be a pair of inputs that will collide for both hash functions. Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $X$ and $Y$ with $X \neq Y$, $A(X) = A(Y)$ and $B(X) = B(Y)$ Here is a simple ...


9

First of all, if your goal is to keep the garbled messages to "once every hundred years", well, you already don't meet that goal, even before the change. With an 8 bit CRC, a random change has a probability 1/256 of being accepted; hence if your wireless network has a transmission error at least once every three months (which, to me, sounds like an ...


8

A collision is between two values. If you take a random pair of values you get a 1/2n chance of having a collision. With 2n/2 values you have about 2n-1 pairs, so you could expect about 1/2 chance of collision. (That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)


8

First of all, I think I want to correct you at one point; in step 2, you aren't actually that interested in whether the operation is commutative, what you're actually interested in is that the operation is associative, that is, if $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. In essence, your operator $\oplus$ in step 2 turns out to be a group operation. ...


8

First things first: there is nothing magical in hexadecimal. The output of MD5 is, nominally, a sequence of 128 bits, or, if you prefer, 16 bytes (each being able to get any value between 0 and 255). Hexadecimal is just a trick to represent a single byte as two characters in a limited range (digits, and letters from 'a' to 'f'). If you can have 30 characters ...


8

The general idea is that either one of the inner hashes, or the combining hash must collide, since there is not other place to introduce the collision. Assume we found a collision for H. This means we have X, Y with $X \neq Y$ such that: $h(h(X_0)||h(X_1)) = h(h(Y_0)||h(Y_1))$ Now we define: $A = h(X_0)||h(X_1)$ and $B = h(Y_0)||h(Y_1)$ This gives us a ...


8

The chance of a collision in such a set is approximately $ \frac{1/2 \cdot n^2}{2^{160}} $, which for n=100k evaluates to about $ 3.4 \cdot 10^{-39} $. So it is fair to say, such a collision won't occur accidentially. AFAIK nobody has every found a SHA-1 collision. Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes. If ...


8

Password strength is typically measured in bits of entropy, or in layman's terms, the amount of "true randomness" in the system. This is measured by the process of how the password is generated rather than by the number of bits in the output. It's a simple extension of Kerckhoff's principle: assume your attacker knows your process, and the only information ...


8

After spending more than two weeks reading well over 750 pages while checking the following documents… "Sponge Functions" http://sponge.noekeon.org/SpongeFunctions.pdf "Cryptographic sponge functions" http://sponge.noekeon.org/CSF-0.1.pdf "Security Analysis of Extended Sponge Functions" ...


8

The answer to your edited question is "yes, it is possible". As a trivial example, let $H$ be an ideal $k$-bit hash function. Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations. Denote ...


7

Here are some other interesting examples. One of them is, two downloadable executables that have the same MD5 hash, but are actually different, and produce different (safe) results when run! So much for using MD5 hashes to ensure download file integrity :-( http://www.mscs.dal.ca/~selinger/md5collision/


7

The hand-waving argument goes thus: when you accumulate $n$ hash outputs, you are actually producing $n^3/6$ triplets, each of them having probability $t^{-2}$ to be a three-way collision (where $t = |T|$, i.e. the size of the output space). So you should expect the first three-way collision to appear when $n^3/6 = t^2$, i.e. $n = 6·t^{2/3}$. For a perfect ...


7

Denote the internal sponge state by $$ S = R||C, $$ where C has size c -- capacity. Every iteration a message block of length $|R|$ is xored into $R$ and then the permutation $P$ is applied. Therefore, if we obtain a collision in $C$ (which can be obtained in $2^{c/2}$ steps with the basic birthday attack), we could cancel any difference in $R$ by injecting ...


7

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



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