ふるつき

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

InterKosenCTF 2020 作問writeup

f:id:Furutsuki:20200907091058p:plain

どうも、非想定解太郎と申します。InterKosenCTF 2020 に出題した問題の題意や解法についての記事です。

出題された問題はこちらのリポジトリから見ることができます。

github.com

ptr-yudaiの作問writeup記事

ptr-yudai.hatenablog.com

[web] matsushima2 (121pts / 46 solves)

SECCON 2018 Finalで出題された松島、という問題が強烈に印象に残っていたのでオマージュ問題です。松島はポーカーだったので、ではということでブラックジャックを実装して*1その後で脆弱性を決定しました。

f:id:Furutsuki:20200907091628p:plain
トランプ頑張って書いた。ptr-yudaiのアイコンむずかしいです

この問題はJWTで状態(スコアや使ったトランプ)を維持しているのですが、過去のCookieを保存しておいて負けたら巻き戻すということをやると負けをなかったことにして勝つまで試行することができます。という簡単な問題でした。

かなり簡単でwarmupにふさわしい難易度、解かれ具合だと思います。

ptr-yudaiによるwriteup

hackmd.io

[web] miniblog (353pts / 14 solves)

Webはよくわからないのでとりあえず脆弱性から決めようと思ってSSTIでRCEをすることに決めました。テンプレートがインジェクションできる状況を都合よく作るためにファイルアップロード時のtarの解凍時のzip slipのような脆弱性を使ってもらうことにしました。問題をちゃんと読めばある程度やることはわかるんじゃないかなと思っています。

ただ、テンプレートをエディットできるということで'{%'のようなパターンは正規表現で弾いていたのですが、途中に改行文字を挟むことでこのチェックをすり抜けることができてしまいました。甘かったです……。

また、問題公開時はtypoによりマルチスレッドが有効になっておらず、問題サーバが重たくなってしまって競技者の皆さんにはご迷惑をおかけしました。

ptr-yudaiによるwriteup

hackmd.io

[web] just sqli (383pts / 11 solves)

問題名の通り、ただSQL Injectionをするだけの問題です。miniblogよりはかなり簡単だと思うのですが、問題公開のタイミングなどもあってsolve数は思ったほどではなかったですね。この問題では自明なSQL Injectionが存在しているのですが、SELECT だけは正規表現で弾かれています。問題の要求を考えるとUNION SELECTをして行を追加したいところなのですが、SELECTが使えないと困ってしまいます……というところで sqlite.org を見に行くと、UNION VALUES (v1, v2, ...) という記法が使えることがわかり、解けます。

何かSQLの面白い仕様を使った問題が出来ないかと考えてドキュメントを見ていたら知らない仕様に出会ったので問題にしました。今回はSELECTが使えない状況でしたが、同様の要求に対して、UNIONを使わずに解く方法がないか模索中です。

ptr-yudaiによるwriteup

hackmd.io

[reversing] harmagedon (182pts / 36 solves)

かなり良く解かれた問題です。ただコンパクトなバイナリがあって、アセンブリをちゃんと読むと4分木を辿ってあるノードにたどり着けるような経路を見つければ勝ちです。想定解法は4分木を葉から根に向かって辿るだけ、という感じでしたが、全探索でも解けるようです。

もともとはもっと大きな、それこそGB単位のバイナリでptr-yudaiに怒られたので頑張ってコンパクトにしました。それっぽい文字列を作るように選択肢を選んでも解けないことはないと思いますが、Ruktun0rDi3 をそれっぽいと感じるのはむずかしいと思います。これは問題を作っているときに平沢進にはまっていたせいでこういう名前になりました。

ptr-yudaiによるwriteup

hackmd.io

[crypto] ciphertexts (201pts / 33 solves)

Cryptoのwarmup問題です。かなり簡単にしたつもりでしたがharmagedonやlimitedよりも全然解かれていないんですね。

問題は単純で、 n_1 = pq, n_2 = pqrというようにそれぞれの剰余でフラグをRSA暗号化しただけです。RSA暗号運用でやってはいけない n のこと #ssmjp を読んでいれば、 n_2' = pqとしてCommon Modulus Attackをすれば良さそうということがわかりますし、あるいは r = n_2 / n_1を求めてから d \equiv e^{-1} \mod pとして [tex: cd \mod r] を計算することでもフラグが得られそうだとわかります。

ptr-yudaiによるwriteup

hackmd.io

[crypto] bitcrypto (326pts / 17 solves)

xorに関する準同型性という珍しい性質を持つ、Goldwasser-Micali cryptosystemに関する問題ですが、多くの方はこの暗号の名前にはたどり着かずに自力で暗号を解析してそのような性質があることを突き止めたようです。解法は簡単で最初に短いとはいえ好きな文字列を暗号化してくれるので、これで0, 1に対応する暗号文を手に入れて準同型性を使って0, 1に対応することなる暗号文を量産するだけです。量産はわりと雑にできるので、解けるなら何でも良いと思います。

ただしこの問題にも非想定解、というか作問ミスがありました。問題中では len(m) > 8 となるような入力に対してエラーを返すことで送った文字列を並び替えて暗号文を作る、ということを禁じたのですが、少ない文字数で多くのバイト数を持つ、非asciiな範囲の文字列を送ることでチェックを無効化できたようです。ごめんなさい。

yoshikingによるwiteup

hackmd.io

[crypto] padding oracle (326pts / 17 solves)

最近ではPadding Oracle Attackもptrlibに収録されるなどして解きやすくなっていますが、原理を理解していますか、という問題です。 Padding Oracle Attackを用いるような問題で使われているパディング方法は PKCS#7 というやつですが、 PKCS#7 では末尾に与えられるパディングがこの問題では先頭につく、という改変を加えています。これで特に難しくなるということはなく、通常のPadding Oracle Attackでは後ろからやっていたことを、前からやるように組み替えるだけで解けるのですが、苦戦された方もいたようです。

