ラック・セキュリティごった煮ブログ

セキュリティエンジニアがエンジニアの方に向けて、 セキュリティやIT技術に関する情報を発信していくアカウントです。

【お知らせ】2021年5月10日～リニューアルオープン！今後はこちらで新しい記事を公開します。

株式会社ラックのセキュリティエンジニアが、 エンジニアの方向けにセキュリティやIT技術に関する情報を発信するブログです。（編集：株式会社ラック・デジタルペンテスト部）
当ウェブサイトをご利用の際には、こちらの「サイトのご利用条件」をご確認ください。

デジタルペンテスト部提供サービス：ペネトレーションテスト

消費電力から機密情報を特定する方法(DPA,CPA編)

or2

こんにちは、or2です。
こちらの記事は消費電力から機密情報を特定する方法(SPA編)の続編です。
前編は見なくても問題ないですが、電力解析についてご興味があればぜひご覧ください。

今回は電力解析の一種、Differential Power Analysis(DPA)/Correlation Power Analysis(CPA)についての理論と実験結果をまとめたいと思います。
攻撃対象はAES暗号化機能を実装したATmega328Pです。
※ATmega328PはArduinoに搭載されているマイコンです。

免責事項

当記事の内容は教育・学習およびセキュリティの向上目的で執筆されており、サイバー攻撃行為を推奨するものではありません。 第三者が所有する資産に管理者の許可なく攻撃行為を行うと各種の法律に抵触する可能性があります。 当記事の内容を使用して起こるいかなる損害や損失に対し、当社は一切責任を負いません。

※当記事の検証では、自身で作成したパスワード認証ファームウェアを使用しております。当記事で紹介している手法を試行する際は、自身の所有する環境に対して実施してください。

構成

今回の実験はATmega328PにAES ECBモードによる暗号化機能をファームウェアとして実装しています。
このデバイスにUARTで平文を入力するとハードコードされている秘密鍵を利用して暗号化処理を実行し、その結果を出力するようになっています。

また、ATmega328Pはパスワード入力を検知すると特定のPinをHighにするように設計しているので、これをトリガーとして利用して消費電力の測定を開始します。
消費電力の測定はChipWhisperer Liteを使いました。オシロスコープで測定することもできます。(測定デバイスのクロック周波数に対して十分な測定能力があれば何でも大丈夫です。)
電源は安定化電源を使います。

物理配線は以下のようになります。

図1. 物理配線図

また、トレースは一貫してサンプリングレート64M samples/secで取得しているので、約15ナノ秒ごとに1点測定しています。

AES ECBモードについて

今回実装したAESは意図的にECBモードを採用しています。
細かいことは省きますが、初期化ベクトル(IV)があると消費電力から秘密鍵を推定することが出来なくなってしまうからです。

攻撃手法

今回扱う攻撃は以下の２つです。

  • DPA(Differential Power Analysis)
    • 消費電力から扱っているデータを推測する攻撃
      • デバイスが扱っているデータによって発生する消費電力の差を見る方法です
      • データによって発生する消費電力の差はかなり小さいので、ノイズの影響を大きく受けます
        • ノイズの影響をかき消すために大量の測定をして平均をとります
  • CPA(Correlation Power Analysis)
    • DPAの高効率版
      • 統計的手法(相関分析)によって測定回数を大幅に減らすことができます

まずはDifferential Power Analysis(以下DPAと略します)についての理論と実験結果を示し、次にCorrelation Power Analysis(以下CPAと略します)についても同様の内容を示していきます。

DPAについて

攻撃者が暗号化デバイスに対して自由に平文を入力し、暗号化処理中の消費電力(トレース)を取得できる場合に有効な攻撃です。
消費電力の時系列データのことをトレースと言うので、以後はこれをトレースと呼んでいきます。

この攻撃はイメージとして選択平文攻撃の攻撃フローに近い攻撃です。
選択平文攻撃は任意の平文とそれに対応する暗号文から秘密鍵を推測する攻撃ですが、DPAは任意の平文とそれに対応する暗号処理中のトレースから秘密鍵を推測します。

