この記事は、 CAMPFIRE Advent Calendar 2025 の6日目の記事 の一部です。連載記事の全体は、「第0回　暗号技術の基礎を学ぶ連載記事一覧」を参照してください。

前回学んだ共通鍵暗号は、データの機密性を保証する技術でした。ただ、暗号化されたデータが途中で改ざんされていないか、本当に意図した送信者からのものかを確認するには、別の技術が必要です。これが ハッシュ関数 と メッセージ認証コード（MAC） の役割です。

ハッシュ関数は任意の長さのデータを固定長の「指紋（一般にハッシュ値やダイジェストと呼ばれます）」に変換し、データの完全性を確認するために使用されます。一方、MACは共通鍵を使用してデータの完全性と認証を同時に提供します。これらの技術は現代の暗号システムにおいて、機密性と並んで重要な役割を果たしています。

※この記事は、文章案の作成や表現の調整、内容の検証や修正のサポート等に生成AIを利用しています。

3.1 ハッシュ関数の概要

ハッシュ関数は、任意の長さのデータを固定長の「指紋」に変換する関数です。この変換により、元のデータが少しでも変更されると、生成される指紋も大きく変化します。この性質を利用して、データの完全性を確認することができます。

数学的には、ハッシュ関数 $H$ は任意長のビット列 ${0,1}^*$ を $n$ ビットの固定長ビット列 ${0,1}^n$ に変換します。

$$H: {0,1}^* \rightarrow {0,1}^n$$

ハッシュ関数の基本動作は単純です。メッセージ $M$ を入力として、固定長のハッシュ値 $H(M)$ を出力します。

ハッシュ関数には三つの重要な特徴があります。まず、 一方向性 です。与えられたハッシュ値から元のデータを求めるのは計算的に困難で、 $H(M)$ から $M$ を求める効率的な方法は存在しません。次に、 衝突耐性 です。異なる入力が同じ出力になる確率が極めて低く、 $M_1 \neq M_2$ かつ $H(M_1) = H(M_2)$ となる $M_1, M_2$ を見つけるのは困難です。最後に、雪崩効果 です。入力の小さな変更が出力に大きな変化をもたらし、1ビットの変更でも出力の約50%のビットが変化します。

これらの特徴により、ハッシュ関数はデータ完全性の確認、ディジタル署名の前処理、パスワードの安全な保存、データベースのインデックスなど、様々な場面で利用されています。

3.2 ハッシュ関数の安全性

ハッシュ関数の安全性は、攻撃者がどのような攻撃を試みても成功できないことを保証する必要があります。この安全性は三つの概念で定義されます。

原像計算困難性 は、与えられたハッシュ値 $y$ に対して、 $H(x) = y$ となる $x$ を見つけるのが困難ということです。数学的には、任意の $y \in {0,1}^n$ に対して、 $H(x) = y$ となる $x$ を求めるのが計算量的に困難であることを表します。

次に、 第二原像計算困難性 です。これは特定の入力 $x_1$ に対して、 $H(x_1) = H(x_2)$ となる別の入力 $x_2 \neq x_1$ を見つけるのが困難であるということです。これは既知のメッセージと同じハッシュ値を持つ別のメッセージ（第二原像）を見つける攻撃に対する耐性です。

最後に、 衝突耐性 です。これは任意の2つの異なる入力 $x_1, x_2$ に対して、 $H(x_1) = H(x_2)$ となるペアを見つけるのが困難であるということです。これは最も強力な安全性概念で、任意の2つのメッセージの衝突を見つける攻撃に対する耐性です。

しかしながら、どのようなハッシュ関数であっても、衝突が全く存在しないものはありません。これは鳩の巣原理と呼ばれる原理に由来します。これは $m$ 個の巣穴に $m<n$となるn羽の鳩を収めるなら、少なくとも1つ以上の巣穴に2羽以上の鳩を収める必要があるという原理です。

各安全性概念には階層的な関係があります。攻撃のしやすさの観点で、第二原像を求めるよりも任意の衝突するペアを見つけることのほうが簡単です。そのため、第二原像計算困難性よりも衝突耐性のほうがより安全性を高めます。

