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


The merchant is securely given a secret key k, known to them and the payment provider only. 
EDIT: Usually the key is quite long.
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&amp;paymentStatus=SUCCESS&amp;...&amp;signature=abcd
The message m which is signed is formed in the following way:

orderid=&lt;..&gt;|paymentStatus=&lt;..&gt;|...
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.
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?
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:


Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (rump session of Crypto 2004, and in Cryptology ePrint Archive)
Xiaoyun Wang, Hongbo Yu: How to Break MD5 and Other Hash Functions (in proceedings of Eurocrypt 2005)
Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute (in Cryptology ePrint Archive, 2006)
Marc Stevens: Single-block collision attack on MD5 (in Cryptology ePrint Archive, 2012, and here with code and example)
Tao Xie, Fanbao Liu and Dengguo Feng: Fast Collision Attack on MD5 (in Cryptology ePrint Archive, 2013)




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.