Rack::Utils.secure_compare を読む
Hanami と Sinatra の CSRF 対策のコードで、いずれも Rack::Utils.secure_compare という API を利用していることを発見した。何が secure なのだろうか？ という思いがあり、読んでみた。
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
https://github.com/rack/rack/blob/master/lib/rack/utils.rb#L371-L385
一瞥して、短いコードであるが、なかなか見慣れない API が目白押しである。以下で順に見ていく。
String#unpack で文字列をバイト配列に変換する
l = a.unpack("C*")
文字列の入った変数 a を任意のフォーマットで解釈し、読み取った値を配列にして変数 l に格納している。フォーマットとして、ここでは "C*" を指定している。これは unsigned char つまり1バイト文字を指定している。
マルチバイト文字に対してこれが実行されるとどうなるか？ 答えは次のように先頭の1バイトだけを解釈することになる。要するに、'あ'と'い'が等価とみなされてしまうことになる。
'あ'.bytes # => [227, 129, 130] 'あ'.unpack('C') # => [227] 'い'.bytes # => [227, 129, 132] 'い'.unpack('C') # => [227]
とはいえ、secure_compareはドキュメントによると、 HMAC 等であらかじめ固定長に符号化した上で呼び出すように指示されているので、シングルバイト文字のみを考慮すれば十分なのだろう。
String#unpack と対になる API として、 Array#pack がある。いずれも芯を掴めていない感じがあるが、ここでは深入りせずにまた別の機会に検討する。
String#each_byte でバイト配列をイテレートする
r, i = 0, -1 b.each_byte { |v| r |= v ^ l[i += 1] }
each_byte は名前の通り、文字列を1バイトずつイテレートするメソッドである。ブロック内で、先ほど unpack した配列 l と1バイトごとに演算している。
マルチバイト文字に対して each_byte を呼び出すと、もちろん全バイトを解釈する。
'あ'.each_byte.to_a # => [227, 129, 130]
というわけで、やはりここではシングルバイト文字列しか受け取らないよう、はじめからデザインされているようである。そうでなければ、 each_byte と unpack('C*') の長さが変わってしまい、比較にならない。
ビット演算
# r, i = 0, -1 b.each_byte { |v| r |= v ^ l[i += 1] }
each_byte のブロック内では二種類のビット演算が記述されている。右辺からみていくことにしよう。
XOR
# i = -1 # v は任意の正の整数, l は任意の正の整数の配列 v ^ l[i += 1]
演算子 ^ は、競技プログラミングでもお馴染みの排他的論理和、XORである。ここでは二つの文字列の先頭から1バイトずつ比較し、排他的論理和を取っている。
排他的論理和、といちいち書くと仰々しいが、ここでは「演算対象の8-bitが等しければ 0 を返し、等しくなければ正の整数を返す」と単純に捉えてしまってもいい。
OR
# r, i = 0, -1 # v は任意の正の整数, l は任意の正の整数の配列 r |= v ^ l[i += 1]
XORの演算を右辺で行いつつ、式全体としては左辺の変数 r にフィードバックしている。その式を仲介している |= とはなにか？
正確な名称を調べてみると、複合代入演算子、と呼ぶらしい。これは ||= の形で見慣れているだろうから、それと同じイメージで構わない。つまり次のような対応関係となる。
a ||= b # a = a || b a |= b # a = a | b
| はビット演算子 OR である。詳しく復習することはしないが、ここで期待される便利な性質として、「増加こそすれ、減少することはない」ことがある。
XOR 演算の結果を OR 演算で累積している。XORの「二つの値が等しければ 0 を返し、等しくなければ正の整数を返す」という性質と、ORの「増加こそすれ、減少することはない」という性質から、その結果を累積していく変数 r の特性は、
- r == 0 のとき、比較対象は等しい
- 0 < r のとき、比較対象は等しくない
とシンプルに表される。
なにがどう secure なのか？
さて、もともとあった疑問に戻る。 secure_compare と名付けられた根拠はなんだろう？ 言い換えると、あえて String#== ではなく、 secure_compare を使う動機はなんだろう？
GitHub Developer にてヒントが示されていた。
Using a plain == operator is not advised. A method like secure_compare performs a "constant time" string comparison, which renders it safe from certain timing attacks against regular equality operators._1
"constant time" string comparison とある。普通 constant time というと、実行時間が O(1) であることを意味すると思うが、上で見たコードからして、実行時間は文字列の長さに比例して O(N) であるはず。いったいどういう含意なのか？
で、こんな投稿を見つけた。
要するに、 secure_compare は「常に文字列を末尾まで舐める」という意味で "constant time" だという。文字列を単純に比較するだけでは、文字列の途中で一致しない文字があることを見つけ次第 false を返すため、入力次第で実行時間が変わってしまう。
入力次第で実行時間が変わってしまうというのはまずい。攻撃者が実行時間を計測し、正しい値を推測できるようになってしまう。このことをタイミング攻撃と呼ぶらしい。実際、 Rack::Utils.secure_compare のコメントにも、「必ず固定長の文字列を比較し、タイミング攻撃を防ぐこと」とある。
固定長の文字列が入力されるという前提に立てば、なるほど実行時間は一定となるはずである。つまり、トークンなどの秘匿したい情報を、検証に要する実行時間から推測できない、という意味で secure_compare は「安全」であるということになる。
おわりに
上にて結論づけたため、蛇足にはなるが、アルゴリズムとしてもすっきりしていて学びになるコードであった。XOR と OR 演算の特性をうまく利用して、シンプルな整数計算で結果を導けるのは清々しい。
また二つの配列の要素を比べるにしても、要素数が等しいことを利用して、シンプルなイテレートでそれを実現できていて気持ちがいい。僕であればあるいは Array#zip で二次元配列をいったん作ってからイテレートする、というような不器用なやり方をしかねない。
こういうエレガントな着想が湧くのが羨ましい。嫉みではなく、もっと知識と経験を身につけようと奮い立たせられた。