理想的なハッシュ関数に対する攻撃の計算量でいうと、原像攻撃と第二原像攻撃は $O(2^n)$ の計算量が必要で、これは総当たり攻撃に相当します。しかし、衝突攻撃は $O(2^{n/2})$ の計算量で実行可能で、これは誕生日攻撃と呼ばれる確率的な手法によるものです。ここで $n$ はハッシュ値のビット長です。

誕生日攻撃は、誕生日のパラドックスに基づく確率的な攻撃手法です。誕生日のパラドックスとは、23人のグループの中に同じ誕生日の人がいる確率が約50%になるという直感に反する結果です。同様に、ハッシュ関数でも $2^n$ 個の可能なハッシュ値の中から衝突を見つけるには、約 $2^{n/2}$ 個のメッセージを試せば50%の確率で衝突が見つかります。

具体的な例として、128ビットハッシュ関数（MD5）では総当たり攻撃に $2^{128}$ 回の計算が必要ですが、誕生日攻撃では約 $2^{64}$ 回の計算で済みます。256ビットハッシュ関数（SHA-256）では、総当たり攻撃に $2^{256}$ 回の計算が必要ですが、誕生日攻撃では約 $2^{128}$ 回の計算で済みます。

この攻撃手法により、ハッシュ関数の出力長は衝突攻撃に対して十分な長さである必要があり、現在では少なくとも256ビットの出力長が推奨されています。

3.3 ハッシュ関数の種類

MD4とMD5

ハッシュ関数として最初に広く使用されたのはMD4です。MD4はRSA暗号の共同開発者であるRonald Rivestによって1990年に設計され、128ビットの出力長と512ビットのブロック長を持つハッシュ関数でした。ブロック長とは、ハッシュ関数が一度に処理するデータの長さのことで、メッセージをこの長さのブロックに分割して順次処理します。当時、ディジタル署名の前処理として使用する高速なハッシュ関数が必要とされており、MD4はそれまでのハッシュ関数よりも高速で実装が簡単な設計として注目されました。
しかし、1995年にDobbertinにより衝突攻撃が発見され、現在は完全に破られています。

MD4の脆弱性を受けて、Ronald Rivestは1992年にMD5を設計しました。MD5はMD4の安全性問題を解決するため、より強固な設計として4ラウンドの圧縮関数を採用し、より複雑なパディング方式を導入しました。MD5は1990年代から2000年代にかけて広く使用され、ファイルの完全性確認やディジタル署名の前処理として標準的なハッシュ関数となりました。
その後、MD5でも2004年にWangらにより衝突攻撃が発見され、約 $2^{39}$ の計算量で衝突を発見可能となり、安全ではないとされています。

現代的ハッシュ関数

SHA-1

MD5の脆弱性を受けて、アメリカ国家安全保障局（NSA）は1995年にSHA-1を設計し、連邦情報処理標準（FIPS）として制定しました。SHA-1はMD5の安全性問題を受けて、より安全なハッシュ関数として160ビットの出力長を採用し、SHA-0の改良版として開発されました。SHA-1は政府機関や金融機関で広く採用され、SSL/TLS、SSH、Gitなど多くのシステムで使用されました。

SHA-1のアルゴリズムは5つの32ビットレジスタを使用するMerkle-Damgård構造です。

しかしながら、2005年に理論的な脆弱性が発見され、2017年にGoogleにより実用的な衝突攻撃が実証され、約 $2^{63}$ の計算量で衝突を発見可能となり、現在は推奨されていません。

SHA-2

SHA-1の理論的脆弱性を受けて、NSAは2001年にSHA-2ファミリーを設計し、2002年にFIPS 180-2として標準化しました。SHA-2はより長い出力長（224ビット、256ビット、384ビット、512ビット）を提供するハッシュ関数ファミリーとして開発され、SHA-1と同様のMerkle-Damgård構造を採用しながら、より強固な設計を実現しています。現在、SHA-256とSHA-512が最も広く使用されており、SSL/TLS、Bitcoin、多くのセキュリティプロトコルで標準的なハッシュ関数として採用されています。

SHA-2の構造は、データをパディングし、ブロック分割を行い、ハッシュ計算を実行して出力を生成する流れです。SHA-2ファミリーはMerkle-Damgård構造を採用し、SHA-256とSHA-512で異なるワードサイズを使用します。

以下にSHA-256のアルゴリズムの概要を示します。

