耐量子計算機暗号HK17-Qを解読する

この記事は、CTF Advent Calendar 2018 の21日目の記事です。

2018年8月に行われたNTT Tech Conference #3の暗号解析中級編 (Beyond CTF-Crypto) に参加した感想文+αです。xagawaさんは神。

TL;DR

  • NIST PQC (Post Quantum Cryptography:耐量子計算機暗号) 標準化プロジェクトの候補だったHK17-Qを解読します。

量子計算機がセキュリティに与える影響

量子計算機ができると簡単に素因数分解ができてしまうので現在使われている暗号は危ない」。この一文は正しいのですが、少し補足をするならば、「量子計算機ができると(量子計算機上で動作する暗号に影響を与えるアルゴリズムが動作することにより)簡単に素因数分解(や離散対数問題)ができてしまうので現在使われている(耐量子計算機性のない)暗号は危ない」となります。本章では、量子計算機が暗号の安全性に与える影響について簡単に紹介します。

量子計算機用のアルゴリズム

量子計算機が実現する、それだけでは暗号の安全性に大きな影響を与えることはありません。ただ量子計算機が実現すると、量子計算機での動作が前提とされているアルゴリズムもまた実現することになります。これらのうち、現在利用されている暗号系に大きな影響を与えるのが、GroverのアルゴリズムとShorのアルゴリズムです。このうち、Groverのアルゴリズム共通鍵暗号系およびハッシュ関数に、Shorのアルゴリズム公開鍵暗号系の安全性に影響を与えます。

量子計算機共通鍵暗号に与える影響

Groverのアルゴリズムはデータベースなどの空間の探索に有用なアルゴリズムです。通常、サイズNの整理されていないデータベースの探索にはΩ(N)の計算量を要しますが、Groverのアルゴリズムを利用することでO(N1/2)の計算量で探索することが可能になります。すなわち、ある暗号系において、利用するnビット鍵の候補を整理されていないデータベースと捉えれば、nビットの鍵の探索をO(n1/2)で実施することが可能となります。

これは公開鍵暗号と比較して、鍵長が比較的短い共通鍵暗号に対して、特に脅威となります。例えば128ビット鍵を用いる共通鍵暗号(AES-128など)の場合、通常であれば攻撃者が128ビット鍵の全数探索に必要な計算量はO(2128)ですが、Groverのアルゴリズムを利用できる場合、O(264)まで計算量を削減できることになります。これは現在のコンピュータの処理性能を勘案すると、十分現実時間で処理可能な計算量と言えるでしょう。

ただ本影響の対策は比較的容易です。なぜなら鍵長を2倍にすることで本アルゴリズムの影響を相殺することが可能だからです。例えば本来AES-128に期待される128ビット鍵相当の安全性を確保したければ、256ビット鍵を利用するAES-256を利用すれば良いからです。

これらのことから、量子計算機共通鍵暗号に影響を与えるが、比較的容易に対策可能であるといえます。

量子計算機公開鍵暗号に与える影響

Shorのアルゴリズム素因数分解問題や離散対数問題に対して有用なアルゴリズムです。通常、サイズNの素因数分解問題の解読には指数時間(または準指数時間)O(2N)の計算量を要しますが、Shorのアルゴリズムを利用することで多項式時間poly(logN)で問題を解くことが可能になります。これは素因数分解問題や離散対数問題を解くことの難しさを安全性の根拠にしている公開鍵暗号に対する脅威となります。

本影響の対策は困難です。例えば後述するNIST PQCにおいて、D.J.BernsteinらはShorのアルゴリズムに対して安全性を持たせたRSA(Post-Quantum RSA)を考察および提案していますが、その中の一つpqrsa30という方式では1024ビットの素数を223個かけた値を公開鍵Nとしています(ちなみに通常のRSA-1024であれば公開鍵は1024ビットの素数を2つかけた値になります)が、この公開鍵のサイズは1GiByte相当にもなります。このサイズの公開鍵を運用することは現実的に難しいのではないでしょうか。

