【ITニュース解説】Checking that functions are constant time with Valgrind (2010)

プログラムは様々な処理を実行するが、その処理にかかる時間は、入力されるデータの種類やサイズによって変動することが多い。しかし、場合によっては、入力データの内容にかかわらず、常に同じ時間で処理が完了することが極めて重要となるケースがある。この「入力データによって処理時間が変動せず、常に一定であること」を「定数時間」と呼ぶ。

特に、セキュリティ分野、中でも暗号化や認証といった機密情報を扱う処理においては、定数時間で動作することが強く求められる。なぜなら、もし処理時間が入力された秘密の情報（例えば暗号鍵やパスワードなど）によって変動してしまうと、その時間差を攻撃者が利用して秘密の情報を推測する「タイミング攻撃」という脅威が存在するからだ。攻撃者は、プログラムが様々なデータで実行される際の処理時間を何度も測定し、その微妙な時間差やパターンを分析することで、本来なら知り得ないはずの秘密情報を割り出そうとする可能性がある。このような攻撃を防ぐためには、機密情報が処理時間に影響を与えないよう、常に定数時間で処理が実行されるようにプログラムを設計・実装する必要がある。

しかし、プログラムが本当に定数時間で動作しているかを、開発者が手作業で確認するのは非常に困難であり、見落としが発生しやすい。そこで、このような検証を自動化するツールの必要性が生まれる。Valgrindは、プログラムが実行されている最中の挙動を監視し、メモリリークや未初期化の変数使用といった様々なバグを検出する有名なツールである。このValgrindの強力な監視機能を応用することで、プログラムが定数時間で動作しているかをチェックするツールが開発された。それが「ctgrind」と呼ばれるツールだ。

ctgrindは、Valgrindのフレームワークの上で動作し、特定の関数が定数時間で実行されているかを検査することを目的としている。その基本的な仕組みは、プログラムが実行中に扱う「機密データ」（暗号鍵など、外部に漏洩してはならない情報）を特定し、その機密データがプログラムの実行フロー（処理の分岐やループ回数など）やメモリアクセスのパターンに影響を与えていないかを詳細に追跡することにある。

具体的には、ctgrindはCPUのレジスタの状態を監視し、条件分岐の判定（例えば、if文の条件式）や、メモリアクセスを行う際のアドレス計算（例えば、配列のインデックス）に機密データが使われているかどうかをチェックする。もし機密データによって条件分岐の結果が変わったり、アクセスするメモリアドレスが変化したりするような処理が検出された場合、それは処理時間の変動に繋がり、タイミング攻撃の足がかりとなる可能性があるため、ctgrindは警告を発する。

例えば、「もし暗号鍵の特定の部分が0ならAの処理を実行し、そうでなければBの処理を実行する」といったif文があったとする。この場合、暗号鍵の値によってAとBのどちらの処理が実行されるかが変わり、それぞれの処理にかかる時間が異なれば、結果として全体の処理時間が変動してしまう。ctgrindはこのようなデータ依存の条件分岐を検出する。また、「配列のsecret_index番目の要素にアクセスする」といった処理も、secret_indexが機密データであり、その値によってアクセスするメモリアドレスが異なると、CPUのキャッシュメモリのヒット・ミスパターンが変わり、処理時間に影響を与える可能性がある。ctgrindはこのようなデータ依存のメモリアクセスも検出対象とする。

ctgrindのようなツールは、人間では見つけにくい微妙なタイミングの脆弱性を自動的に検出できるため、暗号ライブラリやセキュリティ関連のソフトウェア開発において非常に有用だ。これにより、より堅牢で安全なコードを開発するための強力な支援となる。しかし、ctgrindはあくまでソフトウェアレベルでのデータ依存性に焦点を当てたツールであり、CPUの消費電力の変動や電磁波の放射といったハードウェアレベルのサイドチャネル攻撃までを検出できるわけではない点には注意が必要である。それでも、プログラムの定数時間性を確保するための重要な一歩となるツールであることは間違いない。