Some fun with xorshiro.
Heater.
Posts: 21,230
in Propeller 2
This is fun. Let's run the xoroshiro128 pseudo random number generator with some random seed:
Hmm... that's odd. Let's try another random seed:
linux$ ./xoroshiro128 0xeded4ad7b1328220 0x9824332f9806fb61 | hexdump -Cv | head 0000 81 7d 39 49 07 7e 11 86 82 3f 54 b9 27 19 09 cf |.}9I.~...?T.'...| 0010 42 f2 46 d0 f9 29 8e 2f ae 21 ec fa 3e f1 55 ad |B.F..)./.!..>.U.| 0020 be 8e 37 90 c6 c3 8e c4 d3 c4 65 2c c9 69 8e 85 |..7.......e,.i..| 0030 5b e9 9d f0 43 a1 fe 3e 19 16 d7 eb e7 06 53 cf |[...C..>......S.| 0040 49 73 20 74 68 69 73 20 52 41 4e 44 4f 4d 3f 21 |Is this RANDOM?!| 0050 aa f5 1a 79 59 99 9f 7e 73 a4 9d 20 af 3d 93 75 |...yY..~s.. .=.u| 0060 da 3a f4 08 50 0f 53 8d e8 7d 20 08 fc 6b 44 94 |.:..P.S..} ..kD.| 0070 19 43 9b c5 63 e7 84 b6 18 bf a0 bb ca 0f e6 27 |.C..c..........'| 0080 1f c0 74 58 16 e9 23 da 96 33 82 b7 05 7e a0 5e |..tX..#..3...~.^| 0090 65 f0 e5 d5 b1 60 6a 17 3d 3c bd d1 9b 5e 2d 0b |e....`j.=<...^-.|
Hmm... that's odd. Let's try another random seed:
linux$ ./xoroshiro128 0x0b5ba189aff00348 0x6d02f8f46aee8642 | hexdump -Cv | head
0000 8a 89 de 1a 7e 9a 5e 78 e7 94 21 06 91 d6 eb e5 |....~.^x..!.....|
0010 f5 43 b9 09 46 93 59 07 71 11 af 07 35 4b cf a6 |.C..F.Y.q...5K..|
0020 9d a0 a5 7f 57 13 7c 96 34 27 cd 80 35 00 15 a7 |....W.|.4'..5...|
0030 e1 26 65 d6 0a 1d 34 1f cc 87 d7 66 4c 94 ab 8e |.&e...4....fL...|
0040 49 74 27 73 20 64 61 72 6b 2f 73 74 6f 72 6d 79 |It's dark/stormy|
0050 2f 1d be cb 66 79 a5 36 d5 bf 9f c6 c5 6a 2f 57 |/...fy.6.....j/W|
0060 29 65 b6 a3 f9 06 da f8 40 e9 ca 98 de e9 04 29 |)e......@......)|
0070 09 b2 7b d6 c2 9f ef 05 b1 e1 ca e9 5c d9 b9 ba |..{.........\...|
0080 90 c9 81 54 1b 2e ca de c8 b3 7a e4 3c f2 7b c4 |...T......z.<.{.|
0090 f0 e0 ae c0 18 c0 58 05 d8 28 6b f3 af 8f 23 ff |......X..(k...#.|
What?!
Comments
They are real sequences from xoroshiro128+. We can get many four-character ASCII sequences with XORO32. I mentioned this is October and nobody noticed:
That seed is wrong now as XORO32 has changed.
Yep. Output from the actual xorshiro128+.
@TonyB_
Getting sequences of 4 ASCII characters from any random source does not seem like it should be unusual to me.
Question is, can you create the seeds to get the text you want?
https://github.com/lemire/crackingxoroshiro128plus
&clk?
rjo__ is on to it.
The point is that given two outputs of xoroshiro128 it's trivially easy to find out the state of the PRNG and hence know what is coming next in the sequence.
Of course none of this fun is any of my doing. Melisa O'Neill, creator of the PCG PRNG, shows how to do it in a blog post I just stumbled across: http://www.pcg-random.org/posts/predictability-party-tricks.html
Which is fun or distressing. Depending what you expect from a PRNG.
How many sequences would I have to try before I got a result that was meaningful, and timely, for me?
This post and the rest of this thread could be considered to be random. Depends on your definition of random. Chaos is just a higher form of order.
Sandy
You are right. A random process, like all those monkeys, will occasionally produce what looks like sensible text to us.
The point here is a bit different though. Here we are talking about a pseudo random number generator. That is to say an algorithm designed to produce a random looking sequence that is not actually random at all.
The big point here is that for some PRNGs it is trivially easy to determine what is coming next in the sequence given just two outputs of the sequence. For other PRNG's it is very hard.
The little party trick I presented here is a symptom of the predictivity of the xorshiro algorithm. Being able to create a seed to get a desired output is using that predictably in reverse.
With XORO32 the output from each iteration is only two bytes, but with a double-iteration we get four bytes in one go. I wrote a program in assembly language to find the seed, if it exists, for any four-character sequence. I did it late at night using brute-force so I didn't have to think and it worked very well, but I can't get it going today. Also, XORO32 has changed as mentioned before, although that hasn't affected the equidistribution of the output. Sometimes five text characters in a row are possible, the last one being pure luck.
The Python script referred to above seems to using a solver to solve two simultaneous equations.
It's a trick you cannot do easily with some other PRNGs. Like PGC.
You can't do it at all with cryptographically secure PRNGs.
Only question is: Does this predictivity weakness matter for a particular application?
http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
So the trick is to come up with a one-to-one transformation that's irreversible. I seriously doubt that one exists.
-Phil
You cannot walk PGC backwards exactly. You can jump it forwards. Given that these things repeat after some cycle length you can just jump far enough head that you end up behind yourself. If you see what I mean.
The simple PGC has a 64 bit state but only a 32 bit output. There is a one-to-one transformation on the state at each step. But there is a many-to-one transformation from the state to the the output. That shrinks the number of possible outcomes from 2 to the power 64 down to 2 to the power 32. But the cycle length is still 2 to the power 64.
You have to do this really. If a PRNG could only produce every possible output value once in any batch of output that would not look very random and it would fail statistical testing.
Also, outputting the entire state at each step would make it trivially predictable.
Minimal code is here: http://www.pcg-random.org/download.html
Sadly it has that big 64 bit multiply in it which makes it very Prop unfriendly.