これらのことからも、量子計算機公開鍵暗号に影響を与え、その対策は困難であるといえるでしょう。

量子計算機暗号 HK17-Q

先の説明のように量子計算機を利用したアルゴリズム公開鍵暗号に対して大きな影響を与えます。この対抗策として現在活発な議論が行われているのが耐量子計算機暗号(PQC: Post-Quantum-Cryptography)です。

量子計算機暗号とは?

「耐量子計算機暗号」。すごくかっこいい(?)名前ですが、要は量子計算機が実現すると効率よく解ける「素因数分解問題」および「離散対数問題」を安全性の根拠としない暗号の総称です。つまり、部分和問題を利用するナップザック暗号や、最短ベクトル問題を利用する格子暗号などは全て耐量子計算機暗号になります。

ちなみに耐量子計算機暗号≠量子暗号なので注意が必要です。

NIST PQC標準化プロジェクト

量子計算機暗号は、現在米国国立標準技術研究所 (NIST: National Institute of Standards and Technology) において、標準化がすすめられています。本標準化はAESやSHA3を決定した際と同様に、コンペティション形式で実施されています。2017年11月末に応募が締め切られ、12月下旬に応募に申し込みがあった69の候補が公開されました。 今後、3~5年をかけて、これら候補の中から耐量子計算機暗号における米国標準暗号が選定される予定です。

HK17-Q

HK17は上記NIST PQC標準化プロジェクトに申し込まれた暗号の一つです。HechtとKamlofskyによって提案されたこの暗号は非可換環上の多元数の性質を利用しています。この多元数のうち四元数を利用しているものをHK17-Qと呼びます。

四元数

四元数とは複素数を拡張した概念であり、次の形で表現できます。

x + yi + zj + wk

ここで、x, y, z, wは実数であり、(1), i, j, kは四元数の単位です。複素数でいうと1とiの関係ですね。またこれら四元数の単位は下記の式を満たします。

i2 = j2 = k2 = ijk = -1

これら基底間の乗法は左側の因子を列に、右側の因子を行に見立てて、表の形にまとめることが可能です。

x 1 i j k
1 1 i j k
i i -1 k -j
j j -k -1 i
k k j -i -1

なお、4元数は非可換環であることに注意が必要です (ex. i * j ≠ j * i)。

また四元数は4x4の正方行列として表すことも可能です。

HK17-Qのプロトコル

HK17-Qですが、簡単に言うと、四元数環上で行うDiffie-Hellman鍵交換です。ここでp, dを共有するパラメータ、Qを四元数環とすると、これは下記のプロトコルで行われます。

  1. Alice からBobにA, B, Xを送る。
    1. Aliceはランダムに2つの四元数A, BをQから選択する。
    2. Aliceはランダムに2つの正の整数m, nを選択する。
    3. AliceはランダムにGF(p)係数のd次多項式f(x)を選択する。なおf(A)≠0とする。
    4. AliceはX = f(A)m * B * f(A)n を計算する。
    5. AliceはBobにA, B, Xを送る。
  2. BobからAliceにYを送る。
    1. Bobはランダムに2つの正の整数r, sを選択する。
    2. BobはランダムにGF(p)係数のd次多項式h(x)を選択する。なおh(A)≠0とする。
    3. BobはY = h(A)r * B * h(A)s を計算する。
    4. BobはAliceにYを送る。
  3. Aliceは鍵KA = f(A)m * Y * f(A)n を計算する。
  4. Bobは鍵KB = h(A)r * X * h(A)s を計算する。

f:id:trmr105:20181212015029p:plain
HK17-Qのプロトコルフロー

通常2つの四元数の間に交換法則は成り立たないので、KA ≠ KBです。ただし多項式の引数が同じ場合、これら2つの四元数の間に交換法則が成立します。よってKA = f(A)m * h(A)r * B * h(A)s * f(A)n = h(A)r * f(A)m * B * f(A)n * h(A)s = KBとなり、Aliceの持つ鍵KAとBobの持つ鍵KBが同じであることが確認できます。これにて無事、鍵が共有できました。

