Chapter 18

ハッシュ関数・MAC・デジタル署名

この章の位置づけ. 暗号の役割は秘密を守ることだけではない。実務では「データが改ざんされていないか」「本当にこの人が作ったのか」を確かめる場面のほうが多い。パスワードの保管、ソフトウェアの更新、電子契約、ブロックチェーンは、どれも秘密にすることより、完全性（改ざんされていないこと）と認証（誰が作ったか）が主な目的である。 09 章 7 節で CRC は改ざん検知に使えないこと、14 章 8 節で暗号化だけでは改ざんを防げないことを述べた。この章でその解決策を扱う。

この章で使う既出の用語（定義は各リンク先）. XOR \(\oplus\)（04 章 1 節）、二項係数\(\binom{n}{2}\)（06 章 4 節）、CRC とその線形性（09 章）、 鍵・パディング（12 章）、レインボーテーブル・ビット回転（13 章）、連結\(\|\)・認証付き暗号（14 章 8 節）、 RSA の鍵と乗法準同型性・PSS（16 章）、中間者攻撃・ECDHE・ECDSA・Ed25519（17 章）

1. 暗号学的ハッシュ関数

定義と要件

任意の長さの入力から決まった長さの出力（ダイジェスト、ハッシュ値）を作る関数\(H\)をハッシュ関数という。暗号に使うハッシュ関数には、次の 3 つの性質が求められる。

第 2 原像と衝突の違いは、片方が固定されているかどうかである。衝突では攻撃者が両方を選べるので見つけやすく（次の誕生日攻撃）、衝突困難性のほうが強い要求になる。衝突困難なら第 2 原像も見つけにくいが、逆は成り立たない。

誕生日攻撃 — なぜ出力長が 2 倍必要か

出力が\(n\)ビットのハッシュ関数では、

• 原像を見つけるには約\(2^n\)回の計算が必要だが、
• 衝突を見つけるには約\(2^{n/2}\)回で済む。

方針: ランダムな値を\(k\)個選んだとき、すべてが異なる確率を計算し、それが\(1/2\)になる\(k\)を求める。

導出: 出力の取りうる値を\(N = 2^n\)通りとし、出力はランダムに散らばるとみなす。\(k\)個の値を順に選ぶとき、\(i\)番目の値がそれまでの\(i-1\)個のどれとも違う確率は\(1 - (i-1)/N\)なので、\(k\)個すべてが異なる（衝突が無い）確率は

である。\(x\)が小さいとき\(1 - x \approx e^{-x}\)（\(e^{-x} = 1 - x + x^2/2 - \cdots\)の 2 次以降を無視）なので、積は指数の和になり

これが\(1/2\)になるのは\(k^2/(2N) = \ln 2\)、すなわち\(k = \sqrt{2 \ln 2}\,\sqrt{N} \approx 1.18\sqrt{N} = 1.18 \times 2^{n/2}\)のときである ∎

「同じ誕生日の人がいる確率は 23 人で 50% を超える」という誕生日のパラドックスと同じ計算である。\(N = 365\)を入れると\(k \approx 1.18\sqrt{365} \approx 22.5\)人になる。365 日あるのに 23 人で足りるのは、誰と誰が一致してもよいので、比べる組の数が\(\binom{23}{2}=253\)通りもあるからである。

例: SHA-256 の出力の先頭 16 ビットだけを使う（\(N = 2^{16}\)）と、上の式では約\(1.18 \times 2^8 \approx 301\)個で衝突が見込まれる。実際に文字列"0", "1", "2", …のハッシュ値を順に計算すると、252 個目の"251"の先頭 16 ビットが、"157"と同じc75dになる。全体の 65536 通りに比べて、ずっと少ない回数で衝突が見つかる。

したがって 128 ビットの安全性がほしければ、ハッシュの出力は 256 ビット必要である。SHA-256 が標準的に使われるのはこのためである。

主なハッシュ関数

SHA-1 の衝突: 2017 年、Google と CWI は、SHA-1 のハッシュ値が同じになる 2 つの異なる PDF ファイルを公開した（SHAttered）。必要な計算量は約\(2^{63.1}\)回で、誕生日攻撃の\(2^{80}\)回より大幅に少なかった。 これにより、オブジェクトの識別に SHA-1 を使う Git や、証明書の業界が対応を迫られた。「まだ実際には破られていない」ことは「安全である」ことを意味しない。

Merkle-Damgård 構造と長さ拡張攻撃

