好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

ångstromCTF 2020 Crypto の writeup

CTF angstromCTF

2020年 3/14(土)9:00 - 3/19(木)9:00 JST で開催された、ångstromCTFのCrypto分野のwriteupです。CTF Timesはこちら。
他の分野のwriteup, 戦績はこちら。

kusuwada.hatenablog.com

[Crypto] Keysar

Hey! My friend sent me a message... He said encrypted it with the key ANGSTROMCTF.

He mumbled what cipher he used, but I think I have a clue.

Gotta go though, I have history homework!!

agqr{yue_stdcgciup_padas}

タイトルのKeysarから、Key + Caesar が連想されます。
最後の行を、Keyを使ってずらすのかな？と思ったけど、なんかうまく行かない。

cryptoの最初だし、簡単そうだったので割と上の路線で頑張ってみたけど成果が得られないので、ここは換字暗号かも知れないと思って置き換えてみました。

既知のものはたった4文字。フラグフォーマットの部分はactfのはずなので

a -> A
g -> C
q -> T
r -> F

この時点でこう置き換わりました。ACTF{yue_stdcCciup_pAdAs}
次に、pAdAsの部分に着目します。クロスワードのサイトを頼りにしつつ、5文字の真ん中がa、かつ他の文字は被らない、一般的な単語を探していくと、ありました！SALAD!
ほかにもJAPANとかあったのですが、まずはSALAD路線で埋めてみます。

p -> S
d -> L
s -> D

すると、こうなります。ACTF{yue_DtLcCciuS_SALAD}
おや、なんか見える…。念の為クロスワードのサイトで真ん中のDtLcCciuSに当てはまるものを探すと、これ。DELICIOUS! これは合ってそうな予感！

t -> E
c -> I
i -> O
u -> U