HK17-Qの実装

Sagemath神は四元数をライブラリとして実装しています。ありがたく利用しましょう。

p = 65521
d = 64
BOUND = 2**30 # to bound m,n,r,s
Q.<ii,jj,kk> = QuaternionAlgebra(GF(p),-1,-1)
F.<x> = PolynomialRing(GF(p))

def sample_poly(qa):
    f = F(0)
    while f(qa) == 0:
        f = F.random_element(degree=(0,d-1))
    return f

# Alice side:
A = Q.random_element()
B = Q.random_element()
m = randint(0,BOUND)
n = randint(0,BOUND)
f = sample_poly(A)
X = f(A)^m * B * f(A)^n

print "="*20
print "Alice -> Bob:"
print "A = ", A
print "B = ", B
print "X = ", X

# Bob side:
r = randint(0,BOUND)
s = randint(0,BOUND)
h = sample_poly(A)
Y = h(A)^r * B * h(A)^s

print "="*20
print "Bob -> Alice"
print "Y= ", Y

# Alice:
KA = f(A)^m * Y * f(A)^n
# Bob
KB = h(A)^r * X * h(A)^s

# Check!
print "="*20
print "f(A)^m * h(A)^r = ", f(A)^m * h(A)^r
print "h(A)^r * f(A)^m = ", h(A)^r * f(A)^m
print "f(A)^n * h(A)^s = ", f(A)^n * h(A)^s
print "h(A)^s * f(A)^n = ", h(A)^s * f(A)^n
print "="*20
print "KA = ", KA
print "KB = ", KB

上記コードを実行すると、下記のような結果が得られます。

====================
Alice -> Bob:
A =  3905 + 4110*ii + 7735*jj + 1687*kk
B =  19887 + 54086*ii + 7585*jj + 20529*kk
X =  30794 + 41368*ii + 32032*jj + 28956*kk
====================
Bob -> Alice
Y=  44753 + 20270*ii + 60372*jj + 58243*kk
====================
f(A)^m * h(A)^r =  28985 + 64206*ii + 315*jj + 62032*kk
h(A)^r * f(A)^m =  28985 + 64206*ii + 315*jj + 62032*kk
f(A)^n * h(A)^s =  57134 + 58198*ii + 49587*jj + 44198*kk
h(A)^s * f(A)^n =  57134 + 58198*ii + 49587*jj + 44198*kk
====================
KA =  21031 + 22851*ii + 44751*jj + 45841*kk
KB =  21031 + 22851*ii + 44751*jj + 45841*kk

交換法則が成立していること、鍵が共有できていることが確認できます。

HK17-Qを解読する

このHK17-QをCTF問にすると下記のような問題にできそうです。

We succeed in eavesdropping the messages on a PQC key exchange communication. Can you recover the exchanged key?
====================
Alice -> Bob:
A =  3905 + 4110*ii + 7735*jj + 1687*kk
B =  19887 + 54086*ii + 7585*jj + 20529*kk
X =  30794 + 41368*ii + 32032*jj + 28956*kk
====================
Bob -> Alice
Y=  44753 + 20270*ii + 60372*jj + 58243*kk
====================

通信路を流れるMessageであるA, B, X, Yを用いて、鍵であるK = KA = KBを導出する問題です。

Cryptanalysis of HK17

上記のような問題が出たら、CTFerはどうするでしょうか。まずGoogle先生に教えを乞うて、この鍵交換プロトコルがHK17-Qであることを突き止めるでしょうか。そうすれば、このHK17-Qという暗号が実はその公開からわずか数日で解読されていることにも気づくはずです。その解読までの過程はpqc-forumの公式コメントに残されています。本章では、Liらによる「Cryptanalysis of HK17」をもとに攻撃方法を解説します。

攻撃の方針

