珍しいSHA1ハッシュを追い求めて

雑記

「SHA1ハッシュってあるだろう？」

放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。

「ええ、SHA1、ありますね」

「SHA1って何桁か覚えているかい？」

「えっと…」

一年下の後輩、岡村が口を開いた。

「50桁くらいはありましたっけ…？」

先輩はパソコンに向かって何かを打ちはじめた。

現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。

「例えば、こういうふうに… 適当なSHA1の長さを…」

echo -n | openssl sha1 | awk '{print length}'

部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強したら受かるでしょ、らしい。そう言ってもあまり嫌味には聞こえないのが先輩のいいところだ。

「40だ。40桁だね」

「そうなんですね」

後輩の岡村は身を乗り出して先輩の端末操作を観察している。

「正確には160桁ですよね…」

僕は思わず口を開いた。

「そう、桁というより、160ビット、それを16進数で表現するから…」

先輩はそう言いながらプリント用紙の山から一枚手にとって説明しはじめた。

「こうやって4ビットずつ区切って0からfで表現するから、160ビットのハッシュを40桁で表現できるんだ」

「なるほど〜」

岡村は指を折りながら2進数表現を確認している。岡村の理解が追いついていることを確認しながら先輩は口を開く。

「つまり、SHA1ハッシュは16文字40桁で表現される。つまり16の40乗種類考えられるわけだね。これはもちろん2の160乗と同じ」

そう言いながら先輩はプリント用紙に簡単な式を書く。

「えっと、0.3かけると… これくらいかな…」

16^{40} = 2^{160} \simeq 10^{48}

「10の48乗…たくさんありますね…」

「そうだね、そこそこ多い」

先輩はシャーペンを顔の前で振りながらこう言った。

「そこでだ、SHA1ハッシュで、全てが数字になることはあるだろうか」

全て数字になるSHA1ハッシュ

情報部の活動は、いつもこんな感じで始まる。 誰かが問題を持ち寄って、それを下校時刻までにそれぞれ解く。 今日は部長の出題というわけだ。

空文字のSHA1ハッシュは da39a3ee5e6b4b0d3255bfef95601890afd80709 だ (これはさっき先輩がやってみせたようにecho -n | openssl sha1すると表示される)。これにはdやらaやらeなど、沢山アルファベットが含まれている。 つまり、SHA1ハッシュの16進数表現が、全て数字になるような元メッセージを求めよという問題なのだ。

早速、自分も作業に取り掛かった。 まずどれくらい存在するかを考える。 16文字の中で10文字が数字なので… と言いながらブラウザーのアドレスバーに (10/16)^40 と押してエンターを押した。

\displaystyle \left(\frac{10}{16}\right)^{40} = 6.84 \cdots \times {10}^{-9}

10の-9乗か… しかしSHA1ハッシュから直接元のメッセージを求めるのはできないので虱潰しに調べるしかない…

そんなことを考えながら、プログラムを書き始めた。 メッセージは適当にアルファベットと数字から作って、とにかくsha1ハッシュを計算して条件にあっていれば表示するだけのプログラムだ。 後輩の岡村の様子を見ると、どうやらSHA1ハッシュのアルゴリズムを確認しているようだった。 部長はシャーペンで何やら数式を書いている。

自分のプログラムは、しばらくして次のように出力しはじめた。

gflyP 9708825594493053358052040804954710052563
OqmSX 5405673447021682949913714302263814023323
pcBsd 0830855821698284247230340812332913765683
jPHSf 0747815384663891403181360803310055645039

おお、やはりあるのか…と思いながら、opensslコマンドでハッシュが間違っていないことを確認しながら、プログラムの出力を眺めていた。

「先輩、けっこうありますね…」

「おう、速いな」

「もう計算できちゃったんですか…」

岡村はシャーペンを机に放って、結果を見にやってきた。

「元メッセージはどう選んだんだい？」

先輩は自分が書いたコードを眺めながらそう言った。

「アルファベット大文字小文字もしくは数字です」

「なるほど…」

先輩は、シャーペンを手にとって何やら書き始めた。

「探したのは5桁のアルファベットもしくは数字のメッセージというわけだ。つまり62の5乗は…」

先輩はシャーペンを手に持ったまま、器用にアドレスバーに数式を入れる。

62^{5} = 916132832

「およそ9億個ですね」

「ということは、そのうちSHA1が全て数字になるのは…」

岡村は必至に食いついてくる。

「9億に10/16の40乗をかけると…」

\displaystyle 62^{5} \times \left(\frac{10}{16}\right)^{40} = 6.268 \cdots

「6個です。だいたい」

