Tag Info

Hot answers tagged

48

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


25

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


17

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

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


12

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


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

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


10

If you want to use Skein (one of the SHA-3 candidates) anyway: it has a "mode of operation" (configuration variant) for tree hashing, which works just like your method 2. It does this internally of the operation, as multiple calls of UBI on the individual blocks. This is described in section 3.5.6 of the Skein specification paper (version 1.3). You will ...


10

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


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


10

To answer your question, we must first state that for an integer $x$, we define MD5($x$) to be the MD5 hash of the encoding of $x$ as a sequence of bits. Indeed, MD5 expects a sequence of bits as input, not an integer. We should choose a conventional encoding; I select big-endian. Thus, integer $44$ encodes as a sequence of 6 bits: 101100. One may note that ...


9

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


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

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

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

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


9

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


8

Actually a tree-based hashing as you describe it (your method 2) somewhat lowers resistance to second preimages. For a hash function with a n-bit output, we expect resistance to: collisions up to 2n/2 effort, second preimages up to 2n, preimages up to 2n. "Effort" is here measured in number of invocations of the hash function on a short, "elementary" ...


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

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/


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

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

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



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