らんごすたのにっき

セキュリティ系のイベント等のブログです.気が向いた時にしか書きませんが...

相関電力解析【Hamming distance model】によるAESの秘密鍵漏洩をやってみる

はじめに

 おおひらんごすたです.今回は,相関電力解析(以降,CPA; Correlation Power Analysis)【Hamming distance model版】によるAESの秘密鍵漏洩に関してまとめておこうと思います.Hamming weight modelに関しては,こことかに落ちてるんですが,Hamming distance modelはあんまり見なかったので書こうと思いました.また,最近のCTFのCryptoでは,CPAをはじめとするSide channel攻撃がたまーに出たりしてるようです.

Side channel攻撃

 まず,Side channel攻撃について.現代の暗号は,公開されたアルゴリズム(例えば, RSAとか)と秘密鍵を用いて,平文を暗文に変換します.こうした暗号は理論的には安全とされていますが,実際に暗号をハードウェアへ実装すると電磁波の漏洩等が起きたりします.それを悪用して秘密鍵を漏洩させたりするのがSide channel攻撃です.

電力解析と故障解析

 ここでは,ハードウェアへの代表的な攻撃である電力解析と故障解析を紹介します.電力解析の原理は,計算機のハードウェアレベルの動作に着目しています.ざっくり言うと,秘密鍵を使って平文を暗号化する場合に,もし秘密鍵情報の0と1を書き込む場合の電力に一定のパターンがあれば,このパターンは0でこれは1だみたいな感じで簡単に秘密鍵を漏洩させます.
 また,電力解析では攻撃者は漏洩する電力のパターン情報等を盗聴するのみでしたが,故障解析は暗号回路に意図的に電磁波を注入し演算をあえて誤らせて,誤らせた演算結果と正しい演算結果を比較して秘密鍵を特定します.
 以下,電力解析と故障解析の種類を紹介しています.(割と雑に説明してます.)

電力解析

単純電力解析(SPA; Simple Power Analysis)秘密鍵情報の電力波形をモニタリングし,秘密鍵を漏洩させる.
差分電力解析(DPA; Differencial Power Analysis):KocherらがCRYPTO’99にて提案した[1].大量の電力値の平均を用いて,暗号演算の変化部分を抽出して暗号鍵を漏洩させる.
相関電力解析(CPA; Correlation Power Analysis):BrierらがCHES’04にて提案した[2].攻撃者は,暗号処理でレジスタがどれくらい変わるかという情報と電力消費の相関を観測し,秘密鍵を漏洩させる.今回はこれを実装します.ところで,自動車内部のネットワークCAN(Controller Area Network)でも,将来的にCANが暗号化を施された場合,CPAの脅威があることが研究されていました.

故障解析

差分故障解析(DFA; Differential Fault Analysis):BihamらがCRYPTO’97にて提案した[3].正しい暗号文と誤りがある暗号文の差分を取り,秘密鍵候補の探索空間を削減し,秘密鍵を特定させる.
他にも,無効故障解析(IFA; Ineffective Fault Analysis)衝突故障解析(CFA; Collision Fault Analysis)とか提案されているらしいです.

 これらの攻撃に対して,AES,RSA暗号楕円曲線暗号,それぞれでアルゴリズムレベルや回路レベルで対策されているようです.

AES

 AES(Advanced Encryption Standard)は,DESの後釜的な標準的な共通鍵暗号アルゴリズムで,NIST(アメリカ国立標準技術研究所)によって公募され,最終的にRijndael(ラインダール)というアルゴリズムがAESに選ばれました.また,現状AESはどんな攻撃でも破られていないですが,危殆化(安全性が低下すること)も懸念されてるとかなんとからしいです.今回は,Side channel攻撃によってこれを破ります.以降では,AESの仕組みを概説します.
 AESにおいて,各変数は有限体GF(2^8)の要素とみなされ,各Roundの16バイトの内部状態は正方形の4×4行列として表すことができます.この行列を何Roundかの処理(鍵長128bitだと,10Round)にかけて,暗号化します.AESの全体像は以下みたいな感じです.