サーバが遠い場所にあってネットワークが遅くなりがちなのにタイムアウトを短く設定していたり、平文を長くしていたりして、すみませんでした*2

yoshikingによるwriteup

hackmd.io

[crypto] padrsa (426ps / 7 solves)

cryptoのボス問題のつもりで作成しましたが、作問ミスによりそんなに難しくなかったようです。問題としては、平文にパディングを付与してRSA暗号化することでhastad's broadcast attackのような手法を抑止しているというものです。ただ、paddingが小さいので小さい平文を小さいeで暗号化してもらえばsmall public exponent attackでpaddingに使われている乱数を求めることができ、Franklink-Reiter Related Message Attackが適用できるようになります。

というのが想定解法でしたが、パディングの作り方が雑だったこともあり、128回ほど暗号化をした場合にパディングに乱数の影響が現れず、hastad's broadcast attackが成立してしまっていたようで、主にこの方法で解かれていたようでした。これならまあ謝ることはないのでしょうが、個人的には手痛いミスです。

ptr-yudaiによるwriteup

hackmd.io

作問の感想・反省

自信をもって面白い問題を作っていたつもりで、その実作問ミスや非想定解がぽこぽこ見つかるのは本当に滑稽で、思い込みの激しさやチェックの杜撰さが露わになった感じがあります。ただ、作問ミスでこんなに凹んでいるのも私だけで、評価としては概ね良かったのもなんだかもにょっとしています。

*1:ルールを遵守するつもりもないので同点だと負けになります

*2:これに関する苦情がみられないんですが本当ですか?

InterKosenCTF2020 開催記

 もう高専に何を感じることもなくなったけど、今年もInterKosenCTFを開催しました。一昨年、去年に続いて3回目の開催になります。過去の開催では高専生向けの開催を行っていましたが、今年は初級〜中級程度のCTFプレイヤー向けとして開催しました。これには、そもそも高専生向けというと対象が狭すぎて参加者があまり見込めないとか、なんだかんだと言って此れまでの開催でも非高専生の参加者にも楽しんでもらっていたとか、今年は高専セキュリティコンテストもなさそうな雰囲気であるとか*1、最初にも言ったけど高専に対して何ら感じるところがなくなったとかの理由があります。それでも"InterKosenCTF"という名前で開催したのは、2年と短くはあるものの、一応のブランドとしての"InterKosenCTF"が存在したこと、kosenctf.com というドメインを持っていたのでまあそれなら……ということが理由です。

 さて前置きが長くなりましたが、今回も日記・自分用記録を兼ねてInterKosenCTF回りで考えたこと、感じたこと、目指したこと、行ったことなどを述べていきます。

InterKosenCTF 2020

2020年9月5日 10時00分 〜 2020年9月6日 22時00分 までの36時間、 insecure(ptr-yudaiyoshiking)としてInterKosenCTF 2020を開催しました。1ポイント以上獲得したチームは133チームで、1ポイント以上獲得した個人は188名でした。ご参加頂きありがとうございました。

f:id:Furutsuki:20200906223509p:plainf:id:Furutsuki:20200906223538p:plain
f:id:Furutsuki:20200906223503p:plainf:id:Furutsuki:20200906223505p:plain

作問に関する振り返りと反省

 今年はWelcome / Survey 問題を含めて 25問、除くと23問を作成・出題しました。去年が22問だったので大体同じようなバランスです。今年は特に幅広い難易度、ジャンルで良い問題を作ることを心がけていました。良い問題というのはコンセプトが素直に提示されている問題、一筋縄では解けないような問題や、ちょっとマイナーな知っていると面白いような知識を要求される問題などで、かつ問題が台無しになるような非想定解が存在しないものです。逆にひたすら実装を面倒にした問題やあまりに「やるだけ」の問題等は、作問・レビューの段階でできる限り弾く努力をしてきました。その甲斐あって、いろんな層の人が問題を解く楽しみを感じることができ、また何か少しでも実力に繋がるような問題セットを提供できたと思っています。

問題の管理・チェック

 作問の管理には今年もHackmdを使っていたのですが*2、今年はなんとなくのジャンル感と難易度感を表形式で管理してみました。これはなかなか良かったと思っていて、どんな問題が足りていないかということがある程度把握でき、また作問はしたもののレビューを受けていない問題がひとめでわかります。

f:id:Furutsuki:20200906192213p:plain
問題の管理を行っていた表。難易度感は自己申告なのでちょっと低めに出ていた

問題のレビューは「その問題が解けること」「適切な難易度であること」「出題の基準に沿っていること」を確認しつつ「非想定解があれば指摘する」「権限まわりなどのミスを指摘する」ことを目的としています。担当外のジャンルのレビューをすることになるのでヒント等をもらうことはあっても用意された解法は見ずに、できるだけフラットな視点で問題に取り組むように注意していました。実際に権限の不備や非想定解の発見、問題のrejectがそれぞれあり、レビューの重要性が明らかでした。まあそれでも非想定解は残っていたんですが……(後述)。てかめっちゃ残ってましたね。チェックは何重にも行ったほうが良いです(教訓)

難易度表記の非採用

 今回は内部ではある程度の難易度の推定を行ってはいましたが、スコアサーバでは難易度に関する表記は行わないことにしました。これはそもそも難易度の推定が難しいから動的配点を導入しているのに、難易度の表示自体はされるのはちょっとずれているのではないかという考えと、難易度表記に惑わされず、フラットな姿勢で問題に挑戦してほしいという考えによるものです。ただ、初心者のプレイヤーがそれで一問も解けない、あるいはいきなり難しい問題に挑んでしまって心折れる、ということがないようwarmup, lunaticのタグの表記は行いました*3。これが結果として良かったのかどうかはきちんとはわかりませんが、悪くはなかったような気がしています。ただやはり、公開が遅い問題はsolve数が伸びない傾向にあるようで、それほど難しくない問題がなかなか解かれずに残っているということがありました。それでも全ての問題が公開されてからCTFが終了するまでに24時間はあったので、ある程度均されてはいきました。

