おおひらンゴスタ氏（id:o_hi_rangosta ）の記事とほぼ同じ内容です。
o-hi-rangosta.hatenablog.com

彼とは別に記事を作っていたのですが、RHme3のTracing the Tracesで実験してみると誤った結果が返ってきてなかなか公開できませんでした。
本当はそれが解決してから投稿するつもりだったんですが、とりあえず公開することにします。
別のデータでは成功したので間違っていない…はず…

この記事では、CPAを用いた鍵推定手法について述べていきます。
暗号文と波形が与えられた場合や、ハミング距離を用いて解く場合も考えることにします。

今回、RHme3のTracing the Tracesで出題された波形、平文、暗号文を用います。

なお、ジッターの排除まではtrmrさんの手法を用います。 trmr.hatenablog.com

以下、ジッター排除済みの波形を用います。

AES
CPA
- 平文と波形が与えられた場合
- 暗号文と波形が与えられた場合
参考文献

AES

AESでは、入力値は128ビットごとに4×4の二次元配列として扱われます。

$\begin{pmatrix} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \end{pmatrix}$

そのうえで、秘密鍵と平文をXOR（AddRoundKey）してから、次の処理を10回行います。
なお、10回目はMixColumnsは含まれません。

SubBytes
Sボックスと呼ばれる換字表を用いて1バイトごとに換字します。
例えば、0xFFは0x16に置換されます。

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)

ShiftRows
4バイトごとに左シフトを行います。
MixColumns
行列を線形変換します。今回は全く使わないので省略。
AddRoundKey
行列とラウンド鍵をXORします。
https://en.wikipedia.org/wiki/Rijndael_key_scheduleにより、それぞれのラウンド鍵は異なった値となります。

$\begin{pmatrix} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \end{pmatrix} \bigoplus \begin{pmatrix} k_{0,0} & k_{0,1} & k_{0,2} & k_{0,3} \\ k_{1,0} & k_{1,1} & k_{1,2} & k_{1,3} \\ k_{2,0} & k_{2,1} & k_{2,2} & k_{2,3} \\ k_{3,0} & k_{3,1} & k_{3,2} & k_{3,3} \end{pmatrix} = \begin{pmatrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} \\ b_{1,0} & b_{1,1} & b_{1,2} & b_{1,3} \\ b_{2,0} & b_{2,1} & b_{2,2} & b_{2,3} \\ b_{3,0} & b_{3,1} & b_{3,2} & b_{3,3} \end{pmatrix}$

CPA

推測した電力値と計測した電力値との相関から、ラウンド鍵を求めます。

何バイト目の鍵を推測するか決める
ラウンド鍵の行列から、推測する要素を1つ決定します。
AddRoundKeyで見たように、ラウンド鍵は（128bitの場合）16バイトしかありません。つまり、以下の手順2〜手順4を16回繰り返すことになります。
適当な推測鍵を決める
1バイトなので256通りです。
つまり、以下の手順3〜手順4を256回繰り返すことになります。手順1と合わせて、 $16 \times 256=4096$ 回ループを行うことになります。
その鍵をSubBytesする前または後のハミング距離またはハミング重さを求める

平文と波形が与えられた場合
1ラウンドのSubBytes後を求めることとなります。はじめのAddRoundKeyで用いるラウンド鍵は秘密鍵のため、ここで推測したラウンド鍵が秘密鍵となります。

