83
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 ...
51
how can for example SHA-256 be unique if there is only a limited number of them?!
Where your issue occurs is that they're not unique. It's just very improbable that they'll reoccur. Unique in this context is not a mathematical definition, it's a humanist one.
In terms of human numbers, $ 2^{256} $ = ...
51
This answer is based on the work by AleksanderRas, although my conclusion is different.
First, to lay out a definition, a hash is a function that takes an arbitrary length input to a fixed length output. For example, MD5 takes any input and produces a 128 bit output.
A cryptographic hash is a hash function which has certain additional security properties. ...
35
The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions.
All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of ...
33
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 ...
32
That depends on what you want to use the hash function for.
For signing documents, sha2 (e. g. sha512) is considered secure.
For storing passwords, you should use one of the algorithms dedicated for this purpose: e. g. bcrypt, sha512crypt or scrypt. In order to slow down an attacker, these algorithms apply the hash functions many times with an input that ...
32
I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.
There is no published preimage attack on MD5 that is cheaper than a generic attack on any 128-bit hash function. But you shouldn't rely ...
31
Yes, there are currently no known attacks on HMAC-MD5.
In particular, after the first collision attacks on MD5, Mihir Bellare (one of the inventors of HMAC) came up with a new security proof for HMAC that doesn't require collision resistance:
"Abstract: HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming that (1) the underlying ...
30
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).
(...
30
Just to show you how easy it is today to create collisions on MD5:
One could create collisions using Marc Steven's HashClash on
AWS and estimated the the cost of around $0.65 per collision.
These 2 images have the same md5 hash: 253dd04e87492e4fc3471de5e776bc3d
If you want to test it yourself and the images below do not give you the MD5 hash ...
29
You are right, hashes won't be all unique as you already have shown. The important part are practical collisions - how many SHA-512 hashes can the whole earth generate in its lifetime? Definitely much less than $2^{512}$, it's even less than $2^{128}$.
Let's guess unrealistically high and say we generate these $2^{128}$ hashes from perfectly random input, ...
26
MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992).
The main structural differences are the following:
SHA-1 has a larger state: 160 bits vs 128 bits.
SHA-1 has more rounds: 80 vs 64.
SHA-1 rounds have an ...
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 ...
answered Jul 26 '17 at 14:52
Squeamish Ossifrage
38.2k2 gold badges74 silver badges160 bronze badges
22
The answer is 1 bit (Hamming-distance = 1) for any cryptographic hash algorithm.
There are definitely collisions, since the digest of the MD5 algorithm is always 128 bits long but there are more than 2128 possible inputs.
We can explain this due to the Pigeonhole principle.
Mathematical explanation
Let's say we take an input message of 3 bits:
There are ...
20
Two different strings in hex format:
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2
both have MD5 hash:
008ee33a9d58b51cfeb425b0959121c9
Example:
...
20
Does hashing algorithms have an upper bound in the input space?
They can, but they don't have to and it depends on their specification.
All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of ...
19
MD5 is ok here as usual cryptographic attacks do not apply in this scenario.
The probability of accidental MD5 collision is much less than usual probability for soft error. For details read more.
MD5 is currently considered too weak to work as a cryptographic hash. However, for all traditional (i.e. non-cryptographic) hash uses MD5 is often perfectly fine.
...
19
There is an important misconception on your part: in general cryptographic hashes such as MD5, SHA-1 or SHA-512 should not be used to directly hash a password. A password hash or PBKDF should be used. Examples are PBKDF2, bcrypt, scrypt and Argon2. These functions also take a salt and work factor to provide additional protection.
There are a few problems ...
17
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/
17
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 ...
16
Right now, the best published attack against MD5's preimage resistance (first preimage, actually, but it applies to second preimage resistance as well) finds preimages in cost $2^{123.4}$ average cost, which is slightly better than the generic attack (average cost of $2^{128}$), but still way beyond the technologically feasible. The attack rebuilds the ...
16
There are two answers to this: one practical, and one theoretical.
First, the practical one: MD5 is a broken hash function, and we know of collisions for it, and a quick web search turned up a collision with a hamming distance of 6.
Second, the theoretical one: Most cryptographic hash functions are designed to be a reasonable approximation of a random ...
15
Among the options for a replacement of MD5 as a hash function:
If at all possible, you should increase the width of the hash for strong collision resistance, and use an at-least-256 bit member of the SHA-2, or perhaps the new SHA-3 family. The collision resistance of any 128-bit hash can be broken by educated brute force and about $2^{65}$ hashes (which is ...
14
The algorithm (now reasonably clear) is reminiscent of a block cipher in CFB mode, with $random$ as the IV (which can be public), $secret$ as the key, and MD5 used as keystream generator instead of the block cipher.
Decryption works as in CFB:
\begin{align*}
M_1 &= C_1 \oplus \operatorname{MD5}( secret\mathbin\|random )\\
M_n &= C_n \oplus \...
14
The echo command appends a new line at the end, by default. The -n option omits this character. Compare these two executions:
> echo -n "test123" | md5sum
cc03e747a6afbbcbf8be7668acfebee5
> echo "test123" | md5sum
4a251a2ef9bbf4ccc35f97aba2c9cbda
So the difference between the hash values is simply caused by the new line character.
14
There is no timing attack possible on MD5 as practically implemented on most platforms. That's because MD5 uses only 32-bit addition, 32-bit bitwise boolean operators, and constant rotations/shifts, which exhibit no data-dependent timing for any reasonable implementation, even written without consideration for resistance to timing attacks.
There is however ...
14
Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1.
The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value. We can do this by using Joux's idea of forming finding ...
13
The risk of collision is only theoretical; it will not happen in practice.
Except in one particular instance. The description given implies that this system is going to be some form of de-duplicating filesystem or backup system. For most users, the collision risk is tiny.
But, for one particular class of users, there is a much larger risk. Those users ...
13
MD5 – Can I use MD5 as a two-way function? If I can break the data in 64 bit portions, will I be able to recover the original message without a pre-calculated lookup table?
MD5 is a hash function, not a cipher. Differently stated: you will not be able to encrypt or decrypt anything by simply using a hash function.
You could compare MD5 hashes with each ...
Only top voted, non community-wiki answers of a minimum length are eligible
