暗号学的ハッシュ関数は、任意のバイト列を固定サイズのダイジェストに縮約します。プロトコルが依存するのは、単にハッシュ化することではなく、特定の耐性特性です。高速な非鍵付きダイジェストだけでは、メッセージ認証も安全なパスワード保存も実現できないためです。
ハッシュ関数 #
ハッシュ関数は、任意に大きな入力領域を有限の出力領域へ写像します。出力は、多くの場合、固定長のビット列です。
H: {0, 1}* -> {0, 1}^nこの定義だけからセキュリティ特性は導かれません。たとえば、すべての入力に対して f(x) = 0 となる関数もハッシュ関数です。すべてのエントリが1つのバケットに入るためハッシュテーブルには不適切ですが、結果は暗号学的な失敗ではなく、性能の低下です。
暗号学的用途では、より強い要件が課されます。データベースが開示される可能性があるからといって、ユーザーの平文パスワードを保存してはなりません。保存するパスワード検証値は、オフライン推測攻撃に高いコストを課す必要があります。汎用ハッシュだけでは、この目的を達成できません。同様に、ダイジェストは偶発的な破損を検出できますが、メッセージを置き換えられる攻撃者は、そのダイジェストも置き換えられます。通常のハッシュだけでは、送信元認証も能動的な攻撃者に対する完全性も提供できません。
入力領域はダイジェスト領域より大きいため、すべての固定長ハッシュには衝突があります。つまり、異なる入力が同じダイジェストを持ちます。したがって暗号学では、攻撃者が実用的な衝突、または指定されたダイジェストを生成する入力を、実行可能な資源で見つけられるかどうかを問題にします。
バースデー限界 #
誕生日のパラドックスには、同値な2つの説明があります。無作為に選んだ人々の集団では、23人しかいなくても、2人の誕生日が一致する確率は50%を超えます。逆に、誕生日を1人ずつ問い合わせられる場合、驚くほど少ない問い合わせ回数で一致する組を見つけられる確率が大きくなります。365日モデルで366人を調べれば、鳩の巣原理によって組の存在が保証されます。
ハッシュでは、2つ目の説明のほうが有用です。ハッシュ入力は有限の母集団から選ぶ必要がありません。攻撃者は新しい入力を選び続け、公開関数を評価できます。理想ハッシュから、均等に可能性のある N 個の出力値を q 回サンプリングした後、少なくとも1つの出力が重複する確率は、おおよそ次のようになります。
1 - exp(-q(q - 1) / (2N)).この近似は、補集合事象を考えることで得られます。最初の出力には制約がありません。次の出力は、すでに占有された1つの値を避ける必要があり、その次は2つを避ける必要があります。この積を取ると、上記の指数関数のように近似的に減少する積が得られます。したがって、衝突の確率を一定の水準にするには、sqrt(N) 回程度の評価が必要です。N = 2^n である n ビットのダイジェストでは、一般的な衝突コストは約 2^(n/2) です。
均一な出力分布は、理想モデルにおける仮定です。偏りや構造的な弱点があると衝突が容易になる可能性があり、f(x) = 0 のような関数では即座に衝突します。それでもバースデー限界は、理想的な固定出力ハッシュに避けられない限界を示します。入力空間を拡大しても、この限界は改善できません。バースデー攻撃とは、重複が現れるまで過去のダイジェストを保持する、この一般的な衝突探索にほかなりません。
たとえば、理想的な32ビットハッシュでは、約9,300回の試行後に衝突確率が約1%となり、約77,000回の試行後には約50%となります。このようなダイジェストは、衝突耐性が重要な用途には不十分です。バースデー限界が対象とするのは入力の任意の組であり、特定の入力の復元ではありません。
暗号学的ハッシュ関数のセキュリティ特性 #
暗号学的ハッシュ関数とは、指定された攻撃に耐えることを意図した非鍵付きハッシュです。「暗号学的ハッシュ関数」は、1つの形式的なセキュリティゲームを指すものではありません。その意味は、プロトコルが必要とする特性によって異なります。ハッシュ H に対して、値 y の原像とは、H(m) = y を満たす任意のメッセージ m です。
以下のゲームでは、攻撃者が受け取るものと選択できるものが異なります。
- 原像計算困難性: 対象ダイジェスト
yが与えられたとき、H(m) = yを満たす任意のmを見つける。 - 第二原像計算困難性: 特定のメッセージ
m1が与えられたとき、H(m1) = H(m2)を満たす異なるm2を見つける。 - 衝突計算困難性:
H(m1) = H(m2)を満たす、異なるメッセージの組m1,m2を見つける。 - 選択プレフィックス衝突計算困難性: 異なる2つのプレフィックス
p1とp2が与えられたとき、H(p1 || s1) = H(p2 || s2)を満たすサフィックスs1とs2を見つける。
衝突攻撃では攻撃者が両方のメッセージを選べますが、第二原像ゲームでは一方のメッセージが固定されています。原像ゲームではダイジェストが固定されています。これらのゲームを普遍的な順序にまとめるべきではありません。特定の分布やモデルの下では特性間に形式的な含意が成立する可能性がありますが、弱点は標的固有になり得ます。プロトコルは、攻撃者が制御する入力に適合する特性を選択する必要があります。
理想的な n ビットハッシュでは、原像および第二原像の一般的な探索には約 2^n の計算量が必要です。一方、バースデー法は約 2^(n/2) の計算量で衝突を見つけます。衝突計算困難性とは、衝突が存在しないという意味ではなく、一般的なバースデーコストを実質的に下回る攻撃が存在しないという意味です。
選択プレフィックス衝突は、無関係な2つの衝突ファイルよりも強力です。攻撃者は、意味のある異なる2つのプレフィックス、たとえば2種類の文書形式のヘッダーと初期コンテンツから始め、同じダイジェストになるサフィックスを生成できます。MD5に対する実用的な選択プレフィックス衝突は、異なる意味を持つアーティファクトに衝突を埋め込めることを示しました。これには、偽造された証明書関連の素材も含まれます。このような攻撃により、衝突に依存するMD5の用途は受け入れられなくなりました。
非鍵付きハッシュは秘密鍵を取りません。鍵を受け付ける構成は、メッセージ認証コード、一部の用語では鍵付きハッシュ、または別のプリミティブです。そのセキュリティ要件は個別に評価する必要があります。
ハッシュの設計と構成 #
効果的な暗号学的設計では、入力の小さな変化を出力全体に広く分散させます。この効果は雪崩効果と呼ばれます。雪崩特性は有用な診断材料ですが、原像計算困難性、第二原像計算困難性、衝突計算困難性のいずれも証明しません。これらの特性が対象とするのは、攻撃者が利用できる最良のアルゴリズムです。
多くの反復型ハッシュは圧縮関数から始まります。連鎖値と、固定サイズの1つのメッセージブロックを受け取り、同じ幅の新しい連鎖値を生成します。
C: {0, 1}^n x {0, 1}^b -> {0, 1}^n「圧縮」という語は、入力全体が出力より長いことを指します。関数が可逆であるという意味ではありません。セキュリティ分析では、このコンポーネントに適切な一方向性と衝突耐性があるかを検討します。古典的な構成ではブロック暗号から圧縮関数を構築できますが、現代の標準化されたハッシュファミリーは専用設計を使用します。
Merkle–Damgård構成 #
Merkle–Damgård構成は、固定入力の圧縮関数を可変長ハッシュに変換します。初期連鎖値から開始し、メッセージをブロックにパディングし、現在の連鎖値と各ブロックを圧縮関数へ入力します。最終的な連鎖値がダイジェストになります。
Merkle–Damgård強化では、パディングの一部として元のメッセージ長のエンコーディングを追加します。条件を満たす限り、衝突耐性を持つ圧縮関数は、衝突耐性を持つ可変長ハッシュを生成します。強化がなければ、パディング済み入力の衝突が、曖昧なメッセージ境界から生じる可能性があります。MD5、SHA-1、SHA-2はこの広義の構成を使用します。実際のセキュリティは、それぞれの圧縮関数とダイジェスト長によって決まります。
長さのエンコードは、関連する長さ拡張特性を防ぎません。通常のMerkle–Damgårdハッシュでは、m のダイジェストから、m とそのパディングを処理した後の連鎖値が明らかになります。攻撃者はダイジェストと m の長さを知っていれば、m を知らなくても、しばしば m || padding(m) || extension の有効なダイジェストを計算できます。この結果は、システムが次のようにデータを認証する場合に重要です。
SHA-256(secret || message)攻撃者は、秘密の長さを推測できれば、message を拡張して対応するダイジェストを計算できます。通常のMerkle–Damgårdハッシュを秘密プレフィックスMACとして使用してはなりません。代わりにHMACを使用してください。
HMAC(K, m) = H((K XOR opad) || H((K XOR ipad) || m))HMACの入れ子になった鍵付き構成は長さ拡張に耐性があり、SHA-256のような現行のハッシュとともに使用すればメッセージ認証に適しています。ただし、プロトコルでは鍵生成、切り詰め、メッセージエンコーディング、鍵分離も定義する必要があります。
ドメイン分離とソルト #
1つのハッシュ関数が、プロトコル内で複数の役割を担うことがあります。ドメイン分離は、ある役割の値が別の役割で受け入れられることを防ぎます。標準化された構成では、固定された関数識別子を先頭に付けたり、コンテキスト文字列を専用フィールドに配置したり、役割ごとに独立した鍵を導出したりします。エンコーディングは曖昧であってはなりません。長さや指定されたシリアライズ方法なしに可変長値を連結すると、異なるフィールド列が同じバイト列に写像される可能性があります。
プロトコルまたはプリミティブで定義されたドメイン分離機構を使用してください。プレフィックスを変更したり、独自のエンコーディングを作成したりするとプロトコルが変更されるため、個別の分析が必要になります。SHA-3関数、カスタマイズ可能なcSHAKE関数、鍵導出プロトコルはそれぞれ異なる分離機構を公開しているため、それらの入力は交換可能ではありません。
ソルトは別の問題を解決します。パスワード検証値では、認証情報ごとに一意のランダムなソルトを使用します。これにより、同じパスワードが同じ保存値を生成することを防ぎ、攻撃者が1つの事前計算テーブルを複数のアカウントに使い回せなくなります。ソルトは検証値とともに保存され、秘密ではありません。ソルトはパスワードのエントロピーを増加させず、メッセージを認証せず、ドメイン分離の代替にもなりません。
パスワードハッシュには、設定可能な時間コストとメモリコストも課す必要があります。利用できる場合は、RFC 9106に従ってArgon2idを使用してください。プラットフォームやコンプライアンス上の制約により、scrypt、bcrypt、またはPBKDF2が必要になる場合があります。ログイン成功後にパラメーターを更新できるよう、アルゴリズム識別子、パラメーター、ソルト、導出出力を保存してください。
ハッシュアルゴリズムの選択 #
適用される標準、相互運用性の要件、プロトコルに従って、SHA-256、SHA-512/256、SHA-3、BLAKE2などの現代的な汎用ハッシュを使用してください。SHA-256は256ビットのダイジェストを提供し、理想的な一般的衝突計算量は128ビットです。SHA-512/256はSHA-512を基盤とする別個のアルゴリズムであり、出力が256ビットであるだけで、SHA-512を非公式に切り詰めたものではありません。
MD5は衝突耐性が破られているため、衝突がセキュリティに影響する用途で選択してはなりません。SHA-1には実用的な衝突攻撃と選択プレフィックス衝突攻撃があり、デジタル署名、証明書、同様の用途では同じく非推奨です。レガシー検証ではこれらのアルゴリズムを認識する必要がある場合がありますが、新規設計でMD5またはSHA-1の署名を作成してはなりません。移行には、明示的なアルゴリズム識別子、新たに生成するデータに対する許可リスト、レガシー検証を削除する期限、旧アルゴリズムへのダウングレードを防ぐ保護が必要です。
コメント
GitHub で閲覧・コメントする（投稿にはログインが必要です）