現時点でACTF{yUe_DELICIOUS_SALAD}。 使っていない文字はBGHJKMNPQRVWXYZ。この組み合わせでyUeを意味ある単語にします。これでしょ。YUM!(๑´ڡ`๑)

ということで、actf{yum_delicious_salad}を入れてみたら通りました！
なんて力技！これ絶対想定解じゃないよね…。

[Crypto] Reasonably Strong Algorithm

RSA strikes again!

n = 126390312099294739294606157407778835887
e = 65537
c = 13612260682947644362892911986815626931

が与えられます。

タイトル・問題文の通りRSA暗号です。nが小さいので素因数分解できそう。

[126390312099294739294606157407778835887:title]

に突っ込んだら分解してくれました。

p = 9336949138571181619
q = 13536574980062068373

この情報から鍵を構築して、与えられたciphertext(c)を復号します。

from Crypto.Util.number import inverse
import binascii

n = 126390312099294739294606157407778835887
e = 65537
c = 13612260682947644362892911986815626931
p = 9336949138571181619
q = 13536574980062068373

d = inverse(e, (p-1)*(q-1))
plain = pow(c, d, n)
flag = bytes.fromhex(hex(plain)[2:]).decode('ascii')
print(flag)

実行結果

$ python solve.py 
actf{10minutes}

わー、10分で解けるやろこんなもん、ってメッセージ？

[Crypto] Wacko Images

How to make hiding stuff a e s t h e t i c? And can you make it normal again?

png画像とスクリプトが配布されます。

enc.png

f:id:kusuwada:20200319093857p:plain

image-encryption.py

from numpy import *
from PIL import Image

flag = Image.open(r"flag.png")
img = array(flag)

key = [41, 37, 23]

a, b, c = img.shape

for x in range (0, a):
    for y in range (0, b):
        pixel = img[x, y]
        for i in range(0,3):
            pixel[i] = pixel[i] * key[i] % 251
        img[x][y] = pixel

enc = Image.fromarray(img)
enc.save('enc.png')

途中の

pixel[i] = pixel[i] * key[i] % 251

これを復元するだけの問題なんだけど、最初ぱっと思いつかず真っ黒い画像を作ってしまった。
% 251によって、251 を n 回分切り捨てられているので、何回分だったかを復元する必要がある。ちょっと前にrtcpCTFで同じような問題が出たときは、無視して気合で補完してたけど、画像は無理。
よく考えたら、割り切れるかどうかを判定したらいいだけだった。

from numpy import *
from PIL import Image

def find_mod0_number(mod, div):
    i = 0
    for i in range(1000):
        if ((251*i) + mod) % div == 0:
            return (251*i + mod) // div

enc = Image.open(r'enc.png')
img = array(enc)

key = [41, 37, 23]

a, b, c = img.shape

for x in range (0, a):
    for y in range (0, b):
        pixel = img[x, y]
        for i in range (0, 3):
            pixel[i] = find_mod0_number(pixel[i], key[i])
        img[x][y] = pixel
            
flag = Image.fromarray(img)
flag.save('flag.png')

上記のスクリプトを実行すると、下記の画像が得られました！

f:id:kusuwada:20200319093916p:plain

[Crypto] Discrete Superlog

You've heard of discrete log...now get ready for the discrete superlog.

Server 1: nc crypto.2020.chall.actf.co 20603

Server 2: nc 3.234.224.95 20603

Server 3: nc 3.228.7.55 20603

Hint

just do it lmao

それぞれのサーバーに接続してみます。全部同じような文言が出てきました。Serverがたくさんあるのは予備かな？

$ nc crypto.2020.chall.actf.co 20603
We define a^^b to be such that a^^0 = 1 and a^^b = a^(a^^(b-1)), where x^y represents x to the power of y.
Given this, find a positive integer x such that a^^x = b mod p.
Generating challenge 1 of 10...
p = 723016406727943930447
a = 564447721002380463960
b = 642755755056058439913
Enter x:

a^(a^^(x-1))....と展開していって、x-1 -> 0 になるまで繰り返し、その結果が b mod p になるようなxを求める。
正面から計算するのではマシンパワーが持たない。なんか簡単に計算する方法がありそう。

x = 0 のとき
a^^x = a^^0 -> 1

x = 1 のとき
a^^x = a^(a^^0) -> a^1 -> aの1乗 -> a

x = 2 のとき
a^^x = a^(a^^(1)) -> a^(a^(a^^0)) -> a^(a^1) -> aのa乗

x = 3 のとき
a^^x = a^(a^^(2)) -> a^(a^(a^(a^^1))) -> a^(a^(a^(a^(a^^0)))) -> a^(a^(a^(a^1))) -> a^(a^(a^a)) -> aのa乗のa乗の…
なので、ここいらで計算不能になりそう。

ぱっと計算できそうなのはx=2まで。x=0や負数はbad inputになってしまったので、1以上と思われる。
xが大きすぎると、サーバー側の不可も高そうだから小さいのでは？と、予想し、まずは手動で適当にやってxのレンジを限定できないか試してみた。

a==bのときのみ1を入力して、あとは当てずっぽう。

p = 994921607959813404391
a = 698182661120981831336
b = 279161446899730061330
Enter x: 11
Correct!
Generating challenge 2 of 10...
p = 2035098351304747275519179
a = 1214610322619193425837908
b = 1596332489592641708305146
Enter x: 10
Correct!
Generating challenge 3 of 10...
p = 3148408632729316997396959913
a = 1752796251374167696183461400
b = 1805599096894756595815098950
Enter x: 10
Correct!
Generating challenge 4 of 10...
p = 5199751015564469837755766632823
a = 598930976137032034358289690652
b = 3783632118667315731521088649612
Enter x: 9
Correct!
Generating challenge 5 of 10...
p = 11242420143774258374670417600849661
a = 10992975078191321331830830015467422
b = 9245677158709730876242647934110206
Enter x: 9
Wrong!

当てずっぽうの手入力を小一時間頑張って、7回戦まではクリアできました。が、流石に連続10回はクリアできず。
色々入れてみた感じ、x=10を超えた入力だと、連続して正解になる確率が高い気がする。レンジは結局絞れなかった。

もっと簡単にxを求める方法がありそう(sys.maxsizeを超えた数の扱いなど？)だったが

  • 対象サーバーが3台ある
  • ルール上flagについてのみブルートフォースが禁止されている
  • 手動でも良いとこまで行った
  • ヒントの文言を「考えるな！やれ！」と受け取った

上記のことから、確率の高そうなスクリプトを書いてぶん回すことに。

  • a == b % pだったら1を入力する
  • その他の場合は、20から初めて、クリアするごとに2ずつ数を増していく

完全に手動でやってみた観測結果から導き出した戦略なので、特に2つ目の戦略にロジックはないです…。

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

from pwn import *

host = "3.228.7.55"
port = 20603

total_count = 0
histgram = [0] * 10

while True:
    r = remote(host, port)
    cnt = 20
    for i in range(10):
        total_count += 1;
        r.recvuntil(b'of 10...\n')
        p = int(r.recvline().split(b' ')[2].strip())
        a = int(r.recvline().split(b' ')[2].strip())
        b = int(r.recvline().split(b' ')[2].strip())
        r.recvuntil(b'Enter x: ')
        y = b % p
        print(i+1, a, y, total_count)
        if a == y:
            r.sendline(b'1')
        else:
            cnt += 2
            r.sendline(str(cnt).encode())
        ans = r.recvline()
        print(ans)
        if ans == b'Correct!\n':
            continue
        elif ans == b'Wrong!\n':
            r.close()
            break
        else:
            print(ans)
    print(r.recvall())
    histgram[i] += 1
    print(histgram)

最後の回の出力

[+] Opening connection to crypto.2020.chall.actf.co on port 20603: Done
1 215879984025691473982 110556716195490148966 3492
b'Correct!\n'
2 1581210646772698326109943 791396444764946762658877 3493
b'Correct!\n'
3 92186167515681939609818745 201559590206328096567594876 3494
b'Correct!\n'
4 3027447874322094475474920571620 2298025013087052938393753141255 3495
b'Correct!\n'
5 5162052971929183566302752930899595 1961221593529719361211396217578528 3496
b'Correct!\n'
6 15871077012770209361419929164247704368 28637385147929896027963852942254467823 3497
b'Correct!\n'
7 14864647476577027064518141222475408418177 32365804902275071979785026580042171744693 3498
b'Correct!\n'
8 36295485157159471391321305745083857293862672 49443025293727373418986977032450728652053741 3499
b'Correct!\n'
9 68421300075807946101984674303412664948377739396 9663569822610837680890751410616312522729704138 3500
b'Correct!\n'
10 495356959908030212787274725618811097255547462152172 191992482162567355844785016584767628461504127416968 3501
b'Correct!\n'
[+] Recieving all data: Done (50B)
[*] Closed connection to crypto.2020.chall.actf.co port 20603
b'flag: actf{lets_stick_to_discrete_log_for_now...}\n'

なにはともあれ、力づくで ﾌﾗｸﾞｹﾞｯﾄ٩(๑❛ᴗ❛๑)尸
これは想定解がきになる！