ファイルのSHA-256やSHA-512のハッシュ値をコマンドラインで確認するには、Mac/Linuxでは sha256sum や sha512sum 、Windowsでは、certutil を利用することで確認ができます。

SHA-3

SHA-3は、NIST（アメリカ国立標準技術研究所）が2007年に開始したSHA-3コンペティションの結果として選定されました。SHA-2に対する理論的攻撃の可能性を考慮し、異なる数学的構造を持つハッシュ関数を求めて国際的なコンペティションが開催されました。2012年にKeccakが最終候補として選定され、2015年にFIPS 202として標準化されました。SHA-3は、SHA-2とは異なるスポンジ構造を採用しており、理論的な安全性の向上と、SHA-2に対する代替手段としての役割を果たしています。現在、SHA-3は段階的に導入が進められており、特に高セキュリティ要件のシステムで採用されています。

SHA-3はKeccakをベースとしたスポンジ構造を採用しています。スポンジ構造は、吸収フェーズでメッセージを内部状態に吸収し、絞り出しフェーズで内部状態からハッシュ値を出力する構造です。

SHA-3のバリエーションには、SHA3-224（出力長224ビット、容量448ビット）、SHA3-256（出力長256ビット、容量512ビット）、SHA3-384（出力長384ビット、容量768ビット）、SHA3-512（出力長512ビット、容量1024ビット）があります。

コマンドラインでファイルのSHA-3のハッシュ値を確認するには、SHA-2と異なり、組み込みのコマンドがないため、opensslなどで openssl dgst -sha3-256 -r <path> とする必要があります。

BLAKE2

BLAKE2は、SHA-3コンペティションの最終候補であったBLAKEハッシュ関数を改良したもので、2012年に開発されました。SHA-2やSHA-3と同等以上の安全性を保ちながら、MD5と同等の高速性を実現することを目標として設計されました。

BLAKE2には用途に応じて2つのバリエーションがあります。BLAKE2bは64ビットプラットフォーム向けに最適化され、出力長は最大512ビットです。一方、BLAKE2sは32ビットプラットフォーム向けに最適化され、出力長は最大256ビットです。どちらも可変長出力をサポートしています。

BLAKE2の主な特徴として、SHA-2より約3倍高速で、MD5と同等の性能を持ちながら、SHA-3より高速な実装が可能です。鍵付きハッシュ（MAC）やツリーハッシュ（並列処理）などの機能を標準でサポートしています。
これらの特徴から、BLAKE2は実際のシステムでも採用されています。Argon2パスワードハッシュ関数やWireguard VPN、Zcashなどの暗号通貨で使用されています。2025年現在でも実用的な攻撃は発見されておらず、暗号学的に安全なハッシュ関数として評価されています。

コマンドラインでBLAKE2のハッシュ値を求める場合、 b2sum コマンドをインストールすることでできるようになります。

BLAKE3

BLAKE3はBLAKE2を並列化可能で、より単純かつ多用途利用にし、高速化したバージョンとして2020年に発表されました。

各ハッシュ関数の整理

ハッシュ関数の比較を以下に示します。

ハッシュアルゴリズム	出力長	ブロック長	安全性
MD5	128ビット	512ビット	破られているため使用禁止
SHA-1	160ビット	512ビット	破られているため使用禁止
SHA-256（SHA-2）	256ビット	512ビット	現時点では安全
SHA-512（SHA-2）	512ビット	1024ビット	現時点では安全
SHA-3-256	256ビット	1088ビット	現時点では安全
BLAKE2b	可変（最大512ビット）	1024ビット	現時点では安全
BLAKE2s	可変（最大256ビット）	512ビット	現時点では安全

3.4 メッセージ認証コード（MAC）の概要

メッセージ認証コード（Message Authentication Code, MAC）は、メッセージが改ざんされていないことを確認するための短いタグです。MACは共通鍵を使用し、送信者と受信者が同じ秘密鍵を共有することで、データ完全性と認証を同時に提供します。MACは元のメッセージより短い固定長の出力を生成します。

MACの基本動作は、共通鍵 $K$ とデータ $M$ を入力として、MAC関数を適用して$MAC(K, M)$を出力することです。

数学的には、MAC関数は鍵空間 $\mathcal{K}$ 、メッセージ空間 $\mathcal{M}$ 、タグ空間 $\mathcal{T}$ を使用して以下のように定義されます。

