OverTheWire Advent Bonanza 2021 Writeup

Grinch's Game (misc)

サーバの処理概要は以下の通り。

・r = random.Random(secrets.randbits(20))
・my_number: 100未満のランダム整数
・numbers_to_guess = 100
・lives_remaining = 20
・以下繰り返し
　・answer: 整数入力
　・answerとmy_numberが一致している場合
　　・numbers_to_guess: 1減算
　　・my_number: 100未満のランダム整数
　・answerがmy_numberより小さい場合
　　・"Too low..."と表示
　　・lives_remaining: 1減算
　・answerがmy_numberより大きい場合
　　・"Too high..."と表示
　　・lives_remaining: 1減算
　・lives_remainingが0の場合、終了
　・numbers_to_guessが0の場合、フラグを表示

secrets.randbits(20)の部分(=secretとする)が20bitランダム整数で、これをブルートフォースして求める。このとき、secretを特定するのに必要なランダム整数の数は4つ。失敗回数が20のため、失敗する可能性があるが、成功するまで実行して4つの整数が入手できたら、次以降の整数を割り出すことができる。

#!/usr/bin/env python3
import socket
import random

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('grinchgame.advent2021.overthewire.org', 1217))

data = recvuntil(s, b'...\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

nums = []
for _ in range(4):
    g = [0, 99]
    while True:
        data = recvuntil(s, b'\n').rstrip()
        print(data)
        ans = (g[0] + g[1]) // 2
        print(ans)
        s.sendall(str(ans).encode() + b'\n')
        data = recvuntil(s, b'\n').rstrip()
        print(data)
        if data == 'Correct!':
            nums.append(ans)
            break
        elif data == 'Too low...':
            g[0] = ans
        else:
            g[1] = ans

for secret in range(2**20):
    r = random.Random(secret)
    found = True
    for i in range(4):
        my_number = r.randrange(100)
        if my_number != nums[i]:
            found = False
            break
    if found:
        break

for _ in range(96):
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    ans = r.randrange(100)
    print(ans)
    s.sendall(str(ans).encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)

data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

成功したときの実行結果は以下の通り。

SYSTEM INFO:
CPython 3.10.1 (main, Dec  8 2021, 03:30:49) [GCC 10.2.1 20210110] on linux

Are you feeling lucky? Let's play a game...

[round 1/100] Guess my number:
49
Too low...
[round 1/100] Guess my number:
74
Too high...
[round 1/100] Guess my number:
61
Too high...
[round 1/100] Guess my number:
55
Correct!
[round 2/100] Guess my number:
49
Too low...
[round 2/100] Guess my number:
74
Too high...
[round 2/100] Guess my number:
61
Too low...
[round 2/100] Guess my number:
67
Too high...
[round 2/100] Guess my number:
64
Too low...
[round 2/100] Guess my number:
65
Correct!
[round 3/100] Guess my number:
49
Too low...
[round 3/100] Guess my number:
74
Too high...
[round 3/100] Guess my number:
61
Too low...
[round 3/100] Guess my number:
67
Too high...
[round 3/100] Guess my number:
64
Too high...
[round 3/100] Guess my number:
62
Correct!
[round 4/100] Guess my number:
49
Too low...
[round 4/100] Guess my number:
74
Too high...
[round 4/100] Guess my number:
61
Too high...
[round 4/100] Guess my number:
55
Too high...
[round 4/100] Guess my number:
52
Too low...
[round 4/100] Guess my number:
53
Too low...
[round 4/100] Guess my number:
54
Correct!
[round 5/100] Guess my number:
68
Correct!
[round 6/100] Guess my number:
20
Correct!
[round 7/100] Guess my number:
42
Correct!
[round 8/100] Guess my number:
28
Correct!
[round 9/100] Guess my number:
85
Correct!
[round 10/100] Guess my number:
58
Correct!
　　　　　　　　：
　　　　　　　　：
[round 91/100] Guess my number:
71
Correct!
[round 92/100] Guess my number:
95
Correct!
[round 93/100] Guess my number:
74
Correct!
[round 94/100] Guess my number:
73
Correct!
[round 95/100] Guess my number:
71
Correct!
[round 96/100] Guess my number:
94
Correct!
[round 97/100] Guess my number:
33
Correct!
[round 98/100] Guess my number:
60
Correct!
[round 99/100] Guess my number:
18
Correct!
[round 100/100] Guess my number:
41
Correct!
YOU WIN! How are you so lucky!?!??
AOTW{wh3n_th3_0nly_w1nn1n6_m0ve_15_n0t_2_p14y}

AOTW{wh3n_th3_0nly_w1nn1n6_m0ve_15_n0t_2_p14y}