Can I use HKDF to improve security of HMAC used with weak hash function? I am writing a framework which encrypts/decrypts files (or streams, in general) with symmetric key using block cipher (for example, AES). To authenticate encrypted file, I use HMAC, which is initialized with a key derived from supplied password (using PBKDF2 and then HKDF function). It is calculated during encryption phase (I first encrypt, then HMAC). The result of the HMAC function is placed in the header of the encrypted file. On decryption, I check HMAC of the encrypted text. If calculated HMAC and HMAC from the file header match, then supplied password is correct and encrypted text is not corrupted.

My question is about hash function that is used with HMAC. Obviously, the best solution would be just to use some strong hash function (like SHA-256). However, I am experimenting with a thought of using weaker, but faster function, because I would like to improve performance of my framework (SHA-256 is not the fastest one). Using weaker hash function for HMAC does not necessarily mean that HMAC is affected. For example, Bruce Schneier wrote that broken SHA-1 does not affect HMAC.

What about using HMAC with MD4? From various sources I have learned that it is NOT recommended. But what if instead of plain HMAC/MD4 I use PBKDF2_MD4 as input for HKDF function, which takes PBKDF2_MD4 output as its input (e.g. as PRK) and expands entropy? Then I can retrieve this expanded entropy and use it (for example, first 16 bytes, whatever) instead of original HMAC output to authenticate encrypted file.

My question is - if HMAC_MD4 is considered insecure, is HKDF(PBKDF2_MD4) is also insecure? If MD4 is definitely a no-go, what about MD5?

I have read this paper on HMAC security based on various hash functions (including MD4, MD5 and others), which says that using these weak hash functions allows to perform a forgery attack. In my case, I am not concerned with forgery. I just need to verify that encrypted text is not corrupted and can be decrypted with the password provided. Obviously, using weaker hash function must not help an attacker to recover the password or, in general, get access to the unencrypted text.

Thank you for your attention.
First of all: accelerating PBKDF by using a faster hash doesn't make sense; an attacker is likely to receive the same speedup.

On 64 bit machines SHA-512 or one of the 384, 256 or 224 derivatives is likely to be faster than SHA-256. So you might be able to increase security and have a faster hash algorithm.

MD4 should probably not be used for anything anymore, including HMAC. MD5 is still considered secure for key derivation, but I personally would not feel comfortable using it for anything.

If you are not worried about forgeries you could simply go for a checksum over the ciphertext and a check value of some kind to see if the password is correct. I'm wondering though if the consequences of not protecting against forgeries is fully understood (e.g. with regards to padding oracle attacks). It may well be that failing to protect against forgeries allows attacks on the cipher or cipher mode of operation.

Currently I would go for PBKDF2, bcrypt or even scrypt, then perform HKDF-Extract to obtain an encryption key. For the KDF functions I would use SHA-512. Then I would use AES-GCM for authenticated encryption. Many processors will be able to accelerate AES-GCM fine, may it ever come to that.  Possibly I would use another KDF extract to create a different key that I would just use to check if the password entered was correct (in my opinion the work factor of the PBKDF should protect the key, not the size of the ciphertext as that may be small).

Alternatively you could use a NaCl compatible library such as libsodium, which has been optimized for security and speed.