機密情報に関わる文字列の比較は == ではなく secure_compare を使おう

はじめに

パスワードハッシュやトークンなどの文字列を比較する際には、== ではなく Rack::Utils.secure_compare を使ったほうが良いということを学んだので、勉強の記録として共有します。

== での文字列比較の危険性

Rack::Utils.secure_compare を知るまでは、まさか == に危険性があるとは思いませんでした¹が、パスワードハッシュやトークンなどを比較する際には == は使用しないほうが良いです。

その理由は、Timing Attack (タイミング攻撃) と呼ばれる攻撃によって機密情報である文字列を推測されてしまう可能性があるからです。

タイミング攻撃とは、機密情報となる文字列を左から見ていったときに、どこまで合っているかを、文字列比較の処理時間 (false が返ってくるまでの時間) を利用して、推測するという攻撃手法です。

この説明だけだといまいちわかりづらいと思いますので、もう少し詳しく説明します。

== による文字列の比較は、左から文字を見ていって、異なる文字が出てきた時点ですぐさま false を返します。

たとえば、"abcdef" と "abcefg" という文字列を比較する際、左の文字から比較していき、4 文字目で d と e という異なる文字が登場したので、5 文字目以降は見ずに false を返します。

abcdef
abcefg
   ^ ここで false を返す

この仕様は、処理の高速化のために採用されているものですが、これを攻撃に利用されてしまう可能性があるということです。

たとえば攻撃者が "xaeteuijft" というトークンを知りたかったとしましょう。まずは適当にありがちな文字列をサーバに投げて比較させます。

その際に、処理結果がすぐに返ってきた場合は、文字列の (左から見て) 早い段階で文字が間違っていることになります。

何回か繰り返しているうちに、左側の文字が合ってくると、処理結果が返ってくるまでにわずかに時間がかかるようになります。

処理結果が返ってくるのが若干遅くなれば合っている、速くなれば間違っている、というのを何度も繰り返すと、いずれ本当の文字列がバレてしまう可能性があるということです。短くて単純なものならなおさらです。

これがタイミング攻撃の攻撃手法になります。そして、この攻撃を防ぐための文字列比較のメソッドが Rack::Utils.secure_compare と呼ばれるものです。

Rack::Utils.secure_compare の実装を見てみる

では、Rack::Utils.secure_compare はいったいどんな実装になっているのでしょうか。さっそく見てみましょう。

    # Constant time string comparison.
    #
    # NOTE: the values compared should be of fixed length, such as strings
    # that have already been processed by HMAC. This should not be used
    # on variable length plaintext strings because it could leak length info
    # via timing attacks.
    if defined?(OpenSSL.fixed_length_secure_compare)
      def secure_compare(a, b)
        return false unless a.bytesize == b.bytesize

        OpenSSL.fixed_length_secure_compare(a, b)
      end
    else
      def secure_compare(a, b)
        return false unless a.bytesize == b.bytesize

        l = a.unpack("C*")

        r, i = 0, -1
        b.each_byte { |v| r |= v ^ l[i += 1] }
        r == 0
      end
    end

OpenSSL.fixed_length_secure_compare が定義されている場合はこれを使うようになっているのですが、今回は説明のわかりやすさの観点で、こちらではなく、Rack の実装のほうを見てみます。

def secure_compare(a, b)
  return false unless a.bytesize == b.bytesize

  l = a.unpack("C*")

  r, i = 0, -1
  b.each_byte { |v| r |= v ^ l[i += 1] }
  r == 0
end

引数 a に本当の文字列 (トークンなど)、引数 b に対象となる文字列 (クライアントからやってくる文字列など) が来るものとします。以後、a と b をそれぞれ「本当の文字列」、「対象となる文字列」と呼ぶことにします。

バイト長の比較

return false unless a.bytesize == b.bytesize

まず最初の段階で、そもそもバイト長が違っていたら false を返します。

