合同会社そらとりん

第2章 暗号 2-7

ハッシュ関数とは?3つの性質の違いと計算量

ハッシュ関数の仕組みと、安全性を支える三つの性質(原像計算困難性・第二原像計算困難性・衝突発見困難性)の違いを図解します。攻撃に必要な計算量、SHA-2・SHA-512/256・SHA-3、危殆化したMD5・SHA-1まで扱い、最後に過去問を1問解きます。

  1. ハッシュ関数とは
  2. 安全性を支える三つの性質
  3. 攻撃に必要な計算量
  4. 誕生日のパラドックス
  5. 代表的なハッシュ関数
  6. 過去問
  7. まとめ
YouTube で見る

ハッシュ関数とは

ハッシュ関数は、どんな長さのデータからも、決まった長さの値を作る関数です。この値をハッシュ値といいます。例えばSHA-256は、短い一文でも大きなファイルでも、256ビットのハッシュ値を出力します。

入力が同じなら、出てくる値も同じです。入力が1ビットでも変わると、まったく違う値になります。そのため、改ざんの検知や、パスワードの保存、デジタル署名に使われます。

ハッシュ関数とはの図解

安全性を支える三つの性質

ハッシュ関数を安全に使うには、三つの性質が必要です。違いは、攻撃者に何が与えられ、何を探すかです。一つ目は原像計算困難性です。ハッシュ値から元のメッセージ、つまり原像を求めるのが難しい性質で、一方向性ともいいます。

二つ目は第二原像計算困難性です。あるメッセージが与えられたとき、同じハッシュ値になる別のメッセージを見つけにくい性質です。三つ目は衝突発見困難性です。ハッシュ値が一致することを、衝突といいます。

二つのメッセージを両方とも自由に選んでよいとしても、ハッシュ値が一致する組を探し出せない性質です。

安全性を支える三つの性質の図解

攻撃に必要な計算量

SHA-256の場合、ハッシュ値から原像を総当たりで探すには、およそ2の256乗回の計算が必要です。一方、衝突はおよそ2の128乗回で見つかります。ハッシュ値の長さの、半分のビット数です。

攻撃に必要な計算量の図解

誕生日のパラドックス

理由は誕生日のパラドックスです。23人集まれば、誕生日が同じ二人がいる確率は5割を超えます。相手を決めず、どの組でもよいので、一致がずっと早く見つかるのです。

そのため、三つの性質のうち、最初に破られやすいのは衝突発見困難性です。

誕生日のパラドックスの図解

代表的なハッシュ関数

現在の主流はSHA-2です。SHA-256、SHA-384、SHA-512などがあり、数字は出力のビット数です。SHA-512/256は、SHA-512と同じ計算を別の初期値で行い、512ビットの結果を256ビットに切り詰めて出力します。

SHA-3は、SHA-2とは異なる構造で設計された方式で、2015年にNISTが標準化しました。一方、MD5とSHA-1は、実際に衝突する組が見つかっています。

このように安全性が失われることを危殆化といいます。どちらも、新しく使うべきではありません。

代表的なハッシュ関数の図解

過去問にチャレンジ

出典:令和5年度 春期 情報処理安全確保支援士試験 午前Ⅱ 問4

ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち, 適切なものはどれか。

  1. ア SHA-256の衝突発見困難性を示す,ハッシュ値が一致する二つの元のメッセージの発見に要する最大の計算量は,256の2乗である。
  2. イ SHA-256の衝突発見困難性を示す,ハッシュ値の元のメッセージの発見に要する最大の計算量は,2の256乗である。
  3. ウ 衝突発見困難性とは,ハッシュ値が与えられたときに,元のメッセージの発見に要する計算量が大きいことによる,発見の困難性のことである。
  4. エ 衝突発見困難性とは,ハッシュ値が一致する二つの元のメッセージの発見に要する計算量が大きいことによる,発見の困難性のことである。
答えと解説を見る

正解はエです。衝突発見困難性は、ハッシュ値が一致する二つのメッセージを見つけるのが難しい性質です。

アの256の2乗は誤りで、衝突はおよそ2の128乗回です。イは原像を探す場合の計算量、ウは原像計算困難性の説明です。

まとめ

この回の用語

参考:NIST FIPS 180-4 Secure Hash Standard(SHA-1、SHA-2、SHA-512/256 の定義) https://csrc.nist.gov/pubs/fips/180-4/upd1/final、NIST FIPS 202 SHA-3 Standard(2015年8月) https://csrc.nist.gov/pubs/fips/202/final、CRYPTREC LS-0003-2022r1 暗号強度要件(アルゴリズム及び鍵長選択)に関する設定基準 2.2.3節(衝突困難性はハッシュ長の半分、原像計算困難性はハッシュ長のビットセキュリティ) https://www.cryptrec.go.jp/list.html、CRYPTREC LS-0001-2022R2 CRYPTREC暗号リスト(令和8年3月30日更新。SHA-1は運用監視暗号リスト) https://www.cryptrec.go.jp/list.html、Wang, Yu: How to Break MD5 and Other Hash Functions(EUROCRYPT 2005)、Stevens et al.: The first collision for full SHA-1(CRYPTO 2017) https://shattered.io/、IPA 令和5年度春期 情報処理安全確保支援士試験 午前Ⅱ 問4。本ページは独立行政法人情報処理推進機構(IPA)とは関係ありません。過去問題は IPA の公開問題を出典を明記して掲載しています。

企業の方へ

セキュリティ対策のご相談

システム開発会社として、開発時のセキュリティ設計、運用中システムの点検と改修、社内規程の整備と研修を支援しています。

セキュリティ相談について

情報処理安全確保支援士試験の対策サービスを準備しています。公開のお知らせを希望する方は、こちらから事前登録できます。