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
HMAC(K, N || i)
would be stronger and possibly better supported (because of the way the key is used) but even slower. $\endgroup$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$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 formd5sum
by the way. $\endgroup$md5sum
is extremely limited. It cannot output anything more than hex. Thank you though, I'll use a 16 byte key. $\endgroup$