ふるつき

v(*'='*)v かに

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

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がそのまま出題されるような時代ではないですが、これをサッと解けるようになっておくと有利だと思います。

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

[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コード問題があるほうが嬉しい」「ひたすら手を動かすと解ける問題がある方が嬉しい」という感想を持つことは何ら悪いことではなく自然なことです。同様に勝手に辟易してひねくれた設定の問題を出題するのも、その問題が面白く、良いものであれば何ら問題になりません

SECCON 2020 Online CTF作問者writeup

今年は決勝がなかったSECCON CTFですが、Quals相当のCTFはSECCON 2020 Online CTFとして開催されました。嬉しいことに作問をやりませんか? と誘っていただけて、cryptoの問題3問を提供しました。この記事には作問者お気持ちと想定解法を書きます。CTF全体に関するよしなしごとはtwitterとかに書いてます。

koharu (144points / 44 solves)

gist.github.com

多項式環の上でGoldwasser-Micaliをしているだけの問題です。Goldwasser-Micali cryptosystemはInterKosenCTF 2020でも出したので大好きマンみたいになってしまった……。

irreducibleな P, Qがそんなに大きくないので、sageで雑にfactorメソッドを呼べば N素因数分解することができます。あとは問題のスクリプト中にもあるように X^{(p^{|f|}-1)/2} \mod fという式で、ある式 fを法とした時に Xがquadratic residueか否かを判断することができるので、これを使って愚直に復号を行うだけです。

gist.github.com

もともとは多項式体上でquadratic residucityを求められますか? という問題にしたかったはずがうまく形に出来ず、結局題意が「多項式体上でもquadratic residuicity checkができるんですよ、おもしろくないですか? あ、そういえば多項式 Nが弱いと因数分解できるのが問題です」というなんとも中途半端な形になってしまいました。 個人的には不完全なまま時間に追われてこの問題を出題してしまい、実は結構悔いています。

問題名、問題文とフラグはアイドルマスターシンデレラガールズに登場する古賀小春ちゃんとそのペット、ヒョウくんから。polyとperoのフィーリングでヒョウくんぺろぺろを思い出したので。

ところで因数分解しなくても通せるらしいです。全然検証していませんでした。ごめんなさい……

qiita.com

urara (240pts / 14solves)

gist.github.com

出題したなかでは一番にお気に入りの問題です。 \mod nをもってきて、楕円曲線RSAでそれぞれ平文を暗号化しています。楕円曲線の方は C_{EC} = 2 * (m, y)で、RSAの方は C_{RSA} = (m + t)^{e} \mod nです。

変数 Xを用意しておいて、楕円曲線上の2倍公式に基づいて x(C_{EC}) Xとの間の関係式を作った上で、  (X + t)^{e} - C_{RSA} と比べると、どちらも mが根になるため式 X-mで割り切ることができ2式のGCDを取ることで \mod nで等しい式が得られ、あとはいい感じにするとフラグが得られます。

gist.github.com

もともとはもっとくだらない問題にするつもりだったけど、試行錯誤しているうちになんかいい感じになりました。問題も解法もすっきりとかけて、かつ多少の非自明感があってとても良い問題だとおもいます。同じSECCON 2020 Online CTFで出題されたsharsableも問題を見た時感動しましたが、この問題もタイマンを張れるかなと。

問題名、問題文とフラグはうらら迷路帖から。最近漫画の方を読みましたが、良いですね。作中で楕円曲線占いが登場しなかったのが不思議でなりません

また、非想定解として2倍公式から頑張ってcoppersmithで剰余方程式を解くことでも解けるようです。こちらは最終的には想定解に近い解き方になりますが、パラメータ次第では本当に問題として壊れていたかも知れませんね。フラグは十分な長さになるようにパディングをつけましょう。

crypto01 (393pts / 4solves)

gist.github.com

結局これがcryptoとしてはボス問となりました。この問題はこの論文 を発見して理解して実装すれば解けます*1。それ以外にあんまり説明するところはありません。素因数 pのbitの一部を渡しているので、これをうまく使って力任せ素因数分解……することができたかもしれません。多少調べた感じでは出来ないと思いますが、あまり自信がないです(そのせいで問題のインスタンスを3つも用意している)。

gist.github.com

当初はsagemathのsmall_rootsでうまく求解出来ずに困っていましたが、後でとにかくepsilonを小さい値にしておけばなんとかなるということがわかり出題できるようになりました。うまいパラメータを見つけることができればさほど時間をかけずに解けます。

問題名、問題文とフラグは仮面ライダーゼロワンから。名前を考えるのが面倒でcrypto01という仮名を置いていたところ、急にゼロワンの存在を思い出して、この作品について唯一しっている腹筋崩壊太郎をフラグにしました。

*1:そういうわけで問題としては少し気に入らない感じがあります

TokyoWesterns CTF 6th 2020 writeup - XOR and shift encryptor

#!/usr/bin/python3

s = []
p = 0

def init():
  global s,p
  s = [i for i in range(0,64)]
  p = 0
  return

def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1) & 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res

def jump(to):
  # Deleted...
  return

def check_jump():
   ...

check_jump()

init()
for a in range(31337):randgen()

flag = open("flag.txt").read()
assert len(flag) == 256

enc = b""

for x in range(len(flag)):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ])
  print ("%r" % enc)

open("enc.dat","wb").write(bytearray(enc))

The given python script implements a random number generator like xorshift but 64 internal states. The script requires to generate number quite a lot of times and define utility to do it jump. But it is deleted, so our purpose is to implement a fast jump function.

So, in such a case, we want to use the mathematical tool recurrence formula and matrix exponentiation. If we could show the xorshift algorithm as the recurrence formula and accumulate them into the matrix multiplication, it becomes very easy to repeat.

For this purpose, we are thinking of the  GF(2) and make each state a vector who has 64 elements. On the  GF(2), XOR operation is equivalent to the addition. As treating each state as the vector, we can use matrix operation to update all states at once.

Luckily, knowing the matrix means the left/right shift operation, we can write down all operations about xorshift in the matrix context. For example, updating s1 is shown in the following, where  L_x means x bit left shift matrix and  R_x means right shift matrix.

 s_1' = (s_1 + s_1L_a) + s_0 + (s_1 + s_1L_a)R_b + s_0R_b
 = s_0(I + R_c) + s_1(I + L_a + R_b + L_aR_b)

Now nothing is hard. The following formula updates internal states simultaneously.

 \begin{pmatrix} s_1' \\ s_2 \\ \vdots \\ s_{63} \\ s_0 \end{pmatrix}^t = \begin{pmatrix} s_0 \\ s_1 \\ s_2 \\ \vdots  \\ s_{63} \end{pmatrix}^t  \begin{pmatrix} I + R_c & O & \cdots & O & I \\ I + L_a + R_b + L_aR_b & O & \cdots & O & O \\ O & I & \cdots & O & O \\ \vdots & & & & \vdots \\ O & O & \cdots & I & O  \end{pmatrix}

In this form, multiple times update can be shown using the matrix exponentiation. Let the above formula as  s' = sM. For example, jump(n) is made by  s' = sM^n.

So now, we can easily implement jump using the matrix form of xorshift. As the large size (642 * 642) matrix, the calculation is heavy. However, this method is faster than in other ways. On my laptop, 30minutes - 1hour to finish and yield all the keys by the following script.

gist.github.com

reference: TinyMTの更新を行列で書いてみようのコーナー(前編) - yatsuna_827’s blog