非想定解: miniblog

 また非想定解を作ってしまいました。しかも前回のInterKosenCTFでの非想定解と同じです。また、正規表現でフィルタしている部分を改行文字を挿入することで突破できる非想定解を作りました。どの程度この非想定解が使われていたのかはちょっとわからないし調査をするつもりもあんまりないですが、問題の一段階をすっ飛ばすことができ、想定解法との難易度が大きく変わってしまいました。本当に反省しています。どうして学習しないのか……

非想定解: bitcrypto

pythonで文字列長を見てバイトで扱うときは非ascii文字をかんがえましょう。ごめんなさい

非想定解: padrsa

boss問題のつもりで出したのに非想定解を入れました。ごめんなさい

反省: miniblog

 もう一つminiblogについてです。typoがあり、サーバのスレッド化が行われておらず、問題のレスポンスがとても悪くなり解けない状態が出来てしまいました。幸い、ガチャガチャやって治して、そんなにダウンタイムがあったわけではなかったのですが、反省にはかわりありません。

CTFプラットフォームに関する振り返りと反省

雑に言うと私はLMTとかではないので限界があるし、実力不足を痛感しました。あれやこれや、やりたいことはあったんですが結局最低限の環境になりました。

スコアサーバ

 また作りました。懲りないので。もう作りたくないと毎度思いながら、次回また作っている。毎回作ってしまうことには反省しかありません。今回のスコアサーバはzer0ptsCTF 2020で作ったサーバをベースに作ったので作業量がそう多くはなかったとはいえ、やはり大変でした。zer0ptsCTFではファイルディスクリプタのクローズ漏れからサーバが数時間程度で落ちてしまう問題がありましたが、今年はwebsocketではなく定期的なポーリング + redisによるデータのキャッシュを行うことにしてリアルタイム性、レスポンス速度を保ちながら負荷軽減とバグの解消を試みました。結果として情報はほとんど最新のものが得られ、安定して稼働する良いサーバになったのではないかと思っています。問題の表示方法や見た目についてはアンケートにご意見をいくつかいただきましたので、次回のCTFでは改善していきたいと思っています。

DigitalOcean

 これまでのCTFではAWSを使っていましたが、今年は3kCTFの賞品でDigitalOceanで使えるcreditを$100程度いただきましたので、これと、初回登録時にもらえる$100を使って、DigitalOcean環境でサーバやデータベースをホストしていました。AWSにはあったあれこれがDigitalOceanにはない、DigitalOceanのコンソール時々挙動がおかしいことがある等の苦しみはありましたが、概ね問題なく使うことが出来ました。はやめに対処して置かなければならないのが作成できるDroplet数の制限で、初期では3台までしか作成できない上、上限引き上げに際してはフォームに申請を行わなければならず、面倒です。

 ちなみにDigitalOceanでなくて困ったものはFargate相当のもの(Kubernetes Clusterは作成できますがそうではなく、あくまでFargateを求めていました)、Cloudwatch Logs相当のもの(各インスタンスのネットワーク、CPU使用率などを一覧できないのは厳しいものがありました)、Spaces + CDNにおいて、デフォルトで用いられるファイルの指定ができないこと(URLの末尾にindex.htmlがつくのがとても格好悪かったです)、日本リージョンがないことです。

デプロイ方法

 これまでのdocker-composeの資産を活かしつつ、リクエストを分散できる、ということでdocker swarmのclusterを構築してそこにdocker stack deployをしていくような仕組みを構築していたのですが、overlay networkをうまく作れなかった、パケットを上手にキャプチャできなかった等の理由から開催の前日か前々日くらいに没にして、結局これまでどおりいくつかサーバを建てて、そこに問題リポジトリをクローンしてきて手動でdocker-compose up -dをする方法を取りました。なんだかんだでこれが一番安定している気がします。

solvability check

f:id:Furutsuki:20200906203621p:plainf:id:Furutsuki:20200906203738p:plain

 SECCON Beginnersで導入されていた、問題が解けるかどうかの自動チェックが良かったので真似をしようという話になりましたが、きちんと実装するのは大変だったので、サーバでdocker-compose run solve を回しては5分休むようなスクリプトを書いてお茶を濁しました。問題が解けない状態になっていると、discordに通知が飛びます。解ける状態になっていることが確認できたときは、admin専用のチャンネルに通知するようにしました。感想としてはSECCON Beginnersで行われていたように、何度か失敗したときに通知するようにしないと、確率で失敗するエクスプロイト(特にpwn)では、問題は正常に稼働しているのにアラートが飛んできてしまうな、ということと、チェックに失敗した後、復旧したことも通知する必要があるな、ということでした。これらは当然の話で、事前のテストの不足が伺えます。ただ、やはり自動でsolverを回してくれるというだけでもかなり便利で、時折不安になって自分でソルバを回すという手間がなくなったのは良いと思いました。solvability checkの仕組みは今後もきちんと整えて運用できるようにしていきたいところです。

競技前〜競技中の行動に関する振り返りと反省

スコアサーバ公開とか宣伝とか

ptr-yudaiの要請もあり、少し早めに、開催1週間ほど前からスコアサーバを公開していました。が、結局登録があるのは前日夜とか当日とかで、それまでは登録チーム数はあまり伸びず、このままでは参加者が少なく、盛り上がりにかけたCTF担ってしまうのではという恐怖がありました。そのせいもあってTwitterで少しうるさくなってしまったのは大変申し訳無く感じています。

このCTFはカジュアルなCTFということもありctftime.org には登録していなかったので、それも参加者が増えなかった要因であるとは思うのですが、twitter以外の宣伝の手段をとれなかったのも問題だなと思っています。とはいえtwitter以外でどのような手段で、どのような層に宣伝すればよかったのかは全然わからないのですが……。

競技中

