Crack Random Module

Khởi động nhẹ nhàng: How To Predict Random Numbers Generated By Computers

1. Python

Hàm random của Python sử dụng thuật toán Mersenne Twister - với 624 số nguyên 32 bit làm trạng thái, sau đó cứ mỗi lần xuất ra một số nguyên 32 bit, nó sẽ thay đổi trạng thái.

Mersenne Twister

Ta sẽ phân tích thuật toán tạo số ngẫu nhiên trong khoảng [0,0xffffffff]: Link

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* 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]ANDUPPER_MASK)|(mt[kk+1]ANDLOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y AND 0x1U];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]ANDUPPER_MASK)|(mt[kk+1]ANDLOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y AND 0x1U];
        }
        y = (mt[N-1]ANDUPPER_MASK)|(mt[0]ANDLOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y AND 0x1U];

        self->index = 0;
    }

    y = mt[self->index++];
    y ^= (y >> 11);
    y ^= (y << 7) AND 0x9d2c5680U;
    y ^= (y << 15) AND 0xefc60000U;
    y ^= (y >> 18);
    return y;
}

Nếu index >= N (= 624), nghĩa là đã dùng hết số trong mảng mt[] và do đó phải tạo lại 624 số tiếp theo. Mảng mt[] được thay đổi bằng quá trình sau:

1
2
3
4
5
y = (mt[kk] AND UPPER_MASK) | (mt[(kk + 1) % N] AND LOWER_MASK)
mt[kk] = mt[(kk + M) % N] ^ (y >> 1) ^ mag01[y AND 0x1U]

y = (mt[N-1]ANDUPPER_MASK)|(mt[0]ANDLOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y AND 0x1U];

Sau đó, số y ngẫu nhiên được tạo như sau:

1
2
3
4
5
6
y = mt[self->index++];
y ^= (y >> 11);
y ^= (y << 7) AND 0x9d2c5680U;
y ^= (y << 15) AND 0xefc60000U;
y ^= (y >> 18);
return y;

Do đó, nếu ta có thể đảo ngược được quá trình này thì ta có thể dự đoán giá trị tiếp theo khi biết được 624 đầu ra 32 bit.

Khôi phục từ đầu ra đầy đủ 32-bit

Sau đây là các bước đảo ngược chi tiết: y ^= (y >> 18)

Đây là dịch phải 18 bit, ảnh hưởng từ bit cao tới bit thấp và sau bước này thì bit cao không thay đổi cùng với việc $18*2 = 36 > 32$ nên ta chỉ cần 1 lần đảo là được.

1
2
# Step 1
y ^= (y >> 18)

y ^= (y << 15) AND 0xefc60000

Ở đây, mask 0xefc60000 có cấu trúc đặc biệt với làm phép biển đổi trở thành 1 hàm tự nghịch đảo, nghĩa là $f(f(x))=x$, với $f(x) = x \oplus ((x « 15)$ AND 0xefc60000). Chứng minh:

Đặt A = 0xefc60000. Khi đó:

$f(y)=f(f(x)) = f(x \oplus ((x « 15) AND \ A))$

$= (x \oplus ((x « 15) AND \ A)) \oplus (((x \oplus ((x « 15) AND \ A)) « 15) AND \ A)$

$= (x \oplus ((x « 15) AND \ A)) \oplus (((x « 15) AND \ A) \oplus((x « 30) AND (A « 15) AND \ A))$

$= x \oplus (((x « 15) AND \ A) \oplus ((x « 15) AND \ A)) \oplus((x « 30) AND (A « 15) \ AND \ A) = x$

(vì tính chất $P \oplus P = 0$ và $A$ có 17 bit thấp là 0 nên nếu dịch trái 15 bit thì 32 bit cuối của $A « 15$ sẽ đều là 0 nên $(A « 15) AND \ A = 0$)

Do đó, để đảo ngược thì ta chỉ cần 1 lần biến đổi hàm nữa:

