constant-time-testing について
constant-time-testingは、秘密情報を扱う暗号コードのタイミング漏えいを評価するセキュリティスキルです。統計的・動的・シンボリック・形式的な分析手法とテスト手順を解説します。
主な機能
- 01よくあるタイミング漏えいの解説
- 024種類の分析手法の紹介
- 03dudectによる統計テスト
- 04Timecopによる実行時トレース
- 05検証とCI手順の概要
活用シーン
- 01秘密情報を扱う暗号コードの監査
- 02テストで見つかった時間差の調査
- 03暗号コード変更のレビュー
- 04CIへの漏えい検査の追加
インストール
コマンドをコピーしてターミナルで実行します。
npx skills add https:/インストール後、Claude Code で/constant-time-testingを入力して読み込まれたか確認します。
同梱ファイルagents/openai.yamlassets/trail-of-bits-mark.svg
詳細
定数時間テスト
タイミング攻撃は、実行時間のばらつきを悪用し、暗号実装から秘密情報を抽出します。理論上の弱点を狙う暗号解読とは異なり、タイミング攻撃は実装上の欠陥を利用するため、あらゆる暗号コードに影響を及ぼす可能性があります。
背景
タイミング攻撃は1996年にKocherによって紹介されました。それ以来、研究者たちはRSA（Schindler）、OpenSSL（Brumley and Boneh）、AESの実装、さらにはKyberのような耐量子アルゴリズムに対する実用的な攻撃を実証しています。
主な概念
| 概念 | 説明 |
|---|---|
| 定数時間 | コードパスとメモリアクセスが秘密データに依存しないこと |
| タイミング漏えい | 秘密情報と相関する、観測可能な実行時間の差 |
| サイドチャネル | アルゴリズムではなく実装から抽出される情報 |
| マイクロアーキテクチャ | CPU レベルのタイミング差（キャッシュ、除算、シフト） |
重要な理由
タイミング脆弱性は、次のような事態を引き起こす可能性があります。
- 秘密鍵の漏えい - RSA/ECDH の秘密指数を抽出します
- リモート攻撃の実行 - ネットワーク経由で観測可能なタイミング差を悪用します
- 暗号の安全性の回避 - 理論上の保証を損ないます
- 気づかれないまま残存 - 専門的な分析を行わないと、検出されないことがよくあります
悪用には、次の2つの前提条件が必要です。
- オラクルへのアクセス - 脆弱な実装に対する十分な回数のクエリ
- タイミング依存性 - 実行時間と秘密データの相関
よくある定数時間違反のパターン
タイミング脆弱性の大半は、次の4つのパターンに起因します。
// 1. Conditional jumps - most severe timing differences
if(secret == 1) { ... }
while(secret > 0) { ... }
// 2. Array access - cache-timing attacks
lookup_table[secret];
// 3. Integer division (processor dependent)
data = secret / m;
// 4. Shift operation (processor dependent)
data = a << secret;
条件分岐ジャンプは異なるコードパスを生み、実行時間に大きな差をもたらします。
秘密情報に依存する配列アクセスは、AES のキャッシュタイミング研究で示されているように、キャッシュタイミング攻撃を可能にします。
整数除算やシフト演算は、特定の CPU アーキテクチャやコンパイラー設定で秘密情報を漏らします。
これらのパターンを避けられない場合は、マスキング手法を用いて、タイミングと秘密情報の相関を取り除いてください。
例：モジュラー累乗のタイミング攻撃
（RSA や Diffie-Hellman で使われる）モジュラー累乗は、タイミング攻撃の影響を受けやすい処理です。RSA の復号では、次の計算を行います。
$$ct^{d} \mod{N}$$
ここで $d$ は秘密指数です。繰り返し二乗法による最適化では、乗算回数を $\log{d}$ に減らします。
$$ \begin{align*} & \textbf{Input: } \text{base }y,\text{exponent } d={d_n,\cdots,d_0}_2,\text{modulus } N \ & r = 1 \ & \textbf{for } i=|n| \text{ downto } 0: \ & \quad\textbf{if } d_i == 1: \ & \quad\quad r = r * y \mod{N} \ & \quad y = y * y \mod{N} \ & \textbf{return }r \end{align*} $$
コードは指数のビット $d_i$ によって分岐しており、定数時間の原則に違反しています。$d_i = 1$ の場合は乗算が1回追加され、実行時間が長くなるため、ビット情報が漏えいします。
（モジュラー演算で一般的に使われる）モンゴメリ乗算もタイミング情報を漏らします。中間値が法 $N$ を超えると、追加の剰余計算が必要になるためです。攻撃者は次の条件を満たす入力 $y$ と $y'$ を構成します。
$$ \begin{align*} y^2 < y^3 < N \ y'^2 < N \leq y'^3 \end{align*} $$
$y$ の場合、どちらの乗算も時間 $t_1+t_1$ で完了します。$y'$ の場合、2回目の乗算で剰余計算が必要になり、時間は $t_1+t_2$ かかります。このタイミング差から、$d_i$ が0か1かが明らかになります。
使用する場面
定数時間解析を適用する場面：
- 暗号実装（プリミティブ、プロトコル）を監査するとき
- コードが秘密鍵、パスワード、または機密性の高い暗号素材を扱うとき
- 暗号アルゴリズムを一から実装するとき
- 暗号コードに関わる PR をレビューするとき
- タイミング脆弱性の可能性を調査するとき
代替手段を検討する場面：
- コードが秘密データを処理しないとき
- 秘密の入力がない公開アルゴリズムの場合
- 暗号以外のタイミング要件（パフォーマンス最適化）の場合
クイックリファレンス
| シナリオ | 推奨されるアプローチ | スキル |
|---|---|---|
| 漏えいがないことを証明する | 形式検証 | SideTrail、ct-verif、FaCT |
| 統計的なタイミング差を検出する | 統計的テスト | dudect |
| 実行時に秘密データのフローを追跡する | 動的解析 | timecop |
| キャッシュタイミング脆弱性を見つける | シンボリック実行 | Binsec、pitchfork |
定数時間解析ツールのカテゴリー
暗号コミュニティでは、タイミング解析ツールが4つのカテゴリーに発展しています。
| カテゴリー | アプローチ | 長所 | 短所 |
|---|---|---|---|
| 形式検証 | モデルに対する数学的証明 | 漏えいがないことを保証 | 複雑さ、モデル化に関する前提 |
| シンボリック | 実行経路のシンボリック実行 | 具体的な反例 | 経路の探索に時間がかかる |
| 動的 | 秘密としてマークしたデータの実行時トレース | きめ細かく柔軟 | 実行された経路に対象が限定される |
| 統計 | 実際の実行時間を測定 | 実用的で、簡単に設定可能 | 根本原因が分からない、ノイズの影響を受けやすい |
1. 形式検証ツール
形式検証では、コードの抽象化（モデル）におけるタイミング特性を数学的に証明します。ツールはソースコードまたはバイナリからモデルを作成し、指定された特性（例：秘密として注釈された変数）を満たすことを検証します。
主なツール：
長所： 漏えいがないことを証明できる、言語に依存しない（LLVM バイトコード） 短所： 専門知識が必要で、モデル化に関する前提によって実環境の問題を見落とす可能性がある
2. シンボリック解析ツール
シンボリック実行では、経路やメモリアクセスがシンボリック変数（秘密）にどのように依存するかを解析し、具体的な反例を示します。キャッシュタイミング攻撃に焦点を当てています。
主なツール：
長所： 具体的な反例がデバッグに役立つ 短所： 経路爆発によって実行時間が長くなる
3. 動的解析ツール
動的解析では、機密性の高いメモリ領域に印を付け、実行を追跡してタイミングに依存する操作を検出します。
主なツール：
長所： きめ細かな制御、対象を絞った解析 短所： 実行された経路に対象が限定される
詳細なガイダンス： 設定方法と使い方については、timecop スキルを参照してください。
4. 統計的解析ツール
さまざまな入力でコードを実行し、経過時間を測定して不整合を検出します。コンパイラーの最適化やアーキテクチャを含め、実際の実装をテストします。
主なツール：
- dudect（以下を参照）
- tlsfuzzer
長所： 設定が簡単で、実環境で実用的な結果が得られる 短所： 根本原因に関する情報がなく、ノイズによって弱いシグナルが見えにくくなる
詳細なガイダンス： 設定方法と使い方については、dudect スキルを参照してください。
テストのワークフロー
Phase 1: Static Analysis Phase 2: Statistical Testing
┌─────────────────┐ ┌─────────────────┐
│ Identify secret │ → │ Detect timing │
│ data flow │ │ differences │
│ Tool: ct-verif │ │ Tool: dudect │
└─────────────────┘ └─────────────────┘
↓ ↓
Phase 4: Root Cause Phase 3: Dynamic Tracing
┌─────────────────┐ ┌─────────────────┐
│ Pinpoint leak │ ← │ Track secret │
│ location │ │ propagation │
│ Tool: Timecop │ │ Tool: Timecop │
└─────────────────┘ └─────────────────┘
推奨されるアプローチ：
- dudect から始める - タイミング差をすばやく統計的に確認する
- 漏えいが見つかった場合 - Timecop を使って根本原因を特定する
- 高い保証が必要な場合 - 形式検証（ct-verif、SideTrail）を適用する
- 継続的な監視 - dudect を CI パイプラインに統合する
ツールとアプローチ
Dudect - 統計解析
Dudect は、2 種類の入力クラス（固定値とランダム値）の実行時間を測定し、Welch の t 検定を使って統計的に有意な差を検出します。
詳細ガイド： セットアップ、使用パターン、CI への統合については、dudect スキルをご覧ください。
定時間解析のクイックスタート
#define DUDECT_IMPLEMENTATION
#include "dudect.h"
uint8_t do_one_computation(uint8_t *data) {
// Code to measure goes here
}
void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
for (size_t i = 0; i < c->number_measurements; i++) {
classes[i] = randombit();
uint8_t *input = input_data + (size_t)i * c->chunk_size;
if (classes[i] == 0) {
// Fixed input class
} else {
// Random input class
}
}
}
主な利点：
- 簡単に統合できる、C のヘッダーのみの実装
- Welch の t 検定による統計的な厳密性
- コンパイル済みバイナリで動作（実環境に即した条件）
主な制約：
- 漏えいを検出しても根本原因はわからない
- 測定ノイズの影響を受けやすい
- 漏えいがないことは保証できない（統計的な信頼度のみ）
Timecop - 動的トレース
Timecop は Valgrind をラップし、実行時にシークレットのメモリー領域に依存する処理を検出します。
詳細ガイド： インストール、例、デバッグについては、timecop スキルをご覧ください。
定時間解析のクイックスタート
#include "valgrind/memcheck.h"
#define poison(addr, len) VALGRIND_MAKE_MEM_UNDEFINED(addr, len)
#define unpoison(addr, len) VALGRIND_MAKE_MEM_DEFINED(addr, len)
int main() {
unsigned long long secret_key = 0x12345678;
// Mark secret as poisoned
poison(&secret_key, sizeof(secret_key));
// Any branching or memory access dependent on secret_key
// will be reported by Valgrind
crypto_operation(secret_key);
unpoison(&secret_key, sizeof(secret_key));
}
Valgrind で実行します：
valgrind --leak-check=full --track-origins=yes ./binary
主な利点：
- タイミング漏えいが発生する正確な行を特定
- コードへの計測処理の追加が不要
- 実行中のシークレットの伝播を追跡
主な制約：
- マイクロアーキテクチャによるタイミング差は検出できない
- 実行したパスのみが対象
- 性能のオーバーヘッドがある（合成 CPU 上で実行）
実装ガイド
フェーズ 1：初期評価
シークレットを扱う暗号コードを特定します：
- 秘密鍵、指数、ノンス
- パスワードハッシュ、認証トークン
- 暗号化／復号処理
簡易統計チェック：
- 暗号関数用の dudect ハーネスを作成します
timeout 600 ./ct_testを使って 5～10 分実行します- t 値を監視します。絶対値が大きい場合は漏えいを示しています
ツール： dudect 想定時間： 1～2 時間（ハーネスの作成と初回実行）
フェーズ 2：詳細解析
dudect が漏えいを検出した場合：
根本原因を調査します：
- Timecop の
poison()でシークレット変数にマークを付けます - Valgrind の下で実行し、該当する行を特定します
- 代表的な 4 つの違反パターンを確認します
- 条件分岐がないか、アセンブリ出力を確認します
ツール： Timecop、コンパイラー出力（objdump -d）
フェーズ 3：修正
タイミング漏えいを修正します：
- 条件分岐を定時間選択（ビット演算）に置き換えます
- 定時間比較関数を使用します
- 配列参照を定時間の代替手段またはマスキングに置き換えます
- コンパイラーが定時間コードを最適化で取り除かないことを確認します
再検証：
- dudect を再度、長時間（30 分以上）実行します
- 異なるコンパイラーと最適化レベルでテストします
- 異なる CPU アーキテクチャでテストします
フェーズ 4：継続的な監視
CI に統合します：
- テストスイートに dudect テストを追加します
- 一定時間（CI では 5～10 分）実行します
- 漏えいが検出された場合はビルドを失敗させます
CI への統合例については、dudect スキルをご覧ください。
よくある脆弱性
| 脆弱性 | 説明 | 検出方法 | 深刻度 |
|---|---|---|---|
| シークレット依存の分岐 | if (secret_bit) { ... } | dudect、Timecop | CRITICAL |
| シークレット依存の配列アクセス | table[secret_index] | Timecop、Binsec | HIGH |
| 可変時間の除算 | result = x / secret | Timecop | MEDIUM |
| 可変時間のシフト | result = x << secret | Timecop | MEDIUM |
| モンゴメリ還元の漏えい | 中間値が N を超える場合に追加の還元が発生 | dudect | HIGH |
シークレット依存の分岐：詳細
脆弱性： 分岐が実行されるかどうかによって、実行時間が異なります。最適化されたモジュラー指数演算（Square-and-Multiply 方式）でよく見られます。
dudect での検出方法：
uint8_t do_one_computation(uint8_t *data) {
uint64_t base = ((uint64_t*)data)[0];
uint64_t exponent = ((uint64_t*)data)[1]; // Secret!
return mod_exp(base, exponent, MODULUS);
}
void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
for (size_t i = 0; i < c->number_measurements; i++) {
classes[i] = randombit();
uint64_t *input = (uint64_t*)(input_data + i * c->chunk_size);
input[0] = rand(); // Random base
input[1] = (classes[i] == 0) ? FIXED_EXPONENT : rand(); // Fixed vs random
}
}
Timecop での検出方法：
poison(&exponent, sizeof(exponent));
result = mod_exp(base, exponent, modulus);
unpoison(&exponent, sizeof(exponent));
Valgrind は次のように報告します：
Conditional jump or move depends on uninitialised value(s)
at 0x40115D: mod_exp (example.c:14)
関連スキル： dudect、timecop
ケーススタディ
ケーススタディ：OpenSSL RSA タイミング攻撃
Brumley と Boneh（2005）は、ネットワーク経由で OpenSSL から RSA 秘密鍵を抽出しました。この脆弱性は、Montgomery 乗算における処理時間が一定でない剰余演算のステップを悪用していました。
攻撃ベクトル： 冪乗剰余演算におけるタイミング差 検出方法： 統計分析（dudect の先駆け） 影響： リモートからの鍵抽出
使用ツール： カスタムのタイミング測定 適用した手法： 統計分析、選択暗号文クエリ
ケーススタディ：KyberSlash
耐量子アルゴリズムである Kyber のリファレンス実装には、多項式演算にタイミング脆弱性が含まれていました。除算演算によって秘密係数が漏えいしていました。
攻撃ベクトル： 秘密データに依存する除算の処理時間 検出方法： 動的分析と統計的検査 影響： 耐量子暗号における秘密鍵の復元
使用ツール： タイミング測定ツール 適用した手法： 差分タイミング分析
高度な使い方
ヒントとコツ
| ヒント | 効果 |
|---|---|
dudect を分離した CPU コアに固定します（taskset -c 2） | OS のノイズを減らし、信号の検出精度を高めます |
| 複数のコンパイラー（gcc、clang、MSVC）でテストします | 最適化によって漏えいが発生したり、解消されたりする場合があります |
| dudect を長時間（数時間）実行します | 統計的な信頼性を高めます |
| ハーネス内の暗号処理以外のコードを最小限にします | 微弱な信号を覆い隠すノイズを減らします |
アセンブリー出力（objdump -d）を確認します | コンパイラーが分岐を導入していないことを確認できます |
テストでは -O3 -march=native を使用します | 本番環境の最適化レベルに合わせられます |
よくある間違い
| 間違い | 問題点 | 正しい方法 |
|---|---|---|
| 1 種類の入力分布だけをテストする | ほかのパターンで現れる漏えいを見逃す可能性があります | 固定値対ランダム値、異なる固定値同士などをテストします |
| dudect の実行時間が短い（1 分未満） | 微弱な信号を検出するには測定が不十分です | 5～10 分以上実行し、高い信頼性が必要な場合はさらに長く実行します |
| コンパイラーの最適化レベルを無視する | -O0 では -O3 で発生する漏えいが隠れる場合があります | 本番環境の最適化レベルでテストします |
| 対象アーキテクチャでテストしない | x86 と ARM ではタイミング特性が異なります | デプロイ先のプラットフォームでテストします |
| Timecop で秘密としてマークする範囲が広すぎる | 偽陽性が発生し、結果が分かりにくくなります | 真の秘密（公開データではなく鍵）のみをマークします |
関連スキル
ツールスキル
| スキル | 定時間分析での主な用途 |
|---|---|
| dudect | Welch の t 検定によるタイミング差の統計的検出 |
| timecop | タイミング漏えいの正確な箇所を特定する動的トレース |
手法スキル
| スキル | 適用する場面 |
|---|---|
| coverage-analysis | テスト入力が暗号関数のすべてのコードパスを実行するようにします |
| ci-integration | 継続的インテグレーションのパイプラインで定時間テストを自動化します |
関連ドメインスキル
| スキル | 関連性 |
|---|---|
| crypto-testing | 定時間分析は暗号テストに不可欠な要素です |
| fuzzing | 暗号コードのファジングによって、タイミングに依存するパスが実行される場合があります |
スキル依存関係マップ
┌─────────────────────────┐
│ constant-time-analysis │
│ (this skill) │
└───────────┬─────────────┘
│
┌───────────────┴───────────────┐
│ │
▼ ▼
┌───────────────────┐ ┌───────────────────┐
│ dudect │ │ timecop │
│ (statistical) │ │ (dynamic) │
└────────┬──────────┘ └────────┬──────────┘
│ │
└───────────────┬───────────────┘
│
▼
┌──────────────────────────────┐
│ Supporting Techniques │
│ coverage, CI integration │
└──────────────────────────────┘
リソース
主要な外部リソース
これらの結果は誤りでなければならない：定時間解析ツールのユーザビリティ評価 定時間解析ツールの包括的なユーザビリティ調査です。主な調査結果として、開発者は誤検知に苦労しており、より良いエラーメッセージとツール統合の恩恵を受けることが示されています。複数の暗号実装を対象に、FaCT、ct-verif、dudect、MemSanを評価しています。ツールのUX改善とドキュメントの充実を推奨しています。
定時間ツール一覧 - CROCS チュートリアル付きの定時間解析ツールの厳選カタログです。形式手法ツール（ct-verif、FaCT）、動的ツール（Memsan、Timecop）、シンボリックツール（Binsec）、統計ツール（dudect）を取り上げています。セットアップと使い方に関する実践的なチュートリアルも含まれています。
Paul Kocher：Diffie-Hellman、RSA、DSS、その他のシステムの実装に対するタイミング攻撃 タイミング攻撃を初めて紹介した1996年の論文です。RSAおよびDiffie-Hellmanの剰余べき乗演算に対する攻撃を実証しています。タイミング脆弱性を理解するうえで欠かせない歴史的背景を提供します。
リモートタイミング攻撃は実用的である（Brumley & Boneh） OpenSSLに対する実用的なリモートタイミング攻撃を実証しています。ネットワークレベルのタイミング差だけでRSA鍵を抽出できることを示しています。現実的なネットワーク環境でもタイミング攻撃が成立することを証明しています。
AESに対するキャッシュタイミング攻撃 ルックアップテーブルを使うAES実装がキャッシュタイミング攻撃に対して脆弱であることを示しています。キャッシュタイミングのサイドチャネルを利用してAES鍵を抽出する実用的な攻撃を実証しています。
KyberSlash：除算のタイミングが秘密情報を漏えい Kyber（NISTのポスト量子標準）における最近発見されたタイミング脆弱性を扱っています。除算演算が秘密の係数を漏えいさせることを示しています。現代のポスト量子暗号でも定時間処理の問題が依然として存在することを浮き彫りにしています。
動画リソース
- Trail of Bits：定時間プログラミング - 定時間プログラミングの原則とツールの概要