私、ptr-yudai、yoshikingの3人だけで運営を回していたこともあり、とても忙しく、とくに序盤は神経を使いました。スケジュールに合わせて問題を公開し、アナウンスをし、サーバが落ちていないか確認をしたりトラフィックを見たりして過ごしました。Discordのctf-logというチャンネルではだれがどの問題を解いた、という情報が流れるのですが、Fisrt, Second, Third bloodについては、それぞれ金・銀・銅メダルの絵文字をつけたりしていました。特に事前打ち合わせをしていたわけではないのですがなんとなく運営みんなこれをやっていて、参加者からも盛り上がってよかったと概ね好評だったようです。

f:id:Furutsuki:20200906205313p:plain

その他には、Twitterで関連するツイートをサーチしてRTしたりもしました。これは割りとカジュアルなCTFだからこそ、という感じですね。Twitterは趣味みたいなものです。

問題に関する質問はほとんどありませんでした。これは日本人の気質という所もあると思いますが、楽でした。

総括等

 CTFの運営は楽しいですが、つかれます。やはり3人でCTFを回すのは正気の沙汰ではないような気がしますね……。CTF自体はとても楽しいので続けると思いますし、ptr-yudaiがいる限りは安心してもらって良いですが、この体制で続けるかは今の私にはわかりません。InterKosenCTFという名前は少なくとも消えて別の名前になると思います。それでは、またどこかのCTFでお会いできると嬉しいです

*1:去年の開催記を見直していたら、去年もあるかどうかわからないけど……と言っていた

*2:というかCTFに関するドキュメントはだいたい全部Hackmdで管理しているのですが

*3:難しい問題を表すのにlunaticを使っているのは以前からで、理由はなんとなく格好良いからです

3kCTF 2020 writeup

We got 1st place!! Thanks to all the admins for holding a good competition.

f:id:Furutsuki:20200726110824p:plain

overall challenge files and scripts are here

[rev/misc/crypto] pyzzle1/2

The given file pyzzle is an AST produced by libCST. @st98 found a way to recover it into python script.

from libcst import *

with open('pyzzle', 'r') as f:
  program = f.read()

cst = eval(program)
with open('original.py', 'w') as f:
  f.write(cst.code)

The logic of a recovered script file was quite simple. It did just XORing.

import binascii

plaintext = "REDACTED"

def exor(a, b):
    temp = ""
    for i in range(n):
        if (a[i] == b[i]):
            temp += "0"
        else:
            temp += "1"
    return temp


def BinaryToDecimal(binary):
    string = int(binary, 2)
    return string

# encryption
PT_Ascii = [ord(x) for x in plaintext]

PT_Bin = [format(y, '08b') for y in PT_Ascii]
PT_Bin = "".join(PT_Bin)

n = 26936
K1 = '...'
K2 = '...'

L1 = PT_Bin[0:n]
R1 = PT_Bin[n::]

f1 = exor(R1, K1)
R2 = exor(f1, L1)
L2 = R1

f2 = exor(R2, K2)
R3 = exor(f2, L2)
L3 = R2

R3 = '...'
L3 = '...'
cipher = L3+R3

So decryption was also simple.

from params import K1, K2, L3, R3
from Crypto.Util.number import *


def exor(a, b):
    temp = ""
    for i in range(n):
        if (a[i] == b[i]):
            temp += "0"
        else:
            temp += "1"
    return temp

n = 26936

# L3 = R2 = f1 ^ L1 = R1 ^ K1 ^ L1
# R1 = f2 ^ L2 = (R2 ^ K2) ^ (R1) = (f1 ^ L1) ^ K2 ^ R1 = (R^1 ^ K1) ^ L1 ^ K2 ^ R1 = K1 ^ K2 ^ L1
L1 = exor(exor(R3, K1), K2)
R1 = exor(exor(L3, K1), L1)

plaintext = long_to_bytes(int(L1 + R1, 2))
with open("plaintext", "wb") as f:
    f.write(plaintext)

The first flag was in the comment section of plaintext: 3k{almost_done_shizzle_up_my_nizzle}.

The plaintext was the STP format file. It had the edges and vertices with its coordinates. Let's draw them on the canvas.

from PIL import Image, ImageDraw

lines = open("plaintext2.stp").read().strip().split("\n")
points = {}
for line in lines:
    if not line.startswith("DD"):
        continue
    _, idx, x, y = line.strip().split(" ")
    points[int(idx)] = (int(x), int(y))

img = Image.new("RGB", (2200, 200))
draw = ImageDraw.Draw(img)

for line in lines:
    if not line.startswith("E "):
        continue
    _, p1, p2, _ = line.strip().split(" ")
    p1 = points[int(p1)]
    p2 = points[int(p2)]

    draw.line([p1, p2], fill=(255, 255, 255), width=1)

img.save("flag.png")

f:id:Furutsuki:20200726112229p:plain

[rev] microscopic

There is a key checking logic in the sub_F7C. It is straightforward, requiring that (len(input) ^ input[i]) + i == bss_0x202020[i].

xs = [0x14,0x4D,0x5E,0x4C,0x4A,0x4E,0x1D,0x51,0x56,0x5C,0x4C,0x5F,0x84,0x4F,0x5F,0x51,0x65,0x6F,0x62,0x62,0x56,0x6A,0x58,0x8F,0x5A,0x6A,0x5C,0x70,0x7A,0x70,0x6C,0x69,0x62,0x99,0x63,0x76,0x74,0x2B,0x80]
l = len(xs)
ys = []
for i, x in enumerate(xs):
    ys.append(chr(x - i ^ l))
print("".join(ys))

[rev] Passage

The binary is based on the printbf. So I dumped brainf*ck instructions from memory and decode by the following script.

import collections

lines = open("instructions").read().strip().split("\n")
bf = ""
for line in lines:
    inst = int(line[-2:], 16)
    count = int(line[8:10], 16)

    if inst == 18: #A
        bf += "+" * count
    elif inst == 15: #B
        bf += "<" * count
    elif inst == 14: #F
        bf += ">" * count
    elif inst == 13: #Z
        bf += "[-]"
    elif inst == 12: #]
        bf += "]"
    elif inst == 11: #[
        pass
    elif inst == 10: #[
        pass
    elif inst == 9: #[
        bf += "["
    elif inst == 6: #.
        pass
    elif inst == 5: #.
        bf += "."