f:id:o_hi_rangosta:20190110213149p:plain:w300
 今度は,各Roundの処理に注目します.AESの1Round当たりに行われる処理は以下4つです.意外と簡単?

1. SubBytes :S box(GFに基づく換字表)による1byte単位の変換
f:id:o_hi_rangosta:20190110211208p:plain:w400
2. ShiftRows :4byte単位の行をある法則で左シフト
f:id:o_hi_rangosta:20190110211211p:plain:w400
3. MixColumns :bit演算による4byte単位の行列変換(今回注目するAESの10Round目にはMixColumnsはないので図略)
4. AddRoundKey :ラウンド鍵とのXOR
f:id:o_hi_rangosta:20190110211611p:plain:w600

 後述するCPA【Hamming distance model版】では,これらの処理を逆に遡って(InvAddRoundKey->InvShiftRows->InvSubBytes ※9->10RoundはMixColumnsは無い),9Round目のレジスタと10Round目のレジスタの変化量(Hamming distance)を算出し,レジスタの変化量に比例する消費電力の相関から秘密鍵を特定します.

CPA

CPAの概要

 早速,CPAを実装していきます.まずはCPAの流れを説明します.
 Step 0 :電力の計測 10000回くらい(今回は終わっている前提)
 Step 1 :ブルートフォース的に8bitの部分鍵を2^8個生成
 Step 2 :各部分鍵を用いて中間値(9Round目のレジスタ)を2^8個導出
 Step 3 :中間値と暗文(10Round目のレジスタ)からHamming distanceを2^8個算出
 Step 4 :推定電力値(Hamming distance)と計測電力値の相関係数を2^8個算出
 Step 5 :2^8個の相関係数の内,最大となる時の部分鍵が秘密鍵の一部となる

 Step1-5をラウンド鍵毎(15回)行い,秘密鍵全体を漏洩させて終了です.以上から分かるように,攻撃者は,無限に平文を暗文に変換でき,かつ,暗号化時の電力を正しく計測可能なことが前提となっています.

消費電力モデル (Hamming weight/distance model)

 AESのCPAでは,消費電力モデルを仮定して相関係数を出します.ハードウェアで実装されたAESの場合,レジスタの変化を利用したHamming distance modelを用います.v_n-1, v_nがそれぞれ9, 10Round目のレジスタとすると,Hamming weight/distanceは以下です.

v_n-1 v_n HD(v_n-1, v_n) HW(v_n)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

 表から分かるように,Hamming weightは10Round目のレジスタのみで算出できますが,Hamming distanceは9Round目も必要になります.そのため,今回実装するCPAではAESの逆の処理を行いレジスタを書き戻す必要があることがわかります.

PythonでのCPA実装

入力データ

 128bitの暗文と各暗文に対応する計測した電力値の2つが必要になります.また,今回は計測した電力値データの列2800~3000の間に暗号処理があることがわかっているので実装するCPAではその200個の電力値のみに着目しています.
暗文データの例

125,247,107,12,26,184,153,179,62,66,240,71,185,27,84,111
87,18,125,64,52,177,190,191,174,244,102,185,199,114,111,198
 ...

計測した電力値データの例

行10000×列3840の電力値データ

ソースコード

 ここに落ちてるHamming weight modelでのCPAをめちゃくちゃ参考にしてます.

import numpy as np

sbox=(
0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16)

idx_calc=(0,13,10,7,4,1,14,11,8,5,2,15,12,9,6,3)
inv_idx_calc=(0,5,10,15,4,9,14,3,8,13,2,7,12,1,6,11)

def intermediate(pt, keyguess):
    return sbox[int(pt) ^ keyguess]

traces = np.loadtxt('aes_tv_0000001-0005000_power.csv', delimiter=',')
pt = np.loadtxt('CIPHERTEXT10000.csv', delimiter=',')

numtraces = np.shape(traces)[0]
numpoint = 200