本当の文字列を 8 bit 符号なし整数の配列に変換

l = a.unpack("C*")

本当の文字列をアンパックします。

アンパックというのは、簡単に言うと特定のルールに従って文字列を分解し、配列で返すメソッドです。今回は引数に "C*" が指定されているので、文字列中の各々の文字を 8 bit 符号なし整数に変換して、配列で返します。

"abcdef".unpack("C*")
=> [97, 98, 99, 100, 101, 102]

"a" が 97、"b" が 98、"c" が 99、、、とそれぞれ対応しています。

変数の初期化

r, i = 0, -1

r に 0、i に -1 が入ります。

文字列の比較

b.each_byte { |v| r |= v ^ l[i += 1] }

ここがメインの部分で、少しだけ複雑なので丁寧に解説します。

対象となる文字列を each_byte でループ処理します。たとえば b が "abcdef" だったら、v には 97、98、99、、、が順番に入ってきます。

その v と、先ほど本当の文字列を 8 bit 符号なし整数でアンパックした配列 l とを、最初のほうから順番に比較していきます。

ぼく自身も最初見たときに少し戸惑ったのですが、l[i += 1] というのは、先に i += 1 が実行されてから l の中身が参照されます。i は最初 -1 から始まるので、先に i が 0 になってから l[0] が評価されるので、配列を最初から見ているということです。

そして v ^ l[i += 1] の ^ は XOR (排他的論理和演算子) です。こういったライブラリではなく、アプリケーションでしか Ruby を書かない人にとっては、あまり馴染みがないかもしれません。

排他的論理和

排他的論理和は、2 つの数値を 2 進数で表記した際に、両者が異なる数字なら 1、同じ数字なら 0 を返す演算です。

01110101
00100010

上記の 2 つの 2 進数の排他的論理和を取ると、以下のようになります。

01010111

左の 1 文字目は両者とも 0 なので 0、2 文字目は片方が 1 で片方が 0 なので 1、3 文字目は両者とも 1 なので 0、、、といった感じです。

	1	2	3	4	5	6	7	8
1 つめの 2 進数	0	1	1	1	0	1	0	1
2 つめの 2 進数	0	0	1	0	0	0	1	0
排他的論理和	0	1	0	1	0	1	1	1

01110101 は 10 進数で表すなら 117、00100010 は 34、01010111 は 87 となります。つまり、10 進数表記の 117 と 34 の排他的論理和を取ると 87 になる、というわけです。

117 ^ 34
=> 87

---

さて、Rack の実装の話に戻ると、v ^ l[i += 1] なので、対象となる文字列と、本当の文字列の 8 bit 符号なし整数を左から順番に比較しているのでした。

ここで、両者が同じ文字 (数字) だったら、何が返ってくるでしょう。たとえば両者とも "a" だったら 97 を排他的論理和で比較することになります。

両方同じ数字だということは、当然すべての bit が同じなので、0 になります。

1100001
1100001

を比較すると、どの bit もすべて同じなので、

0000000

となります。

97 ^ 97
=> 0

つまり、同じ文字 (数字) なら 0 になり、そうじゃなければ 0 じゃない値になるということです。

そしてこの結果を r に代入していますが、ただの代入ではなく、論理和代入になっています。

r |= v ^ l[i += 1]

これは、以下と同様です。

r = r | v ^ l[i += 1]

つまり、r と、先ほどの文字 (数字) 比較を論理和演算した結果を r に代入しています。論理和演算は、どちらか片方が 1 なら 1 で、両者とも 0 なら 0 を返す演算です。

1 つめの bit	2 つめの bit	論理和
0	0	0
0	1	1
1	0	1
1	1	1

r は 0 で初期化されていたので、先ほどの文字 (数字) 比較の結果、すべての bit が 0 なら r もすべて 0 が入り、0 じゃない値がどこかの bit に入ったら、r もどこかの bit に 0 じゃない値が入ります。

