ハッシュ関数とハッシュアルゴリズム ~PKI基礎④~

PKI

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

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

ハッシュ関数とは

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

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

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

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

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

少し図解です。

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

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

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

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

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

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

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

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

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

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

MD5(Message Digest Algorythm 5)

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

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

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

強衝突耐性と弱衝突耐性の違いを正しく認識せずに社会問題になった事件があります。オーストラリアの交通裁判所でMD5を利用した証拠が無効である、という判決が下ったのです。正しい知識があれば、証拠の有効性(真正性)に問題ないことを認識でき、違う結末になっていたと思います。
興味があれば以下のページを読んでみてください。
ハッシュ値の有効性 ITに疎い裁判官が起こした問題 (2/2)
裁判での証拠の真正をITの知識で判断しなければならないケースがある。オーストラリアでのある裁判では、ITの知識を十分に備えていない裁判官が後に禍根を残しかねない判決を下したのだった。

SHA(Secure Hash Algorithm)

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

SHA-0

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

SHA-1(シャーワン)

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

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(ハッシュ値:224bit)
  • SHA-256(ハッシュ値:256bit)
  • SHA-384(ハッシュ値:384bit)
  • SHA-512(ハッシュ値:512bit)
  • SHA-512/224(ハッシュ値:224bit)
  • SHA-512/256(ハッシュ値:256bit)

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

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

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

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

SHA-3(シャースリー)

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

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

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

まとめ

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

コメント

  1. […] ハッシュの詳しい説明は「ハッシュ関数とハッシュアルゴリズム ~PKI基礎④~」とか「ハッシュ関数」など、調べればわんさか出てきます。 […]