Timeless Timing Attacks を紹介してみる
はじめに
ある技術記事を読んでいたところ、「センシティブなデータの比較には定数時間比較を用いると良い」という旨の記述がありました。
自分はそこで初めてタイミング攻撃について知ったのですが、あまり現実的ではないように感じました。
というのも比較処理時間の差異程度の小さな誤差をネットワーク越しに検出できるとは思えなかったためです。
懐疑的になりつつタイミング攻撃に関して調べていくうちにTimeless Timing Attacksという新しめの攻撃手法があることを知り、その核心部分のアイデアがおもしろいと感じたため、ざっくり概要や対策を共有できればと思い本記事を投稿しました。
では始めます。
タイミング攻撃
まずは従来のタイミング攻撃について説明し、その限界を確認します。
タイミング攻撃の概要
タイミング攻撃はサイドチャネル攻撃の一種に分類され、入力によって処理時間が異なることを利用して情報を得ようと試みる攻撃手法です。
一例として、パスワードやトークンなどの秘密文字列との比較処理に対して攻撃するケースを考えます。
デフォルトの文字列比較(==)を用いた処理を、内部実装を想像してシンプルに書くと以下のような感じになると思います。
SECRET_TOKEN = "71m31355_5h0071N6_574r"
def check(input):
if len(input) != len(SECRET_TOKEN):
return False
for i in range(len(input)):
if input[i] != SECRET_TOKEN[i]:
return False
return True
文字列の長さが一致しているかどうか、さらにどの程度一致しているかに依存してcheck関数の処理時間が変動してしまうため、様々な入力に対する処理時間を計測・比較することで秘密文字列に関する情報を得ることができてしまいます。
タイミング攻撃の限界
理論上は良さそうですが、より現実的な状況としてWebアプリケーションに対するタイミング攻撃のシーケンスを考えます。
サーバー側の処理の一部として、前述のcheck関数のように リクエストに含まれる文字列と秘密文字列とを比較するような処理 を想定し、これを検証と呼ぶことにします。
ネットワークを介したやりとりではサーバー側の処理時間や伝送時間自体が様々な要因でブレるため、（例え同一内容のリクエストであっても）レスポンスが返るまでの時間に誤差が生じます。この誤差をまとめてジッターと呼びます。
このようにジッターの影響でサーバー側の処理時間の差を検出するのは難しく、
タイミング攻撃は（一般的なネットワーク越しのやり取りでは）あまり実践的ではないようです[1][2]。
Timeless Timing Attacks
ここから"Timeless Timing Attacks: Exploiting Concurrency to Leak Secrets over Remote Connections" (USENIX Security 2020) の論文で紹介されている手法の説明と、従来のタイミング攻撃と比較した際の優位性を見ていきます。（以下論文という単語が出てきた際はこの論文を指します。）
本記事では攻撃者が直接Webサーバーにアクセスするケースを元に説明していきますが、論文では他にもTorやWi-Fi認証に対する攻撃も紹介されています。根底にある原理は共通です。
Timeless Timing Attacks の概要
先ほどと同様のWebサーバーに攻撃を仕掛けるケースを考えますが、前提条件として以下の二つを仮定します。
- HTTP/2でリクエストする
- サーバー側はリクエストを並列に処理する
Timeless Timing Attacks ではHTTP/2 のリクエストの多重化を利用し、二つのリクエストを単一のパケットに載せてほぼ同時にサーバー側に届けます。
これによって、サーバーへの送信時のジッターは共通となるので無視でき、二つ目の仮定から各リクエストの処理はほぼ同時に開始されます[3]。そしてHTTP/2 ではレスポンスはサーバー側の処理が完了次第送信されます。
サーバー側の処理が前述のcheck関数の場合のシーケンスを以下に示します。
図のように最初のリクエストに対するレスポンスの方が遅れた場合、より検証に時間がかかった＝より秘密文字列に近い入力だったと推測できます。
このように絶対的な時間差ではなく、レスポンスの順序を利用して情報を得ていることから Timeless と付いているようです[4][5]。（自分が感銘を受けたのはこのアイデアの部分です）
Timeless Timing Attacks の優位性
95%の精度で攻撃を成功させるのに必要なリクエスト数を以下に示します。
（論文中のTable1より簡略化して抜粋）
| 攻撃手法/時間差 | 100ns | 1μs | 10μs |
|---|---|---|---|
| Timeless (Internet) | ~40,000 | ~500 | 11 |
| 従来 (Europe -> Europe) | - | - | ~25,000 |
| 従来 (localhost) | - | ~900 | 20 |
（※攻撃失敗、あるいは100,000以上の場合は-）
特筆すべき点として、以下の2点が挙げられます。
- インターネット上の攻撃においては従来手法における100分の1程度の時間差を検出して攻撃可能
- ローカルにおける従来手法と同レベルの精度をインターネット上で実現できる
このように、Timeless Timing Attacksは現実的なリクエスト数で攻撃が成功しうる脅威があります。
対策
現実味を帯びてきているタイミング攻撃についての対策を確認し、各言語やフレームワークでどのように実装すれば良いかを簡単に紹介します。
定数時間比較の重要性
論文ではタイミング攻撃に対する最も効果的な対策は、定数時間実行を保証することであると述べられています。
タイミング攻撃の本質は様々な入力に対して処理時間を計測・比較することで情報を得ることなので、これらの処理時間を均一に揃えることで攻撃者が得られる情報量を抑えることができます。
本記事で想定した秘密文字列との比較においては、定数時間比較(constant-time comparison)でこれを実現できます。
なので、冒頭で触れた技術記事の主張は妥当であるということになります。
各言語やフレームワークでの定数時間比較実装
Python: hmac.compare_digest
Pythonではhmac.compare_digestを用いると良さそうです。使用例を以下に示します。（wandbox）
import hmac
SECRET_TOKEN = b"71m31355_5h0071N6_574r"
# OK: 定数時間比較
def check(input):
return hmac.compare_digest(input, SECRET_TOKEN)
# NG: 通常の比較
# def check(input):
# return input == SECRET_TOKEN
x1 = b"aaaa"
x2 = SECRET_TOKEN
assert not check(x1)
assert check(x2)
Rust: subtle crate
Rustではsubtleクレート（ライブラリに相当）にて定数時間比較の機能が提供されています[6]。
使用例を以下に示します。(rust-playground)
use subtle::{Choice, ConstantTimeEq};
const SECRET_TOKEN: &[u8] = b"71m31355_5h0071N6_574r";
fn main() {
let x1 = b"a";
let x2 = SECRET_TOKEN;
assert_eq!(check(x1).unwrap_u8(), 0);
assert_eq!(check(x2).unwrap_u8(), 1);
}
fn check(input: &[u8]) -> Choice {
input.ct_eq(SECRET_TOKEN)
}
Antikythera (Elixir): Crypto.secure_compare
Antikytheraは株式会社ACCESSが開発しているElixir製のWebフレームワークであり、Cryptoモジュールにsecure_compare/2関数が定義されています。(hexdocs)
使用例は省略します。
secure_compareの実装詳細
折角なので簡単に内部実装を解説します。実装の本質部分は以下のようになっています。
defp secure_compare_impl(<<x, left::binary>>, <<y, right::binary>>, acc) do
import Bitwise
secure_compare_impl(left, right, bor(acc, bxor(x, y)))
end
defp secure_compare_impl(<<>>, <<>>, acc) do
acc
end
比較対象である2つのbyte列に対してbyte毎にxor（排他的論理和）を取り、それを累積or（論理和）でまとめて返り値としています。
返り値が0であれば入力は一致しており、非0であれば異なるということになります。
上記の処理対象をbit列に置き換えた具体例で確認します。（本質的にはbyte列と同じです）
-
a != bのケース
-----▽-- 右から2bit目が異なってます
a: 0110
b: 0100
a xor b: 0010
a xor b に対する累積or -> 1
bitが一箇所でも異なるとそのbitに関する排他的論理和が1になってしまうので、累積orを取った結果は非0になります。
-
a == cのケース
a: 0110
c: 0110
a xor c: 0000
a xor c に対する累積or -> 0
bit列として一致している場合は、全てのbitに対して排他的論理和が0なので、累積orを取っても0になります。また論理和の性質上、0になるのは全てのbitが一致している場合に限ります。
いずれのケースでも早期リターンはせずに全てのbitに対して計算した結果を累積orを取って返すので、処理時間が一定（bit列の長さにのみ依存）になることが期待されます。
一応Elixir(正確にはErlang)自体にも:crypto.hash_equals/2という定数時間比較のための関数が用意されています。
まとめ
本記事では、定数時間比較を推奨する記事を読んで湧いた「タイミング攻撃は現実的なのか？」という疑問に対して、新しめの手法であるTimeless Timing Attacksを提示し、その脅威と定数時間比較の重要性を確認してきました。
遭遇頻度は低いかもしれませんが、定数時間比較の概念を頭の片隅に置いておいて適切な実装を施すことで、潜在的な攻撃からアプリケーションを守れるでしょう。
内容に関して誤りや不明な点があれば、コメントなどにて指摘いただければと思います。
最後までお読みいただきありがとうございました。
参考文献
- Tom Van Goethem, Christina Pöpper, Wouter Joosen, Mathy Vanhoef. "Timeless Timing Attacks: Exploiting Concurrency to Leak Secrets over Remote Connections". 29th USENIX Security Symposium, 2020.
-
より正確にはタイミング攻撃はリクエストと測定を繰り返して統計的に処理して判断するのですが、意味のある結果を得るのに必要なリクエストの数が数万かそれ以上のオーダーになってしまうという意味で現実的ではないようです。 ↩︎
-
シーケンス図に現れる時間のオーダーは論文中の数値に合わせています。 ↩︎
-
正確にはTLSレコードの復号が逐次的なので最初のリクエストが若干早くなってしまうのですが、これを調整するためにHTTPリクエストにURLパラメータを40個ほど追加しているようです。 ↩︎
-
サーバーからのレスポンスのジッターは考慮しなくて良いのかと思われた方もいるかもしれませんが、レスポンスの受信順ではなく、レスポンスに含まれるTCPのシーケンス番号を確認することで、ジッターの影響を無視できます。 ↩︎
-
実践では時間差も含めて考慮する方が精度が上がると論文で言及されています。 ↩︎
-
subtleクレートはGoの
crypto/subtleモジュール相当の機能を実現しようとしているようです（aboutより）。 ↩︎
Discussion