Using HMAC-SHA256 with short passwords and sliced outputs for short-lived secure hashing
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.).