Tag Info

Hot answers tagged

61

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


17

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


16

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


16

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


15

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


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.


13

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: $$M_1 = C_1 \oplus \operatorname{MD5}( secret||random )$$ $$M_n = C_n \oplus \operatorname{MD5}( secret||C_{n-1} ...


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

Two different strings in hex format: 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 both have MD5 hash: 008ee33a9d58b51cfeb425b0959121c9 ...


11

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/


11

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


11

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


11

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


10

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


10

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


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

No, there are expressions relating input values which demonstrate extremely strong correlations between output bits. The output bits of of MD5 are not independent, particularly if the party supplying the input to MD5 chooses for them not to be. These correlations are sufficiently powerful to enable the generation of completely identical output values ...


8

It's not clear from your decryption what the algorithm is used for. But you should be aware that while at first glance it provides privacy : it's a weird mode CFB with md5 used as a block cipher ; it doesn't provide authenticity. A simple bit flip of the ciphertext will result in the corresponding bit being flipped in the plaintext and such a bit flip ...


8

Any time there is a choice and password search is an issue, one should prefer scrypt or perhaps bcrypt to stretched-md5, or even PBKDF2. The reason is that scrypt and bcrypt provide better security, by requiring a bigger investment in hardware (in particular, RAM) for the would-be password cracker, assuming parametrization yielding the same runtime for ...


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

For the smallest in theory based on a heuristic argument, see this other answer. For two concrete examples with 512-bit messages, much more than minimum but half the size of the example linked to in the question 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 and the ...


8

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


7

The reason we, at the end of the compression function, add the input to the compression function, well, that's because otherwise the compression function would be invertible, and that would be bad. Without that final step, the compression function would be invertible in this sense: given a desired compression function output and a message block, we would be ...


7

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


7

It's called padding. MD5 fills the "not finished block" with exactly one "1" bit and a number of "0" bits until the length of the number is 64 bits away from being divisible be 512. It could happen that you don't need to add any "0" bits, that's okay, but never omit the "1" bit! After that, the length of the original message in bits is added, formatted with ...


7

Summary: a single HMAC-MD5 with a key later revealed is a completely insecure way to do commitments of messages that can be chosen malignantly, because of the ease with which MD5 collisions can now be found. There is no compelling evidence that's so insecure for messages constrained to belong in a small arbitrary set that no adversary can choose or ...


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

"Stochastically independent bits in an MD5 output" must be stated with some definition of what enters MD5. It is trivial to generate, by trial and error, MD5 inputs that generate MD5 output which right two bits are equal (hash incremental inputs, keep the ones matching that condition). A more appropriate rephrasing of the question would be: is an adversary ...


6

To have approximately a 50% chance of a collision, you'd need $2^{128}$ data blocks. This comes from the birthday problem. Are you anticipating your list to be that large? I would doubt it as that would be an astronomical amount of data (much, much more than a petabyte). That said, it is very, very unlikely that a collision for MD5 would also be a collision ...



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