Tag Info

46

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

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

10

MD5, like other hash functions, uses the Merkle-Damgard construction. You take the message and break it up into fixed-size blocks. You start with an intialization vector (IV), which you feed into a compression function along with the first block. Take the output (it will be the same length as the IV), and feed it into the compression function along with the ...

10

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

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

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

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

8

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

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

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

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

7

The Merkle–Damgård hash construction customarily pads the message $M$ to be hashed with a single bit set to 1, a minimal number of bit(s) set to 0, and the representation of the length of the message in binary over some fixed number of bits. The padded message is then formed of a number of blocks $B_i$. The hash is computed by repeatedly applying a ...

7

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

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

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

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/

6

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

6

Among the options for a replacement of MD5 as a hash function: (Updated) A candidate worth examination is RIPEMD-128, a pin-compatible replacement of MD5, with a name. RIPEMD-128 uses the same security argument as RIPEMD-160 (though with 4 groups of rounds instead of 5). RIPEMD-160 in turn is AFAIK the single standard unbroken 160-bit hash, and has enjoyed ...

6

If MD5 is used to hash "something like patient name or SSN or some unique personal identifier" in order to "ensure that a multiple prescriptions of the same patient (as identified by the personal identifier) are linked to each other, without revealing the identifier itself", then that solution is technically imperfect, but not for reasons related to ...

6

EDIT: The following block of text (between the lines) was written as an answer to the original question, which did not explicitly state that the secret was used for any blocks after the initial one. Hmmm, I assume that the goal of this algorithm is to provide privacy; that is, to create an encrypted message, and someone that hears this encrypted message ...

6

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

6

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

6

Not really. Finding distinct $m_1, m_2$ such that $H(m_1) = H(m_2)$ is a different problem than finding $m_1, d$ such that $H(m_1) = d$. If the first problem is hard it's called collision resistance, if the second problem is hard it's called preimage resistance. MD5's collision resistance is practically broken - it's quite easy to generate a pair of $m_1, ... 6 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 ... 5 What you're suggesting is likely good enough, and very likely far more secure than just about any other lock on your house. If the only hash function you can find is MD5, go with it, but make sure to HMAC with the passphrase as the key. Again, it's not going to be the weak point of your security. I'm sure I could pick the lock on your front door faster than ... 5 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 ... 5 The short answer is no. The scheme gives poor protection against collisions, that is inputs detected as having the same content (within order) when they have not. As noted in the question, this can occur when entries in an input are duplicated; e.g. ("O","X","O") and ("X") collide. This can also occur for maliciously crafted entries. For a start, MD5 is ... 5 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