副作用暗号化

リチャード・スノーデンのおかげで、 NSAが何であり、何をするのかを知る人が増えています。 開示された内部プレゼンテーションに基づいて、NSAがトラフィックの収集とインターネットプロバイダーとソフトウェアジャイアントのネットワークでの「正しい」プログラムの導入だけでなく、暗号アルゴリズムの分析にも多大な努力を費やしていることは明らかです。 2013年の国家安全保障予算を含む178ページの文書が公開されました。 その結果、統合暗号化プログラムプロジェクトに110億ドルが費やされました。 そのようなお金のために何ができるでしょうか？ 確かに利益を生む。 たとえば、ユタ州の巨大なコンピューティングセンターの建設は、20億ドルで、モルモン教徒の住居にあります。 センターには2300 m2のサーバースペースがあり、65メガワットの発電所と、すべてを冷却する6万トンの冷凍設備があります。 2012年、NSAが最近、暗号解読と複雑なシステムのハッキングで画期的な成功を収めたことが公式の口から隠されました。 これが彼らが新しいデータセンターを必要とした理由ですか？ 暗号学の第一人者であるブルース・シュナイアーは、これらの声明についてコメントし、近い将来、NSAがAESなどの最新の強力な暗号を解読する可能性は低いことを示唆しました。 そして彼は、NSAがその努力をアルゴリズムの「正直な」ハッキングではなく、これらのアルゴリズムの実装の脆弱性を見つけることに集中すると仮定しました。 ブルースは、成功を達成できるいくつかの分野を特定しました。

• ハッキング乱数センサーが使用されるキー生成手順に対する攻撃
• データ送信の弱いリンクへの攻撃（たとえば、チャネルは十分に保護されており、ネットワークスイッチは不良です）
• システム管理者の監視のために一部の場所に残っている弱いキーを使用した暗号に対する攻撃（適切な候補は1024ビットキーを持つRSAです）
• 副作用攻撃

副作用への攻撃とは何かを考えてみましょう。



非常に多くの研究と研究が、さまざまな暗号システムのセキュリティの分析に費やされています。 同時に、「暗号システム」はここでは非常に広く考えられています。特定の暗号化プロトコル、ハードウェアデバイス、またはサーバー、サブスクライバーなどを含むソフトウェアとハ​​ードウェアシステム全体です。まず、特定の種類の攻撃に耐えるシステムの能力を分析します：クラッカー（暗号に関する文献では、通常、イブまたはマロリーという名前が付けられています）。特定の知識とツールにアクセスできます。 彼はそれらを使用してシステムにハッキングします。キーを計算し、暗号化されたメッセージを読み取り、データまたはデジタル署名を置き換えます。 潜在的な攻撃者が妥当な時間、妥当なコンピュータの電力を使用してこのシステムの秘密情報にアクセスできない場合、システムは耐性があると見なされます。 暗号化の優れた形態は、独自のアルゴリズムの発明ではなく、徹底的に研究され、その強度が通常数学によってサポートされているため、永続的でタイムテストされた方法の使用です。 疑問が生じます：私のデバイスで、たとえば、いくつかの実証済みの定理に基づいたアルゴリズムを使用すると、落ち着くことができます（少なくとも量子コンピューターの発明まで）。 判明しました、いいえ。



セキュリティ分析の従来のモデルは、「実験」オブジェクトを、暗号化などの特定の操作を実行する一種のブラックボックスと見なします。プレーンテキストは入力に送信され、暗号化は出力に表示されます。 また、このボックス内にキーを保存します（オプションとして、外部から設定することも、一定にすることも、セッションごとに生成することもできます-重要ではありません）。 主なことは、キーが外部の世界にアクセスできないことであり、Evaはハッカーの標準的な武器に満足しています：入出力でデータをインターセプトする、任意のデータを大量に提供する機能、アルゴリズム自体とそのパラメーターの正確な知識などです。



