ハッシュ関数とハッシュアルゴリズム

デジタル署名は「秘密鍵で暗号化した平文は、ペアとなる公開鍵でしか復号化出来ない」という理論に基づいて成り立っています。

しかし、平文全体に対して秘密鍵で暗号化⇒公開鍵で復号化という処理をすると、平文が長大であるほど演算に時間が掛かってしまい、実用的ではなくなってしまいます。そこでハッシュ関数を利用し、平文を一定の長さに変換してから署名する仕組みが一般的になっています。

この記事の目次

ハッシュ関数とは
ハッシュアルゴリズムの種類
1. MD5 (Message Digest Algorythm 5)
2. SHA (Secure Hash Algorithm)
まとめ

ハッシュ関数とは

まずは Wikipedia の説明を確認してみましょう。

ハッシュ関数 (ハッシュかんすう、英: hash function) あるいは要約関数とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。

引用元：Wikipedia

さすが wikipedia、難しいですね。箇条書きにまとめてみます。

どのような長さの文字でも、ハッシュ関数を通すと固定長の文字列 (ハッシュ値) が出力される
ハッシュ値は指定されたハッシュアルゴリズム (ルール) に従って出力されるため、同じ文字列とアルゴリズムであれば同じハッシュ値が得られる
文字列 (情報) が 1 文字 (バイト) でも変わると、ハッシュ値は大きく変わる
特定のハッシュ値を出力するメッセージを見つけ出すのは非常に困難 (弱衝突耐性)
ハッシュ値が一致する２つメッセージを見つけ出すのは非常に困難 (強衝突耐性)

以上のような特性を持っています。

少し図解です。

Hello という平文が記載されたテキストファイルを SHA2 というハッシュアルゴリズムで処理すると「185F8DB3227～～～～」というハッシュ値が得られます。

これは元のデータとハッシュアルゴリズムが分かれば、誰がやっても同じハッシュ値が得られます。

では Hello に「!」を付けて SHA2 で処理してみましょう。

ハッシュ値が「334D016F755C～～～～」となりました。「!」マーク１つ付くだけでハッシュ値が大きく変わりましたね。

この特性は元のデータが改ざんされていないかの確認に利用できます。

A さん B さんを例に見てみましょう。

B さんは平文のハッシュ値を求めます。
出力されたハッシュ値を B さんの秘密鍵で暗号化します。
暗号化されたハッシュ値を平文に付与して、A さんに送ります。
A さんは平文に付与されている暗号化されたハッシュ値を、B さんの公開鍵で復号化します。
A さんも平文自体のハッシュ値を求めます。
復号化したハッシュ値と平文から得られたハッシュ値が一致するか確認します。

復号化したハッシュ値と送られてきた平文から求めたハッシュ値が一致したら、送られてきた平文は間違いなく B さんが送ってきたものであるという証明になります。また、途中で平文の改ざんなどが発生した場合も、⑤で求めるハッシュ値が大きく異なるため検知することが可能となっています。

ハッシュアルゴリズムの種類

代表的なものを紹介します。

MD5 (Message Digest Algorythm 5)

与えられた情報から 128 bit のハッシュ値を出力するアルゴリズムです。128 bit なので 32 桁の 16 進数となります。

MD5 は同じハッシュ値を持つ原文のペアが、普通のパソコンレベルで探索出来てしまうため、安全性が低いアルゴリズムです。言い換えれば MD5 は強衝突耐性が低い、ということです。

狙ったハッシュ値を出力させるのは現時点でもほぼ不可能なため、弱衝突耐性はあります。
そのため、現在はセキュリティ用途で利用するのは推奨されておらず、インターネットに公開しているファイルのチェックサム (ファイルの改ざんや欠損がないことを確認する) などに利用するのが主な利用用途となっています。

強衝突耐性と弱衝突耐性の違いを正しく認識せずに社会問題になった事件があります。オーストラリアの交通裁判所で MD5 を利用した証拠が無効である、という判決が下ったのです。正しい知識があれば、証拠の有効性 (真正性) に問題ないことを認識でき、違う結末になっていたと思います。
興味があれば以下のページを読んでみてください。

ハッシュ値の有効性　ITに疎い裁判官が起こした問題

裁判での証拠の真正をITの知識で判断しなければならないケースがある。オーストラリアでのある裁判では、ITの知識を十分に備えていない裁判官が後に禍根を残しかねない判決を下したのだった。

SHA (Secure Hash Algorithm)

SHA-0, 1, 2, 3 の 4 つが存在します。

SHA-0

SHA-0 は発表後まもなく欠点が発見され、欠点が改善されたものが SHA-1 となりました。実質 SHA-0 はなかったと思って差し支えありません。

SHA-1 (シャーワン)

SHA-1 は与えられた情報から 160 bit のハッシュ値を出力します。

2005 年に SHA-1 に対して効果的な攻撃方法が発見され、より安全性の高い SHA-2 への移行が推奨されていました。

今では SHA1 の証明書を使った Web サイトを開くと、ブラウザによって閲覧できなかったり警告が出たりするようになっています。

ちなみに最近騒がれたのは Google と CWI が SHA-1 の強衝突耐性の突破に成功した、というニュースです。
https://internet.watch.impress.co.jp/docs/news/1046144.html

SHA-2 (シャーツー)

SHA-1 を改良したとなります。SHA-2 はバリエーションが豊富で以下の種類があり、全てを総称して SHA-2 とされています。

SHA-224 (ハッシュ値：224 bit)
SHA-256 (ハッシュ値：256 bit)
SHA-384 (ハッシュ値：384 bit)
SHA-512 (ハッシュ値：512 bit)
SHA-512/224 (ハッシュ値：224 bit）
SHA-512/256 (ハッシュ値：256 bit）

ベースはS HA-256 と SHA-512 となっています。

SHA-224 は SHA-256 で出力されたハッシュ値を 224 bit に切り詰めたもの、SHA-384 は SHA-512 で出力されたハッシュ値を 384 bit に切り詰めたものとなります。SHA-512/224 と SHA512/256 についても SHA-512 で出力されたハッシュ値を 224 bit、256 bit に切り詰めたもです。

大きな違いは SHA-256 は 32 bit CPU、SHA-512 は 64 bit CPU に最適化されている点です。

ハッシュ長が長い方がセキュリティ的な強度が高いですが、負荷が高くなります。ただし、現状 SHA-256 でも必要十分な強度となっているため、一般的には SHA-256 が利用されている状況です。

SHA-3 (シャースリー)

SHA-3 は SHA-1 の脆弱性が SHA-2 にまで波及することが懸念されたため、コンペにより公募されたアルゴリズムです。

SHA-X と名前は付いているものの、SHA-2 までの構造と全く異なるアルゴリズムです。

当初危惧されていた SHA-2 に対して有効な攻撃手法が見つかってないことから、SHA-3 の導入を急いで進める必要性が無くなってきているのが実情です。

まとめ

ハッシュ関数に関わる技術は色々なものに利用されています。PKI においても重要な役割を担っているので、しっかり理解することをおすすめします。

リンク