How to calculate the odds of finding "20" at least three times in a sha256 string?

Question

For example, what are the odds of this happening:

Can this even be calculated?

Answer 1

If we assume that the output of a SHA-256 hash is roughly random, this is ultimately just a combinatorics problem. That is:

Given a random string of 64 hexadecimal digits, what is the probability that the sequence "20" appears 3 or more times.

We can think of this as having three set items, the three "20"s, and then 58 other hexadecimal characters distributed around them. That gives us four spots to put the rest of the numbers:

$$ X_1\ |\ 20\ |\ X_2\ |\ 20\ |\ X_3\ |\ 20\ |\ X_4 $$

Where $X_n$ is a string of hexadecimal digits with size ranging 0 to 58, with $\sum_{i=1}^n len(X_i) = 58$ and "|" denoting concatenation.

After seeing kodlu's answers I figured I would include a more complete answer.

The above ultimately led me down the path of counting all possible 58-hexadecimal-digit strings and then counting the ways we can "insert" the 20's throughout it. The number of random strings is $16^{58}$. We can insert 20's at the beginning or after any of the digits, and there are 3 inserts required. Since we want to allow repetitions (sections without any digits between the 20's) we want ${58 + 3 - 1 \choose 3} = {60 \choose 3}$ (see combinations with repetition). Dividing that by the total number of SHA-256 hashes, we get:

$$ \frac{16^{58} \cdot {60 \choose 3}}{2^{256}} \approx 0.00203967 \approx ~0.204\% $$

Just to see if this made sense, I ran a quick test using bash to see how this panned out:

#!/bin/bash

function next() {
    head -c 32 /dev/urandom | xxd -p -c 64
}

total=100000

count=0
i=0
while [[ $i -lt $total ]]; do
    next | grep -q "20.*20.*20" && let count="$count+1"
    let i="$i+1"
done

echo "$count / $total"

I ran this a few times and got:

$$175 / 100000 = 0.175 \%$$ $$200 / 100000 = 0.200 \%$$ $$187 / 100000 = 0.187 \%$$

So this seems about right.

---

A couple notes on the properties of this. As kodlu mentioned, since "20" is not symmetrical, we don't have to worry about things like "FFF" potentially counting as two instances of "FF" if that's what we were looking for. However, if we don't want to count that as two, my approach should still work, even if we were using a symmetric target string like "FF" or "00".

Also, since we are looking for "at least" 3 occurrences of "20" in the string, we don't have care about whether any of $X_1, ..., X_4$ contain a 20, those are just extra. In fact, this is exactly why this approach works. That said, we may end up double counting in cases where our variant placements of 20s don't really change the ultimate string. For example, if the 58-digit string is "202020202020..." there are many places we could insert our three "20's" without actually changing the resulting string. Accounting for that could prove tricky, and I'm not sure how to do so at the moment, but given the extremely large number of cases we're looking at I'm inclined to think this is probably relatively small. Although it's not hard to come up with other examples, so caution is good. Regardless, this type of thing is exactly why I wanted to include a more empirical approach (i.e. brute-force counting with code).

On that note, I decided to run another, longer test (with 1,000,000 values) to see if it might be closer to my updated probability than my original one. Or at least further confirm that we're in the right ballpark. I got:

$$ 1797 / 1000000 = 0.001797 = 0.1797 \% $$

So, for what it's worth, it seems like the answer is at least "somewhere between 0.17% and 0.20%."

Answer 2

Based on how you said "at least 3 times", first note that there are $16^2=256$ possible consecutive hex values. Let's find the probability that this happens at most 2 times and subtract from 1. Let $q=255/256$ be the probability that $\sf 00$ doesn't occur at some random point.

So the probability this pattern $\sf 20$ never occurs in a random SHA256 output is $q^{63}$ since there are 63 starting positions possible. This probability is not that small, it's about $0.7815.$

Probability that the pattern occurs exactly once is $$\binom{63}1 q^{62}(1-q)=63 q^{62}(1-q)\approx 0.1931$$ and the probability that it happens exactly twice would be $$\binom{63}{2}\cdot q^{61}(1-q)^2\approx 0.0234$$ if the binomial model applied directly. Instead we use $$\frac{63\cdot 60}{2} q^{61}(1-q)^2 \approx 0.0227$$ see the explanation below.

Let's subtract these 3 probabilities from 1, to get the answer $ 0.002744 $ as the probability that the pattern $\sf 20$ occurs at least 3 times. This probability is not that small, roughly one in 364.

Notes: The expression for exactly two occurences is only approximate since if the pattern occurs starting in position $k$ this rules out $k-1$ and $k+1$ as starting positions as well so there are actually $63-3=60$ starting positions left. We then need to divide by 2 and use $63\cdot 60/2$ instead of $\binom{63}{2}$ to avoid counting twice. This is actually still approximate since the two ends have slightly different probabilities so actually at the two ends we should use 61 instead of 60 as the second factor but overall effect is minute.

Note that the analysis may be slightly different for other patterns but for the parameters of "at least 3" this won't make much difference to the overall answer.

The pattern $\sf 20$ is special since it doesn't overlap with itself. This depends on exactly how you count, but if the pattern was $\sf 00$ it can overlap with another $\sf 00$ if you have the pattern $\sf 000$ somewhere and two $\sf 00$ one to the left and one to the right if you have a $\sf 0000$ somewhere in the output.

Answer 3

TL;DR: Odds of finding at least three times 20 in the expression as hexadecimal of a SHA-256 hash are below $1/545$, and above $3/1636$. Probability is $0.0018305\ldots$.

We are making the assumption that SHA-256 is a Pseudo Random Function (which is believed true from a computational perspective) and is fed with an input chosen without making use of the definition of SHA-256 to winnow input (which is not stated).

---

Let $n[i,j]$ be the number of distinct strings of $i$ hexadecimal digits with exactly $j$ occurrences of 20. It holds $n[0,0]=1$ and $n[1,0]=16$. It holds (or we define, for negative indices) $n[i,j]=0$ when $j<0$ or $i<2j\,$.

When we append one digit to strings of length $i>0$, strings of length $i+1$ with exactly $j$ occurrences of 20 can be formed in three exclusive ways:

• By appending one of the 15 digits other than 0 to any of the $n[i,j]$ strings of length $i$ with exactly $j$ occurrences of 20.
• By appending a 0 to any of the $n[i-1,j-1]$ strings of length $i$ with exactly $j-1$ occurrences of 20 and ending in 2.
• By appending a 0 to any of the $n[i,j]-n[i-1,j]$ strings of length $i$ with exactly $j$ occurrences of 20 and not ending in 2.

Hence when $i>0$, it holds $n[i+1,j]=16\,n[i,j]+n[i-1,j-1]-n[i-1,j]$. And by examination of the case $i=0$, that holds for $i\ge0$, and makes $n[1,0]=16$ redundant. This yields e.g. $$\begin{array}{r|rrr} n[i,j]&j=0&j=1&j=2\\ \hline i=0&1&0&0\\ i=1&16&0&0\\ i=2&255&1&0\\ i=3&4064&32&0\\ i=4&64769&766&1\\ i=5&1032240&16288&48\\ i=6&16451071&324611&1533\\ i=7&262184896&6209728&40768\\ i=8&4178507265&115482108&975366\\ i=9&66593931344&2103688896&21774816\\ \end{array}$$ The probability $p$ that at least three 20 occur is $$p=1-\sum_{0\le j<3}n[64,j]/2^{256}\quad\approx\;0.0018304972246326$$

The odds are $p/(1-p)$. Continued fractions allow to give compact and increasingly precise approximations of the odds, including $1/545$ and $3/1636$.

In Mathematica (try it online!):

n[0,0] = 1;
n[i_,j_] := n[i,j] = If[j<0||i<2j, 0, 16n[i-1,j]+n[i-2,j-1]-n[i-2,j]];
p = 1 - Sum[n[64,j], {j, 0, 2}]/2^256
N[p, 14]
odds = p/(1-p)
FromContinuedFraction[ContinuedFraction[odds,2]]
FromContinuedFraction[ContinuedFraction[odds,3]]

211957097983322227623903608563706242318359649398468817819333331057325977135/115792089237316195423570985008687907853269984665640564039457584007913129639936
0.0018304972246326
211957097983322227623903608563706242318359649398468817819333331057325977135/115580132139332873195947081400124201610951625016242095221638250676855803662801
1/545
3/1636

The answer would be slightly higher for 00, because the two characters are identical. It would be considerably lower if it was added that the two characters must be byte-aligned in the hash (as considered in this answer). It would be much higher for finding a two-characters string appearing at least three times (as considered in this comment).

Answer 4

A sha-256 hash is 32 bytes. Each byte has a possibility of 256 different byte values. And I'm assuming when you indicate that "20 occurs", you mean it's in a byte position (ala 34 20 56...), and not straddling a pair of bytes as in 32 00 45...

So if we can compute the totals combinations of that a particular byte value appears in 0 bytes, 1 bytes, and 2 bytes of a sha256 array, we can surmise the right probability.

Let x = 256³², which is the the number of unique 256-bit values in a 32 byte array. (Or more precisely, the same as 2²⁵⁶, the number of sha256 hashes)

Let y = the number of occurrences in which all 32 bytes are not this given value of 0x20, but are one of the remaining 255 valid values: 255³²

Let z = the number of occurrences in which 0x20 appears in exactly one byte within the 32 byte array. There's 32 possible slots for the 20 byte to exist. The remaining 31 bytes can have 255 different value each. Hence, z=32*255³¹

let w = the number of occurrences in which 20 appears exactly in two bytes. Basic combinatorics:

32!
-------    ==  32*31/2 == 496
30! 2!

496 unique placements for two values of 20 in an array of 32 positions. Multiplied by the available combinations for the remaining 30 bytes. So w = 496 * 255³⁰

Now for probability

                   y + z + w
P =          1 - --------------
                       x

Launch Python to help us out with the math:

>>> x = 256**32
>>> y = 255**32
>>> z = 32 * 255**31
>>> w = 496 * 255**30
>>> P = 1 - (y+z+w)/x
>>> P
0.0002715886651215582

So the probability of 3 or more occurences of a given byte value appearing in a 32 byte array is 0.0002715886651215582 or approximately .0271%