耐量子計算機暗号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(N^1/2)の計算量で探索することが可能になります。すなわち、ある暗号系において、利用するnビット鍵の候補を整理されていないデータベースと捉えれば、nビットの鍵の探索をO(n^1/2)で実施することが可能となります。

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

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

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

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

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

本影響の対策は困難です。例えば後述するNIST PQCにおいて、D.J.BernsteinらはShorのアルゴリズムに対して安全性を持たせたRSA（Post-Quantum RSA）を考察および提案していますが、その中の一つpqrsa30という方式では1024ビットの素数を2²³個かけた値を公開鍵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の関係ですね。またこれら四元数の単位は下記の式を満たします。

i² = j² = k² = 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を四元数環とすると、これは下記のプロトコルで行われます。

Alice からBobにA, B, Xを送る。
1. Aliceはランダムに２つの四元数A, BをQから選択する。
2. Aliceはランダムに２つの正の整数m, nを選択する。
3. AliceはランダムにGF(p)係数のd次多項式f(x)を選択する。なおf(A)≠0とする。
4. AliceはX = f(A)^m * B * f(A)ⁿ を計算する。
5. AliceはBobにA, B, Xを送る。
BobからAliceにYを送る。
1. Bobはランダムに２つの正の整数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を送る。
Aliceは鍵KA = f(A)^m * Y * f(A)ⁿ を計算する。
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)ⁿ = h(A)^r * f(A)^m * B * f(A)ⁿ * 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)ⁿとします)。また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)=A⁴ + .... = Oが得られます。これよりA⁴=A³...のようにA⁴と等価な3次式を得られます。これによりAⁿ (n > 3)はすべて3次式に変換できるので、f1(A)はf1(A) = a0I + a1A + a2A² + a3A³のように3次式で表せます。

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

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

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