Deriving how to reverse the output of a Mersenne Twister PRNG into the internal state, as used in https://github.com/46bit/pinocchio.

deriving-mersenne-twister-state-from-outputs.txt

func (m *MersenneTwister) Urand32() uint32 {
  if m.index == 0 {
    m.generate_numbers()
  }

  y := m.State[m.index]
  y = y ^ (y >> 11)                   //
  y = y ^ ((y << 7) & 2636928640)     //
  y = y ^ ((y << 15) & 4022730752)    //
  y = y ^ (y >> 18)                   // "y XOR leftmost 14 bits of y"

  m.index = (m.index + 1) % 624
  return y
}

// WORKING INWARDS

// y = y ^ (y >> 18)
// "y XOR leftmost 14 bits of y"

  abcd efgh ijkl mnop qrst uvwx yz12 3456
  0000 0000 0000 0000 0000 0000 0000 0000
^                       00 0000 0000 0000

out(s) = in(s) ^ out(a)
∴ in(s) = out(s) ^ out(a)
∴ in(s..6) = out(s..6) ^ out(a..n)


// y = y ^ ((y << 15) & 4022730752)
// beginning with y ^ (y << 15)

  abcd efgh ijkl mnop qrst uvwx yz12 3456
  0000 0000 0000 0000 0000 0000 0000 0000
^ 0000 0000 0000 0000 0
  pqrs tuvw xyz1 2345 6

To figure out in(a..b) we need to XOR with in(p..q)

in(c..q) = out(c..q) ^ out(r..6)
in(a..b) = out(a..b) ^ in(p..q)

// so now the "& 4022730752"
this hides in values where 4022730752 has binary zeros:
1110 1111 1100 0110 0000 0000 0000 0000
pqrs tuvw xyz1 2345 6

in(s, z, 1, 2, 5) = 0
out(others) = in(others)

So we lose in(s, z, 1, 2, 5). I hope the last step will make those immaterial or we may
have to trial-improve the Mersenne generator and figure out the missing values.

// y = y ^ ((y << 7) & 2636928640)
// beginning with y ^ (y << 7)

  abcd efgh ijkl mnop qrst uvwx yz12 3456
  0000 0000 0000 0000 0000 0000 0000 0000
^ 0000 0000 0000 0000 0000 0000 0
  hijk lmno pqrs tuvw xyz1 2345 6

// so now the "& 2636928640"
this hides in values where 2636928640 has binary zeros:
1001 1101 0010 1100 0101 0110 1000 0000
hijk lmno pqrs tuvw xyz1 2345 6

out(i, j, n, p, q, s, v, w, x, z, 2, 5) = 0
out(others) = in(others)

So we lose in(i, j, n, p, q, s, v, w, x, z, 2, 5). Thats a lot of bits.

Since all operations following are bitwise, we can guarantee that some bits in the
later stages are zero, from this and the 4022730752 step.

It seems definite that we need to analyse the result of our partial reversal. We cannot
derive the internal state without looking into what is happening between inputs.

// y = y ^ (y >> 11)

  abcd efgh ijkl mnop qrst uvwx yz12 3456
  0000 0000 0000 0000 0000 0000 0000 0000
^              0 0000 0000 0000 0000 0000
               a bcde fghi jklm nopq rstu

in(a..k) = out(a..k)
in(l..v) = out(l..v) ^ in(a..k)
in(w..6) = out(w..6) ^ in(l..u)

// knit together

                11 1111 1111 2222 2222 2233
    0123 4567 8901 2345 6789 0123 4567 8901
    abcd efgh ijkl mnop qrst uvwx yz12 3456
1   1111 1111 1111 1111 1111 1111 1111 1111
2 ^                       ab cdef ghij klmn
3 ^ pqr0 tuvw xy00 0340 0
4 ^ h00k lm0o 00r0 tu00 0y01 0340 6
5 ^              a bcde fghi jklm nopq rstu

5->4    4(a..k) = 5(a..k)
        4(l..v) = 5(l..v) ^ 5(a..k)
        4(w..6) = 5(w..6) ^ 4(l..u)
4->3    3(1..6) = 4(1..6)
        3(b, c, g, i, j, l, o, p, q, s, u) = 4(b, c, g, i, j, l, o, p, q, s, u)
        3(t, v, w, y) = 4(t, v, w, y) ^ 3(1, 3, 4, 6)
        3(r) = 4(r) ^ 3(y)
        3(n) = 4(r) ^ 3(u)
        3(m) = 4(m) ^ 3(t)
        3(k) = 4(k) ^ 3(r)
        3(h) = 4(h) ^ 3(o)
        3(e, f) = 4(e, f) ^ 3(l, m)
        3(d) = 4(d) ^ 3(k)
        3(a) = 4(a) ^ 3(h)
3->2    2(r..6) = 3(r..6)
        2(d, k, l, m, p, q) = 3(d, k, l, m, p, q)
        2(n, o) = 3(n, o) ^ 2(3, 4)
        2(e..j) = 3(e..j) ^ 2(t..y)
        2(a..c) = 3(a..c) ^ 2(p..r)
2->1    1(a..r) = 2(a..r)
        1(s..6) = 2(s..6) ^ 1(a..n)