R4v!dus

CODEGATE 2022 암호학 문제입니다.

풀이에는 실패했으나 접근 방식은 맞았었기에 아쉬운 마음이 커서 작성하게 되었습니다.

암호학 방식은 RSA입니다.(Bold 쳐진 부분은 solver의 설명을 참조한 부분입니다.)

문제 분석

#!/usr/bin/python3
from Crypto.Util.number import *
import os

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS 
FLAG = b'codegate2022{this_is_a_sample_flag}'

def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))     
        p = UPPER | lower
        if isPrime(p): return lower    # p가 소수면 lower 반환

def menu2():
    p = UPPER + menu1()     
    q = getPrime(512)       
    e = 65537               
    n = p * q              
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
    
   
while True:
    print("1. Generate 10 random primes (only lower bits)")
    print("2. Encrypt a flag")
    idx = int(input("> "))
    if idx == 1:
        print("How many? (Up to 10)")
        num = int(input("> "))
        for _ in range(min(10, num)):
            print(menu1())             
    elif idx == 2:
        n, c = menu2()
        print(f"n : {n}")              
        print(f"c : {c}")                            
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS

본 대회에서 제공된 문제 코드입니다.

문제 풀이를 위해 코드 분석부터 해보도록 하겠습니다.

크게 menu1과 menu2 두가지 부분으로 나뉩니다.

def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))     
        p = UPPER | lower
        if isPrime(p): return lower

menu1 : p가 소수면 216 비트(25 바이트) lower 값을 반환합니다.

어떻게든 UPPER 값을 찾을 수 있다면 p의 상위 비트 중 절반 이상을 알 수 있으므로 Coppersmith 알고리즘을 사용하는 표준 RSA 공격을 통해 n을 인수분해할 수 있습니다.

이는 특정 소수에 대한 나머지 후보를 제거할 수 있습니다.

UPPER + lower가 소수가 되도록 충분한 수의 lower가 주어지면 각 소수 p<700에 대해 UPPER (mod p)에 대해 하나의 가능한 후보를 제외하고 모두 제거할 수 있습니다. 이는 소수 p<700에 대해 UPPER (mod p)를 복구할 수 있음을 의미합니다.

def menu2():
    p = UPPER + menu1()     # UPPER + lower
    q = getPrime(512)       # 512 비트 소수
    e = 65537               # 65537 알려진 지수 공격
    n = p * q               # 공개키에 사용되는 (e, n) -> (65537, n) 
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)

menu2 : FLAG값을 포함하여 연산한 값에 FLAG가 포함되어 있습니다.

#!/usr/bin/python3
from Crypto.Util.number import *
import os

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS # 37바이트, 206비트만큼 왼쪽으로 이동
FLAG = b'codegate2022{this_is_a_sample_flag}'

def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))      # 25바이트
        p = UPPER | lower
        if isPrime(p): return lower    # p가 소수면 lower 반환

def menu2():
    p = UPPER + menu1()     # UPPER + lower
    q = getPrime(512)       # 512 비트 소수
    e = 65537               # 65537 알려진 지수 공격
    n = p * q               # 공개키에 사용되는 (e, n) -> (65537, n) 
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
    
    # bytes_to_long(codegate2022{this_is_a_sample_flag} + 0x00 + random(91))만큼 랜덤 비트 생성^65537 % n

while True:
    print("1. Generate 10 random primes (only lower bits)")
    print("2. Encrypt a flag")
    idx = int(input("> "))
    if idx == 1:
        print("How many? (Up to 10)")
        num = int(input("> "))
        for _ in range(min(10, num)):
            print(menu1())              # lower값 획득
    elif idx == 2:
        n, c = menu2()
        print(f"n : {n}")               # n
        print(f"c : {c}")               #  bytes_to_long(codegate2022{this_is_a_sample_flag} + 0x00 + random(91))만큼 랜덤 비트 생성^65537 % n                 
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS    # 37바이트, 206비트만큼 왼쪽으로 이동

최종적으로 분석한 내용은 위와 같습니다.

문제 풀이

#!/usr/bin/sage
from Crypto.Util.number import *
from pwn import *
from sage.all import *
import math

r = remote("localhost", 9001)

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659]

remainders = [set([x for x in range(p)]) for p in primes]

def prod(L):
    val = 1
    for x in L:
        val *= x
    return val

