認証基盤のセキュリティとハッシュ関数

2020/11/15 (Sun)

セキュリティに関する注意事項
ハッシュ関数とは
なぜ認証基盤にハッシュ関数が必要なのか
著名な暗号学的ハッシュ関数
暗号学的でないハッシュ関数を作りその脆弱性を見てみる
特殊なハッシュ関数など
おわりに
Reference

こんにちは。ソフトウェアエンジニアの淵脇です。私は日経グループ全体のサービスにおける認証・認可を支える「日経ID」といわれるプラットフォームの開発に携わっています。日経IDの開発チームは「NIDチーム」と呼ばれ、日々日経のサービスにおける認証・認可のユーザ体験の向上を目指し奮闘しております。

本日は認証・認可の大切な技術要素であるハッシュ関数について、「認証・認可基盤における役割」と、「様々なハッシュ関数の特性と用途」といった2つの観点から具体的な実装を交えて解説したいと思います。

セキュリティに関する注意事項

以下の文章はセキュリティに関する内容を含みますが、その正当性は保証しておりません。また、わかりやすさのために正確性を一部欠いている箇所も存在します。実装にあたっては正式なセキュリティレビューのもとに行ってください。

ハッシュ関数とは

Wikipedia によると、著名なハッシュ関数の一つである SHA-2 のアーキテクチャは下記のような感じだそうです。

Wikipedia - SHA-2 より

と、これだけ見ても何がなにやらという感じかなと思います。まず一般に「ハッシュ関数」と聞いて想像される定義は次のようなものがあるのではないでしょうか。

暗号化するための関数
復元が難しい文字列を出力するための関数
改ざん防止のために用いられる署名
データが壊れていないか確認するためのチェックサム

これらは（用語の曖昧さはひとまずおいておくとしても）、一部のハッシュにそういった性質があるというだけで、「ハッシュ関数」自体の定義ではありません。ハッシュ関数自体は例えば [1] では「データオブジェクトに基づいて値を計算するアルゴリズム」などと定義されています。ちなみに「あるデータに対して一意の値を返す」という意味は当然含まれているものとして扱うことが多いですが、こちらはどちらかというと「関数（数学）」の定義によるところが大きいと考えています。

さて、この定義に従い我がNIDチームの総力を結集し、独自に開発した最先端ハッシュ関数がこちらです！

public class NidHash {
  public static long hash(int[] data) {
    return 0;
  }
}

なんということでしょう。単に0という固定値を返すだけの関数がハッシュ関数になってしまいました。これは数学においてはよくある話ですが、定義の範囲内で極端な例というものも考えうるという話です。これを見ると「改ざん防止のための用いられる署名」などというものが単に「ハッシュ関数」といわれるものに当然備わっていると考えるのは違うというのが体感できたのではないでしょうか。

また「ハッシュ関数は復元ができないので暗号とはことなる」という話も聞いたことがある方も多いかと思います。このような感じで一般にハッシュ関数として想像される性質と、定義が許す範囲ではかなり差があるため、「実用的なハッシュ関数」には次の性質をいくつか要求することが多いです。

入力は任意長バイト、出力は固定長バイトとする
ハッシュ関数 $f$ について、 $f(M_1) = f(M_2), M_1 \neq M_2$ を満たす入力ペアの発見が困難（強衝突困難性）などの各種耐性を持つ。
計算コストが非常に高い or 非常に低いのどちらか

「情報が失われることがないようにデータを無限に圧縮することは不可能である」というシャノンの情報源符号化定理を考えると、1.のように入力が任意の長さであるのに対して出力が固定長であるような関数は、情報の損失が発生する関数である、つまりハッシュ関数から元の文字列を完全に復元することはできないということを意味しています。また、3はその用途によりデータ破損検出のためのチェックサムとして使うのか、または改ざん防止やセキュリティのために用いるのかによって極端に振り切ることが多いです。これらの性質を考えると「ハッシュ関数」といわれるもののイメージに近くなるのではないでしょうか。

なぜ認証基盤にハッシュ関数が必要なのか

認証基盤はもちろんセキュリティのためにあるものです。そのため、用いるハッシュ関数も「暗号学的ハッシュ関数」といわれ次のような特性を備えていることが必要になります。

原像計算困難性
第2原像計算困難性
強衝突耐性

