# [EN] Where Is My Bit
###### tags: `Writeup` `Crypto` `English`
> [name=Curious]
## Train Of Thought & Solution
> This Writeup will directly reference the symbols in these two links
> - How To Crack MT19937 : [Link](https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html)
> - Python Impletement : [Link](https://github.com/Curious-Lucifer/CTFLib/blob/master/Crypto/PRNG.py#L21)
Upon analyzing `server.py`, we can find that we need to predict `random.randrange(0x80000000, 0xFFFFFFFF)`. By examining the code for `random.randrange`, we can determine that it eventually calls `random.getrandbits(31)`. Therefore, the main objective of this problem is to predict `random.getrandbits(31)`.
If we further examine the [code](https://github.com/python/cpython/blob/ce558e69d4087dd3653207de78345fbb8a2c7835/Modules/_randommodule.c#L487) for `random.getrandbits`, we can observe that `random.getrandbits(31)` first generates a 32 bit pseudo-random number using MT19937, and then removes the last bit.
Firstly, since we only lack knowledge about the last bit of the random number, and the last bit can either be 1 or 0, we can make an initial assumption that the last bit is 0. Next, we need to convert the random number into a state number using the `rand_to_state` transformation.
The first step of `rand_to_state` is `tmp = un_bitshift_right_xor(rand_num, 18)`, where `rand_num = tmp ^ (tmp >> 18)`.
```
10110111010111100111111001110010 tmp
10110111010111 tmp >>> 18
10110111010111100101001110100101 tmp ^ (tmp >>> 18) = rand_num
```
During the `un_bitshift_right_xor` operation, since the first 18 bits of `tmp` and `rand_num` are the same, the first 18 bits of `tmp` are directly taken from `rand_num`. Then, these first 18 bits of `tmp` are used to infer the remaining 16 bits of `tmp`. As `rand_num` has only the last bit uncertain, `tmp` will also have only the last bit uncertain.
Next, we proceed with `pre_tmp = un_bitshift_left_xor_mask(tmp, 15, 0xefc60000)`, where `tmp = pre_tmp ^ ((pre_tmp << 15) & 0xefc60000)`
```
# The `tmp` here is unrelated to the previous part, I just typed it randomly
00111111001110011000000000000000 pre_tmp << 15
11101111110001100000000000000000 0xefc60000
11111111111111111000000000000000 (pre_tmp << 15) & 0xefc60000
10110111010111100111111001110011 pre_tmp
11111111111111111000000000000000 (pre_tmp << 15) & 0xefc60000
01001000101000011111111001110011 pre_tmp ^ ((pre_tmp << 15) & 0xefc60000) = tmp
10011101001011000101011010000000
```
During the step of `pre_tmp = un_bitshift_left_xor_mask(tmp, 15, 0xefc60000)`, since the last 15 bits of 0xefc60000 are all 0, the last 15 bits of `pre_tmp` will be the same as `tmp`. By using the last 15 bits of `pre_tmp`, we can infer the remaining bits from 30 to 16. As the last bit of `tmp` is uncertain, the last bit of `pre_tmp` is also uncertain. Next, since we use the last 15 bits of `pre_tmp` to infer the bits from 30 to 16, but 0xefc60000 has 0 in the 16th bit from the end, the uncertainty in the last bit of `pre_tmp` does not affect the bits from 30 to 16 in `pre_tmp`. Therefore, there are no uncertain bits in the bits from 30 to 16 of `pre_tmp`. Furthermore, there are also no uncertain bits in the 32nd and 31st bits from the end of `pre_tmp`.
Up to this point, only the 31st bit (counting from 0) of `pre_tmp` is uncertain. If we continue the inference process using the mentioned method to obtain `state_number`, then the 3rd, 10th, 14th, 17th, 21st, 24th, 25th, 28th, and 31st bits of `state_number` will also be uncertain. Additionally, due to the properties of xor operations, all the uncertain bits will either be incorrect together or correct together.
let's take a look at the `gen_next_state` function. In this case, we are considering the usage of `state[0]`, `state[1]`, `state[397]`, and the next `state[0]` for our analysis
```python=
y = (state0 & 0x80000000) + (state1 & 0x7fffffff)
next = y >> 1
next ^= state397
if ((y & 1) == 1):
next ^= 0x9908b0df
next_state0 = next
```
From the code, we can observe that `y` is obtained by taking the 0th bit of `state0` and the 1st - 31st bits of `state1`. Since `next` is related to `y >> 1`, the uncertain bits are shifted right by 1 bit. If we can find an uncertain bit that, after the right shift in `y`, corresponds to a certain bit in `state397` and `next_state0`, and the corresponding bit of 0x9908b0df is 0, we can solve the equation to determine if that uncertain bit is correct. Based on the previous reasoning, if it is incorrect, the last bit of `rand_num` will be 1.
If the uncertain bit you found is the 10th bit, then after the right shift, the 10th bit of `state1` corresponds to the 11th bit of `next`, and both the 11th bit of `state397` and the 11th bit of `next_state0` are certain. Furthermore, the 11th bit of 0x9908b0df is 0, so we can compare the 11th bit calculated from `state0` and `state1` with the 11th bit of `next_state0`. If they are different, it implies that `state1` should be recalculated using `rand_num` with the last bit being 1
With the above method, it is possible to infer the entire `state`. Once the entire `state` is known, it becomes possible to predict future `rand_num` values.
Solve Script :
```python=
def un_bitshift_right_xor(value: int, shift: int):
"""
- input : `value (int)`, `shift (int)`
- output : `result (int)` , `value = (result >> shift) ^ result`
"""
i = 0
result = 0
while ((i * shift) < 32):
partmask = int('1' * shift + '0' * (32 - shift), base = 2) >> (shift * i)
part = value & partmask
value ^= (part >> shift)
result |= part
i += 1
return result
def un_bitshift_left_xor_mask(value: int, shift: int, mask: int):
"""
- input : `value (int)`, `shift (int)`, `mask (int)`
- output : `result (int)` , `value = ((result << shift) & mask) ^ result`
"""
i = 0
result = 0
while ((i * shift) < 32):
partmask = int('0' * (32 - shift) + '1' * shift, base = 2) << (shift * i)
part = value & partmask
value ^= (part << shift) & mask
result |= part
i += 1
return result
def rand_to_state(value: int):
"""
- input : `value (int)`
- output : `value (int)` , for MT19937
"""
value = un_bitshift_right_xor(value, 18)
value = un_bitshift_left_xor_mask(value, 15, 0xefc60000)
value = un_bitshift_left_xor_mask(value, 7, 0x9d2c5680)
value = un_bitshift_right_xor(value, 11)
return value
def state_to_rand(value: int):
"""
- input : `value (int)`
- output : `value (int)` , for MT19937
"""
value ^= (value >> 11)
value ^= (value << 7) & 0x9d2c5680
value ^= (value << 15) & 0xefc60000
value ^= (value >> 18)
return value
def gen_next_state(state: list[int]):
"""
- input : `state (list[int])` , `state` will be changed to next state
- output : None
"""
assert len(state) == 624
for i in range(624):
y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff)
next = y >> 1
next ^= state[(i + 397) % 624]
if ((y & 1) == 1):
next ^= 0x9908b0df
state[i] = next
# =================================
from pwn import *
from tqdm import trange
r = remote('lotuxctf.com', 30003)
r.recvline()
def get_random():
r.sendlineafter(b'> ', b'-1')
return int(r.recvline().strip().split(b'is ')[1].decode()) - 0x80000000
randlist = [get_random() for _ in trange(624 * 2)]
state = [rand_to_state(randlist[0] << 1)]
for i in range(624):
s_test = rand_to_state(randlist[i + 1] << 1)
s_xor = rand_to_state(randlist[i + 397] << 1)
s_new = rand_to_state(randlist[i + 624] << 1)
if (bin((s_test >> 1) ^ s_xor)[2:].rjust(32, '0')[11] != bin(s_new)[2:].rjust(32, '0')[11]):
state.append(rand_to_state((randlist[i + 1] << 1) | 1))
else:
state.append(s_test)
state, next_state0 = state[:-1] ,state[-1]
gen_next_state(state)
state[0] = next_state0
gen_next_state(state)
for i in range(100):
r.sendlineafter(b'> ', str((state_to_rand(state[i]) >> 1) + 0x80000000).encode())
r.recvline()
r.interactive()
```
{%hackmd M1bgOPoiQbmM0JRHWaYA1g %}
Sign in with Wallet
Connect another wallet