AESに対する相関電力解析を勉強する
これはkatagaitai CTF勉強会 #10で喋った内容の一部を要約したものです。 勉強会のスライドはこちら。
www.slideshare.net
概要
- AESの相関電力解析を勉強
- ジッターの排除方法を勉強
- RHme3 Tracing the tracesを解く
電力解析
一般的に暗号システムの評価はその入力及び出力を攻撃者が得られる仮定のもとで、保護資産 (平文・鍵 etc.) が適切に保護されているかを評価します。選択平文攻撃や選択暗号文攻撃などがこれに該当します。これは暗号システムが入力をどのように出力に変換しているかの情報は全く攻撃者は得られません。すなわち攻撃者にとって暗号システムがブラックボックスであることを意味します。
ただ、実際に攻撃者にとって暗号システムはブラックボックスなのでしょうか？残念ながら、違います。多くの場合、暗号システムはコンピュータに実装され、コンピュータは暗号の処理を行う際に電力を消費します。負荷がかかる演算が行われたら、メモリの内容を多く書き換えたら、それだけ電力が多く消費されます。つまり、演算処理やメモリの情報は消費電力という形で外部に現れてしまいます。暗号システムの入出力に加え、消費電力を解析することで、保護資産を手に入れようとすることを電力解析と呼びます。
CTFと電力解析
一般にCTFであまり出題頻度が高いとは言えない電力解析問ですが、最近流行りのIoT系のCTF*1の暗号問では頻出問となっています。というかIoT系のCTFでは、現在のところ暗号問はホワイトボックス暗号か電力解析のほぼ２択となっている気がします*2 。
ということで一般のCTFではあまり出題されませんが、IoT系CTFの暗号問では頻出となる電力解析問をRHme3のTracing the tracesを題材に勉強していこうと思います。最近流行りのIoT*3の波に乗りたい場合は習得必須ですよ。
相関電力解析
電力解析には単純電力解析 (SPA : Simple Power Analysis)、差分電力解析 (DPA : Differential Power Analysis)、相関電力解析 (CPA : Correlation Power Analysis) など様々な手法が存在します。CTFではCPAが出題されることが多いので、ここではCPAを解説します。
コンピュータのデータはメモリやレジスタといった記憶装置に保存されます。これらメモリやレジスタはその内部に電荷を保持しているかいないかで、保存しているビットが"1"か”0"かを判断します。そしてその電荷を保持する性質上、ビットを反転させる（＝内容を書き換える) 際に大きく電力を消費します。つまり一回のデータ変更で書き換えるデータの量が多ければ多いほど、その消費電力は大きくなります。
一般的なコンピュータシステム同様、多くの暗号システムでも、さまざまな入力が記憶装置に格納され、処理され、格納され、処理されを繰り返し、最終的にシステムの出力である暗号文を生成します。その間、記憶装置では各処理ごとに入力と出力の差分（＝ハミング距離）だけ、レジスタの保存しているビットを反転させます。この際、処理の入力と出力の差分が小さければ消費電力は小さく、大きければ消費電力もまた大きくなると考えられます。すなわち、処理の入出力のハミング距離と消費電力は相関関係を持ちます。
これら入力出力のハミング距離とその消費電力の相関関係を利用して、暗号を分析する攻撃が相関電力解析です。
このような線形な相関はピアソンの相関係数で表すことができます。ハミング距離と消費電力が比例の関係に近ければ近いほど、相関係数は1に近づきます。
AES
AESのラウンド処理は下記の図のような処理を組み合わせて実施されます。今回は一つ一つの処理はあまり重要ではありません。重要なのは、下記二点です。
- AESではAddRoundKeyとSubBytes処理は8bitのテーブル (word) 単位で処理
- 最初のラウンドで利用される鍵は128ビット鍵がそのまま利用される (Key Scheduling Algorithmの影響を受けない)
つまりAESの最初のラウンド処理では、AddRoundKeyとSubByte処理に関しては8ビット単位で16個に秘密鍵が分割されて処理されることになります。
AESの相関電力解析
攻撃者は次の能力を持っていると仮定します。
任意の平文を暗号化可能 (選択平文攻撃)
AESの最初のラウンドのSubBytes処理の消費電力を測定可能
ただAESの暗号鍵を直接知ることはできません。 攻撃者の手元に機器があるような場合を想定すると、これら条件を満たすことは現実的にもそう難しくなさそうです。
攻撃者は次のようなステップで攻撃を実施します。
Step 1 : 準備
まず準備として、攻撃者は大量の平文を暗号化し、そのAESの最初のラウンドのSubBytesの消費電力を計測し、そして平文と消費電力を紐付けて保管します。 これにより攻撃者の手元には平文と消費電力のリストができました。
Step 2 : 鍵候補の選択
次に攻撃者は8ビット*16個に分割した秘密鍵から8ビット鍵K[x]を選択します。ここでxは0から15の任意の自然数です。そして、その28個のK[x]の候補から1つ選択します。
Step 3 : SubBytesの計算
選択した8ビット鍵とStep 1で保管していた平文を用いて、最初のラウンドのSubBytesの出力を対応する8ビット分だけ計算します。ここでSubBytesの出力はS-Box[選択した8ビット鍵⊕対応する平文8ビット]となります。
Step 4 : 相関係数の導出
Step 3で計算したSubBytesの出力と平文のハミング距離を計測し、そしてそのハミング距離に応じて、平文と対応する消費電力をグループ分けします。例えばハミング距離が1だったら対応する消費電力はグループ1に分類し、ハミング距離が5だったら対応する消費電力はグループ5に分類する、という具合です。そしてこれらグループの消費電力とハミング距離の相関係数を計算します。
Step 5 : 鍵の導出
もしStep 2で選択した鍵候補が正しければ、Step 3で計算したSubBytesの出力もまた正しいはずです。そのため、ハミング距離と消費電力には相関が生じるため、相関係数は比較的1に近い値となるはずです。 しかし、Step 2で選択した鍵候補が誤っていればどうなるでしょうか。Step 3で計算したSubBytesの出力もまた誤ったものとなり、入力と出力のハミング距離も誤ったものとなるはずです。結果として、ハミング距離と消費電力の相関は小さくなり、相関係数は比較的0に近い値となるはずです。つまり導出した相関係数が1に近ければ、Step 2で選択した鍵候補は正しく、相関係数が0に近ければ、鍵候補は誤っているとみなすことが可能です。これにより鍵の8ビットを特定できます。
これを繰り返すことで128ビット鍵をすべて特定することが可能です。
RHme3 Tracing the traces
ということでモノは試し、さっそく問題を解いていきましょう。題材はRHme3のTracing the tracesです。 ちなみに問題は下記を参照のこと。
初動調査・方針
与えられたファイルは拡張子がmatだがmatlabで開こうとするとエラー。 先頭箇所を見ると下記記述あり。
# Created by Octave 4.0.3, Fri Aug 04 14:04:39 2017 CEST <andres@kali-andres>
Octaveというアプリケーションで作成されているみたいです。私は知らなかったのですが、調べるとmatlabのalternativeとして広く利用されているらしいです。
早速インストールして実行して、そしてファイルを読み込んで、matlab形式で保存し直しましょう。
$ octave octave:1> load traces.mat octave:2> save -mat traces.2.mat
このファイルを読み込むと、inoutとsamplesという2つのテーブルがあることがわかります。 問題文からinoutがinput/output data、samplesがそれぞれの消費電力測定値と思われます。
試しにSamplesをいくつかプロットしてみましょう。
import scipy.io as sio import matplotlib.pyplot as plt input = sio.loadmat("traces.2.mat") for x in input[‘samples’]: plt.plot(x) plt.show()
プロットされた消費電力波形はいろんな波形が重なり合っていてきれいな波形になっていません。 これはそれぞれの波形の測定したタイミングが完全に一致できておらず、時間軸方向にずれ (ジッター) が生じていることが原因です。 相関電力解析をやる前にこのジッターを取り除いてやる必要がありそうです。
ジッターの排除
ジッターを排除するために、テンプレートマッチングの一種であるSAD (Sum of Absolute Difference) を利用します。 SADを利用して、ある波形から抽出点を選択し、他の波形の差分との絶対値の合計が小さくなる箇所を探索することで、ずれ幅を求めることが可能です。
ということで、最初の波形の一部を抽出点として抜き出して、100番目までの波形のずれを修正するサンプルコードです。
これを実行すると下記の結果が得られます。 左がSAD前の波形、右がSAD後です。 ジッターが低減していることがわかります。
相関電力解析！
ようやく準備が整ったので、相関電力解析をやっていきましょう。 と言っても、実施内容についてはすでに説明してしまっているので、実装するだけです。
まとめ
今回はRHme3 Tracing the tracesを題材に、AESに対する相関電力解析を勉強しました。 なんとなく雰囲気だけでも伝わったでしょうか。
え、実装がめんどくさいので、もっと簡単に解きたい？はい、私もそう思います。 ということで、次回はツールで解く方法を紹介します。
