鍵発見攻撃

鍵探索攻撃とは、暗号化技術を利用するコンピュータシステムに対する攻撃であり、コンピュータメモリまたは不揮発性ストレージから、データの復号や署名に使用できる秘密暗号鍵を探します。この用語は、一般的に、各バイトシーケンスを単純にテストして正しい答えが得られるかどうかを判断するよりもはるかに効率的にメモリを検索する攻撃の文脈で使用されます。これらの攻撃は、コールドブート攻撃と組み合わせてコンピュータから鍵データを抽出するために使用されることがよくあります。

アプローチ

シャミールとヴァン・ソメレンは、鍵発見攻撃に関する画期的な論文^[1]において、鍵発見のための2つの異なるアプローチを提案しました。統計的またはエントロピー的な鍵発見と分析的な鍵発見です。前者は暗号鍵を構成するデータの統計的特性の違いを検出することに依存し、後者は標的の鍵素材に必ず存在する特定のバイトパターンを特定し、それらのパターンを探すことに依存します。

統計上の重要な発見

一般に、ほとんどの暗号化システムでは、暗号化キーは可能な限りランダムである必要があります。ほとんどの対称暗号では、キーは完全にランダムなビットの集合にすることができ、またそうあるべきです。ほとんどの非対称暗号では、秘密キーは、一定の制約 (素数であることやグループのジェネレータであることなど) 内でランダムに選択された数値であるか、何らかの制約のある乱数の集合に基づく計算の結果です。いずれの場合も、キー マテリアルは高いエントロピーを示します。これとは対照的に、コンピューターのメモリ内のほとんどの非圧縮データは、比較的低いエントロピーを持っています。その結果、キーが生の形式でメモリ内に存在することがわかっている場合、その高いエントロピーのおかげで、キー以外のデータの背景から目立つ可能性が高く、攻撃者はメモリまたはストレージの高いエントロピーを持つ領域で一致するキーをテストするだけで済みます。

高エントロピー キーは、背景の低エントロピー データに対して視覚的に目立ちます。

ほとんどのデータの低いエントロピーと、重要なデータの高いエントロピーとのコントラストは、視覚的にも明らかです。右の図は、その例を示しています。

分析の主な発見

統計的な鍵探索は、検索に必要なメモリ量を削減するのに効果的ですが、高エントロピー領域をテストし、正しい鍵素材が含まれているかどうかを確認する必要があります。特に公開鍵暗号システムにおいては、鍵素材に必ず出現するパターンを特定し、それらのパターンが見つかる領域のみに探索範囲を限定することが可能です。

シャミールとヴァン・ソメレン^[1]は、公開鍵が既知で公開指数が小さい場合にRSA秘密鍵を見つけるためのこの解析的アプローチの一例を示した。RSAシステムでは、公開鍵は のペアであり、pとqは2つの大きな素数である。対応する秘密鍵は（あるいは場合によってはその変形）であり、これはeにdを乗じた値が1を法として等しいことを意味する。ここでφはオイラーのトーシェント関数を表し、 はnを法とする乗法群のサイズである。RSA鍵の場合： ${\displaystyle (n,e)}$ ${\displaystyle n=pq}$ ${\displaystyle (n,d)}$ ${\displaystyle (p,q,d)}$ ${\displaystyle ed\equiv 1{\pmod {\phi (n)}}}$ ${\displaystyle \phi (n)}$

${\displaystyle \phi (n)=(p-1)(q-1)=np-q+1}$

n からの値を求めることで n を因数分解することが可能となり、RSA暗号システムのセキュリティは、その困難さにかかっています。そのため、攻撃者はeとnが与えられたとしてもd を正確に特定することはできません。しかし、pとq は通常同じビット長に選ばれ、どちらもnの平方根に「近い」という知識があれば、攻撃者はdがどのような値になるかについてある程度の推測が可能です。したがって、攻撃者は以下の式を概算することができます。 ${\displaystyle \phi (n)}$

${\displaystyle \phi (n)\approx \phi '(n)=n-2{\sqrt {n}}}$

そして、この近似値は、通常、2進表現の上位半分のビットにおいては正しい。eとdの関係は、次のことを意味する。

${\displaystyle d=(1+k.\phi (n))/e}$

ここでkの正確な値は不明ですが、この事実と近似値 を用いることで、攻撃者はkの各値に対して、 dのバイナリ表現の上位半分の可能な値の集合を列挙することができます。これらのバイナリパターンは、試行的な復号化を実行するよりも桁違いに高速にテストできます。さらに、 の一般的なケースでは、が示され、これによりdの上位半分のビットを正確に決定し、直接検索することが可能になります。 ${\displaystyle 0<k<e.}$ ${\displaystyle \phi '(n)}$ ${\displaystyle e=3}$ ${\displaystyle k=2,}$

応用

キー検索攻撃は、コールドブート攻撃と組み合わせて、マシンの電源を切った後にキーを抽出するために使用されてきました。^[2] ヘニンガーとシャカムは、電源を切ったことでメモリ内のデータが破損していても、キーを抽出できることを示しました。^[3]

Nicko van Somerenは、統計的キー検索を用いて、 MicrosoftがMS-CAPIプラグインの署名を検証するために使用する署名検証キーを特定しました。これらのキーの1つが後にMicrosoftによってNSAKEYと呼ばれていたことが判明し、論争を巻き起こしました。^[4]

緩和策

鍵発見攻撃はいくつかの方法で軽減できます。分析攻撃の場合、ランダム鍵ブラインド化は、メモリ内で予想されるパターンが発見されるのを防ぐだけでなく、他の種類のサイドチャネル攻撃からも保護します。統計攻撃は、他の種類の高エントロピーデータや圧縮データをメモリに保存することで効果を低下させ、鍵素材は未使用時にはより大きなメモリブロックに分散させることで、エントロピーの一箇所への集中を軽減できます。

参考文献

1. Shamir, Adi; van Someren, Nicko (1998-01-01).保存された鍵を使ったかくれんぼ. コンピュータサイエンス講義ノート. pp.  118– 124. CiteSeerX  10.1.1.40.4467 .
2. Halderman, J. Alex; Schoen, Seth D.; Heninger, Nadia ; Clarkson, William; Paul, William; Cal, Joseph A.; Feldman, Ariel J.; Felten, Edward W. (2008-01-01). 「少なくとも忘れてはならないこと：暗号化キーに対するコールドブート攻撃」USENIXセキュリティシンポジウム.
3. Heninger, Nadia ; Shacham, Hovav (2009-01-01). 「ランダム鍵ビットからのRSA秘密鍵の再構築」Proceedings of Crypto 2009. pp.  1– 17. CiteSeerX 10.1.1.215.6281 . 
4. “Microsoft/NSA Info”. 2000年6月17日. 2000年6月17日時点のオリジナルよりアーカイブ。2016年10月12日閲覧。