放射線、電力消費、およびその他の記録された症状、電子デバイス、またはこれらのデバイス上のコンピュータープログラムを通じて外の世界と対話することにより、攻撃者に多くの有用な情報を与えることができます。 これらの症状は、副作用、時には副作用と呼ばれ、英語で呼ばれます。 文献には確立された用語-サイドチャネルがあります。 ハッカーにとって、この情報は、徹底的な検索という不愉快な見通しから彼を救うことができるので、「金でその重みに値する」ことができます。 ドアロックを開くこととの類推で、ドアが取り付けられているボルトを外すのに十分な場合、泥棒の家の所有者がマスターキーを選ぶのに長い時間がかかるのはなぜですか？

起源

副作用の「利点」についての最初の重大な言及は、英国のMi-5エージェントであるピーター・ライトの自伝にあります。60年代にロンドンのエジプト大使館に駐車されたロータリー暗号マシンの暗号を解読する試みについて説明しています。 当時は明らかにコンピューティング能力が不足していたため、著者はマイクを設置し、マシンから発せられるクリックを記録することを提案しましたが、毎朝、技術者によって整理されました。 したがって、3つのホイールのうちの2つのホイールの位置を計算できたため、最終的にはコードを開くのに役立ちました。



包括的な副作用は、1995年にPaul Kocherによる研究の公開後、秘密鍵の値と暗号化デバイスがべき乗演算を計算するのにかかる時間との統計的関係の存在を証明した後、検討され始めました。 それ以来、特定のハードウェアデバイスでの暗号化の実装は、もはや「鉄筋コンクリート」に見えないことが明らかになりました。 さまざまなシステムのセキュリティを確保するための重要な場所は、暗号プロセッサによって占められています。 それらは暗号化操作用に最適化されており、敵対的な環境と相互作用しない独自の分離コードを実行し、秘密キーを独自のメモリに保存します。多くの場合、保護されています-不正な読み取りが検出された場合、キーマテリアルは破棄されます 副作用分析の開発により、少なくとも2つの理由により、暗号プロセッサはそれほど安定していないように見えます。

• それらは利用可能です（チップを備えた銀行カード、SIMカード、タブレットやラップトップのDRMチップ、トークン-私たちは毎日これに遭遇します）
• 副作用に攻撃を展開するために、巨大なコンピューティング能力と超高価な機器は必要ありません。 たとえば、100 MHzの分解能を持つデジタルオシロスコープのコストは約2000ドルです。

攻撃の分類

文献における副作用への攻撃は、通常、いくつかの独立した基準に従って分類されます。

1.介入の事実について

• 受動的攻撃 ：攻撃者はデバイスの操作に干渉せず、情報を収集するオブザーバーにすぎません。 この場合、「実験的」デバイスは、攻撃が発生しなかったかのように機能します。
• 能動的攻撃 ：攻撃者は、外部および内部の両方のインターフェイスに作用することにより、デバイスの操作を妨害するか、少なくともデバイスをオンにして作業を開始します

2.介入の程度により

• 侵入攻撃 ：デバイス内部への直接的な影響。 それは、導体の単純な電気的測定、または非常に筋金入りの方法、たとえば、イオン照射、結晶のレーザー切断、命令の実行に影響を与える目的での意図的な干渉などによる導電性構造の作成のいずれかです。
• 侵入なしの近接攻撃 ：攻撃者は測定されたすべてを測定しますが、デバイスの通常の操作を妨害しません。 通常、電力消費とランタイムを測定し、アクセス可能な導体の信号も読み取ります
• 遠くからの攻撃：侵入のない攻撃に似ていますが、この場合、デバイスへの物理的なアクセスはありません。つまり、測定されたパラメーターのセットが大幅に狭められます。 一方、このような攻撃の目標は、隔離されたデバイスだけでなく、ネットワークサービスまたは単なるプログラムでもあります。

3.データ分析の方法による

