Harekaze mini CTF 2021に、一人チームrotationで参加しました。そのwrite-up記事です。問題等はhttps://github.com/TeamHarekaze/harekaze-mini-ctf-2021-challenges-publicで公開されています。
- コンテスト概要
- 結果
- 環境
- 解けた問題
- [Welcome] Welcome (100 points, 70 Solves)
- [Web] Incomplete Blog (201 points, 21 Solves)
- [Reversing] Crackme (205 points, 20 Solves)
- [Reversing] Pack Program (428 points, 3 Solves)
- [Crypto] first exam (134 points, 52 Solves)
- [Crypto] sage training (179 points, 27 Solves)
- [Crypto] mulmulmulti-prime rsa (215 points, 18 Solves)
- 感想
コンテスト概要
2021/12/24(金) 18:00 +09:00 - 2021/12/24(金) 21:00 +09:00 の開催期間でした。他ルールはaboutページから引用します:
ルール
Harekaze mini CTF 2021は2021-12-24 18:00:00 (UTC+9) に開始し、2021-12-24 21:00:00 (UTC+9) に終了します。
本大会はチーム戦です。登録時には、まずチームのリーダーがユーザとチームを作成してください。他のメンバーは、ユーザを作成してから、リーダーから共有されたパスワードを用いてチームに加入してください。なお、チームメンバーの数に制限はありません。
本大会はダイナミックスコアリングを採用しており、各問題のポイントは解いたチームの数に応じて変化します。解いたチームが多くなるほど、問題のポイントは低くなります。
得点したポイントの多いチームが上位となります。同点の場合には、より早くそのポイントに到達したチームが上位となります。
アナウンスや問題文は日本語および英語で提供されます。
すべての問題はCTFの開始後すぐに公開されます。
フラグは問題文で特記がない限り、HarekazeCTF{(ascii printable)+}というフォーマットに従います。
禁止行為が確認されたチームは、運営チームの判断により減点や失格などの処分の対象となります。
(後略)
結果
正の得点を得ている73チーム中、1462点で6位でした。
環境
Windows+WSL2(Ubuntu)を使って取り組みました。
Windows
c:\>ver Microsoft Windows [Version 10.0.19044.1415] c:\>wsl -l -v NAME STATE VERSION * Ubuntu Running 2 kali-linux Stopped 2 c:\>
他ソフト
- IDA(Free版) Version 7.6.210507
- x64dbg Version Oct 2 2020, 23:12:00
WSL2(Ubuntu)
$ cat /proc/version Linux version 5.10.60.1-microsoft-standard-WSL2 (oe-user@oe-host) (x86_64-msft-linux-gcc (GCC) 9.3.0, GNU ld (GNU Binutils) 2.34.0.20200220) #1 SMP Wed Aug 25 23:20:18 UTC 2021 $ cat /etc/os-release NAME="Ubuntu" VERSION="18.04.6 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.6 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionic $ python3.8 --version Python 3.8.0 $ python3.8 -m pip show pip | grep Version Version: 21.3.1 $ python3.8 -m pip show requests | grep Version Version: 2.26.0 $ python3.8 -m pip show pycryptodome | grep Version Version: 3.11.0 $ python3.8 -m pip show sympy | grep Version Version: 1.9 $ curl --version curl 7.58.0 (x86_64-pc-linux-gnu) libcurl/7.58.0 OpenSSL/1.1.1 zlib/1.2.11 libidn2/2.0.4 libpsl/0.19.1 (+libidn2/2.0.4) nghttp2/1.30.0 librtmp/2.3 Release-Date: 2018-01-24 Protocols: dict file ftp ftps gopher http https imap imaps ldap ldaps pop3 pop3s rtmp rtsp smb smbs smtp smtps telnet tftp Features: AsynchDNS IDN IPv6 Largefile GSS-API Kerberos SPNEGO NTLM NTLM_WB SSL libz TLS-SRP HTTP2 UnixSockets HTTPS-proxy PSL $
解けた問題
コンテストは、問題文が日本語と英語の2言語で記述されていました。本記事では日本語版表記のみを引用します。
[Welcome] Welcome (100 points, 70 Solves)
Harekaze mini CTF 2021へようこそ! フラグは HarekazeCTF{bon_voyage} です。
問題文中にフラグそのものが記述されていました: HarekazeCTF{bon_voyage}
[Web] Incomplete Blog (201 points, 21 Solves)
JavaScriptでブログを作ってみました。 ただ、まだ開発中ですし、有料記事のための課金システムも今頑張って作っているところで未完成です。なので、一部の有料にするつもりの記事は閲覧できません。ごめんなさい😉 http://incomplete-blog.harekaze.com 添付ファイル: incomplete-blog.zip
zip中の1つに、サーバー側で動作している以下のindex.jsがありました:
// 前略 let articles = []; for (let i = 0; i < 10000; i++) { articles.push({ title: `Dummy article ${i}`, content: 'Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.'.trim() }); } articles[1337] = { title: 'Flag', content: `Wow, how do you manage to read this article? Anyway, the flag is: <code>${flag}</code>` }; // 中略 app.get('/article/:id', async (request, reply) => { // id should not be negative if (/^[\b\t\n\v\f\r \xa0]*-/.test(request.params.id)) { return reply.view('article.ejs', { title: 'Access denied', content: 'Hacking attempt detected.' }); } let id = parseInt(request.params.id, 10); // free users cannot read articles with id >9 if (id > 9) { return reply.view('article.ejs', { title: 'Access denied', content: 'You need to become a premium user to read this content.' }); } const article = articles.at(id) ?? { title: 'Not found', content: 'The requested article was not found.' }; return reply.view('article.ejs', article); }); // 後略
idが1337番目のページを閲覧できればフラグが手に入ります。しかしidが9より大きい場合はAccess deniedとなる分岐に入ってしまいます。
articles.at(id)で使われている関数を調べてみると、Array.prototype.at() - JavaScript | MDNに以下の記述が見つかりました:
if a negative number is used, the element returned will be found by counting back from the end of the array.
負の数を指定すると、後ろからのindexを指定できるとのことです。この問題でもそれを使えれば、と思いましたがif (/^[\b\t\n\v\f\r \xa0]*-/.test(request.params.id))の分岐が厄介です。
入力を使用しているparseInt関数の仕様を調べてみると、parseInt() - JavaScript | MDNに以下の記述がありました:
Parameters
string
The value to parse. If this argument is not a string, then it is converted to one using the ToString abstract operation. Leading whitespace in this argument is ignored.
ここでwhitespace箇所には別ページのリンクが貼られています。そのページのWhitespace - MDN Web Docs Glossary: Definitions of Web-related terms | MDNを見てみると、以下の記述がありました:
The ECMAScript Language Specification defines several Unicode codepoints as “white space”: U+0009 CHARACTER TABULATION <TAB>, U+000B LINE TABULATION <VT>, U+000C FORM FEED <FF>, U+0020 SPACE <SP>, U+00A0 NO-BREAK SPACE <NBSP>, U+FEFF ZERO WIDTH NO-BREAK SPACE <ZWNBSP>, and any other Unicode “Space_Separator” code points <USP>.
今回の問題ではU+FEFF ZERO WIDTH NO-BREAK SPACE <ZWNBSP>をチェックしていないので、それを使うと迂回できそうです。それを使ってソルバーを書きました:
#!/usr/bin/env python3.8 import requests url = f"http://incomplete-blog.harekaze.com/article/\uFEFF{1337-10000}" r = requests.get(url) print(r.text)
実行しました:
$ ./solve.py
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Incomplete Blog</title>
<link rel="stylesheet" href="/static/style.css">
</head>
<body>
<main>
<h1>Incomplete Blog</h1>
<h2>Flag</h2>
<p>Wow, how do you manage to read this article? Anyway, the flag is: <code>HarekazeCTF{I_d0nt_kn0w_h0w_t0_m4ke_ctf_ch4llenges_t4sukete}</code></p>
</main>
</body>
</html>
$
フラグを入手できました: HarekazeCTF{I_d0nt_kn0w_h0w_t0_m4ke_ctf_ch4llenges_t4sukete}
[Reversing] Crackme (205 points, 20 Solves)
入力した文字列がフラグか判定してくれるようです。 添付ファイル: crackme
配布ファイルのcracmeを調べてみると、64-bit ELFでした:
$ file * crackme: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=d69092bd1aa8d178ec76bf9c7ac6ad33b4c6fda6, for GNU/Linux 3.2.0, not stripped $
IDAで開きました。64-bitプログラムなのでFree版でもクラウドベースの逆コンパイルができます:
int __cdecl main(int argc, const char **argv, const char **envp) { int i; // [rsp+18h] [rbp-8h] _BOOL4 v5; // [rsp+1Ch] [rbp-4h] v5 = 0; if ( argc == 1 ) { puts("Usage: crackme <flag>"); } else if ( strlen(argv[1]) == 31 ) { for ( i = 0; i <= 30; ++i ) { v5 = calc(argv[1][i], a[i], b[i]); if ( !v5 ) break; } if ( v5 ) { printf("Conguratulations!! Flag is %s\n", argv[1]); return 1; } } else { puts("Oops, Try again."); } return 0; } _BOOL8 __fastcall calc(char a1, int a2, int a3) { return a2 * a1 + a1 * a1 + a3 == 0; }
ここでmain関数で使っているaとbはグローバル変数です:
.data:0000000000004060 public a .data:0000000000004060 ; unsigned int a[32] .data:0000000000004060 a dd 7Ah, 45h, 3Eh, 58h, 3Dh, 57h, 35h, 39h, 6Ch, 68h, 5Fh .data:0000000000004060 ; DATA XREF: main+7A↑o .data:0000000000004060 dd 49h, 3Ah, 38h, 54h, 61h, 34h, 60h, 38h, 8Dh, 56h, 4Ch .data:0000000000004060 dd 85h, 3Ah, 40h, 3Dh, 3Bh, 57h, 73h, 3Bh, 30h, 0 .data:00000000000040E0 public b .data:00000000000040E0 ; unsigned int b[32] .data:00000000000040E0 b dd 0FFFFC970h, 0FFFFC11Ah, 0FFFFB1A0h, 0FFFFB56Fh, 0FFFFB9C8h .data:00000000000040E0 ; DATA XREF: main+63↑o .data:00000000000040E0 dd 0FFFFBA48h, 0FFFFAC9Ah, 0FFFFC1AAh, 0FFFFD233h, 0FFFFC250h .data:00000000000040E0 dd 0FFFFD2E2h, 0FFFFA1D4h, 0FFFFB485h, 0FFFFB0EFh, 0FFFFBB6Bh .data:00000000000040E0 dd 0FFFFB30Ch, 0FFFFB614h, 0FFFFB6DFh, 0FFFFB210h, 0FFFFDBA2h .data:00000000000040E0 dd 0FFFFB875h, 0FFFFC08Bh, 0FFFFDB58h, 0FFFFB485h, 0FFFFAD47h .data:00000000000040E0 dd 0FFFFC422h, 0FFFFB0B4h, 0FFFFB140h, 0FFFFE170h, 0FFFFB762h .data:00000000000040E0 dd 0FFFFAB87h, 0
main関数では、31文字の入力それぞれについて、対応したindexのaとbの要素をcalc関数へ渡してチェックしていることが分かります。ここまで分かったので、各位置の文字が何かを総当りで検索するソルバーを書きました(グローバル変数の内容はテキストエディタで整形しました。もっといい方法はあるんでしょうか……？):
#!/usr/bin/env python3.8 def attack_calc(a, b): for i in range(0, 128): if ((i*a + i*i + b) & 0xFFFFFFFF) == 0: return i return None def split_as_int_array(s): result = [] for element in s.split(", "): if element[-1] == "h": element = element[:-1] result.append(int(element, 16)) return result a = "7Ah, 45h, 3Eh, 58h, 3Dh, 57h, 35h, 39h, 6Ch, 68h, 5Fh, 49h, 3Ah, 38h, 54h, 61h, 34h, 60h, 38h, 8Dh, 56h, 4Ch, 85h, 3Ah, 40h, 3Dh, 3Bh, 57h, 73h, 3Bh, 30h" b = "0FFFFC970h, 0FFFFC11Ah, 0FFFFB1A0h, 0FFFFB56Fh, 0FFFFB9C8h, 0FFFFBA48h, 0FFFFAC9Ah, 0FFFFC1AAh, 0FFFFD233h, 0FFFFC250h, 0FFFFD2E2h, 0FFFFA1D4h, 0FFFFB485h, 0FFFFB0EFh, 0FFFFBB6Bh, 0FFFFB30Ch, 0FFFFB614h, 0FFFFB6DFh, 0FFFFB210h, 0FFFFDBA2h, 0FFFFB875h, 0FFFFC08Bh, 0FFFFDB58h, 0FFFFB485h, 0FFFFAD47h, 0FFFFC422h, 0FFFFB0B4h, 0FFFFB140h, 0FFFFE170h, 0FFFFB762h, 0FFFFAB87h" a_list = split_as_int_array(a) b_list = split_as_int_array(b) assert(len(a_list) == 31) assert(len(b_list) == 31) for i in range(31): c = attack_calc(a_list[i], b_list[i]) print(chr(c), end="") print()
実行しました:
$ ./solve.py
HarekazeCTF{quadrat1c_3quati0n}
$
フラグを入手できました: HarekazeCTF{quadrat1c_3quati0n}
[Reversing] Pack Program (428 points, 3 Solves)
プログラムに隠されたフラグを探してください 添付ファイル: challenge
配布ファイルのchallengeを調べてみると、32-bit EXEでした(Windows Defenderが配布ファイルに反応して隔離してくるのでちょっと大変でした。一時的にWindows Defenderを無効化することで対応しました。):
$ file challenge challenge: PE32 executable (console) Intel 80386, for MS Windows, UPX compressed $
この時点でUPX圧縮されていると認識されています。それではupxで展開を、と試すと失敗してしまいました:
$ upx -d challenge
Ultimate Packer for eXecutables
Copyright (C) 1996 - 2017
UPX 3.94 Markus Oberhumer, Laszlo Molnar & John Reiser May 12th 2017
File size Ratio Format Name
-------------------- ------ ----------- -----------
upx: challenge: CantUnpackException: file is modified/hacked/protected; take care!!!
Unpacked 0 files.
$
仕方がないのでデバッガー経由で起動することにしました。UPX圧縮されているので、popaされている箇所でブレークしてメモリダンプするとパック元のプログラムが展開できるはずです。IDAで開いて、Alt+Tでpopaを検索しました:
UPX1:004726AE 04C popa UPX1:004726AF 02C lea eax, [esp+2Ch+var_AC] UPX1:004726B3 UPX1:004726B3 loc_4726B3: ; CODE XREF: start+1D7↓j UPX1:004726B3 02C push 0 UPX1:004726B5 030 cmp esp, eax UPX1:004726B7 030 jnz short loc_4726B3 UPX1:004726B9 030 sub esp, 0FFFFFF80h UPX1:004726BC -50 jmp near ptr dword_401118 UPX1:004726BC start endp ; sp-analysis failed
(解いた後に思ったことですけど、今回のプログラムはASLRに対応しているEXEです。デバッガーでのアドレス指定がやりづらくなるので、事前にDllCharacteristicsのIMAGE_DLLCHARACTERISTICS_DYNAMIC_BASEビットを下ろしたEXEを用意しておくとやりやすくなったのかなと思いました。)
x64dbgの32-bit版プログラムのx32dbgを起動して配布ファイルのデバッグを開始します。popa箇所にブレークポイントを貼って実行してブレークさせて、メニューの「Plugins→OllyDumpEx→Dump Process」を選びます。表示されるダイアログ右上のDumpボタンでEXE形式としてダンプします。
ダンプしたEXEをとりあえずstringsで調べてみると、5jqb5bvFEphcP4DHcvWM9rr46tVjjpxX4tMJImtyvoNhfIQazYJ4Z7a7oJo=という怪しい文字列が目に止まりました。IDAで開いてその文字列が使われている場所を見ると、1つの関数でのみ使われていました(今回は32-bitプログラムなので、Free版のクラウドベースでは逆コンパイルできません):
UPX0:00FD76A0 sub_FD76A0 proc near ; CODE XREF: sub_FD357B↑j UPX0:00FD76A0 UPX0:00FD76A0 var_1C = dword ptr -1Ch UPX0:00FD76A0 var_18 = dword ptr -18h UPX0:00FD76A0 var_14 = dword ptr -14h UPX0:00FD76A0 var_10 = dword ptr -10h UPX0:00FD76A0 var_C = dword ptr -0Ch UPX0:00FD76A0 var_8 = dword ptr -8 UPX0:00FD76A0 var_4 = dword ptr -4 UPX0:00FD76A0 UPX0:00FD76A0 000 push ebp UPX0:00FD76A1 004 mov ebp, esp UPX0:00FD76A3 004 sub esp, 1Ch UPX0:00FD76A6 020 mov [ebp+var_10], offset aN96t6tpfeelhk0 ; "n96t6tPFEElhk0uSjcoeJasW" UPX0:00FD76AD 020 push 40h ; '@' UPX0:00FD76AF 024 call sub_FD1316 UPX0:00FD76B4 024 add esp, 4 UPX0:00FD76B7 020 mov [ebp+var_4], eax UPX0:00FD76BA 020 push 10h UPX0:00FD76BC 024 push 0 UPX0:00FD76BE 028 mov eax, [ebp+var_4] UPX0:00FD76C1 028 push eax UPX0:00FD76C2 02C call sub_FD21E9 UPX0:00FD76C7 02C add esp, 0Ch UPX0:00FD76CA 020 mov [ebp+var_8], offset a6jtjBRsjzxblgc ; "6jTJ+b/RSJZxBLGcVcbglt==" UPX0:00FD76D1 020 mov ecx, [ebp+var_4] UPX0:00FD76D4 020 push ecx UPX0:00FD76D5 024 mov edx, [ebp+var_8] UPX0:00FD76D8 024 push edx UPX0:00FD76D9 028 call sub_FD3C2E UPX0:00FD76DE 028 add esp, 4 UPX0:00FD76E1 024 push eax UPX0:00FD76E2 028 mov eax, [ebp+var_8] UPX0:00FD76E5 028 push eax UPX0:00FD76E6 02C call sub_FD38E1 UPX0:00FD76EB 02C add esp, 8 UPX0:00FD76EE 024 push eax UPX0:00FD76EF 028 mov ecx, [ebp+var_10] UPX0:00FD76F2 028 push ecx UPX0:00FD76F3 02C call sub_FD3341 UPX0:00FD76F8 02C add esp, 0Ch UPX0:00FD76FB 020 mov [ebp+var_18], eax UPX0:00FD76FE 020 cmp [ebp+var_18], 0 UPX0:00FD7702 020 jnz short loc_FD7717 UPX0:00FD7704 020 mov edx, [ebp+var_4] UPX0:00FD7707 020 push edx UPX0:00FD7708 024 push offset a16s ; "%.16s" UPX0:00FD770D 028 call sub_FD19BF UPX0:00FD7712 028 add esp, 8 UPX0:00FD7715 020 jmp short loc_FD7769 UPX0:00FD7717 ; --------------------------------------------------------------------------- UPX0:00FD7717 UPX0:00FD7717 loc_FD7717: ; CODE XREF: sub_FD76A0+62↑j UPX0:00FD7717 020 push 78h ; 'x' UPX0:00FD7719 024 call sub_FD1316 UPX0:00FD771E 024 add esp, 4 UPX0:00FD7721 020 mov [ebp+var_14], eax UPX0:00FD7724 020 mov [ebp+var_C], offset a5jqb5bvfephcp4 ; "5jqb5bvFEphcP4DHcvWM9rr46tVjjpxX4tMJImt"... UPX0:00FD772B 020 mov eax, [ebp+var_14] UPX0:00FD772E 020 push eax UPX0:00FD772F 024 mov ecx, [ebp+var_C] UPX0:00FD7732 024 push ecx UPX0:00FD7733 028 call sub_FD3C2E UPX0:00FD7738 028 add esp, 4 UPX0:00FD773B 024 push eax UPX0:00FD773C 028 mov edx, [ebp+var_C] UPX0:00FD773F 028 push edx UPX0:00FD7740 02C call sub_FD38E1 UPX0:00FD7745 02C add esp, 8 UPX0:00FD7748 024 push eax UPX0:00FD7749 028 mov eax, [ebp+var_10] UPX0:00FD774C 028 push eax UPX0:00FD774D 02C call sub_FD3341 UPX0:00FD7752 02C add esp, 0Ch UPX0:00FD7755 020 mov [ebp+var_1C], eax UPX0:00FD7758 020 mov ecx, [ebp+var_14] UPX0:00FD775B 020 push ecx UPX0:00FD775C 024 push offset aFlagIsS ; "flag is %s" UPX0:00FD7761 028 call sub_FD19BF UPX0:00FD7766 028 add esp, 8 UPX0:00FD7769 UPX0:00FD7769 loc_FD7769: ; CODE XREF: sub_FD76A0+75↑j UPX0:00FD7769 020 xor eax, eax UPX0:00FD776B 020 mov esp, ebp UPX0:00FD776D 004 pop ebp UPX0:00FD776E 000 retn UPX0:00FD776E sub_FD76A0 endp
UPX0:00FD775C箇所に"flag is %s"という文字列が見えること、そこへいくかどうかはUPX0:00FD7702 020 jnz short loc_FD7717の分岐で切り替わることが分かります。とりあえずその分岐へブレークポイントを貼って実行を続行すると、ブレークしてくれました。そのままでは反対の方向へ行ってしまう状態だったので、EFLAGレジスタのZFを反転させました。そのまま実行を続けてUPX0:00FD7761 028 call sub_FD19BF箇所の引数の調べると、フラグが書かれていました:
ようやくフラグを入手できました: HarekazeCTF{rc4_1s_c0mmonly_us3d_1n_m@lwar3}
ところで12月24日だからか、x32dbgの右クリックメニューがクリスマス仕様のアイコンになっていました。思いがけないイースターエッグでびっくりしました:
[Crypto] first exam (134 points, 52 Solves)
kurenaif魔法学校の入学試験です。PythonでCrypto問を解く基礎を学んでください！ Attachments first_exam
配布ファイルには、problem.pyと、その出力のoutput.txtがありました:
import base64 import random # flag.py から flag を読み込みます。flag.pyは非公開なので、手元でデバッグするときは自分でテスト用のファイルを生成してください。 # Load the flag from flag.py. Since flag.py is not public, you can generate your own test file for debugging at hand. from flag import flag # pycryptodomeから(https://pycryptodome.readthedocs.io/en/latest/) import します。使えない場合は `pip3 install pycryptodome` をしてください # import from pycryptodome (https://pycryptodome.readthedocs.io/en/latest/). If you can't run this problem, do `pip3 install pycryptodome` from Crypto.Util.number import long_to_bytes, bytes_to_long flag = base64.b64encode(flag) flag = bytes_to_long(flag) key = random.randrange(flag) flag = flag ^ key print(f"{key = }") print(f"{flag = }")
key = 407773567691797768945309646881381330143924911048532252374484400956007416406007936505301187512369384531883020224488253602523154102140950477859193 flag = 1392812161183976577227166142672085037819799462496681473937900208451109718213256601589927195482395914799893761610554140977947503369343069077952836
とても丁寧なコメントが書かれたスクリプトです。出力にkeyも含まれているので、それを使って各種処理を逆順に処理するソルバーを書きました:
#!/usr/bin/env python3.8 from Crypto.Util.number import long_to_bytes, bytes_to_long import base64 key = 407773567691797768945309646881381330143924911048532252374484400956007416406007936505301187512369384531883020224488253602523154102140950477859193 flag = 1392812161183976577227166142672085037819799462496681473937900208451109718213256601589927195482395914799893761610554140977947503369343069077952836 print(base64.b64decode(long_to_bytes(key ^ flag)).decode())
実行しました:
$ ./solve.py
HarekazeCTF{OK_you_can_join_wizardry_school}
$
フラグを入手できました: HarekazeCTF{OK_you_can_join_wizardry_school}
[Crypto] sage training (179 points, 27 Solves)
一緒にsageに入門しよう！ Attachments sage_training
配布ファイルには、problem.sageと、その出力のoutput.txtがありました:
# この問題ではsagemath(https://www.sagemath.org/)を利用します。 # インストールして、 `sage problem.sage` コマンドを実行することで実行することができます。 # this problem requires `sagemath(https://www.sagemath.org/)`. # you can run `sage problem.sage` after install this tool. # *sagemathに* pycryptodomeを入れる必要があります。 # `sage --sh` コマンドでshellに入った後、`pip install pycryptodome` で Python の module をインストールすることが可能です。 # to solve this problem, you have to install `pycryptodome`. # After entering the shell with the command `sage --sh`, you can use `pip install pycryptodome` to install the Python module. from Crypto.Util.number import * from flag import flag # bytes <- str flag = flag.encode('utf-8') # long <- bytes flag = bytes_to_long(flag) p = getStrongPrime(512) q = getStrongPrime(512) n = p*q e = 65537 # 計算するたびに mod n を取る 行列を生成します。 # generate matrix which calculate modulus n at every operation. m = matrix(Zmod(n), [ [p, 0], [0, flag] ]) # sagemathでは ^ は xor を表さずに、冪乗を表しています。 # in sagemath, ^ means exponentiation. not `xor` m = m^e # listで二次元配列に変換します。 # convert two-dimensional array by list() function print("c =",list(m)) print("n =",n) print("e =",e) # hint 1 # c = [? 0] <= what's ? # [0 ?] <= what's ? # hint 2 # JP: https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0 # EN: https://en.wikipedia.org/wiki/Greatest_common_divisor
c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0), (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)] n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609 e = 65537
problem.sageでは対角行列をe乗しているので、cの対角成分はそれぞれp^eとflag^eになります。n = p*qであるため、gcd(p^e, n)でpを抽出できます。するとqを計算でき、dも計算できるのでフラグを復号できます。それを使ったソルバーを書きました:
#!/usr/bin/env python3.8 import math from Crypto.Util.number import long_to_bytes c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0), (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)] n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609 e = 65537 c_elem = c[1][1] p = math.gcd(c[0][0], n) q = n // p assert p*q == n d = pow(e, -1, (p-1)*(q-1)) m = pow(c[1][1], d, n) print(long_to_bytes(m).decode())
実行しました:
$ ./solve.py
HarekazeCTF{which_do_you_like_mage_or_sage?}
$
フラグを入手できました: HarekazeCTF{which_do_you_like_mage_or_sage?}
[Crypto] mulmulmulti-prime rsa (215 points, 18 Solves)
とっても安全なRSA暗号をより安全にするためにたくさん素数をかけました♥ Attachments mulmulmulti-prime_rsa
配布ファイルには、problem.pyと、その出力のoutput.txtがありました:
from sympy.ntheory.modular import crt from Crypto.Util.number import * from Crypto.Random.random import * from flag import flag flag = bytes_to_long(flag) N = 1 num = 2 while N < flag: if isPrime(num): N *= num num += 1 p = getStrongPrime(512) q = getStrongPrime(512) N = N * p * q e = 65537 c = pow(flag, e, N) print("bit_length =", flag.bit_length()) print("c =", c) print("e =", e) print("N =", N)
bit_length = 535 c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175 e = 65537 N = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730
from sympy.ntheory.modular import crt行がありますが、crt関数は使用していません。これはヒントだと解釈しました。Nは素因数に小さな素数の積を含んでおり、その大きさはflagよりも大きいです。そのため中国剰余定理が実際に刺さりそうです。その後は多分復号できると信じて、試行錯誤してソルバーを書きました(解法の証明はしていません……):
#!/usr/bin/env python3.8 from sympy.ntheory.modular import crt from Crypto.Util.number import long_to_bytes, isPrime bit_length = 535 c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175 e = 65537 N = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730 U = [] M = [] phi = 1 for i in range(2, N): if isPrime(i): if N % i != 0: break U.append(c % i) M.append(i) phi *= (i - 1) # https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.modular.crt (c2, n2) = crt(M, U) d = pow(e, -1, phi) m = pow(c2, d, n2) print(long_to_bytes(m).decode())
実行しました:
$ ./solve.py
HarekazeCTF{Small_prime_numbers_give_a_large_amount_of_information}
$
フラグを入手できました: HarekazeCTF{Small_prime_numbers_give_a_large_amount_of_information}
感想
- 3時間は短いです！1問にのめり込むうちの他の問題に取り組む時間がどんどん減っていきました……。
- 残ったReversingジャンルの問題はWASMを読む問題でした。ググってみるとwasm2cが便利らしいので試しましたが
Aborted (core dumped)となって絶望していました。 - パッキング系問題を解けたのは嬉しいです。
