定時間テスト

タイミング攻撃は、実行時間の変動を利用して暗号実装から秘密情報を抽出します。暗号解読理論的な弱点を対象とするのとは異なり、タイミング攻撃は実装上の欠陥を活用します。そして、あらゆる暗号コードに影響を与える可能性があります。

背景

タイミング攻撃は Kocher によって1996年に導入されました。それ以来、研究者たちは RSA (Schindler)、OpenSSL (Brumley and Boneh)、AES実装、さらには Kyber などの耐量子暗号アルゴリズムに対する実践的な攻撃を実証しています。

主要概念

概念	説明
定時間	コードパスとメモリアクセスが秘密データに依存しない
タイミングリーク	秘密と相関する観測可能な実行時間の差
サイドチャネル	アルゴリズムではなく実装から抽出される情報
マイクロアーキテクチャ	CPU レベルのタイミング差 (キャッシュ、除算、シフト)

なぜこれが重要か

タイミング脆弱性は以下が可能です:

• 秘密鍵の露出 - RSA/ECDH の秘密指数の抽出
• リモート攻撃の実現 - ネットワーク観測可能なタイミング差
• 暗号セキュリティの回避 - 理論的保証の無効化
• 静かに持続 - 専門分析がない限り未検出のまま

悪用を可能にする2つの前提条件:

1. オラクルへのアクセス - 脆弱な実装への十分なクエリ
2. タイミング依存性 - 実行時間と秘密データの相関

定時間違反の一般的なパターン

4つのパターンが大部分のタイミング脆弱性を占めます:

// 1. 条件分岐 - 最も深刻なタイミング差
if(secret == 1) { ... }
while(secret > 0) { ... }

// 2. 配列アクセス - キャッシュタイミング攻撃
lookup_table[secret];

// 3. 整数除算 (プロセッサ依存)
data = secret / m;

// 4. シフト操作 (プロセッサ依存)
data = a << secret;

条件分岐 は異なるコードパスを引き起こし、膨大なタイミング差につながります。

配列アクセス が秘密に依存すると、AES キャッシュタイミング研究 で示されているように、キャッシュタイミング攻撃を可能にします。

整数除算とシフト操作 は特定の CPU アーキテクチャとコンパイラ設定で秘密をリークします。

パターンが回避できない場合、マスキング技術 を採用してタイミングと秘密の相関を除去します。

例: モジュラー累乗のタイミング攻撃

モジュラー累乗 (RSA および Diffie-Hellman で使用) はタイミング攻撃に対して脆弱です。RSA 復号化は以下を計算します:

$$ct^{d} \mod{N}$$

ここで $d$ は秘密指数です。累乗法による二乗 最適化は乗算を $\log{d}$ に削減します:

$$ \begin{align*} & \textbf{入力: } \text{底 }y,\text{指数 } d={d_n,\cdots,d_0}_2,\text{法 } 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$ の場合、追加の乗算が発生して実行時間を増加させ、ビット情報をリークします。

モジュラー算術で一般的に使用される Montgomery 乗算もタイミングをリークします: 中間値が法 $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 かを明かします。

使用時機

以下の場合に定時間分析を適用してください:

• 暗号実装 (プリミティブ、プロトコル) の監査
• コードが秘密鍵、パスワード、または機密暗号材料を処理する
• 暗号アルゴリズムをゼロから実装する
• 暗号コードに触れるプルリクエストのレビュー
• 潜在的なタイミング脆弱性の調査

以下の場合に代替案を検討してください:

• コードが秘密データを処理しない
• 秘密入力がない公開アルゴリズム
• 非暗号的なタイミング要件 (パフォーマンス最適化)

クイックリファレンス

シナリオ	推奨手法	スキル
リークの不在を証明	形式的検証	SideTrail、ct-verif、FaCT
統計的タイミング差を検出	統計的テスト	dudect
ランタイムで秘密データフローを追跡	動的分析	timecop
キャッシュタイミング脆弱性を検出	シンボリック実行	Binsec、pitchfork

定時間ツールのカテゴリ

暗号コミュニティは4つのカテゴリのタイミング分析ツールを開発しました:

カテゴリ	アプローチ	利点	欠点
形式的	モデル上の数学的証明	リークの不在を保証	複雑性、モデル化の仮定
シンボリック	シンボリック実行パス	具体的な反例	時間集約的なパス探索
動的	マークされた秘密でのランタイムトレース	詳細で柔軟	実行パスへの限定的カバレッジ
統計的	実行時間の測定	実用的、簡単なセットアップ	ルートコーズなし、ノイズ感度

1. 形式的ツール