部長は、後輩の理解が追いついていることに満足そうに頷いた。 それは、自分のプログラムが6桁のメッセージの解を表示しはじめたのと、ほとんど同時だった。

gflyP 9708825594493053358052040804954710052563
OqmSX 5405673447021682949913714302263814023323
pcBsd 0830855821698284247230340812332913765683
jPHSf 0747815384663891403181360803310055645039
IL3rj 3243002591985408609566985352935152776909
MUeWp 8297833274599142233719359578426918109541
JG4Y80 0099530489181060830720140193389029330084
WiMtG0 2254364706744121285147874769100420502311
KMnsR0 4760110574803441139829661498017839123177
...

「つまり今考えているメッセージで5文字で、えっと」

部長がその言葉を遮ってこう続けた。

「アルファベット大文字小文字数字で5文字からなる元メッセージに対して、SHA1ハッシュが全て数字となるのは6つ、およそ期待値通りだね」

岡村も頷いた。

「でも、これに何の意味があるんですかね」

僕は思わず尋ねてしまった。

「意味というのは」

「いや、つまりですよ。SHA1というのは160ビットのバイナリー列って最初に言ってたじゃないですか。この16進数の表現は、なんというか、人間が勝手に4ビットずつ区切って勝手に0からfに割り当てただけじゃないですか」

「なるほど、たしかにそれはそうだね」

「つまり、SHA1ハッシュが数字だろうがアルファベットだろうがSHA1にとっては何の特徴にもならない気がするんです」

「なるほどね」

先輩は頷きながらそう言った。

「でも、それだからこそ、こうやって期待値通り、6個見つかったということにもなるね」

「そこなんですけど…」

岡村が怪訝そうな顔で口を開いた。

「それってつまり、16進数の表現の中で、文字がまんべんなく現れるということを仮定していますよね」

「たしかに」

「本当にそうなんですかね」

先輩はしばらく考えていたが、急に笑顔になって、こう言った。

「SHA1の文字が本当に一様に分布するか、計算してみよう！」

その言葉と同時に、下校時刻を告げるチャイムが鳴った。

SHA1ハッシュの文字分布

家に帰ってから、改めて全て数字となるSHA1ハッシュの計算を再開した。 数字とアルファベット6文字の元メッセージは 62^{6} = 56800235584個あり、その中でSHA1が全て数字となるものは397個あった。 期待値は388.64個なので、少し多めに見つかっていることがわかった。 7文字の中でも計算しようとしたが、時間がかかってプログラムが終了しなかった (後日結果を見てみたら、24061個見つかった。期待値は24095.86個、その誤差は0.15%未満となった)。

夕食後、SHA1ハッシュの文字分布を集計するプログラムを組んだ。 元メッセージは先程の計算と同じように、アルファベット大文字小文字もしくは数字で選んだ。 元メッセージの長さを軸に集計すると、次のようになった。

|X| 0 1 2 3 4 5
0 5 (12.500%) 133 (5.363%) 9551 (6.212%) 595152 (6.243%) 36950623 (6.252%) 2290283302 (6.250%)
1 1 (2.500%) 157 (6.331%) 9648 (6.275%) 595439 (6.246%) 36949237 (6.251%) 2290285498 (6.250%)
2 1 (2.500%) 139 (5.605%) 9539 (6.204%) 596209 (6.254%) 36946427 (6.251%) 2290302477 (6.250%)
3 3 (7.500%) 140 (5.645%) 9598 (6.242%) 596671 (6.259%) 36949064 (6.251%) 2290259456 (6.250%)
4 1 (2.500%) 164 (6.613%) 9727 (6.326%) 596720 (6.259%) 36943267 (6.250%) 2290339043 (6.250%)
5 4 (10.000%) 143 (5.766%) 9586 (6.234%) 595214 (6.244%) 36942983 (6.250%) 2290318196 (6.250%)
6 2 (5.000%) 175 (7.056%) 9673 (6.291%) 595193 (6.243%) 36931008 (6.248%) 2290360368 (6.250%)
7 1 (2.500%) 163 (6.573%) 9558 (6.216%) 595012 (6.242%) 36937662 (6.249%) 2290455010 (6.250%)
8 2 (5.000%) 149 (6.008%) 9691 (6.303%) 595441 (6.246%) 36950679 (6.252%) 2290411313 (6.250%)
9 4 (10.000%) 172 (6.935%) 9658 (6.281%) 596341 (6.255%) 36943415 (6.250%) 2290385579 (6.250%)
a 3 (7.500%) 168 (6.774%) 9797 (6.372%) 596924 (6.262%) 36936091 (6.249%) 2290363615 (6.250%)
b 3 (7.500%) 131 (5.282%) 9611 (6.251%) 595164 (6.243%) 36942624 (6.250%) 2290301647 (6.250%)
c 0 (0.000%) 186 (7.500%) 9417 (6.124%) 596098 (6.253%) 36928976 (6.248%) 2290281914 (6.250%)
d 3 (7.500%) 176 (7.097%) 9571 (6.225%) 596065 (6.253%) 36936884 (6.249%) 2290307306 (6.250%)
e 4 (10.000%) 153 (6.169%) 9567 (6.222%) 595888 (6.251%) 36930409 (6.248%) 2290299939 (6.250%)
f 3 (7.500%) 131 (5.282%) 9568 (6.223%) 595589 (6.248%) 36934091 (6.249%) 2290358617 (6.250%)

