constant-time-analysis

定数時間解析

コードをコンパイルし、生成されたアセンブリまたはバイトコードで可変時間の命令を調べたうえで、検出された操作のうち、実際に秘密情報を扱うものを判断します。コンパイルの手順は機械的ですが、トリアージが本作業です。

使用する場面

• 署名、暗号化、KEM、鍵導出ルーチンを実装またはレビューするとき
• コードで、鍵、平文、ノンス、トークンから導出された値に / または % を適用しているとき
• ユーザーが「constant-time」、「timing attack」、「side-channel」、「KyberSlash」に言及しているとき
• sign、verify、encrypt、decrypt、derive_key という名前の関数をレビューするとき

使用しない場面

• 実行中のバイナリのタイミング変動を測定するとき — dudect や統計的手法を扱う testing-handbook-skills プラグインの constant-time-testing スキルを使用してください。このスキルはインストールされていない場合があります。このスキルはコンパイラーの出力を静的に調べ、テスト対象のコードを実行することはありません。
• 暗号処理以外のコード、またはすべての入力が公開されている暗号処理コード
• 十分に検証されたライブラリが定数時間の保証を担う高レベル API の使用
• キャッシュなど、その他のマイクロアーキテクチャー上のサイドチャネル — アセンブリの確認では検出できません

言語の振り分け

検出結果を解釈する前に、対象言語のガイドを読んでください。各ガイドには、その言語で危険な命令と、慣用的な定数時間の代替手段が記載されています。

ガイド	言語
references/compiled.md	C、C++、Go、Rust
references/swift.md	Swift
references/vm-compiled.md	Java、C#
references/kotlin.md	Kotlin
references/php.md	PHP
references/javascript.md	JavaScript、TypeScript
references/python.md	Python
references/ruby.md	Ruby

アナライザーの実行

アナライザーは単一のファイルを受け取り、拡張子から言語を判定します。必ず --warnings を指定してください。

uv run {baseDir}/ct_analyzer/analyzer.py --warnings <source_file>

指定しない場合、アナライザーはエラー重大度の検出結果のみを報告します。つまり、除算、剰余、弱い RNG です。4 種類の検出ファミリーは警告重大度のため、報告されません。これらは、シークレットに依存する分岐、早期終了比較（memcmp、strcmp、.equals、==）、シークレットでインデックス付けされたテーブル検索、可変時間のエンコーディングです。認証タグの早期終了比較は、実際のコードで最もよく見られるタイミングバグです。Lucky Thirteen もまさにこれが原因でした。そのため、デフォルトの実行では、最も検出されやすい問題が報告されません。

フラグ	効果
--warnings	上記の警告重大度の 4 つのファミリーを追加します。毎回指定してください
--func <regex>	正規表現に一致する関数名に出力を限定します
--json	機械可読形式の出力
--github	GitHub Actions のアノテーション
--arch <target>	ターゲットアーキテクチャ（x86_64、arm64、riscv64、...）。ネイティブ言語のみ
--opt-level <level>	最適化レベル（O0 から O3、Os、Oz）。ネイティブ言語のみ
--compiler <name>	コンパイラーの選択を上書きします（gcc、clang、go、rustc、swiftc）

大きなファイルからシークレットを扱うルーチンに対象を絞るには、たとえば --func 'sign|verify' のように正規表現を指定します。

ネイティブコンパイル言語（C、C++、Go、Rust、Swift）のコードは、複数の --arch と --opt-level で実行してください。 除算のタイミングと分岐の変換は、アーキテクチャと最適化に依存します。x86_64 の IDIV と arm64 の SDIV は異なり、-O2 での cmov が -O0 では分岐になることもあります。1 回の実行で問題が見つからなくても、安全性が確認できたのは 1 つの構成だけであり、コード全体ではありません。

--arch のクロスコンパイル方法はツールチェーンによって異なります。 clang は --target でクロスコンパイルでき、2 つ目のコンパイラーは不要ですが、libc ヘッダーを含むソースでは、libc6-dev-riscv64-cross など、そのターゲット用の C ライブラリヘッダーも必要です。これがないと bits/libc-header-start.h file not found で失敗します。Go は GOARCH を使ってクロスビルドしますが、go tool objdump には riscv64 ディスアセンブラーがありません。GNU クロスツールチェーンは別個のバイナリなので、gcc では --compiler x86_64-linux-gnu-gcc、--compiler riscv64-linux-gnu-gcc のように明示的に指定する必要があります。代わりに選択されることはないため、レポートには実行されたバイナリが常に記載されます。rustc ではターゲット用の標準ライブラリ（rustup target add）が必要で、Linux 上の Swift はホストのみをターゲットにします。ディストリビューションに含まれる任意のクロスビルドではなく、製品のビルドに使用するツールチェーンと比較してください。

