[🥉 Bronze 4] "로봇 인증"이 오히려 로봇에게 판을 깔아줬다 — DreamHack Robot Only 풀이

2026-07-20·1분 읽기·

[🥉 Bronze 4] "로봇 인증"이 오히려 로봇에게 판을 깔아줬다 — DreamHack Robot Only 풀이

숫자 하나를 3초 안에 그대로 되받아 타이핑하면 "로봇 인증"이 완료된다. 그 숫자는 Python random 모듈의 원시 출력 6개를 이어붙여 고정된 상수로 XOR한 값이라, 우리가 화면에서 읽는 순간 그 6개 숫자를 그대로 역산할 수 있다. 그리고 이 인증은 실패해도 몇 번이든 다시 시도할 수 있다 — 104번만 반복하면 Mersenne Twister의 내부 상태를 완전히 복원하는 데 필요한 624개의 연속된 원시값을 전부 모을 수 있다는 뜻이다. 그 뒤로는 서버가 뽑을 도박 게임의 정답을 베팅하기도 전에 알 수 있게 된다.

문제: DreamHack — Robot Only 분류: Misc / Crypto 난이도: 🥉 Bronze 4 FLAG: DH{0086b1776b2b2dac7aebb790ec005ecf2bcce345c52225f03bb177b47a357a40}

로봇만 들어갈 수 있는 카지노다. "로봇 인증"을 통과해야 도박(gamble)을 할 수 있고, 도박으로 100억 달러를 모아야 flag를 살 수 있다. 인증 방식이 흥미롭다 — 화면에 뜬 아주 큰 숫자를 3초 안에 그대로 타이핑해서 돌려주면 된다. 사람에겐 불가능에 가깝고 로봇(스크립트)에겐 식은 죽 먹기인, 말 그대로 "로봇만" 통과할 수 있는 관문이다.


문제 개요

항목내용
문제명Robot Only
난이도🥉 Bronze 4
분류Misc / Crypto
제공 파일robot_only.py
핵심 기법반복 가능한 인증 절차로 Python random(Mersenne Twister)의 내부 상태를 624개 연속 출력으로 완전 복원


🔬 정찰 — 인증 숫자는 그냥 XOR로 가려놓은 난수 6개

gamble()부터 보면 게임 규칙이 단순하다.

def get_randn():
    return random.randint(0, 0xfffffffe)
 
def gamble():
    if verified is False:
        print('you\'re are not verified as a robot ;[')
        return
    bet = int(input('how much money do you want to bet (your money: ${0})? '.format(money)))
    randn = get_randn()
    answer = randn % 5 + 1
    print('[1] [2] [3] [4] [5]')
    user_answer = int(input('pick one of the box > '))
    print('answer is [{0}]!'.format(answer))
    if user_answer == answer:
        money += bet
    else:
        money -= bet
robot_only.py 의 get_randn() 과 gamble() 소스. get_randn() 은 random.randint 한 줄이고, gamble() 은 그 값을 5로 나눈 나머지에 1을 더해 정답 상자를 정한 뒤 베팅액만큼 자금을 더하거나 뺀다.
robot_only.py 의 get_randn() 과 gamble() 소스. get_randn() 은 random.randint 한 줄이고, gamble() 은 그 값을 5로 나눈 나머지에 1을 더해 정답 상자를 정한 뒤 베팅액만큼 자금을 더하거나 뺀다.

박스 5개 중 하나를 맞히면 베팅한 만큼 벌고, 틀리면 잃는다. answer는 Python 표준 random 모듈에서 뽑은 값이다 — 여기서 자연스럽게 "이 난수를 미리 알 수 있으면 무조건 이긴다"는 생각이 든다. Python의 random은 암호학적으로 안전한 난수가 아니라 **Mersenne Twister(MT19937)**를 쓴다 — 알고리즘 자체가 공개되어 있고, 연속된 624개의 32비트 원시 출력만 확보하면 내부 상태를 완전히 복원해서 이후의 모든 출력을 정확히 예측할 수 있다는 게 잘 알려진 약점이다.

