定数時間プログラミングの原理と落とし穴

定数時間が意味するもの

定数時間（constant-time）プログラミングは、名前に反して「実行時間を一定にする」技術ではありません。本質は、攻撃者が観測できる量（実行時間・分岐経路・メモリアクセス先・消費電力）を、秘密データと統計的に無相関にすることです。実行時間が入力長やキャッシュ状態でばらつくのは構いません。禁じられるのは、秘密の値そのものに応じて観測量が変わることです。

この規律が要るのは、アルゴリズムが数学的に安全でも実装が秘密を漏らすからです（サイドチャネル攻撃の核心）。具体的には、秘密に対して次の4つを禁じます。

• 秘密に依存した分岐：if (secret_bit) で経路・時間・電力が変わる。
• 秘密に依存した早期 return / ループ回数：処理量が時間に漏れる。
• 秘密をインデックスにしたメモリアクセス：table[secret] でアクセス位置がキャッシュに漏れる。
• 秘密オペランドに対する可変時間命令：除算・剰余・一部の乗算は値で所要サイクルが変わる。

なぜ「比較」すら危険か

最も基本的かつ頻出の落とし穴が、トークンや MAC タグの比較です。標準ライブラリの memcmp や素朴な等価比較は、不一致を見つけた瞬間に return するため、一致した先頭バイト数が実行時間に漏れます。

/* 危険：先頭から一致した分だけ走査が進み、一致バイト数が時間に出る */
int insecure_equal(const uint8_t *a, const uint8_t *b, size_t n) {
    for (size_t i = 0; i < n; i++)
        if (a[i] != b[i]) return 0;   /* 早期 return が秘密を漏らす */
    return 1;
}

攻撃者は先頭バイトを総当たりし、**わずかに処理時間が伸びた候補が「正解の1バイト」**だと判定できます。これを繰り返すと、256^n の探索が 256×n 程度に落ちます。MAC 検証でこれをやると、タグを偽造されかねません。対策は、常に全長を走査し、差分を XOR で累積して最後にまとめて判定することです。

/* 安全：途中で抜けず、経路・回数が中身に依存しない（定数時間） */
int constant_time_equal(const uint8_t *a, const uint8_t *b, size_t n) {
    uint8_t diff = 0;
    for (size_t i = 0; i < n; i++)
        diff |= a[i] ^ b[i];          /* 1ビットでも違えば diff に痕跡 */
    return diff == 0;
}

実務では自作せず、CRYPTO_memcmp（OpenSSL）、sodium_memcmp（libsodium）、Python の hmac.compare_digest を使います。なお、長さが秘密でない限り、長さの不一致で早期 return しても問題ありません。

分岐の代わりに：マスクと条件付き move

秘密に依存して値を選びたいときは、if を使わずビットマスクで両方を常に評価して選びます。

/* cond（0 か 1）が秘密でも経路は一定 */
uint32_t select_ct(uint32_t cond, uint32_t a, uint32_t b) {
    uint32_t mask = (uint32_t)(-(int32_t)(cond & 1)); /* 1→全ビット1, 0→全ビット0 */
    return (a & mask) | (b & ~mask);                  /* 常に両方を計算して選ぶ */
}

集合 {a, b} のどちらを採るかを、分岐ではなくデータフローで表現するのがコツです。CPU レベルでは条件付き move（cmov）が同じ役割を果たしますが、後述の通りコンパイラに cmov を出させる保証はありません。テーブル参照を秘密で引く場合は、テーブル全体を線形走査してマスク選択する（全エントリに触れる）ことでアクセス位置を隠します。これは AEAD 実装や RSA の冪乗、サイドチャネル攻撃で触れた bitsliced AES の発想と同じです。

最大の落とし穴：コンパイラが定数時間性を壊す

定数時間プログラミングが難しい最大の理由は、ソースコードが定数時間でも、コンパイラが生成コードで秘密依存の経路を再導入することです。C 標準は「観測等価な変換」を許すだけで、タイミングは観測対象に含まれません。コンパイラから見れば定数時間性はただの非効率であり、最適化の対象です。

実務的な緩和策は、コンパイラに最適化させない「不透明化バリア」を挟むことです。例えばインラインアセンブリで値を一度通し、コンパイラに中身を推論させない手法が使われます。

/* 値を「不透明」にし、コンパイラの定数伝播・分岐化を妨げる */
static inline uint32_t opaque(uint32_t x) {
    __asm__ volatile("" : "+r"(x));   /* x の正体を見えなくする壁 */
    return x;
}

libsodium や BearSSL はこの種のバリアや手書きアセンブリを多用しています。ただし、これは規格保証ではなく経験則であり、新しいコンパイラが回避してくる可能性は常にあります。

ハードウェアという下の層

コンパイラを抑え込んでも、その下の CPU が定数時間性を壊すことがあります。

整数除算・剰余は多くの CPU でオペランド値依存の可変サイクル命令であり、秘密に対して使うと漏れます。暗号実装が剰余をモンゴメリ乗算で置き換えるのはこのためです。投機実行による Spectre / Meltdown は、秘密に依存した分岐やアクセスを投機的に実行し、その痕跡をキャッシュに残します。さらに Hertzbleed は、データ依存の消費電力が CPU の動的周波数調整（DVFS）を通じて実行時間に化けることを示し、「電力だけの問題」だったものをリモートのタイミング攻撃に格上げしました。

検証：信じずに測る

定数時間性は目視レビューでは保証できません。専用ツールで生成コードと実測を検証します。

• ctgrind / MemSan 系（静的・動的解析）: 秘密データを Valgrind の「未初期化メモリ」として印付けし、それが分岐条件やメモリアドレスに使われた瞬間に検出する。ConstantTime 違反を直接捕まえる発想で、Adam Langley による ctgrind（2010）が原型。秘密がアドレス計算や分岐に流れ込めばエラーになる。
• dudect（統計的実測）: 2クラスの入力（固定の秘密 vs ランダム）で実行時間分布を大量に集め、Welch の t 検定で「両者の分布が区別できるか」を判定する。区別できれば秘密依存のタイミングがある証拠。ソースを読まず実バイナリ・実CPUで測るため、コンパイラやマイクロアーキ由来の漏れも捉えられる。

dudect の骨子:
1. クラス0（固定の秘密入力）とクラス1（ランダム入力）を交互に実行
2. 各実行のサイクル数を計測し、外れ値を crop（高パーセンタイルで裾を切る）
3. 2クラスのサイクル分布に Welch の t 検定を適用
4. |t| が閾値（例 ~4.5）を超えたら「タイミングが入力で区別できる」＝漏れあり

実務での向き合い方

第一原則は「暗号と機微な比較を自作しない」です。定数時間性はソースの正しさだけでは決まらず、コンパイラとCPUという下の層で崩れるため、監査済みの libsodium・BearSSL・各言語標準（hmac.compare_digest など）に任せます。

それでも自前で書く必要があるなら、(1) 秘密依存の分岐・早期return・テーブル参照・除算を排し、(2) 不透明化バリアで最適化を抑え、(3) ctgrind と dudect で生成コードと実測の両面を検証する、という三層の規律を守ります。鍵を扱う処理を専用ハードウェア（HSM）に逃がし、そもそも攻撃者と同じCPUで秘密を計算しない設計も有効です。最後に、定数時間性はライブラリ更新やコンパイラ更新のたびに再検証が要ることを忘れないでください。一度通った検証は、ツールチェーンが変われば無効になります。