comibear
article thumbnail
Published 2023. 4. 14. 13:53
[Midnight Sun CTF 2023] - Mt.Random Cryptography/CTF

요즘은 해킹 분야보다는 블록체인에 관심이 많이 생겨서 해킹 공부를 쉰 지 조금 되었다.. 이번에 처음으로 동아리 사람들과 모여서 함께 CTF 문제를 풀어보는 시간을 가졌는데, 뭔가 나 혼자 뒤쳐진 느낌이 들었다. 뭔가 스스로 한심하기도 하고 ~ 다시 열심히 해야겠다는 생각이 들어서 지금까지 했던 모든 포스팅을 지우고 나서 다시 초심을 찾아보려고 한다. 파이팅..!! 😊

🖲️ Code Analysis

크립토 문제답지 않게 PHP 로 작성된 웹 페이지를 제공해주었다. 먼저 HTML 소스를 보도록 하자.

( 내가 문제를 아카이빙 해서 comibear.kr 에 그대로 만들어 놓았는데, 직접 해보고 싶은 사람은 문제 사이트로 가서 직접 풀어보도록 하자 > < )

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Mt. Random</title>
</head>
<body>
    <h1>Hiking Guide</h1>
    <p>This mountain is boring, I'm going to sample alot of seeds!</p>
    <a href="?generate_samples=1">Get a new sample</a>
</body>
</html>

일단 첫번째로 HTML 코드에는 별 게 없는 것 같다. 한 가지 기능을 살펴보자면, Get a new sample 이라는 링크를 클릭하면, 파라미터로 generate_samples 을 1 로 설정해주게 된다. generate samples 가 도대체 무슨 기능을 가졌을지 PHP 코드를 살펴보도록 하자.

<?php
session_start();

$flag = "midnight{***redacted***}";

function flag_to_numbers($flag) {
    $numbers = [];
    foreach (str_split($flag) as $char) {
        $numbers[] = ord($char);
    }
    return $numbers;
}

function non_continuous_sample($min, $max, $gap_start, $gap_end) {
    $rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
    if ($rand_num >= $gap_start) {
        $rand_num += ($gap_end - $gap_start);
    }
    return $rand_num;
}

if(!str_starts_with($flag, "midnight{")){
    echo "Come back later.\n";
    exit();
}

$flag_numbers = flag_to_numbers($flag);

if (isset($_GET['generate_samples'])) {
    header('Content-Type: application/json');

    // Maybe we can recover these constants
    $min = 0;
    $max = 0;
    $gap_start = 0;
    $gap_end = 0;
    $seed = mt_rand(0, 10000); // Varying seed
    $samples = [];

    foreach ($flag_numbers as $number) {
        mt_srand($seed + $number);
        $samples[] = non_continuous_sample($min, $max, $gap_start, $gap_end);
    }

    echo json_encode(["samples" => $samples]);
    exit();
}
?>

아까 보았던 generate_smaples 라는 파라미터가 정의되었을 때, if 문이 실행되는 구문이 있다. 여러 변수들을 정의하고, 각 flag 의 문자를 하나의 메르센 트위스터의 시드로써 작동하게 된다.

 

그 후에, non_continuous_smaple 이라는 함수를 실행하게 되는데, 그 함수에 대해서 간략하게 알아보자.

function non_continuous_sample($min, $max, $gap_start, $gap_end) {
    $rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
    if ($rand_num >= $gap_start) {
        $rand_num += ($gap_end - $gap_start);
    }
    return $rand_num;
}

잘 보면, min 부터 max - (gap_end - gap_start) 까지의 랜덤값을 rand_num 으로 정의하게 된다. 하지만, 이 rand_num 이라는 값이 gap_start 보다 크다면, gap_end - gap_start 를 더해주어 gap_end 보다 크도록 만들어준다.

 

이 말은, min 부터 max 까지의 랜덤값을 추출하지만, gap_start 부터 gap_end 까지의 범위에는 나오지 않도록 설정해주는 기능이라고 볼 수 있다.

 

결론은, 각 generate 를 할 때마다, min, max 등의 변수값 그리고 seed 값을 사용해서 반복문의 형태로 랜덤값을 출력해주는 기능을 가졌다고 판단할 수 있겠다. ( 여기서 flag 의 바이트들은 seed 에 순차적으로 더해지며 seed 를 랜덤화하게 된다. )

💡 Main Idea

문제 이름은 Mt.Random 이라고 되어 있어서 처음에는 메르센 트위스터를 이용해서 다음 랜덤값을 예측하는 형태의 문제라고 생각했었다. 하지만 다시 생각해보니 적당한 브루트포싱만으로 문제를 해결할 수 있겠다는 생각을 해서 코드를 작성해 보았다.

 

먼저 랜덤값이 정의될 때, 모든 랜덤값이 0 으로 정의되었기 때문에 정확한 값을 알아줄 필요가 있다. 따라서 1 부터 256 까지의 리스트를 형성하여 절대 나오지 않는 gap 들을 알아볼 것이다. ( 여기서 1 부터 256 이라는 min 과 max 를 정한 이유는, 엄밀하게 따지면 이 또한 코드로써 작성해야 하지만 귀납적인 이유로 생략했다. )

