2
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

As previously mentioned, the location of the fixed byte or the number of them doesn't matter if we assume that the output is randomized.

Let's assume bits, so $v = 8 \cdot V$.

Now for one value, the chance of it starting with $k$ bits can be brought down to the chance that the first $k$ bits have a constant value. The size of the hash does not matter. So for one try this is just $1 \over 2^k$.

As the output is randomized, we can also conclude that the outputs are not related; each try has the same chance. In that case it is much like rolling dice, so the computation is similar to one minus the chance of not throwing a 6 in an amount of throws.

So that means that the probability is one minus the chance that the constant value of $k$ bits is not thrown:

$$1 - \bigg({{2^k-1} \over {2^k}}\bigg)^{2^v} = 1 - (1 - 2^{-k})^{2^v}$$

Now this seems daunting, but you can play around with (small) values using WolframAlpha.

Note that if $v$ is becomes larger than $k$ then the probability quickly goes towards 1, while it quickly moves to zero when $k$ becomes larger than $v$ - which makes sense, they are used as exponents after all.

As we assume that SHA-256 already randomizes the output, this seems to have nothing to do with entropy at all, a counter with size $v$ would work just as well as random input - better even since there is no chance of duplicates.

$\endgroup$
1
  • $\begingroup$ Note that WolframAlpha tries to calculate the exact amount; if somebody has a nice approximation (e.g. in $\log_2$ form) then I'm all ears. $\endgroup$
    – Maarten Bodewes
    Jan 19 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.