zh3r0 CTF v2 writeup - Attack All Around

先日、TEAM NACS 第17回公演「マスタ―ピース～傑作を君に～」を拝聴しました。いやあ、面白い。大泉洋＝面白い俳優 → 水曜どうでしょう面白すぎる → TEAM NACS 面白い → 舞台観てみたい、となり今回この舞台をストリーミング配信で観ました。リーダーのカーテンコールにモーレツに感動した。皆さんも是非。

CTF中にこの配信があり、気になって仕方なかったよという話です。

Result
Writeup
- alice_bob_dave
- 1n_jection
- b00tleg
  - Q1-1
  - Q1-2
  - Q2
  - Q3
  - Q4
  - Q5
  - Q6
  - Q7
Problems & Solver

Result

f:id:partender810:20210607005717p:plain — 最近良さげ？

Writeup

今回、m1z0r3新入生の方がすごくてcrypto問題を結構解いてくれました！しかも自分が苦手な問題をやってくれたので何とも良いチームプレイでした！
それらも勉強せねば。

Chaos
Twist and Shout はこちらから。その新入生が解いてくれました！ zh3r0 CTF 2021 writeUp - HackMD

alice_bob_dave

Alice and Bob are sending their flags to Dave. But sadly Dave lost the modulus :( Try to retrive the flag!
ファイル：chall.py, out.txt

公開鍵e, 暗号文ct_a, ct_b, 秘密鍵d_a, d_bが分かっていてn_a (=pq), n_b (=pr)が分からないという鬼畜。これが一番簡単なのか…。

e×d_a = k×φ(n_a)+1 = k×(p-1)×(q-1)+1
e×d_b = l×φ(n_b)+1 = l×(p-1)×(r-1)+1

より、GCD(e×d_a+1, e×d_b+1) = (p-1)×kとなります。このGCDした値を因数分解して、kと(p-1)に分ける組み合わせを全探査します。(p-1)に分けた方に1を足して1024bitsの素数となればOKです。因数の組み合わせが20個以内であればそんなに時間かかりませんね。

pが求まったらそこから頑張ってq, rを求めてもいいのですが(上と同じやり方で)、pをモジュールとしてやったらflag出てきましたやったね。

from Crypto.Util.number import *
ct_a= 
ct_b=
d_a=
d_b=
e=65537
import math
c = math.gcd(e*d_a-1,e*d_b-1) #c = k*(p-1)
print(c)
# cを素因数分解したやつがpp
pp = [ 2,2,3,3,1543,36097,1014259,17275267,33878479,64555363525704839503363,13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377]
import sympy
for i in range(pow(2,len(pp))):
    cc = bin(i)[2:]
    while len(cc) < len(pp): cc = "0" + cc
    np = 1
    for j in range(len(cc)):
        if cc[j] == "1": np*=pp[j]
    if sympy.isprime(np+1) and len(bin(np+1)[2:]) == 1024:
        print("Found!")
        p = np+1

    
#p = 177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163

m1 = pow(ct_a,d_a,p)
m2 = pow(ct_b,d_b,p)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

zh3r0{GCD_c0m3s_70_R3sCue_3742986}

1n_jection

COVID: exists
vaccine jokes: challenge_name
ファイル：challenge.py

from secret import flag

def nk2n(nk):
    l = len(nk)
    if l==1:
        return nk[0]
    elif l==2:
        i,j = nk
        return ((i+j)*(i+j+1))//2 +j
    return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])

print(nk2n(flag))
#2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585

まず、nk2n(x, y) = 259...585 になったことが分かります。elif l==2: を見てみると、 ( (i+j)×(i+j+1) )//2 +j = 259...585 ということが分かり、i, j が x, yに該当します。

enc = ( (i+j)×(i+j+1) )//2 +j
2×enc = ( (i+j)×(i+j+1) ) +2×j
2×enc ≃ (i+j)²

と強引な近似式を立てます。

x² < 2×enc となる最大の自然数xを見つけ、2×enc - (x+1)x が 2×j となるのでj求め。x-jからiを出します。あとは、見つけたi, jをencとして共に128以下になるまで再帰的に計算させます。128以下としたのはASCII文字だろうという想定です。

感覚でnk2nの逆関数書いたら出来たという感じです。もっと理論的なwriteupありそう。最大の自然数としてうまくいったのも正直よく分かっていない。

