暗号理論(5) ~ 一方向ハッシュ関数 ~

暗号技術入門 第3版

暗号技術のすべて

一方向ハッシュ関数とは

前回の記事で, ハイブリッド暗号システムを紹介しました.

ハイブリッド暗号システムとは, 公開鍵暗号方式のデメリットの1つである「処理速度が遅い」ことを解決するための手法でありました.

また公開鍵暗号方式のもう一つのデメリットとして, 「man-in-the-middle攻撃に弱い」ことが挙げられます. これの対処法として, 「認証」というものが使われることを説明しました.

これから認証の話に入っていくのですが, その前に「正真性のチェック」をする手段である「一方向ハッシュ関数」について説明していこうと思います.

正真性とは, そのデータが本来のものである(本物である)という性質のことです.

例えば, Aliceさんが以下のような平文Aを作成したとします.

親愛なるBobへ

愛しています.
Aliceより.

Aliceさんは平文AをUSBに保存して, 自分の引き出しに入れておきました.

そして後日, この平文AをBobさんに送ることにしました.
このとき, 平文Aが

親愛なるBobへ

愛しています.
Aliceより.

となっていたら, 平文Aは正真性をもつと言えます.

一方, 悪意のある第三者Malloryが, USBを盗んで平文Aを以下のように書き換えたとします.

親愛なるBobへ

大嫌いです.
Aliceより.

このとき, 平文Aは正真性を持たないと言えます.

ではAliceさんが, この平文Aは正真性をもつかどうかを調べるにはどうしたらいいでしょうか.

1つの方法として, データをコピーしておき, 安全な場所に保存しておくことが挙げられます.
そして後日作業をするときに, コピー元のデータとコピーしたデータを比較して, 一致していたら正真性をもつことが言えます.

しかしこれはナンセンスです.
そもそも安全な場所に保存することができるならば, 正真性をチェックする必要がありません. さらにデータが巨大であった場合, コピーするにも, データを比較するにも時間がかかってしまいます.

ここで一方向ハッシュ関数の登場です.

一方向ハッシュ関数に対して入力データを与えると, ハッシュ値と呼ばれる固定バイト長の出力データを得ることができます.

任意長のどんなデータも一方向ハッシュ関数に入力すれば, 固定バイト長のハッシュ値を得ることができます.

また, 似ているデータが存在したとしても, そのハッシュ値は全く違うものになります.

例えば, パスワード「abcde」のハッシュ値(ここでは6バイトとします)が「15 0E 46 72 AD B8」だとしても,
パスワード「abcdf」のハッシュ値は「43 71 3E DD 96 CA」のように全く違うものになります.

このようにデータのハッシュ値を求めておいて, 次に利用するときにもう一度ハッシュ値を求めて, それらが一致するかどうかをチェックすることで, 正真性をチェックすることができます.

一方向ハッシュ関数がもつべき性質

次に, 一方向ハッシュ関数がもつべき性質について説明します.

一方向ハッシュ関数がもつべき性質は以下のものが挙げられます.

1. 任意長のメッセージから固定長のハッシュ値を計算する
2. ハッシュ値を高速に計算できる
3. メッセージが異なればハッシュ値も高確率で異なる

3番に注目してみましょう.

メッセージが1ビットでも異なれば, ハッシュ値は高確率で異なる値を取らないといけません. そうでないと正真性を確認することができないからです.
2つの異なるメッセージが同じハッシュ値をもつことを衝突と言います.

1番で述べたようにハッシュ値は固定データ長なので, 取りうる値の個数は有限です. 例えばハッシュ値が80ビット長だとしたら, 個のハッシュ値が存在します. しかし入力されるデータの個数は個以上なので, 鳩の巣原理より, 必ず同じハッシュ値をもつものが存在します.
つまり衝突は免れないのです!!

衝突がおきにくい性質のことを「衝突耐性」と言います.
衝突耐性には2種類あって, 弱衝突耐性と強衝突耐性があります.

弱衝突耐性とは, あるメッセージのハッシュ値が与えられて, 同じハッシュ値を持つ別のメッセージを見つけ出すことが非常に困難な性質のことを言います.
強衝突耐性とは, ハッシュ値が一致するような異なる2つのメッセージを見つけ出すことが非常に困難である性質のことを言います.このとき, ハッシュ値はどの値をとっても構いません.

暗号技術で用いる一方向ハッシュ関数は, 弱衝突耐性と強衝突耐性の2つを持ち合わせる必要があります.

一方向性とは

一方向ハッシュ関数の「一方向」とはどういう意味でしょうか.

これは, あるデータからハッシュ値を計算することはできるが, ハッシュ値からあるデータを復元することはできないという意味です.
窓ガラスを割ると破片が飛び散りますが, その破片から窓ガラスを復元することはできませんね. それと同じことです.

一方向性は非常に重要な性質で, 今後「パスワードを元にした暗号化」や「擬似乱数生成器」を紹介するときに一方向性という概念を使用します.

一方向ハッシュ関数の応用例

一方向ハッシュ関数には以下のような応用例があります.

• ソフトウェアの改竄検出

