ハッシュ関数

1.ハッシュ関数とは

(1)ハッシュ関数とは

　メッセージダイジェストも呼ばれ、メッセージのダイジェスト版です。
たとえば、原稿用紙400字の文章を、要約して20字にするような感じです。
ですが、ハッシュの場合は、何がかかれているのかわからないようにハッシュ（細切れ）にします。
ハッシュ関数の代表的で身近なものは、MD5、SHA-1、SHA-256です。情報処理安全確保支援士試験では、この3つくらいの名称しか登場しません。
ハッシュ関数にはMD5やSHA-1がありますが、これらの危殆化の問題があり、SHA-256などが利用されるようになっています。
※hashとは、「細切れにする」などの意味があります。

(2)ハッシュ関数の目的

　目的は、以下です。
❶暗号
パスワードをそのまま持っておくと危険です。誰かに見られる。
そこで、ハッシュ値を持っておきます。パスワードが入力されたら、ハッシュ値を計算して、それが、持っていたハッシュ値と一致すればOK、という仕組みです。

❷改ざん検知
元の文章と、ハッシュ値を同時に相手に送ります。
元の文章が改ざんされていた場合、ハッシュ値が変わります。受信した側は、元の文章を自らハッシュし、ハッシュ値が一致するかで、改ざんされていないかを判断できます。一般的には、ハッシュ値はデジタル署名などで暗号化されるので、ハッシュ値も改ざんすることはできません。


ハッシュ関数が暗号化の方式というのには、違和感があります。
たとえば，Windowsのシステムではパスワードをそのまま保存せずに，ハッシュ値にして暗号化して保存しています。暗号とは、第三者が内容を読むことができないようにすることですから、立派な暗号です。
ただ、復号することができないので、少し違和感があるのでしょうね。

ハッシュ関数の機能は、暗号だけでしょうか。それだけではありません。改ざん検知としても利用されます。その手順の理解を含めて、以下の過去問（H24秋AP午前）を解きましょう。

過去問（H24秋AP午前）
問38　手順に示すハッシュ関数とメッセージダイジェストの処理を行うことで得られるセキュリテイ上の効果はどれか。ここで，メッセージダイジェストは安全な方法で保護され，改ざんや破壊がされていないものとする。 〔手順〕 (1)送信者Aは，電子メールの本文からハッシュ関数を用いて，メッセージダイジェストを作成する。電子メールの本文とメッセージダイジェストを別々に受信者Bに送信する。 (2)受信者Bは受信した電子メールの本文からハッシュ関数を用いて，メッセージダイジェストを作成する。その作成したメッセージダイジェストと，受信したメッセージダイジェストを比較する。 ア　電子メールの改ざんの有無の確認 イ　電子メールの誤送信の防止 ウ　電子メールの送達確認 エ　電子メールの盗聴の防止

↓
↓
↓
↓
↓
答えはアです。

以下の情報処理安全確保支援士試験の問題を考えよう。

過去問（H21春SC午前2問6）
「160ビットの出力データを生成し、改ざんの検出に利用するアルゴリズム」は何か。

↓
↓
↓
↓
↓
この問題の正解はSHA-１である。

2.ハッシュ関数（メッセージダイジェスト）の特徴

(1)プロ野球ニースでハッシュ関数の特徴を考えよう

プロ野球ダイジェスト（プロ野球ニース）の特徴を言え。 　※ハッシュ関数を意識して

（1）ダイジェストの放送時間は決まっている
試合がどんなに長くても、短くても、ダイジェストの放送時間は（だいたい）決まっている。
放送時間の枠があるので、たとえば、1試合あたり1分とか2分とか。

（2）同じ試合のダイジェストは同じ
プロ野球ファンの人は、好みの球団が勝つと、プロ野球ニースをハシゴする人がいる。しかし、その内容は各局でほとんど同じだ。同じ試合からできるダイジェスト版は（ほぼ）同じである。

（3）ダイジェストから本当の試合は見れない
ダイジェストで放送されなかったシーンなどを知りたい人もいるだろう。でも、それは絶対に不可能だ。本当の試合からダイジェスト版は作れるが、ダイジェスト版から本当の試合を作ることはできない。


ハッシュ関数は、ハッシュ値（メッセージダイジェスト）を作成するもので、プロ野球のダイジェスト版が短時間での内容であるのと同様に、メッセージダイジェストは文書の短編版です。

特徴は以下だ。上記のプロ野球のダイジェスト版と特徴が似ているのが分かる。
（1）どんな長さのデータも必ず固定長になる
（2）同じメッセージからは同じハッシュ値が出力される
（3）ハッシュ値から元のメッセージを求めることはほぼ不可能　←この特徴から、暗号としての機能を持つ。