def inv_nk2n(enc,dep):
    if enc < 128:
        print(chr(enc))
        return
    e,_ = gmpy2.iroot(2*enc,2) #e = i+jになっていたらいいな
    e = int(e)

    while True:
        j = (2*enc-(e*(e+1)))//2
        if j < 0:
            e -= 1
            continue
        e1,_ = gmpy2.iroot(2*enc-2*j,2) #e1 = i+jのはず。e=e1ならちゃんと求められている
        if e == e1:
            i = e-j
            assert ((i+j)*(i+j+1))//2 +j == enc
            break
        e -= 1
    if i < 128:
        print(chr(i),end="")
        print(chr(j),end="")
        return
    elif j < 128:
        #print(chr(j),end="")
        inv_nk2n(i,dep+1)
        print(chr(j),end="")       
    else:
        inv_nk2n(i,dep+1)
        inv_nk2n(j,dep+1)

zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_n^k_t0_n_c0uld_b3_s00000_c0000000l!}

b00tleg

Source? Gotta comply to Indian CTFs' crypto standards
nc crypto.zh3r0.cf 1111

これ本当にだるかった。

暗号文が渡されてそれがどんな暗号化をしているかは教えてくれないが、任意の16進数は暗号化してくれるoracleがあります。そして、渡された暗号文に対する平文が分かったら答えてねといった問題が8問もありました。

Q1-1

Level: 1, encrypted flag: 69666d6d70217870736d6522214d667574216866752168706a6f68

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
01

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
02

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0f
10