HK17ではAliceからBobへのmessageとしてA, B, X = f1(A) * B * f2(A)が通信路を流れます(ここでf1(A) = f(A)m, f2(A) = f(A)nとします)。またBobからAliceへのmessageとしてYが流れます。そしてAliceの持つ鍵KA = f1(A) * Y * f2(A)で導出されます。すなわち攻撃者は盗聴したA, B, Xの値からf1(A), f2(A)を導出することができれば、その値をもとに鍵KAを計算することが可能です。このf1(A), f2(A)を導出することが本攻撃の方針です。

方針

f1(A), f2(A)とも四元数なので、4x4の正方行列としても表現が可能です。ケーリーハミルトンの定理を使って問題を解いていきましょう。

1. ケーリーハミルトンの定理

Aをn次正方行列とすると、Aの固有多項式p(λ)=det(λI - A)について、p(A) = 0が成り立つ。

2. 3次式への変換

先に述べたようにf1(A)は4x4の正方行列として表現が可能です。すなわち、ケーリーハミルトンの定理よりp(A)=A4 + .... = Oが得られます。これよりA4=A3...のようにA4と等価な3次式を得られます。これによりAn (n > 3)はすべて3次式に変換できるので、f1(A)はf1(A) = a0I + a1A + a2A2 + a3A3のように3次式で表せます。

3. 3次から1次への変換

四元数の場合、対応する行列の性質より、p(A) = A2 - (tr A) A + (det A) I = 0が得られます。すなわちA2 = (tr A)A - (det A) I のようにA2は1次式で表現することが可能です。これによりf1(A)の3次式はさらにf1(A) = a0I + a1Aのように1次式とみなすことが可能です。これよりf1(A) = f(A)m、f2(A) = f(A)nはそれぞれ下記の一次式で求められます。

f1(A) = aA + b, f2(A) = cA + d (a, b, c, d ∈ GF(p))

鍵の導出

1. f1(A)とf2(A)を計算する

A, B, X = f1(A) * B * f2(A)は通信路の盗聴により手に入れることが可能です。ここでf1(A), f2(A)に先の一次式を代入することで下記式が得られます。

X = (aA + b) * B * (cA + d) = ac * ABA + ad * AB + bc * BA + bd * B

すなわちABA, AB, BA, Bのそれぞれの係数 (ac, ad, bc, bd) = (s0, s1, s2, s3) とおくと、下記式が成立します。

(s0, s1, s2, s3) * (ABAの係数ベクトル, ABの係数ベクトル, BAの係数ベクトル, Bの係数ベクトル) = Xの係数ベクトル

これを解くことでs0, s1, s2, s3が導出でき、各a, b, c, dはa = 1, b = s2 * s0 ^ -1, c = s0, d= s1として手に入ります。これよりf1(A)およびf2(A)を導出可能です。

2. KAを計算する

KA = (A+ b) * Y * (cA + d)を計算しましょう。

HK17-Qの攻撃手法の実装

p = 65521
d = 64 #16, 32, or 64
BOUND = 2**30 # to bound m,n,r,s
Q.<ii,jj,kk> = QuaternionAlgebra(GF(p),-1,-1)
F.<x> = PolynomialRing(GF(p))

#Alice -> Bob:
A =  3905 + 4110*ii + 7735*jj + 1687*kk
B =  19887 + 54086*ii + 7585*jj + 20529*kk
X =  30794 + 41368*ii + 32032*jj + 28956*kk

#Bob -> Alice
Y=  44753 + 20270*ii + 60372*jj + 58243*kk


def make_vector(Z):
    return vector(GF(p),Z.coefficient_tuple())

def make_matrix(A,B):
    return matrix(GF(p),[make_vector(z) for z in [A*B*A,A*B,B*A,B]])

def solver(A,B,X):
    v = vector(GF(p),X.coefficient_tuple())
    # obtain s s.t. s*M=v
    s = make_matrix(A,B).solve_left(v)
    # we assume a = 1
    return [1, s[0]^(-1)*s[2], s[0], s[1]]


