# Strange MAC algorithm

I'm working with a payment provider which uses the following algorithm for signing messages:

1. The merchant is securely given a secret key k, known to them and the payment provider only. EDIT: Usually the key is quite long.
2. The payment is implemented by using a redirect, and the merchant later receives callbacks containing information about the success or failure of the payment operation. The merchant considers this information trustworthy. Here is an example of a successful payment callback for order no. 1234 and a merchant hosted at example.com:

example.com?orderID=1234&paymentStatus=SUCCESS&...&signature=abcd

3. The message m which is signed is formed in the following way:

orderid=<..>|paymentStatus=<..>|...

4. The signature algorithm S(m,k) is chosen to be: signature=H(m||k) (m||k means m concatenated with the secret key k) where H is a hashing function, in this case MD5.

5. The verification algorithm is V(signature, m, k) and returns true only if H(m||k) = signature.

As far as I understood the inner workings of MD5 if the signing algorithm was S(m,k) = H(k||m) then this would be totally insecure because if an attacker knows H(k||m) she may be able to calculate H(k||m||m') where m' is a message of her choice - this would mean that the signature is vulnerable to both existential and selective forgery. Correct? But deliberately or not the algorithm is S(m,k) = H(m||k) - the key is put last in the concatenated string.

So far I cannot think of exploitable vulnerability in this protocol (I'm not considering the problems inherent to MD5). Any ideas, is this secure enough?

• Somewhat related to this question. $\;$ Independently: knowing MD5(k||m) allows computing MD5(k||m||m'||m") for m' a certain known function of m and the length of k (with m' at least 9 bytes or 65 bits), and freely chosen m". – fgrieu Nov 13 '14 at 9:58
• In short this would be relatively safe unless the message m allows a lot of freedom. In that case you would have to worry (immediately) about the security of MD5. Using HMAC or SHA-3 would fix both the length extension as well as the MD5 related attacks on the MAC (if we just focus on the MAC anyway, I have no idea about the security of the rest of the protocol). – Maarten Bodewes Nov 13 '14 at 15:02

We can attack the MAC defined by: MAC(k,m)=MD5(m||k), in a chosen-messages setup, basically because MD5's collision-resistance is broken.
The adversary chooses m and m' of the same length $b\ge64$ bytes, differing only in their first $\lfloor b/64\rfloor$ 64-byte blocks, such that there is a collision after hashing these blocks of m and m'. If follows that MAC(k,m)=MAC(k,m'), and also MAC(k,m||m")=MAC(k,m'||m") for any m". We know various efficient techniques to create such m and m', with $b$ down to 128 or even 64 bytes, including with a moderate degree of constraints:
In general (without talking about MD5): Suppose our hashfunction $H$ is a Merkle-Damgard construction using a Davies-Meyer compression function $h=(H_i,m)=E_{m_i}(H_{i-1})\oplus H_{i-1}$. Since the compression function is public, everybody is able to compute the input to the final round of the MD-Hash. In addition, if you know the input to the final round of the compression function, lets call it $H(m)$, you're able to invert the $\oplus$ in the Davies-Meyer construction. This means that the "secret" part of this MAC can be reduced to $E_{k}(H(m))$ which is nothing else than an encrypted hash. So the general answer can be linked to the question is E(H(m)) a good MAC.