SECCON2016qual 参加記

はじめに

SECCON2016予選にチームHarekazeの黒木洋美として参戦していました。

普段は競技プログラミングをしているのですが、ある日hiwwさんからお誘いいただきCTFに参加することになりました。

~~(現在の記事は速報版です)~~
~~2016/12/12 深夜更新(未完。まあちまちま完成に向けて更新していきます。)~~
2016/12/15 完成？

結果

個人的0完。延長戦でcrypt200pts Backpacker's Capricious Cipher を解いたので解説(CTF界隈ではWriteUpと言うらしい？)を貼っておきます。コンテスト中は競技の知識に付け焼刃でなんとかなりそうな暗号問に取り組んでました。

Backpacker's Capricious Cipher (crypt 200pts) 解法

解法概要

つらいやるだけ。手計算をがんばる。~~オイラー~~フェルマーの小定理を知っていれば小学生でも解ける。

問題概要

暗号化/復号用のソースコードと、公開鍵と暗号文が渡されるので復号してくださいという問題。暗号化のアルゴリズムは部分和問題の難しさを拠り所にしたものでした。後述しますが、この問題の場合はナップザック問題を解くことなく復号できます。

蛇足。同じく部分和問題の難しさを拠り所にした暗号にはナップザック暗号というものがあるらしいです（チームメイトが教えてくれました）。しかし、この問題の暗号はナップザック暗号ではないようです。これは次の理由によります。Wikipediaの解説によればナップザック暗号は超増加数列というものを利用するらしいのですが、ナップザック暗号で用いる素数Pは使用する超増加列の総和よりも大きく選ぶ必要があります。数列の和が最小となるような超増加列は $\{1,2,4,8,16,32,...\}$ と、初項1、公比2の等比数列であり（このことは帰納法で証明できる）、その総和は長さNの超増加列では $2^N-1$ となります。ところがこの問題で与えられるパラメータを見てみると、 $2^N -1 \gt P$ でありナップザック暗号のPの選び方からは外れていることがわかります（ナップザック暗号だという勘違いを防ぐいいヒントですね！）。よって、この問題がナップザック暗号ではなく、別の何かの方法で暗号化されていてこれを復号する必要があるということがわかります。ナップザック暗号だと思って時間を溶かした各位は反省しましょう。

暗号化手法(配布されたコード中での)

私のような脳みそ空っぽ人間にはrubyで書かれた元のコードは難しすぎた。ということで、cipher.rbと等価なコードをpythonで書きました（等価になってるはず？）。python固有の機能はほぼ使ってないし、コメントもたくさんいれたので動作は理解できるはず？

#!/usr/bin/env python3
# -*- coding : utf-8 -*-
import random

def keygen(N, P) :
	k = [] # 鍵の集合(公開鍵)
	K = 0  # kの部分和(公開鍵)
	priv = [] # 和がKとなるようなkの選び方(秘密鍵)
	for i in range(N) :
		# [0,P)の区間から整数を一つランダムに選ぶ
		k.append(random.randint(0,P-1))
	for i in k :
		# 1/2の確立でkからアイテムを選択する
		if random.randint(0,1) :
			K = (K+i) % P
			priv.append(1)
		else :
			priv.append(0)

	return K, k, priv # (公開鍵,公開鍵,秘密鍵)

def encrypt(msg, N, k, K, P) :
	# vec_Aの内容は、[ [-K,[]], [k[0], [0]], [k[1], [1]], ... ]
	vec_A = [[-K,[]]]
	for i, key in enumerate(k) :
		vec_A.append([key,[i]])

	# 暗号化に使用する乱数を事前生成しておく
	R0 = []
	R1 = []
	R2 = []
	for i in range(N) :
		R0.append(random.randint(0,P-1))
		R1.append(random.randint(0,P-1))
		R2.append(random.randint(0,P-1))
	
	# vec_Bの内容は [ [R0[0], [0]], [R1[0], []], [R0[1], [1]], [R1[1], []], ... ]
	vec_B = []
	for i in range(N) :
		vec_B.append([R0[i], [i]])
		vec_B.append([R1[i], []])
	
	# normalize + multiply を含んだ処理。addはvec_Bを生成しているので考えなくてよい
	enc_dic = {tuple([]):msg} # もとのコードのrに相当
	for i in vec_A :
		for j in vec_B :
			# この辺はmultiplyに相当
			mul = (i[0] * j[0]) % P

			# この辺はnormalizeに相当
			vec_key = i[1] + j[1]
			# vec_key[0] <= vec_key[1] を保証
			if len(vec_key) == 2 and vec_key[0] > vec_key[1] :
				# swap
				vec_key[0], vec_key[1] = vec_key[1], vec_key[0]

			# vec_keyをキーとしたハッシュテーブルに値を足しこむ
			if not(tuple(vec_key) in enc_dic) :
				enc_dic[tuple(vec_key)] = 0
			enc_dic[tuple(vec_key)] = (enc_dic[tuple(vec_key)] + mul) % P
	
	for i in range(N) :
		enc_dic[tuple([i])] = (enc_dic[tuple([i])] - R2[i] + P) % P
		enc_dic[tuple([i,i])] = (enc_dic[tuple([i,i])] + R2[i]) % P
	
	# return用にencを成形する。特に意味はない。
	enc = []
	for i in range(N+1) :
		for j in range(i,N+1) :
			vec_key = [i-1,j-1]
			if i == 0 and j == 0 :
				vec_key = []
			elif i == 0 :
				vec_key = [j-1]
			enc.append([enc_dic[tuple(vec_key)], vec_key])
	return enc