z = solver(A,B,X)
R = (z[0]*A+z[1]) * B * (z[2]*A+z[3])
K = (z[0]*A+z[1]) * Y * (z[2]*A+z[3])

print "="*20
print " X=", X
print " R=", R
print "="*20
print " K=", K

上記コードを実行すると下記の結果が得られます。

====================
 X= 30794 + 41368*ii + 32032*jj + 28956*kk
 R= 30794 + 41368*ii + 32032*jj + 28956*kk
====================
 K= 21031 + 22851*ii + 44751*jj + 45841*kk

先のKA, KBと同じ値の鍵Kが導出できました。

おわりに

いやー暗号って本当に楽しいですね。

参考文献

[1] Xagawa, "Beyond-CTF-crypto", https://gitlab.com/xagawa/Beyond-CTF-crypto

[2] "HK17 official comment", https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/HK17-official-comment.pdf

[3] Haoyu Li et al. "Cryptanalysis of HK17", https://eprint.iacr.org/2017/1259.pdf

【BkP2014 Differential Power】TEAの差分電力解析

本エントリは↓の続きです。

trmr.hatenablog.com

trmr.hatenablog.com

問題

we hooked up a power meter to this encryption box. we don’t know the key. that’s what we want to know. you can encrypt any string of 8 characters on the service http://54.218.22.41:6969/string_to_encrypt

準備

本来はサーバに平文を入力した際のasmの各処理で反転したbit数がグラフで表示される問題だったらしいですが、残念ながらサーバは動いていません。 ただ、CTF終了後に公開されたソースコードコンパイルしたものを実行するとデータの羅列が手に入ります。(本来はこのデータがグラフとしてプロットされていた) 勉強会では下記のランダムな平文を10個暗号化した際の反転したbit数を配布しました。

asmを読む

与えられたasmを読んでいきましょう。asmといっても各行にコメントで処理の概要が書いているので、アセンブラに慣れていない人でもそんなに読むのは難しくありません。2行目でTEA magicという表現があることからもわかるとおり、この暗号アルゴリズムはTEA (Tiny Encryption Algorithm) です。

add $t1, $zero, $zero# clear out $t1 ; 00004820
addi $t1, $t1, 0x9e# TEA magic is 0x9e3779b7 ; 2129009E

与えられた値はこのasmにおけるTEAの各操作におけるbitが反転した数です。

asmを読んでいくと11行目〜14行目にただ鍵の値を読み込んでいるだけ、という操作があります。

lw $t8, $zero, 8# k0 mem[8-23] = k ; 8c180008   
lw $s7, $zero, 12# k1 ; 8C17000C
lw $s6, $zero, 16# k2 ; 8C160010
lw $t3, $zero, 20# k3 now our keys are in registers ;  8c0b0014 

この操作では鍵のbitのうち1が立っている数と同じ数だけbitが反転していることになります。つまりこの処理の反転bit数は鍵のビット和と同じと考えられます。つまり鍵のビット和ではありますが、鍵の情報を手に入れることができました。

同様に他の操作を見ていきましょう。例えば19行目の下記操作はどうでしょう。

add $s4, $s4, $t8# +k0  part 1 is in s4 ; 0298a020  

この操作は与えた平文を4bit左シフトさせたものと鍵を足したものです。この演算はXoRではなくaddであるため、桁上りの影響を受けます。つまりこの操作は入力される平文次第でそのビットが反転する数は異なります。複数の平文を試すことで、鍵の条件を絞っていけそうです。

このようにasmの各処理から鍵が満たす複数の条件式が取り出せそうです。この条件式を満たす範囲に鍵の探索範囲を絞ることで、鍵探索を効率化してみましょう。

解答1 SMTソルバー (Z3) で解く

複数の条件式があるので、SMTソルバーの利用を検討しましょう。 ここではMicrosoftが開発した神ツールZ3を利用します。 Z3の利用方法は下記MMA wikiを見るのをおすすめします。

CTF/Toolkit/z3py - 電気通信大学MMA