MD5、SHA-1、SHA-256 は次の構造を持つ（以下は SHA-256 の場合）。入力\(m\)の末尾に、全体の長さが 512 ビットの倍数になるよう詰め物（パディング。\(m\)の長さ\(|m|\)も含める）を付け、512 ビットずつのブロック\(m_1, m_2, \dots, m_t\)に切る。決まった初期値\(h_0\)から始めて

を順に計算し、最後の\(h_t\)を出力とする。\(f\)は、256 ビットの値と 512 ビットのブロックを受け取って 256 ビットの値を返す決まった関数で、圧縮関数という。中身は XOR、加算、ビット回転を何十段も重ねたもので、設計ごとに違うが、この章では「入力を混ぜて短くする箱」と考えればよい。途中の\(h_i\)を内部状態という。

長さ拡張攻撃: この構造では、出力\(H(m) = h_t\)がそのまま内部状態である。したがって攻撃者は\(H(m)\)と\(m\)の長さ\(|m|\)を知っていれば、\(m\)の中身を知らなくても、\(h_t\)から\(f\)の計算を続けて、\(m\)の後ろに\(m\)のパディングと別のデータ\(m'\)を付け足したもののハッシュ\(H(m \,\|\, \text{pad} \,\|\, m')\)を計算できる。

これは素朴な MAC を壊す。\(\mathrm{MAC} = H(K \,\|\, m)\)という作り方では、攻撃者は鍵\(K\)を知らないまま、\(m\)を延長したメッセージに対する正しい MAC を作れてしまう。そのため次節のHMACという入れ子の構造が必要になる。

SHA-3 のスポンジ構造は、内部状態を出力より大きく取り、その一部だけを出力する構造である。出力から内部状態全体は分からないので、この弱点は無い。

2. MAC（メッセージ認証コード）

目的

共有鍵を持つ 2 者の間で、メッセージが改ざんされていないことを確かめるための短い値をMAC（Message Authentication Code）という:

受信者は同じ鍵で\(t\)を計算し直し、届いた値と一致するかを見る。鍵を知らない者は、改ざんしたメッセージに対する正しい\(t\)を作れない。

HMAC

\(K\)はハッシュ関数のブロック長（SHA-256 なら 512 ビット）まで 0 を付け足したものである（ブロック長より長い鍵は、先にハッシュして短くする）。\(\mathrm{ipad}\)はバイト\(\texttt{0x36}\)を、\(\mathrm{opad}\)はバイト\(\texttt{0x5C}\)をブロック長まで並べた定数である。 2 つの定数は 1 バイトあたり 8 ビット中 4 ビットが異なり、内側と外側で異なる鍵を使ったのと同じ効果を持たせるためのものである。

2 重にする理由: 内側のハッシュの結果を、さらに鍵付きでハッシュし直すことで、長さ拡張攻撃を防ぐ。攻撃者が延長したいのは内側の計算だが、外に出てくるのは外側のハッシュの出力だけで、内側の計算の内部状態は分からない。

CRC・ハッシュ・MAC・署名の違い

「ハッシュ値を付けておけば改ざんを検知できる」は誤りである。攻撃者はデータを書き換えた上で、ハッシュ値も計算し直して付け替えればよい。 ハッシュ値が役に立つのは、ハッシュ値そのものが安全な経路で別に伝わる場合だけである。たとえば公式サイトに載っている SHA-256 の値と、ミラーサイトからダウンロードしたファイルのハッシュ値を照合する場合である。 鍵を使わなければ、悪意ある改ざんは防げない。

3. デジタル署名

MAC との違い

否認防止とは、作成者が後から「自分は作っていない」と言い逃れできないようにすることである。 MAC では Alice と Bob が同じ鍵を持っているので、Bob が「Alice がこのメッセージを送った」と主張しても、Bob 自身も同じ MAC を作れるので、第三者にはどちらが作ったか判断できない。 署名なら秘密鍵を持つのは Alice だけなので、Alice が署名したことを第三者に示せる。電子契約や行政の電子申請で署名が使われるのはこのためである。

RSA 署名

16 章の鍵\((n, e)\)、\(d\)を使い、

• 署名: \(\sigma = H(m)^d \bmod n\)（秘密鍵で、復号と同じ計算をする）
• 検証: \(\sigma^e \bmod n\)が\(H(m)\)に等しいかを確かめる

とする。\((H(m)^d)^e \equiv H(m)\)は 16 章 3 節の正しさの証明そのものである。