1
2
# Step 2
y ^= (y << 15) AND 0xefc60000

y ^= (y << 7) AND 0x9d2c5680

Ở bước này thì ta sẽ thiết lập một hàm dịch bit gần tương tự như bước trên:

Đặt B = 0x9d2c5680. Với $y = x \oplus ((x « 7) AND \ B)$ , ta sẽ dùng hàm $f(x’) = y \oplus ((x’ « 7) AND \ B)$ Khi đó:

$f_4(y) = f_4(x \oplus ((x « 7) AND \ B)) = f_3(y \oplus (((x \oplus ((x « 7) AND \ B)) « 7)AND \ B))$

$= f_3(x \oplus (((x « 7) AND \ B) \oplus ((x « 7) AND \ B)) \oplus((x « (7\times2))AND (B « 7) AND \ B))$

$= f_3(x \oplus((x « (7\times2))AND (B « 7) AND \ B))$

$= f_2(x \oplus((x « (7\times3))AND (B « (7\times2)) AND (B « 7) AND \ B))$

$= f(x \oplus((x « (7\times4))AND (B« (7\times3)) AND (B « (7\times2)) AND (B « 7) AND \ B))$

$= x \oplus((x « (7\times5))AND (B« (7\times4)) AND (B« (7\times3)) AND (B « (7\times2)) AND (B « 7) AND \ B)$

$=x$

(vì B có 7 bit thấp là 0 nên nếu dịch trái 28 bit thì 32 bit cuối của $B « 28$ sẽ đều là 0 nên đẳng thức trên xảy ra.)

Do đó, để đảo ngược thì ta chỉ cần 4 lần biến đổi hàm như sau:

1
2
3
4
5
# Step 3
res = y
for _ in range(4):
    res = y ^ (res << 7) AND 0x9d2c5680
y = res

y ^= (y >> 11) Đây là dịch phải 11 bit, ảnh hưởng từ bit cao tới bit thấp và sau bước này thì bit cao không thay đổi cùng với việc $11*3 = 33 > 32$ nên ta chỉ cần 2 lần đảo để khôi phục từ bit cao đến bit thấp.

1
2
3
4
# Step 4
res = y
for _ in range(2):
    res = y ^ (res >> 11)

Tổng hợp lại thì ta có hàm đảo (untemper):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def untemper(y):
    # 1. Rev: y ^= (y >> 18)
    y ^= (y >> 18)
    # 2. Rev: y ^= (y << 15) AND 0xefc60000
    y ^= (y << 15) AND 0xefc60000
    # 3. Rev: y ^= (y << 7) AND 0x9d2c5680
    temp = y
    for _ in range(4):
        temp = y ^ (temp << 7) AND 0x9d2c5680
    y = temp
    # 4. Rev: y ^= (y >> 11);
    temp = y
    for _ in range(2):
        temp = y ^ (temp >> 11)
    y = temp
    return y

Ví dụ cụ thể:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import random

state = random.getstate()

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)

State được phục hồi có 3 phần tử:

Số nguyên 3, là chỉ số “vị trí trạng thái” được module random của Python sử dụng để chỉ ra vị trí của bộ tạo trong mảng trạng thái.
Bộ dữ liệu gồm 624 số nguyên, biểu diễn mảng trạng thái đã phục hồi.
None là “giá trị giữ chỗ” để đảm bảo tính tương thích với định dạng trạng thái mà module random của Python mong đợi.

Khi chạy đoạn kiểm thử trên thì dòng lệnh đối chiếu với assert không bị lỗi, chứng tỏ đã khôi phục thành công state ban đầu.

2. Javascript

Phương thức tĩnh Math.random() trả về một số dấu phẩy động, ngẫu nhiên lớn hơn hoặc bằng 0 và nhỏ hơn 1, với phân phối gần như đồng đều trong phạm vi đó — sau đó bạn có thể điều chỉnh theo phạm vi mong muốn. Việc triển khai sẽ chọn seed ban đầu cho thuật toán tạo số ngẫu nhiên; người dùng không thể chọn hoặc đặt lại seed này.

