"При атаке HMAC, злоумышленник не сможет генерировать пару («сообщение», «код») в удалённом (офлайн) режиме, так как злоумышленник не знает ключа K.
...
Таким образом, если скорость имеет значение, вполне приемлемо использовать MD5, а не SHA-1 в качестве встроенных хеш-функций для HMAC." Википедия
Не знаю, как работает hmac, но если положить хэш последним блоком в cbc (со случайным iv), то md5 очевидно можно использовать.  Аутентификацию нельзя будет целенаправленно нарушить, так как слабый хэш зашифрован нормальным алгоритмом.
Или же можно взять хэш сообщения вместе с iv и зашифровать отдельно.

Merkle-Damgård это модель, по которой строятся хэш-функции (а не hmac). По ней строились md5, sha1, sha2. Более современная и простая модель хэш-функций - cryptographic sponge. Представлена разработчиками sha3 keccak, по сути превращает в хэш-фунцию любой блочный шифр с достаточной длиной блока и гарантирует устойчивость, если устойчив шифр.