Encrypting data with HMAC-SHA1 challenge response as the key

Question

I came across a piece of software that uses the following algorithm to generate a symmetric encryption key to encrypt data.

1. Generate a non-secret 64 byte random string $M$ (fixed challenge)
2. Generate a secret 20 byte random string $K$ (HMAC key)
3. Compute $E = \operatorname{HMAC-SHA1}(K, M)$

$E$ is a 20-byte encryption key that is used to encrypt some data (with some well-known cryptographically secure algorithm). $M$ is kept alongside the data, while $K$ is separated from it and kept secret. Whenever data has to be accessed, $K$ is retrieved and the HMAC computation is repeated to re-generate $E$ and decrypt the data.

Is this algorithm secure, assuming that $E$ and $K$ are kept secret?

Answer 1

Yes, it is secure to generate the key as long as the $K$ is kept secret. Although the collision of SHA-1 is broken, HMAC is a PRF under the sole assumption that the compression function is a PRF. It is not affected by the collision of the has function.

The security strength of the HMAC is relay on the size of the key. The usual attack is to search for the key $K$.

Keep in mind that, the attacker will go to search for $E$ if $E<K$. In your case, since both are 20 bytes, so brute-forcing $K$ can be faster, though not possible.