詳細については[2]などが参考になりますが、ざっくりいうとハッシュ値からもとのメッセージの情報がわかりにくいというものです。

一般に認証・認可基盤では様々な所にこのような暗号学的ハッシュ関数を含む各種ハッシュ関数を用いていますが、例えばよく用いられるケースとしては「パスワードの保存」があります。現在の一般的な認証基盤では暗号学的ハッシュ関数 $h : M \rightarrow h(M)$ を用いて次のような処理を行っていることが多いです。

初回ユーザー作成時、設定されたパスワード $P$ に対し、DBに $H = h(P)$ を保存する。もとのパスワード $P$ は破棄する。
ログイン時、入力されたパスワード $M$ に対し、 $h(M)$ を計算し、DB上の記録 $H = h(P)$ と比較する。
一致していたらログイン成功、不一致ならログイン失敗とする。

実際にはこの他にソルトの付与などいくつかのステップを踏みますが、大まかにはこのような感じになります。なぜこのようにハッシュ関数を挟んだ複雑な手順を取るかというと、例えば何らかの事故で情報漏えいが起き、DBに記録されたデータが流出した場合にパスワードそのものの流出を防ぐという効果[3]があります。もちろん流出しないのが一番ではありますが、多層防御の考えに従いセキュリティをあらゆるレイヤーで確保するということが重要です。

よくパスワードを忘れたという場合に「メール等でパスワードを教えてくれる」サービスはあまりなく、「新規パスワードの再設定」というステップになるケースが多いのは1.で元のパスワードを廃棄しているためです。

著名な暗号学的ハッシュ関数

著名な「暗号学的ハッシュ関数」は次のようなものがあります。

MD5
- 早々に衝突耐性が破られており、現時点で使用するのは危険
- レインボーテーブル[4]による原像攻撃も実用的になってきた
SHA-1
- 一昔前までのデファクトスタンダード（今はむしろ非推奨）
- Google の研究者により衝突耐性がやぶられた[5]
- 有効な原像攻撃はまだ存在しないが、速やかなSHA-256等への移行が求められる
- あまりにも多くのシステムで使われてしまったため移行コストが問題になっている
SHA-2
- SHA-1 から移行する場合によく選ばれる
- 執筆時点現在ではまだ有効な攻撃法は見つかっていない
- 処理が軽い（これは一長一短ある）
bcrypt
- ブルートフォース攻撃に耐えられるよう処理を重くする機能を持つ
- cost といわれるパラメータにより処理の重さを指定できる
Argon2
- 処理の重さだけでなく使用するメモリサイズも指定できる（メモリ困難性）
- メモリ困難性により GPU や ASIC を用いたブルートフォース攻撃に耐性がある
- サイドチャネル攻撃への耐性がある

サイドチャネル攻撃というのは例えば応答時間や周りに出ている電磁波などを解析し攻撃する手法です。有名なところでは最近CPUに対する攻撃手法として一世を風靡した Meltdown および Spectre [6] などがあります。サイドチャネル攻撃は IoT への攻撃手法としても興味深いところがあり、また別途紹介したいと思います。

暗号学的でないハッシュ関数を作りその脆弱性を見てみる

では「暗号学的でない」ハッシュ関数を実際に作り、その脆弱性を見てみたいと思います。

public class NidHash {
  private static final int MOD = (int) 1e9 + 7;
  private static final int B = 13;

  public static long hash(int[] data) {
    long ret = 0;
    long v = 13;
    for (int b : data) {
      ret += b * v % MOD;
      ret %= MOD;
      v = v * B % MOD;
    }
    return ret;
  }
}

これはローリングハッシュといわれる、主に文字列検索で実際によく使われるハッシュアルゴリズムの簡易実装になります。競技プログラミング界隈では原像計算困難性が著しく低いハッシュとして有名であり、単純な実装であれば大体撃墜される極めて脆弱（だが少し工夫すれば計算量も低く大変便利）なハッシュです。これは簡単に言えば $hash(data) = data[0] B^1 + data[1] B^2 + data[2] B^3 + ... \mod MOD$ という関数になります。

