タイミング攻撃
タイミング攻撃（タイミングこうげき、英:timing attack）とは、アルゴリズムの動作特性を利用したサイドチャネル攻撃のひとつ。暗号処理のタイミングが暗号鍵の論理値により変化することに着目し、暗号化や復号に要する時間を解析することで暗号鍵を推定する手法[1]。
概要
暗号化におけるタイミング攻撃とは、暗号アルゴリズムを実行するのにかかる時間を解析することで、攻撃者が暗号システムへの不正侵入を試みようとするサイドチャネル攻撃である。コンピュータ内で全ての論理演算を実行するには時間がかかり、入力に応じて時間が異なることがある。各演算の時間を正確に測定することで、攻撃者は入力の後からの作業ができる[2]。
ある質問への応答にかかる時間を測定することにより、システムから情報が漏れる可能性がある。この情報が攻撃者をどの程度助けるかは多くの変動要因しだいであり、暗号システムの設計、システムを実行するCPU、使われているアルゴリズム、さまざまな実装の詳細、タイミング攻撃対策、タイミング測定の精度、などで異なる。
タイミング攻撃は実装に非常に依存しており、コンパイラ最適化に伴って不注意で取り込まれる可能性があるため、設計段階ではしばしば見落とされることがある。タイミング攻撃を回避するには、一定時間(constant-time)機能の設計と最終実行可能コードの慎重な試験が必要となる。
タイミング攻撃は、アルゴリズムの数学的特性というよりも、アルゴリズム実装のデータ依存動作特性を利用する攻撃の例である。データ依存のタイミング情報を削減または排除する方法で、多くの暗号アルゴリズムを実装（またはプロキシによって隠す）することが可能となる。具体的にはサブルーチンへの全ての呼び出しが常に正確にx秒、ここでのxは可能な全ての入力認可に対してルーチンを実行するのに必要な最大時間、で返される実装を考える。そのような実装なら、アルゴリズムのタイミングが何らかの呼出しに供給されたデータに関する情報を漏らすことはない。このアプローチの欠点は、全ての実行に対して使用される時間が機能パフォーマンスの最悪な場合となってしまうことである。
多くの場合、タイミング攻撃は実用的である。
- タイミング攻撃は、データ依存のタイミング変化を有するアルゴリズムに適用できる。データキャッシュを備えたCPU上で実行されるソフトウェアは、メモリがキャッシュを調べる結果として、データ依存のタイミング変化を見せる。乗算などの一部の演算では、入力に応じて実行時間が変化することがある。さまざまな実行時間を頻繁に示す低いレベルの演算を使用するアルゴリズムでは、タイミング依存性を削除することが難しくなる。
- タイミング情報を通して秘密を見つけることは、知られている平文の暗号解読や、暗号文のペア解読を使うよりもはるかに容易い。時々、タイミング情報が暗号解読と組み合わされて、情報漏洩の割合が増加することがある。
例証
冪剰余(modular exponentiation)で使用される平方乗算アルゴリズム（より詳しくはSquare-and-multiply algorithm）の実行時間は、キー内の「1」ビットの数に応じて線形に依存する。「1」ビットの数だけでは鍵の発見を容易にするのに十分な情報ではないが、同じ鍵と異なる入力で繰り返される実行では、受動的攻撃者でさえも、タイミング情報の統計的な相関分析を実行して鍵を完全に復元することだろう。
観測されたタイミング測定には、しばしばノイズ（その源としてはネットワーク遅延や、アクセス移行によるディスクドライブアクセスの違い、伝送エラーから回復するために使用されるエラー訂正技術など）が含まれる。にもかかわらず、タイミング攻撃は、RSA暗号、ElGamal暗号、デジタル署名 アルゴリズムを含む多くの暗号化アルゴリズムに対して実用的である。
2003年にダン・ボネアとデビット・ブラムリーが、SSL対応のWebサーバーに対する実践的なネットワークベースのタイミング攻撃を実演し、それは中国の剰余定理最適化を伴うRSAの使用によるものとは異なる脆弱性に基づいていた。実験における実際のネットワーク距離は小さかったが、その攻撃は見事に数時間でサーバー秘密鍵を復元した。この実演は、SSL実装における幻惑技術の普及と使用をもたらした。この文脈内で、幻惑（Blinding）とは鍵と暗号化時間との間の相関を取り除くことを意図している。
いくつかのバージョンのUnixでは、8文字のパスワードを11文字の文字列にハッシュするために、比較的高価な暗号ライブラリ関数を実装している。旧式のハードウェアでは、この算出には計測可能な程の長い時間がかかり、場合によっては2-3秒かかった。Unixの初期バージョンのログインプログラムは、システムによりログイン名が認識された場合に限り暗号関数（crypt関数）を実行した。これは、パスワードが間違っていたとしても、ログイン名の有効性に関するタイミングを通して情報漏洩となる。攻撃者は、まずブルートフォースをかけて有効だと分かったログイン名のリストを作成し、次にこれらの名前だけを、頻繁に使用されることが知られている大量のパスワードセットと組み合わせてアクセスを試みる。ログイン名の有効性に関する情報がなくても、そうしたアプローチの実行に必要とされる時間は桁違いに増加し、効果的にそれを無効状態にしていく。Unixの以後のバージョンでは、ログイン名の有効性にかかわらず、常にcrypt関数を実行することでこの漏洩を修正している。
キャッシュメモリまたは仮想メモリの両方を用いた単一のシステム上で実行されている安全に分離されたプロセスは、意図的にページフォールトおよび/またはキャッシュミスを1つのプロセスで発生させ、その結果生じるアクセス時間の変化をもう一方から監視することにより通信を可能にする。同様に、アプリケーションは信頼できるものの、そのページング/キャッシングが分岐ロジックの影響を受ける場合においては、アクセス時間の変化を監視することにより分岐条件で比較されたデータの値を決定することが、第2アプリケーションで可能となり得る。極端な例では、これが暗号鍵ビットの復元を可能にさせてしまう[3][4]。
CPU製造業者（インテル、AMD、ARM、IBMを含む）にCPUの再設計を強いることになった2017年のMeltdownとSpectre攻撃は、どちらもタイミング攻撃に依拠したものである[5][6]。
2018年の初頭に、世界のほぼ全てのコンピュータシステムがSpectreに襲われたが、それがタイミング攻撃の歴史上最も強力な例となっている[7][8]。
以下のVisual Basicコードは、文字の不一致があると即座に検査を停止する、安全性に欠けた典型的なデータ列(string)比較を表したものである。例えば、これは "ABCDE"と "ABxDE"を比べる時に3回のループ反復後に（結果を）返すことになる。
Function InsecureCompare(StrA As String, StrB As String, length As Integer) As Boolean
Dim result As Boolean
For i = 1 To length
If Mid(StrA, i, 1) <> Mid(StrB, i, 1) Then Exit For
Next
result = (i > length)
InsecureCompare = result
End Function
比較すると、次のバージョンは全ての文字を検査し、ビット演算を使用して条件付きジャンプなしで検査することにより、一定時間で実行される。
Function SecureCompare(StrA As String, StrB As String, length As Integer) As Boolean
Dim result As Boolean
For i = 1 To length
result = result Or (Asc(Mid(StrA, i, 1)) Xor Asc(Mid(StrB, i, 1)))
Next
SecureCompare = Not result
End Function
備考
もしも敵がハードウェア実装の内部を知っている場合、さらには使用する暗号システムまでも知っていたら、タイミング攻撃を仕掛けるのはより簡単になる。暗号セキュリティは決して隠蔽(obscurity)に依存するべきではない（隠蔽によるセキュリティと、シャノンの格言ことケルクホフスの原理を参照）し、タイミング攻撃への対策もそうであるべきではない。少なくとも、模範を購入してリバースエンジニアリングすることはできる。タイミング攻撃やその他のサイドチャネル攻撃は、一部のデバイスで使用されている暗号アルゴリズムを特定する場合や、場合によってはリバースエンジニアリングに役立つ場合もある。
脚注
- 「平成25年秋期問6 タイミング攻撃の対策」情報処理安全確保支援士ドットコム、2018年9月29日閲覧。
- "BearSSL Why Constant-Time Crypto". www.bearssl.org. Retrieved 2017-01-10.
- See Percival, Colin, Cache Missing for Fun and Profit, 2005.
- Bernstein, Daniel J., Cache-timing attacks on AES, 2005.
- 「「Meltdown」および「Spectre」を狙う攻撃の検出手法を検証」トレンドマイクロ、2018年3月28日。2018年9月30日閲覧。
- 「CPU脆弱性「Meltdown」「Spectre」がセキュリティに及ぼす決定的な影響」ITメディア tech target、2018年7月17日。2018年9月30日閲覧。
- Security flaws put virtually all phones, computers at risk,reuter,January 4, 2018.
- Potential Impact on Processors in the POWER Family,IBM,Aug 16, 2018.
参考文献
- 野崎華恵、藤崎浩一、川村信一「暗号モジュールの実装攻撃対策技術 -」『東芝レビューvol64 No.7』、2009年、28-31頁。（タイミング解析として言及）
- Paul C. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996: 104-113 (https://www.paulkocher.com/TimingAttacks.pdf pdf file])
- David Brumley and Dan Boneh: Remote timing attacks are practical. USENIX Security Symposium, August 2003. pdf file
- Colin Percival: Cache Missing for Fun and Profit, 13 May 2005 (pdf file)
- Lipton, Richard; Naughton, Jeffrey F. (March 1993). “Clocked adversaries for hashing”. Algorithmica 9 (3): 239-252. doi:10.1007/BF01190898 2008年9月2日閲覧。.