# Cryptographic hash function 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.

• This is about the representation of H(x) as an integer. Take for example a 4-bit hash function. The 4 bits 1111 are the integer 15 while the 4 bits 0001 are the integer 1. Basically the k in the question is the minimal number of leading 0 in the bit representation. – Steffen Ullrich Nov 16 '20 at 19:54
• SHA-1 has output size of 160 bits, not 161. What is the origin of this question? Why do you need this? There is no guarantee that SHA1 output 11.......111 – kelalaka Nov 16 '20 at 19:54
• Model the output as unform random than it will be easy... – kelalaka Nov 16 '20 at 19:56
• I have the strong feeling that the question should read $2^{n-k}$ not $2^n-k$, i.e. the same as mining a block. In that case $k$ is just the number of starting zeros after all. – Maarten Bodewes Nov 17 '20 at 8:15

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).
• While educative, this doesn't address the actual question of the OP. I believe, the OP wants to estimate the Bitcoin Mining probability that one can find the required hash < the current hash. – kelalaka Nov 17 '20 at 16:26
• @kelelaka: you are right about what the OP is trying to achieve. See the question's last line for why I don't touch this, but only what the problem means. – fgrieu Nov 17 '20 at 16:46
• You can help to model, at least without the modelling it is hard. – kelalaka Nov 17 '20 at 16:47