XorShift128 trả về trạng thái 128-bit qua state0, state1 và được triển khai như sau:

1
2
3
4
5
6
7
8
9
def xs128(state0, state1):
    mask = (1 << 64) - 1
    s1 = state0 AND mask
    s0 = state1 AND mask
    s1 ^= (s1 << 23) AND mask
    s1 ^= (s1 >> 17) AND mask
    s1 ^= s0
    s1 ^= (s0 >> 26) AND mask
    return s0, s1

Khi cache trống, 1 chuỗi 64 giá trị ngẫu nhiên mới sẽ được tạo thành qua xs128 và lưu trữ trong cache với chỉ số được đặt ở cuối.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def _refill(self):
    """
    Refill the Math.random cache using xs128.
    Can only be used when Math.random cache is empty.

    A new 64-long list of random values is stored in cache.
    The cache_idx is set to the last index of the cache (63).
    """
    assert self.cache_idx == -1
    self.cache = []
    for _ in range(64):
        self.state0, self.state1 = xs128(self.state0, self.state1)
        self.cache.append(self.state0)
    self.cache_idx = 63

Lúc gọi Math.random() thì next() được gọi và đưa ra 1 giá trị thập phân từ 0.0 đến 1.0. Ở đây thì v8 chuyển đổi số từ xs128 sang double bằng cách bỏ 12 bit cuối, còn 52 bit thì đưa vào phần Mantissa của số double trong chuẩn IEEE754. Sau đó trừ đi 1 và có được giá trị thập phân từ 0.0 đến 1.0.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def v8_to_double(state0, debug):
    r = (state0 >> 12) | 0x3ff0000000000000
    if debug:
        return r
    else:
        return struct.unpack('d', struct.pack('<Q', r))[0] - 1
    
def next(self):
    if self.cache_idx < 0:
        self._refill()
    val = v8_to_double(self.cache[self.cache_idx], self.debug)
    self.cache_idx -= 1
    return val

Khôi phục trạng thái từ một lượng giá trị ngẫu nhiên được cho

Math.random() của V8 sử dụng xs128 gồm các biểu thức tuyến tính trong hệ GF(2). Do đó, ta có thể xây dựng một hệ các phương trình tuyến tính trên GF(2) với 1 lượng giá trị ngẫu nhiên cho trước vừa đủ và từ đó, ta được nghiệm của hệ này là hai trạng thái ban đầu (seed) của thuật toán và dự đoán được giá trị ngẫu nhiên tiếp theo.

Chúng ta sẽ xây dựng hệ như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
numbers = [
    0.20850633840727073,
    0.28382289045651743,
    0.4071416957057805,
    0.3101367279739642,
    0.6813711566813534,
    0.8365880507655776,
    0.2238039081275922,
    0.014754643967695324,
    0.44290438850282876,
    0.5473214381957232,
    0.40023560591139606,
    0.14837298522461473,
    0.12321774476187275,
    0.8501766788936596,
    0.9212308144118708,
    0.8099337802981195,
    0.06047989985671265,
    0.6552969701254443,
    0.5803218168252511,
    0.41915921494443964,
    0.9153038363744563,
    0.7403989120318095,
    0.6630141727527132,
    0.5230661117641415
]

Đây là những giá trị ngẫu nhiên cho trước

1
2
3
4
5
6
7
from gf2bv import LinearSystem

lin = LinearSystem([64] * 2)
state0, state1 = lin.gens()

Random = MathRandom(state0, state1, True)
out = [Random.next() for _ in range(len(numbers))]

state0, state1 là hai symbolic unknown có 64-bit và nằm trong hệ tuyến tính. Random sẽ tạo những biểu thức tuyến tính chính là out với ẩn là state0, state1 để xây dựng hệ.