さて、ここでMODは $1e9 + 7$ という値ですが、これは実は素数になっています。そのため $B$ に対して $B \cdot C = 1 \mod MOD$ となるような $C$ は拡張ユークリッド互除法やフェルマーの小定理などの手法で非常に早く計算可能であることが知られています。ここで、与えられたハッシュ値 $H$ に対して、1文字からなる攻撃文 $attack = [H \cdot C]$ という入力を考えてみましょう。ハッシュ関数に入れると $hash(attack) = B \cdot C \cdot H = H \mod MOD$ となり、ハッシュ値 $H$ を復元する攻撃メッセージの作成に成功してしまいました。

このように暗号学的でないハッシュ関数を用いてしまうと、ハッシュ値が流出したときにそのハッシュ値になるような値が逆算できてしまうことがあります。このようにして見つかった値はユーザが設定したパスワードとは異なるものの、前前節で記載したロジックに従い認証要求をするとログインできることがわかります。そのため、セキュリティ上脆弱ということになってしまうのです。

特殊なハッシュ関数など

では最後に特殊な性質を持つハッシュ関数として準同型ハッシュ関数というものをご紹介します。これはわかりやすくいうと

「2個の入力メッセージに対して、もとの入力メッセージがわからなくてもそれぞれのハッシュ値があれば、元のメッセージを連結したハッシュ値も求められるハッシュ関数」

です。形式的な定義はこちらになります。

ハッシュ関数 $h : M \rightarrow H$ のメッセージ空間 $M$ 及びハッシュ値空間 $H$ に、モノイドとしての二項演算 $M \cdot M \rightarrow M$ 、および $H * H \rightarrow H$ を仮定します。

このとき、2つのメッセージ $M_1, M_2$ に対し、 $h(M_1 \cdot M_2) = h(M_1) * h(M_2)$ を満たすハッシュ関数を準同型ハッシュ関数と呼びます。

定義中の二項演算ですが、例えば $H$ が数値ならMOD加算やXORなどが考えられますし、 $M$ が文字列なら2個の文字列の連結などが考えられます。形式的な定義だけだとわかりにくいかと思いますので、実際に一つ作ってみましょう。

public class NidHash {
  public static long hash(int[] data) {
    long ret = 0;
    for (int b : data) {
      ret ^= anotherHash(b);
    }
    return ret;
  }

  private static final int MOD = (int) 1e9 + 7;
  private static final long A = 13234252;
  private static final long B = 1233135235235L;
  private static long anotherHash(long v) {
    return (v * A + B) % MOD;
  }
}

これは Zobrist Hash といわれるハッシュです（anotherHash は本来 SHA とかのほうがよいのですが、ここでは簡易実装しています）。入力するメッセージ $data1$ 及び $data2$ に対して、「配列の連結（例えば $data1 = [1,2,3], data2 = [8,9]$ のとき $[1,2,3] + [8,9] = [1,2,3,8,9]$ など）」という演算を考えます。すると、ハッシュ関数については $\oplus$ を数値のxorとすると $h([1,2,3]) \oplus h([8,9]) = h([1,2,3,8,9])$ といった演算が成り立ちます。

このような準同型ハッシュが何の役に立つのかという話ですが、性能改善に非常に役立ちます。例えば $N$ 個のデータ $A_i (i=0..N-1)$ をDBに格納しており、そのデータ破損検出のためにハッシュ $h([A_0, A_1, A_2, ...])$ を保存しているという状況を考えましょう。DBなのでもちろん更新クエリが来ることがあります。例えば $j$ 番目のデータ $A_j$ が $B_j$ になった、というケースを考えましょう。

このとき、通常のハッシュ関数であれば $h([A_0, A_1, ..., A_{j-1}, B_j, A_{j+1}, ...])$ といったハッシュ関数をまるまる計算し直しになります。通常ハッシュ関数は入力のデータサイズに比例して処理量が増えるため、一部のデータのアップデートにもかかわらずハッシュ関数の計算は $O(N)$ と重くなりがちです。しかし、準同型ハッシュ関数として先程のZobrist Hashを用いると $h([A_0, A_1, ..., A_{j-1}, B_j, A_{j+1}, ...]) = h([A_0, A_1, A_2, ...]) \oplus h([A_j]) \oplus h([B_j])$ となります。このとき右辺の第1項は以前のハッシュ関数であるため、差分計算だけでよくなり計算量が $O(N)$ から $O(1)$ へと激減します。