Reversing the xoshiro256** engine?

[Peter Verswyvelen]

When seeding the xoshiro256** using 4 SplitMix64 calls, does anyone know how to find the initial seed (for the SplitMix64) exist that will produce a given first output value?

E.g. does the xoshiro256** first value function has an inverse function?

I tried a brute force approach but it would take about 4 years to find such seeds on one NVIDIA A6000 GPU :)

I know SplitMix64 is invertible, but it's not clear how to solve for the xoshiro256** first statement the returns the random value, e.g. rotl(state0 + state3, 23) + state0;

Thanks,
Peter

[Jsknkj RNG]

rotl(state0 + state3, 23) + state0 is in xoshiro256++, not xoshiro256** (which has rotl(s[1] * 5, 7) * 9 instead)

[Sebastiano Vigna]

> On 2 Mar 2023, at 14:18, Peter Verswyvelen <bug...@gmail.com> wrote:
>
> When seeding the xoshiro256** using 4 SplitMix64 calls, does anyone know how to find the initial seed (for the SplitMix64) exist that will produce a given first output value?

There are 2^192 such values.

> E.g. does the xoshiro256** first value function has an inverse function?

That does not make any mathematical sense--an inverse function implies a bijection, and there's no bijection between 2^64 and 2^256.

> I tried a brute force approach but it would take about 4 years to find such seeds on one NVIDIA A6000 GPU :)

You just have to solve an F₂-linear system which will be very underspecified, so it'll have a lot of solutions.

> I know SplitMix64 is invertible, but it's not clear how to solve for the xoshiro256** first statement the returns the random value, e.g. rotl(state0 + state3, 23) + state0;

That is xoshiro256++, not xoshiro256**. I have no idea how to invert the xoshiro256++ mixing function, but inverting the xoshiro256** mixing function is easy, as all three steps are invertible.

Ciao,

seba

[Sebastiano Vigna]

> On 3 Mar 2023, at 14:07, Sebastiano Vigna <sebastia...@unimi.it> wrote:
>
> I tried a brute force approach but it would take about 4 years to find such seeds on one NVIDIA A6000 GPU :)
>
> You just have to solve an F₂-linear system which will be very underspecified, so it'll have a lot of solutions.

BTW: if you are using the standard version of xoshiro256**, which uses the current state to emit the output, you don't even need a system. Just plug in s[0] the value obtained by reversing the scrambling. All other values can be anything.

Ciao,

seba

[Peter Verswyvelen]

> E.g. does the xoshiro256** first value function has an inverse function?

That does not make any mathematical sense--an inverse function implies a bijection, and there's no bijection between 2^64 and 2^256.

Ah yes, chat.openai.com told me the same ;) My reasoning was that because the input is 64-bits (the seed), and the output is 64-bits, an inverse might exist (for the first output value)

> I tried a brute force approach but it would take about 4 years to find such seeds on one NVIDIA A6000 GPU :)

You just have to solve an F₂-linear system which will be very underspecified, so it'll have a lot of solutions.

> I know SplitMix64 is invertible, but it's not clear how to solve for the xoshiro256** first statement the returns the random value, e.g. rotl(state0 + state3, 23) + state0;

That is xoshiro256++, not xoshiro256**. I have no idea how to invert the xoshiro256++ mixing function, but inverting the xoshiro256** mixing function is easy, as all three steps are invertible.

You must be kidding, I feel so silly now, I must have clicked the wrong link on your excellent webpage.

Okay, if anyone needs it, this is what I came up with (seems to work, based on https://www.vincent-lunot.com/post/playing-with-pseudo-random-number-generators-part-3/)

uint64_t reverse_xorshift(uint64_t y, int shift)
{
  auto delta = 64 - shift;
  auto x = y >> delta << delta;
  auto reversed = shift;
  delta = std::max(0, delta - shift);
  while (reversed < 64) {
    auto const yrr = y << reversed >> reversed;
    auto const xrr = (x << (reversed - shift)) >> reversed;
    auto const zrr = (yrr ^ xrr) >> delta << delta;
    x += zrr;
    delta = std::max(0, delta - shift);
    reversed += shift;
  }
  return x;
}

uint64_t constexpr reverse_odd_number(uint64_t x)
{
  auto r = x;
  r *= 2 - r * x;
  r *= 2 - r * x;
  r *= 2 - r * x;
  r *= 2 - r * x;
  r *= 2 - r * x;
  return r;
}

uint64_t reverse_splitmix64(uint64_t z5)
{
  auto constexpr rev_0x94d049bb133111eb = reverse_odd_number(0x94d049bb133111eb);
  auto constexpr rev_0xbf58476d1ce4e5b9 = reverse_odd_number(0xbf58476d1ce4e5b9);

  auto const z4 = reverse_xorshift(z5, 31);
  auto const z3 = z4 * rev_0x94d049bb133111eb;
  auto const z2 = reverse_xorshift(z3, 27);
  auto const z1 = z2 * rev_0xbf58476d1ce4e5b9;
  auto const x1 = reverse_xorshift(z1, 30);
  auto const x0 = x1 - 0x9e3779b97f4a7c15;
  return x0;
}

uint64_t reverse_xoshiro256ss_seeded_with_splitmix64(uint64_t first_output)

{
   auto constexpr rev_9 = reverse_odd_number(9);
   auto constexpr rev_5 = reverse_odd_number(5);

   auto const l7 = first_output * rev_9;
   auto const m5 = _rotr64(l7, 7);
   auto const s1 = m5 * rev_5;

   auto const x1 = reverse_splitmix64(s1);
   auto const x0 = x1 - 0x9E3779B97F4A7C15;

   return x0;
}

Ciao,

                                                         seba

--
You received this message because you are subscribed to a topic in the Google Groups "prng" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/prng/WPjMq-IH5HI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to prng+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/prng/A6C2F6C2-A269-465D-9186-0786272A4602%40unimi.it.