def get_lower():
    r.recvuntil(b"> ")
    r.sendline(b"1")
    r.recvuntil(b"> ")
    r.sendline(b"10")
    return [int(r.recvline()) for _ in range(10)]

def get_nc():
    r.recvuntil(b"> ")
    r.sendline(b"2")
    r.recvuntil(b"n : ")
    n = int(r.recvline())
    r.recvuntil(b"c : ")
    c = int(r.recvline())
    return n, c

def rsa_high_bits_known(n, c, upper):
    F.<x> = PolynomialRing(Zmod(n), implementation='NTL'); 
    pol = x - upper
    beta = 0.48  # we should have q >= N^beta
    XX = 2 ** LOWER_BITS
    epsilon = beta / 7
    rt = pol.small_roots(XX, beta, epsilon)  
    q = int(gcd(rt[0] - upper, n))
    p = int(n) // int(q)
    assert(p*q == n and p > 1 and q > 1)
    phi = (p-1)*(q-1)
    e = 0x10001
    d = int(pow(e, -1, phi))
    plain = int(pow(c, d, n))
    print(long_to_bytes(plain))

#### STEP 1. Recover UPPER using crt ####
print("[+] STEP 1. Recover UPPER using crt")
crt_a = [0]
crt_m = [2**LOWER_BITS]

cnt = 0
while prod(crt_m) < 2**BITS:
    cnt += 1
    if cnt % 10 == 0:
        print(f"Gather {cnt*10} primes.. progress : {int(100 * (math.log2(prod(crt_m))-LOWER_BITS) / UPPER_BITS)}%")
    lowers = get_lower()
    for lower in lowers:
        for i in range(len(primes)):
            rem = lower % primes[i]
            if rem in remainders[i]:
                remainders[i].remove(rem)
                if len(remainders[i]) == 1:
                    crt_a.append(primes[i] - remainders[i].pop())
                    crt_m.append(primes[i])

upper = crt(crt_a, crt_m)
print(f"[+]UPPER = {upper.hex()}")

#### STEP 2. Recover FLAG using RSA Factoring with high bits known attack ###
print("[+] STEP 2. Recover FLAG using RSA Factoring with high bits known attack")
n, c = get_nc()
rsa_high_bits_known(n, c, upper)

위 코드는 solver barkingdog의 풀이 코드로 본 문제 이해에 있어 많은 도움이 되었습니다.

추후 시간이 남는다면 풀이 코드에 대한 해설도 적어보도록 하겠습니다.

암호는 너무 어려운거 같습니다...

CODEGATE2022 문제입니다.

Description :

You can enjoy this cafe :)

upload text, youtube, ...

본 사이트에서 텍스트 업로드 유튜브 등 사용하여 보세요 :) 라고 설명하고 있습니다.

이때만 해도 업로드란 단어에 포커싱이 되어 파일 업로드로 푸는 문제인줄 알고 착각하였습니다.

문제 분석

login, search, write 등 많은 기능들이 존재합니다.

write에서 파일 업로드를 수행하는 줄 알고 접근하였으나 실패하여 코드를 살펴보았습니다.

그 중 bot.py가 존재하는 것을 보고 이를 살펴보았습니다.

코드는 다음과 같았습니다.

#!/usr/bin/python3
from selenium import webdriver
from selenium.webdriver.chrome.options import Options
from webdriver_manager.chrome import ChromeDriverManager
import time
import sys

options = webdriver.ChromeOptions()

options.add_argument('--headless')
options.add_argument('--disable-logging')
options.add_argument('--disable-dev-shm-usage')
options.add_argument('--no-sandbox')
#options.add_argument("user-agent=Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36")

driver = webdriver.Chrome(ChromeDriverManager().install(),options=options)
driver.implicitly_wait(3)

driver.get('http://3.39.55.38:1929/login')
driver.find_element_by_id('id').send_keys('admin')
driver.find_element_by_id('pw').send_keys('$MiLEYEN4')
driver.find_element_by_id('submit').click()
time.sleep(2)

driver.get('http://3.39.55.38:1929/read?no=' + str(sys.argv[1]))
time.sleep(2)

driver.quit()

의도치 않게 표기되어 있는 admin 계정의 id와 pw를 확인하게 되었습니다.

driver.find_element_by_id('id').send_keys('admin')
driver.find_element_by_id('pw').send_keys('$MiLEYEN4')

이를 사용하여 로그인을 진행하였더니 flag를 확인할수 있었습니다.