import requests
import json
URL = "http://comibear.kr/?generate_samples=1"

def get():
    res = requests.get(URL)
    res = json.loads(res.text)
    return res['samples']

test = [i for i in range(256)]
while True:
    for c in get():
        if c in test:
            test.remove(c)
    print(f"maybe gap is {test[0]} to {test[-1]}")

이 코드를 실행해보면, 다음과 같은 결과가 나오게 되어 gap 은 100 부터 150 까지라고 판단할 수 있게 된다. 결국은 모든 변수를 알아냈기 때문에, flag 브루트 포싱이 가능하게 된다.

 

이렇게 gap 들을 알아낼 수 있어 결국 임의의 출력값을 통해 seed 를 알아내고, 그 seed 를 사용해 브루트 포싱을 할 수 있게 된다. 브루트 포싱을 통해 seed 를 알아내는 코드를 작성해보자. 

<?php
    $flag = "midnight{";
    $flag_len = strlen($flag);
    $ans = [21,7,42,71,7,220,238,154,163,21,252,71,42,57,154,238,185,57,220,35,1,156];

    function non_continuous_sample($min, $max, $gap_start, $gap_end) {
        $rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
        if ($rand_num >= $gap_start) {
            $rand_num += ($gap_end - $gap_start);
        }
        return $rand_num;
    }

    function flag_to_numbers($flag) {
        $numbers = [];
        foreach (str_split($flag) as $char) {
            $numbers[] = ord($char);
        }
        return $numbers;
    }

    $flag_numbers = flag_to_numbers($flag);

    for($new_seed = 0; $new_seed <= 10000; $new_seed++) {

        $min = 1;
        $max = 256;
        $gap_start = 100;
        $gap_end = 150;
        $dump = mt_rand(0,10000);
        $seed = $new_seed;
        $samples = [];

        foreach ($flag_numbers as $number) {
            mt_srand($seed + $number);
            $samples[] = non_continuous_sample($min, $max, $gap_start, $gap_end);
        }

        if (array_slice($samples,0,$flag_len) == array_slice($ans,0,$flag_len)) {
            echo $seed . "\n";
        }
    }
?>

별 아이디어 없이 그냥 찐 브루트포싱이라 딱히 설명할 게 없다...

 

따라서 seed 는 8336 이라고 알아낼 수 있다 !!

📖 Exploit Code

<?php
    $flag = "midnight{";
    $valid = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890_{}";
    $length = strlen($valid);
    $ans = [21,7,42,71,7,220,238,154,163,21,252,71,42,57,154,238,185,57,220,35,1,156];

    function non_continuous_sample($min, $max, $gap_start, $gap_end) {
        $rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
        if ($rand_num >= $gap_start) {
            $rand_num += ($gap_end - $gap_start);
        }
        return $rand_num;
    }

    function flag_to_numbers($flag) {
        $numbers = [];
        foreach (str_split($flag) as $char) {
            $numbers[] = ord($char);
        }
        return $numbers;
    }

    function dfs($flag) {
        global $ans;
        global $valid;
        global $length;
        $flag_len = strlen($flag);
        if (strlen($flag) == 22) {
            echo $flag; echo "\n";
            return;
        }
        for($new = 0; $new < $length; $new++) {
            $newflag = $flag.$valid[$new];
            $flag_numbers = flag_to_numbers($newflag);

            $min = 1;
            $max = 256;
            $gap_start = 100;
            $gap_end = 150;
            $dump = mt_rand(0,10000);
            $seed = 8336;
            $samples = [];

            foreach ($flag_numbers as $number) {
                mt_srand($seed + $number);
                $samples[] = non_continuous_sample($min, $max, $gap_start, $gap_end);
            }

            if ($samples[$flag_len] == $ans[$flag_len]) {
                // echo $newflag;
                dfs($newflag);
            }
        }
    }
    dfs($flag);
?>

따라서 이렇게 코드를 작성해주면, dfs 알고리즘을 이용한 브루트 포싱이 가능할 것이다. 하지만 한 가지 seed 만 가지고 실행했기 때문에 이 ans list 가 출력되는 flag 들이 여러 가지 나올 수 있겠다. 이 경우에는 앞선 seed 만 변화시켜주며 모든 seed 를 만족하는 flag 의 값을 찾아주면 된다.

 

예상대로 많은 결과가 나왔는데, CTF 에서는 meaningful 한 string 이 flag 일 확률이 높기 때문에

 

Flag : midnight{m1nd_th3_g4p} 이다.

저작자표시

'Cryptography > CTF' 카테고리의 다른 글

[Kaist-Postech 2020] - Baby Bubmi  (0) 2023.04.18
[CodeGate 2022] - GIGA Cloud Storage  (0) 2023.04.17
[CodeGate 2022] - Hidden Command Service  (0) 2023.04.17
[HITCON 2022] - SuperPrime  (0) 2023.04.17
[HITCON 2022] - Babysss  (0) 2023.04.17
profile

comibear

@comibear

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그

Cryptography
CTF

티스토리툴바