왜 하필 624개인가는 MT19937 내부 구조를 보면 바로 나온다. 이 알고리즘은 이름 그대로 "Mersenne Twister" — 내부 상태가 32비트 워드 624개로 이루어진 배열이고, 값을 하나 뽑을 때마다 그 배열에서 워드 하나씩을 꺼내 "템퍼링"이라는 가역 변환을 씌워 반환한다. 즉 getrandbits(32)를 한 번 호출하는 건 내부 배열의 다음 칸 하나를 열어 보여주는 것과 같다. 623개만 모으면 배열 624칸 중 딱 한 칸이 미지수로 남고, 그 한 칸을 채우지 못한 상태로는 다음 출력을 계산할 수 없다 — 624칸짜리 방정식 시스템에서 변수 하나가 비면 시스템 전체가 안 풀리는 것과 같은 이치다. 반대로 625개, 626개를 모아봐야 상태 복원에 필요한 정보는 이미 624개째에서 다 채워졌으므로 남는 값들은 그냥 검증용 여분일 뿐 새로 얻는 건 없다. 그래서 624는 "대충 넉넉히"가 아니라 정확히 필요충분한 개수다. 이 문제에서는 verify() 한 번이 6개씩 내주니 624 / 6 = 104, 오차 없이 딱 떨어지는 숫자다.

문제는 "624개를 어떻게 모으느냐"다. 답은 verify()에 있었다.

def verify():
    if verified is True:
        print('you have already been verified as a robot :]')
        return
 
    randn224 = (get_randn() | get_randn() << 32 | get_randn() << 64 |
                get_randn() << 96 | get_randn() << 128 | get_randn() << 160)
 
    challenge = randn224 ^ 0xdeaddeadbeefbeefcafecafe13371337DEFACED0DEFACED0
 
    signal.alarm(3)
    try:
        print('please type this same: "{0}"'.format(challenge))
        user_challenge = input('> ')
        if user_challenge == str(challenge):
            verified = True
            print('you\'re are now verified as a robot :]')
        else:
            print('you\'re not a robot ;[')
    except MyTimeoutError:
        print('\nyou failed to verify! robots aren\'t that slow ;[')
verify() 전체 소스 — get_randn() 6개를 이어붙여 고정 마스크로 XOR한 게 challenge
verify() 전체 소스 — get_randn() 6개를 이어붙여 고정 마스크로 XOR한 게 challenge

challenge는 get_randn()을 6번 호출해 32비트씩 이어붙인 값(randn224)을 고정된 상수로 XOR한 것뿐이다. 마스크 값을 알고 있으니, 화면에 출력된 challenge를 보는 즉시 randn224 = challenge ^ mask로 역산할 수 있고, 거기서 32비트씩 잘라내면 get_randn() 6번의 원본 출력값을 그대로 복원할 수 있다. 그리고 결정적으로 — 인증에 실패해도(오답이든 타임아웃이든) verified는 그대로 False로 남고, verify()를 다시 호출하는 데 아무 제약이 없다. 매 호출마다 새 난수 6개가 소모되니, verify()를 104번(6 × 104 = 624) 반복하면 MT19937 상태 복원에 필요한 624개 연속 출력을 정확히 모을 수 있다.



💣 핵심 — 624개의 원시값으로 내부 상태를 되감는다

Python의 random.getrandbits(32)가 반환하는 값은 MT19937 내부 상태 워드에 고정된 "템퍼링"(tempering) 연산 4단계를 적용한 결과다. 각 단계는 시프트와 XOR, 일부는 AND 마스크까지 곁들인 가역 연산이라, 순서를 거꾸로 밟으면 원래의 내부 상태 워드로 되돌릴 수 있다.

def undo_right_shift_xor(y, shift):
    x = y
    for _ in range(5):
        x = y ^ (x >> shift)
    return x & 0xFFFFFFFF
 
def undo_left_shift_xor_and(y, shift, mask):
    x = y
    for _ in range(5):
        x = y ^ ((x << shift) & mask)
        x &= 0xFFFFFFFF
    return x
 