print(bf)

Then I got a brainf*ck script. I wrote a simple interpreter because printbf's behaviour is a bit of different to usual interpreter. By emulating the script, I found some ascii-range values on the memory. So I dumped it then I got the flag.

The following is the my interpreter and solution script.

import string

table = set([ord(c) for c in string.ascii_letters + string.digits + ' -{}_'])

pc = 0
ptr = 0
mem = [0 for _ in range(65536)]

jumplist = {}
code = open("code.bf").read().strip()
while pc < len(code):
    if code[pc] == '+':
        mem[ptr] = (mem[ptr] + 1) % 256

    elif code[pc] == '-':
        mem[ptr] = (mem[ptr] - 1) % 256

    elif code[pc] == '>':
        ptr = (ptr + 1) % 65536

    elif code[pc] == '<':
        ptr = (ptr - 1) % 65536

    elif code[pc] == '[':
        cnt = 0
        if pc not in jumplist:
            pc2 = pc + 1
            while True:
                if code[pc2] == ']':
                    if cnt == 0:
                        jumplist[pc2] = pc-1
                        jumplist[pc] = pc2
                        break
                    else:
                        cnt -= 1
                elif code[pc2] == '[':
                    cnt += 1
                pc2 += 1

        if mem[ptr] == 0:
            pc = jumplist[pc]
            print([chr(v) for v in mem if v in table])

    elif code[pc] == ']':
        pc = jumplist[pc]

    elif code[pc] == '.':
        pass
        # print(mem[ptr], ",", end="")

    
    pc += 1

import code
code.interact(local=locals())

[crypto] once upon a time

The given encryption program is based on https://github.com/MatthewDarnell/SCSS. The difference were:

  • delete decryption
  • redact initialize key

So our task is found a redacted key and decrypt using the referenced repository. The key wasn't in the source code but in the compiled binary. Just reverse it and decrypt by ofb mode, then we could get the flag: 3k{my_hands_are_registered_as_lethal_weapons_that_means_we_get_into_a_fight_i_accidentally_kill_you_i_go_to_jail}.

[crypto] You shall not get my cookies

Be careful that the banner's corner formed by pkcs7 (shit!). If you noticed that, just do the padding oracle encryption attack.

from ptrlib import padding_oracle_encrypt, Socket
from Crypto.Util.Padding import pad
from binascii import hexlify, unhexlify
from logging import getLogger, WARN

getLogger("ptrlib.pwn").setLevel(WARN + 1)

def decrypt(c):
    sock = Socket("youshallnotgetmycookies.3k.ctf.to", 13337)
    sock.sendlineafter("your cookie:", hexlify(c).upper())
    result = sock.recvline().decode()
    result = sock.recvline().decode()
    sock.close()
    if 'Nop' in result:
        return True
    elif "rude" in result:
        raise Exception("RUDE!!!")
    else:
        return False

plain = pad(b'Maple Oatmeal Biscuits', 16)
print(padding_oracle_encrypt(decrypt, plain, bs=16))

By the way, my network issue and physical distance make my script running over 1 hour.

[crypto] RSA textbook

The challenge is pretty similar to De1CTF 2020 - Easy RSA. The difference is d's bit length is a bit of long and three of e are given this time. The paper records the lattice when the three e are given.

from sage.all import *
from Crypto.Util.number import long_to_bytes
import gmpy2


N = 12170190688004538444277411858659743698858881698522002560104158646993985233366286537140023919311475138247627293483294012428391264973961998717641256731743650816966630823200651379840685959607068295100050560483372204779059185916233606668058455492543750789590662887744463330804561435647720395428571207395720326720079784739378979190536116850099548129878814526898868252532680831715727722854511143304480680172052813141124420045611849828057723775363105949126828405455366200106404262310675794659470280643495090398585218024841176044368628727517113941678716688564185680961627362553111203039001198980515164358280669308454156335407
e1 = 3608925965574376523567945341556278002516414013521504911184984382205274952167864225371696017993914370497201512168776166664088733042670271646970202280312387281923684119807730941123751515160638485698825644259362763695807647636424870261387602647920252532625627698043754500477196359587280636895393200790995388403075695605752313259071472848947759665811971017441614507395695166977173983209874826569262567456954762013063380865150534725774724048932079149474773099227628235894219595993039786915437293792843467687437824528953466687440976745496029400371187996064849843219741352701174026683144995955926404403452468786948428940027
e2 = 2705742985834249419593731294742640629063082486092845443539270908653438835415907814640922583157596954837534793829979420920198220583127130141172579878212440120192417321752335684151522579530049628576946957043579231780623871429784888205786958275264941043957214384797910571377927751881376467152335343819159923905777819744174333126671522426796324838179520524018483919571215970759256674475827355541411323954244780923617745270386685895731319052600788632072228874066127098381849641952288244849313571762646260481179154523761739298818111645172710767353435965052896552293260158397774508443428719331456374349726714924857674679205
e3 = 3035365189985498586303047048784147960258852204370735950376858958412525602591256013408704341559429814208409740880540723564047453268194004007025515302654689487102249859432374152268384575758806644375008555596328108954751739613261097357911851867276625220692495609283168900124098676799207897772849526250849182230188000946516269730320060104809776594584791996622731993896557212016228453224349936398794285686351250712690093264997448606619172537355077652043467103166971300884698914802166607190765845078412359425449726466096602648615851255067426028168676632944926874766408639251537680297862420982004104687562994618386282503979
c = 8428440225372437159697731953040047552034760946696949785472254831497076019605441760668381296291759447497600405504562269104549915534101891117092326606340168399884372637000427767246446007973335837452013998684912761764510307152056346432612919127031634162077989869360717849451315550957073076040273291239841901635055739913150280146317663383345358421035311465389299247093408775682992619258004736599439564552486105106585061374815530581898589428950106020942797612406757368312750240904783591854877330620611395246954169095417676892061171148418509328414536101813085141351870212082214659362996288288403303642365539978759986883582