これは最初に説明しましたね. 途中で文書が書き換えられていた場合は, 異なるハッシュ値が得られる可能性が高くなってしまい, 改竄検出されてしまいます.

• パスワードを元にした暗号化
• メッセージ認証コード
• デジタル署名
• 擬似乱数生成器
• ワンタイムパスワード

これらは別の記事でそれぞれ紹介したいと思います.

一方向ハッシュ関数への攻撃

これまで紹介したきた暗号技術には, それぞれ攻撃手法が存在しました. 一方向ハッシュ関数にはどのような攻撃手法が存在するでしょうか.
なかなか想像しにくいですね. 衝突耐性が強ければ同じハッシュ関数を求めることも難しいです.

ですが, 現段階では2つの攻撃手法が存在します. それらを紹介します.

弱衝突性を破る攻撃 (ブルート・フォース・アタック)

例えば以下のような状況を考えてみましょう.

AliceさんBobさんに電子ラブレターを書こうと思っています. そしてその電子ラブレターを12/25(クリスマス)にBobさんに送信しようと思っています.
12/24(クリスマスイブ)の夜, Aliceさんは電子ラブレターを作成し, PC内に保存しておきました.
ラブレターの本文には, 「Bobへ. あなたのことをとても愛しているわ. Aliceより」
そしてそのデータのハッシュ値をUSBに保存しておき, USBは安全な場所に保管しておきました. そしてAliceさんは寝床につきました.

その後, Aliceさん宅にEveさんが泥棒しに入り, PC内の電子ラブレターを書き換えようと思いました.
Eveさんは悪いやつなので, ラブレターを「Bobのことなんて大嫌い」というような要旨に書き換えようと思いました.

しかし, ただ書き換えてもいけません. なぜならAliceさんは元データのハッシュ値を持っているので, 書き換えてもハッシュ値が違う可能性が高いからです.

そこでEveさんは「Bobのことなんて大嫌い」というような要旨の文章を大量に機械的に作成しました.
例えば,
「Bobへ. あなたなんて大嫌い. Aliceより」
「Bobへ. Bobなんて大嫌い. Aliceより」
「Bobへ. あなたなんて大嫌いだわ. Aliceより」
「Bobへ. あなたなんて大嫌いよ. Aliceより」
「Bobへ. 大嫌いよ, あなたなんて. Aliceより」
「Bobへ. 大嫌い, Bobなんて. Aliceより」
「Bobへ. 顔も見たくないわ. Aliceより」
「Bobへ. 大嫌い, 顔も見たくない. Aliceより」
などなど...

そこで, たまたま元データとハッシュ値が同じである文章が作成できたとします.
Eveさんは悪い笑みを浮かべながらそのデータに書き換え, 家を後にしました.

そして12/25当日, AliceさんはBobさんに書き換えられたデータを送信してしまいました.

返事を待っていたのに, Aliceはずっと返事を得られないまま, 今後Bobと連絡を取れなくなってしまいました...

このように似ている文章を大量に作成し, 同じハッシュ値のものを見つけることによる攻撃が可能です.
いわゆる「ブルート・フォース・アタック」ですね.
この手法は, 一方向ハッシュ関数の「弱衝突耐性」を破ろうとする攻撃です.

強衝突耐性を破る攻撃 (誕生日攻撃)

上と似たストーリーを考えます.
悪いEveさんは, あらかじめハッシュ値が同じである2つの文章を作成しました. その2つの内容は,
「Bobへ. 愛しているわ. Aliceより」... (1)
というものと,
「Bobへ. 大嫌い, 顔も見たくない. Aliceより」 ... (2)
というものです.

そしてEveは(1)の文章とそのハッシュ値をAliceに送信します. Aliceはそのハッシュ値が正しいものかを実際に計算することで確認できます.
そしてその後, Eveは(1)の文章を(2)にすり替えます.

こうすることで, (2)の文章をBobあてに送ってしまうことで, 上のストーリーと同じ悲劇が実現されてしまいます.

このように, 同じハッシュ値をもつ2つの文章を事前に用意することによる攻撃を誕生日攻撃ということがあります. 誕生日攻撃は, 一方向ハッシュ関数の「強衝突耐性」を破ろうとする攻撃です.

一方向ハッシュ関数で解決できない問題

一方向ハッシュ関数は, 正真性をチェックするためにとても有効な手段であることがわかりました. しかしこれだけでは不十分です.
例えば, 能動的攻撃者MalloryがAliceのふりをして, Bobにメッセージとハッシュ関数の両方を送る場合を考えます.
Bobはメッセージのハッシュ値を実際に計算し, 送られてきたハッシュ値と比較して一致することが確認できれば正真性をチェックすることができます.

しかし, 送られてきたメッセージは実際にはAliceさんが送ったものではありません.
このように, メッセージの正真性をチェックすることはできても, 本当に意図した人物からのメッセージなのかということはチェックできません.
意図した人物からのメッセージなのかをチェックすることを認証と言います.

認証を行うための技術として, 「メッセージ認証コード」と「デジタル証明書」があります. これらは別の記事で紹介したいと思います.

暗号技術入門 第3版

暗号技術のすべて