タイミング攻撃

暗号学におけるタイミング攻撃は、暗号アルゴリズムの実行にかかる時間を解析することで暗号システムを侵害しようとするサイドチャネル攻撃です。コンピュータ内のあらゆる論理演算は実行に時間がかかり、その時間は入力によって異なります。各演算の時間を正確に測定することで、攻撃者は入力までさかのぼって調べることができます。タイミング情報から秘密を見つけることは、既知の平文と暗号文のペアを解読するよりもはるかに簡単です。タイミング情報は暗号解読と組み合わされて情報漏洩率を高めることもあります。^[1]

特定のクエリに応答するのにかかる時間を測定することで、システムから情報が漏洩する可能性があります。この情報が攻撃者にどの程度役立つかは、暗号化システムの設計、システムを実行する CPU、使用されるアルゴリズム、さまざまな実装の詳細、タイミング攻撃対策、タイミング測定の精度など、多くの変数に依存します。タイミング攻撃は、データに依存したタイミング変動があるアルゴリズムに適用できます。実行時間が頻繁に変化する低レベルの操作を使用する一部のアルゴリズムでは、タイミング依存性を排除することが困難です。

タイミング攻撃は実装に大きく依存し、コンパイラの最適化によって意図せず導入される可能性があるため、設計段階では見落とされがちです。タイミング攻撃を回避するには、定数時間関数の設計と最終的な実行可能コードの慎重なテストが必要です。^[1]

多くの暗号化アルゴリズムは、データに依存するタイミング情報を削減または排除する方法、つまり定数時間アルゴリズムで実装（またはプロキシでマスク）できます。定数時間アルゴリズムの実装は、タイミングセーフ実装と呼ばれることもあります^[2]。サブルーチンへのすべての呼び出しが常に正確に x 秒で返される実装を考えてみましょう。ここで、x は、すべての許可された入力に対してそのルーチンを実行するのにかかる最大時間です。このような実装では、アルゴリズムのタイミングによって、その呼び出しに提供されたデータに関する情報が漏洩する可能性が低くなります。^[3]このアプローチの欠点は、すべての実行に使用される時間が、関数の最悪ケースのパフォーマンスの時間になることです。

タイミングのデータ依存性は、次のいずれかから生じる可能性がある。^[1]

• CPU がデータをキャッシュする可能性があるため、非ローカル メモリ アクセスです。データ キャッシュを備えた CPU で実行されるソフトウェアは、メモリがキャッシュを参照する結果として、データに依存するタイミング変動を示します。
• 条件付きジャンプ。現代の CPU は推測によって過去のジャンプを投機的に実行しようとします。推測が間違っていると (本質的にランダムな秘密データでは珍しいことではありません)、CPU がバックトラックしようとするため、測定可能な大きな遅延が発生します。これには、分岐のないコードを記述する必要があります。
• 実際の CPU ハードウェアに応じて、いくつかの「複雑な」数学演算が実行されます。
  • 整数除算は、ほとんどの場合、一定時間ではありません。CPU は、除数または被除数が小さい場合に異なるコード パスを使用するマイクロコード ループを使用します。
  • バレル シフターのない CPU は、シフトと回転をループで 1 度に 1 つの位置ずつ実行します。そのため、シフトする量を秘密にすることはできません。
  • 古い CPU は、除算と同様の方法で乗算を実行します。

モジュラ指数演算で使用される平方乗算アルゴリズムの実行時間は、キー内の '1' ビットの数に比例します。 '1' ビットの数だけでは、キーを簡単に見つけるのに十分な情報ではありませんが、同じキーと異なる入力で繰り返し実行することで、タイミング情報の統計的相関分析を実行し、受動的な攻撃者であってもキーを完全に復元できます。 観測されたタイミング測定には、多くの場合、ノイズ (ネットワーク遅延、アクセスごとのディスク ドライブ アクセスの違い、伝送エラーからの回復に使用されるエラー訂正技術など) が含まれます。 ただし、タイミング攻撃は、 RSA、ElGamal、デジタル署名アルゴリズムなど、多くの暗号化アルゴリズムに対して実用的です。

2003 年、BonehとBrumley は、中国剰余定理の最適化による RSA の使用に関連する別の脆弱性に基づいて、SSL対応 Web サーバーに対する実用的なネットワークベースのタイミング攻撃を実証しました。実験では実際のネットワーク距離は短かったものの、攻撃によりサーバーの秘密鍵が数時間で復元されました。この実証により、SSL 実装におけるブラインド技術が広く導入され、使用されるようになりました。この文脈では、ブラインドは鍵と暗号化時間の相関関係を排除することを目的としています。^[4]

