OpenSSH 情報

2007/12/28 - [misc][暗号]「原理から学ぶネットワーク・セキュリティ 第4回 ハッシュ関数」の問題点

原理から学ぶネットワーク・セキュリティ 第4回 ハッシュ関数:ITproの問題点を挙げていきます.

一通り書きました. 作成中の段階では間違っていた部分があったのを確認していますが, 修正したつもりです. 私も暗号屋ではありませんので, 文章の内容の保証は致しません. 修正の御指摘は歓迎します.

導入部

データ構造としてのハッシュ/ハッシュ・テーブルと暗号技術のハッシュ関数を混同して説明するのは, 誤解を生むおそれがあります. 仮に暗号技術のハッシュ関数の説明の中でデータ構造としてのハッシュに触れる場合でも, 異なるものと説明したほうがよいでしょう.

ハッシュ関数の説明として, 一方向性だけが挙げられていますが衝突耐性についても触れておくべきです. 後のコラムで衝突耐性について触れられていますが, 内容は不正確です.

ハッシュ関数の実験

この部分の内容に問題はありません. ただし, 先に衝突耐性について触れていないので説明がつながっていないように思えます.

ハッシュ関数で改ざんを検出する

いきなり侵入者の話になる部分は言葉足らずであったり, rootkitがtarファイルである必要はないなど, 細かいツッコミどころはありますが, 大筋では問題ありません.

メッセージの改ざん防止

ただ,ハッシュ値も上書きされれば,意味がありません。そこでハッシュ値を添付する際は,事前に共有化した鍵(かぎ)でハッシュ値を暗号化して,メッセージに添付します(図6)。

この暗号化されたハッシュ値を「MAC」(Message Authentication Code)といい,特にハッシュを使っていることからHMACともいいます。受信側でも,受け取ったメッセージのハッシュを計算し,一方でMACを復号化してみて計算したハッシュと一致すれば,メッセージは改ざんされていないと分かります。

MACにはそこでハッシュ値を添付する際は,事前に共有化した鍵(かぎ)でハッシュ値を暗号化して,メッセージに添付しますという方式のものもあります. しかし, HMACはこのようなMACではありません. HMACの最終の出力はハッシュ関数の出力のため, 「復号」することはできません. HMACの定義はHMAC - Wikipediaで参照できます.

HMACを用いてメッセージの改ざん防止を行なう場合, 受信側でも秘密鍵とメッセージからMACを(再)計算し送られてきたものと比較します. MACを復号化して比較するのではありません.

電子署名の仕組み

HMACは,通信者AとBの間で改ざんを防止します。しかし,共有鍵を持っている人しか検証できませんし,認証機能もありません。そこで,送るデータのハッシュの暗号化に,秘密鍵を使うようにします。

図7のように,メッセージ送信者Aliceは,送るデータのハッシュ値を自分の秘密鍵で暗号化してメッセージに付加します。この付加された暗号文を電子署名といいます。メッセージを受信したBobは,そのメッセージのハッシュ値を計算します。そして電子署名をAliceの公開鍵で復号化して,ハッシュ値と比較します。一致すれば,そのメッセージは改ざんされておらず,しかもAliceその人が書いたものだと分かります。

このような仕組みでメッセージの正当性を保証することも可能です. RSAを利用する場合は, 「だいたい」このような仕組みで電子署名が行なわれています. が, RSAと共に広く使われている電子署名アルゴリズムであるDSAでは, 署名は「なにかを暗号化したもの」ではありません.

詳細は稲村さんの記事「電子署名≠秘密鍵で暗号化」をご覧下さい.

電子署名の計算において, メッセージそのものではなくメッセージのハッシュを利用する点は問題ありません. DSAでは, SHA-1の利用がアルゴリズムに組み込まれています. RSAではアルゴリズムには組み込まれていませんが, MD5やSHA-1と共に用いられるのが一般的です. ハッシュ関数の利用には, 処理量の軽減の他にも, 処理するメッセージのサイズを固定化できるなどの利点があります. 暗号化にも電子署名にも利用できるRSAでは, ハッシュ関数を利用することで選択暗号文攻撃を防ぐ効果もあります.(暗号技術大全 P. 523)

