random

crp | random

Information

This is xoshiro256** 1.0, one of our all-purpose, rock-solid generators. It has excellent (sub-ns) speed, a state (256 bits) that is large enough for any parallel application, and it passes all tests we are aware of.

Public

Provide 2 files: public/Program.cs and public/output.txt

Writeup

When no seed is specified, recent versions of C# on 64-bit machines use the xoshiro256** PRNG:

internal ulong NextUInt64()
{
    ulong s0 = _s0, s1 = _s1, s2 = _s2, s3 = _s3;

    ulong result = BitOperations.RotateLeft(s1 * 5, 7) * 9;
    ulong t = s1 << 17;

    s2 ^= s0;
    s3 ^= s1;
    s1 ^= s2;
    s0 ^= s3;

    s2 ^= t;
    s3 = BitOperations.RotateLeft(s3, 45);

    _s0 = s0;
    _s1 = s1;
    _s2 = s2;
    _s3 = s3;

    return result;
}

The transition function is linear in GF(2), and the result is a non-linear function of s1. If we're given exact return values of NextUInt64, it's trivial to break the RNG. We would be able to recover s1 by multiplying by multiplicative inverses, to express the bits of s1 as linear functions of the initial state, build a system of linear equations and solve it to find the initial state. However, the challenge uses the output of rng.Next(256), which for 256 is equivalent to keeping only the 8 upper bits of result. It is not possible to recover any bits of s1 given this information.

We can even check if there are any fixed linear (or affine) relations between bits of s1, conditional on the value of result:

from sage.all import *
import random
def f(x):
    x *= 5
    x %= 2**64
    x = (x << 7) | (x >> (64 - 7))
    x %= 2**64
    x *= 9
    x %= 2**64
    return x >> 56
vectors = [[] for _ in range(256)]
for i in range(100000):
    a = random.getrandbits(64)
    v = vector(GF(2), '1' + bin(a)[2:].zfill(64))
    vectors[f(a)].append(v)
for i in range(256):
    mat = matrix(GF(2), vectors[i])
    print(mat.rank(), len(vectors[i]))

For every value of result, this program generates some random potential values of s1, and then computes the rank of the matrix generated by these values' bits (and a 1 to handle subsets with xor 1 as well). All 256 matrices have rank 65, meaning that the vectors are independent and no fixed affine relations exist for any value of result, and no information can be gained in this way.

It's possible to gain probabilistic linear relations, but then solving the linear system becomes the LPN (learning parity with noise) problem, for which as far as I know no sufficiently fast algorithms are known.

There may be multiple solutions here; the one I found is to check for degree 2 relations instead:

• Assuming the value of result is fixed, it's possible that there exist nontrivial degree <=2 boolean functions with 64 inputs that are always true when evaluated on s1. The function f(...) = 1 fits this description, but isn't worth considering as it doesn't provide any information.
• The function can be written as $$f(x_1, \dots, x_{64}) = k_0 + \sum_{i} k_i x_i + \sum_{i \le j} k_{ij} x_i x_j,$$ and every bit of s1 can be represented as $\sum_i k_i s_i$, where s is the initial state.
• We can substitute expressions for bits of s1 directly into f, expand parentheses and obtain degree 2 equations that are true for the initial state.

We still have to find these degree 2 boolean functions. This can be done by generating many random 64-bit vectors that correspond to a given value of result >> 56, computing all $1 + 64 + \frac{64 \cdot 63}2 = 2081$ monomials for each of them and finding a matrix's kernel. The implementation is in gen_rels.cpp, it finds on average 23 equations per output byte.

This allows us to create an overdetermined system of degree 2 equations on 256 variables, which has the initial state as its (hopefully only) solution. The algorithm I used to solve it is linearization: we can consider every monomial (like $x_1x_2$) as a separate variable. Then we will have a system of linear equations with $1 + 256 + \frac{256 \cdot 255}2 = 32897$ variables, which can be solved using M4RI. The implementation is in hax.cpp, it expects the output of gen_rels.cpp in file list_rels and a hex-decoded version of output.txt in file out_bin.

Flag

brics+{8d30547486c090f6a057d296fc167089}