52
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. ...
37
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 ...
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 ...
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
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 ...
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 ...
answered Apr 25 '19 at 14:01
Squeamish Ossifrage
41.2k3 gold badges79 silver badges167 bronze badges
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, ...
28
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
41.2k3 gold badges79 silver badges167 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 8 ...
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
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 ...
15
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 ...
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
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 ...
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
The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like ...
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
TO understand what is going on, you have to consider how MD5 works and how the collision attack works.
MD5 is a Merkle-Damgård hash function: it process the input data by blocks (of 64 bytes each), with a "running state" of 128 bits. So there is an internal function $f$ that takes as inputs the current state $s$ and the next message block $m$, and outputs ...
12
An important aspect of cryptographic hash functions is that even the smallest difference in input usually results in different output. But given the unlimited input space compared to the limited output space of the cryptographic hash it is likely that sequences with only small differences (like a single bit) but the same hash value exist.
But for a more ...
Only top voted, non community-wiki answers of a minimum length are eligible
