21
$\begingroup$

In the HOTP protocol after calculating a 20 byte hash it is truncated to 4 bytes.

For this first an offset is calculated (low-order 4 bits of the last byte) which determines the four bytes to be selected:

DT(String) // String = String[0]...String[19]
 Let OffsetBits be the low-order 4 bits of String[19]
 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
 Let P = String[OffSet]...String[OffSet+3]
 Return the Last 31 bits of P

Why is this more 'secure' than simply always taking the first four bytes of the hash?

$\endgroup$
1
  • 5
    $\begingroup$ Looks like over-engineering to me. $\endgroup$
    – fgrieu
    Nov 2, 2012 at 20:48

2 Answers 2

17
$\begingroup$

It looks to me that the original intent was to make sure that all bits of the hash digest have an equal chance to contribute to the truncated portion. But one of the properties required of a secure hash function (the diffusion property) is to ensure that a single bit change results in a cascade that yields changing multiple bits across the entire digest (the Avalanche effect.) If you don't trust this property in the hash algorithm, you either have a very weak hash algorithm or are ignoring the principles that make a hash algorithm strong.

If any of the input bits to the hash differed from the original, at least some of bits in the last four bytes will reflect it, with the expected reduction in collision resistance from $2^{80}$ to $2^{16}$.

So, given a good hash algorithm, it's not "more secure". At best, it's equally secure. In the real world, it's slightly more risky (and therefore less secure) because the added complexity offers the chance for a programmer to make an implementation mistake.

$\endgroup$
4
  • $\begingroup$ You meant from $2^{80}$ to $2^{16}$. $\endgroup$
    – bob
    Nov 3, 2012 at 21:05
  • $\begingroup$ You're right, I forgot the birthday paradox for computing collision resistance of a hash function. I edited the answer. $\endgroup$ Nov 5, 2012 at 15:08
  • $\begingroup$ The answer(s) given seem plausible enough to accept, they confirmed my suspicions. $\endgroup$
    – Jeff
    Nov 6, 2012 at 13:46
  • 1
    $\begingroup$ The interesting number is not collision resistance, but "MAC forgery resistance", which is still $2^{31}$ for the truncated bits (the top bit is blanked out to avoid worrying about signed versus unsigned calculations) and about $10^d$ for the final resulting number, $d\leq 8$ being the number of decimal digits. $\endgroup$ Nov 7, 2012 at 21:02
6
$\begingroup$

It looks like unnecessary window dressing to me. As far as I can see, there is absolutely no reason to use this scheme instead of just choosing the first four bytes of the hash. It looks like unnecessary complexity -- or, as fgrieu put it, over-engineering. If the hash function is any good, then all this should be unnecessary. And if the hash function isn't any good, then you've got bigger problems and shouldn't be using that hash function in the first place.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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