3
$\begingroup$

For example, what are the odds of this happening:

09200b3ccbaef58e20f6c596a800edc93c3ff0e6c4c8865cf7bd520546408f15

Can this even be calculated?

$\endgroup$
2
  • $\begingroup$ Can we assume that the byte pattern, 0x20, only is counted as appearing in the string if it starts on byte boundary. E.g. "01 20 30 40 50..." would be an instance of 20 appearing in a string, but "90 12 03 04 05 06..." would not since the 2 and 0 are not within the same byte? Correct? Or is the latter string a valid appearance of "20 appearing in a string" ? $\endgroup$
    – selbie
    Sep 22, 2020 at 21:24
  • 1
    $\begingroup$ @selbie The third "20" in the given example does not appear to be byte-aligned in that way, which I take to mean that either way is fine. $\endgroup$ Sep 22, 2020 at 21:52

4 Answers 4

6
$\begingroup$

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%."

$\endgroup$
4
  • 2
    $\begingroup$ nice approach, always liked bars and stars... $\endgroup$
    – kodlu
    Sep 22, 2020 at 5:30
  • 4
    $\begingroup$ This answer is approximately correct, but mathematically still wrong because it double-counts many strings (since the 58 decimal digits could contain 20 themself), and also doesn't consider the case of multiple 20's in a row. Additionally, since 20 is extremely arbitrary, it's likely OP is actually interested in the odds of seeing any digit-pair repeated 3 times, which is significantly higher. $\endgroup$ Sep 22, 2020 at 9:22
  • $\begingroup$ @BlueRaja-DannyPflughoeft I think I've fixed some of the things you mentioned and at least addressed the others in an edit. I ultimately think you're right though, there is still some double-counting happening (which is a shame because I still ended up revising my answer upward)... Regardless, I think we at least have some nice evidence that this is probably close enough for most purposes (e.g. evaluating the security of a scheme). $\endgroup$ Sep 22, 2020 at 12:35
  • $\begingroup$ I agree with probability between 0.17% and 0.20%, as I get 0.18305…% $\endgroup$
    – fgrieu
    Sep 22, 2020 at 16:01
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ "but overall effect is minute": is it? When the answer introduces $q^{63}$, it assumes the 63 events of probability $q$ are independent. But if there is a 20 starting at the first position, it is certain that there is not one in the second. Knowing there is not a 20 starting in the first position, the probability that there is a 20 starting at the second position becomes 1/255 rather than 1/256. A better estimate of the quantity given as "about $0.7815$" is thus $\frac{255}{256}\left(\frac{254}{255}\right)^{62}\approx0.7807$. That has quite a significant effect on the final result. $\endgroup$
    – fgrieu
    Sep 22, 2020 at 6:25
  • $\begingroup$ Computing things exactly, I get odds roughly one in 545, rather than roughly one in 364. $\endgroup$
    – fgrieu
    Sep 22, 2020 at 16:13
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ That's a neat approach! Definitely didn't expect continued fractions to come up when I first saw this question. :) $\endgroup$ Sep 22, 2020 at 18:02
  • $\begingroup$ @thesquaregroot: to be honest, continued fractions come up only to express the odds (rather than probability) in an optimally compact form. $\endgroup$
    – fgrieu
    Sep 22, 2020 at 18:04
1
$\begingroup$

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 = 25632, which is the the number of unique 256-bit values in a 32 byte array. (Or more precisely, the same as 2256, 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: 25532

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*25531

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 * 25530

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%

$\endgroup$
1
  • 1
    $\begingroup$ In the question's example, the last of the three 02 highlighted is "straddling a pair of bytes", thus this is answering a variant of the question, correctly as far as I can tell. That's why you are obtaining a much smaller value than the other answers. Call me a purist but when stating "approximately" I round probabilities to the nearest, here .0272% rather than .0271%. My daughter's physic's teachers insist on that (they want 0,0272%, but that's France). $\endgroup$
    – fgrieu
    Sep 22, 2020 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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