def untemper(y):
    y = undo_right_shift_xor(y, 18)
    y = undo_left_shift_xor_and(y, 15, 0xEFC60000)
    y = undo_left_shift_xor_and(y, 7, 0x9D2C5680)
    y = undo_right_shift_xor(y, 11)
    return y
직접 짠 mt19937.py 소스. 고정점 반복 5회로 시프트-XOR 를 되감는 undo 함수 둘과, 우측시프트 18·좌측시프트 15·좌측시프트 7·우측시프트 11 을 역순으로 벗겨 내는 untemper() 가 보인다.
직접 짠 mt19937.py 소스. 고정점 반복 5회로 시프트-XOR 를 되감는 undo 함수 둘과, 우측시프트 18·좌측시프트 15·좌측시프트 7·우측시프트 11 을 역순으로 벗겨 내는 untemper() 가 보인다.

템퍼링의 네 단계 중 하나, z = w ^ (w >> 18)만 떼어서 보자(w는 이 단계로 들어오는 입력, z는 출력). 이걸 z만 갖고 거꾸로 풀려는 사람은 얼핏 막막해 보이지만, 사실 절반은 이미 풀려 있다 — 32비트 워드를 18비트만큼 우측 시프트하면 상위 18비트 자리는 시프트로 밀려 들어올 값이 없어 0으로 채워지고, w와 XOR해도 그 자리는 그대로 w가 남는다. 즉 z의 상위 18비트는 손대지 않은 w의 상위 18비트 그 자체다. 그 18비트를 알면 w >> 18의 상위 구간(=자신의 하위 14비트를 채울 재료)을 계산할 수 있고, 그걸로 w의 그다음 구간을 복원하고, 다시 그 구간으로 또 다음 구간을 복원하는 식으로 — 마치 도미노가 한 칸씩 넘어가듯 — 정답이 상위 비트에서 하위 비트로 전파되며 결국 w 전체가 확정된다. undo_right_shift_xor의 for _ in range(5) 루프는 이 도미노를 코드로 흉내낸 것이다: x = z ^ (x >> shift)를 초기값 x = z(아직 하위 비트가 틀린 추정치)로 시작해 반복하면, 한 번 돌 때마다 정확한 비트 구간이 shift만큼씩 늘어나다가 32비트 전부가 맞아떨어지는 **고정점(fixed point)**에서 더 이상 값이 바뀌지 않는다. 네 시프트값(18, 15, 7, 11) 중 가장 작은 게 7이니 ⌈32/7⌉ = 5번이면 어떤 시프트값에 대해서도 전체 32비트를 확실히 덮는다 — 그래서 untemper()의 모든 단계가 공통으로 5회 반복을 쓴다.

이 네 단계를 순서를 뒤집어(마지막에 적용된 우측시프트 18부터 시작해 좌측시프트 15, 좌측시프트 7, 우측시프트 11 순으로) 하나씩 벗겨내면, 템퍼링 전체가 정확히 역산되어 처음의 32비트 내부 상태 워드로 돌아온다. 이걸 실제 숫자로 눈으로 확인해봤다. random.Random(1337)이 뽑은 진짜 원시 출력 하나 y = 0x9e250d03을 untemper()로 4단계 전부 되감아 내부 상태 워드 x = 0x9b56044a를 얻고, 그 x를 다시 temper()에 넣었을 때 정확히 처음의 y로 돌아오는지 그 자리에서 검증했다(시드를 박아 뒀으니 몇 번을 돌려도 같은 값이 나온다).

$ python3 demo_untemper.py
raw tempered output y = 0x9e250d03
untempered state x    = 0x9b56044a
temper(x)             = 0x9e250d03
temper(untemper(y)) == y -> True
untemper/temper 왕복 검증 REPL 캡쳐 — 실제 raw 출력 y를 untemper로 되감아 내부 상태 x를 얻고, 다시 temper(x)가 정확히 원래 y로 돌아옴을 단일 값으로 확인
untemper/temper 왕복 검증 REPL 캡쳐 — 실제 raw 출력 y를 untemper로 되감아 내부 상태 x를 얻고, 다시 temper(x)가 정확히 원래 y로 돌아옴을 단일 값으로 확인

