## Math.random() in Nodejs
https://github.com/m1dm4n/CTF-WriteUp/blob/main/2023/plaidCTF/README.md

Hàm này được xây dựng dựa trên [XorShift128+ algorithm](https://github.com/v8/v8/blob/master/src/base/utils/random-number-generator.h#L119)

### XorShift128+ algorithm
Là một PRNG đơn giản với 128-bit `state`
Thuật toán này được thực hiện như sau:

  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;
  }

Ta có 2 giá trị `state0` và `state1`. Ở mỗi lần gọi hàm: `state1` được cập nhật giá trị là kết quả của các phép tính `XOR` và `shift` từ `state1` và `state0`. `state0` nhận giá trị `state1` trước đó.

### Cách hoạt động
Ta sẽ thử in ra một số giá trị random

nums = []; 
for(var i=0; i<5; ++i) { 
    nums.push(Math.random()) 
}; 
console.log(nums);

output:

[
  0.30135435755863194,
  0.3726454850458716,
  0.4198182193668114,
  0.7236693563736067,
  0.00626728852787628
]


Các giá trị được sinh ra là các số thập phân nằm trong khoảng $(0, 1)$. Các số nguyên 64bits đã được đưa về dạng `doubles` theo fomat của [IEEE 754 double-precision](https://en.wikipedia.org/wiki/Double-precision_floating-point_format). Bao gồm:
- Sign bit: 1 bit
- Exponent: 11 bits
- Significand precision: 53 bits (52 explicitly stored)

với 0x3fff được áp dụng cho exponent và sign, $e = 1023$ và $sign = 0$ giá trị thực của một số dấu phẩy động 64-bit theo chuẩn double-precision (độ chính xác kép) được tính như sau:
$$
-1^{sign}(1+\sum_{i=1}^{52}{b_{52-i}2^{-i}}) \times 2^{e-1023} = \
(1+\sum_{i=1}^{52}{2^{-i}})
$$

Sau khi trừ cho 1 thì luôn nhận được giá trị trong khoảng $(0,1)$.

  // Static and exposed for external use.
  static inline double ToDouble(uint64_t state0) {
    // Exponent for double values for [1.0 .. 2.0)
    static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
    uint64_t random = (state0 >> 12) | kExponentBits;
    return base::bit_cast<double>(random) - 1;
  }

Và đây là cách convert lại `state0`

static inline uint64_t FromDouble(double value) {
    // Exponent for double values for [1.0 .. 2.0)
    static const uint64_t kSignBitMask = uint64_t{0x7FFFFFFFFFFFFFFF};  
    // Add 1.0 to shift [0.0 .. 1.0) to [1.0 .. 2.0)
    value += 1.0;
    // Convert double to uint64_t by bit-casting, then remove the sign bit
    uint64_t bits = std::bit_cast<uint64_t>(value) & kSignBitMask;   
    return bits;
}

Như vậy ta thấy cách hoạt động của nó khá đơn giản và chỉ dựa trên phép `XOR` và `SHIFT`. Nên ta hoàn toàn có thể tìm lại được các `state` bằng Z3.Mình ở sẽ không trình bày cách giải ở đây.

Hàm **v8** không trả về giá trị random ngay lập tức mà lưu trữ 64 giá trị cùng lúc để có hiệu suất nhanh hơn và tạo ra đầu ra theo thứ tự ngược lại nên Math.random() sẽ giống thế này trong python.

def xs128p(state0, state1):
    s1 = state0
    s0 = state1
    s1 ^= (s1 << 23) & MASK
    s1 ^= (s1 >> 17) & MASK
    s1 ^= s0
    s1 ^= (s0 >> 26) & MASK
    return state1, s1
def to_double(value):
    double_bits = (value >> 12) | 0x3FF0000000000000
    return unpack('d', pack('<Q', double_bits))[0] - 1
def next_random(state0, state1):
    while True:
        cache = []
        for i in range(64):
            state0, state1 = xs128p(state0, state1)
            cache.append(to_double(state0))
        for i in reversed(cache):
            yield i
rng = next_random(..., ...)
print(next(rng))

### Implementing symbolic PRNG state
Mỗi bit của `state` có thể được biểu diễn tuyến tính với các bit xác định trước của trạng thái ban đầu. Vì dùng các phép biến đổi XOR(là phép cộng trên trường GF(2)).

Gọi $V$ là ma trận đơn vị chứa 128 vectors, $S$ là vector chứa 128 bits của `state` bao gồm cả `state0` và `state1`. Ta có: $V*S = S$. Ví dụ `state0 = state0^state1` ta sẽ có state mới được cập nhật như sau:

$\begin{pmatrix}
1_{1 - 1} & \dots & \dots & 1_{1 - 65} & \dots & 0_{1 - 128} \\
\vdots & \ddots & & \vdots & \ddots & \vdots \\
\vdots & & 1_{64 - 64} & \vdots & & 1_{64 - 128} \\
0_{65 - 1} & \dotsb & \dots & 1_{65 - 65} & \dots & 0_{65 - 128} \\
\vdots & & & \vdots & \ddots & \vdots \\
0_{128 - 1} & \dotsb & \dotsb & \dotsb & \dotsb & 1_{128 - 128}
\end{pmatrix} * \
\begin{pmatrix}
s_1 \\ s_2 \\ \vdots \\ s_{64} \\ s_{65} \\ \vdots \\ s_{128}
\end{pmatrix} = \
\begin{pmatrix}
s_1 + s_{65} \\ s_2 + s_{66} \\ \vdots \\ s_{64} + s_{128} \\ s_{65} \\ \vdots \\ s_{128}
\end{pmatrix}$

Python code:
- Khởi tạo `Add`, `ShiftRight` và `Shiftleft`

def Add(a, b):
    c = []
    for i, j in zip(a, b):
        c.append(i + j) #like i said, adding 2 vectors in GF(2) work same as xoring 2 numbers 
    return c
def SL(a, n):
    return a[n:] + [vector(F, 128)]*n
def SR(a, n):
    return [vector(F, 128)]*n + a[:64 - n]

Ta sẽ xây dựng các state tiếp theo dựa trên state đầu như sau.
Symbolic the Xorshift128 function:

def sym_xs128p(sym_state0, sym_state1):
    # Symbolically represent xs128p
    s1 = sym_state0
    s0 = sym_state1
    s1 = Add(s1, SL(s1, 23))
    s1 = Add(s1, SR(s1, 17))
    s1 = Add(s1, s0)
    s1 = Add(s1, SR(s0, 26))
    return sym_state1, s1

Cần đủ ma trận để thiết lập 128 phương trình độc lập
- Mục tiêu là khôi phục state0 và state1, mỗi cái 64 bit
- Tổng cộng cần tìm 128 bit chưa biết
- Do đó cần ít nhất 128 phương trình độc lập để giải hệ phương trình

Mỗi giá trị từ Math.random() cho ta 52 bit từ state0. Nhưng không phải lúc nào ta cũng nhận được đầy đủ 52 bit này nên ta cần biến tấu với yêu cầu của đề bài.

Do server có giới hạn thời gian, lưu trữ 820 ma trận đầu tiên của 820 đầu ra Math.random() để tra cứu nhanh hơn:

F = GF(2)
v = [vector(F, [0]*i + [1] + [0]*(127-i)) for i in range(128)]
state0 = v[:64]
state1 = v[64:]
N = 64 + (250+128)*2
Bigg = []
for i in range(N):
    state0, state1 = sym_xs128p(state0, state1)
    Bigg.append(state0[:-12]) # Output only using 52 bits for fraction
save(Bigg, f'equals')

Vì các trạng thái tiếp theo sẽ là tổng của 64 tập con từ 128 vector ban đầu của chúng ta, chúng ta có thể xây dựng một ma trận hệ số và giải hệ phương trình với 128 ẩn để khôi phục trạng thái ban đầu sau khi thu thập đủ các đầu ra. Mỗi đầu ra từ Math.random() sẽ cho chúng ta 52 bit từ state0 hiện tại.

### Predict
Trước tiên, cần tải các ma trận symbolic đã lưu trước đó:

equals = load(f'equals.sobj')

Nhớ rằng Node.js sử dụng bộ nhớ đệm cho mỗi 64 số, tạo một hàm hoạt động như một pivot trong việc tra cứu phương trình:

def next_idx():
    k = 63
    while True:
        for l in range(k, k-64, -1):  # Trả về index ngược từ k đến k-63
            yield l
        k += 64  # Tăng k thêm 64 cho lần lặp tiếp theo

Như đã đề cập, cần xây dựng một hệ phương trình và giải nó. Ma trận có rank đầy đủ sẽ luôn có nghiệm nên ta sẽ nạp ma trận cho đến khi có một ma trận với rank 128:

def solve_random(payloads, pre_run, idx_rng, leaks, step=0):
    Ms = matrix(F, 128, 128)  # Ma trận hệ số 128x128
    ans = vector(F, 128)      # Vector kết quả 128 phần tử
    c = 0  # Đếm số hàng đã thêm vào ma trận
    
    # Bỏ qua pre_run số đầu ra đầu tiên
    for i in range(pre_run):
        next(idx_rng)
        
    # Xử lý từng giá trị trong payload
    for value in payloads:
        if c == 128:  # Đã đủ 128 hàng độc lập
            break
        i = next(idx_rng)
        # Bỏ qua step lần gọi Math.random()
        for _ in range(step):
            next(idx_rng)
            
        # Xử lý các bit rò rỉ từ mỗi giá trị
        for j in range(len(leaks[value])):
            if leaks[value][j] is None:  # Bỏ qua nếu bit không rò rỉ
                continue
            Ms.set_row(c, equals[i][j])  # Thêm hàng mới vào ma trận
            if Ms.rank() > c:  # Kiểm tra nếu hàng mới độc lập
                ans[c] = leaks[value][j]  # Thêm giá trị bit rò rỉ vào vector kết quả
                c += 1
            if c == 128:
                break
                
    # Giải hệ phương trình Ms * state = ans
    state = Ms.solve_right(ans)
    # Chuyển đổi vector nhị phân thành số nguyên
    state0 = int(''.join(map(str, state[:64])), 2)
    state1 = int(''.join(map(str, state[64:])), 2)
    return state0, state1

Trong đó:
- Tham số `pre_run`: Math.random() có thể đã được chạy trước khi rò rỉ một số đầu ra cho chúng ta.
- Tham số `leaks`: Đầu ra không phải lúc nào cũng rò rỉ toàn bộ giá trị ngẫu nhiên.

Ví dụ nếu nhân với 4 rồi làm tròn:
- leaks = [[0,0], [0,1], [1,0], [1,1]]

from new_xs128p import *
import os
import math

b4 = [
    [0, 0],
    [0, 1],
    [1, 0],
    [1, 1],
]
seed = os.urandom(16)
original_state0, orginal_state1 = int.from_bytes(
    seed[:8], 'big'), int.from_bytes(seed[8:], 'big')
print("original seed: (%s, %s)" % (original_state0, orginal_state1))
rng = next_random(original_state0, orginal_state1)

randoms = [next(rng) for i in range(15 + 192 + 128)]
mult = 4
payloads = [math.floor(random * mult) for random in randoms]
print("Last 128 value of payloads:\n\t", payloads[-128:])


state0, state1 = solve_random(payloads[15:-128], 15, next_idx(), b4)
print("recovered seed: (%s, %s)" % (state0, state1))

new_rng = next_random(state0, state1)
for i in range(15 + 192):
    next(new_rng)
predict_random = [math.floor(next(new_rng)*mult) for i in range(128)]
print("Predicted value:\n\t", predict_random)

- 15 là số lần đã chạy Math.random()
- Ta cần thêm 192 lần random (64*3) giúp đồng bộ cache lại đúng với trạng thái ban đầu mà nó đã có khi tạo ra chuỗi số ngẫu nhiên mà ta đang cố gắng dự đoán.
- 128 là các giá trị tiếp theo.

Tham số step: Dùng khi mỗi lần output gọi nhiều lần Math.random()
Vậy là ta đã thành công!!