• 簡単な分析 ：一連の少数の測定が実行され、各測定が個別に分析されます。実行可能な命令と「漏洩した」情報の関係を特定しようとします。 これとは別に、ソースデータの変化が観測データの変化にどのように影響するかだけでなく、異なる測定値間の相関関係を明らかにしようとしていないことを意味します。 この方法の主な問題は、機密情報の実際の兆候を無駄なノイズから分離することです。
• 差分分析 ：ソースデータと観測データの関係を特定しようとしています。 これは、多数の測定とそれに続く結果の統計分析を実行することで達成されます。 分析は、ノイズの影響を平準化するのに役立ちます-「ハエをカツレツから分離する」ことができます。 この場合、攻撃者は関心のあるデバイスの単純化されたモデルによって撃退されます。

実践-RSA暗号化に対するタイムアタック

RSA暗号化のタイムアタックについては、文献でよく知られ、よく研究されています。 攻撃の基本は、暗号化操作の実行にかかった時間を正確に測定することです。 ここでは、ハッカーはデバイス自体、入力にデータを提供し、タイムスタンプを測定するために必要な機器を持ち、デバイスで使用されているのはRSAであることも確実に知っていると仮定します。



タイムアタックは、原則として、攻撃されたデバイスが入力データ（暗号か平文かに関係なく）、またはキーに応じて暗号化操作に異なる時間を費やすという事実により可能です。 この違いは最適化によって増幅されます。プロセッサーは最大限に最適化するように「シーク」し、その結果、一部の操作は理論的に予想されるよりもはるかに高速に実行できます。



ご存知のように、RSAアルゴリズムの基礎は（そしてDiffie-Hellmanも同じです）、累乗法で累乗する操作です。 次の表記を使用することをお勧めします。



m-プレーンテキスト（ メッセージから）

c-暗号（暗号から）

{e、n}-公開キー（ 暗号化から-暗号化から取得）

{d、n}-秘密鍵（ 復号化から-復号化中に取得）

w-キーの幅 （ widthから）

d [i]-キーのi番目のビット



次に、復号化プロセスは次のようになります。

m = c^d mod n





ここで、nは公開キーの一部であるため、公開されており、cはデータチャネルをリッスンすることで取得できます。 私たちの目標はdを見つけることです。



