# Crack coding language’s default random
https://github.com/DPhuoc/Crack-coding-language-s-default-random
## python random
### Mersenne Twister Algorithm
Đầu tiên ta cần nhìn qua hàm `genrand_uint32` dưới đây:
```c++
/* Period parameters -- These are all magic. Don't change. */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfU /* constant vector a */
#define UPPER_MASK 0x80000000U /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffU /* least significant r bits */
static uint32_t genrand_uint32(RandomObject *self)
{
uint32_t y;
static const uint32_t mag01[2] = {0x0U, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */
uint32_t *mt;
mt = self->state;
if (self->index >= N) { /* generate N words at one time */
int kk;
for (kk=0;kk<N-M;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
}
for (;kk<N-1;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
}
y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
self->index = 0;
}
y = mt[self->index++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680U;
y ^= (y << 15) & 0xefc60000U;
y ^= (y >> 18);
return y;
}
```
Khi chú ý vào đoạn code sau:
```c++
y = mt[self->index++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680U;
y ^= (y << 15) & 0xefc60000U;
y ^= (y >> 18);
```
Ta nhận ra rằng đây là một đoạn có thể được reverse lại và khi có đầy đủ 624 states 32 bits thì ta có thể tạo lại được nguyên mảng `mt` và predict được random
```python
def unshiftRight(x, shift):
res = x
for i in range(32):
res = x ^ res >> shift
return res
def unshiftLeft(x, shift, mask):
res = x
for i in range(32):
res = x ^ (res << shift & mask)
return res
def untemper(v):
v = unshiftRight(v, 18)
v = unshiftLeft(v, 15, 0xefc60000)
v = unshiftLeft(v, 7, 0x9d2c5680)
v = unshiftRight(v, 11)
return v
import random
outputs = [ random.getrandbits(32) for _ in range(1000) ]
recovered_state = (3, tuple([ untemper(v) for v in outputs[:624] ] + [0]), None)
random.setstate(recovered_state)
for i in range(1000):
assert outputs[i] == random.getrandbits(32)
```
### Recovering from partial outputs
Tuy nhiên trong một số trường hợp ta lại không có đủ 32 bit của 1 state, vậy thì nên xử lí như thế nào?
Ta thấy hàm `getrandbits` được implement như sau:
```c++
static PyObject * _random_Random_getrandbits_impl(RandomObject *self, int k)
/*[clinic end generated code: output=b402f82a2158887f input=8c0e6396dd176fc0]*/
{
int i, words;
uint32_t r;
uint32_t *wordarray;
PyObject *result;
if (k < 0) {
PyErr_SetString(PyExc_ValueError,
"number of bits must be non-negative");
return NULL;
}
if (k == 0)
return PyLong_FromLong(0);
if (k <= 32) /* Fast path */
return PyLong_FromUnsignedLong(genrand_uint32(self) >> (32 - k));
words = (k - 1) / 32 + 1;
wordarray = (uint32_t *)PyMem_Malloc(words * 4);
if (wordarray == NULL) {
PyErr_NoMemory();
return NULL;
}
/* Fill-out bits of long integer, by 32-bit words, from least significant
to most significant. */
#if PY_LITTLE_ENDIAN
for (i = 0; i < words; i++, k -= 32)
#else
for (i = words - 1; i >= 0; i--, k -= 32)
#endif
{
r = genrand_uint32(self);
if (k < 32)
r >>= (32 - k); /* Drop least significant bits */
wordarray[i] = r;
}
result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,
PY_LITTLE_ENDIAN, 0 /* unsigned */);
PyMem_Free(wordarray);
return result;
}
```
Khi ta lấy `getrandbits(k)` $(k < 32)$ thì kết quả ta nhận được sẽ là `genrand_uint32() >> (32 - k)` hay nói cách khác là ta có được $k$ bit đầu.
Nhìn lại đoạn code của hàm `genrand_uint32()` ta có thể rút gọn lại như sau:
```python
N = 624
M = 397
MATRIX_A = 0x9908b0df; mag01 = [0, MATRIX_A]
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff
if index >= N:
for kk in range(N):
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
mt[kk] = mt[(kk + M) % N] ^ (y >> 1) ^ mag01[y & 1];
index = 0
y = mt[index];
y ^= (y >> 11)
y ^= (y << 7) & 0x9d2c5680
y ^= (y << 15) & 0xefc60000
y ^= (y >> 18)
index += 1
```
Ta thấy toàn bộ các biểu thức tính toán đều được sử dụng phép `and`, `xor` và `shift` nên ta có thể biểu diễn output của y dưới dạng các biến trong GF(2).
Điều này có nghĩa là, khi ta thu thập đủ phương trình ta có thể giải được state ban đầu mà không cần đầy đủ bit của hàm `genrand_uint32()`. Tuy nhiên trong quá trình biến đổi của Mersenne Twister có vài bit nếu chúng ta không có được sẽ không thể tạo ra đủ phương trình để giải.
Sau đây là cách implement của `rbtree`:
https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/
`class Twister` được sử dụng để gen bit mask:
```python
class Twister:
N = 624
M = 397
A = 0x9908b0df
def __init__(self):
self.state = [ [ (1 << (32 * i + (31 - j))) for j in range(32) ] for i in range(624)]
self.index = 0
@staticmethod
def _xor(a, b):
return [x ^ y for x, y in zip(a, b)]
@staticmethod
def _and(a, x):
return [ v if (x >> (31 - i)) & 1 else 0 for i, v in enumerate(a) ]
@staticmethod
def _shiftr(a, x):
return [0] * x + a[:-x]
@staticmethod
def _shiftl(a, x):
return a[x:] + [0] * x
def get32bits(self):
if self.index >= self.N:
for kk in range(self.N):
y = self.state[kk][:1] + self.state[(kk + 1) % self.N][1:]
z = [ y[-1] if (self.A >> (31 - i)) & 1 else 0 for i in range(32) ]
self.state[kk] = self._xor(self.state[(kk + self.M) % self.N], self._shiftr(y, 1))
self.state[kk] = self._xor(self.state[kk], z)
self.index = 0
y = self.state[self.index]
y = self._xor(y, self._shiftr(y, 11))
y = self._xor(y, self._and(self._shiftl(y, 7), 0x9d2c5680))
y = self._xor(y, self._and(self._shiftl(y, 15), 0xefc60000))
y = self._xor(y, self._shiftr(y, 18))
self.index += 1
return y
def getrandbits(self, bit):
return self.get32bits()[:bit]
```
`class Solver` dùng để khử gauss mỗi khi 1 equation mới được thêm vào và tìm ra `state`
```python
class Solver:
def __init__(self):
self.equations = []
self.outputs = []
def insert(self, equation, output):
for eq, o in zip(self.equations, self.outputs):
lsb = eq & -eq
if equation & lsb:
equation ^= eq
output ^= o
if equation == 0:
return
lsb = equation & -equation
for i in range(len(self.equations)):
if self.equations[i] & lsb:
self.equations[i] ^= equation
self.outputs[i] ^= output
self.equations.append(equation)
self.outputs.append(output)
def solve(self):
num = 0
for i, eq in enumerate(self.equations):
if self.outputs[i]:
# Assume every free variable is 0
num |= eq & -eq
state = [ (num >> (32 * i)) & 0xFFFFFFFF for i in range(624) ]
return state
```
Ngoài ra còn có thể sử dụng `z3` hoặc là `gf2bv` để giải phương trình trong GF(2)
```python!
import random
from gf2bv import LinearSystem, BitVec
class MersenneTwister:
def __init__(self, mt, w, n, m, r, a, u, d, s, b, t, c, l):
w1 = (1 << w) - 1
if len(mt) != n or min(r, u, s, t, l) > w and max(a, b, c, d) > w1:
raise ValueError("invalid parameters")
self.mt = list(mt)
self.w = w
self.n = n
self.m = m
self.r = r
self.a = a
self.u = u
self.d = d
self.s = s
self.b = b
self.t = t
self.c = c
self.l = l
self.w1 = w1
self.lmsk = w1 & ((1 << r) - 1)
self.umsk = w1 ^ self.lmsk
self.mti = 624
def twist(self):
for i in range(self.n):
y = (self.mt[i] & self.umsk) ^ (self.mt[(i + 1) % self.n] & self.lmsk)
sel = (
y.broadcast(0, 32) & self.a
if isinstance(y, BitVec)
else (y & 1) * self.a
)
self.mt[i] = self.mt[(i + self.m) % self.n] ^ (y >> 1) ^ sel
def temper(self, y):
y ^= (y >> self.u) & self.d
y ^= (y << self.s) & self.w1 & self.b
y ^= (y << self.t) & self.w1 & self.c
y ^= y >> self.l
return y
def __call__(self):
if self.mti >= self.n:
self.twist()
self.mti = 0
y = self.mt[self.mti]
self.mti += 1
return self.temper(y)
def _getrandbits_word(self, k):
r = self()
if isinstance(r, BitVec):
return r[self.w - k :]
return r >> (self.w - k)
def getrandbits(self, k=None):
"""Uses the CPython's implementation of random.getrandbits()"""
if k is None:
k = self.w
if k < 0:
raise ValueError("number of bits cannot be negative")
if k <= self.w:
return self._getrandbits_word(k)
words = (k - 1) // self.w + 1
x = 0
for i in range(words):
r = self._getrandbits_word(min(k, self.w))
if isinstance(r, BitVec):
x |= r.lshift_ext(self.w * i)
else:
x |= r << (self.w * i)
k -= self.w
return x
bs = 30
samples = 1500
rand = random.Random(1503)
st = tuple(rand.getstate()[1][:-1])
effective_bs = ((bs - 1) & bs) or bs
out = [rand.getrandbits(bs) for _ in range(samples)]
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MersenneTwister(mt, 32, 624, 397, 31, 0x9908B0DF, 11, 0xFFFFFFFF, 7, 0x9D2C5680, 15, 0xEFC60000, 18)
zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
print("solving...")
sol = lin.solve_one(zeros)
assert sol == st
```
## js `Math.random()`
Đầu tiên ta nhìn vào các hàm sau:
```javascript!
static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
uint64_t s1 = *state0;
uint64_t s0 = *state1;
*state0 = s0;
s1 ^= s1 << 23;
s1 ^= s1 >> 17;
s1 ^= s0;
s1 ^= s0 >> 26;
*state1 = s1;
}
static inline double ToDouble(uint64_t state0) {
// Exponent for double values for [0.0 .. 1.0)
static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
uint64_t random = (state0 >> 12) | kExponentBits;
return base::bit_cast<double>(random) - 1;
}
Address MathRandom::RefillCache(Isolate* isolate, Address raw_native_context) {
Tagged<FixedDoubleArray> cache =
Cast<FixedDoubleArray>(native_context->math_random_cache());
// Create random numbers.
for (int i = 0; i < kCacheSize; i++) {
// Generate random numbers using xorshift128+.
base::RandomNumberGenerator::XorShift128(&state.s0, &state.s1);
cache->set(i, base::RandomNumberGenerator::ToDouble(state.s0));
}
pod->set(0, state);
Tagged<Smi> new_index = Smi::FromInt(kCacheSize);
native_context->set_math_random_index(new_index);
return new_index.ptr();
}
```
Khi gọi hàm `Random` chương trình sẽ tạo một mảng `cache` lưu lại `ToDouble(state.s0)` và từ đó lấy ra giá trị theo thứ tự cuối đến đầu mảng mỗi khi người dùng gọi hàm.
Ngoài ra với mỗi `state` có được ta sẽ bị mất 12 LSB do quá trình chuyển sang `double`.
Tương tự như `python random`, `xorshift128` cũng được thực hiện chỉ bằng phép `xor`, `shift` nên cũng có thể biểu diễn output trong GF(2)
## c\c++ `rand()`
```c
#include <stdio.h>
#define MAX 1000
#define seed 1
main() {
int r[MAX];
int i;
r[0] = seed;
for (i = 1; i < 31; i++) {
r[i] = (16807LL * r[i - 1]) % 2147483647;
if (r[i] < 0) {
r[i] += 2147483647;
}
}
for (i = 31; i < 34; i++) {
r[i] = r[i - 31];
}
for (i = 34; i < 344; i++) {
r[i] = r[i - 31] + r[i - 3];
}
for (i = 344; i < MAX; i++) {
r[i] = r[i - 31] + r[i - 3];
printf("%d\n", ((unsigned int)r[i]) >> 1);
}
}
```
Thật sự thì `seed` có thể được bruteforce do chỉ có 32 bits. Nhưng vẫn còn cách khác.
Đầu tiên ta sẽ `recover` lại `r[344]` --> `r[MAX]`. Tuy ta chỉ có `r[i] >> 1` nhưng ra biết rằng `r[i] = r[i - 31] + r[i - 3]` nên nếu `(r[i] >> 1) != (r[i - 31] >> 1) + (r[i - 3] >> 1)` thì có nghĩa là bit cuối của `r[i - 31]` và `r[i - 3]` = 1 và bit cuối của `r[i]` = 0
```python!
def crack(outputs):
states = []
for i in range(len(outputs)):
if (i >= 31 and
outputs[i] != None and
outputs[i - 31] != None and
outputs[i - 3] != None and
outputs[i] != (outputs[i - 31] + outputs[i - 3]) & 0x7fffffff
):
states[i - 31] = (outputs[i - 31] << 1) + 1
states[i - 3] = (outputs[i - 3] << 1) + 1
states.append((outputs[i] << 1) + 0)
else:
states.append(None)
return states
```
Với `r[i] = r[i - 31] + r[i - 3]` ta có thể duyệt lại mảng lần nữa để kiểm tra xem còn điền thêm được `r` nào không
```python!
def self_recover(states):
MOD = 2 ** 32
length = len(states)
while True:
updated = False
for i in range(34, length):
s_i = states[i]
s_31 = states[i - 31]
s_3 = states[i - 3]
if s_i is not None and s_3 is not None and s_31 is None:
states[i - 31] = (s_i - s_3) % MOD
updated = True
elif s_i is not None and s_31 is not None and s_3 is None:
states[i - 3] = (s_i - s_31) % MOD
updated = True
elif s_i is None and s_3 is not None and s_31 is not None:
states[i] = (s_3 + s_31) % MOD
updated = True
if not updated:
break
```
Sau đó ta chỉ cần lần lượt recover lại các state cũ (sẽ có thể có vài state là `None`)
```python!
def recover_seed(outputs):
states = crack(outputs)
init = [None] * 344
for i in range(343, 2, -1):
s31 = states[i + 31 - 344] if i + 31 >= 344 else init[i + 31]
s28 = states[i + 28 - 344] if i + 28 >= 344 else init[i + 28]
if s31 is not None and s28 is not None:
init[i] = (s31 - s28) % 2**32
for i in range(3):
init[i] = init[i + 31]
base_idx = next((i for i in range(31) if init[i] is not None), None)
if base_idx is not None:
for i in range(31):
if init[i] is None:
init[i] = (
pow(16807, i - base_idx, 2147483647) *
init[base_idx] % 2147483647
)
all_states = init + states
self_recover(all_states)
print(all_states[:20])
assert all(s is None or s < 2147483647 for s in all_states[1:31]), "Invalid states"
return all_states[0] if all_states[0] is not None else None
```
Đến đây có thể xài Z3 để tìm lại seed ban đầu
## golang `math/rand`
Để ý hàm seed của `rng.go`
```go!
func (rng *rngSource) Seed(seed int64) {
rng.tap = 0
rng.feed = rngLen - rngTap
seed = seed % int32max
if seed < 0 {
seed += int32max
}
if seed == 0 {
seed = 89482311
}
x := int32(seed)
for i := -20; i < rngLen; i++ {
x = seedrand(x)
if i >= 0 {
var u int64
u = int64(x) << 40
x = seedrand(x)
u ^= int64(x) << 20
x = seedrand(x)
u ^= int64(x)
u ^= rngCooked[i]
rng.vec[i] = u
}
}
}
```
Ta thấy seed chỉ là **int32** nên có thể bruteforce dễ dàng.
Ngoài ra sau đây là cách implement sử dụng z3 mà không cần bruteforce seed.
```python!
from rand import new_source, new
from rng import RngSource, RNG_LEN
from tqdm import trange
from z3 import *
s = Solver()
NUM_TEST = 700
vec = [BitVec(f'vec_{i}', 64) for i in range(RNG_LEN)]
rng = RngSource(vec)
psudo_rand = new(rng)
test = [psudo_rand.uint64() for _ in range(NUM_TEST)]
print(vec[0])
src = new_source(123843)
hehe = list(src.vec)
rand = new(src)
real = [rand.uint64() for _ in range(NUM_TEST)]
for i in trange(NUM_TEST):
s.add(real[i] == test[i])
print("solve......")
if s.check() == sat:
model = s.model()
array_values = [model.evaluate(vec[i]).as_long() for i in range(RNG_LEN)]
rng = RngSource(array_values)
print(f"{hehe[:10] = }")
print(f"{rng.vec[:10] = }")
test_rand = new(rng)
test = [test_rand.uint64() for _ in range(NUM_TEST)]
for i in range(20):
print(test_rand.uint64(), rand.uint64())
```
Các file cần thiết sẽ ở trong github của mình
## bash `$RANDOM`
```python!
def next_seed(self) -> int:
if self.seed == 0:
self.seed = 123459876
h = self.seed // 127773
l = self.seed - (127773 * h)
t = 16807 * l - 2836 * h
self.seed = (t + 0x7fffffff) if t < 0 else t
return self.seed
```
Tiếp tục là bruteforce seed :v
## Tài liệu tham khảo
1. https://soon.haari.me/import-random/
2. https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/
3. https://github.com/maple3142/gf2bv
4. https://www.mscs.dal.ca/~selinger/random/
5. https://cs.opensource.google/go/go/+/refs/tags/go1.24.2:src/math/rand/rng.go
Sign in with Wallet
Connect another wallet