1
zeros=[(v8_from_double(x) >> 12 | 0x3ff0000000000000) ^ y for x,y in zip(numbers, out)]

Với mỗi cặp giá trị và phương trình ẩn, ta khôi phục 52 bit mantissa của đầu ra và đưa về chuẩn IEEE754 cho dạng double + 1.0 rồi XOR với biểu thức ẩn đã cho.
Nếu biểu thức này trùng với giá trị đầu ra thì sau khi XOR sẽ bằng 0. Vậy là ta đã có hệ tuyến tính ẩn state0, state1, giải hệ này và ta nhận được trạng thái ban đầu.

1
sol = lin.solve_one(zeros)

3. C/C++

Bên ngôn ngữ C/C++, hàm rand() xây dựng dựa trên GLIBC random number generator

Hàm random() của thư viện GNU C cung cấp các số giả ngẫu nhiên thông qua phương pháp phản hồi cộng tuyến tính. Phản hồi này tuyến tính theo modulo $2^{32}$. Tính phi tuyến tính nhỏ duy nhất xuất hiện trong giai đoạn seeding, do phép này được thực hiện theo modulo $2^{31} - 1$ chứ không phải modulo $2^{31}$ hay $2^{32}$. Điều này có nghĩa là, mặc dù mỗi số ngẫu nhiên được tạo ra phụ thuộc tuyến tính vào các số trước đó trong chuỗi, nhưng toàn bộ các số ngẫu nhiên không phụ thuộc tuyến tính vào seed.

Thuật toán

Như mô tả ở trên, ta có: $2147483647 = 2^{31} - 1$ và $4294967296 = 2^{32}$

Với mỗi seed cho trước, 1 initialization vector (iv) $r_0…r_{33}$ được tính như sau:

$r_0$ = seed
$r_i\equiv (16807 * r_{i-1}) \mod 2147483647 \ ( i \in [1,30])$
$r_i=r_{i-31}\ (i\in [31, 33])$

Sau đó, 1 chuỗi các số ngẫu nhiên $r_{34}…$ được tạo bằng vòng lặp phản hồi tuyến tính:

$r_i\equiv r_{i-3}+r_{i-31}\mod 4294967296 \ (i \ge 34)$

$r_0…r_{343}$ không được sử dụng mà đầu ra $o_i$ của hàm rand() là: $o_i =r_{i+344} \gg 1$

Code in C:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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);
  }
}

Khôi phục

Phân tích thuật toán trên thì ta thấy rằng:

Từ $i\ge34$, $r_i\equiv r_{i-3}+r_{i-31}$ là tuyến tính và có nghĩa là khi ta biết được 2 trong 3 giá trị thì sẽ suy ra được giá trị còn lại.
Với đầu ra $o_i =r_{i+344} \gg 1$, nghĩa là nó có 31 bit và mất bit bên phải ngoài cùng $r_{i+344}$
Nghĩa là nếu ta có đủ đầu ra liên tiếp thì hoàn toàn có thể lan truyền để khôi phục lại mảng trạng thái ban đầu (iv).

Các bước để khôi phục iv như sau:

Đoán bit thấp bị bỏ rồi ghép thành một phần trạng thái:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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]) AND 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

Nếu ta có $o_i, o_{i-31},o_{i-3}$ và chúng không thỏa:

1
outputs[i] == (outputs[i - 31] + outputs[i - 3]) AND 0x7fffffff

Đoán trạng thái của nỏ ở dạng:

$$ \begin{cases} s_{i-31} = o_{i-31} << 1 + 1 \\ s_{i-3} = o_{i-3} << 1 + 1 \\ s_i = o_i << 1 + 0 \end{cases} $$

Nếu không, gắn $s_i =$ None vì chưa biết dạng chuẩn.

Khôi phục trạng thái:

Chạy ngược công thức cộng để khôi phục các giá trị (nếu có) trong 344 giá trị đầu