この数式を計算するためのさまざまなアルゴリズムがあります。「額」を計算するのは費用がかかりすぎるからです。 暗号デバイスが、バイナリ露出アルゴリズムと呼ばれることの多い最も単純な高速累乗アルゴリズムを使用していると仮定します。または、外部ソースの場合のように、二乗と乗算または累乗を使用します。 彼の擬似コードは次のとおりです。

 int squareAndMultiply(c, d, n) { R = array(0..w-1) S = array(0..w-1) s(0) = 1 for (k = 0, k < w, k++) { if (d[k] == 1) R(k) = (s(k) * y) mod n else R(k) = s(k) s(k+1) = (R(k) ^ 2) mod n } return R(w–1) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

明らかに、最初のケースではプロセッサが乗算を実行し、2番目のケースでは割り当てのみを実行するため、キーのゼロビットの反復は単一ビットの場合よりも時間がかかりません。 squareAndMultiply関数の実行時間を測定することにより、キー全体を計算する方法を示します。 正確な式はありません;一般的な意味を説明します。

Kosherが提案する方法は、最初にビット0、次にビット1などのキービットを繰り返し計算することで構成され、そのような各反復には次の特性があります。

• 一部のビットはすでに計算されています（これが最初の反復の場合は何もありません）
• 検査中の現在のビットを含む残りのビットは不明ですが、それらの値は均等に分布しています（そうでない場合は、キーの生成に使用される乱数センサーをコピーする必要があります）

各反復で、ハッカーは多数の測定を行います。それぞれの目的は、3つの値を取得することです。

1. 合計関数実行時間
2. システムが既知のキービットを処理するのにかかる時間
3. アルゴリズムの操作ごとの時間（s（k）* y）mod n

パラメーター1は測定するのが最も簡単で、入力に暗号文を入力します。2と3はより困難ですが、デバイスの物理的な実装の機能を知っている場合、または少し「分析する」場合は現実です。 その場合、テストビットに続くすべての不明なビットの処理にかかる時間は次のようになります。

• 学習済みビット= 0の場合、 T = T1-T2
• 学習済みビット= 1の場合、 T = T1-T2-T3

調査中のこのビットに対して多くの測定を行い、T値の「ヒープ」全体を蓄積した後、条件付き確率式を使用して、このビットがそれぞれ1および0である確率を計算できます。



タイムアタックの最も単純なべき乗アルゴリズムを見てみました。 現代の暗号システムでは、めったに使用されず、代わりに、より最適な方法が使用されます。 これは通常、中国の剰余定理、Montgomeryアルゴリズム、またはKaratsubaアルゴリズムに基づくアルゴリズムです。 しかし、これらの「高度な」アルゴリズムでさえ、純粋な形で適用された場合、一時的な攻撃を受けやすくなります。これは、OpenSSLサーバーに対する攻撃の成功によって証明されました。

OpenSSLサーバーへの攻撃

当初、一時的な攻撃の運命はハードウェアデバイスのみであると考えられていました。たとえば、ハッカーはスマートカードを受け取り、センサーとデバイスでそれをハングさせ、その後、秘密キーを抽出します。 しかし、スタンフォード大学のDavid BrumleyとDan Boniが示したように、ソフトウェアは一時的な攻撃、特にOpenSSLストックライブラリバージョン0.9.7を使用してSSL接続を受け入れるWebサーバーの影響を受けます。 そして、これは典型的なサーバーが多くの並列プロセスを実行し、サーバーへのアクセスのチャネルも貢献するという事実にもかかわらずです。 ただし、次の3つの成功した攻撃オプションが作成されました。

1. ローカルネットワーク経由でアクセス可能なApache Webサーバーに対するクライアント攻撃。 確信を高めるために、クライアントとサーバー間のチャネルには複数のルーターとスイッチが含まれていました
2. 両方が同じマシン内で実行されている間に、あるプロセスから別のプロセスへの攻撃
3. 隔離された仮想マシンに秘密キーが保存されている分散キーストレージシステムに対する攻撃。 ここでは、Webサーバー自体はデータを復号化しませんが、キーマシンに要求を行います

SSL / TLSは、RFC 6101（SSL v3.0）、2246（TLS v1.0）、4346（TLS v1.1）、5246（TLS v1.2）および6176（TLS v2.0）で詳細に説明されているため、攻撃の標的となる部分に焦点を当てます。 そのため、一般的なハンドシェイクには次の手順が含まれます。

1. クライアントは、28バイトの乱数とサポートされている暗号のリストを送信するClientHelloメッセージを送信します
2. サーバーはクライアントに類似したServerHelloメッセージを送信します
3. サーバーは証明書とともに証明書メッセージを送信します
4. サーバー証明書を受け取ったクライアントは、サーバー証明書をサーバー証明書から抽出し、48バイトの乱数で暗号化し、 ClientKeyExchangeメッセージでサーバーに渡します。
5. サーバーは秘密鍵でクライアントの乱数を解読し、その後、相互マスター鍵が計算されます

節4では、ブロックはPKCS＃1標準（タイプ2）に従ってフォーマットされていることに注意してください。

  [0x00] [0x02] [パディング文字列] [データ] 

、その後暗号化されます。



攻撃の繰り返しは、暗号化されたブロックとしてサーバーにテストデータを送信することです。 復号化後、サーバーはデータがPKCS＃1に従ってフォーマットされていないことを自然に発見します。 この段階でハンドシェイクが一時的に中断されると、脆弱性（攻撃はBell LaboratoriesのDanel Bleichenbacherによって示されました）が開かれるため、最新のSSL / TLS実装はエラーがないことを「ふり」してハンドシェイクを続行します。 その結果、クライアントとサーバーは、次のメッセージでポップアップする異なるマスターキーを計算します-とにかく、クライアントはアラートメッセージを受信し、接続が中断されますが、これはあまり興味がありません。 主なことは、 ClientKeyExchangeを送信してからサーバーから応答を受信するまでの時間が測定されることです。 ここで、 N = p·q



はRSAモジュールであり、秘密および開指数は関係d·e = 1 mod (p-1)(q-1)



によって関連付けられていることを思い出してください。 そのため、一連の測定の後、ビットごとにqを復元することができるため、秘密鍵を見つけることができます。 そのような奇跡はどこから来たのですか？ 正確な証明を得るには、この記事の範囲外の数式を多数提供する必要がありますが、代わりに、分析の基礎となる一般原則を説明します。 それらの2つがあります。



まず、露出モジュロのOpenSSLは、前述のバイナリアルゴリズムを使用しますが、多くの最適化が行われています。 まず、 中国の剰余定理を適用すると、問題m = c^d mod N



2つの副問題m1 = c1^d1 mod p



とm2 = c2^d2 mod q



に分割され、その後、2つの数値m1



とm2



から、特別な式m



次に、アルゴリズムで使用されるモジュロ乗算は、モンゴメリー法によって最適化されます。 この方法の本質は、元のモジュールの計算から離れて、2次に等しいモジュールを計算することです。これは、プロセッサにとってはるかに高速です。 最初に、両方の因子が特別なモンゴメリー形式に変換され、次に素早い乗算が行われ、その後、結果が通常の形式に変換されます。 すべてうまくいきますが、2000年にドイツのWerner Schindler教授g



、 g



q



倍数に近いほど、アルゴリズム全体に時間がかかることを発見しました。 最初の原理は次のとおりです。モンゴメリー法の時間を測定することにより、 g



q



、 2q



、 3q



などにどのように近いかを結論付けることができます。



どうぞ 最も簡単な乗算（モジュロを使用しない）は、2つの方法でOpenSSLに実装されます：従来の方法とKaratsubaメソッド 。 通常の方法の複雑さはO(n·m)



で推定されます。ここで、mとnは倍数のサイズです。 ソビエトの科学者A. A. A.カラツバは、最初に複雑度O(n^1,58)



の高速乗算の方法を発明しました。 これは、乗数が同じサイズのときにOpenSSLが使用するものです。 2番目の原則は、これから得られます。gがqの倍数より少し小さい場合、高速な方法が使用され、少し大きい場合、より多くの時間がかかります。



このOpenSSLに対する攻撃の作成者は、約100万のリクエストで1024ビットキーを見つけるのに十分であり、約2時間かかったことを実証することができました。 しかし、急いでパニックにならないでください。 バージョン0.9.7b以降、OpenSSLには一時的な攻撃に対する保護が含まれています。 防御は、復号化操作自体の前x = r^e · · mod N



の無駄な計算にあります。ここで、rは乱数、eは秘密の指数、cは暗号化されたテキストです。 この操作により、ランダムな遅延が発生し、キー情報が副作用に「漏洩」することはありません。 保護のコストは、2〜10％のパフォーマンス損失です。

パワー攻撃

副作用に対する別のクラスの攻撃、エネルギー消費に対する攻撃に移りましょう。 これらの攻撃は、実際にはハードウェア暗号化モジュールにのみ適用でき、モジュールが実行する機能をより隔離し、狭めるほど、攻撃は成功します。 明らかに、プロセッサによって実行される異なる命令は異なるエネルギー量を消費しますが、これは最終的にスイッチングトランジスタの数によって決まります。 （物理学の過程から、MOSトランジスタはスイッチング時に電流を消費し、静止時の電流は無視できることを知っています。これはTTLトランジスタについては言えません）。 したがって、消費チャートで指示または指示のグループを特定できます。 しかし、同じコーシャは、スマートカードの消費グラフを分析することで、秘密キーを抽出できることを示しました。



これは、1ブロックのDES暗号化の消費グラフです。初期順列、16の暗号化ラウンド、および最終順列が表示されます。



そして、これが第2ラウンドと第3ラウンドの詳細なスケジュールです。





消費攻撃は、一般に単純および差分 （SPA、単一電力解析、DPA、差分電力解析と略記）に分類されます。 上記のようなチャートはSPA攻撃で分析されます。主な目標は、チャートの一部を実行された命令または機能にマップし、何らかの方法でデバイスレジスタに表示される値を決定することです。 SPA攻撃は、デバイスの内部実装に関する詳細情報があることを前提としています。 一方、DPA攻撃は、複数の測定結果の統計分析に基づいています。 たとえば、Kosherによって記述されたDESスマートカードに対する古典的な攻撃は次のようになります。

1. 最後の数ラウンドのエネルギー消費は1000 DES暗号化で記録され、各ラウンドでは暗号化の結果も記録されます
2. このような各暗号化のスケジュールは100,000の等しいセグメントに分割され、各セグメントには電力消費が割り当てられます
3. 結果のマトリックス1000 x 100000は統計的方法で分析され、測定期間全体を通して変化しなかったキーを見つけます。 （正確なアルゴリズムについては、読者は元のソースを参照することをお勧めします。habraの記事の形式は、複数階の数式をレイアウトするのにあまり便利ではないためです）

対抗

副作用に対する攻撃のいくつかのオプションを検討しました。 世界中の人々は、暗号システムを設計するとき、そのような攻撃は開発段階でも考慮に入れなければならないことに気付きました。 ここで、彼らはいくつかの方向に行動します：

• 読み取りサイド情報の妨害。 デバイスへの物理的なアクセスを妨げない限り、非常に限られた手段。 他の場合では、ハッキングは通常、データ収集のためのより高価な機器に帰着し、その価値がハッキング自体の価値を超える場合、目標は達成されます
• 漏洩信号へのランダム干渉の導入。 これはすでにより効果的な手段ですが、落とし穴もあります。 まず、コンピューターシステムでランダムデータを取得すること自体が問題です。それをどこで適切な量で取得するかです。 干渉が「完全ではない」ランダムな場合、パターンを計算でき、有用な信号からノイズをさらに分離できます。 第二に、「良い」ランダムノイズであっても、ハッカーは削減アルゴリズムを見つけることができ、収集するデータが多いほど、成功の確率が高くなります。
• システムを決定論的にする試み。 たとえば、すべての操作に同じ時間がかかるようにすると、時間に対する攻撃は役に立たなくなります。 プロセッサとコンパイラの最適化がアリーナに入り、アクセス時間が異なる複数レベルのキャッシュメモリが存在するため、これも容易ではありません。これらはすべてクラッカーの手に渡ります。
• 最初はサイドチャネルを介したリークに対して耐性のある暗号化アルゴリズムとプロトコルを設計することが、最も信頼できる対策です。 たとえば、そのようなアルゴリズムを適用して特定の式を計算します。その実行時間は、入力データのビット深度、ゼロまたは1の数、または引数の他のプロパティに依存しません。

副作用攻撃の設計は、多くの科学論文の主題でした。 そして、古い暗号アルゴリズムのみがこれらの攻撃の対象であると考えてはいけません：RSA、DES、Diffie-Hellman。 AESおよび楕円曲線のアルゴリズムから「リーク」の証拠がすでにあります。 このすべてを1つの記事で説明するのは非現実的です。 私の仕事は、読者がこの魅力的なトピックを掘り下げることだけです。

もっと深くしたい人のために

• 電力差解析および関連する攻撃の概要。 ポール・コッチャー、ジョシュア・ジャッフェ、ベンジャミン・ジュン
• Diffie-Hellman、RSA、DSS、およびその他のシステムの実装に対するタイミング攻撃。 ポール・C・コッチャー
• リモートタイミング攻撃は実用的です。 デビッド・ブラムリー、ダン・ボネ
• RSAに対するタイミング攻撃。 マーク・ファン・カイク
• 製品暗号のサイドチャネル暗号化。 ジョン・ケルシー、ブルース・シュナイアー、デビッド・ワグナー、クリス・ホール
• DPA攻撃とSボックス。 エマニュエル・プルーフ