攻撃対象におけるハミング重みを導きたいため、SubBytes(AddRoundKey(平文, 推測鍵))のハミング重みを求めることになります。
暗号文と波形が与えられた場合
10ラウンドのSubBytes前を求めることとなります。ここで推測するラウンド鍵は10ラウンド目のラウンド鍵です。
この段階では、Rijndael key scheduleにより、秘密鍵が得られる訳ではありません。
ハミング距離を用いる場合、図の攻撃対象における値と暗号文との値の2つが必要となります。
ゆえに、AddRoundKey、ShiftRows、SubBytesの逆処理を行う必要があります。
つまり、InvSubBytes(InvShiftRows(InvAddRoundKey(平文, 推測鍵)))と暗号文のXORによってハミング距離を求めることになります。
InvAddRoundKey
AddRoundKeyがXORするだけなので、InvAddRoundKeyもXORするだけです。
InvShiftRows
4バイトごとに右シフトします。これにより、逆処理を行った後のバイト位置と暗号鍵のバイト位置にズレが生じます。
例えば、2バイト目の鍵を推測していたとします。InvShiftRowsにより、この推測は14バイト目のものとなります。
つまり、14バイト目の攻撃対象における値と2バイト目の暗号文とXORすることになります。
InvSubBytes

値のインデックスを返せば良いだけです。
観測した波形とハミング距離またはハミング重みとの相関係数を求める
相関係数が一番高い推測値が秘密鍵またはラウンド鍵となる
前述したように、平文と波形が与えられた場合は、その推測値が秘密鍵です。
一方で、暗号文と波形が与えられた場合、それは10ラウンドにおけるラウンド鍵です。秘密鍵を得るためには、Rijndael key scheduleの逆処理を行う必要があります。今回の場合、

ラウンド回数	ラウンド鍵
はじめ	cafebabedeadbeef0001020304050607
ラウンド1	a0917f4c7e3cc1a37e3dc3a07a38c5a7
ラウンド2	a5372396db0be235a5362195df0ee432
ラウンド3	0a5e0008d155e23d7463c3a8ab6d279a
ラウンド4	3e92b86aefc75a579ba499ff30c9be65
ラウンド5	f33cf56e1cfbaf39875f36c6b79688a3
ラウンド6	43f8ffc75f0350fed85c66386fcaee9b
ラウンド7	77d0eb6f28d3bb91f08fdda99f453332
ラウンド8	9913c8b4b1c07325414fae8cde0a9dbe
ラウンド9	e54d66a9548d158c15c2bb00cbc826be
ラウンド10	3bbac8b66f37dd3a7af5663ab13d4084

となります。ゆえに、3bbac8b66f37dd3a7af5663ab13d4084が求まるはずです。
（が実際に試したら別の値が導出されました...何でだろう...）
ラウンド鍵から秘密鍵に戻すプログラムは探せば出てくるため、今回はそれを使います。
私は以下のスクリプトを用いました。
github.com

$ python2 inverse_aes.py 3bbac8b66f37dd3a7af5663ab13d4084
Inverse expanded keys = [
        3bbac8b66f37dd3a7af5663ab13d4084
        e54d66a9548d158c15c2bb00cbc826be
        9913c8b4b1c07325414fae8cde0a9dbe
        77d0eb6f28d3bb91f08fdda99f453332
        43f8ffc75f0350fed85c66386fcaee9b
        f33cf56e1cfbaf39875f36c6b79688a3
        3e92b86aefc75a579ba499ff30c9be65
        0a5e0008d155e23d7463c3a8ab6d279a
        a5372396db0be235a5362195df0ee432
        a0917f4c7e3cc1a37e3dc3a07a38c5a7
        cafebabedeadbeef0001020304050607
]
Cipher key: cafebabedeadbeef0001020304050607
As string: '\xca\xfe\xba\xbe\xde\xad\xbe\xef\x00\x01\x02\x03\x04\x05\x06\x07'

以上をプログラムにするとこのようになります。なお、このプログラムは、暗号文と波形が与えられた場合に、ハミング距離を用いて推測するプログラムとなっています。 gist.github.com

couyoh’s old blog

移転先：https://couyoh.pages.dev/blog/

相関電力解析（CPA）による秘密鍵推定のメモ

AES

CPA

平文と波形が与えられた場合

暗号文と波形が与えられた場合

InvAddRoundKey

InvShiftRows

InvSubBytes

参考文献