March 9, 2018

機密情報の比較処理、secure_compareの実装について

ActiveSupport::SecurityUtils.secure_compareRack::Util.secure_compareについてメモ。

文字列が等価であるかどうか確認するのにa == bという風に書くことが多い。
しかし、機密情報の比較にこの形式を用いると、処理に要する時間からアルゴリズムが特定されたり、機密情報自体が漏れる可能性がある(所謂、Timing Attack)。

例えば、クーポンや一時トークンの確認などではTiming Attackに気をつける必要がある。
通常の文字列比較の場合、1byte目から確認していき、文字列が異なる時点でFalseを返す実装が多いと思う。

'secret' == 'hoge'
# F
'secret' == 'soge'
# TF
'secret' == 'sege'
# TTF
...
'secret' == 'secret'
# TTTTT

早々にレスポンスが返ってくれば異なることが分かるし、少し返ってくるのが遅ければ、ある段階までは合っていることが分かる。
これを何度も繰り返せば、1byte目から順々に正解の文字列が分かる。これがTiming Arrackで、知っている人は多いと思う。

しかし、クーポンコードや一時トークンの比較などでは == が取られていることも多いのでは…という気がする。
では、どのように実装すればいいのか。
そこでRack::Util.secure_compareではどのように実装されているか見てみる。

https://github.com/rack/rack/blob/master/lib/rack/utils.rb#L373

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

まず、Timming Attackを防ぐには以下の処理を行う必要がある。

  1. 文字列の長さを比較し、異なればさっさとFalseを返す
  2. 全ての文字列を比較する
return false unless a.bytesize == b.bytesize

ここでバイトサイズが違えばさっさとFalseを返すようにしている。

次に l = a.unpack("C*") でByteのArrayを作成。

a = "hfurg3r78qt72bd3bfg2yf89"
l = a.unpack("C*")
[104, 102, 117, 114, 103, 51, 114, 55, 56, 113, 116, 55, 50, 98, 100, 51, 98, 102, 103, 50, 121, 102, 56, 57]

そして以下でXORによる比較を行っていく。

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

XORなので等しければ0が返る。自明。

res = 104 ^ 104
# 0
res = 104 ^ 114
# 26

以上のように実装されている。

他の言語ではどう実装するのかについては https://security.stackexchange.com/questions/83660/simple-string-comparisons-not-secure-against-timing-attacks/83671#83671 にいくつか載っている。

そして、具体的には以下のようなところでTiming Attack対策を行わなければいけない。

  • クーポンコードの比較
  • ログイン時でのパスワードハッシュの比較
  • パスワードリマインダで発行する一時トークン
  • CSRFトークン
  • APIキー
このエントリーをはてなブックマークに追加

© Kouhei Morita 2018