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?

  • 4
    $\begingroup$ Looks like over-engineering to me. $\endgroup$ – fgrieu Nov 2 '12 at 20:48

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 of a secure hash function is to ensure that a single bit change results in a cascade that yields changing bits across the entire digest. If you don't trust this property in the hash algorithm, you either have a very weak hash algorithm or a weak understanding of the properties that make a hash algorithm strong.

If any of the input bits to the hash differed originally, 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.

  • $\begingroup$ You meant from $2^{80}$ to $2^{16}$. $\endgroup$ – bob Nov 3 '12 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$ – John Deters Nov 5 '12 at 15:08
  • $\begingroup$ The answer(s) given seem plausible enough to accept, they confirmed my suspicions. $\endgroup$ – Jeff Nov 6 '12 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$ – Paŭlo Ebermann Nov 7 '12 at 21:02

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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