12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Note that MD5 uses a block size of 64 bytes. So you'd be hashing 64 bytes to get an input/output of 16 bytes; that is: if you stay within the 55 byte limit for the input - otherwise it will be padded to two blocks. Just a remark, nothing to do with security / applicability of the scheme. Personally I don't see how the attacks on MD5 are applicable to this scheme. HMAC(K, N || i) would be stronger and possibly better supported (because of the way the key is used) but even slower. $\endgroup$ – Maarten Bodewes Apr 20 '18 at 10:01
  • $\begingroup$ @MaartenBodewes 64 bytes is fine, it leaves 32 bytes for the key, 16 bytes for the nonce, and 16 bytes for the counter. However I think you misunderstand. I'm not going to be implementing the raw MD5 function where any of that matters. I'll quite literally be doing something along the lines of block=`echo $key$nonce$counter | md5sum | cut -b-32`... Yes, it's bad. To put it into perspective, incrementing the counter takes about as long as computing the actual hash in this shell. $\endgroup$ – forest Apr 21 '18 at 13:53
  • $\begingroup$ The full MD5 and therefore md5sum pads the bytes with both bit padding (at minimum one byte, as most implementations don't handle bits too well) and the length in 8 bytes: overhead 9 bytes, so $64 - 9 = 55$. So you should not give it 64 bytes because that means it will hash two blocks / 2 * 64 bytes. Unless you don't care about halving the speed, of course. Just use 16 bytes for the key; MD5 will not give you over 128 bits of security anyway. I think there are options to just produce raw, unencoded bytes for md5sum by the way. $\endgroup$ – Maarten Bodewes Apr 21 '18 at 21:52
  • $\begingroup$ @MaartenBodewes Unfortunately this version of md5sum is extremely limited. It cannot output anything more than hex. Thank you though, I'll use a 16 byte key. $\endgroup$ – forest Apr 22 '18 at 6:10
  • $\begingroup$ @MaartenBodewes: Actually, with a bigger key MD5 might give you more than 128-bit security. $2^{128}$ effort to find a preimage doesn't mean same effort will recover a secret key. NIST SP 800-107 for example suggests that HMAC-MD5 should have key recovery resistance up to 256-bit (§5.3.4). $\endgroup$ – Luis Casillas Apr 23 '18 at 3:17
9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Your distinguisher, which is the standard length extension attack of computing $\operatorname{MD5}(\operatorname{pad}(x) \mathbin\Vert y)$ given $\operatorname{MD5}(x)$, doesn't work if the input is fixed-length. $\endgroup$ – Squeamish Ossifrage Apr 23 '18 at 21:03
  • $\begingroup$ Yeah, I guess that's true if you never hash messages exceeding the block size minus the padding length. There are single-block, identical-prefix collisions for MD5 (e.g., marc-stevens.nl/research/md5-1block-collision/… ) , but I'm not sure I've seen anything showing single-block, secret-identical-prefix collisions. That said, finding a collision is not the only way an oracle machine could distinguish between secret-prefix, single-block MD5 and a uniformly distributed function. Importantly, if single-block MD5 is not a PRF neither are is HMAC-MD5 or sandwich. $\endgroup$ – fowlslegs Apr 23 '18 at 21:27
  • $\begingroup$ That's true: if you had a better PRF distinguisher, then this would be a bad stream cipher. But if you have a better-than-generic PRF-distinguisher for single-block $\operatorname{MD5}(k \mathbin\Vert x)$, I expect you could get a publication in a serious cryptography journal! $\endgroup$ – Squeamish Ossifrage Apr 23 '18 at 21:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed, the speed of spawning processes is where the most overhead comes from. Simply incrementing the counter takes a fifth of a second since it can only be done by spawning a process with counter=`expr $counter + 1` on this system... But yes, I certainly understand the malleability issues and am sure that the threat model here does not require authentication. $\endgroup$ – forest Apr 22 '18 at 6:13
  • $\begingroup$ @forest No counter=$((counter + 1))? $\endgroup$ – Squeamish Ossifrage Apr 24 '18 at 3:19
  • $\begingroup$ @SqueamishOssifrage Nope, it's ash shell from the 90s. Extremely limited in what it can do. $\endgroup$ – forest Apr 24 '18 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.