DPAの理論は少し複雑なので、まずはAES ECBモードについてのおさらいと、この攻撃において特に重要な概念であるハミングウェイトと仮説リークについてまとめていきます。最終的にこれらをどのように利用すれば秘密鍵の推測につながるのかを説明していきます。

AES ECBモードのアルゴリズムの復習

ここでは前提として、平文・秘密鍵を16byteとして話を進めていきます。
AES ECBモードは以下の図のような変換を何度も行って暗号文を出力します。

図2. AES ECBモードにおけるSbox処理

数学的に記述すると以下のようになります。

\begin{aligned} &C(n) = Sbox(P(n) \oplus S(n)), 0 \leqq n \leq 16 \\ &\quad C(n): 暗号文のnバイト目の値 \\ &\quad Sbox(): Sbox関数\\ &\quad P(n): 平文のnバイト目の値\\ &\quad S(n): 秘密鍵のnバイト目の値 \end{aligned}

図3. Sbox出力の計算式

DPAではSboxの出力を1byte単位で推測していくので、平文・秘密鍵の最初の1byteの変換だけを取り出して見ておきます。
また、ここでは具体的なイメージのため平文として0x23、秘密鍵として0x45を設定しました。
Sboxは基本的に固定の行列として定義されています。(具体的な値を知りたい場合はRijndael S-boxのWikiなどを参照してください。)

図4. 1byte単位でみた場合のAES ECBモードにおけるSbox処理

重要な点は、未知の値が秘密鍵だけであり、Sboxによる非線形変換が行われているということです。
DPAの観点では、AES ECBモードの理解は以上で十分です。
後はハミングウェイトと中間値の概念さえわかれば実際に消費電力から秘密鍵の推測が可能です！

ハミングウェイトについて

ハミングウェイトとは、データを2進数で表現した時、値が1のbitの数を指します。
文章で説明してもいまいち分かりにくいので8bitレジスタに格納されている2進数で具体例を示します。

図5. ハミングウェイトの数え方

ハミングウェイトが大きくなると消費電力も大きくなり、ハミングウェイトが小さくなると消費電力も小さくなるという比例関係があります。
ただし、その消費電力の差は非常に小さくノイズにかき消されてしまいます。そこで、大量のトレースを取得して平均を見ることでノイズの影響を抑えて差を観測することができます。
DPAにおいてこの点はとても重要なポイントになるので覚えておいてください。

仮説リークについて

仮説リーク(hypothetical leakage)とは、攻撃端末側で計算するSbox出力の予測値のことです(文脈によって何の予測値か変わりますが、ここではAESのSbox出力と考えて大丈夫です)。
DPAでは秘密鍵を推測するため、仮説リークを計算し、秘密鍵の推測に利用します。

Hypothetical Leakage Function: Sbox(P(n) \oplus S(n))

図6. 仮説リークの計算式

DPAのアルゴリズム

ここまででDPAを理解するのに必要な基本的な知識がそろったので、実際のアルゴリズムを示していきます。
文字だけの説明だとわかりにくいので、python的な仮想コードも用意しました。
また、ここでは簡単のため、平文・秘密鍵の先頭1byteだけを考えていきます。

まずは事前準備として暗号化デバイスに大量の平文を入力し、その時のトレースを取得します。
今回の環境ではトレース数1000個ではうまくいかず、10000個にしたところうまくいきました。

次に仮説リーク関数を用意し、先ほど入力した平文と推測鍵guessKeyで仮説リークHypotheticalLeakageを計算します。
推測鍵とは、秘密鍵の1byteを適当に設定したものです。ここではguess key = 0x00と仮置きして考えていきます。

次に仮説リークの先頭1bitが0 or 1確認してトレースを振り分けます。
先頭1bitが0である場合はzero_tracesグループに、1である場合はone_tracesグループに分けていきます。
さらに各グループでトレースの平均の絶対値をとり、差分トレースdiff_traceを計算します。

#推測鍵の設定
guessKey = 0x00

#先頭1bitによるグループ分け
zero_traces = []
one_traces = []