[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0102030405
0203040506

と1byteごと1足した値が返ってきます。なので貰った暗号文を1byteごと1減らして出せばOKです。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:68656c6c6f20776f726c6421204c6574732067657420676f696e67
Correct

Q1-2

Level: 1, encrypted flag: 167536933462626657495469026094356252520425094567558410085605026028734973776349984140755605180214900

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:10
16

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:1000
4096

hex -> dec だけのようですね。貰った暗号文をhex()でOKです。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74
Correct

Q2

Level: 2, encrypted flag: 0082288254783f5b78d033d03fd03382287854c1e88928d054d0ccc1d0541be889c1d0331d89

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
f2

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
8d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
a9

これだけじゃ一切分からなかったのですが、下のですぐに分かりました。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0101
8d8d

00~ffが別の1byteとマッピングしているようですね。換字式暗号のよう。00~ffを暗号化させて対応表を作成し復号します。

このあたりから繋ぎ直す度に暗号文が変わっていきました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665
Correct

このあたりから繋ぎ直す度に暗号文が変わっていきました。そして暗号文が変わっても平文は毎回一定ということが分かり、ASCII変換すると意味のある文字列になりました。早く気付け…

Q3

Level: 3, encrypted flag: c46b9613f603197b6d8d7ce39bc6ada752de6bff165924dfe5c3b90c00c792ea4775b0602d93a6cfc9652cf090b3

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
ef

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
a6

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0101
a693

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0102
a6c7

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
2d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0201
2d93

これまた換字式暗号のようですが、"0101"を送っても同じ1byteが2回続くわけではなさそう。ただ、i byte目かによって変わる換字式暗号のだろう。2byte目を"01"にしたら1byte目に依存せず"93"となりました。

なので、暗号文の上位1byteと一致するまで00~ffを暗号化してもらい、"(一致した1byte)+00~ff" で暗号化してもらい、暗号文の上位2byteと一致するか確かめ、"(一致した2byte)+00~ff" で…を繰り返します。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172
Correct

Q4

Level: 4, encrypted flag: 83c492da5a071252f030f87c4424db86a7cd110f5b1eaec1fc7935eb5f073d2c3631caab94de551071f35dc3b5ba93e2680c44dc670d8cdc0560e43caebb620cf77fc1a060121059471ab7b7da9a

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
c43c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
dc24

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
38c8

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
8e72

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
14ec

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
a45c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
847c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
b05058a9

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
7a867e83

なんの方法も思いつきません。1byteの平文が2byteの暗号文になっていて、2倍の関係はずっと成り立つくらいです。

無心で"00"を暗号化していると…

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
11ef

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
12ee

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
11ef

と同じ暗号文になる時があった。もしかして、"00"の暗号文は256通りあってだから1byte平文→2bytes暗号文か？となりました。

00~ffまで100回ほど暗号化してもらって、貰った暗号文と一致しているかチェックして平文を復号させていきます。256通りもあるので、何回も暗号化してもらっても貰った暗号文と一致しない箇所があるかもしれませんが、平文は意味ある文字列になるので最後はエスパー出来るだろう。

47xy616420xy6861xyxy796fxyxy66696775726564206fxyxy2074686520696e7661xyxyxy6e74
G?ad ?ha??yo??figured o?? the inva???nt

予想当たってそう。

Glad, figured out になるのだろう。最後の単語なんだろう。

ここで2日目の夜を迎えます。僕はお休みですがPCには頑張ってもらいます。夜通しグルグルさせたら復号できました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74
Correct

Glad that you figured out the invariant

実際、"00"の暗号文256個を全て出すのにかかる暗号化試行回数の期待値はいくつなのだろう。

Q5

Level: 5, encrypted flag: 21632f60371e637d646719633361371d6e38257c0c7f7d727e1d6e7d7c781c747d767f007271256705633c76724962326b63497238697b4967337c780763cdc8ef69065d0517

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
2d1d7371522d4207101c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
77d092631876f707d06a

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
01d479285c03ca8ee440

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
ed22e53735ed2323ded2

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102
3d6c2d55f63d6d2fbc4b

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203
3b5742e8213b5640eb2d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001020304
5a77fc8bd45a76fe88d0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102030405
228a9f15b82739069578228b9d16bc

5bytesまで暗号文の長さは10bytesと変わらず、6bytes送ると15bytesになりました。初めは5bytes -> 10bytesなのでQ5と変わらないのかと思いましたが、6bytes(10bytesでも) -> 15bytesで断念。なんか余計な5bytesがあるな。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
4b3f92695d4e389762504b3e906a59

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
6c5fd82ec26958dd25cf6c5eda2dc6

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
22f1249dd427f62196d922f0269ed0

またもや無心oracle attackをしていると、いずれも0~2, 20~22文字目が一致している & 3, 23文字目の差の絶対値が1という共通点を発見。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102030405060708090001020304
ba7470d81abf7375d317ba7470d81aba7572db1e

この0~9, 20~29文字が等しい暗号文を送ると、暗号文の0~9, 20~29が等しくなりました。

XORだ！！！！

下位5bytesは乱数で、それと平文5bytesずつXORしているよう。平文長が5の倍数出ない場合は乱数でパディングしているよう。

貰った暗号文の下位5bytesと他でXORすると文章が出てきました。後ろ3bytesはパディングのようですね。

Here we append the key with your shit, please dont tell anyone\x90\xcd\xf8

後ろ3bytesをカットして提出でcorrect

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65
Correct

Q6

次の問題が出るまでちょっと待たされる

Level: 6, encrypted flag: 136384619054339654698475609187854339113882435852470452229300074212198483311645305554174498023573137797735886243473558340482613861649177748126144672869929906606346385500823906944622319359965197258529068372012245196075373073203790506545107848221246609729715492848444591450621341939920310444052818596797750926038

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
1

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
8

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:03
27

Q5, 6の疲労からまだ難しいのがどんどん来るのだろうと思ったら、ただの3乗やんけ！とウッキウキで暗号文の3乗根を取ってみる。無い。キレる。

どんな暗号文を送っても3乗になるだけ…となっていたのですが、大きい数字を送ると3乗根はありませんでした。e=3, N=unknownのRSA暗号のよう。

m³ > N となるmを送り、m³ - c (=m³ mod N)からNの倍数が手に入ります。これは先程の新入生が教えてくれました。自分は気付かず二分探索で求めようと…。

素因数分解してみると、1024bitsの素数が1つだけありました。色々検証した結果、c = m³ mod p (p:prime) と断定。ed = 1 mod (p-1) でdを求め、c^d mod pで意味ある文字列になりました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f
Correct

Q7

Level: 7, encrypted flag: 108613801296595507842842562285901639870700128823984221118522899150125891850980318127085910315828915486703595963395705206816199002398854310898276932839241255030719759005865491552890311738885862387404277721909188630301200138952557304529868842692309573491972932743859389182753896383477285635296983981909565573190

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
1

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
170141183460469231731687303715884105728

今度も何乗もしていそう。"02"の時、かなり大きい値となっていますが、2進数にする進数にすると

>>> c = 170141183460469231731687303715884105728
>>> bin(c)
'0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

ここから、eの値が求められます。この場合128bitsあるのでe=127ですね。

先と同様に、m^e > nとなる平文を送ってその差分からnが分かります。Q6でもやればよかったのですが、GCD(m1^e - c1, m2^e - c2)でよりnがわかりやすいです。今回もn=p (p:prime)でした。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d
Correct
Shh, you got the flag already

もうもらっているとあるので、出てきた平文をASCII変換するとflagでした