alpha2 = 815./2048
M1 = int(gmpy2.mpz(N)**(3./2))
M2 = int( gmpy2.mpz(N) )
M3 = int(gmpy2.mpz(N)**(3./2 + alpha2))
M4 = int( gmpy2.mpz(N)**(0.5) )
M5 = int( gmpy2.mpz(N)**(3./2 + alpha2) )
M6 = int( gmpy2.mpz(N)**(1.+alpha2) )
M7 = int( gmpy2.mpz(N)**(1.+alpha2) )
D = diagonal_matrix(ZZ, [M1, M2, M3, M4, M5, M6, M7, 1])
B = Matrix(ZZ, [ [1, -N,   0,  N**2,   0,      0,      0,    -N**3],
                 [0, e1, -e1, -e1*N, -e1,      0,   e1*N,  e1*N**2],
                 [0,  0,  e2, -e2*N,   0,   e2*N,      0,  e2*N**2],
                 [0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*N],
                 [0,  0,   0,     0,  e3,  -e3*N,  -e3*N,  e3*N**2],
                 [0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*N],
                 [0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*N],
                 [0,  0,   0,     0,   0,      0,      0, e1*e2*e3] ]) * D

L = B.LLL()

v = Matrix(ZZ, L[0])
x = v * B**(-1)
phi_ = (e1*x[0,1]/x[0,0]).floor()
print(phi_)

[crypto] A hundred friends

This is appearently Hastad's broadcast attack on padded message.

As the m is large 3 ciphertexts are not enough to recover full plaintext, thus I used 5 ciphertexts.

# https://raw.githubusercontent.com/pwang00/Cryptographic-Attacks/master/Public%20Key/RSA/hastad.sage
"""
Sage implementation of Hastad's broadcast attack for small public exponent and multiple message/ciphertext pairs
"""

import binascii
import random


def linear_padding(ciphertexts, moduli, pad_array, const_array=(), e=3, eps=1/8):
#     if not(len(ciphertexts) == len(moduli) == len(pad_array) == len(const_array) == e):
#         raise RuntimeError("Moduli and ciphertext arrays have to be equal in length, and contain at least as many elements as e")
 
    '''
    Initialization with placeholders
    ciphertexts: ciphertext array
    T_array: Chinese Remainder Theorem coefficients
    moduli: Modulus array
    pad_array: Linear coefficient of padding applied to the message during encryption
    const_array: constant pad added to message during encryption (optional)
    '''

    n = len(ciphertexts)

    T_array = [Integer(0)]*n
    crt_array = [Integer(0)]*n
    polynomial_array = []

    for i in range(n):
        crt_array = [0]*n
        crt_array[i] = 1
        T_array[i] = Integer(crt(crt_array,moduli))

    G.<x> = PolynomialRing(Zmod(prod(moduli)))
    for i in range(n):
        polynomial_array += [T_array[i]*((pad_array[i]*x+const_array[i])^e - Integer(ciphertexts[i]))] #Representation of polynomial f(x) = (A*x + b) ^ e - C where (A*x + b) is the padding polynomial

    g = sum(polynomial_array).monic()  #Creates a monic polynomial from the sum of the individual polynomials
    roots = g.small_roots(epsilon=eps)
    return roots[0] if len(roots) >= 1 else -1



# def test_linear_padding():
#     moduli = []
#     ciphertexts = []
#     pad_array = []
#     const_array = []
#     e = 3
#     pad_bound = 2^512
#     prime_bound = 2^1024
#     m = int.from_bytes(b"p00rth0_th3_p00r", "big")
# 
#     for i in range(e):
#         pad = 1 # random.randint(0,pad_bound)
#         constant = random.randint(0,pad_bound)
#         pad_array += [pad]
#         const_array += [constant]
#         p = random_prime(prime_bound,proof=false)
#         q = random_prime(prime_bound,proof=false)
#         n = p*q
#         moduli += [n]
#         ciphertexts.append(pow(pad * m + constant,e,n))
# 
#     print(linear_padding(ciphertexts, moduli, pad_array, const_array))
#     return 0

import json
from random import sample

with open("params.json", "r") as f:
    params = json.load(f)

for i in range(1000):
    ns = []
    cs = []
    alist = []
    blist = []
    es = []
    e = 3
    paramlist = sample(params, k=5)
    for param in paramlist:
        ns.append(param["n"])
        cs.append(param["c"])
        alist.append(1)
        blist.append(param["pad"])

    res = linear_padding(cs,ns,alist,blist,e=e)
    if res == -1:
        print("NOT FOUND ({})".format(i),es)
    else:
        print(res)
        break

[misc] libcDB

jq was used to filter the result. and we could know that $maindb was defined like that . as $maindb from the error message. The query like this was to steal the username/password: .search fprintf 0x4b970 name=$maindb.users[].username.

Then we could get the admin's username and password and could execute .secret to get the flag: 3k{jq_is_r3ally_HelpFULL_3af4bcd97f5}.

UIUCTF 2020 writeup

I participated in this year's UIUCTF as a member of zer0pts. We got 5th place! The competition was well-designed and had a lot of good challenges. The other, there were a few of a guess or boring challenges and unfair operations. I hope it will be fixed in the next competition.

f:id:Furutsuki:20200720142023p:plain

[web] nookstop

There was a quite simple web page. It seems easy to get a flag. Just launch a click event for the flag button by this script: $("#flag").click(). It set a cookie clicked_flag_button=true and reloaded the page.

<html>
    <head>
   <script src="/static/cookie.js"></script>
   <script src="/static/jquery.min.js"></script>
   </head>
<body>

<!-- im so sorry -->
<div id="main">

    <pre id="output" ></pre>

    <br><br>
    <div id="buttons">
        <button type="button" id="status">Network Status</button> 
        <div>
            <button type="button" id="flag" style="margin-left: 300px">Flag</button> 
        </div>
    </div>

    
        <pre>Not that easy c: but here's a crumb: uiuctf{w</pre>
        

        

