[Google CTF 2023] PAPAPAPA | LEAST COMMON GENOMINATOR | UNDER-CONSTRUCTION

MISC

PAPAPAPA

- Is this image really just white?

 

문제 파일로 정사각형의 흰색 jpg 파일이 주어졌다.

 

 

HxD로 white.jpg 파일을 열어 시그니처 구조를 살펴봤는데 의심스러운 부분은 없었다.

옛날에 이렇게 이미지 파일이 주어지고 이미지 크기를 변경해서 플래그를 찾았던 경험이 있다.

이 문제도 그런 문제인가 싶어서 jpg 파일 시그니처를 좀 더 공부해봤다.

 

 

문제에서 이게 진짜 흰색이냐고 묻는 것을 보니 원본 이미지에 플래그를 적어놓고, 의도적으로 이미지 크기를 잘라 놓은 것인가 싶었다.

 

파일 크기를 조정하기 위해 JPG의 SOF에서 파일의 가로*세로 부분을 변경했다.

 

정사각형 이미지이기 때문에 가로 세로 크기가 0X0200, 512로 동일하다.

이 값을 조금씩 키워보았다.

02 08

02 10

이미지의 크기를 02 08, 520*520으로 바꾸었더니 플래그 값이 보이기 시작했다.

크기를 조금 더 키워서 02 10, 528*528로 바꾸었더니 플래그 값이 보였다.

 

CTF{rearview-monorail-mullets-brackroom-stopped}

---

CRYPTO

LEAST COMMON GENOMINATOR

Someone used this program to send me an encrypted message but I can't read it! It uses something called an LCG, do you know what it is? I dumped the first six consecutive values generated from it but what do I do with it?!

문제 파일로 총 4개가 제공됐다.

Python 코드와 코드를 실행할 때 필요한 세 개의 파일인 것 같다.

(암호화된 플래그, 정수 데이터, pem 공개 키)

 

문제에서 언급된 LCG가 정확히 무엇을 의미하는지 알아보았더니 선형 합동 생성기였고, 정의하면 아래와 같은 식을 얻을 수 있다.

s n+1 = as n + b mod m

https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator 이 URL을 많이 참고했다.

 

 

from secret import config
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime

class LCG:
    lcg_m = config.m
    lcg_c = config.c
    lcg_n = config.n

    def __init__(self, lcg_s):
        self.state = lcg_s

    def next(self):
        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
        return self.state

if __name__ == '__main__':

    assert 4096 % config.it == 0
    assert config.it == 8
    assert 4096 % config.bits == 0
    assert config.bits == 512

    # Find prime value of specified bits a specified amount of times
    seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
    lcg = LCG(seed)
    primes_arr = []

    dump = True
    items = 0
    dump_file = open("dump.txt", "w")

    primes_n = 1
    while True:
        for i in range(config.it):
            while True:
                prime_candidate = lcg.next()
                if dump:
                    dump_file.write(str(prime_candidate) + '\n')
                    items += 1
                    if items == 6:
                        dump = False
                        dump_file.close()
                if not isPrime(prime_candidate):
                    continue
                elif prime_candidate.bit_length() != config.bits:
                    continue
                else:
                    primes_n *= prime_candidate
                    primes_arr.append(prime_candidate)
                    break

        # Check bit length
        if primes_n.bit_length() > 4096:
            print("bit length", primes_n.bit_length())
            primes_arr.clear()
            primes_n = 1
            continue
        else:
            break

    # Create public key 'n'
    n = 1
    for j in primes_arr:
        n *= j
    print("[+] Public Key: ", n)
    print("[+] size: ", n.bit_length(), "bits")

    # Calculate totient 'Phi(n)'
    phi = 1
    for k in primes_arr:
        phi *= (k - 1)

    # Calculate private key 'd'
    d = pow(config.e, -1, phi)

    # Generate Flag
    assert config.flag.startswith(b"CTF{")
    assert config.flag.endswith(b"}")
    enc_flag = bytes_to_long(config.flag)
    assert enc_flag < n

    # Encrypt Flag
    _enc = pow(enc_flag, config.e, n)

    with open ("flag.txt", "wb") as flag_file:
        flag_file.write(_enc.to_bytes(n.bit_length(), "little"))

    # Export RSA Key
    rsa = RSA.construct((n, config.e))
    with open ("public.pem", "w") as pub_file:
        pub_file.write(rsa.exportKey().decode())

주어진 Python 코드를 분석했다.

LCG 특정 비트 길이의 소수를 생성하여, 총 8개의 소수가 512비트의 비트 길이로 생성된다.

해당 소수로부터 modulus와 totient가 생성되고 이를 이용하여 개인키를 만들어 암호화된다.

 

암호화 된 걸 복호화 하려면 앞서 생성된 개인키를 얻어야 한다.

개인키를 얻기 위해서는 위에서 생성된 8개의 소수가 필요하다. 이 소수를 구할 때 사용되는 식이 있는데, 이게 잘 이해가 되지 않아서 아래 링크에서 힌트를 많이 얻었다.

https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator

 

위 식을 참고하여 solve.py로 코드를 재 작성했다.

제공된 generater.py파일을 기반으로 아래와 같은 코드를 추가했다.

 

with open("public.pem", "rb") as file:

    key = RSA.importKey(file.read())
 
d = pow(key.e, -1, phi)

with open("flag.txt", "rb") as file:

    flag = int.from_bytes(file.read(), "little")

flag = pow(flag, d, n)

print(long_to_bytes(flag))

 

다행히 플래그 값이 잘 출력되었다.

개인적으로 좀 어려웠다..

 

CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

---

WEB

UNDER-CONSTRUCTION 

We were building a web app but the new CEO wants it remade in php.

 

https://under-construction-web.2023.ctfcompetition.com

https://under-construction-php-web.2023.ctfcompetition.com

2개의 URL과 flask, php 파일들이 제공되었다.

 $response = "Login successful. Welcome " . htmlspecialchars($username) . ".";

    if ($tier === "gold") {
        $response .= " " . getenv("FLAG");
    }

    return $response;

Index.php 파일에서 tier 값이 gold일 경우에 FLAG를 출력하는 것을 알 수 있었다.

 

URL에 접속해서 확인해 봐야겠다.

로그인과 회원가입을 할 수 있는 사이트(1)와 php 로그인 사이트(2)가 있었다.

Gold로 선택하면 회원가입이 되지 않았다.

Burp suite로 패킷을 확인해 봐야겠다.

회원가입 때 넣은 값들이 필터링 되지 않은 채 전송되고 있는 것을 알 수 있다.

이 값을 Intruder로 넘겨서 공격해봤다.

https://under-construction-web.2023.ctfcompetition.com/signup을 타겟으로 지정하고,

&tier=gold 부분을 Add $ 해주었다.

공격이 잘 진행되었다.

타겟으로 설정한 URL로 들어와 회원가입 시 사용했던 ID, PW를 입력해주었더니 FLAG 값을 얻을 수 있었다.

 

CTF{ff79e2741f21abd77dc48f17bab64c3d}