def decrypt(enc, p) : #暗号文、秘密鍵
	msg = 0
	for i in enc :
		# i は [num,[a,b]] の形で、[a,b]はencryptのvec_keyに相当するもの
		add_flg = True
		for j in i[1] :
			add_flg = add_flg and p[j]

		# iが[num,[a,b]]であり、k[a]とk[b]がともに公開鍵Kを作るために使われていればnumを加算
		if add_flg :
			msg = (msg + i[0]) % P
	return msg

if __name__ == "__main__" :
	# 試しに暗号化/復号をしてみる
	N = 128
	P = 79228162514264337593543950319
	K, k, priv = keygen(N,P)
	# こいつを暗号化
	msg = 12345678987654321
	enc = encrypt(msg, N, k, K, P)
	msg_ = decrypt(enc, priv)

	print(msg, msg_)

暗号化に用いられているコードを読むと、それと等価なpythonのコード中でvec_Aとvec_Bの乗算が行われていることがわかる。この手のコードを読むには表を書いてしまうのが楽なので表を書くと次のようになる。

		vec_A
		-K, [ ]	k[0], [0]	k[1], [1]	...	k[N-1], [N-1]
vec_B	R0[0], [0]	-K*R0[0], [0]	k[0]*R0[0], [0,0]	k[1]*R0[0], [0,1]	...	k[N-1]*R0[0], [0,N-1]
	R1[0], [ ]	-K*R1[0], [ ]	k[0]*R1[0], [0]	k[1]*R1[0], [1]	...	k[N-1]*R1[0], [N-1]
	R0[1], [1]	-K*R0[1], [1]	k[0]*R0[1], [0,1]	k[1]*R0[1], [1,1]	...	k[N-1]*R0[1], [1,N-1]
	R1[1], [ ]	-K*R1[1], [ ]	k[0]*R1[1], [0]	k[1]*R1[1], [1]	...	k[N-1]*R1[1], [N-1]
	...	...	...	...	...	...
	R0[N-1], [N-1]	-K*R0[N-1], [N-1]	k[0]*R0[N-1], [0,N-1]	k[1]*R0[N-1], [1,N-1]	...	k[N-1]*R0[N-1], [N-1,N-1]
	R1[N-1], [ ]	-K*R1[N-1], [ ]	k[0]*R1[N-1], [0]	k[1]*R1[N-1], [1]	...	k[N-1]*R1[N-1], [N-1]

この表の内容の要素を足しあげて暗号化を行っているので、表の要素の和をキーとなるリストの要素ごとに取ると、