修正後は、コンパイラー、ターゲット、および Os と Oz を含むすべてのレベルで、テスト全体を再実行してください。 コンパイラーに定数除数を渡して強度削減させることで機能する修正は、コンパイラーがその変換を選ぶ場合にしか有効ではありません。その選択は、見た目以上にさまざまです。key_coef / (2 * gamma2) を #define した除数に置き換えても、ここでは実際の除算が生成されます。

ツールチェーン	除算が生成されるレベル
gcc riscv64	O0 から Oz まで、すべてのレベル
gcc arm64、gcc x86_64	Os、Oz
clang arm64	O0、Oz

強度削減はオプティマイザーの便宜的な機能であり、言語による保証ではありません。明示的な乗算とシフトを優先し、サンプル値ではなく入力範囲全体で元の式と一致することを確認してください。2 のべき乗分だけずれた逆数でも、食い違いが生じるまで数百万個の入力に一致することがあります。

Java、Kotlin、C# は JVM／CIL バイトコードにコンパイルされます。アナライザーはそのバイトコードを読み取るため、--arch と --opt-level は適用されません。また、JIT がアナライザーでは確認できない可変時間のネイティブコードを導入する可能性があります。

言語ごとのカバレッジ制限

カバレッジは一律ではなく、その不足によってクリーンなレポートの意味も変わります。

言語	レポートでカバーされない内容
Go	解析対象ファイルのシンボルのみです。go build はランタイムをリンクするため、その除算処理（すべて公開データ上のもの）がなければ検出結果の大半を占めてしまいます
JavaScript, TypeScript	バイトコードの検出結果は、ファイル内で名前を宣言している関数に限定されます。V8 は node の内部処理もユーザーコードと同じようにダンプするためです。無名コールバックはソーススキャンに回されます。TypeScript では、バイトコードの検出結果に関数名は含まれますが行番号はありません。V8 の位置情報はトランスパイル後の出力をインデックスとしているためです
Python, Ruby, PHP	バイトコードには、JIT コンパイルされたランタイムや代替ランタイムではなく、実行に使用したインタープリターが反映されます
Rust	ファイルで fn main が宣言されていない場合はライブラリとして解析されます。呼び出し元のない非公開関数は、解析前に最適化で削除されることがあります
Swift	Linux ではホストプラットフォームをターゲットにします。iOS と macOS のトリプルには Apple ツールチェーンが必要です

検出結果も検出されないことも設定に左右されるため、結果を報告する際は、使用したコンパイラー、アーキテクチャ、最適化レベルを明記してください。

ディレクトリ全体を調べるには、シェルでループ処理します。アナライザーは決定論的なスクリプトで、ファイルごとに 1 回実行します。

