Using weak hash functions to construct a stream cipher

Question

I am in the awkward position of developing a secure encryption scheme that provides data-at-rest security for a very limited embedded system. The system is only guaranteed to have 4 MiB of memory (some systems have an extra 32 MiB), and they do not even have an MMU. They are running an old version of μClinux. While the resources are not that big an issue (even a cheap 8051 could run a secure cipher), the real issue is that I can only use the utilities that are present on the system. Unfortunately, there are no scripting languages other than a rather limited ash shell, so implementing a real stream cipher is out of the question. However, the md5sum utility is present, as is od which is necessary to combine the keystream with the plaintext of a binary stream.

Because implementing a stream cipher in ash shell would be too slow, I thought of using MD5, where the keystream $H$ at position $i$ is the hash of key $K$, nonce $N$, and counter $i$ concatenated. Encryption of plaintext $P$ and decryption of ciphertext $C$ is done as in any stream cipher.

\begin{align*} C_i &= P_i \oplus \operatorname{MD5}(K \mathbin\| N \mathbin\| i) \\ P_i &= C_i \oplus \operatorname{MD5}(K \mathbin\| N \mathbin\| i) \end{align*}

I understand that it is possible to design a stream cipher from a hash function, but I would like to know specifically if MD5 is an acceptable hash function in this particular scenario. As far as I am aware, collision attacks are irrelevant for use in a stream cipher, but I want to make sure I missed nothing. Is this scheme appropriate for my unfortunate hardware / software limitations?

I am also aware that designing a cryptographic scheme as an amateur is very bad. Unfortunately, I have little choice as I can't load my own executables onto the device, and thankfully I do not need authentication or any security properties other than data-at-rest security (i.e. it is a situation where unauthenticated AES-CTR would suffice).

Answer 1

As long as your encoding of $K$, $N$, and $i$ is injective (i.e., for each encoded string you can uniquely derive $K$, $N$, and $i$) and fixed-length, this is almost certainly a decent stream cipher.

It won't break any speed records, obviously! But collision resistance is not relevant here, and I have no reason to suspect that the distribution of $x \mapsto \operatorname{MD5}(k \mathbin\Vert x)$ for fixed-length $x$ is distinguishable from uniform under a uniform choice of $k$. Any distinguisher would probably suggest a better than generic partial preimage attack on MD5, and in spite of some papers claiming the contrary in nonsensical cost models, so far there's no evidence of preimage attacks on MD5.

That said: Consider carefully whether you also need to do authentication! Unauthenticated encryption is seldom useful in real-world applications. Using the tools you have, you can probably compute HMAC-MD5 too without too much trouble. Encrypt-then-MAC with MD5-CTR and HMAC-MD5 may be goofy, but it probably makes a reasonably secure authenticated encryption scheme.

Do make sure, though, to limit yourself to ${\lll}2^{64}$ messages under any one key because the 128-bit state of HMAC-MD5 admits a birthday forger, and make sure to use at least a 256-bit key in case there is any danger of multi-target attacks.

Answer 2

Edit: Feel free to skip this proof for distinguishability in the multi-block setting, which doesn't apply in the single-block setting as pointed out in the comments. I still think the suggestions starting with "A second suggestion" might be helpful.

For this scheme to be IND-CPA secure $\textsf{MD5}(k\mathbin\|m)$, or "secret-prefix MD5," must be a pseudorandom function (I will not prove this, but it follows from the fact that your scheme is very close to $\textsf{CTR}$ mode). To define pseudorandomness formally, we say for all probabilistic polynomial time oracle machines $M$, polynomials $p(\cdot)$

$$\big| \Pr[M^{\textsf{MD5}(k\mathbin\|m)} = 1] - \big| \Pr[M^{H_n} = 1]\big| < \frac{1}{p(n)}$$