形式的検証は、コードの抽象化 (モデル) 上でタイミングプロパティを数学的に証明します。ツールはソース/バイナリからモデルを作成し、指定されたプロパティ (例: 秘密として注釈が付けられた変数) を満たしていることを検証します。

人気のあるツール:

• SideTrail
• ct-verif
• FaCT

長所: 不在の証明、言語非依存 (LLVM バイトコード) 短所: 専門知識が必要、モデル化の仮定は実際の問題を見逃す可能性がある

2. シンボリック解析ツール

シンボリック実行は、パスとメモリアクセスがシンボリック変数 (秘密) にどのように依存するかを分析します。具体的な反例を提供します。キャッシュタイミング攻撃に焦点を当てます。

人気のあるツール:

• Binsec
• pitchfork

長所: 具体的な反例はデバッグを助ける 短所: パス爆発は長い実行時間につながる

3. 動的ツール

動的分析は機密メモリ領域をマークし、実行をトレースしてタイミング依存操作を検出します。

人気のあるツール:

• Memsan: チュートリアル
• Timecop (以下を参照)

長所: 詳細な制御、ターゲットを絞った分析 短所: カバレッジは実行されたパスに限定される

詳細ガイド: セットアップと使用法については timecop スキルを参照してください。

4. 統計的ツール

さまざまな入力でコードを実行し、経過時間を測定し、矛盾を検出します。コンパイラ最適化とアーキテクチャを含む実装をテストします。

人気のあるツール:

• dudect (以下を参照)
• tlsfuzzer

長所: セットアップが簡単、実践的な実世界の結果 短所: ルートコーズ情報なし、ノイズが弱いシグナルを曇らせる

詳細ガイド: セットアップと使用法については dudect スキルを参照してください。

テストワークフロー

フェーズ1: 静的分析        フェーズ2: 統計的テスト
┌─────────────────┐            ┌─────────────────┐
│ 秘密データ      │      →     │ タイミング      │
│ フロー を識別   │            │ 差を検出        │
│ ツール: ct-verif│            │ ツール: dudect  │
└─────────────────┘            └─────────────────┘
         ↓                              ↓
フェーズ4: ルートコーズ      フェーズ3: 動的トレース
┌─────────────────┐            ┌─────────────────┐
│ リーク位置を    │      ←     │ 秘密伝播を      │
│ 特定            │            │ 追跡            │
│ ツール: Timecop │            │ ツール: Timecop │
└─────────────────┘            └─────────────────┘

推奨アプローチ:

1. dudect から開始 - タイミング差の迅速な統計チェック
2. リークが見つかった場合 - Timecop を使用してルートコーズを特定
3. 高い確実性のため - 形式的検証を適用 (ct-verif、SideTrail)
4. 継続的監視 - dudect を CI パイプラインに統合

ツールとアプローチ

Dudect - 統計分析

Dudect は2つの入力クラス (固定対ランダム) の実行時間を測定し、Welch の t-検定を使用して統計的に有意な差を検出します。

詳細ガイド: 完全なセットアップ、使用パターン、CI 統合については dudect スキルを参照してください。

定時間分析のクイックスタート

#define DUDECT_IMPLEMENTATION
#include "dudect.h"

uint8_t do_one_computation(uint8_t *data) {
    // 測定するコードをここに記述
}

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) {
            // 固定入力クラス
        } else {
            // ランダム入力クラス
        }
    }
}

主な利点:

• シンプルな 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;

    // 秘密を汚染としてマーク
    poison(&secret_key, sizeof(secret_key));

    // secret_key に依存する分岐またはメモリアクセスは
    // Valgrind によって報告されます
    crypto_operation(secret_key);

    unpoison(&secret_key, sizeof(secret_key));
}

Valgrind で実行:

valgrind --leak-check=full --track-origins=yes ./binary

主な利点:

• タイミングリークの正確な行を特定
• コード計装が不要
• 実行時の秘密伝播を追跡

主な制限:

• マイクロアーキテクチャのタイミング差を検出できない
• カバレッジは実行されたパスに限定される
• パフォーマンスオーバーヘッド (合成 CPU で実行)

実装ガイド

フェーズ1: 初期評価

秘密を処理する暗号コードを識別:

• 秘密鍵、指数、ノンス
• パスワードハッシュ、認証トークン
• 暗号化/復号化操作

迅速な統計チェック:

1. 暗号関数の dudect ハーネスを記述
2. timeout 600 ./ct_test で 5-10 分実行
3. t-値を監視: 高い絶対値はリークを示唆

ツール: dudect 所要時間: 1-2 時間 (ハーネス記述 + 初期実行)