</div>

<script>

async function print(m, ms) {
   $("#output").append("\n");
   for (var i=0; i < m.length; i++)
   {
       var sel = $("#output");
       sel.append(m[i]);
       await sleep(ms);
   }
   $("#output").append("\n");
}

var msg1 = "Welcome to the Nook Stop, a magical multimedia terminal from Nook Inc.\nPlease select one of the following services:\n1) Network status\n2) Flag";
var msg2 = "Ah, sorry!! Our banking systems run on FORTRAN and they're a bit \non the slow side today.............................................\nyou know how this game's netcode can be sometimes, ahahahahaha!\nAlthought, come to think of it, they did say they were rolling out \nsome kind of new system the other day.......anyway, seems like that flag button isn't working right now."

$(document).ready(function(){

   $("#flag").click(function(){
       console.log("TODO: シークレット_バックエンド_サービスを可能にする");
       document.cookie = "clicked_flag_button=true";
       location.reload();
   });

   f = $("#flag");

   f.mousemove(function(){
       var r = Math.random()*100;
       if (r < 25)
           f.css("margin-left", "+=100px");
       else if (r >= 25 && r < 50)
           f.css("margin-left", "-=30px");
       else if (r >= 50 && r < 75)
           f.css("margin-top", "+=50px");
       else if (r >= 75 && r < 97)
           f.css("margin-top", "-=50px");
       else
           f.remove();
   });


   $("#status").click(function(){
       print(msg2,100);
   });

   print(msg1,10);
});

</script>



</body>
</html>

Then the following line is appended to HTML.

Not that easy c: but here's a crumb: uiuctf{w

To get full of the flag, we should set additionally cookie secret_backend_service=true according to the log of the console. Then got a flag! uiuctf{wait_its_all_cookies?}

[crypto] isabelles_file_encryption

The following script was a challenge. Also blackmail_encrypted was given.

#!/usr/bin/python

# password-protect your files with this super powerful encryption!
def super_secret_encryption(file_name, password):
  with open(file_name, "rb") as f:
    plaintext = f.read()
  
  assert(len(password) == 8) # I heard 8 character long passwords are super strong!
  assert(password.decode("utf-8").isalpha()) # The numbers on my keyboard don't work...
  assert(b"Isabelle" in plaintext) # Only encrypt files Isabelle has been mentioned in
  add_spice = lambda b: 0xff & ((b << 1) | (b >> 7))
  ciphertext = bytearray(add_spice(c) ^ password[i % len(password)] for i, c in enumerate(plaintext))

  with open(file_name + "_encrypted", "wb") as f:
    f.write(ciphertext)

# use this to decrypt the file with the same password!
def super_secret_decryption(file_name, password):
  with open(file_name + "_encrypted", "rb") as f:
    ciphertext = f.read()
  
  remove_spice = lambda b: 0xff & ((b >> 1) | (b << 7))
  plaintext = bytearray(remove_spice(c ^ password[i % len(password)]) for i, c in enumerate(ciphertext))

  with open(file_name + "_decrypted", "wb") as f:
    f.write(plaintext)

with open("password", "rb") as f: # I got too lazy typing it in each time
    password = f.read()
    # Make sure to encrypt the text in the middle!!!
    super_secret_encryption("blackmail", password)
    super_secret_decryption("blackmail", password)

It must be included in the plaintext that the spice added (= bit rotated) Isabelle and the key must be alphabetical 8 bytes. So using like the following script, we can enumerate list of (some rotation of) the key. And easily decrypt the blackmail by the given super_secret_decryption function.

from ptrlib import xor


add_spice = lambda b: 0xff & ((b << 1) | (b >> 7))
plaintext = bytes(add_spice(b) for b in b"Isabelle")

ciphertext = open("blackmail_encrypted", "rb").read()
for i in range(0, len(ciphertext) - 8):
    key = xor(plaintext, ciphertext[i:])
    try:
        if key.decode().isalpha():
            print(repr(key))
    except UnicodeDecodeError:
        pass

The key was iSaBelLE and the flag was in the mail: uiuctf{winner_winner_raccoon_dinner}

[crypto] coelacanth_vault

coelacanth_vault.py

#!/usr/bin/python
import random
from Crypto.Util import number
from functools import reduce

TOTAL = 15
THRESHOLD = 10
MAX_COELACANTH = 9

NUM_LOCKS = 5
NUM_TRIES = 250

# substitute for math.prod
prod = lambda n: reduce(lambda x, y: x*y, n)

def create_key(t, n, size=8):
    while True:
        seq = sorted([number.getPrime(size) for _ in range(TOTAL)])
        if len(set(seq)) != len(seq):
            continue

        alpha = prod(seq[:t])
        beta = prod(seq[-t + 1:])
        if alpha > beta:
            secret = random.randint(beta, alpha)
            shares = [(secret % num, num) for num in seq]
            return secret, shares