ということは、本当の文字列と、対象となる文字列が完全に一致していれば、r はずっと 0 のままなので最終的にも 0 になり、逆にどこか一箇所でも違う文字になっていれば、つまり一致していなければ、r は 0 じゃない値になる、というわけです。

一度でも r に 0 じゃない bit が含まれてしまうと、その bit を再び 0 に戻すことは、論理和では無理です。なぜなら片方が 1 なら 1 になってしまうからです。つまり r は最初から最後までずっと 0 じゃないと、最終的にも 0 にはなりえないというわけです。

裏を返せば、b.each_byte で本当の文字列と対象となる文字列を一文字ずつ比較した結果、r が 0 のままであるなら両者の文字列は一致していることになります。

真偽値の返却

r == 0

最後に r が 0 かどうかを見ていて、0 (両者の文字列が一致している) ならこのメソッドは true を返し、0 じゃなければ (両者が一致していなければ) false を返すというわけです。

---

少し長い説明になりましたが、これで Rack::Utils.secure_compare がどのように文字列を比較しているかがわかりました。

Rack::Utils.secure_compare の安全性

文字列比較は == でもできるわけですから、肝心なのは、冒頭で説明したタイミング攻撃が防げるかどうかです。

== の場合は文字の比較の途中で違う文字が登場したらすぐさま false を返す仕様でしたが、Rack::Utils.secure_compare はどうでしょうか。

文字列の比較は以下の部分です。

b.each_byte { |v| r |= v ^ l[i += 1] }

処理の高速化という意味では、r が途中で 0 じゃなくなれば、文字列が一致していないことになるので、false を返すことができますが、それだと本末転倒です。途中で false を返したらタイミング攻撃が成立してしまう可能性があります。

しかし Rack::Utils.secure_compare は、文字列比較の途中で false を返すようなことはしていないので、途中で文字が違うことがわかっても最後まで比較し続けます。そのためループ内の処理時間は文字列が合っていようが間違っていようが変わらず、タイミング攻撃 (文字列そのものの推測に限る) は成立しないと言えます。

Rack::Utils.secure_compare の危険性

ただし注意点もあります。これは ソースコード内のコメント にも記載されていますが、タイミング攻撃で、本当の文字列の 長さ を推測されてしまう危険性はあります。

これが先ほど「文字列そのものの推測に限る」と書いた理由です。Rack::Utils.secure_compare はたしかに、タイミング攻撃による「文字列そのものの推測」は防ぐことができます。しかし、「文字列の長さの推測」までは防げない可能性があります。

理由はここにあります。

return false unless a.bytesize == b.bytesize

そもそも比較する 2 つの文字列のバイト長が異なっていたら文字列の比較をせずにすぐさま false を返しています。

もし本当の文字列が 10 文字だったとしたら、10 文字以外の長さの文字列を対象となる文字列として渡すと、すぐさま false が返ってくるので、順番に文字列の長さを変えて試していけば、そのうち文字列が長さがバレてしまいます。

つまりどういうことかというと、Rack::Utils.secure_compare は 可変長の平文文字列では安全ではない ということになります。

使用用途としては、HMAC のような、文字列長が常に一定になるアルゴリズムを使って、文字列をハッシュ化してから使うことになります。ハッシュ化せずそのままの文字列 (平文文字列) をこのメソッドに渡してしまうと長さが推測されてしまう可能性があります。

さいごに

今回は機密情報に関わる文字列を Ruby で安全に比較する方法として Rack::Utils.secure_compare をご紹介しました。

この記事では Ruby を例に挙げましたが、他の言語でも似たようなライブラリが提供されているかと思いますので、機密情報に関わる文字列を比較する際は一度調べてみることをおすすめします。

参考サイト

---

1. 一応、誤解のないように書いておくと、機密情報に関わらない文字列の比較に == を使用することは何も問題はありません。Ruby の == の実装に脆弱性があるというわけではないです。 ↩