フェーズ2: 詳細分析

dudect がリークを検出した場合:

ルートコーズ調査:

1. Timecop poison() で秘密変数をマーク
2. Valgrind で実行して正確な行を識別
3. 4つの一般的な違反パターンをレビュー
4. 条件分岐をチェック (objdump -d)

ツール: Timecop、コンパイラ出力 (objdump -d)

フェーズ3: 修復

タイミングリークを修正:

• 条件分岐をビット操作による定時間選択に置き換え
• 定時間比較関数を使用
• 配列ルックアップを定時間代替またはマスキングに置き換え
• コンパイラが定時間コードを最適化しないことを検証

再検証:

1. 拡張期間 (30+ 分) で dudect を再実行
2. 異なるコンパイラと最適化レベルでテスト
3. 異なる CPU アーキテクチャでテスト

フェーズ4: 継続的監視

CI への統合:

• テストスイートに dudect テストを追加
• 固定期間 (CI では 5-10 分) 実行
• リークが検出された場合はビルドを失敗

dudect スキルで CI 統合の例を参照してください。

一般的な脆弱性

脆弱性	説明	検出方法	重大度
秘密依存分岐	if (secret_bit) { ... }	dudect、Timecop	致命的
秘密依存配列アクセス	table[secret_index]	Timecop、Binsec	高
可変時間除算	result = x / secret	Timecop	中
可変時間シフト	result = x << secret	Timecop	中
Montgomery 削減リーク	中間値 > N の場合の追加削減	dudect	高

秘密依存分岐: 深掘り

脆弱性: 分岐が実行されるかどうかで実行時間が異なります。最適化されたモジュラー累乗 (二乗乗算法) で一般的です。

dudect で検出する方法:

uint8_t do_one_computation(uint8_t *data) {
    uint64_t base = ((uint64_t*)data)[0];
    uint64_t exponent = ((uint64_t*)data)[1]; // 秘密!
    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(); // ランダムな底
        input[1] = (classes[i] == 0) ? FIXED_EXPONENT : rand(); // 固定対ランダム
    }
}

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-testing  │
                    │     (このスキル)       │
                    └───────────┬─────────────┘
                                │
                ┌───────────────┴───────────────┐
                │                               │
                ▼                               ▼
    ┌───────────────────┐           ┌───────────────────┐
    │      dudect       │           │     timecop       │
    │    (統計的)       │           │    (動的)         │
    └────────┬──────────┘           └────────┬──────────┘
             │                               │
             └───────────────┬───────────────┘
                             │
                             ▼
              ┌──────────────────────────────┐
              │   サポート技術                │
              │ coverage、CI統合             │
              └──────────────────────────────┘

リソース

主要な外部リソース

These results must be false: A usability evaluation of constant-time analysis tools 定時間分析ツールの包括的な使いやすさ評価。主な知見: 開発者は偽陽性に苦労し、より良いエラーメッセージが必要であり、ツール統合の恩恵を受けます。複数の暗号実装にわたって FaCT、ct-verif、dudect、Memsan を評価します。改善されたツール UX とより良いドキュメントを推奨します。

List of constant-time tools - CROCS セットアップと使用法のチュートリアル付きの定時間分析ツールのキュレーション済みカタログ。形式的ツール (ct-verif、FaCT)、動的ツール (Memsan、Timecop)、シンボリックツール (Binsec)、統計的ツール (dudect) をカバーします。セットアップと使用法の実践的なチュートリアルが含まれています。

Paul Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems タイミング攻撃を導入した原始的な1996年の論文。RSA および Diffie-Hellman のモジュラー累乗に対する攻撃を実証します。タイミング脆弱性の理解に不可欠な歴史的背景です。

Remote Timing Attacks are Practical (Brumley & Boneh) OpenSSL に対する実践的なリモートタイミング攻撃を実証します。ネットワークレベルのタイミング差は RSA 鍵抽出に十分であることを示します。タイミング攻撃は実際のネットワーク条件で動作することを証明します。

Cache-timing attacks on AES ルックアップテーブルを使用する AES 実装がキャッシュタイミング攻撃に対して脆弱であることを示します。キャッシュタイミングサイドチャネル経由で AES キーを抽出する実践的な攻撃を実証します。

KyberSlash: Division Timings Leak Secrets Kyber (NIST 耐量子標準) のタイミング脆弱性の最近の発見。除算操作が秘密係数をリークすることを示します。定時間の問題は最新の耐量子暗号にも存在することを強調します。

ビデオリソース

• Trail of Bits: Constant-Time Programming - 定時間プログラミングの原則とツールの概要