ハッシュ関数を理解する
まえおき
暗号通貨、ブロックチェーンをある程度勉強すると必ずハッシュ関数の話が出てきます。アドレス生成、署名などはもちろん、TLSにおけるデータの整合性の確認などにも使用されるなど、今日のインターネットにおける重要な基盤技術です。これからブロックチェーン技術について深く理解したいという方に向けて、本記事では必要最低限の内容をまとめました。
ハッシュ関数とは
その名からも予想できるように、関数の一種です。関数ですからある入力に対応した出力が得られます。ではハッシュ関数ではどのような入力に対して、どのような出力が得られるのでしょか。性質としては以下が求められます。（ハッシュ”hash”には『切り刻む』『細かくする』という意味があります。 ）
- 任意長のデータ（SHA-256なら2^64ビット未満、SHA-384,SHA-512は2^128ビット未満）に対し、固定長の出力
- 同じ入力に対して同じ出力
また、ブロックチェーンでは暗号学的ハッシュ関数が使われます。以下のような安全性を満たすハッシュ関数がそう呼ばれます。
- 一方向性（原像計算困難性）
- 第２原像計算困難性
- 衝突困難性
任意長のデータに対し、固定長の出力を出す
実際にビットコインで使われているSHA-256（シャ-ニゴロと読みます）を例に見てみます。
入力：1
出力：6B86B273FF34FCE19D6B804EFF5A3F5747ADA4EAA22F1D49C01E52DDB7875B4B
入力：1234567890
出力：C775E7B757EDE630CD0AA1113BD102661AB38829CA52A6422AB782862F268646
１桁でも１０桁でも全く同じ長さです。試しにこちらで色々試してみてください。必ず任意の長さの入力に対し、任意の固定長の出力をするように設計されています。
同じ入力には同じ出力
そのままの意味です。1という入力に対し、3という値が出てきたとします。この後もう一度1という値を入力したらどうなるでしょうか。もちろん3ですね。何を当たり前なことをと言われるかもしれませんが、これにより入力に対する出力がの検証などを行うことが可能になります。そのためとても大事な性質です。
＊数学的関数ならば自明な性質ですが、本記事で述べているハッシュ関数はCSにおける関数です。そのため参照透過性を必ずしも持つ訳ではありませんが、ハッシュ関数はそれを満たすという意味を強調するために記述しています。
一方向性（原像計算困難性）
出力されたh(m)から入力したmを求めることは非常に困難であるという性質です。簡単に言うなら出力から入力を求めることは困難ということです。これは総当たり以上に効率的なアルゴリズムが存在せず、かつ総当たりの探索空間が非常に大きいためです。
例えば
4A44DC15364204A80FE80E9039455CC1608281820FE2B24F1E5233ADE6AF1DD5
という出力が得られた時、どんな値が入力されたかわかりますか？おそらくわからないですね。このように、逆算が不可能であるという事が求められます。
第２原像計算困難性
ある入力 mと、そのハッシュ値h(m)が与えられた時、同一のハッシュ値になる別の入力を計算することは困難であるという性質です。例えば先ほど10を入力したときのハッシュ値で考えた時、これと全く同じハッシュ値になる入力を見つけるのは非常に困難であることを指します。
衝突困難性
同じハッシュ値h(m) をとるようなメッセージ(m,m’) の組を一つでも見つけることは非常に困難という性質。先ほどの第２原像計算困難性と似ていますが別物です。
またメッセージは異なるが、ハッシュ値が同じになる現象を”ハッシュ値の衝突”と言います。
第二原像計算困難性と衝突困難性の強弱
2つの異なるデータから同じハッシュ値が出た場合、これを衝突と言います。この衝突を意図的に起こすそうとする攻撃者がいた場合、第２原像計算困難性と衝突困難性、どちらが攻撃しやすいでしょうか？
答えは「衝突困難性」です。これは誕生日のパラドックスを例に考えるとわかりやすいです。
誕生日のパラドックス（たんじょうびのパラドックス、英: birthday paradox）とは「何人集まれば、その中に誕生日が同一の2人（以上）がいる確率が、50%を超えるか?」という問題から生じるパラドックスである。出典：Wikipedia（誕生日のパラドックス）
1年を365日とし、ある40人のクラスがあったとします。この中で自分と同じ誕生日の人が見つかる確率 pは、1から自分と同じ誕生日の人がいない確率を引けばよいので
40人クラスなら、自分と同じ誕生日の人は0.1ぐらいの確率でいることになります。
では"同じ誕生日の人の組"がいる確率p'はどれくらいでしょうか。
なんと9割ほどいることになります。この同じ誕生日の人が見つかる状態は、ハッシュ値が見つかる状態と同じです。
つまり衝突困難性（＝同じ誕生日の人の組を探す）方が攻撃しやすく、第二原像計算困難性（＝自分と同じ誕生日の人を探す）方が攻撃しにくいということです。
攻撃しにくいということは安全性が強く、攻撃しやすいということは安全性が低いということですね。
ではハッシュ関数に対して安全性を求める（衝突しにくい）場合、第２原像計算困難性と衝突困難性のどちらを満たす事が求められるでしょうか。
答えは「衝突困難性」です。元々攻撃に弱い方の安全性が強ければハッシュ関数もより安全だからです。
よってここから衝突困難性を「強い意味での衝突困難性」、第二原像計算困難性を「弱い意味での衝突困難性」と呼びます。
３つの安全性を破るための計算回数
ここまで述べてきた暗号学的ハッシュ関数に求められる3つの安全性ですが、これらを破ろうとした時どのような攻撃方法が考えられるでしょうか。おそらく真っ先に思いつくのは「とりあえず計算しまくる」でしょう。では一体どれくらいの計算が必要でしょうか。詳しい過程は省きますが、ハッシュ値が n ビットのハッシュ関数の場合、理論上の期待値は以下のようになります。
例えばSHA-256を破ろうとした時、一番簡単な衝突困難性でも2^128 回の計算が必要になります。大体340,282,366,920,938,463,463,374,607,431,768,211,456 (39 桁)＝340 澗 2823 溝 6692 穣 938 じょ※ 4634 垓6337 京 4607 兆 4317 億 6821 万 1456回計算すれば一回は当たるよ。という感じです。
現在世界最速のパソコンで1秒あたり20京の計算ですので、大体2000京年ぐらいかかります（たぶん）。
まとめ
最後の衝突困難性の強弱は理解するのに頭を悩ます部分かと思います。何度も考えれば少しづつ理解できますので、焦らずじっくり考えて理解しましょう。より詳しく知りたい方は「暗号技術のすべて」という本がオススメです。数学知識を身につけてから読むといいと思います。
また、「理論上はできるが現実的に無理」という話を聞いて「理論上できるなら危ないだろ！」みたいに思った時はこの話を思い出して落ち着きましょう。万が一そういう人に出会ったら腹パンしてしばらく眠らせておきましょう。
参考資料
- 暗号技術のすべて
- ブロックチェーン・プログラミング 仮想通貨入門 (KS情報科学専門書)
- https://moblock.jp/articles/17868
- https://github.com/herumi/ango-src/blob/master/hash.tex
- http://darutk-oboegaki.blogspot.com/2014/04/2-256.html
- https://www.nikkei.com/article/DGXMZO31576630Z00C18A6000000/
お知らせ
■HashHubでは入居者募集中です！
HashHubは、ブロックチェーン業界で働いている人のためのコワーキングスペースを運営しています。ご利用をご検討の方は、下記のWEBサイトからお問い合わせください。また、最新情報はTwitterで発信中です。
HashHub：https://hashhub.tokyo/
Twitter：https://twitter.com/HashHub_Tokyo
■ブロックチェーンエンジニア集中講座開講中！
HashHubではブロックチェーンエンジニアを育成するための短期集中講座を開講しています。お申込み、詳細は下記のページをご覧ください。
ブロックチェーンエンジニア集中講座：https://www.blockchain-edu.jp/
■HashHubでは下記のポジションを積極採用中です！
・コミュニティマネージャー
・ブロックチェーン技術者・開発者
・ビジネスディベロップメント
詳細は下記Wantedlyのページをご覧ください。
Wantedly：https://www.wantedly.com/companies/hashhub/projects
