Hacker News Digest

Xorshift128+ можно «перевернуть» за 226 операций, если даны два полных 64-битных вывода.

Math.random() в Node.js использует Xorshift128+, но отдаёт лишь 52 младших бита суммы новых состояний. CVE-2025-7783 показал, что при пяти последовательных выводах можно предсказать дальнейшие значения через z3. Автор решил проверить, достаточно ли меньше данных.

Алгоритм Xorshift128+

s1 = L
s0 = R
L = R
s1 ^= s1<<23 ^ s1>>17 ^ s0 ^ s0>>26
R = s1

Вывод: x = L + R (64 бита). В Math.random() старшие 12 бит теряются.

Обозначения

• (L₀,R₀) – начальное состояние.
• (Lᵢ,Rᵢ) – состояние на шаге i.
• xᵢ = Lᵢ₊₁ + Rᵢ₊₁ – вывод.

Суть атаки

1. Зная x₀, выражаем L₁ = x₀ - R₁.
2. Из уравнений Xorshift128+ получаем 64 линейных уравнения относительно 64 неизвестных битов R₁.
3. Система решается за O(2²⁶) операций методом Гаусса по модулю 2.

Расширение до Math.random()
Нужны три вывода, чтобы восстановить недостающие 12 бит каждого. Сложность ≈ 2⁵⁰, но можно улучшить.

Код и приглашение
GitHub-репозиторий с реализацией; автор приглашает к оптимизации.