Do MD5's weaknesses affect Oplop?

Question

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?

Answer 1

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

Answer 2

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.