I am trying to solve a CTF challenge in which the goal is to guess the generated number. Since the number is huge and you only have 10 attempts per number, I don't think you can apply binary search or any kind of algorithm to solve it, and that it has something to do with somehow getting the seed of the random function and being able to generate the next number, but I have no idea on where to start to get the correct seed. Do you have any idea? Here's the code of the challenge:
#!/usr/bin/env python3
import signal
import os
import random
TIMEOUT = 300
assert("FLAG" in os.environ)
FLAG = os.environ["FLAG"]
assert(FLAG.startswith("CCIT{"))
assert(FLAG.endswith("}"))
def handle():
for i in range(625):
print(f"Round {i+1}")
guess_count = 10
to_guess = random.getrandbits(32)
while True:
print("What do you want to do?")
print("1. Guess my number")
print("2. Give up on this round")
print("0. Exit")
choice = int(input("> "))
if choice == 0:
exit()
elif choice == 1:
guess = int(input("> "))
if guess == to_guess:
print(FLAG)
exit()
elif guess < to_guess:
print("My number is higher!")
guess_count -= 1
else:
print("My number is lower!")
guess_count -= 1
elif choice == 2:
print(f"You lost! My number was {to_guess}")
break
if guess_count == 0:
print(f"You lost! My number was {to_guess}")
break
if __name__ == "__main__":
signal.alarm(TIMEOUT)
handle()
Don't try guessing the first 624 numbers, just give up on them. You're told what they were, feed them into randcrack as shown in its example. Ask it to predict the next 32-bit number and guess that.
For a bigger challenge, you could try it without that tool. Here's some insight, "predicting" the next number, i.e., showing how it's computed from the state:
import random
for _ in range(5):
s = random.getstate()[1]
y = s[s[-1]]
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680;
y ^= (y << 15) & 0xefc60000;
y ^= (y >> 18);
print('predict:', y)
print('actual: ', random.getrandbits(32))
print()
Sample output:
predict: 150999088
actual: 3825261045
predict: 457032747
actual: 457032747
predict: 667801614
actual: 667801614
predict: 3817694986
actual: 3817694986
predict: 816636218
actual: 816636218
First I get the state, which is 624 words of 32 bits and an index. The calculation of y is from here. The first number is wrong because in reality, the first time the more complicated code above it runs.
If you can figure out how to inverse those calculations, you could reconstruct the original state from the given first 624 numbers, then set that state with random.setstate, and generate the next number. The tool does seem to do that inversal, but it doesn't look trivial.