def construct_key(shares):
    glue = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or glue(n, A % n, t, s - A//n * t, N or n), -1)[n < 1]
    mod = prod([m for s, m in shares])
    secret = sum([s * glue(mod//m, m) * mod//m for s, m in shares]) % mod
    return secret

if __name__ == "__main__":
    print("Hi, and welcome to the virtual Animal Crossing: New Horizon coelacanth vault!")
    print("There are {} different cryptolocks that must be unlocked in order to open the vault.".format(NUM_LOCKS))
    print("You get one portion of each code for each coelacanth you have caught, and will need to use them to reconstruct the key for each lock.")
    print("Unfortunately, it appears you have not caught enough coelacanths, and thus will need to find another way into the vault.")
    print("Be warned, these locks have protection against brute force; too many wrong attempts and you will have to start over!")
    print("")

    num_shares = abs(int(input("How many coelacanth have you caught? ")))
    if num_shares > MAX_COELACANTH:
        print("Don't be silly! You definitely haven't caught more than {} coelacanth!".format(MAX_COELACANTH))
        print("Come back when you decide to stop lying.")
        quit()

    for lock_num in range(NUM_LOCKS):
        print("Generating key for lock {}, please wait...".format(lock_num))
        secret, shares = create_key(THRESHOLD, TOTAL)
        r_secret = construct_key(random.sample(shares, THRESHOLD))
        assert(secret == r_secret)
        print("Generated!")
        
        print("Here are your key portions:")
        print(random.sample(shares, num_shares))

        for num_attempts in range(NUM_TRIES):
            n_secret = abs(int(input("Please input the key: ")))
            if secret == n_secret:
                print("Lock {} unlocked with {} failed attempts!".format(lock_num, num_attempts))
                break
            else:
                print("Key incorrect. You have {} tries remaining for this lock.".format(NUM_TRIES - num_attempts))        
        else:
            print("BRUTE FORCE DETECTED. LOCKS SHUT DOWN.")
            print("Get out. You don't deserve what's in this vault.")
            quit()
    
    print("Opening vault...")
    with open("flag.txt", "r") as f:
        print(f.read())

It makes some of the shares by getting the remainder by the prime modulus of the secret. So it is recoverable by the Chinese Remainder Theorem. It seems impossible for the lack of shares, however, the 8-bit primes is at most 251 and we have 250 times to challenge. Thus we can pick a one of the large (and not in the given share) prime and bruteforce to hit the correct remainder.

The solution script:

from ptrlib import Socket, crt

NUM_LOCKS = 5
NUM_TRIES = 250

sock = Socket("chal.uiuc.tf", 2004)
sock.sendlineafter("caught? ", "9")

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251][::-1]

for i in range(NUM_LOCKS):
    print(f"stage {i+1}")
    shares = eval(sock.recvlineafter("portions:\n").decode())

    for p in primes:
        flag = True
        for s in shares:
            if s[1] == p:
                flag = False
                break
        if flag:
            prime = p
            break

    for x in range(251):
        v, _ = crt(shares + [(x, prime)])
        sock.sendlineafter("key: ", str(v))
        if b"unlocked" in sock.recvline():
            break
sock.interactive()

the flag was uiuctf{small_oysters_expire_quick}

[rev] Redd's Art

We're given the 64bit ELF binary. The point was sub_A5A. It does xor bytes in address 973 by the key: the result of sub_91A which was sum of string uiuctf{v3Ry_r341_@rTT}. However the modification of .text causes a segmentation fault. So I wrote the modification script

data = [0x4B,0x56,0x97,0xFB,0x4D,0x56,0x9D,0xF2,0x36,0x56,0xD9,0x5B,0xF6,0x17,0x1E,0x1E,0x1E,0x56,0x95,0x5B,0xF6,0x11,0xA8,0x1E,0x56,0x11,0xA0,0xDE,0x56,0x1F,0x5B,0xF6,0x56,0x95,0x5B,0xF6,0x11,0xA8,0x1E,0x96,0x5B,0xC5,0xD9,0x5B,0xC2,0x1E,0x1E,0x1E,0x1E,0xF5,0x2C,0x56,0x95,0x0B,0x65,0x08,0x3E,0x1E,0x95,0x5B,0xC2,0x56,0x86,0x56,0x1F,0xCE,0x11,0xA8,0x1E,0x97,0xDC,0x11,0xA8,0x5B,0xC5,0x93,0x12,0x1C,0x56,0x95,0x0B,0x7E,0x08,0x3E,0x1E,0x95,0x5B,0xC2,0x56,0x86,0x56,0x1F,0xCE,0x97,0xD4,0x96,0x0E,0x9D,0x5B,0xC2,0x1F,0x95,0x5B,0xC2,0x56,0x7D,0xC6,0x56,0x95,0x1B,0x5D,0x08,0x3E,0x1E,0x56,0x97,0xD9,0xF6,0xAD,0xE3,0xE1,0xE1,0x56,0x27,0xDD,0x6C,0xAA,0xA6,0x1E,0x1E,0x1E,0x1E,0xF6,0x00,0xE1,0xE1,0xE1,0x97,0x5B,0xFA,0xD9,0x5B,0xFE,0x1E,0x1E,0x1E,0x1E,0xF5,0x2E,0x56,0x95,0x0B,0x07,0x08,0x3E,0x1E,0x95,0x5B,0xFE,0x56,0x86,0x56,0x1F,0xCE,0x11,0xA8,0x16,0x95,0x5B,0xFA,0x97,0xD8,0x56,0x95,0x0B,0x1C,0x08,0x3E,0x1E,0x95,0x5B,0xFE,0x56,0x86,0x56,0x1F,0xCE,0x2F,0xEF,0x97,0xD4,0x96,0x0E,0x9D,0x5B,0xFE,0x1F,0x95,0x5B,0xFE,0x56,0x7D,0xC6,0x56,0x95,0x1B,0xFD,0x0B,0x3E,0x1E,0x56,0x97,0xD9,0xF6,0x4D,0xE3,0xE1,0xE1,0x56,0x27,0xDD,0x6C,0xA8,0x8E,0x56,0x9D,0xDA,0x36,0x45,0x43]

key = sum(ord(c) for c in "uiuctf{v3Ry_r341_@rTT}")
xored = [(d^key)&0xff for d in data]


data = bytearray(open("ReddsArt", "rb").read())

data = data[:0x973] + bytes(xored) + data[0x973 + len(xored):]
open("modified", "wb").write(data)

Then It tuned out that the sub_973 does add some constant x to the each byte of string at 0x202028, and after that, xor them by the key which calculated by sub_91A.

The unknown x was only 1 byte. So I brute-forced all candidates.

key = sum(ord(c) for c in "uiuctf{v3Ry_r341_@rTT}")
xs = [ord(c) for c in "hthzgubI>*ww7>z+Ha,m>W,7z+hmG`"]

for k in range(256):
    ys = "".join(chr((((k+x) % 256) ^ key) & 0xff) for x in xs)
    print(repr(ys))

the flag was: uiuctf{R_3dd$_c0Uz1n_D1$c0unT}