Javaアプレットに署名する

検証はブラウザ側で行います。Javaアプレットは,クラス・ファイル(アプレット本体),電子署名であるハッシュ値を秘密鍵で暗号化したもの,開発者の公開鍵__が1つのjarファイルにまとめられて一括でダウンロードされます(図8)。受信者側では送られてきたクラス・ファイルのハッシュ値を計算します。JavaアプレットではMD5,SHA-1の両方が使われているようです。

Javaのアプレットの電子署名にはDSAも利用できるので, 必ずしも開発者の秘密鍵で暗号化されたクラス・ファイルのハッシュ値を秘密鍵で暗号化したものが電子署名としてjarファイルに含まれるわけではありません.

また, 開発者の公開鍵だけでは不正確で, 開発者の公開鍵を含む証明書がjarファイルに含まれます.

参考: Understanding Signing and Verification (The Java Tutorials > Deployment > Packaging Programs in JAR Files)

shadowファイルに含まれる「ソルト」の役割

説明に大きな問題点はありません. なお, 塩は「sult」ではなく「salt」です.

GNU/Linuxのglibcではcrypt(3)の実装にMD5ないしDESを利用していることを触れておくべきでしょう. ここで上げられている例の場合, ソルトが'$'で終端されているのでcrypt()の内部ではMD5が利用されています.

なお, 末尾のcのプログラムはそのままではコンパイルできません. また, セキュリティの記事なのにパスを指定ないでカレントディレクトリのコマンドを実行しているのはいただけません.

50人のクラスで同じ誕生日の生徒がいる確率は?――ハッシュ値の衝突確率は意外に高い

このコラムは, ハッシュ関数の強衝突耐性と弱衝突耐性を混同しています. 強衝突耐性と弱衝突耐性は以下のような性質をいいます. 暗号技術におけるハッシュ関数では, この2つ(と一方向性)が満たされている必要があります.

強衝突耐性
ハッシュ値が一致する異なる2つのメッセージを見つけるのが難しい (それぞれのメッセージに意味がある必要はない). 誕生日のパラドックスから攻撃に2(N/2)のオーダーの試行が必要(Nはハッシュ関数の出力のサイズ(bit).
弱衝突耐性
あるメッセージのハッシュ値と同じハッシュ値を返す別のメッセージを見つけるのが難しい. 攻撃に2Nのオーダーの試行が必要.

コラム前半の誕生日のパラドックスの説明は問題ありません. しかし, 以下の記述には問題があります.

 一般的には,ハッシュ値の長さがNビットのときには,1/2のN/2乗の確率でハッシュ衝突が起きるといわれてます。MD5だと280回程度の試行で,目的のハッシュ値を出力できる入力値を見つけ出すことができます。

上記の引用は, 話の流れから考えるに強衝突耐性についての記述です.. ただし, MD5は128bitのハッシュ値を出力するので, 264回の試行とする必要があります. さらに, MD5は強衝突耐性については破られているので, 試行回数はもっと少なくて済んでしまいます.

例えば,配布されているFedora CoreのISOイメージのハッシュ値は,SHA1SUMというファイルに格納されています。偽物のISOイメージを作るには,原本と同じSHA-1値を出力するように短い“詰め物”ビットを加えればよいだけなのです。

この引用は先の引用の続きの文ですが, 突然弱衝突耐性の話になっています. 原本と同じSHA-1値を出力するためには2160の試行が必要です. たとえ, 280の試行回数で済んだとしても, 短い“詰め物”ビットを加えればよいだけといえるほど気軽な回数ではありません.

(2008/01/07) 意味のある複数のメッセージに対して同じMD5値を出力することが可能になった模様です. Nostradamus - Predicting the winner of the 2008 US Presidential Elections using a Sony PlayStation 3. SHA-1についてもそのうち同様の状況になることが予想されています. ただし, 上記では, 現実のハッシュ関数が例となっているとはいえ理想的なハッシュ関数の場合について議論されていますので, 論旨に変更はありません.