右に行くほど、つまり沢山のSHA1ハッシュを調べるほど、全ての文字が均等に現れることがわかる。 ある特定の文字だけ沢山出現したり、少なかったりすることはなさそうだ。 この結果に満足して、僕は就寝についた。

SHA1のSHA1がだいたい数字

「おお、たしかに収束しているようだね」

昨日の計算結果を見せると、先輩は満足そうにそう言った。

「100を16で割って6.25%ですね」

岡村も頷いている。

「まあ証明したわけじゃないが…」

先輩は軽く咳をしてから頭を掻いた。

「SHA1の文字は一様に出現することを仮定して、いろいろな期待値をもとめてみよう」

そう言いながら、先輩はテキストファイルを順番に開きはじめた。

LvwEJe1 6051096335827944381165360280845795286423 111613f48230408056a71706b4174442640b6489
sG9wqMH 9788371029031493501751484666965269206614 e6279615888204167759744340b6c13236273b37
AIJsWgU 4833765415800580402215357543416053382134 823885871864d85103339b7110420321b64b7901
HFrIKpt 1515438875168251864313109613925545684403 820316645881e3020f35e48662206491972878c8
wc9U6dv 5898389906639826050665528530112945836398 5966347988220353b91383721534804a3a278c21

多くの数字が並んでいるが、一番右のSHA1には少しアルファベットが含まれているようだ。

「これはなんですか」

思わず僕は疑問を口にした。

「これは、SHA1ハッシュが全て数字となり、そしてそれをさらにSHA1ハッシュを取った時に、アルファベットが4文字以下となるものだ」

岡村は少し混乱した様子で紙を手に取った。

「つまり…まずは全てが数字で… さらにSHA1ハッシュを取ったら40文字の中で4文字以下がアルファベットとなるので、こうなりますね」

\displaystyle \left(\frac{10}{16}\right)^{40} \sum_{k=0}^{4} {40 \choose k} \left(\frac{6}{16}\right)^{k} \left(\frac{10}{16}\right)^{40-k} = 6.687 \times 10^{-13}

先輩は空中で指を振りながら、計算が間違っていないことを確かめながら口を開いた。

「そうそう、元メッセージは昨日と同様、アルファベットもしくは数字の7文字以下で探索したものだから… その数を掛けて…」

\displaystyle \cdots \times \sum_{i=0}^{7} {62}^{i} = 2.394\cdots

「期待値はこれくらいになる」

「あ、少し低くないですか」

岡村がすぐに指摘した。

「期待値が2.4で、見つかったのが5個ですか」

「まあこういうこともあるさ。次のファイルは」

HQC8su9 03003251839018941492807233288828427481a2 3395664741163489868183a7392270978a505005
VByKdTE 027985658547959903b826850439976465234220 1a3268963b445974667880579063493748834739

「SHA1ハッシュと、そのさらにSHA1ハッシュをあわせた80文字の中で、アルファベットが3文字しか含まれないものだ。2つしか見つからなかった」

\displaystyle \sum_{k=0}^{3} {80 \choose k} \left(\frac{6}{16}\right)^{k} \left(\frac{10}{16}\right)^{80-k} \sum_{i=0}^{7} {62}^{i} = 3.173\cdots

「今度は期待値が少し高いんですね」

僕はファイルのSHA1を見つめ、目を凝らしてどこにアルファベットがあるのかを探しながらそう言った。

「でも、昨日考えていた、全てが数字になるものは期待値通りでしたよね」

「だいたいね」

「要するに、3個とか4個とかの時はあまり合わないけど」

「沢山見つかるほど、見つかった数と期待値の誤差が小さくなるということですね」

「それはまあ、そうだろうね」

岡村は自分のディレクトリに移動してテキストファイルを開いた。

「ところで僕も探索してみました」

ZDyHlIM 5954449490599416666154915409164008649984

そのファイルには一行しか書かれていなかった。