＋（4）衝突発見困難性：ハッシュ値が同じとなる2つの元データを求めることが難しい性質です。過去問（R5春SC午前2問4改）では、「衝突発見困難性とは，ハッシュ値が一致する二つの元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のこと」とあります。

過去問（H24春AP午前）を見ましょう。

過去問（H24春AP午前）
問38 ディジタル署名などに用いるハッシュ関数の特徴はどれか。 ア　同じメッセージダイジェストを出力する異なる二つのメッセージが，容易に求められる。 イ　メッセージが異なっていても,メッセージダイジェストは同じである。 ウ　メッセージダイジェストからメッセージを復元することは困難である。 エ　メッセージダイジェストの長さはメッセージの長さによって異なる。

↓
↓
↓
↓
↓
先ほどの特徴を理解していれば，簡単だったことでしょう。
正解はウです。
アは，メッセージダイジェストからメッセージを求めるのはほぼ不可能です。
イは，メッセージが異なれば、メッセージダイジェストも異なります。
エは，メッセージダイジェストの長さは、常に同じです。

もう一問、以下の情報処理安全確保支援士試験の問題を解こう。

過去問（H22SC春午前Ⅱ問1）
セキュアハッシュ関数SHA-256を用いて、32ビット、256ビット、2048ビットの三つの長さのメッセージからハッシュ値を求めたとき、それぞれのメッセージのハッシュ値の長さはどれか。

↓
↓
↓
↓
↓
答えは当然ながら全て256ビットである。


話が変わりますが、
ファイル名だけ変更した場合、ハッシュ値はどうなりますか？
　ファイル名を変えても、ハッシュ値は変わりません。ファイル自体のデータとファイル名は別だからです。
試しにやってみましょう。Windowsのパソコンで、コマンドプロンプトを立ち上げましょう。
以下のコマンドを入力します。file1.txtというファイルを、sha1でハッシュ値を求めるという意味です。
c:\certutil -hashfile file1.txt sha1
c:\certutil -hashfile file1_rename.txt sha1  ←こちらは、同じファイルのファイル名だけを変えています。

どちらも、同じハッシュ値が表示されています。

(2)本当に不可逆か

単純なものであれば、レインボーテーブルにデータベース化されている。 以下、ハッシュ値から元の値を求めるサイトもある。（悪用禁止）
https://crackstation.net/

3.ハッシュ関数とシノニム（または衝突：collision）

過去問を参考に、シノニムについて整理したい。

参考：過去問（H23春AP午後）
ハッシュ関数Hash(key)は,  keyを基にデータの格納位置を算出して,戻り値として戻す。格納位置は1～Nの整数となる。関数Hash(key)が,異なるkeyから同じ格納位置を算出することを,シノニムの発生という。

シノニムは、衝突（collision）という言葉でも使われる。Synonymとは「同意語」という意味であり、ハッシュ関数の結果が同じことからこう呼ばれるのだろう。

次の問題を見てみよう。

過去問（H21春AP午後問2設問1）
衝突（collision）とはどのような現象か。“キー”と“ハッシュ関数”という単語を用いて，35宇以内で述べよ。

↓
↓
↓
↓
↓
試験センターの解答例は「違うキーの値でも，ハッシュ関数を適用した結果が同じ値になること」

違う問題を見てみよう。

過去問（H17秋共通午前）
問2　4,999を除数とする剰余を用いるハッシュ関数で，キー値が12,500のレコードに対するシノニムレコードのキー値はどれか。 ア　2 イ　1,250 ウ　2,501 エ　17,499

↓
↓
↓
↓
↓
シノニムレコードなので、剰余が同じものを探せばよい。
12500 ÷ 4999 = 2 あまり2502
2 ÷ 4999 = 0 あまり2
1250 ÷ 4999 = 0 あまり1250
2501 ÷ 4999 = 0 あまり2501
17499 ÷ 4999 = 3 あまり2502
よって，エ

4.ハッシュ関数とソルト

　パスワードを暗号化するために利用されているハッシュ関数。ハッシュ値から元のパスワードデータを復元することができないというのが、ハッシュ関数の特徴である。

しかし、パスワードなんてしょせん10文字以内。
今のコンピュータ性能であれば、できるのでは？
この疑問に関して、ズバリ情報処理安全確保支援士試験の過去問（H20SV午後Ⅰ問4）で解説されている。

過去問（H20SV午後Ⅰ問4）