##plains, traces: 暗号デバイスに入力した平文と取得したトレースのリスト
for plain, trace in zip(plains, traces):
  #仮説リークの計算
  HypotheticalLeakage = Sbox(plain[0] ^ guessKey)

  if HypotheticalLeakage & 0x01:
    one_traces.append(trace)
  else:
    zero_traces.append(trace)

#グループ分けしたトレースの平均の絶対値の計算
avg_one_trace = absolute(average(one_traces))
avg_zero_trace = absolute(average(zero_traces))

#トレース間の差分計算
diff_trace = avg_one_trace - avg_zero_trace

図7. DPAの仮想的なPythonコード

この時、推測鍵が正しい場合は仮説リークも正しい値になっているので、先頭1bitの違いによるグループ分けが正しく行われます。
bit0のグループとbit1のグループでは、仮説リークにハミングウェイト1の差ができるので、あるタイミング(Sboxが出力を出すとき)で消費電力の差が発生します。
逆に推測鍵が間違っている場合は仮説リークによって計算した値は間違っているので、bit0/bit1のグループ間にハミングウェイトの差が(ほとんど)ないので、消費電力の差は発生しません。

ここでは推測鍵を0x00で考えていましたが、ほかの値0x00-0xFFでも同じことをやって消費電力の差を確認します。各推測鍵の差分トレースの中でも大きな消費電力の差が確認できれば、その推測鍵が正しい秘密鍵である可能性が高いです。
また、攻撃対象の秘密鍵も1byteと仮定していましたが、1byte目が終わったら2byte目、次は3byte目...と拡張できます。

DPAの実験

上記のアルゴリズムを実装し、各推測鍵毎に最も大きな消費電力の差が発生しているポイントを確認した際の結果の一部を以下に示します。
ちなみに今回設定した秘密鍵はThisIsSecret!!!!([0x54, 0x68, 0x69, 0x73, 0x49, 0x73, 0x53, 0x65, 0x63, 0x72, 0x65, 0x74, 0x21, 0x21, 0x21, 0x21])という値です。
トレース数は10000です。

まずは0x00-0x1Fまでの推測鍵を試して、差分トレースの中で最も大きな差を抽出しています。
差は大体0.01前後であることが確認できます。

図8. 推測鍵0x00-0x1Fにおける最も大きな消費電力の差分

次に推測鍵を秘密鍵の1byte目と同じ0x54に設定した場合の差分を見てみます。
0.02以上の差が出ており、ほかの値よりも明らかに大きいことがわかります。

図9. 推測鍵0x54におけるもっとも大きな消費電力の差分

実際にトレースをプロットしてみて、推測鍵が正しい場合と間違っている場合を比較してみます。
下のプロットは正しい推測鍵0x54を選択したときのプロットです。
オレンジのプロットが仮説リークの1bit目が0のトレース、青のプロットが1のトレースです。
※横軸が時系列に比例した値(約15ナノ秒間隔)、縦軸が消費電力に比例した値です。

図10. 推測鍵0x54における平均トレースの比較

次のプロットは間違った推測鍵0x00を選択したときのプロットです。

図11. 間違った推測鍵0x00における平均トレースの比較

オレンジのプロットと青のプロットを比較すると、正しい推測鍵を選択した場合の図10のほうが図11よりも差分が大きく出ていることが確認できます。
あとは残りの秘密鍵に対しても同じ処理を繰り返していきます。

鍵を構成する16個のbyteに対して試した結果が以下です。
Subkeyの次の数字が秘密鍵のインデックス、most likelyの次の16進数が最も大きな差分がでた推測鍵を示しています。

図12. DPAによる秘密鍵全体の推測

秘密鍵全体の特定に成功しました。

CPAについて

CPAはDPAを効率的にした攻撃方法です。
今回の環境ではトレース数200程度で正しい秘密鍵を推測できました。

DPAと大まかな流れは共通していますが、仮説リーク(ハミングウェイト)の使い方と秘密鍵の特定の仕方が異なります。
以下にDPAとCPAの違いをまとめました。

  • 仮説リークの使い方
    • DPAでは仮説リークで計算した1byteの先頭1bitのハミングウェイトをもとに秘密鍵を推定していた
    • CPAでは仮説リークで計算した1byte全体のハミングウェイトに拡張して秘密鍵を推定する
  • 秘密鍵の特定の仕方
    • DPAでは仮説リークの先頭1bitをもとにトレースを2つのグループに分類し、平均・絶対値・差分という初歩的な演算を経てトレースをグループ分けて差分トレースから秘密鍵を推定していた
    • CPAでは仮説リークのハミングウェイトとトレースの相関係数(統計的な処理)を計算することで秘密鍵を推定する

