# How many hash functions must Bob compute to find a solution?

Alice proposes the following puzzle to be completed.
Let m be the body of the email message,
let a be the recipient’s email address,
let H( )be the hash function SHA3-256, and
let x be an arbitrary 256-bit value.
The sender must send the value x such that the output of H(m|a|x) is smaller than the following value: $2^{215}$

How many hash functions must Bob compute to find a solution?

• What would you expect? – SEJPM Oct 6 '17 at 22:50
• Hints: the question and the rules governing the body of emails allow $m$ to be the value of $x$ in hexadecimal, or even $x$ itself with some restrictions on $x$ that still leave the task feasible. Cryptographers assimilate bistrings to integers (in big-endian order) without even noticing it, e.g. in expressions like "the output of H(..) is smaller than..", except in carefully written standards and some extra-picky textbooks. The base-two logarithm of the answer is likely less than The Answer. – fgrieu Oct 7 '17 at 15:40

## 1 Answer

See the hash as a $256$-bit number. This number is smaller than $2^{215}$ iff the upper $40$ bits are all $0$.

Suppose that a bit of the output of the hash has an equal chance to be $0$ or $1$....

• ..is smaller than $2^{215}$ (give or take some) iff.. – fgrieu Oct 7 '17 at 16:51