# Do MD5's weaknesses affect Oplop?

Oplop is an algorithm that generates account-specific passwords from a master password and user-chosen nickname (typically username@domain). From the website:

1. Concatenate the master password with the nickname (in that order!).

2. Generate the MD5 hash of the concatenated string.

3. Convert the MD5 hash to URL-safe Base64.

4. See if there are any digits in the first 8 characters. If no digits are found ...

a. Search for the first uninterrupted substring of digits.

b. If a substring of digits is found, prepend them to the Base64 string.

c. If no substring is found, prepend a 1.

5. Use the first 8 characters as the account password.

The author says MD5 is safe. Is this true? Are there any flaws in MD5 that make it insecure as a one-way function (instead of a "thumbprint" of a string)? Is it secure when the attacker can access all 128 bits of the hash, or does the hash need to be truncated (as it is in Oplop) in order to prevent collision attacks?

-
Step 4 seems really weird. What is its purpose? –  CodesInChaos Aug 9 '12 at 20:09
@CodesInChaos it guarantees that Oplop complies with websites that require passwords to contain numerals. –  Jordan Aug 9 '12 at 20:12
Perhaps another question you might want to ask is, "Is there good reason to believe that MD5 has properties that would allow one to PROVE Oplop is secure?". The relevant definition of "secure" here should probably be unforgeability (i.e., is it a secure MAC?). Personally, I'd feel more comfortable with a scheme based on HMAC-MD5 or HMAC-SHA256... –  Seth Aug 10 '12 at 4:22
If that's the only goal of that step, then there are more straightforward ways to achieve this, that introduce less bias. –  CodesInChaos Aug 10 '12 at 12:02

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 not seem to be a serious threat in the stated usage. At worse, it seem possible to exhibit different (master password, nickname) pairs resulting in the same account password, but I fail to see that it leads to a practical attack.

The main technical drawback of using MD5 in the stated usage is, paradoxically, MD5's main quality: it is fast. That makes password cracking much easier than for a purposely slow Password-Based Key Derivation Function like PBKDF2 or Scrypt, and slightly easier than if using a hash stronger than MD5, like one of the SHA-2. However being fast is not considered an MD5 weaknesses; using a fast hash is a weakness of the proposed usage.

Also, from a Public Relation standpoint, using MD5 is a bad idea, much like using a tire known to explode at high speed is a bad idea for a manufacturer of low speed cars.

Update: Unless the master password is imposed on the user (which makes the scheme much less useful), a controllably slow Key Derivation Function is required, and as an aside should be followed by a better method to generate an acceptable password (as pointed in that other answer). I recommend Scrypt, because it uses controllably much RAM and (possibly) CPU cores, hence raising the cost of a determined attack for a given penalty to the user (a small parameterizable delay, and using the computer's resources during that time). See this table from the paper defining Scrypt:

: Note: A letter is random among 26 lowercases; a character is random among 95 ASCII symbols; text entropy per NIST SP800-63-1.

-
It seems like the answer would be yes, due to the quality you mentioned. $\:$ –  Ricky Demer Aug 9 '12 at 18:27
Do existing collision attacks on MD5 give any stepping stones for a pre-image attack? Given that the pre-image contains a master password, that could be a concern. –  B-Con Aug 9 '12 at 21:21
@B-Con: AFAIK, there is no first pre-image attack against MD5, nor indication collision attacks could be extended in this direction. There is a generic second-preimage attack, see this recent question. Here, the setup is fit for neither kind of pre-image attack, it is a rather a plain "find the key". –  fgrieu Aug 10 '12 at 6:52
@fgrieu if the master password has over 100 bits of entropy (e.g. a 20-character base64 string generated by flipping a coin), can it be cracked? –  Jordan Aug 10 '12 at 15:48
@Jordan: IF a master password has over 100 bits of entropy, I see no way it can be cracked. Bust real passwords/passphrases can not be relied to have that much entropy, if the user chooses them. Using Scrypt typically gain the equivalent of over 30 bits of entropy over MD5, at the cost of a small delay at each use. That's enough to give sizable security to a mediocre master password. –  fgrieu Aug 11 '12 at 9:40

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:

1. Hash the password using PBKDF2, with the nickname as salt and the iteration count set to make this about as slow as you can stand. Let K denote the first 128 bits of the output from PBKDF2. Set i to 0.

2. Set X = AES(K, i). Convert X to a candidate password P in some deterministic manner (e.g., by applying base64 encoding and keeping just the first 8 characters of the result).

3. If P meets your "acceptability criterion", then it is your password. Otherwise, increment i and go back to step 2.

It sounds like your "acceptability criterion" is: the password must contain at least one numeral. That's fine. The above algorithm will work with that acceptability criterion. (It will also work with many others.) It will provide about the best security you can get, for a given iteration count to PBKDF2.

-