asmから取り出した条件式をひとまとめにしてz3神にお願いしたサンプルコードです。

この方法でもフラグはとれるんですが、私のラップトップ環境では50分程度の時間がかかります。

解答2 SMTソルバーなしで解く

解答1を勉強会で紹介したところ、参加者の方があっという間に改良版を書いて提供してくれました。

f:id:trmr105:20180317025259p:plain

katagaitai #10 differential power without SMT Solver — Bitbucket

こちらのコードでは私の環境ではフラグを見つけるまでが1分程度、全部の処理が終わるまででも8分程度でした。 私ももっと早くアルゴリズムを思いついて早く実装する力を身に着けていきたい所存です。

まとめ

この問題面白いですよね。解法のアイディアが分かればそんなに難しく無い問題だとは思いますが、 アセンブラの各処理のビット反転数から鍵を推測するアイディアを今まで見たことがなかったので、 勉強会でとりあげてみました。

Write-up Links

http://mslc.ctf.su/wp/boston-key-party-ctf-differential-power-crypto-400/

神ツールChipWhispererでAESの相関電力解析をする

本記事は↓の続きです。

trmr.hatenablog.com

概要

電力解析の神ツールの一つChipWhispererを使って、RHme3 Tracing the tracesを解きます。

ChipWhisperer

前回はAESの相関電力解析を実施する方法を勉強しましたが、 このような電力解析を簡単にやってくれるツールが世界には存在します。 そのようなツールの一つがChipWhispererです。

ChipWhisperer® – NewAE Technology Inc.

ChipWhispererは、電力をキャプチャするハードウェア部分とキャプチャした波形を解析するソフトウェア部分で構成されています。 このうちソフトウェア部分はオープンソース (GPLライセンス) で提供されています。 本記事ではこのソフトウェアを用いて、問題を解いていきます。

ちなみにハードウェア部分は販売されており、一番安いChipWhisperer Liteは下記サイトから250USD + カナダからの送料 + 税金で購入することが可能です。

NewAE Technology Inc.

ちなみに購入するとハートウォーミングなメッセージの書かれた領収書と、使い道のわからないトランプもついてきます。 こういう心遣いがうれしいですね。

f:id:trmr105:20180317013638p:plain

ただ今回の問題は電力はすでにデータとして与えられており、キャプチャをする必要がないため、ハードウェアの購入は必要ありません。 以降はソフトウェア部分にフォーカスして説明していきます。

インストール

まず下記サイトからChipWhispererをインストールしましょう。

Installing ChipWhisperer - ChipWhisperer Wiki

Windows版、Linux版、Mac版と用意されていますが、パッケージが用意されていてインストールが容易なこと、処理が早い (気がする) ことから、個人的にはWindows版をおすすめします。

Tracing the traces

題材は前回と同様にRHme3のTracing the tracesです。 問題は下記を参照のこと。

github.com

ChipWhisperer形式への変換

前回を参考にmatlab形式の変換までは完了していることとします。 下記コマンドでmatlabフォーマットをchipwhispererフォーマットに変換しましょう。

import scipy.io as sio
import numpy as np
import os
from chipwhisperer.common.traces.TraceContainerNative import TraceContainerNative

traces = sio.loadmat("traces.2.mat")


ntraces = len(traces['samples'])
traceLen = len(traces['samples'][0])

inp = np.uint8(traces['inout'][:, 0:16])
out = np.uint8(traces['inout'][:, 16:32])

#Save as ChipWhisperer project
tc = TraceContainerNative()
for i in range(0, ntraces):
    tc.addWave(traces['samples'][i])
    tc.addTextin(inp[i])
    tc.addTextout(out[i])
    tc.addKey([0]*16)

os.mkdir('rhme3')
tc.saveAllTraces('rhme3')
tc.config.setConfigFilename('rhme3/rhme.cfg')
tc.config.saveTrace()

