Using HMAC-SHA256 with short passwords and sliced outputs for short-lived secure hashing

Question

I don't have much background in cryptography, so forgive me if I'm using the wrong mathematical terms to explain my needs.

Following this question, I learned that taking a random secret 16-bytes password and some random 16-bytes msg, and calculating output = HMAC_SHA256(password, msg), it will take an attacker that knows output and msg an unreasonable amount of time (more than 20 years) to restore password, or even to find a different password (say password2) that gives a collision, i.e. the same output for HMAC_SHA256(password2, msg).

What would happen if I use a shorter password of 14 bytes (and the attacker knows that)? How much time would it take the attacker to find password or a colliding password2?

What if I slice the output and save only output[:14]? How much time would it take the attacker to find a colliding password2 such that: output[:14] = HMAC_SHA256(password2, salt)[:14] ?

What about less than that, like 12 bytes or 10 bytes?

The hashing mechanism should be "unbreakable" for a really short time of only 1 minute - the final purpose is creating a hash-chain for an OTP with a dumb client that stores the whole list and each minute sends the previous "password" in the list (its hash gives the "password" that was sent a minute ago). The memory on the client is limited (every byte counts), but I don't want it to make complex calculations than a lookup from an array.

According to my uneducated estimations, a 2 bytes shortening (to 14 bytes) means it would take at least $\frac{20}{2^{16}}$ years, which is around 2.7 hours. Am I right?

Thanks

--- New Estimations ---

Using a 14-bytes password for life time of 1 minute shouldn't be a problem. If an attacker had an algorithm to recover 14-bytes passwords in a minute, he could develop an algorithm to recover 16-bytes passwords in 65536 minutes (brute force the extensions), which is around 45 days (much less than 20 years).

Slicing the output is shouldn't be a problem even when it comes to finding collisions. There are 65536 times more collisions that would match output[:14] than the full output, so it would be 65536 times "easier" to find one (i.e. $\frac{20}{2^{16}}$ years $\approx 2.7$ hours). Saying that the password is 14-bytes is equivalent to saying that it is a 16-bytes password that ends with \00\00 (this is how HMAC treats short passwords anyway). This will only make it harder for the attacker to find a collision, because the collision must end with \00\00 too.

Does anyone disagree?

-- Newer Estimations --

Bad news - The output of HMAC_SHA256 is 32 bytes long, not 16! Slicing the output to 14 bytes would make it $2^{8 \cdot (32-14)}$ times easier to find a collision ($\frac{20}{2^{144}}$ years $\approx$ no time at all). Hmmm... right?

Answer 1

It is very hard to estimate time it takes for attacker to brute-force password. This is because HMAC-SHA256 can be calculated billions of times per second on some devices, and there are some devices existing which take millisecond to calculate one HMAC.

BTW, I understood that password is actually a 128-bit cryptographic key, i.e. it can may contain any bytes, right? Usually term password is used for something that is much weaker.

If your adversary has thousands of high-end GPUs or dedicated ASIC chips, it is amazing how many passwords they can try. For this reason, it is very hard trying to estimate how strong is strong enough.

Earlier very good answer from T. Pornin to question on brute-forcing: Cost of brute-forcing AES-128. Although AES-128 is different algorithm than HMAC-SHA256(128 bit key), similar formula can be used to estimate costs. Short answer: if password is 16 truly random bytes, you would not break it even if you had all the money in the world.

---

The output of HMAC-SHA256 indeed is 32 bytes. Should you truncate it, depending on how you use HMAC, you may risk collisions. When the HMAC is used as MAC (message authentication code), it is in fact almost customary to truncate the output. (HMAC-SHA256-128 i.e. truncated to 128 bits is quite common.) If you use it in some "hash-like" application, or if you use the function vary many times, the 128 bits is indeed below what is recommended due to the birthday effect.

---

BTW, when working with time estimate like 20 years, you need to remember that processing power double every two years or so (Moore's law). For that reason, if something takes 20 years, large part of processing is done within the last three years. Also, 20 years may expect that there will be some new ways to crypto analyze SHA256 can be found during the time frame (but not full break.).