3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – fgrieu Nov 13 '14 at 9:58
  • 2
    $\begingroup$ 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). $\endgroup$ – Maarten Bodewes Nov 13 '14 at 15:02
5
$\begingroup$

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:


If instead of MD5 we had an unbroken Merkle-Damgård hash like SHA-256, or a hash secure in the random oracle model (which SHA-256 is not quite, for it has the length-extension property), then we'd basically have no known attack, as discussed in this question.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.