Harekaze mini CTF 2020 作問者writeup

はじめに

今年のHarekazeとしての活動をなにかしておきたい、ということで急遽Harekaze mini CTF 2020を開催が決まり、私はCryptoジャンルの4問を出題しました。初心者向けとはいえ、単にbase64をするだけの問題や、RSAとはなんでしょう？　調べてみましょう、のような問題を出題するのは性に合わないし、コストパフォーマンスも悪いうえ、多くの参加者にとっては解いても楽しくない問題となってしまうため出題を避けました。代わりにいわゆる「典型」とでも言うような、よく出題される基礎的な知識について問いつつ、ストレス少なく解けて、ある程度の解きごたえがあるような問題を出題することを目標にしました。つまり、非典型ではあるけど典型について学べる、というようなところです。本エントリでは私が作問を担当した問題について、出題の意図と解法を振り返っていきます。

競技中に解けなかった問題は是非復習してください。復習しないと競技中に調べた分しか学びがありません。 writeupが書けると更に良いです！
https://ptr-yudai.hatenablog.com/entry/2020/09/07/020405

はじめに
[Crypto] rsa
[Crypto] QR
[Crypto] Curving Torpedo
[Crypto] Wilhelmina Says
Survey結果

[Crypto] rsa

from Crypto.Util.number import getStrongPrime, getRandomRange

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read(), "big")

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
c1 = pow(flag, e, n)
c2 = pow(p + q, e, n)
c3 = pow(p - q, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")

とてもシンプルなRSAの問題です。 $(p+q)^e \mod n, (p-q)^e \mod N$ が与えられているのが特徴的で、ここからp, qを復元してflagを求める問題だと推測できます。 $(p+q)^e \mod N$ を展開した形を考えると、 $\binom{0}{e} p^e + \binom{1}{e-1}p^{e-1}q + \dots + \binom{e-1}{1}pq^{e-1} + \binom{e}{0} q^{e} \mod N$ という形になりますが、 $pq$ を因数に含むような項はすべて0になりますから、結局 $(p+q)^e \equiv p^e + q^e \mod N$ となることがわかります。同様に $(p-q)^e \equiv p^e - q^e \mod N$ ですから、 $c_2 + c_3 = 2p^e \mod N$ であるということがわかります。 $p^e \mod N$ と $N$ はどちらも因数として $p$ を持ちますから、 $\gcd(c_2 + c_3, N) = p$ となることが期待できます。

RSAの簡単な問題で、かつ発展的な問題に応用できる手法を用いたものを出題しようと思い、このような形になりました。pやqに関連する値をRSAで暗号化するような問題に出会ったときは、十中八九GCDで素因数を取り出すような問題ですし、他の形でも式変形を用いてGCDでp, qを得るという形はよく見かけるので、憶えておくと良いと思います。

[Crypto] QR

import qrcode

with open("flag", "r") as f:
  flag = f.read().strip()

qr = qrcode.QRCode(border=0)
qr.add_data(flag)
qr.make(fit=True)

matrix = qr.get_matrix()
matrix2 = [ [0 for _ in range(len(matrix) - 1) ] for _ in range(len(matrix) - 1)]

for y in range(len(matrix)-1):
  for x in range(len(matrix)-1):
    matrix2[y][x] = (matrix[y][x] + matrix[y+1][x] + matrix[y][x+1] + matrix[y+1][x+1]) % 4

print(matrix2)

とてもシンプルなQRコードに関する問題です。某コンテストの影響か、一部の方には日本のCTF＝QRコードのような印象があるようで、QRコードに関する問題を出題しないと楽しめない、また、過去のCTFのアンケート結果などを見ていると、ただ手を動かすだけで解ける問題あったほうが楽しいという方がいらっしゃるようなので、「こういう問題好きでしょ？」という形で出題しています*1。ただ、それでつまらない問題を出してはひどいですから、できるだけ綺麗な形に落とし込めるように努力しました。

解法ですが、こんなものはz3にでも食わせておけばよいでしょう。z3はとても優秀なので人が手や頭を動かさなくても良くなります。

from z3 import Solver, Int, Or, sat
import ast

matrix2 = ast.literal_eval(open("output.txt").read().strip())
solver = Solver()

matrix = [[ Int("{}_{}".format(x, y)) for x in range(len(matrix2) + 1)] for y in range(len(matrix2) + 1)]

for y in range(len(matrix)):
  for x in range(len(matrix)):
    solver.add(Or(matrix[y][x] == 0, matrix[y][x] == 1))

for y in range(len(matrix2)):
  for x in range(len(matrix2)):
    solver.add( matrix2[y][x] == (matrix[y][x] + matrix[y+1][x] + matrix[y][x+1] + matrix[y+1][x+1]) % 4)

r = solver.check()
if r != sat:
  print(r)
  quit()

m = solver.model()

output = ""
for y in range(len(matrix)):
  for x in range(len(matrix)):
    if m[matrix[y][x]].as_long():
      output += '\033[0;37;47m  '
    else:
      output += '\033[0;37;40m  '
  output += '\033[0m\n'

print(output)

[Crypto] Curving Torpedo

from params import p, a, b

EC = EllipticCurve(GF(p), [a, b])
order = EC.order()

with open("flag", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")
    assert flag < order

G = EC.random_point()

print(G.xy())
print((flag * G).xy())

for i in range(10):
    x = randint(2, order-1)
    print((x * G).xy())

とてもシンプルな楕円曲線の問題です。楕円曲線のパラメータは一切与えられておらず、代わりに $G$ と $flag*G$ の他にランダムな10点が与えられています。実は楕円曲線上の点が6点もあればその楕円曲線のパラメータを求めることができるので、まずは楕円曲線のパラメータを求めてみます。方針としては、演算を駆使して

まず、楕円曲線上の点 $(x_i, y_i)$ について、次のような等式が成り立っています。

$x_i^3 - y_i^2 = k_i p - Ax_i - B$

3点 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$ について、この等式同士の引き算を考えてみると、定数項である $B$ を消すことが出来ます。

$(x_1^3 - y_1^2) - (x_2^3 - y_2^2) = (k_1 - k_2)p - (x_1 - x_2)A \triangle$ $(x_2^3 - y_2^2) - (x_3^3 - y_3^2) = (k_2 - k_3)p - (x_2 - x_3)A \square$

さらに、 $\triangle(x_2 - x_3) - \square(x_1 - x_2)$ を計算すると、 $A$ の影響も消すことが出来ます。計算を丁寧に追うのは大変（texを書くのが）なのでここでは省略しますが、最終的に $p(k_1x_2 - k_1x_3 + k_2x_3 - k_2x_1 + k_3x_1 - k_3x_2)$ という形になります。これをもう3点に対しても行い、GCDを取ると $p$ が得られます。 $p$ がわかれば、あとは $\triangle$ などの式から $A$ を求めるのは簡単ですし、 $B$ も難なく得ることが出来ます。

というわけで楕円曲線のパラメータを得ることが出来ました。そしてここからいかにして離散対数問題を解くか、というのが楕円曲線に関する問題で多く問われるところですが、今回の場合は楕円曲線の位数が小さい素数の積で表せることに気がつけば、Pohligh-Hellmanを用いて簡単に解くことが出来ます。

楕円曲線に関する問題で、かつ「やるだけ」ではない問題を出題しようとしてこのような格好になりました。前半の楕円曲線のパラメータを求めるパートは調べて答えそのものがあるようなものではないので、自分で数式と格闘しながら少しずつ答えに近づく必要があります。このような場合は、まず未知変数を減らす、あるいは未知変数のうちいくつかがわかっているとして、残った変数をどのように求めるか、というところから考えていくと手を進めやすい印象があります。後半はいわゆる典型というやつで、もうPohligh-Hellmanがそのまま出題されるような時代ではないですが、これをサッと解けるようになっておくと有利だと思います。

この問題はrsaやQRに比べると格段に難しくなりました。中程度の難易度の問題が間にあればより良かったのですが、そのような問題をうまく配置するのは難しいですね。

[Crypto] Wilhelmina Says

from Crypto.Util.number import getStrongPrime
import random

p = getStrongPrime(512)

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read().strip(), "big")
  assert flag < p

t = flag.bit_length()
n = 5
k = 350

xs = [random.randint(2, p-1) for _ in range(n)]
ys = [x * flag % p for x in xs]
zs = [(y >> k) << k for y in ys]

print(f"{t=}")
print(f"{p=}")
print(f"{xs=}")
print(f"{zs=}")

Hidden Number Problemの定義をそのままコードに落とし込んだような問題です。特になんのひねりもないので、CVP、あるいはSVPを解くことで簡単に解けます。

import ast

with open("output.txt") as f:
  t = ast.literal_eval(f.readline().strip().split("=")[1])
  p = ast.literal_eval(f.readline().strip().split("=")[1])
  xs = ast.literal_eval(f.readline().strip().split("=")[1])
  zs = ast.literal_eval(f.readline().strip().split("=")[1])

n = len(xs)
k = 350

M = matrix(ZZ, n+2, n+2)
M.set_block(0, 0, p * matrix.identity(n))
M.set_block(n, 0, matrix(ZZ, 1, n, xs))
M.set_block(n+1, 0, matrix(ZZ, 1, n, zs))
M[n,n] = 1
M[n+1,n+1] = 2^k

B = M.LLL()
flag = abs(B[0][n])

print(bytes.fromhex(hex(flag)[2:]))

最近何かと流行っているLLLを用いた簡単な問題ということでこうなりました。特に創意工夫が無いのが悲しいところですが、LLLに触れるきっかけとしては悪くないんじゃないかなと思っています

Survey結果

難易度やクオリティについて、かなり良い評価を得られたように思います。簡単すぎる、難しすぎるといったことなく、バランスの取れた問題編成なったのかなと。また、pwn / web / cryptoでソースコードを配布していたことが評価されていたので良かったです。以下アンケートを見ていて目についた意見についてです

Cryptoはソースコードがシンプルでコードリーディングが全く苦痛でなかった。それでいてそれなりに難易度の高い問題になっていてよかった
- まさに目指していたところがきちんと伝わっていて良かったです
easyやwarmup程度の難易度の問題には公式writeupがほしいです。次に活かすことができません
- 多分みんな書いてくれるし、問題と解法一式は公開されるので是非復習をしてください
Wilhelmina Saysがド典型
- はい……。HNPに関連する問題で難しくなりすぎず、典型すぎない問題を作れるように努力します

*1:当然、CTF面白い問題が出題されていればよく、それがQRコードに関係しているかどうかはどうでも良いことです。また、一参加者として「QRコード問題があるほうが嬉しい」「ひたすら手を動かすと解ける問題がある方が嬉しい」という感想を持つことは何ら悪いことではなく自然なことです。同様に勝手に辟易してひねくれた設定の問題を出題するのも、その問題が面白く、良いものであれば何ら問題になりません

ふるつき

v('=')v かに