# Why the extra bits in Hash width?

Quark says u-Quark has 64 or 128 security (bits). But u-Quark width is 17 bytes means 136 bits.

Why this difference? If the hash produced is 136 bits then why do we call them as 128-bit hash value and not 136-bit hash value? If I wish to use the hash value generated, then should I use just the 128 bits or all 136 bits must be used?

Simple example: Suppose you have a hash that is 136 bits but the last 8 bits are always 0.

Clearly it is not more secure than just the first 128 bits.

In practice it will be less obvious but it means that the 136 bit long output will be one of only $2^{128}$ different values.

The extra bits are required to guarantee 128 bit security and cannot be omitted. To continue the analogy, assume that the 8 extra zero bits are mixed with the rest of the 128 bits. You simply don't know which bits to omit.

To give a possibly more visual, short example consider the following fictitious hash outputs:

$100, 110, 011, 010$

Since there are only 4 possibilities the hash could not have a security level greater than $2^2$. (You could simply attack it by guessing one out of the $2^2$ values.)

However, the output is 3 bits long and you cannot remove any of the bits. If you did you would have less than $2^2$ possibilities left.

• Does this apply to all the hash functions? For example, how many bit security does MD5 provide? – Shridhar R Kulkarni Apr 7 '17 at 1:26