Cryptographic hash function question

Question

Consider the following question:

Given a $n$-bit cryptographic hash function $H$, how many messages should we expect to hash before before finding a message $x$ such that $H(x) < 2^{n-k}$, for some integer $k$.

For me, this question does not make a lot of sense. A cryptographic hashing function has always a fixed size on the output, such as SHA1 with 160 bits. It does not really matter what $x$, the message to be hashed, is $\operatorname{len}(\operatorname{SHA1}(x)) = 160\,$bits. In this case $\operatorname{len}(H(x)) = n$. Because of this, it is sufficient to hash a unique, random message. Because the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.

Please do not give the answer, if you do, hide it ! :) I just want to better understand the question.

Answer 1

In cryptography, we often assimilate bitstrings to integers. Unless otherwise specified, that is per big-endian binary, where a bitstring $S$ of $n$ bits $b_0,b_1,\ldots b_{n-2},b_{n-1}$ is assimilated to integer $s$ with $$s=\sum_{i=0}^{n-1}b_i\,2^{n-1-i}$$

E.g. bitstring 00010001 (which is 8-bit) is assimilated to integer $16+1=17$. Bitstring 0000000000010001 (which is 16-bit) and bitstring 10001 (which is 5-bit) also are assimilated to integer $17$. Note that for some purposes like hashing, we can't assimilate these bitstrings, even though they are assimilated to the same integer.

$H(x)<2^{n-k}$ compares $H(x)$, which is a bitstring (or perhaps a bytestring for a programmer), to $2^{n-k}$, which is an integer (an element of $\mathbb Z\,$). Some kind of transformation is needed. This is a sure sign that in the question, $H(x)<2^{n-k}$ must be read as:

the integer assimilated to the bitsring $H(x)$ is less than the integer $2^{n-k}$.

Note: In the circumstance it's also OK to assume little-endian binary, which uses the simpler $s=\displaystyle\sum_{i=0}^{n-1}b_i\,2^i$, but one should first get convinced this won't change the result.

---

There are several things wrong with stating

the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.

• If the question considered the size of "the size of the hashed $x$", it would be written $|H(x)|<2^{n-k}$, rather than $H(x)<2^{n-k}$.
• Even with the statement understood as $|H(x)|<2^{n-k}$, the argument given would be wrong, with a counterexample the choice of $k=n$.
• Cryptographers measure size of bitstrings and integers in bits (not bytes) unless otherwise stated. BTW, the bit size of non-negative integer $s$ is $\bigl\lceil\log_2(s+1)\bigr\rceil$, or equivalently the size of the smallest bitstring assimilated to $s$ (equivalently per big-endian or little-endian binary).