はじめに
SHA-256, SHA-512などに代表されるハッシュ関数は、ダウンロードしたファイルの同一性を検証する時など、様々な場面、用途で使用されていますが、詳しい性質はあまり意識せずに使用している方も多いのではないでしょうか。この投稿では、そんな縁の下の力持ちとも言えるハッシュ関数の基本的な性質や利用例などを解説したいと思います。
また、本稿を書いた動機の一つとして、ハッシュ関数の重要な概念である「強衝突耐性」、「弱衝突耐性」、「原像計算困難性」の違いについてわかりやすく解説している資料があまり見つからなかったので、自分でわかりやすくまとめようと思った、というのもあります。
非専門家が浅い理解で書いたので、間違いなどあれば指摘していただけると嬉しいです。
ハッシュ関数とは
任意のデータから要約された値（ハッシュ値）を得る関数です。ハッシュ関数のうち、特に暗号、情報セキュリティの用途に適した性質を持つものを暗号学的ハッシュ関数（または一方向ハッシュ関数）と言います。本稿でのハッシュ関数とはこの暗号学的ハッシュ関数のことを指します。
（暗号学的）ハッシュ関数は以下の性質を持ちます。
- 同じ結果を返す
- 高速にハッシュ値を計算できる
- ハッシュ値から元のデータを復元することができない (一方向性)
- 衝突耐性および原像計算困難性を持つ
ハッシュ値は16進数で表されることが多いです。それぞれの性質を順にみていきましょう。
同じ結果を返す
同じアルゴリズムを使用する限り、同じデータを何度変換しても同じ結果となります。
高速に計算可能
実用上、ハッシュ値を求める計算時間は十分短くないといけません。
ハッシュ値から元のデータを復元することができない
ハッシュ値から元のデータを復元することはできません、つまり、あるハッシュ関数 h の逆関数 $h^{-1}$は存在せず、元のデータを知るためにはハッシュ値を総当たり的に計算して、合致するデータを探す必要があります。衝突耐性の項で述べますが、これには膨大な計算が必要になり、この計算量の大きさがハッシュ関数の重要な性能指標の一つになります。
衝突耐性および原像計算困難性をもつ
異なる2つのデータのハッシュ値が同じになった場合、これを「ハッシュの衝突(hash colision)」といいます。
ハッシュ関数は、入力に対し出力の規則性がありません。図は、10桁の数字の末尾1桁のみを変えてSHA-256でハッシュ値を計算した例ですが、ハッシュ値はそれぞれ全く異なる数値になります。したがって、ハッシュを衝突させるデータを効率的に求めることは困難です。
ハッシュの衝突に関する概念として、以下の3つがあります（様々な資料で、これら3つの概念の表記ゆれがありました、CSでの慣習の表記を知っている方がいれば教えてください）。
- 強衝突耐性 (Strong collision resistance)
- 第２原像計算困難性 または 弱衝突耐性 (2nd preimage resistance or Weak collision resistance)
- 原像計算困難性 (preimage resistance)
順を追ってみていく前に、衝突を試みる攻撃に対する強さを表す指標として、セキュリティビットという概念を説明します。
セキュリティビット
暗号分野 (ハッシュ関数は暗号アルゴリズムではありませんが、それについては割愛) には、セキュリティビットというアルゴリズムの安全性を表す指標があります。あるアルゴリズムの攻撃に必要な計算量が $2^n$ のオーダーの時、そのアルゴリズムの安全性は $n$ ビットセキュリティ（n-bits of security）1であるといいます。
この考え方をハッシュ関数に適用します。ある $n$ ビットハッシュ関数（ $n$ ビットのハッシュ値を返すハッシュ関数 ）のハッシュ値が与えられた時、そのハッシュ値となるデータを見つける試行回数のオーダーは、$2^n$ になります ( $2^n$ 回の試行で同じハッシュ値となるデータを見つける確率が十分高い ) 。したがってこのハッシュ関数のセキュリティビットは $n$ です。のちに述べるとおり、誕生日のパラドックスにより、同じアルゴリズムでも強衝突耐性は、弱衝突耐性または現像計算困難性よりもビットセキュリティが小さく、あるハッシュ関数への衝突攻撃でまず初めに破られるのは比較的突破が簡単な強衝突耐性です。
強衝突耐性 (Strong collision resistance)
あるハッシュ関数 $h$ が与えられた時に $h$($m_1$) = h($m_2$)となる 任意の$m_1$, $m_2$ ($m_1$≠$m_2$) を見つけるのが困難。セキュリティビットは$\frac{n}{2}$ビット。
第２原像計算困難性 または 弱衝突耐性(2nd preimage resistance or Weak colision resistance)
ある $m_1$ とハッシュ関数 $h$ が与えられた時に、 $h$($m_1$) = $h$($m_2$)となる 任意の $m_2$ (≠$m_1$) を見つけるのが困難。セキュリティビットは $n$ ビット。
原像計算困難性 (preimage resistance)
あるハッシュ値 $S$ とハッシュ関数 $h$ が与えられた時に、 $S$ と一致する任意の $m_1$ を見つけるのが困難。セキュリティビットは $n$ ビット。
強衝突耐性が他より比較的簡単に破られる理由
以下は、ある $n$ ビットハッシュ関数のそれぞれの衝突耐性とビットセキュリティの対応をまとめた表です。
| 計算量 | ビットセキュリティ | |
|---|---|---|
| 強衝突耐性 | $O$($2^\frac{n}{2})$ | $\frac{n}{2}$ |
| 弱衝突耐性 | $O(2^n)$ | $n$ |
| 原像計算困難性 | $O(2^n)$ | $n$ |
同じアルゴリズムでも、強衝突耐性は弱衝突耐性、現像計算困難性よりも $n$ ビットセキュリティがずっと小さい理由は、誕生日のパラドックスで説明できます。
誕生日のパラドックス
1年は365日とし、部屋にN人の人がいるとき、その中に同じ誕生日の人の組が存在する確率が半分を超える最小のNは?
答えは23人。この時の確率は約50.7%です。ある特定の誕生日の人と同じ誕生日の人を探すのは困難（弱衝突耐性及び原像計算困難性に対応）でも、同じ誕生日を持つ2人を探す（強衝突耐性に対応）のは比較的簡単であるというパラドックスです。
ここで、このパラドックスを一般化し、以下のように考えてみます。
1年をY日とし、部屋にN人の人がいるとき、その中に同じ誕生日の人の組が存在する確率が半分を超える最小のNは？
詳細の計算は割愛しますが、Yが十分大きい時、
N \approx \sqrt{Y} = Y^{\frac{1}{2}}
となります。$n$ビットハッシュ関数の$n$ビットのハッシュ値の総数は $2^n$ 個なので（これが上式のYに対応）、これが十分大きい時、強衝突耐性は $N = n^\frac{1}{2}$ 回の試行でおよそ1/2の確率で破られることになります。従ってビットセキュリティの定義から、強衝突耐性のビットセキュリティは $n/2$ になります。対し、弱衝突耐性及び現像計算困難性は $2^n$ 回の試行で(高い確率で)破られるため、それらのビットセキュリティは $n$ になります。
仮に $n = 256$ とすると、
強衝突耐性を破るための計算回数は、$\approx 10^{77}$
弱衝突耐性及び現像計算困難性を破るための計算回数は、$\approx 10^{154}$
となり、強衝突耐性を破るための計算量は他2つと比べてずっと小さいことがわかります。
Googleの衝突実験
2017年2月、Google はSHA-1アルゴリズムに対し、強衝突耐性を破り、全く同じハッシュ値を持つ2つのpdfファイルが作成できたことを公表しました。SHA-1は160ビットなので、強衝突耐性を破るためには$2^{80}$回の計算が必要ですが、効率の良いアルゴリズムの開発により、 $2^{63.1}$ 回の計算で求められました。2
In total the computational effort spent is equivalent to 2^63.1 SHA-1 compressions and took approximately 6,500 CPU years and 100 GPU years.
ここでは、Googleの用いたアルゴリズムの詳細は述べません。別の機会に勉強してまとめたいと思います。
また、先述の通り、弱衝突耐性を破るためにはずっと大きな計算量が必要となるため、SHA-1の弱衝突耐性は今のところ (2021年6月現在) 破られたという報告はありません。
ハッシュ関数の使用例
デジタル署名
デジタル署名は、送信データの送信者の真偽と、改竄の有無を検証し証明する、ハッシュ関数と公開鍵暗号を組み合わせた仕組みです。
- 送信者Aは送信するメッセージをハッシュ化し、さらにAの秘密鍵で暗号化したものをデジタル署名としてメッセージと合わせてBへ送付する。
- 受信者Bは受信したデジタル署名をAの公開鍵で復号化(a)し、メッセージのハッシュ値(b)と比較する。
- (a)と(b)が一致していれば、メッセージは間違いなく（衝突耐性が破られ、かつ公開鍵暗号が破られていない限り）Aが送信したものであり、改ざんもされていないことが証明できる。
Aの秘密鍵で暗号化することにより、データの送信者がA本人であることを証明し、メッセージのハッシュ値を計算することにより、途中で改竄されていないことを証明しています。
その他
衝突のないハッシュ関数は存在しない
原理的に衝突の発生しないハッシュ関数は存在しません。
なぜかというと、例えば $n$ビットハッシュ関数のハッシュ値の総数は$2^n$個なので、$2^n + 1$ だけ試行すれば、鳩の巣原理よりある2つのハッシュ値は必ず重複するからです。
鳩の巣原理
N+1羽の鳩をN個の巣箱に分けると、鳩が2羽以上いる巣箱が少なくとも1個は存在する
hashの語源
ハッシュの語源はフランスの古語 (古:hatchet, 現代:hache) で「斧」という意味です。この古語から英語 (hash) では、細切れ肉、細切れ料理という意味になっています（ハッシュドポテトもこの意味のつながり）。3
参考文献・動画
結城浩 『暗号技術入門 第3版 秘密の国のアリス』SBクリエイティブ, 2015年, p.169-204
第7章「一方向ハッシュ関数」を本稿の参考にしました。特に誕生日のパラドックスの解説がわかりやすかったです。hashアルゴリズムとハッシュ値の長さ一覧（＋ハッシュ関数の基本と応用）
各アルゴリズムの特徴および基礎の説明がとてもわかりやすかったです。How We Created the First SHA-1 Collision and What it Means for Hash Security
GoogleのResearch Team の方によるSHA-1衝突実験の解説動画(YouTube)です。衝突耐性に関係する3つの概念の違いがわかりやすかったです。