ハッシュ関数

ひとことで

ハッシュ関数には，次の性質があります。

• 入力の長さに関係なく，出力の長さは決まっている。SHA-256 なら，32ビットのデータでも2,048ビットのデータでも，ハッシュ値は256ビットです
• 同じ入力からは必ず同じ値が出る。だから，受け取ったデータのハッシュ値を求め直して比べれば，1ビットでも書き換えられたかが分かります
• 入力が少し変わるだけで，出力は大きく変わる

暗号学的ハッシュ関数に求められる3つの性質

セキュリティに使うハッシュ関数は，次の3つが「計算量的に困難」であることを求められます。

違いは「何が先に決まっているか」です。原像はハッシュ値が，第2原像は片方のメッセージが決まっていて， 衝突は何も決まっていない（2つとも自由に選べる）ので，最も見つけやすい攻撃に耐えることを求める性質です。

代表的なアルゴリズムは SHA-2 系（SHA-256 など）です。SHA-1 は出力が160ビットで， 衝突を見つける攻撃が現実的になったため，いまは新しい用途に使いません。

ハッシュ表

データ構造のハッシュ表は，キーをハッシュ関数に通して格納する場所を計算で決める方法です。 衝突（違うキーが同じ場所になること）が起きなければ，データの数がいくら増えても1回の計算で場所が分かるので， 探索の時間はデータの数によらず一定です。

試験でよく使われるのは，キーを表の大きさ n で割った余りを場所にする h(x) ＝ x mod n です。 2つのキー a と b が衝突するのは余りが同じとき，つまりa − b が n の倍数のときです。

試験での問われ方

当サイトが収録している午前の問題のうち，ハッシュ関数・ハッシュ値・メッセージダイジェスト・SHA のどれかが出てくるのは59問です。 情報処理安全確保支援士の午前Ⅱと午前Ⅰで大半を占めます。型ごとに数えると次のとおりです。

• ハッシュ関数の性質とアルゴリズム（12問）。 衝突発見困難性の説明を選ぶ問題は支援士の午前Ⅱで6回出ています。 正解は「ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性」など。 SHA-256 のハッシュ値の長さ（入力の長さによらずすべて256ビット）も2回出ています。
• ハッシュ表（10問，ほぼ午前Ⅰ）。 h(x) ＝ x mod n でキー a と b が衝突する条件（a − b が n の倍数）は午前Ⅰで6回出ています。 ほかに，衝突した値から除数を求める計算，探索時間のグラフ（データ数によらず一定）があります。
• ハッシュ値を使う仕組み（12問）。 ディジタル署名でハッシュ値を変換する鍵（発信者の秘密鍵）， DNSSEC の機能（8問。正解は署名による送信者の正当性とデータの完全性の検証），OCSP の問合せです。
• 認証のプロトコル（7問）。チャレンジレスポンス方式や CHAP は， パスワードそのものを送らず，サーバから届いたランダムな値とパスワードからハッシュ値を計算して返します。 SMTP-AUTH の問題（4問）では選択肢に出てきます。
• パスワードを狙う攻撃（4問）。 Pass the Hash 攻撃（ハッシュ値だけでログインできる仕組みを悪用する，支援士で3回）と， レインボーテーブル攻撃（平文とハッシュ値の対応をチェーンで持つ表から逆引きする）です。
• このほか，ブロックチェーンに必須の技術（正解はハッシュ関数，3問），マルウェアの検出手法（4問）， デジタルフォレンジックス（2問），前方秘匿性（2問）などの選択肢に出てきます。

出題された過去問（59問）

リンク先の年度ページで，問題と解説を読めます。

関連する用語

ディジタル署名（デジタル署名）