Unixの一部のバージョンでは、8 文字のパスワードを 11 文字の文字列にハッシュするためのcryptライブラリ関数の比較的高価な実装が使用されています。古いハードウェアでは、この計算には意​​図的に測定可能な長い時間がかかり、場合によっては 2 秒から 3 秒もかかりました。 ^{[引用が必要] Unix の初期バージョンの}ログイン プログラムは、ログイン名がシステムによって認識された場合にのみ crypt 関数を実行しました。これにより、パスワードが間違っている場合でも、タイミングを通じてログイン名の有効性に関する情報が漏洩しました。攻撃者は、最初にブルート フォースを適用して有効であることがわかっているログイン名のリストを作成し、次にこれらの名前と頻繁に使用されることがわかっている大量のパスワードを組み合わせてアクセスを試みることにより、このような漏洩を悪用する可能性があります。ログイン名の有効性に関する情報がなければ、このようなアプローチを実行するために必要な時間は桁違いに長くなり、事実上役に立たなくなります。Unix のそれ以降のバージョンでは、ログイン名の有効性に関係なく常に crypt 関数を実行することでこの漏洩を修正しました。^{[引用が必要]}

キャッシュメモリまたは仮想メモリのいずれかを備えた単一システム上で実行されている、安全に分離された 2 つのプロセスは、一方のプロセスで意図的にページフォールトやキャッシュミスを発生させ、もう一方のプロセスからのアクセス時間の変化を監視することで通信できます。同様に、アプリケーションが信頼されていても、そのページング/キャッシュが分岐ロジックの影響を受ける場合、2 番目のアプリケーションがアクセス時間の変化を監視することで、分岐条件と比較したデータの値を特定できる可能性があります。極端な例では、これにより暗号キー ビットを回復できる可能性があります。^{[5] [6]}

2017年のメルトダウン攻撃とスペクター攻撃は、CPUメーカー（Intel、AMD、ARM、IBMなど）にCPUの再設計を強いることになったが、どちらもタイミング攻撃を利用している。^[7] 2018年初頭の時点で、世界中のほぼすべてのコンピュータシステムがスペクターの影響を受けています。^{[8] [9] [10]}

タイミング攻撃は防ぐのが難しく、他の攻撃を拡張するためによく使用されます。たとえば、2018年には、RSAに対する古い攻撃が、元のバグから20年後にタイミングサイドチャネルの亜種として再発見されました。^[11]

次のCコードは、文字が一致しなくなるとすぐにテストを停止する、典型的な安全でない文字列比較を示しています。たとえば、「ABCDE」と「ABxDE」を比較する場合、ループを 3 回繰り返した後に戻ります。

bool insecureStringCompare ( const void * a 、const void * b 、size_t length ) { const char * ca = a 、* cb = b ; for ( size_t i = 0 ; i < length ; i ++ ) if ( ca [ i ] != cb [ i ] ) falseを返します。trueを返します。}         
         
          
       
       
   

比較すると、次のバージョンは、すべての文字をテストし、ビット演算を使用して結果を累積することで、 定数時間で実行されます。

bool constantTimeStringCompare ( const void * a , const void * b , size_t length ) { const char * ca = a , * cb = b ; bool result = true ; for ( size_t i = 0 ; i < length ; i ++ ) result &= ca [ i ] == cb [ i ]; return result ; }         
         
     
          
        
   

Cライブラリ関数の世界では、最初の関数は に類似しておりmemcmp()、後者の関数はNetBSDのconsttime_memequal()または^[12] OpenBSDのtimingsafe_bcmp()およびに類似しています。他のシステムでは、 OpenSSLやlibsodiumtimingsafe_memcmpなどの暗号化ライブラリの比較関数を使用できます。

タイミング攻撃は、攻撃者がハードウェア実装の内部を知っていれば、さらには使用されている暗号システムを知っていれば、実行しやすくなります。暗号のセキュリティは、どちらかの不明瞭さに決して依存すべきではないため (「不明瞭さによるセキュリティ」、具体的にはシャノンの格言とケルクホフスの原理の両方を参照)、タイミング攻撃に対する耐性も、そのどちらにも依存すべきではありません。少なくとも、サンプルを購入してリバース エンジニアリングすることは可能です。タイミング攻撃やその他のサイド チャネル攻撃は、デバイスで使用される暗号アルゴリズムを特定したり、場合によってはリバース エンジニアリングしたりする際にも役立つ場合があります。

• ポール C. コッチャー。Diffie-Hellman、RSA、DSS、およびその他のシステムの実装に対するタイミング攻撃。CRYPTO 1996: 104–113
• リプトン、リチャード; ノートン、ジェフリーF. (1993 年 3 月) 。「ハッシュのためのクロックされた敵対者」。Algorithmica。9 ( 3): 239–252。doi :10.1007/BF01190898。S2CID  19163221。
• Reparaz, Oscar; Balasch, Josep; Verbauwhede, Ingrid (2017 年 3 月)。「私のコードは定数時間ですか?」(PDF)。Design , Automation & Test in Europe Conference & Exhibition (DATE)、2017 年。pp. 1697–1702。doi : 10.23919 / DATE.2017.7927267。ISBN 978-3-9815370-8-6. S2CID  35428223。   さまざまなデータに対してコードを実行する時間を計測するシンプルなプログラム、dudect について説明します。