1
2
3
4
5
6
7
8
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

Nếu có 1 giá trị trong khoảng 31 giá trị đầu, ta có thể tính tất cả các giá trị còn lại vì tính chất tuyến tính bằng công thức: $r_i\equiv (16807 * r_{i-1}) \mod 2147483647 \Leftrightarrow r_{i-1}\equiv (16807^{-1} * r_i) \mod 2147483647$

1
2
3
4
5
6
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

Vì tính chất tuyến tính $r_i \equiv r_{i-3}+r_{i-31}, \forall i \ge 34$ nên nếu ta biết 2 giá trị thì suy ra được giá trị còn lại. Do đó, ta viết hàm lặp đến khi không thể khôi phục giá trị nào nữa để điền tất cả các giá trị còn thiếu.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
             
all_states = init + states
self_recover(all_states)

Điền 3 giá trị đầu bằng các sao chép từ thứ tự 31 và lấy được seed ban đầu:

1
2
for i in range(3):
    all_states[i] = all_states[i + 31]

Full code ở đây…

4. Golang

PRNG của Golang xây dựng dựa trên Lagged Fibonacci Generator.

Thuật toán

Hàm tạo seed cho rng: $x_{n+1} = 48271 * x_n \mod (2^{31} - 1)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def seedrand(x):
    A = 48271
    Q = 44488
    R = 3399

    hi = x // Q
    lo = x % Q
    x = A * lo - R * hi
    if x < 0:
        x += INT32_MAX
    return x

Để tránh tràn số thì code dùng Schrage’s Method (hi = x // Q, lo = x % Q).

Tiếp theo, ta có class RNGSource là PRNG chính.

1
2
self.tap = 0
self.feed = RNG_LEN - RNG_TAP   # 607 - 273 = 334

Hai con trỏ là tap và feed chạy ngược nhau, thực hiện phép cộng sinh số ngẫu nhiên rồi sau đó lưu trữ trạng thái này vào mảng vec, tổng 607 phần tử 64-bit.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def seed(self, seed):
    self.tap = 0
    self.feed = RNG_LEN - RNG_TAP

    seed %= INT32_MAX
    if seed < 0:
        seed += INT32_MAX
    if seed == 0:
        seed = 89482311

    x = int(seed)
    for i in range(-20, RNG_LEN):
        x = seedrand(x)
        if i >= 0:
            u = (int(x) << 40) AND 0xFFFFFFFFFFFFFFFF
            x = seedrand(x)
            u ^= (int(x) << 20) AND 0xFFFFFFFFFFFFFFFF
            x = seedrand(x)
            u ^= int(x)
            u ^= rng_cooked[i]
            self.vec[i] = u

Hàm seed() sẽ nhận giá trị seed và tạo ra mảng trạng thái vec như sau:

x được gọi seedrand() 20 lần để tạo số ngẫu nhiên.
Ghép 3 giá trị 31-bit thành số 64-bit qua hàm seedrand() với $x « 40, x « 20, x$.
XOR với 1 giá trị trong bảng rng_cooked[].

Tiếp theo, ta sẽ sinh số ngẫu nhiên 64-bit qua vec bằng hàm uint64():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def uint64(self):
    self.tap -= 1
    if self.tap < 0:
        self.tap += RNG_LEN

    self.feed -= 1
    if self.feed < 0:
        self.feed += RNG_LEN

    x = (self.vec[self.feed] + self.vec[self.tap]) AND 0xFFFFFFFFFFFFFFFF
    self.vec[self.feed] = x
    return x

Hai con trỏ tap và feed đi lùi trong vòng có độ dài 607.
Theo đó là công thức Additive Lagged-Fibonacci Generator: $$ vec_{feed}=(vec_{feed} + vec_{tap}) AND 0xFFFFFFFFFFFFFFFF $$

1
2
x = (self.vec[self.feed] + self.vec[self.tap]) AND 0xFFFFFFFFFFFFFFFF
self.vec[self.feed] = x

Khôi phục

Như ta thấy, trong golang thì từ sau giai đoạn sinh seed, giai đoạn sinh số ngẫu nhiên chỉ gồm phép cộng tuyến tính trên chuỗi seed lấy được. Nghĩa là nếu ta có chuỗi đầu ra đủ dài, ta có thể xây dựng hệ phương trình tuyến tính để tính chuỗi seed ban đầu.

Để xây dựng được hệ như vậy, mình nghĩ ngay tới z3-solver và sau đây là phần crack:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from rng import *
from z3 import *

s = Solver()
NUM_TEST = 700

vec = [BitVec(f'vec_{i}', 64) for i in range(RNG_LEN)]
rng_equation = RngSource(vec)
equations = [rng_equation.uint64() for _ in range(NUM_TEST)]

rng_value = RngSource()
rng_value.seed(int(input("Enter seed: ")))
vals = [rng_value.uint64() for _ in range(NUM_TEST)]

for i in range(NUM_TEST):
    s.add(equations[i] == vals[i])

print("99%...")

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)

    for _ in range(NUM_TEST):
        res = rng.uint64()

    for _ in range(10):
        print(rng.uint64(), rng_value.uint64())

