MICRO 51 - 最優秀論文はLLC経由の情報リーク防止技術が受賞

暗号化には、次の図に示す40bitのブロック暗号を使った。40bitの暗号はそれほど強度は高くないが、この用途ではセットをバラまくのが目的で、攻撃者がELAを読むことはできないので、暗号が解読されることは考えにくい。

キャッシュのアクセス時間に直接影響するので、暗号化の速度が速いことも重要であり、次の図に示すLow-Latency Block Cipher(LLBC)を使った。この暗号化は4段のFeistel Networkを使っている。この回路には24段のXORネットワークがあり、暗号化は2サイクル程度の遅延時間で行うことができる。

なお、Fと書かれた部分の中のS-Box、P-Boxの内部接続はランダムに決められ、この図の4つのFの中身はそれぞれ異なっている。

Low Latency Block Cipherは4段にFiestel-Networkで作られる。暗号化には24段のXORを通過し、2サイクルで暗号化ができる。F部の内部はランダムに決められ、4つのF部はそれぞれ異なる

これでキャッシュラインとの対応を暗号化してランダムにすることができるが、キャッシュライン対応が固定されている場合は、次の図のようにすると、比較的、短時間で暗号を破ることができる。

まず、衝突ミスが起こるようなキャッシュラインパターンを作って置く。そこから1ラインを除いて衝突が起こるかどうかをチェックし、衝突が起きなくなれば、そのラインは衝突を起こすセットに属するラインであり、衝突が起き続ければそのラインは衝突セットには含まれないことが分かる。

これを繰り返すと暗号を破ることができ、8MBのLLCの場合、22秒で暗号を破ることができてしまうという。

暗号化しても、キャッシュラインの対応が固定である場合は、順番に虱潰しに衝突が起こるキャッシュラインを調べていけば、衝突セットを見つけて、暗号を破ることができてしまう

この問題を解決するため、「CEASER(CEASE with Remapping)」を考えた。CEASERでは、N回のメモリアクセスを1つのエポックとし、エポックごとに暗号化に使用するKeyを変更してキャッシュラインの対応を変更してしまう。

原理的には、1つのKeyを1エポックの間、使って、次のKeyに切り替えるという方法で、暗号が破られてしまうのを防ぐことができるが、エポックが終わるとすべてのキャッシュラインをメモリに書き戻し、Keyを切り替えて再度読み込むというバルクで処理を行うのは性能の負担が大きく大変で、下側の図のように、CurrKey(現在のKey)とNextKey(次のKey)を持ち、キャッシュラインごとにNextKeyを使うキャッシュラインを増やしていくという方法が良い。

エポックごとにKeyを変えてキャッシュ全体をリマップするバルク方式は大変で、CurrKeyとNextKeyを持ち、エポックごとに1キャッシュラインずつ、順番にリマップを進めていく方式の方が良い

Remap Rateを1%にセットした場合は、キャッシュがW-wayの場合は100×W回のキャッシュアクセスを行うのが1エポックとなる。そして、エポックが終わるとSetPtrで指されたセットのリマップを行うというやり方でNextKeyを使って暗号化されたラインを増やしていく。

各キャッシュラインに必要となるのは、すでにNextKeyでのリマップが行なわれたかどうかを示す1bitだけで、ハードウェア負担は小さい。

CEASERでは、エポックが終わると、SetPtrで指されたCurrKeyで暗号化されているキャッシュラインをNextKeyで暗号化されたアドレスにリマップする。衝突関係がダイナミックに替わるので、暗号の解読が難しくなる

8MBのLLCでリマップなしのCEASEの場合は22秒で解読されてしまうが、リマップでマッピングが変わってしまうと攻撃者がマッピングを理解するのに使える時間が短くなり、暗号を破るのが難しくなる。

1エポックに1キャッシュラインずつのリマップを行うと、1エポックの長さが100アクセスとすると同一セットに入るキャッシュラインを見つけて暗号を破るには100年以上の時間が必要になる。リマップの頻度を減らして、2000アクセスに1回のリマップにすると暗号解読時間は37年に短縮される。

次の表の右の欄は、8MBのLLCが1MBバンク8個で作られており、アタックを1バンクに集中した場合で、全体に暗号を破るのに必要な時間は短くなるが、この場合でも100アクセスに1回のリマップであれば暗号を破るには100年以上の時間が掛かる。

固定的なマッピングの場合は8MB LLCの場合で22秒、1MBのバンクに攻撃を集中した場合は0.4秒で暗号が破られるが、Remap-Rate 1%(100アクセスに1回の1キャッシュライン)にリマップを行えば、暗号を破るには100年以上かかり、現実的には破ることは難しい

次の図にCEASEとCEASERの性能的なオーバヘッドと記憶量のオーバヘッドを示す。性能は、Rate-34とMix-100と両者を合わせたALL-134で比較しており、CEASEの性能は保護なしの場合と比べて99.2%～99.7%となっている。そして、CEASERの性能は98.9%～99.2%となっている。

一方、CEASERを実装するのに必要な記憶素子は、2個のLLBC暗号化のKeyを記憶する20バイトのメモリと2バイトのSPtr、2バイトのAccess Counterで、合計24バイトである。大容量でチップの専有面積も大きいLLCに対する攻撃を防ぐコストとしては、安いものといえる。

CEASEとCEASERの性能オーバヘッドとCEASERのハードウェアオーバヘッド。性能オーバヘッドは1%程度、ストレージのオーバヘッドは24バイトで、どちらも無視できる程度の軽微なオーバヘッドである

まとめであるが、この論文は、LLCをコンフリクトベースの攻撃から守る実用的な方法を提案している。

このCEASERは年単位の攻撃に耐える堅牢性を持ち、性能低下は1%程度と無視できる程度である。また、わずか24バイトのレジスタを追加するだけで済み、経済的である。回路の変更はLLCの内部で閉じており、キャッシュの外部から見たインタフェースや働きには変更は必要としない。そして、OSのサポートも不要である。

ということで、LLCをコンフリクトベースの攻撃から守る手段として、実装が容易で、十分な堅牢性をもつ実用性の高い解になっている。