ハッシュ関数の強衝突耐性を実感したい！
Spotlight でも活躍中の katakotoさん の依頼で考えてみた。
依頼内容は、
「ハッシュ関数の強衝突耐性を皮膚感覚で実感したい。」
これは非常に難しい、大きな数というのは往々にして皮膚感覚で実感しにくい。例えば 233,280 ㎡ と言われてもよくわからないので、東京ドーム５個分と言われるような感じだ。
しかし今回の話はそんなレベルではない、2 の 256 乗という話だ。
ハッシュ関数などについての説明は間違っているかもしれないが、今回は皮膚感覚で実感できる例えに焦点を当てている、厳密な話は置いておこう、その辺を知りたい方は別のところで調べて欲しい。
問題：
ここに本が１冊ある。この本のページを適当にめくって、開いたページの一番初めに書いてある文字をメモするものとする。
これがハッシュ関数。
何の本の何ページめか言えば初めの１文字を出せるが、
初めの一文字から何の本の何ページめかは逆引き出来ない。
このとき、初めの１文字が同じであるページの組を見つけるには、何回ページをめくれば良いだろうか。
同じハッシュ値を返すページの組を見つけようとしている。
ただし文字は全てひらがなで、ひらがなは50種類あるものとする。
答え：
9 回適当にページをめくれば、
初めの１文字が同じページの組が見つかる確率が 50％ を超える。
17 回めくれば 97％ の確率で見つかる。
50 種類もあるのに意外と早く同じ文字が２回出てくるな、と思っただろうか。試しにその辺にある本でやってみて欲しい。
僕は４回目で出てくる文字が被った。
これを誕生日のパラドックスというそうだ。
この意外と早く同じ文字が出てくるページの組を見つけられることを利用したハッシュ関数への攻撃を誕生日攻撃という。
そして誕生日攻撃に耐えられるかどうかを強衝突耐性というらしい。
答えを出すための確率の計算はこうなる。
何でこうなるかは省略、数 A の教科書を参考にして欲しい。
ちなみに予め探す文字を指定し、初めの一文字がその文字と一致するページを探すとなると格段に大変になる。こちらの方法での攻撃に耐えられるかどうかを弱衝突耐性というそうだ。
計算法はこうなる。
35 回ページをめくれば、
探したい文字で始まるページを含んでいる確率が 50％ を超える。
180 回で 97％ になる。
これは上とは逆に思ったより見つからないものだという感じだ。
話を戻して、同じ一文字で始まるページの組は、たった 17回 ページをめくっただけで 97％ の確率で発見されてしまう。
このハッシュ関数に強衝突耐性は全くないと言って良いだろう。
では、初めの２文字にしたらどうだろうか。
問題：
初めの２文字が一致するページの組を見つけるためには、何回ページをめくれば良いだろうか。
初めの２文字は 50×50 で 2500 パターンある。
計算は上の式の50の部分を2500にすれば良い。
答え：
60 回ページをめくれば 50％ の確率で見つかる。
140 回で 98％ 見つかる。
2500パターンもあるのに？という感じだ。これは誕生日攻撃流行る。
では、さらに。
問題：
初めの３文字が一致するページの組を探すならどうなるか。
初めの３文字は 50×50×50 で 125000 パターンある。
もう電卓を使っても計算したくないだろう。
答え：
417 回で 50％ を超える。
1000 回なら 98％ だ。
人間が手動でさがしているなら、この辺でかなり厳しいが、コンピュータにやらせているのだ、これでもすぐに発見されてしまうだろう。
ハッシュ関数がこんなんで秘密鍵は安全だろうか。
大丈夫だ、なにしろ実際は 125000 パターンどころの話ではない、
2 の 256 乗パターンあるのだ。文字通り桁が全く違う。
では、2 の 256 乗を実感しよう。
文字のパターンが 2 の 256 乗になるように問題を書き直してみる。
問題：
初めの 45 文字が一致するページの組を見つけるためには、何回ページをめくれば良いだろうか。
45 文字の組み合わせは、およそ 2 の 256 乗パターンある。
45文字を求める計算は、
詳しくは数Ⅱの教科書、指数方程式を参考にして欲しい。
さて、試しに適当に机に積んである本をめくってみよう。
京極夏彦ー塗仏の宴ー
「つまりおよそこうとうむけいなりゆうきなのたかそれたけにわたいせいはあるものとみえてさいきん」
ひらがなにして50音の範囲に丸めているが、これで45文字だ。
こういうことを何ページくり返せば、同じ45文字で始まるページの組が見つけられるか、ということである。
いやいやいやいや無理でしょ、と思っただろうか。
そう、無理なのである。
これが誕生日攻撃に耐え得る 256bit ハッシュ関数の強衝突耐性だ。
計算すると、
同じ45文字で始まるページの組が50％の確率で見つかる試行回数は、
となり、2.11×10 の 38 乗 回となる。
これだけの回数ページをめくりまくって見つかるか見つからないか半々の確率だ、これはもう無理だと言っても良いだろう。
ちなみに、この式を導くためには大学レベルの数学が必要なようで、ちょっと挑戦してみたが無理だったので、結論だけ借りている。
実際の 256bit ハッシュ関数の方も計算しておこう。
となるので、
4.26 × 10 の38 乗 回の試行で同じハッシュ値を返す組が見つかる。
ところで、これは強衝突耐性の話である、自分の持っている秘密鍵をハッカーが特定するのは弱衝突耐性の話になるので、上でも書いた通り、これよりも遥かに多い試行回数が必要となる。
これはもう無理だと思わざるを得ないのではないだろうか。
自分の秘密鍵がたまたまハッカーの作った乱数と一致してしまう可能性を考えたくなった場合、部屋の本棚を見て欲しい。そこから適当に本を取り出してページをめくり、初めの45文字をメモしよう。
次に同じ本でも別の本でも適当に開いて、そのページの初めの45文字がたまたまさっきメモした文字と一致する確率を考えてみる。
こんなものたまたまだろうが必死に探し回ろうが一致する訳が無い。
如何でしょうか、僕もこれを書き始める前は、たまたま何となくで被っちゃうことってあるんじゃないの？無いとは言い切れないでしょ。と思っていたのだが、今は、無理無理、それは無理、と意見を変えている。僕の皮膚感覚ではなかなか良い例え話が作れたと思っているのだが、皆さんはどうだろうか。
参考：
何回で50％を超えるかは、最近勉強している Python に計算させた。
import math
def permutations_count(n,r):
return (1 - (math.factorial(n) // math.factorial(n -r)/n**r)*100
n,X = map(int,input().split())
left = 0
right =n
while left < right - 1:
mid = (right + left) // 2
mid_P = permutations_count(n,mid)
if mid_P == X:
left = mid
break
elif mid_P > X:
right = mid
else:
left = mid
print(right)
print(permutations_count(n,right))
ここまでお読みいただきありがとうございました。