CPAでは新しく相関係数を使うのですが、何に使うのかについての説明から入っていきます。

相関係数

相関係数とは、2つのデータの間にどれだけ強い相関があるかを示す値のことです。
詳細な話は統計の世界に入ってしまうのでここでは割愛し、計算式だけ示しておきます。気になる方は調べてみてください。

\begin{aligned} &r_{ij} = \frac{{\Sigma(x_i - \bar{x})}{\Sigma(y_j - \bar{y})}}{\sqrt{{\Sigma(x_i - \bar{x})}^2}\sqrt{{\Sigma(y_i - \bar{y})}^2}} \\ &\quad\bar{x}: \frac{1}{n}{\Sigma{x_i}} \\ &\quad\bar{y}: \frac{1}{n}{\Sigma{y_i}} \end{aligned}

図13. 相関係数の計算式

DPAでは仮説リークで計算した1byteの先頭1bitのハミングウェイトをもとに秘密鍵の推測を行いましたが、CPAでは相関係数を計算することで仮説リークの1byteすべてのハミングウェイトを利用できるようになります。

具体的には、相関係数で扱うデータの一つをハミングウェイト、もう一つをトレースとしてやって、ハミングウェイトとトレースの相関を計算します。
ここで一つ注意点があります。トレースは消費電力の時系列データなので、トレースそのものを使って相関係数を計算することはできません。
なので、トレースの任意のタイミングの消費電力に対して相関係数を計算します。(すべてのtに対する相関係数を計算する)
式にすると以下のような感じです。

\begin{aligned} &r_{ij}(t) = \frac{{\Sigma(hw_i - \bar{hw})}{\Sigma(trace_j(t) - \bar{trace(t)})}}{\sqrt{{\Sigma(hw_i - \bar{hw})}^2}\sqrt{{\Sigma(trace_j(t) - \bar{trace(t)})}^2}} \\ &\quad hw_i: i番目の仮想リークのハミングウェイト \\ &\quad trace_j(t): j番目のトレースの時刻tの消費電力 \\ &\quad \bar{hw}: 仮想リークのハミングウェイトの平均(\frac{1}{n}{\Sigma{hw_i}}) \\ &\quad \bar{trace(t)}: トレースの平均(\frac{1}{n}{\Sigma{trace_j(t)}}) \end{aligned}

図14. ハミングウェイトとトレースの相関係数の計算式

相関係数を計算することで、あるタイミング(時間)の消費電力とハミングウェイトの相関を見ることができます。
ハミングウェイトについてで説明した通り、ハミングウェイトと消費電力には比例関係があります。
このことから、推測鍵を正しく設定できれば仮説リークから正しいハミングウェイトを計算でき、トレースとの間に相関が見えることが期待できます。

CPAのアルゴリズム

pythonの仮想コードを示します。

#リストの用意
HypotheticalLeakages = []
HammingWeights = []
CorrelationCoefficients = []

#推測鍵の設定
guessKey = 0x00

#秘密鍵1byte目に対する仮説リークの計算
##平文のリストをすべて仮説リークに変換する
##plainsとHypotheticalLeakagesは複数の要素を持つリストであることに注意
HypotheticalLeakages = [Sbox(plain[0] ^ guessKey) for plain in plains]

#仮説リークのハミングウェイトの計算
##HammingWeight()メソッドは引数のハミングウェイトを返す
##HammingWeightsは複数の要素を持つリストであることに注意
HammingWeights = HammingWeight(HypotheticalLeakages)

#相関係数の計算
##CorrelationCoefficient()メソッドは2つの引数を受け取り、それらの間の相関係数を計算する
##traces, HammingWeightsは複数の要素を持つリストであることに注意
CorrelationCoefficients = CorrelationCoefficient(traces, HammingWeights)