이 단일 워드 왕복이 성립하면, 624개의 원시 출력 전부에 똑같이 적용해 원래 내부 상태 워드 624개를 모두 되찾고, random.setstate((3, tuple(state_words) + (624,), None))로 서버와 완전히 동일한 상태를 가진 나만의 복제 RNG를 만들 수 있다. 같은 원리를 624개 전체·이후 출력 예측까지 확장해서 검증해보면 이 원리가 정확히 들어맞는다.

$ python3 mt19937.py
직접 만든 untemper/temper 함수와 상태 복제 로직의 자체 검증 — temper(untemper(x))==x, 624개로 복제한 RNG가 이후 20개 출력을 전부 정확히 예측함
직접 만든 untemper/temper 함수와 상태 복제 로직의 자체 검증 — temper(untemper(x))==x, 624개로 복제한 RNG가 이후 20개 출력을 전부 정확히 예측함
전체 공격 흐름 다이어그램 — challenge XOR 역산부터 104회 반복, 상태 복원, 도박 예측, 자금 증식까지
전체 공격 흐름 다이어그램 — challenge XOR 역산부터 104회 반복, 상태 복원, 도박 예측, 자금 증식까지

일단 복제 RNG가 서버와 완전히 동기화되면, gamble()을 호출하기 전에 우리 쪽 복제 RNG로 다음 get_randn() 결과를 미리 계산해 answer를 정확히 알아낼 수 있다. 매번 전 재산을 걸고(all-in) 베팅하면 판마다 자금이 정확히 2배가 된다 — $500 × 2²⁵ ≈ $167억이니, 25번만 연속으로 이기면 100억 달러 관문을 넘는다.


🎯 자체 완결 solve

104번의 verify() 호출로 624개를 모으고, 상태를 복제한 뒤, 25번의 gamble()을 전부 예측대로 진행하는 전체 흐름이다.

outputs = []
for i in range(104):
    p.sendlineafter(b'> ', b'2')
    line = p.recvline_contains(b'please type this same').decode()
    challenge = int(line.split('"')[1])
    randn224 = challenge ^ MASK
    words = [(randn224 >> (32 * j)) & 0xFFFFFFFF for j in range(6)]
    outputs.extend(words)
    # 마지막 호출만 정답으로 응답해 verified=True 확보, 나머지는 일부러 오답
    p.sendlineafter(b'> ', str(challenge if i == 103 else 0).encode())
 
clone = random.Random()
clone.setstate(clone_state_from_outputs(outputs))   # 624개로 상태 복제
 
money = 500
while money < 10_000_000_000:
    predicted = clone.randint(0, 0xfffffffe) % 5 + 1   # 서버가 뽑을 answer 를 미리 계산
    p.sendlineafter(b'> ', b'1')
    p.sendlineafter(b'? ', str(money).encode())         # 전 재산 베팅
    p.sendlineafter(b'> ', str(predicted).encode())
    money *= 2   # 예측이 맞으므로 항상 승리

로컬에서 먼저 전체 파이프라인을 검증했다.

로컬 실행 결과 — 624개 수집, 상태 복제, 25연속 all-in 승리로 $167억까지 증식 후 flag 획득
로컬 실행 결과 — 624개 수집, 상태 복제, 25연속 all-in 승리로 $167억까지 증식 후 flag 획득

같은 스크립트를 실제 원격 서버(host3.dreamhack.games:15706)에 그대로 실행했다.

solve.py 를 원격 인스턴스에 붙여 돌린 화면. 624개 수집과 RNG 상태 복제에 이어 25라운드 전부 예측대로 자금이 두 배씩 불어나고, 마지막 줄에 실제 플래그 문자열이 찍혔다.
solve.py 를 원격 인스턴스에 붙여 돌린 화면. 624개 수집과 RNG 상태 복제에 이어 25라운드 전부 예측대로 자금이 두 배씩 불어나고, 마지막 줄에 실제 플래그 문자열이 찍혔다.