Ｍ君　：しかし,部門サーバのOSでは,パスワードはハッシュ化されています。ハッシュ値からパスワードを復元することは,困難なのではないでしょうか。 Ｈ主任：パスワード候補のハッシュ値をあらかじめ計算し蓄えておいたテーブルを利用して,ハッシュ値からパスワードを特定する方法もある。例えば,小文字のアルファベットと数字で作成される7文字のパスワードの候補数は,[　d　]で表されるから,約780億通りになる。1秒間にパスワードを1万回試すことができるとすると,すべてのパスワードを試すには,約91日必要だ。ところが,テーブルがソート済みで2分探索法を利用できるとすると,テーブルのデータ数をNとして,最大比較回数は[　e　]を超えない整数値になる。1回の比較に100ミリ秒かかるとしても,最大3.7秒で探索できることになる。 Ｍ君　：なるほど。ただし,約780億通りだとすると,テーブルのサイズはかなり大きくなりそうですね。 Ｈ主任：そのとおりだ。パスワードとハッシュ値の一組当たりのサイズを30バイトとすると,全体で約2.4 T (W)バイトのテーブルになる。しかし,レインボーテーブルというテーブルを用いた攻撃では,ハッジュ値の計算を併用することによって,テーブルのサイズを抑えつつ,数秒から数分でほとんどのパスワードを解読できたという報告がある。 Ｍ君　：それは危険ですね。では,どうしたらいいのでしょうか。 Ｈ主任：パスワードの情報だけでなく,ソルトという情報を付加してハッシュ値を計算することによって,ハッシュ値からパスワードを特定しにくくする方法を採用したOSを導入するのがいいだろう。 設問4 サーバに対する不正ログインについて, (1)~(3)に答えよ。 (1)本文中の[　d　]，[　e　]に入れる適切な数式を解答群の中から選び,記号で答えよ。 　解答群 　ア　736　　　イ　36^　　　 ウ　36^^7　　　 エ　36^^7 　オ　log2N　　カ　log10N　　キ　N log2N　　ク　Nlog10N (3)ソルトを使用するとハッシュ値からパスワードを特定しにくくなるのはなぜか。その理由を, 40字以内で具体的に述べよ。

↓
↓
↓
↓
↓
この、問題(3)を考えましょう。
難しい問題ですが、順を追って説明します。

■パスワードの保存方法
ユーザ認証用のパスワードは、認証サーバにて、そのままの平文で保存されているわけではない。ハッシュ値によって暗号化されている。


最近は不正アクセスによって、OCNのIDパスワードが最大400万件流出の可能性というニュースを聞きました。でも、確かにこのようにハッシュ化されていれば、元のパスワードは分からないですね。
　そうなんだ。でも、最近は攻撃者もあの手この手で攻めてくる。
以下のように、パスワードとハッシュ値をデータベース化しておくのだ（レインボーテーブル）。そして、不正入手したパスワードのハッシュ値から元のパスワードを見つければよい。

そこで、ソルトの登場だ。パスワードをハッシュするときに、ランダムな値（ソルト）を付加する。これにより、同じパスワードでも、ソルトが違うので、ハッシュ値も違う。攻撃者はレインボーテーブルを用意できなくなるのだ。

●解答●
・同じパスワードでもソルトが異なるとハッシュ値が変わるから
・攻撃者がソルトの値ごとにテーブルを用意する必要があるから

ちなみに、ソルト（salt)とは、塩コショーの「塩」で、ハッシュのセキュリティを強化するために、塩を振りかけるという意味である。

■事例
以下、LinuxによるBasic認証でもソルトが使われています。少し長いですが・・・・
認証の全体像（(4)ベーシック認証とダイジェスト認証） - 情報処理安全確保支援士 - SE娘の剣 -

（旧リンク）
Basic認証とDigest認証

5.フィンガープリント

情報処理安全確保支援士試験では、過去に登場したことはありますが、それほど重要ではないので、言葉だけ覚えておけばいいでしょう。
フィンガープリントを直訳すると「指の印刷」なので、指紋と考えればよく、その実体はハッシュ値である。たとえば、公開鍵であれば、そのフィンガープリントは公開鍵のハッシュ。

政府認証基盤(GPKI)のフィンガープリントは以下で公開されており、ブラウザの拇印を確認することで、検証することが可能だ。
https://www.gpki.go.jp/selfcert/finger_print.html

情報処理安全確保支援士試験の過去問を見てみよう。

過去問（H22春SC午後I問3）
設問1 (3)　PGPでは，通常，証明書のフィンガプリントを確認するが，正しいフィンガプリントの入手方法として安全と考えられるものを一つ挙げ， 30字以内で述べよ。

↓
↓
↓
↓
↓
試験センターの解答例：紙媒体でフィンガプリントを入手する。

■フィンガープリントの例１：メールの署名
メールの署名に以下のように付けている場合もあるだろう。

♪♪------------♪♪------------ Shihoo Samon samon@example.com Fingerprint：9c07 e4a4 3567 0c3d 23f3 42c2 83f1 62b6 c0bc 932d

■フィンガープリントの例２：ブラウザ
ブラウザに証明書が入れられているのであれば、ブラウザから確認できる。
「インターネットオプション」「コンテンツ」「証明書」で該当の証明書を開く。「詳細」タブの「拇印」で確認できる。