5. Bash

Bash dùng linear congruential generator (LCG) là biến thể của thuật toán Park–Miller “minimal standard” để tạo số ngẫu nhiên 31-bit.

Thuật toán

Hàm next_seed sinh seed mới bằng cách áp dụng công thức Park-Miller LCG:

$$ X_{k+1}=(a\times X_k)\mod m $$

với $a = 16807,\ m = 2^{31} - 1$

1
2
3
4
5
6
7
8
9
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

Giống Golang, nhằm tránh bị tràn số thì ta dùng Schrage’s Method để tách h và l.

Với seed đó, ta sinh giá trị ngẫu nhiên bằng hàm next_16:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def next_16(self) -> int:
    self.next_seed()

    if self.is_old:
        # Bash 5.0 and earlier
        result = self.seed AND BASH_RAND_MAX
    else:
        # Bash 5.1 and later
        result = ((self.seed >> 16) ^ (self.seed AND 0xffff)) AND BASH_RAND_MAX

    # Skip if same as last
    if result == self.last:
        return self.next_16()
    self.last = result
    return result

Có 2 phiên bản khác nhau:

Từ bản Bash 5.0 trở xuống, ta chỉ lấy 15 bit thấp.
Bash 5.1 trở lên: XOR 2 giá trị 16 bit cao và 16 bit thấp của seed rồi trả về 15 bit cuối.

Bên cạnh đó, nếu số mới giống số cũ, ta bỏ qua và tính số mới.

Khôi phục

Vì ở đây, ta không có được trực tiếp $X_n$ mà chỉ lấy được giá trị của nó sau hàm next_16 nên không thể truy ngược được Park-Miller LCG. Do đó, kỹ thuật mình có thể sử dụng ở đây để crack là brute-force.

Mặt khác output chỉ cho 15 bit, trong khi state có 31 bit, thế nên chắc chắn có rất nhiều state cho ra cùng 1 giá trị output. Để lọc được state phù hợp, ta cần nhiều giá trị output liên tiếp để chắc chắn tìm được duy nhất 1 state. Nếu không có nhiều output như vậy, ta có thể tìm những state phù hợp để thử và tìm ra kết quả cuối cùng.

Do seed có 32 bit, ta nên sử dụng nhiều luồng nhằm chia các khoảng của nó và chạy các task song song để giảm thời gian thực hiện và tối ưu hóa bộ nhớ. Ở đây, mình sử dụng Pool của thư viện multiprocessing trong Python để chia luồng, rồi thực hiện các task duyệt, so sánh với đầu ra cho trước và trả về seed nếu khớp. Full code ở đây…