# [CH] Where Is My Bit
###### tags: `Writeup` `Crypto` `Chinese`
> [name=Curious]
## 思路和解法
> 這篇 Writeup 會直接引用這兩個連結裡的符號
> - 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)
分析一下 `server.py` 可以發現我們需要去預測 `random.randrange(0x80000000, 0xFFFFFFFF)`，去翻一下 `random.randrange` 的程式碼，可以知道最後會呼叫到 `random.getrandbits(31)`，所以說這題主要目標是預測 `random.getrandbits(31)`
如果再去翻一下 `random.getrandbits` 的 [code](https://github.com/python/cpython/blob/ce558e69d4087dd3653207de78345fbb8a2c7835/Modules/_randommodule.c#L487) 的話，可以發現 `random.getrandits(31)` 會先用 MT19937 產生一個 32 bits 的偽隨機數，然後把最後一個 bit 拿掉。
首先因為我們拿到的 random number 只有最後一個 bit 不知道，而且最後一個 bit 不是 1 就是 0，所以可以先假設最後一個 bit 是 0。接下來要把 random number 丟給 `rand_to_state` 轉換成 state number。
`rand_to_state` 的第一步是 `tmp = un_bitshift_right_xor(rand_num, 18)`，因為 `rand_num = tmp ^ (tmp >> 18)`
```
10110111010111100111111001110010 tmp
10110111010111 tmp >>> 18
10110111010111100101001110100101 tmp ^ (tmp >>> 18) = rand_num
```
當進行 `un_bitshift_right_xor` 時，因為`tmp` 和 `rand_num` 的前 18 bits 是相同的，所以 `tmp` 的前 18 bits 是直接從 `rand_num` 那邊拿取，然後用 `tmp` 前 18 bits 再去推 `tmp` 的後 16 bits。因為 `rand_num` 只有最後一個 bit 不確定，所以 `tmp` 也是只有最後一個 bit 不確定。
接下來是進行 `pre_tmp = un_bitshift_left_xor_mask(tmp, 15, 0xefc60000)`，因為 `tmp = pre_tmp ^ ((pre_tmp << 15) & 0xefc60000)`
```
# 這裡的 `tmp` 跟上面沒有關係，我隨便打的
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
```
進行 `pre_tmp = un_bitshift_left_xor_mask(tmp, 15, 0xefc60000)` 時，因為 0xefc60000 的最後 15 bits 都是 0，所以 `pre_tmp` 和 `tmp` 的最後 15 bits 是一樣的。透過 `pre_tmp` 的最後 15 bits 可以推論出最後 30 - 16 bits，然後再推出全部。因為 `tmp` 的最後 1 bit 是不確定的，所以說 `pre_tmp` 的最後 1 bit 也不確定，接著因為用 `pre_tmp` 最後 15 bits 來推最後 30 - 16 bits，但是 0xefc60000 在第倒數 16 bit 是 0，所以 `pre_tmp` 最後 1 bit 不確定對於 `pre_tmp` 的倒數 30 - 16 bits 並沒有影響，所以說倒數 30 - 16 bit 沒有不確定的 bit，接著 `pre_tmp` 的倒數 32 - 31 bits 也沒有不確定的 bit。
到這邊為止 `pre_tmp` 只有第 31 個 bit 不確定（正著數從 0 開始，倒著數從 1 開始），如果用以上方法推論到 `state_number`，那 `state_number` 的第 3, 10, 14, 17, 21, 24, 25, 28, 31 個 bit 都是不確定的，而且這邊因為 xor 運算的特性，全部不確定的 bits 要不就一起錯，要不就會一起對。
接著可以看一下 `gen_next_state` 這個函數，我們這邊用 `state[0]` `state[1]` `state[397]` 和下一個 `state[0]` 來思考
```python=
y = (state0 & 0x80000000) + (state1 & 0x7fffffff)
next = y >> 1
next ^= state397
if ((y & 1) == 1):
next ^= 0x9908b0df
next_state0 = next
```
從 code 中可以發現 `y` 其實是取 `state0` 的第 0 個 bit 和 `state1` 的第 1 - 31 個 bit，接著因為 `next` 是 `y >> 1` 的關係，所以不確定的 bit 就被右移了 1 bit，如果可以找到一個不確定的 bit，在 `y` 右移之後對應到的 `state397` 和 `next_state0` 的 bit 都是確定的，而且 0x9908b0df 對應的 bit 是 0，就可以解方程式知道那個不確定的 bit 對不對，然後根據前面的推論，如果不對，那 `rand_num` 的最後一個 bit 就是 1。
我找到的那個不確定的 bit 是第 10 個 bit，`state1` 第 10 個 bit 右移之後到 `next` 的第 11 個 bit，且 `state397` 和 `next_state0` 的第 11 個 bit 都是確定的，且 0x9908b0df 的第 11 個 bit 是 0，所以比較用 `state0` 和 `state1` 算出來 `next_state0` 的第 11 bit 和 `next_state0` 本身的第 11 bit，如果不同的話那 `state1` 就要用 `rand_num` 且最後一個 bit 是 1 來重推一次。
由以上方法就可以把整個 `state` 推完，當知道整個 `state` 後，就可以預測以後的 `rand_num` 了。
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