例（16 章の鍵、\(n = 3233\)、\(e = 17\)、\(d = 2753\)）: ハッシュ値を\(H(m) = 123\)とすると、署名は\(\sigma = 123^{2753} \bmod 3233 = 2746\)である。検証者は\(2746^{17} \bmod 3233 = 123\)を計算し、\(H(m)\)と一致することを確かめる。

\(m\)そのものではなく\(H(m)\)に署名する理由:

1. 長さ: RSA は\(n\)未満の数しか扱えないので、長いメッセージには直接署名できない。
2. 速さ: べき乗の計算は重い。固定長のハッシュ値 1 つなら 1 回で済む。
3. 安全性: 16 章 5 節の乗法準同型性により、\(m\)に直接署名すると、2 つの署名の積\(\sigma_1\sigma_2 = (m_1m_2)^d\)が\(m_1 m_2\)の正しい署名になってしまい、署名を偽造できる。ハッシュを挟むと、偽造するには\(H(m_1)H(m_2) \equiv H(m_3)\)となる\(m_3\)を見つける必要があり、それは難しい。

実用では、さらに乱数を入れて整形するRSA-PSSを使う。

ECDSA / EdDSA

楕円曲線を使う署名は17 章 4 節で扱った。現在の主流はEd25519で、署名ごとの乱数を秘密鍵とメッセージから決定的に作るので、乱数生成器の不具合による事故が起きない。

4. 応用

パスワードの保管

してはいけないこと: パスワードをそのまま保存すること、単純なハッシュ（SHA256(password)など）だけを保存すること。

単純なハッシュでは、よく使われるパスワードのハッシュ値を事前に計算した表（レインボーテーブル）で逆引きされる。また GPU を使えば SHA-256 を 1 秒に数十億回以上計算できるので、総当たりも速い。

正しい方法は、次の 2 つを組み合わせることである。

• ソルト: ユーザーごとのランダムな値。パスワードに連結してからハッシュするので、同じパスワードでもユーザーごとに別のハッシュ値になり、事前計算した表が使えなくなる。
• 計算の重い KDF: KDF（Key Derivation Function、鍵導出関数）は、パスワードから鍵やハッシュ値を作る関数である。パスワード保管用のものは、わざと時間やメモリを多く使うように作られている。

わざと遅くするのが要点である。正規の利用者はログインのとき 1 回計算するだけなので、0.1 秒かかっても困らない。攻撃者は候補を数十億回試す必要があり、1 回 0.1 秒かかれば総当たりは事実上できなくなる。

ブロックチェーン

• 各ブロックが直前のブロックのハッシュ値を含むので、過去のブロックを改ざんすると、それ以降のすべてのブロックのハッシュ値が合わなくなり、改ざんが見つかる。
• マークル木: \(n\)件のデータのハッシュ値を葉に置き、隣どうしのハッシュ値を連結してハッシュする操作を繰り返して、1 本の木にまとめる。頂点（ルート）のハッシュ値 1 つで全体が改ざんされていないことを確かめられる。ある 1 件が含まれることを示すには、その葉からルートまでの経路の「隣のハッシュ値」を渡せばよく、木の高さ分の約\(\log_2 n\)個で済む。

証明書チェーン (PKI)

1. 認証局（CA、Certificate Authority）が「この公開鍵は example.com のものである」という内容に署名した証明書を発行する。
2. ブラウザは、OS やブラウザにあらかじめ組み込まれている CA の公開鍵で、その署名を検証する。
3. 検証できれば、証明書の公開鍵を使って TLS のハンドシェイクを行う。

これで17 章 1 節の「DH だけでは中間者攻撃を防げない」問題が解決する。証明書によって通信相手が本物かを確かめ、その上で ECDHE で鍵を共有する。暗号化（機密性）と認証（真正性）は別々の仕組みで、両方がそろって初めて安全になる。

5. 全体のまとめ — このシリーズで学んだこと

同じ数学が両方を支えている

次の表は、同じ数学が誤り訂正と暗号の両方で使われている場所をまとめたものである。用語の定義はリンク先の章にある。

壊れたデータを直す技術と、データを読まれないようにする技術は、目的は正反対だが、同じ代数の言葉で書かれている。 誤り訂正は元に戻しやすくなるように有限体の構造を使い、暗号は鍵を知らない者には戻しにくくなるように同じ構造を使う。 どちらも、02 章〜05 章で見た「有限の世界で四則演算が閉じている」という事実の上に成り立っている。