25번의 베팅 전부 예측이 적중했다. 단 한 번도 틀리지 않았다는 사실 자체가 MT19937 상태 복원이 완벽하게 맞아떨어졌다는 증거다.

FLAG: DH{0086b1776b2b2dac7aebb790ec005ecf2bcce345c52225f03bb177b47a357a40}

flag()와 메뉴 루프는 간단하다 — 자금이 100억 달러를 넘으면 그대로 flag 파일을 열어 보여줄 뿐이다.

robot_only.py 뒷부분 소스. verify() 의 challenge 비교에 이어 def flag() 가 자금이 100억 달러에 못 미치면 그냥 return 하고, 넘으면 ./flag 파일을 열어 내용을 그대로 출력하는 부분이 보인다.
robot_only.py 뒷부분 소스. verify() 의 challenge 비교에 이어 def flag() 가 자금이 100억 달러에 못 미치면 그냥 return 하고, 넘으면 ./flag 파일을 열어 내용을 그대로 출력하는 부분이 보인다.

📝 결론

보안에 중요한 난수는 절대 random 모듈로 만들면 안 된다. 그것도 "코드를 잘못 짜서"가 아니라 모듈 자체가 설계상 그 용도로 쓰라고 만들어진 게 아니기 때문이다. Python 공식 문서는 random 모듈 맨 위에 "이 모듈의 함수들은 암호학적으로 안전하지 않다. 보안·암호화 목적에는 secrets 모듈을 쓰라"고 명시해 두었다. 이번 풀이가 보여준 건 그 경고가 이론상의 트집이 아니라 624개 값만 모으면 항상 100% 성공하는 구체적인 공격 절차가 존재한다는 사실이다 — MT19937은 내부 상태가 624워드짜리 유한 배열이고 템퍼링이 가역 연산이라는 게 알고리즘 명세 그 자체이므로, 파이썬 구현이 아무리 버그 없이 "올바르게" 짜여 있어도 이 성질은 절대 사라지지 않는다. 즉 패치로 고칠 수 있는 결함이 아니라 알고리즘의 정의에 내재된 구조적 한계다. 반대로 secrets.token_bytes()나 os.urandom()은 OS 커널의 CSPRNG(리눅스는 getrandom(2), /dev/urandom)를 직접 끌어다 쓰는데, 이건 출력 일부를 아무리 많이 관찰해도 다음 출력을 예측할 방법이 알려져 있지 않도록 설계된 것이 스펙의 일부다 — MT19937과 정반대로, "예측 불가능함"이 알고리즘이 지켜야 하는 계약이다. 인증 토큰, 세션 ID, 게임의 승부 결과처럼 예측되면 안 되는 값에는 반드시 이쪽을 써야 한다.

"실패해도 몇 번이든 재시도할 수 있는 절차"는 그 절차가 노출하는 정보를 무제한으로 긁어모을 수 있는 창구가 된다. verify()는 매 호출마다 6개의 새 난수를 소모하고 그 값을 (XOR로 가려놨을 뿐) 사실상 그대로 노출하는데, 실패해도 다시 시도하는 데 아무 제약이 없었다. 재시도 횟수 제한이나 속도 제한(rate limit)이 없는 절차는, 그 절차 자체가 아무리 사소해 보여도 정보 유출 관점에서는 "무제한 오라클"이 된다는 걸 잊으면 안 된다.

"XOR로 가려놨다"는 건 숨긴 게 아니라 그냥 인코딩일 뿐이다. 고정된 상수와의 XOR은 대칭 연산이라, 공개된 상수를 알고 있는 사람이라면 언제든 정확히 되돌릴 수 있다. 진짜 비밀(여기서는 6개의 원시 난수)을 외부에 노출하지 않으려면, 애초에 그 값 자체를 클라이언트에게 보여주지 않는 구조로 설계해야 한다.

이 글이 도움이 됐나요?

Comments

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개