はじめに
TsukuCTF 2023にWani Hackaseとして参加して1位を取ることができました。（完全にチームメイトのおかげですが）ということで折角なので参加記を残そうと思います。Qiita初投稿なのでところどころ読みづらかったり、説明不足だったりするかもしれませんが、大目に見てもらえたら助かります。
new cipher sceme[cry]
基本的にはRSAですが以下のmagic関数を用いてp+qを処理した値sが追加で得られます。
def magic2(a):
sum = 0
for i in range(a):
sum += i * 2 + 1
return sum
def magic(p, q, r):
x = p + q
for i in range(3):
x = magic2(x)
return x % r
ここからp+qを求めることができればn=p*qと合わせてp, qが得られるので嬉しい。
ということでぐっと睨んだり手を動かしたりすると、magic2は引数の二乗を返す関数だとわかります。
例１）$magic2(4) = 1+3+5+7 = 16$
例２）$magic2(6) = 1+3+5+7+9+11 = 36$
ここで、以下の処理
for i in range(3):
x = magic2(x)
は2乗を3回行っており、$x := x^{2^3} = x^8$と等しいです。
よって、magic関数は$x^8\ (mod\ r)$を返すのですが、奇素数rを法としたときの平方根はTonelli-Shanksのアルゴリズムを使うと求まるので、3回適用すれば$x\ (mod\ r)$が得られます。
ここで、
-
$p+q \simeq 2^{512}$
-
$r \simeq 2^{1024}$
であることから、$x\ (mod\ r) = x$です。
以上より、
- $x = p+q$
- $n = pq$
を解くことでp, qが得られるので、あとは$\phi$を計算して$d$を求めたらOKです。（実家のような安心感）
一見よくわからないmagic関数がp+qの8乗を返していたり、Tonelli-Shanksを3回使うことで8乗根が求められたりとcryptらしさが強くて面白い問題でした。
what_os[misc]
ざっと配布されたtty.txtを見ているとetc/gettyが目に入りました。調べてみるとUnix/Linux系統のOSにあるファイルのようです。
また、calコマンドで1971年と出力されているので「相当古いんだろうな～」と思いながら当てはまるものを調べていくとUnix Version1, Unix Version2などが条件を満たしそうです。
他のOS分からないし、ひとまず入れてみるかとUnixを試したらFlagが取れました。適当の極み
build_error[misc]
main.oとone.oをghidraでデコンパイルしていい感じに整形したらなんとかなるだろ！と頑張っていたら良さげなコードを作ることができました。
#include <bits/stdc++.h>
using namespace std;
long a, b, c;
void one_init();
int main(){
int i;
long local_30;
long loopLimit;
long local_20;
local_30 = 12;
loopLimit = 11;
local_20 = 75;
one_init();
for (i = 0; i < loopLimit; i = i + 1) {
if (i < local_30) {
local_20 = local_20 + 1;
}
if (local_20 < i) {
loopLimit = loopLimit + 1;
}
local_30 = local_30 + 1;
}
local_20 = local_20 + local_30 + loopLimit;
if (local_20 == c + a + b) {
printf("flag is %ld\n",local_20);
}
else {
puts("please retry");
}
return 0;
}
void one_init(void){
int local_c;
a = 0xc;
b = 0xb;
c = 0x4b;
for (local_c = 0; (ulong)(long)local_c < b; local_c = local_c + 1) {
if ((ulong)(long)local_c < a) {
c = c + 1;
}
if (c < (ulong)(long)local_c) {
b = b + 1;
}
a = a + 1;
}
return;
}
これを改めてコンパイルして実行することでFlagをGETしました。適当の極み２
変数名を色々付け直したり、ライブラリまで調べたりとghidraの練習に丁度いい問題でした。
最後に
TsukuCTFに参加するのは初めてでしたが様々なOSINT問題があって面白かったです。（解けたとは言っていない）
来年はOSINTも得点源にしていきたいですね。
運営の皆さん、楽しいCTFをありがとうございました。