#Use less than the maximum traces by setting numtraces to something

#Calculate Hamming distance
def HD(vn_1, vn):
    diff = int(vn_1) ^ vn
    return bin(diff).count("1")


bestguess = [0]*16
#Set 16 to something lower (like 1) to only go through a single subkey & save time!
for bnum in range(0, 16):
    cpaoutput = [0]*256
    maxcpa = [0]*256
    for kguess in range(0, 256):
        corr_coef = 0.0
        max_corr = 0.0
        print "Subkey %2d, hyp = %02x: "%(bnum, kguess),

        #Initialize arrays & variables to zero
        sumnum = np.zeros(numpoint)
        sumden1 = np.zeros(numpoint)
        sumden2 = np.zeros(numpoint)

        hyp = np.zeros(numtraces)

        #Go back 9 Round (middle value) register
        for tnum in range(0, numtraces):

            idx = idx_calc[bnum]

            snum = int(pt[tnum][idx]) ^ kguess
            for i in range(0,256):
                if snum == sbox[i]:
                    leak_middle = i
                    break
            hyp[tnum] = HD(pt[tnum][bnum], leak_middle)


        #Mean of hypothesis
        meanh = np.mean(hyp, dtype=np.float64)

        #Mean of all points in trace
        meant = np.mean(traces[:,2800:3000], axis=0, dtype=np.float64)

        for i in range(0, 200):
            corr_coef = abs(np.corrcoef(hyp, traces[:,(2800+i)])[0, 1])
            if max_corr < corr_coef:
                max_corr = corr_coef
                maxcpa[kguess] = corr_coef

        print maxcpa[kguess]

    #Find maximum value of key
    bestguess[bnum] = np.argmax(maxcpa)

print "Best Key Guess: "
for subkey_i in range(len(bestguess)): print "%02x "%bestguess[inv_idx_calc[subkey_i]],

 couyoh氏のCPAも貼っときます.(多分こっちのが読みやすい)

gistc5f48d93a496b6f557cb3f5b56c47584

実行例

1つ目の部分鍵の特定

f:id:o_hi_rangosta:20190110194207p:plain:w400
 部分鍵がd0の時,相関係数が高くなってることがわかります.

相関係数のグラフ

 グラフで見ただけ.※0xd0=208
f:id:o_hi_rangosta:20190110201327p:plain:w400

InvKeyExpansionによる秘密鍵の導出

 d0は,正しくは10Round鍵なので,秘密鍵を導出するには,10,9,...,秘密鍵まで,KeyExpansionの逆演算を行う必要があります.以下が参考になりそうです.
github.com

終わりに

 公開されてるデータで,実行できそうなものが見つかれば追記します.

参考文献/サイト

[1] P. Kocher, J. Jaffe, and B. Jun. Differential power analysis. In Advances in Cryptology — CRYPTO ’99, LNCS 1666, pp. 388–397, Springer-Verlag, 1999.
[2] Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds.): Cryptographic Hardware and Embedded Systems—CHES 2004: 6th International Workshop Cambridge, MA, USA, August 11–13, 2004. Proceedings, Lecture Notes in Computer Science, vol. 3156, pp. 16–29. Springer, Berlin (2004)
[3] E. Biham and A. Shamir, “Differential Fault Analysis of Secret Key Cryptosystems,” Advances in Cryptology: Proceedings of CRYPTO’ 97, Springer-Verlag, August 1997, pp. 513–525.
[4] Tutorial B6 Breaking AES (Manual CPA Attack) https://wiki.newae.com/Tutorial_B6_Breaking_AES_(Manual_CPA_Attack))
[5] AESに対する相関電力解析を勉強する http://trmr.hatenablog.com/entry/2018/03/18/220441
[6] 神ツールChipWhispererでAESの相関電力解析をする http://trmr.hatenablog.com/entry/2018/03/18/220711
[7] Announcing the ADVANCED ENCRYPTION STANDARD (AES) https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.197.pdf