I'm creating an application that requires message authentication on the payload of a QR-code. Because of the maximum length of an error-correcting (H) QR-code (368 bits) and the original size of my payload (128 bits), I have to limit the size of the MAC.

This leaves me with several options. I can use basically any HMAC variant, and cut the output to fit in the QR-code payload (I tried this with HMAC-SHA512) or I can use a potentially weak implementation with HMAC-MD5, which fits perfectly.

My question is: which of the proposed solutions is more secure?