where $k \xleftarrow{\$} \{0,1\}^{128}$ and $H_n$ is uniformly distributed among all functions mapping $384$-bit to $128$-bit strings (we're going to ignore padding for the purposes of the proof, but I'll informally explain later how this distinguishing attack can work with $\textsf{MD5}$'s padding scheme as well). We claim we can construct a probabilistic polynomial time oracle machine $M$ that makes no more than two queries such that

$$\big| \Pr[M^{\textsf{MD5}(k\mathbin\|x)} = 1] - \Pr[M^{H_n} = 1]\big| = 1 - \frac{1}{2^{128}}$$

showing that $\textsf{MD5}(k\mathbin\|x)$ is far a pseudorandom function, and that your encryption scheme is not IND-CPA secure.

First we're going to open the hood on the $\textsf{MD5}$ hash function. $\textsf{MD5}$ uses the Merkle–Damgård (MD) construction, which is a way of taking a compression function $h: \{0,1\}^c \times \{0,1\}^b \rightarrow \{0,1\}^c$ and turning into into a variable-input-length hash function $H: \{0, 1\}^c \times \{0,1\}^* \rightarrow \{0,1\}^n$. $\textsf{MD5}$ might better be written $\textsf{MD5}(IV, m)$ to signify its fixed-length initialization vector $IV$, which is always used to begin the MD iteration of the compression function.

The iteration works as follows. After padding, the message $k\mathbin\|m$ (which in our case has a secret-prefix key) is split into $512$-bit chunks $k\mathbin\|m_1, m_2, \ldots m_p$. The MD iteration is defined as follows: $h_1 = h(IV, k\mathbin\|m_1), h_i = h(h_{i-1},m_i)$. Then $\textsf{MD5}(IV, k\mathbin\|m) = h_p$.

Our oracle machine $M$ works as follows. First $M$ picks a message $m' \xleftarrow{\$} \{0,1\}^{384}$ and queries it's hashing oracle to get response $h'$. If its oracle is $\textsf{MD5}(k\mathbin\|m)$ then $h'=h_1$, else $h'=\mathcal{U}_{128}$ (i.e., $h'$ is a random variable with equal probability in the set of $128$-bit strings). Next our $M$ picks a message $m'' \xleftarrow{\$} \{0,1\}^{512}$, and queries it's oracle with $m'\mathbin\|m''$ to get $h''$. If its oracle is $\textsf{MD5}(k\mathbin\|m)$ then $h''=h_2$, else $h''=\mathcal{U}_{128}$. Notice that we can compute $h_1$ from $h_2$ because no secrets are needed to do so. Specifically, $M$ computes $h''' = h(h',m'')$. If $h''' = h''$ $M$ outputs one, else zero. If the oracle is $\textsf{MD5}(k\mathbin\|m)$, then $\Pr[M^{\textsf{MD5}(k\mathbin\|x)} = 1] = 1$, and if the oracle is $H_n$, then $\Pr[M^{H_n} = 1] = 1/ 2^{128}$, which represents the chance $\mathcal{U}_{128}$ is any particular string.

Note this same problem is why you cannot use any of the $\textsf{SHA-2}$ family in this construction either, as we can similarly construct a $M$ using the same length-extension attack. That is why it was a requirement that $\textsf{SHA-3}$ candidates were not vulnerable to this attack.

My, first recommendation is to use $\textsf{HMAC-MD5}$ and I highly recommend doing so. The pseudorandomness of $\textsf{HMAC}$ can be reduced to the pseudorandomness of its underlying compression function [1], and as far as I've seen no distinguisher has been built for the full $\textsf{HMAC-MD5}$ (see [2] for a reduced round distinguisher). You might also want to look into the Sandwich MAC [3], which also has a (slightly different in the gritty details) reduction of its pseudorandomness to its underlying compression function. The benefit of the Sandwich MAC is that you won't lose any speed as it only requires one hash function call per $128$-bits of keystream generated.

If you go with $\textsf{HMAC}$, then using a $256$-bit key makes sense as suggested above (actually, I'm curious if anyone can link a paper on "effective key security" in $\textsf{HMAC}$).

A second suggestion is to simply use $\textsf{CTR}$ mode, and get rid of your nonces which will create a lot of overhead generating and storing a unique random string for every $128$ bits of keystream. Just make sure for each stream of plaintext you wish to encrypt that you select your counter uniformly at random from a large enough space (e.g., $2^{256}) so that the counter may only overlap with negligible probability. This way you only have to store one counter value per stream of plaintext you encrypt, and the reduction of its security is well-known.

Finally, maybe it would be faster to pick a random counter and then iterate over seq ctr <ctr+keystream-needed> to encrypt your blocks, since apparently calls to your counter incrementer are grotesquely slow.

If I may ask, what's your threat model where IND-CCA2 and authentication are not important?

[1] "New Proofs for NMAC and HMAC: Security without Collision-Resistance" http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html

[2] "On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1?" https://eprint.iacr.org/2006/187.pdf

[3] "“Sandwich” Is Indeed Secure: How to Authenticate a Message with Just One Hashing" https://www.researchgate.net/profile/Dhiman_Saha3/publication/220798573_Strengthening_NLS_Against_Crossword_Puzzle_Attack/links/543d1a480cf20af5cfbfa786.pdf#page=366

Answer 3

Yes, that seems like a solid construction for a stream cipher. MD5 is still considered preimage resistant with no remotely viable attack known.

Note however what you get here is only confidentiality. And it is trivially malleable.

Without any authentication an active attacker could modify the cipher text by xoring it with a change he wishes to apply to plain text. An attacker could make very specific changes without much knowledge of the plain text.

You could theoretically implement GCM with MD5 but that would have you writing significantly more code in ASH.

Also note the speed of spawning the md5sum process per block will dwarf the time of any actual computation.

Have you considered not using ash, there must be a cross compiler available allowing you to write C elsewhere and transferring the binaries. Why can't you add something, recheck your assumptions. Or suffer writing significant logic in ash.