ちなみTraceContainerNativeを利用してフォーマットを変換すると出来上がった設定ファイルrhme.cfgファイルの 設定値にprefix=Noneと書かれた行が自動的に付与されます。 ただ、なぜかこの値をChipWhispererはprefixが"不要"という意味ではなく、prefix="None"という文字列として解釈してしまいます。 Noneを削除したprefix=に値を変えておきましょう。

ファイルの読込

ChipWhispererがインストールされたフォルダのsoftware配下に存在するCWAnalyzer.pywを起動します。 trace managerを実行し、rhme.cfgファイルを読み込んでみたところ、下記波形が表示されました。

f:id:trmr105:20180317015914p:plain

与えられたサンプル値を一つ表示しているみたいです。 たくさんのグラフを同時に表示してみましょう。 Resultタブのtrace to plotを0-100にしてみます。

f:id:trmr105:20180220003657p:plain

f:id:trmr105:20180220003623p:plain

これでジッターだらけではありますが、波形を表示することができました。

ジッターの排除

Attack Script Generatorでpre processingでResync: sum of differenceに設定してやり、次にpreprocessingタブに移動し、ref traceで特徴を抽出するトレースを指定し、特徴点(ピーク値等)をreference pointsの間にいれてやり、マッチングさせる範囲をinput windowとして設定してやりましょう。そして最後にenabledにチェックを入れれば、ある程度波形がきれいに表示されるはずです。

f:id:trmr105:20180317020811p:plain

f:id:trmr105:20180220004008p:plain

相関電力解析!

start attackをクリックしてください。

f:id:trmr105:20180317020936p:plain

Results Tablesの最も上に並んでる値が、最も相関係数の高かった値、すなわちFlagとなるはずです。

f:id:trmr105:20180220004154p:plain

まとめ

単純なAESに対する相関電力解析はツールで解けちゃいます。 低い得点で電力解析問が出たらとりあえずツールにかけてしまうのが勝ちパターンかもしれません。

次回は一風変わった電力解析問を紹介します。

trmr.hatenablog.com

Write-up Links

AESに対する相関電力解析を勉強する

これはkatagaitai CTF勉強会 #10で喋った内容の一部を要約したものです。 勉強会のスライドはこちら。

www.slideshare.net

概要

  • AESの相関電力解析を勉強
  • ジッターの排除方法を勉強
  • RHme3 Tracing the tracesを解く

電力解析

一般的に暗号システムの評価はその入力及び出力を攻撃者が得られる仮定のもとで、保護資産 (平文・鍵 etc.) が適切に保護されているかを評価します。選択平文攻撃や選択暗号文攻撃などがこれに該当します。これは暗号システムが入力をどのように出力に変換しているかの情報は全く攻撃者は得られません。すなわち攻撃者にとって暗号システムがブラックボックスであることを意味します。

ただ、実際に攻撃者にとって暗号システムはブラックボックスなのでしょうか?残念ながら、違います。多くの場合、暗号システムはコンピュータに実装され、コンピュータは暗号の処理を行う際に電力を消費します。負荷がかかる演算が行われたら、メモリの内容を多く書き換えたら、それだけ電力が多く消費されます。つまり、演算処理やメモリの情報は消費電力という形で外部に現れてしまいます。暗号システムの入出力に加え、消費電力を解析することで、保護資産を手に入れようとすることを電力解析と呼びます。

f:id:trmr105:20180316202714p:plain

CTFと電力解析

一般にCTFであまり出題頻度が高いとは言えない電力解析問ですが、最近流行りのIoT系のCTF*1の暗号問では頻出問となっています。というかIoT系のCTFでは、現在のところ暗号問はホワイトボックス暗号か電力解析のほぼ2択となっている気がします*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を解説します。

f:id:trmr105:20180316202315p:plain

コンピュータのデータはメモリやレジスタといった記憶装置に保存されます。これらメモリやレジスタはその内部に電荷を保持しているかいないかで、保存しているビットが"1"か”0"かを判断します。そしてその電荷を保持する性質上、ビットを反転させる(=内容を書き換える) 際に大きく電力を消費します。つまり一回のデータ変更で書き換えるデータの量が多ければ多いほど、その消費電力は大きくなります。