「これは？」

「全て数字なんですけど、7種類の数字しか含まれていないんです」

「なるほど…」

先輩も身を乗り出して後輩が見つけたSHA1ハッシュを眺めている。

「5と9と4と… 0と6、1、それから8で… 確かに7つの数字みたいだね」

「そうなんです。アルファベットと数字7文字以下の文字列のSHA1の中ではこの1つしか見つかりませんでした」

「貴重だね」

僕も感心して思わず軽く口笛を吹いた。

文字連続

先輩は、また計算結果が書かれたファイルを開いてみせた。

dGtWcS d6141925ca72293fba0b5f43000000000000f70b
9J2DJv8 a9fc511111111111125d3d87910d68ddfe350f24
QDi79qF c80b072b3f2c2b6b34cb404cfc2555555555555a
cE2sXYZ d59938cf4afe4effffffffffff6f8181ef568bc1
y1m5aTz b60a1e6666666666665f09a5d8a0c05eb382dca0

「これは、同じ文字が12個連続するところがあるSHA1ハッシュだ」

「おおお」

「それから、13個連続するのも1つ見つけることができた」

rcb0lQv 3333333333333455f30f9a9f761fb8e94b906a0f

「なんかすごい」

「つまり、12個以上連続するものがいま6個あるのだけど…」

そう言いながら先輩はシャーペンを持って期待値を計算しはじめた。

「連続している文字が16通りで、その位置が40-12+1通りだから…」

\displaystyle 16 \cdot (40 - 12 + 1) \left(\frac{1}{16}\right)^{12} \sum_{i=0}^{7} {62}^{i} = 5.900 \cdots

「だいたい期待値通りですね」

岡村は期待値の式を眺めながら数式の意味を追っている。

「他にもこんなものも見つかった」

先輩はそう言いながらファイルを開いた。

w5PPbh5 222222222220101b01d906e32e61373b45265361
bzajR5G 555555555558a91de2fb2fa98af5048bfd887c65
daycahL 2222222222281376525c8dbab5a18e3ca933d5c3
Q4dDYWa fffffffffffa03a907d9650eb91bc99642a86199
2o0XCwe 888888888886d55909a93a870fe44fd91aea5392

「先頭11文字が同じSHA1ハッシュだ」

「おもしろいですね」

「GitHubのリンクで、こんなの見つけたらスクショを取りたくなりますね」

「そうそう、こんなSHA1はおもしろい、ただそれだけでいいと思うんだよね」

さらに珍しいSHA1を目指して

部室に夕日が差し込んでいる。まもなく下校時刻になる。

「色々な性質のSHA1ハッシュが集まりましたね」

岡村は感慨深くため息を付いた。

「そうだね。まず考えたのが全て数字、二回SHA1を取ったもの、それから岡村くんが見つけてくれた、7つの数字しか含まれていないもの、先輩が計算した連続文字…」

「いろいろあるね」

先輩はしばらく夕日を眺めてから、口を開いた。

「全て同じ文字となる確率はどれくらいかな」

岡村はアドレスバーに式を打ち込んで答えた。

\displaystyle 16 \cdot \left(\frac{1}{16}\right)^{40} = 1.095\cdots \times 10^{-47}

「10の-47乗ですね。だいたい」

「なるほど」

先輩は頷きながら暗算してこう続けた。

「SHA1が全て0となる確率は、それを16で割ると、6、いや7かける10の-49乗くらいかな」

「そうですね」

岡村は式を調整しながら答えた。

「じゃあ、いくつSHA1を探したらどのくらいの確率で全て同じ文字のものを見つけられるかな」

先輩は少し意地悪そうにこう言った。

「えっと、さっきのを1から引いて… あれ」

どうやら検索エンジンの誤差で計算できないようだ。僕はすかさずWolframAlphaを開いて計算してみせた。

\displaystyle \left(1 - 16 \cdot \left(\frac{1}{16}\right)^{40}\right)^{10^{46}} = 0.8963\cdots

「10の46乗個探すと、10%の確率で見つかる計算になります」

「1秒に10の7乗個のSHA1を計算できるパソコンがあるとしよう」

岡村はすぐに計算して結果を答えた。

「およそ3かける10の31乗年かかりますね」

「宇宙ができてから確か138億年だよね」

僕がそう言うと、すぐに岡村は計算結果を割って答えた。

「宇宙が10の21乗個できちゃいますね」

「そりゃあ、大変だなぁ」

先輩が夕日を眺めながらそう言うと、下校のチャイムが鳴った。どのくらいの性質のSHA1なら現実的な時間で見つけられるか、そんなことを議論しながら、僕らは帰路に着いた。