タイミング攻撃の仕組み

概要

タイミング攻撃を調べていたところ、こんなサイトがあったので意訳っぽくまとめ。

原理

簡単に言えばアプリケーションがなにかをするときにかかる時間の差異を分析することによる攻撃。
今回登場するHMACに限って言えば、トークン認証で値を比べるときの時間を分析して情報を得ようとする。

例えば

'ber' == 'bar'
'foo' == 'bar'

という２つの処理は上の方が１文字目を共有している分、2文字目まで比較がされより時間がかかる。

攻撃手法

あるユーザーIDに対してのsession cookieを探りたいとする。
このとき新のcookieの先頭２文字はA1だとしよう。
まず

0000000000000000000000000000000000000000
0100000000000000000000000000000000000000
0200000000000000000000000000000000000000
... snip 250 ...
FD00000000000000000000000000000000000000
FE00000000000000000000000000000000000000
FF00000000000000000000000000000000000000

という256個の値に対してアクセスをかける。
するとA100000000000000000000000000000000000000のときのみ数ミリ秒だけ比較の時間が長くなる。
よって攻撃主はcookieの先頭2文字がA1じゃないかという推測が可能になる。
これを残りの桁に対しても順次適用すれば情報の抜き取りが完成する。

現実性

Opportunities And Limits Of Remote Timing Attacksの内容を踏まえると、1バイトを特定するにはおよそ数百~数千回の測定で十分らしい。
もしHMACのハッシュの長さが20のときには攻撃に必要なリクエスト回数は
ハッシュ長×256パターン×byte当たり必要リクエスト数
すなわち
20×256×数百~数千≒5000000リクエスト
で攻撃が完了する。
これは秒当り10リクエストで１週間かからずに達成できる。

対処法

値の比較に可変時間アルゴリズムでなく定数時間アルゴリズムを使う。

Python

def is_equal(a, b):
    if len(a) != len(b):
        return False

    result = 0
    for x, y in zip(a, b):
        result |= x ^ y
    return result == 0

Java

public static boolean isEqual(byte[] a, byte[] b) {
    if (a.length != b.length) {
        return false;
    }

    int result = 0;
    for (int i = 0; i < a.length; i++) {
      result |= a[i] ^ b[i];
    }
    return result == 0;
}

感想

今はタイミング攻撃はフレームワークなどが勝手に対処してくれてるそうだが、原理を知るのは楽しい。