一般的なコンピュータシステム同様、多くの暗号システムでも、さまざまな入力が記憶装置に格納され、処理され、格納され、処理されを繰り返し、最終的にシステムの出力である暗号文を生成します。その間、記憶装置では各処理ごとに入力と出力の差分(=ハミング距離)だけ、レジスタの保存しているビットを反転させます。この際、処理の入力と出力の差分が小さければ消費電力は小さく、大きければ消費電力もまた大きくなると考えられます。すなわち、処理の入出力のハミング距離と消費電力は相関関係を持ちます。

これら入力出力のハミング距離とその消費電力の相関関係を利用して、暗号を分析する攻撃が相関電力解析です。

このような線形な相関はピアソンの相関係数で表すことができます。ハミング距離と消費電力が比例の関係に近ければ近いほど、相関係数は1に近づきます。

f:id:trmr105:20180219230029p:plain

AES

AESのラウンド処理は下記の図のような処理を組み合わせて実施されます。今回は一つ一つの処理はあまり重要ではありません。重要なのは、下記二点です。

  1. AESではAddRoundKeyとSubBytes処理は8bitのテーブル (word) 単位で処理
  2. 最初のラウンドで利用される鍵は128ビット鍵がそのまま利用される (Key Scheduling Algorithmの影響を受けない)

つまりAESの最初のラウンド処理では、AddRoundKeyとSubByte処理に関しては8ビット単位で16個に秘密鍵が分割されて処理されることになります。

f:id:trmr105:20180316202456p:plain

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です。 ちなみに問題は下記を参照のこと。

github.com

初動調査・方針

与えられたファイルは拡張子がmatだがmatlabで開こうとするとエラー。 先頭箇所を見ると下記記述あり。

# Created by Octave 4.0.3, Fri Aug 04 14:04:39 2017 CEST <andres@kali-andres>

Octaveというアプリケーションで作成されているみたいです。私は知らなかったのですが、調べるとmatlabalternativeとして広く利用されているらしいです。

早速インストールして実行して、そしてファイルを読み込んで、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()

f:id:trmr105:20180316203141p:plain

プロットされた消費電力波形はいろんな波形が重なり合っていてきれいな波形になっていません。 これはそれぞれの波形の測定したタイミングが完全に一致できておらず、時間軸方向にずれ (ジッター) が生じていることが原因です。 相関電力解析をやる前にこのジッターを取り除いてやる必要がありそうです。

ジッターの排除

ジッターを排除するために、テンプレートマッチングの一種であるSAD (Sum of Absolute Difference) を利用します。 SADを利用して、ある波形から抽出点を選択し、他の波形の差分との絶対値の合計が小さくなる箇所を探索することで、ずれ幅を求めることが可能です。

f:id:trmr105:20180316203723p:plain

ということで、最初の波形の一部を抽出点として抜き出して、100番目までの波形のずれを修正するサンプルコードです。

これを実行すると下記の結果が得られます。 左がSAD前の波形、右がSAD後です。 ジッターが低減していることがわかります。

f:id:trmr105:20180316210228p:plain

相関電力解析!

ようやく準備が整ったので、相関電力解析をやっていきましょう。 と言っても、実施内容についてはすでに説明してしまっているので、実装するだけです。

まとめ

今回はRHme3 Tracing the tracesを題材に、AESに対する相関電力解析を勉強しました。 なんとなく雰囲気だけでも伝わったでしょうか。

え、実装がめんどくさいので、もっと簡単に解きたい?はい、私もそう思います。 ということで、次回はツールで解く方法を紹介します。

trmr.hatenablog.com

Write-up Links

*1:DEFCONのCar Village Hacking, CODE BLUEのICS CTFなど

*2:というか暗号問の出題自体が少ないのですが。このあたりは今後問題の開発が進めば変わってくるかもしれませんね。

*3:筆者は定義もせずIoTと言う言葉を使う人は信用しないことにしています。