Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
It doesn't matter what the original hash length was. Trimming the output of a random oracle to $n$ bits will cause it to require $2^{n-1}$ operations on average to find a collision for a particular output, and $2^{n/2}$ operations on average to find any collision. –  Stephen Touset Aug 19 at 17:59

1 Answer 1

up vote 1 down vote accepted

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.).

share|improve this answer
    
I should have used the term 128-bit cryptographic key instead of "password" - it's definitely not a textual password. –  Ozo Jan 10 at 22:56
    
From the code here: en.wikipedia.org/wiki/… it seems short keys are padded to fit the block size. –  Ozo Jan 10 at 22:58
    
Removed the part. I was accidentally thinking the data input, but indeed in your construct the password was key input. –  user4982 Jan 10 at 23:09
    
I know that the 20 years estimation is based on current technology, but it's good enough for my purposes. However, collisions are a problem when working with hash-chains (the attacker could "take-over" the chain by sending fake keys that match). Back to the drawing table... –  Ozo Jan 10 at 23:19
    
Truncating the output to 16 bytes is considered safe but finding a collision is not infeasible: security.stackexchange.com/questions/34796/… –  Ozo Jan 11 at 10:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.