# Tag Info

40

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

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

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

7

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

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

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

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

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

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

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

5

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

5

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

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

It sounds like you're pretty much out of luck. Yes, there are a few tricks you could use to speed up a brute force search; for example, if we fix everything other than DWORD 3 of B, we can precompute everything up to round 10 of MD5, and compute what the value of the internal 'b' variable of round 52 of MD5 must be to generate the expected hash; this ...

5

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

5

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

4

You are not asking for a collision but for a preimage. Collision attack: the attacker computes two messages m and m', distinct from each other, such that m and m' hash to the same value. Preimage: the attacker is given a goal (a hash value h) and finds a message m which hashes to h. MD5 is weak for collisions, but not for preimages: no attack method is ...

4

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

4

This depends on your input. If your input is random and at least of the output size, I would expect the output bits to be approximately independent. (There might not be a full independence, as likely some of the 2128 combinations are not possible at all, while others occur more often, but the remaining dependence would be quite difficult to measure at all in ...

4

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

4

There is a beautiful characterization for the collision preserving padding rule of any Merkle–Damgård-construction: the padding rule should be suffix free. See the 2009 paper Characterizing Padding Rules of MD Hash Functions Preserving Collision Security by Mridul Nandi for more details. The length of the message, as it turns out to be, is the simplest ...

4

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

4

Your scheme is a bad one. It is too fast. Also, your step 4 is weird and I worry it might introduce biases into the password that might reduce the entropy of your resulting passwords. Instead, I suggest you use the following alternative: Hash the password using PBKDF2, with the nickname as salt and the iteration count set to make this about as slow as ...

4

That is quite impossible. Lets assume that such an encryption scheme would exist and assume that it always outputs ciphertexts of length $n$ bits. Then, because the scheme is assumed to encrypt plaintexts of arbitrary length, it in particular encrypts all plaintexts of length $n+1$ to ciphertexts of length $n$. However, there exist twice as many plaintexts ...

3

There are two points to consider here: How likely is it that two different strings give the same MD5 hash? This is known as a hash collision. A good hash function makes this probability as small as possible (this would be about $1/2^{128}$ for MD5). If you have a larger number of strings to hash, the probability of any collision between any of them grows ...

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