# A query regarding SHA256 output hash structure vs input entropy?

Given an Input string of N bytes where some bytes positions in the string are fixed/immutable (F Bytes) and rest of the bytes positions can contain any value as we want or are configurable/variable (V = N-F Bytes).

SHA256(SHA256(N)) = H (256 bits).

Now, Given an Input string of N bytes, the values of N, F, V and the positions which can change and which can't:

How do we calculate the probability/formula that for at least 1 assignment of values in V, the calculated H has k leading bytes as 0?

For eg: For a random input string of size N, N=80, F=40, V=40 (assuming the position information is also given) how do we know/calculate the probability that for at least 1 assignment of values in V first k bytes of H are 0?

I tried searching for some analysis on this but couldn't find any answer. Can someone please help?

## 1 Answer

The analysis is provided by the Left Over Hash lemma.

Positions of F are irrelevant. That's just called a bit fixing entropy source, and the extractor function completely subsumes F. So $$P(H_k=0)$$ is as if the output was random, but biased:-

$$P(H_k=0) = \big(\frac{1}{2}- \epsilon \big)^k$$

where $$\epsilon$$ is the bias. Just plug the numbers into $$\epsilon = 2^{-(sn-k)/2}$$, to get $$P(H_k=0) =\big(\frac{1}{2}- 2^{-32} \big)^k$$. NIST would not consider this source as perfectly random.

Is this a cryptocurrency question?

• Thanks a lot. Firstly yes its a cryptocurrency question and I don't have much theoritical background in crypto. When you say $P(H_k=0)$ I interpret it as probability that first $k$ bytes are 0 in $H$. but in my humble opinion that isn't the question. If $V$ is 1 byte for $N$=80 the probability $P(H_k=0)$ w.r.t. $V=N$ bytes in input the probability $P(H_k=0)$ would be different since potential allowed input range changes dramatically. That probabilty depedence on $V$ for a input of size $N$ (very specifically V=40, N=80) and in general too is the value I was asking about? Aug 21 at 15:13
• Am I missing something? Aug 21 at 15:27
• No, you have it exactly :-) This concept isn't tied to crypt£. It's just statistics. Forget F. The probability of a 'run' of $n$ zeros is $\frac{1}{2^n}$. But since source N is not entirely random, a bias occurs. That's the $\epsilon$ in the lemma. Read the paper. Aug 21 at 17:14
• Apologies for testing your patience. I did try to read though the paper in last half an hour or so and I simply do not have that sort of background. i understand the concept of bias (but not in here). what i was wondering was if we could have a formula for probability $P(H_k=0)$ based on how many bytes we are allowed to manipulate in $N$ (denoted by $V$). i am failing to see the variable $V$ in the eqn. you have used $s$ which i am not sure of what it represents? Aug 21 at 17:31
• It's not my patience. It's my sobriety. Which is going down hill rapidly. Aug 21 at 17:48