for f in src/crypto/*.c; do uv run {baseDir}/ct_analyzer/analyzer.py --warnings --json "$f"; done

前提条件

言語	要件
C, C++, Go, Rust	PATH に gcc／clang、go、rustc があること
Swift	Xcode または Swift ツールチェーン（swiftc）
Java / Kotlin	JDK（javac、javap）。Kotlin では kotlinc も必要です
C#	.NET SDK と ilspycmd（dotnet tool install -g ilspycmd）
PHP	VLD 拡張機能または OPcache を備えた PHP
JavaScript / TypeScript	Node.js
Python	Python 3.x
Ruby	--dump=insns に対応した Ruby

「toolchain not found」エラーが発生した場合は、JVM と .NET のインストール、macOS での keg-only の PATH 設定、トラブルシューティングについて、references/vm-compiled.md を参照してください。

結果の解釈

PASSED — 実行した設定で、error 重大度の検出結果がありません。警告は判定に影響しないため、Result: PASSED と Warnings: 6 が並んでいても通常の状態であり、クリーンな結果ではありません。何かを結論づける前に、警告一覧を確認してください。

FAILED — 危険な命令が見つかりました。関数ごとに報告されます。

[ERROR] SDIV
  Function: decompose_vulnerable
  Reason: SDIV has early termination optimization; execution time depends on operand values

検出結果のトリアージ

このアナライザーにはデータフロー解析がありません。シークレットが対象の命令に渡るかどうかにかかわらず、危険な命令をすべて検出するため、FAILED レポートは判定結果ではなく、調査対象の一覧です。 生の出力をそのまま脆弱性一覧として報告することが、このスキルで最もよくある失敗です。

検出された命令ごとにソースを読み、次の問いに答えてください。オペランドはシークレットデータに依存していますか？ 命令の関数から呼び出し元の入力まで遡って追跡し、分類します。

// FALSE POSITIVE: operands are a buffer length, already public from the ciphertext size
int num_blocks = data_len / 16;

// TRUE POSITIVE: dividend is a private-key coefficient; IDIV/SDIV leaks its magnitude
int32_t q = secret_coef / GAMMA2;

質問	はいの場合
オペランドはコンパイル時定数ですか？	おそらく誤検出です
オペランドは公開パラメーター（長さ、個数、インデックスの上限）ですか？	おそらく誤検出です
オペランドは鍵、平文、nonce、またはトークンに由来しますか？	真陽性です
攻撃者がオペランドの値に影響を与えられますか？	真陽性です

検出された項目ごとに、判定と、その根拠となるデータフローを明記してください。シークレットまで追跡できない検出項目は検出とはいえません。黙って除外せず、その旨を明記してください。

{baseDir}/ct_analyzer/tests/triage_samples/ には、各言語の既知の答えを持つケースがあります。各フィクスチャでは、アナライザーが同じように報告する真陽性と誤検出を組み合わせ、どちらがどちらか、またその理由を expectations.json に記録しています。最も短い例は triage_c.c です。アナライザーは ct_high_bits と ct_block_count の両方で除算を検出し、適切なトリアージを行うと、前者は確認され、後者は除外されます。

弱い乱数生成器やエンコードに関する検出項目では、別の問いが必要です。 Math.random、mt_rand、random.randint、System.Random、base64_encode では、オペランドがシークレットではないため、「オペランドはシークレットに依存していますか？」という問いでは判断できません。代わりに、結果の用途を確認してください。nonce や鍵のシードに使われていれば真陽性ですが、再試行までの遅延にゆらぎを加える用途であれば該当しません。これらはバイトコードではなく、ソースに対する正規表現スキャンで報告されるため、囲んでいる関数ではなく、行番号付きで <source> に帰属します。ただし、PHP では関数名も付与されます。

比較とルックアップに関する検出項目には、それぞれ固有の問いと修正方法があります。 早期終了する比較では、どちらかの値がシークレットかどうかを確認してください。認証タグ、MAC、またはパスワードハッシュの比較は真陽性ですが、公開プロトコルヘッダーの比較は該当しません。テーブルルックアップでは、インデックス がシークレットかどうかを確認してください。配列の内容は関係なく、要素を選択する値だけが重要です。どちらもそのままでは悪用可能なため、該当が確認された場合は、ループを書き換えるのではなく、言語の定時間プリミティブを使用する必要があります。

言語	定時間比較
C, C++	CRYPTO_memcmp（OpenSSL）または sodium_memcmp
Go	crypto/subtle.ConstantTimeCompare
Rust	subtle クレートの ConstantTimeEq
Java, Kotlin	MessageDigest.isEqual
C#	CryptographicOperations.FixedTimeEquals
PHP	hash_equals
Python	hmac.compare_digest
Ruby	OpenSSL.secure_compare
JavaScript, TypeScript	crypto.timingSafeEqual

シークレットに依存するインデックスを使ったルックアップには、置き換え可能な関数はありません。すべての要素にアクセスするビットスライス方式、または算術式での実装が必要です。そのため、AES の S-box テーブルが典型例となっています。base64_encode、bin2hex、chr／ord のようなテーブルを介したシークレットのエンコードも、ライブラリー内で同じ問題を引き起こします。PHP では paragonie/constant_time_encoding が代表的な修正方法です。

制限事項

1. 静的解析のみ — アセンブリーとバイトコードを読み取り、実行時の動作は確認しません。キャッシュタイミングなど、その他のマイクロアーキテクチャー上のチャネルは検出できません。
2. データフロー解析なし — 上記のトリアージを参照してください。
3. 構成に依存 — コンパイラー、最適化レベル、アーキテクチャー、またはランタイムのバージョンが異なると、同一のソースから異なる命令が出力される場合があります。

実世界への影響

• KyberSlash（2023） — ML-KEM の実装における除算命令により、鍵の復元が可能になりました
• Lucky Thirteen（2013） — CBC パディング検証時のタイミング差により、平文の復元が可能になりました
• RSA のタイミング攻撃 — 初期の実装では、除算のタイミングを通じて秘密鍵のビットが漏洩しました

参考資料

• Cryptocoding Guidelines — 暗号のための防御的コーディング
• KyberSlash — ポスト量子暗号における除算のタイミング
• BearSSL Constant-Time — 実践的な定時間処理の手法