🔖

ハッシュ値が衝突する確率について with 誕生日攻撃

2023/05/21に公開

確率

SHA-256

tech

はじめに

過去に書いたネタ記事が最近バズっていた。
$6^{99}$ と $2^{256}$ の値が似ているなぁということに気づいて、ぱっと書いた記事。

なので、ある特定のハッシュ値と衝突する確率を求めただけになっていたが、コメントで「沢山ハッシュ値を生成して、その中で衝突する場合はどうなるの？」ともらった。

そりゃ気になるよね。僕も気になる。
...求めてみよう。

今回考えること

SHA256 によってハッシュ値を取ることを想定する。この際、 SHA256 が取る値は一様にランダムとする。
$n$ 個生成したとき、ハッシュ値が衝突する確率考える。

衝突の確率

衝突の確率は、誕生日攻撃と呼ばれるもので求められている。

$H$ を全体の要素数(今回は $2^{256}$ )で $n$ を生成数としたとき、途中にある近似式、
$p(n; H) \approx 1 - e ^ {-n(n-1)/2H}$
を使えば簡単に求められる。

.
.
.
と、思うじゃん？
近似式を使う時、近似できる条件と、近似の精度を気にする必要がある。

近似確率

そもそも、その近似式の出所は、英語版の誕生日攻撃に引用元が書かれていた。
その論文の p273-274 の "THE BIRTHDAY PROBLEM" という付録Aに導出過程が記されている。

そこを読む限り、近似できる条件に $H$ と $n$ には制約はなさそうである。近似の精度に関しては、

$1 - e ^ {-n(n-1)/2H} < p(n; H) < \frac{n(n-1)}{2H}$

という評価ができる。また、 $1 \le n \le \sqrt{2H}$ のとき、

$0.3 * \frac{n(n-1)}{H} < p(n; H)$

という評価もできる。

実際に求めてみる

上界と下界が分かったので、実際に求めみる。
wiki の表によると、256bit で $4.8 * 10^{29}$ 個生成すると、衝突する確率が $10^{-18}$ になるとのことなので確認する。

import math

def getProbableRange(h, n):
    upperBound = n * (n - 1) / (2 * h)

    lowerBound1 = 1 - math.exp(-n * (n- 1) / (2 * h))
    lowerBound2 = 0
    if n * n <= 2 * h:
        lowerBound2 = 0.3 * n * (n - 1) / h

    lowerBound = lowerBound1 if lowerBound1 > lowerBound2 else lowerBound2

    return (lowerBound, upperBound)

h = 2 ** 256
n = 4.8 * 10 ** 29

(lowerBound, upperBound) = getProbableRange(h, n)
print("n = 4.8 * 10 ** 29")
print(f"{lowerBound} < p < {upperBound}")

n = 4.9 * 10 ** 29
(lowerBound, upperBound) = getProbableRange(h, n)
print("n = 4.9 * 10 ** 29")
print(f"{lowerBound} < p < {upperBound}")

結果は下記のようになった。wiki の表は上界の値を元に作成されていそう。近似の精度もそれなりにありそう。
(本来はいろんな値を見るべきだが今回は省略)

n = 4.8 * 10 ** 29
5.969319705281278e-19 < p < 9.948866175468797e-19
n = 4.9 * 10 ** 29
6.220632210234529e-19 < p < 1.0367720350390882e-18

確率から個数を求める

上では $n$ 個生成した際に衝突する確率を求めたが、逆に衝突確率 $p$ を与えたときに何個なのかというのを求める。上で見た通り wiki の表が上界の値で計算されているので、それに倣って上界の値を使う。

def getMaxNumberUnderProbabilty(h, p):
    f = lambda h, p, a, b: a if b - a <= 1 else f(h, p, (a + b) // 2, b) if getProbableRange(h, (a + b) // 2)[1] < p else f(h, p, a, (a + b) // 2)
    return f(h, p, 1, h)

h = 2 ** 256
p = 10 ** -15

n = getMaxNumberUnderProbabilty(h, p)
print(f"{n:.2E}")

実行結果は下記。

1.52E+31

wiki の表の 256bit と $10^{-15}$ のところを見ると合っていそう。

確率の比較

今回は前回の表を元に、SHA256のハッシュ値を $n$ 個生成したときに衝突する確率を並べてみた。

事象	10の累乗表記	同時生成数
ロイヤルストレートフラッシュ	$1/10^{4.83}$	$1.85*10^{36}$
天和	$1/10^{5.52}$	$8.36*10^{35}$
2択20問のテストででたらめ回答で0点	$1/10^{6.02}$	$4.70*10^{35}$
宝くじ一等	$1/10^{7.00}$	$1.52*10^{35}$
何もせず6Vが生まれる(ポケモンの話)	$1/10^{9.03}$	$1.47*10^{34}$
天和四暗刻大四喜字一色	$1/10^{15.0}$	$1.52*10^{31}$
センター国語(2020)で適当回答で満点	$1/10^{24.0}$	$4.81*10^{26}$
40人クラスの席替えが席替えにならない	$1/10^{47.9}$	$5.40*10^{14}$
54枚のトランプが購入時の並び順になる	$1/10^{71.4}$	$96$
100個のサイコロ振ってゾロ目	$1/10^{77.0}$	$2$
ある1つの SHA256 が衝突する	$1/10^{77.1}$	$2$

サイコロ振りたい

追加で実用的な面から衝突する確率を求めてみる。
下記の仮定の元で、全世界の人が一生の間ハッシュ値を生成し続ける。

世界人口: 100億人
平均寿命: 100年
1秒間の生成数: 100個
1年: 365日(31536000秒)

つまり $n = 3.1536 * 10 ^ {21}$ である。その際、衝突確率は、

2.5756705139739875e-35 < p < 4.2927841899566463e-35

の間になる。一方、 $6^{44} = 5.77 * 10 ^ {-35}$ となるので、サイコロ45個振ったときにぞろ目が出る確率に近くなる。

実際にサイコロ45個振ってみた

前回よりもインパクトが減るが振ってみる。

私を振ってんじゃないよバカ
振っていいわけがないでしょう

という歌が聞こえてくるがお構いなし。

45個のサイコロを準備した。

それを手にもって振る！

その結果...
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

全部ピンじゃねぇかっ・・・！

.
.
.
.
.
.
.
.
.
.
.

まぁ、そんなわけないよね。

あとがき

同じネタを繰り返すことを天丼という。

宣伝

麻雀の待ちについて研究した記事。