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?