Is this encryption algorithm built from MD5 secure?

Question

I'm being asked to use an encryption algorithm in my code, and besides the fact that I'm sure there will be implementation faults that lead to vulnerabilities, I also have concerns about the algorithm itself. I'd like to know how strongly I need to convince these guys to not use this. If it is an acceptable algorithm and there is a name for it, I'd like to know so I can find an implementation of it somewhere (I've been trained to not implement my own crypto).

I'm not a cryptographer, and this is coming from a large company and from people with much more programming experience than I have, so if I do need to convince people not to use this, it will be difficult.

1. The algorithm starts with a secret concatenated with a random string the length of an MD5 digest.
2. It MD5-digests this initial string and XORs the digest with the input data (up to the length of the MD5 digest).
3. It takes the result of that XOR operation, saves it to the output buffer and digests it concatenated with the original secret to get a new digest.
4. Then it keeps going until it has covered the whole input.

The goal of this scheme is to allow messages to be read by parties who know a secret and to not allow those messages to be read by parties who don't know the secret.

Now that I understand the notation, I can make this clearer:

$C_1 = M_1 \oplus \operatorname{MD5}( secret || random )$

$C_n = M_n \oplus \operatorname{MD5}( secret || C_{n-1} )$

I also don't understand how this is to be decrypted. It seems like the same random string is needed for that, in which case, we have the problem of how to get the random string to the other parties – is it okay for that part to be sent in plaintext?

Answer 1

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: \begin{align*} M_1 &= C_1 \oplus \operatorname{MD5}( secret\mathbin\|random )\\ M_n &= C_n \oplus \operatorname{MD5}( secret\mathbin\|C_{n-1} ) \end{align*}

If MD5 was secure in the Random Oracle Model, that would be as secure as a 128-bit block cipher in CFB mode. Although MD5 is not secure in the ROM, I do not see an attack compromising the confidentiality of the message in a non-interactive attack, assuming the $secret$ is unguessable and $random$ not reused. In particular, I do not see that the feasibility of MD5 collisions, or MD5's length-extension property, directly enable an attack.

Main issues are:

• This is unsafe if $secret$ is short or/and susceptible to enumeration, for there is no key stretching used.
• This is unsafe if the attacker can inject something in the message being encrypted, based on earlier ciphertext blocks in the same message.
• This is unsafe if the deciphering side reveals deciphered messages that do not make sense, and the attacker can modify the ciphertext.
• There is no attempt at protecting the integrity of the message.
• No test vectors are given.
• This is inefficient compared to a block cipher (but in a context where MD5 is the only efficiently implemented cryptographic primitive, it might still beat a block cipher coded in an interpreted language).
• MD5's name is tarnished, it has known weaknesses, and attacks only get better.
• The whole thing is not an established algorithm, and nothing in the present answer constitutes any form of endorsement, much to the contrary.

Answer 2

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 won't be noticeable if it happens on the last block of input.

Addendum : I just recalled that long before your question I had read something a bit like your proposal that would enjoy both privacy and authenticity Hash CFB (see slide 5)

Answer 3

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 (but not the key) is unable to recover information about the original message.

Well, your algorithm effectively divides the message into 16 byte blocks $M_1, M_2, ..., M_n$, and first generates the first block of the encrypted message:

$C_1 = M_1 \oplus MD5( secret || random )$

(where $\oplus$ is exclusive or, and $||$ is concatination). This, in itself, isn't horrible; it is slower than necessary (MD5 isn't wonderfully efficient if you time how fast it generates bytes). However, as long as your secret is unguessable (and you never use the same random to encrypt two different messages), this should be fine.

However, to encrypt the second block, it sounds like (from your description), you do:

$C_2 = M_2 \oplus MD5( C_1 )$

This is horrible. What anyone can do is rewrite it as:

$M_2 = C_2 \oplus MD5( C_1 )$

and so anyone who hears the encrypted message ($C_1, C_2, ..., C_n\ $) can recover the second block of the message (and if you continue down this logic, can recover the entire message except for the first 16 bytes).

---

The obvious question which needs to be asked: if the company needs a cryptographical algorithm to protect something, why aren't they using a well-vetted standard (such as AES), rather than making up their own? As Bruce Schneier puts it "Anyone who creates his or her own cryptographic primitive is either a genius or a fool. Given the genius/fool ratio for our species, the odds aren't very good".

Just plugging in AES may not be sufficient (you need to use it in a mode that gives you the security services you need), but it's a start.