図15. CPAの仮想的なPythonコード

相関係数の計算については少し難しいと思いますが、DPAのアルゴリズムより行数が少なくシンプルになりました。(関数を使っているだけなのですが)

CorrelationCoefficientsにトレースのあるタイミング(時間)ごとのハミングウェイトと消費電力の相関係数が格納されます。
Sbox処理に関係ないタイミングの相関係数は0に近い値が、Sbox処理に関係するタイミングでは相関係数は大きな値になるはずです。

CPAの実験

今回の秘密鍵もThisIsSecret!!!!([0x54, 0x68, 0x69, 0x73, 0x49, 0x73, 0x53, 0x65, 0x63, 0x72, 0x65, 0x74, 0x21, 0x21, 0x21, 0x21])に設定しています。
まずは最初の1byte0x54の推測からやっていきます。
トレース数は1000個です。

推測鍵0x01-0x1Fを設定したときの最大の相関係数が以下です。
おおよそ0.1前後であることがわかります。

図16. 推測鍵0x00-0x1Fにおける最も大きな相関係数

対して推測鍵0x54を設定したときの最大の相関係数が以下です。
0.6以上とかなり大きな値になっていることがわかります。

図17. 推測鍵0x54における最も大きな相関係数

次にトレースの各タイミングにおける相関係数を見ていきます。
今回利用したトレースはサンプリングポイント23400なので、この各時点における相関係数をプロットしたものを示します。
※Python仮想コードで示したCorrelationCoefficientsの中身がこれです。

まずは正解の推測鍵0x54から
10000の地点より少し前にピークがあることがわかります。
※ピークはマイナスの値ですが、正負は関係ありません。ピークの大きさ(相関の強さ)のみが重要になります。
※横軸が時系列に比例した値(約15ナノ秒間隔)、縦軸が相関係数です。

図18. 推測鍵0x54における相関係数と時系列

↓ピーク付近を拡大したもの

図19. 推測鍵0x54における相関係数と時系列のピーク

次に間違った推測鍵0x00を見てみます。
どこにもピークらしいものがないことがわかります。

図20. 推測鍵0x00における相関係数と時系列

最後に鍵を構成する16個のbyteの値を全部推測し、最も大きな相関係数がでた推測鍵を示したのが下の画像です。
Best Key Guessに各byte毎に最も大きな相関係数が算出できた推測鍵を表示しています。
その下の数字の羅列はそれに対応する相関係数の値です。

図21. CPAによる秘密鍵全体の推測

無事、正しい秘密鍵が推測できていることがわかりました。

対策

ソフトウェア的には、初期化ベクトル(IV)を利用した暗号化モードを利用するのがよいと思います。
DPA/CPAは暗号系に入力する平文が既知であることを前提に、Sboxに入力された秘密鍵を特定する攻撃でした。
IVを使うことでSboxに入力する秘密鍵がランダム化され、もとの秘密鍵を特定できなくなります(特定できるのは秘密鍵とIVをxorしたあとのデータになる)。
ただし、攻撃者が何らかの方法でIVを特定できた場合は秘密鍵を復元できる可能性があります。
また、攻撃者の立場から見て、“これは実装されていたら厄介だな”と感じた対策としては、タイミングをずらす処理や意味のないダミー処理がランダムに入ってくると攻撃の難易度が上がると感じました。

ハードウェア的な面については設計に詳しくないため、現実にどのような工夫がされているかはわかりませんが、攻撃者の視点でDPA/CPAの難易度が高くなる要素をまとめます。
まずは消費電力の変動を抑えて常に一定になるような仕組みがあれば、解析に必要になるトレース数が増えることで攻撃の労力が増えます。また、ランダムなタイミングでノイズを生成することでトレースからパターンを推測しにくくなります。
※基盤からチップとROMを外して攻撃できる可能性もあるので、これらの対策はチップ内で完結しているのが望ましいと思います。

まとめ

SPA(SimplePowerAnalysis)に続き、古典的な電力解析攻撃であるDPA/CPAの実験をしてみました。
攻撃に必要な前提条件は多いですが、トレースを攻撃に利用する方法について以前よりも深く理解できました。

参考