$$MAC: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{T}$$

MACの生成と検証の流れは以下の通りです。MAC生成では、メッセージ $M$ と共通鍵 $K$ を入力として、MAC関数を適用してタグ $T = MAC(K, M)$ を生成し、メッセージとタグの組 $(M, T)$ を送信します。MAC検証では、受信したメッセージ $M'$ とタグ $T'$ を取得し、共通鍵 $K$ を使用して $T = MAC(K, M')$ を計算し、 $T = T'$ ならば検証成功、そうでなければ検証失敗となります。

MACは偽造困難性、鍵依存性、一意性という重要な性質を持ちます。偽造困難性により攻撃者は有効なMACを生成できず、鍵依存性により異なる鍵では異なるMACが生成され、一意性により同じメッセージでも異なる鍵では異なるMACが生成されます。

3.5 MACの安全性

MACの安全性は偽造困難性で定義されます。この性質により、攻撃者は過去にMACを計算したメッセージ以外のメッセージに対して有効なMACを生成できません。

MACに対する攻撃モデルとして、選択メッセージ攻撃（Chosen Message Attack, CMA）が考えられます。この攻撃では、攻撃者が任意のメッセージ $M_i$ を選択し、オラクルが $MAC(K, M_i)$ を返します。その後、攻撃者は新しいメッセージ $M^*$ とタグ $T^*$ を出力し、 $M^*$ が過去にクエリしたメッセージでなく、 $T^* = MAC(K, M^*)$ なら攻撃成功です。

MACの安全性は、基盤となる暗号技術の安全性に依存します。ブロック暗号ベースMACでは基盤となるブロック暗号の安全性に依存し、ハッシュ関数ベースMACでは基盤となるハッシュ関数の安全性に依存します。

実際の攻撃例として、長さ拡張攻撃があります。これは単純なハッシュ関数ベースMACに対する攻撃で、 $MAC(K, M) = H(K || M)$ （$K || M$ は $K$ と $M$ を結合したもの）の場合、攻撃者は $H(K || M)$ から $H(K || M || M')$ を計算できる可能性があります。また、弱い鍵を使用した場合の鍵回復攻撃では、 $MAC(K, M) = H(K \oplus M)$ の場合、 $K$ が短い場合、総当たり攻撃で鍵を回復できる可能性があります。
長さ拡張攻撃は、Merkle-Damgård構造に由来する脆弱性を利用した攻撃のため、SHA-3では攻撃が成立しません。

3.6 MACの種類

MACは基盤となる技術によっていくつかに分類されます。ブロック暗号ベースのMACには、CBC-MACとCMACなどがあります。CBC-MACは最も基本的なブロック暗号ベースMACで、メッセージをブロックに分割し、CBCモードと同様に各ブロックを連鎖的に暗号化していき、最後の暗号文ブロックをMAC値とします。CBC-MACはシンプルな構造を持ちますが、可変長メッセージに対しては偽造攻撃が可能であり、脆弱性を持ちます。
CMACはCBC-MACの可変長メッセージに対する脆弱性を解決するために設計されたMACで、最後のブロックを処理する際に、メッセージ長に応じて異なる派生鍵（$K_1$ または $K_2$）を使用します。CMACはCBC-MACの安全性問題を解決し、可変長メッセージに対して安全で、AESなどの標準ブロック暗号と組み合わせて使用されます。

ハッシュ関数ベースのMACには、HMACなどがあります。HMACは最も広く使用されているハッシュ関数ベースMACで、 $HMAC(K, M) = H(K \oplus opad\ ||\ H(K \oplus ipad\ ||\ M))$ で表されます。ここで、 $ipad$ と $opad$ は定数パターンです。HMACの構造は、 $K \oplus ipad$ をハッシュ関数 $H$ に通し、その結果を $K \oplus opad$ と組み合わせて再度ハッシュ関数 $H$ に通す流れです。HMACは任意のハッシュ関数と組み合わせ可能で、長さ拡張攻撃に対して安全で、理論的な安全性が証明されています。

MAC専用のアルゴリズムをベースとしたMACには、Poly1305やSipHashなどがあります。これらは、MAC専用で設計されているため、MACに最適化されていることが共通の特徴となります。Poly1305（読みは Poly Thirty O Five です）は、ChaCha20-Poly1305などのAEADで用いられ、長いメッセージに対しても非常に高速である特徴があります。ただし、Poly1305は、単独では鍵の使いまわしに対して安全ではありません（ChaCha20-Poly1305では回避する仕組みあり）。 SipHash はPoly1305のもととするWegman-Carter構造とは異なる構造を利用するMACです。もともとhash flooding 攻撃（DoS）に耐性を持つ疑似乱数関数として作られており、Poly1305とは異なり、同じ鍵の使い回しに対する安全性があり、入力されるメッセージが短い（128バイト未満）場合には性能が高くなるように設計されています。

MACの比較では、CBC-MACはブロック暗号を基盤とし、安全性は固定長メッセージのみでしか保証されず、現在は基本的に使用されません。CMACはブロック暗号を基盤とし、安全性と性能が高く、AES環境で使用されます。HMACはハッシュ関数を基盤とし、安全性は高く性能は中程度で、汎用的に使用されます。

3.7 現実世界での応用例

ハッシュ関数とMACは、現実世界の様々なシステムで活用されています。

TLS（Transport Layer Security） では、データの完全性と認証を保証するためにMACが使用されます。TLS 1.2では、標準ではMACを計算してから暗号化（MAC-then-encrypt）し、HMAC-SHA256が最も一般的に使用され、高セキュリティ要件ではHMAC-SHA384が使用されます。TLS 1.3では、TLS 1.2ではオプションだった、認証付き暗号（AEAD）がMACの代わりに標準で使用されています。AES-GCMが認証と暗号化を同時に提供し、ChaCha20-Poly1305が高速なAEADとして使用されます。

Gitでは、歴史的にデータの完全性確認のためにSHA-1ハッシュ関数が使用されています。ただし、SHA-1の脆弱性を受けてSHA-256への移行を段階的に進められています。ただし、過去のリポジトリなどの存在もあり、バージョン2.13以降では sha1dcという衝突検知が可能なSHA-1実装を利用する変更も入れられています。

Linuxディストリビューションなどのソフトウェア配布では、ファイルの完全性を確認するためにハッシュ関数が使用されます。

クラウドストレージサービスでは、データの完全性を保証するためにハッシュ関数が使用されます。AWS S3では、アップロード時にContent-MD5ヘッダーを使用してデータ転送の完全性を検証します。これは通信経路での破損検出を目的とするものであり、暗号学的なセキュリティ保証を提供するものではありません。AWS S3の例のように、セキュリティ保証が重要ではない場面で、後方互換性やパフォーマンスの観点でMD5が利用されていることがあります。セキュリティが重要な場面では、MD5は衝突耐性が弱いため、より安全なSHA-256などのハッシュ関数の利用や、HTTPS（TLS通信）との併用が推奨されています。

3.8 まとめ

今回学んだハッシュ関数とメッセージ認証コード（MAC）について、ポイントを整理します。ハッシュ関数は、データの完全性確認とディジタル署名の前処理を目的とし、原像計算困難性、第二原像計算困難性、衝突耐性という安全性目標があります。種類としては、MD5とSHA-1は脆弱で、SHA-2とSHA-3は安全です。また、一般的にSHA-xシリーズが有名ですが、それ以外にもBLAKE2なども存在し、利用されていることを紹介しました。

メッセージ認証コード（MAC）は、データ完全性と認証の同時提供を目的とし、偽造困難性が重要となります。種類としては、ブロック暗号ベースのCBC-MACとCMAC、ハッシュ関数ベースのHMACがあります。

ハッシュ関数とMACは、現代暗号技術において重要な役割を果たしています。機密性は共通鍵暗号と公開鍵暗号で提供され、完全性はハッシュ関数とMACで提供され、認証はMACとディジタル署名で提供され、否認防止はディジタル署名で提供されます。

次回（「第4回　公開鍵暗号 1（RSA暗号・分散署名・準同型暗号））では、RSA暗号・分散署名・準同型暗号について学びます。扱うトピックには、素因数分解の困難性に基づく公開鍵暗号であるRSA暗号、ディジタル署名の実現であるRSA署名、秘密鍵の安全な分散管理である分散署名、暗号化したまま計算を実行する準同型暗号があります。

目次