タイミング攻撃

タイミング攻撃とは

タイミング攻撃（Timing Attack）は、暗号アルゴリズムの実装における処理時間の変動を利用したサイドチャネル攻撃の一種です。攻撃者は、暗号化や復号の処理にかかる時間を詳細に分析することで、暗号鍵の情報を推測しようと試みます。この攻撃は、アルゴリズム自体の弱点ではなく、実装の詳細に起因する点が特徴です。

タイミング攻撃の原理

コンピュータのすべての演算処理は、実行にわずかな時間を要します。その処理時間は、入力データによって変動することがあります。タイミング攻撃では、この処理時間の変動を精密に測定し、そこから暗号システムの内部動作に関する情報を取得します。例えば、ある質問に対する応答時間が、システム内部の情報漏洩につながる可能性があります。この情報がどれほど攻撃に役立つかは、システムの設計、使用されているCPU、アルゴリズム、実装の詳細、タイミング攻撃対策、測定精度など、多くの要因に左右されます。

タイミング攻撃は実装に強く依存しており、コンパイラの最適化によって意図せず導入されてしまうこともあります。そのため、設計段階で見落とされがちです。この攻撃を回避するには、一定時間で動作する機能（constant-time）を設計し、最終的な実行可能コードを慎重にテストする必要があります。

タイミング攻撃の具体例

タイミング攻撃は、データ依存の処理時間変動を示すアルゴリズムに対して有効です。例えば、データキャッシュを持つCPU上で動作するソフトウェアでは、メモリがキャッシュを調べる結果として、処理時間に変動が生じます。また、乗算などの演算も、入力値によって処理時間が異なる場合があります。これらの低レベルの演算を頻繁に使用するアルゴリズムでは、タイミング依存性を除去することが難しくなります。

タイミング情報から秘密情報を発見することは、既知の平文や暗号文のペアを使った解読よりも容易な場合があります。場合によっては、タイミング情報と暗号解読を組み合わせることで、情報漏洩の割合を増加させることも可能です。

べき剰余演算の例: べき剰余演算で使用される平方乗算アルゴリズムでは、鍵の中の「1」ビットの数に比例して実行時間が長くなります。この情報だけでは鍵を特定するには不十分ですが、同じ鍵と異なる入力で処理を繰り返すと、攻撃者はタイミング情報の統計的な分析から鍵を完全に復元できる可能性があります。
ネットワーク遅延の影響: 実際のタイミング測定には、ネットワーク遅延、ディスクアクセス、伝送エラー回復処理などによるノイズが含まれることがあります。しかし、タイミング攻撃は、RSA暗号、ElGamal暗号、デジタル署名アルゴリズムなどの多くの暗号アルゴリズムに対して実用的です。
SSL攻撃の例: 2003年には、ダン・ボネとデビッド・ブルムリーによって、SSLに対応したWebサーバーに対する実践的なネットワークベースのタイミング攻撃が実証されました。これは、中国剰余定理によるRSA最適化とは異なる脆弱性に基づいたものでした。実際のネットワーク距離は短いにもかかわらず、この攻撃によって数時間でサーバーの秘密鍵が復元されました。この事件を受けて、SSL実装における幻惑（ブラインディング）技術が普及しました。ブラインディングとは、鍵と暗号化時間の相関関係を解消するための手法です。
パスワードハッシュの例: いくつかのUnixシステムでは、パスワードをハッシュ化する際に、時間のかかる暗号ライブラリ関数を使用していました。初期のバージョンのログインプログラムでは、ログイン名がシステムに認識された場合にのみこの関数を実行していました。これにより、パスワードが間違っていたとしても、ログイン名の有効性に関する情報がタイミングを通じて漏洩していました。攻撃者は、まず有効なログイン名のリストを作成し、次にそれらの名前に対して頻繁に使われるパスワードを試すことで攻撃を実行しました。この脆弱性は、ログイン名の有効性に関わらず常に暗号化関数を実行するように修正されました。
プロセス間通信の例: キャッシュメモリや仮想メモリを使用するシステムでは、安全に分離されたプロセス間で、意図的なページフォールトやキャッシュミスを発生させることで、アクセス時間の変化を通じて通信が可能になります。同様に、アプリケーションのページングやキャッシングが分岐ロジックの影響を受ける場合、アクセス時間の変化を監視することで、分岐条件で比較されたデータの値を特定できる可能性があります。極端な場合、これにより暗号鍵のビットを復元することが可能です。

近年の事例

2017年には、CPUの再設計を余儀なくさせたMeltdownとSpectreの攻撃が発表されました。これらの攻撃は、いずれもタイミング攻撃に依存したものでした。2018年初頭には、Spectre攻撃が世界中のほぼすべてのコンピュータシステムに影響を与え、タイミング攻撃の歴史の中で最も強力な例となりました。

タイミング攻撃への対策

タイミング攻撃を防ぐためには、以下の対策が必要です。

一定時間アルゴリズム: アルゴリズムの処理時間が入力データに依存しないように、一定時間で動作する設計を採用します。
ブラインディング: 暗号鍵と暗号化時間の相関関係を取り除くブラインディング技術を使用します。
ハードウェア対策: CPUのキャッシュやメモリへのアクセス時間を変動させないようなハードウェア対策を講じます。
* 実装の慎重なテスト: 実装時にタイミング攻撃の脆弱性が混入していないかを厳密にテストします。

まとめ

タイミング攻撃は、実装の詳細に依存する攻撃であり、アルゴリズムの数学的な特性とは関係ありません。この攻撃は実用的であり、適切に対策を講じないと情報漏洩につながる可能性があります。暗号システムの設計者は、タイミング攻撃の脅威を十分に理解し、実装時に適切な対策を講じる必要があります。

もし攻撃者がハードウェアの実装を詳細に知っており、さらには使用している暗号システムまでも知っている場合、タイミング攻撃はより容易になります。暗号セキュリティは隠蔽に依存すべきではなく、タイミング攻撃への対策も同様です。少なくとも、製品を購入してリバースエンジニアリングすることが可能です。タイミング攻撃や他のサイドチャネル攻撃は、一部のデバイスで使用されている暗号アルゴリズムを特定したり、場合によってはリバースエンジニアリングに役立ったりすることもあります。

もう一度検索