[] : -K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1)
[i,i] : R0[i]*k[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。さらに平文・乱数が足しこまれ、最終的には

[] : msg - K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1) - R2[i]
[i,i] : R0[i]*k[i] + R2[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。暗号文は、各キーとそれに紐づく数のタプルの集合である。

復号手法(配布されたコード中での)

秘密鍵として保存された、公開鍵Kをつくるような鍵kのインデックスの集合をIとすると、[], [i], [i,i], [i,j] $(i, j \in I)$ に紐付く数を足し上げることで復号を行っている。実際に足し上げると
$msg + (\sum_{i \in I} k_i - K)(\sum_{i \in I} R0_i + \sum_{i}R1_i)$
となることが分かり、 $\sum_{i \in I} k_i = K$ であるから、配布されたコード中に記された方法で確かに復号できることがわかる。

解読手法

記号類の定義

$msg$ : 復号を目指す数(未知)
$k_i$ : 鍵i(既知)
$K$ : 鍵iの部分集合の和(既知)
$R0_i$ : 乱数(未知)
$R1_i$ : 乱数(未知)
$R2_i$ : 乱数(未知)
$S_{i,j}$ : enc.txtの[i,j]に紐付く内容 $(i \lt j)$ (既知)

また、合同式の法は常に素数Pとする。

解読

以下が成り立つ。

$S_{Null,Null} \equiv msg - K \sum_{i}R1_i$
$S_{i,Null} \equiv -K \cdot R0_i + k_i \cdot \sum_{j}R1_j - R2_i$
$S_{i,i} \equiv R0_i \cdot k_i + R2_i$
$S_{i,j} \equiv R0_i \cdot k_j + R0_j \cdot k_i$

式4から
$\begin{cases} R0_0 \cdot k_1 + R0_1 \cdot k_0 \equiv S_{0,1} \\ R0_0 \cdot k_2 + R0_2 \cdot k_0 \equiv S_{0,2} \end{cases}$
ここから $R0_0$ を消去して整理すると
$R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1}$
さらに式4から導かれる式と連立して
$\begin{cases} R0_1 \cdot k_2 + R0_2 \cdot k_1 \equiv S_{1,2} \\ R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1} \end{cases}$
これを解いて
$R0_1 = ((S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^ {-1} + S_{1,2}) \cdot (2k_2) ^{-1}$
$R0_0 = (S_{0,1} - R0_1 \cdot k_0) \cdot k_1^{-1}$

式4を変形して
$R0_i = (S_{i,j} - R0_j \cdot k_i) \cdot k_j ^{-1}$

$R0_0 , R0_1$ が既知なので、上式を用いてすべての $i$ に対して $R0_i$ を求めることができる。( $j=0$ とすればよい)

式2,3より
$-K \cdot R0_i + k_i \cdot \sum_{j} R1_{j} + R0_i \cdot k_i \equiv S_{i,Null} + S_{i,i}$
これを変形して
$\sum_{j}R1_j \equiv ((S_{i,Null} + S_{i,i}) + K \cdot R0_{i} - R0_{i} \cdot k_{i} ) \cdot k_i ^{-1}$

右辺は既知なので、R1の総和 $\sum_{i}R1_i$ が求まる。

式1より
$msg \equiv S_{Null,Null} + K \cdot \sum_{i} R1_{i}$
となり、msgを復号できる。

msg = 0x534543434f4e7b6b70736b7d
であり、フラグはSECCON{kpsk}

ソースコード

#!/usr/bin/python3

P = 79228162514264337593543950319
k_hs = 14883097866997387203089669453
keys = # 省略します。解説中のk_iを埋め込んでください

def mod_inv(n) :
	global P
	res = 1
	p = P-2
	while p :
		if p % 2 :
			res = (res * n) % P
		p //= 2
		n = (n * n) % P
	return res

# enc.txtから
c = # 省略します。解説中のS_{i,j}を[S_{i,j},[i,j]] のリストの形で埋め込んでください。Nullのところは要素数を減らして対応します。

sum_all = 0
tab = {}

for i in c :
	sum_all += i[0]
	tab[tuple(i[1])] = i[0]
	sum_all %= P

r0 = [0 for i in range(128)]
sum_r0 = 0

r0[1] = mod_inv(2*keys[2]) * ((tab[tuple([0,1])] * keys[2] - tab[tuple([0,2])] * keys[1]) * mod_inv(keys[0]) + tab[tuple([1,2])])
r0[0] = (tab[tuple([0,1])] - r0[1] * keys[0]) * mod_inv(keys[1])

r0[0] = (r0[0] % P + P) % P
r0[1] = (r0[1] % P + P) % P

sum_r0 = r0[0] + r0[1]

for i in range(2,128) :
	r0[i] = (tab[tuple([0,i])] - r0[0] * keys[i]) * mod_inv(keys[0])
	r0[i] = (r0[i] % P + P) % P
	sum_r0 += r0[i]

#assert
for i in range(128) :
	for j in range(i+1,128) :
		#print(i, j, (keys[i] * r0[j] + keys[j] * r0[i]) % P, tab[tuple([i,j])])
		assert((keys[i] * r0[j] + keys[j] * r0[i]) % P == tab[tuple([i,j])]);

sum_r1 = mod_inv(keys[0]) * ((tab[tuple([0,0])]+tab[tuple([0])]) + k_hs * r0[0] - r0[0] * keys[0])

sum_r0 = (sum_r0 % P + P) % P
sum_r1 = (sum_r1 % P + P) % P

#assert
for i in range(1,128) :
	tmp = mod_inv(keys[i]) * (tab[tuple([i,i])] + tab[tuple([i])] + k_hs * r0[i] - r0[i] * keys[i])
	tmp = (tmp % P + P) % P
	assert(sum_r1 == tmp)

ans = sum_all - ((sum(keys) - k_hs) % P) * (sum_r0 + sum_r1)
ans = (ans % P + P) % P

assert(ans == ((tab[tuple([])] + k_hs * sum_r1) % P + P) % P)

print(hex(ans))

問題雑感

初めて解いたCTFの古典暗号でない問題で、面白さを感じた。面白さを感じて解説を書いていたら長文になってしまった。rubyを読むのは辛かったが、解くのにそう必要な知識も多くなく「CTFの暗号問題はクソなぞなぞや謎知識を要求する問題の山」だと思っていたCTF初心者の私には良い影響を与えてくれたと思う。現代暗号面白そうなのでがんばろう。

感想

ひと月ほど準備期間があったが、論文やらCODEFESTIVALやらDDCCやらでなかなか準備できていなかった。正直役に立てる気がしていなかったが案の定役に立ってなかった。

Cryptは数弱にはつらい問題だったが、どうにかなりそうなのがCryptしかなかったのでCryptに取り組んでいた。はじめて読むrubyはつらかった。

~~オイラー~~フェルマーの小定理さえ知ってれば小中学生でも解けるCrypt200が解けなかったのは恥としか言えない。今後一層精進したい。

学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理