Forum Update - Announcement about May 10th, 2018 update and your password.

Some fun with xorshiro.

This is fun. Let's run the xoroshiro128 pseudo random number generator with some 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

  • 14 Comments sorted by Date Added Votes
  • Are those really sequences from the PRNG?
  • cgracey wrote: »
    Are those really sequences from the PRNG?

    They are real sequences from xoroshiro128+. We can get many four-character ASCII sequences with XORO32. I mentioned this is October and nobody noticed:
    TonyB_ wrote: »
    All of them, but let's put this to one side for a while. Try doing a hexdump of the first few Xoroshiro32+ sums (eight is plenty) when seed is $32F3_1EDB :)

    That seed is wrong now as XORO32 has changed.
    Formerly known as TonyB
  • To find a seed which yields a 16-character sequence of readable text seems quite unlikely, doesn't it?
  • Heater.Heater. Posts: 20,842
    edited January 29 Vote Up0Vote Down
    @Chip,

    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?







  • Chip,
    To find a seed which yields a 16-character sequence of readable text seems quite unlikely, doesn't it?
    Turns out it trivially easy to find such a seed for a given 16 character string. Although not all 16 character strings are possible.

    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.




  • Wouldn't 'Is this RANDOM?!' be just as random as any other sequence? I'm thinking of 10 thousand monkeys banging away on 10 thousand typewriters. Eventually there will be something produced that humans would consider not random.

    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
    Infantryman's Axiom; Always cheat, always win.
  • Alexander,

    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.

  • The only thing that makes this reasonably possible is the fact that xoroshiro128 outputs 8 bytes per iteration, or 8 whole characters.
  • TonyB_TonyB_ Posts: 581
    edited January 29 Vote Up0Vote Down
    It's just a trick that looks impressive because of the 64-bit output from xoroshiro128+. Every possible 8-byte string occurs 2^64 times due to equidistribution, except for all zeros. The probability of any two particular strings in sequence is fairly good - some pairs never occur, while others happen once or just a few times.

    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.
    Formerly known as TonyB
  • It's a trick. That looks impressive.

    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?
  • I was just reading Melissa's paper "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation". She talks about how this party trick can be done in section 4.3.3 Party Tricks.

    http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
  • This should be possible with any PRNG having a big enough radix and that you can walk backwards. But if you can't walk it backwards, that likely implies a many-to-one transformation from one iteration to the next, which would shrink the space of possible outcomes from the PRNG.

    So the trick is to come up with a one-to-one transformation that's irreversible. I seriously doubt that one exists.

    -Phil

    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Heater.Heater. Posts: 20,842
    edited January 29 Vote Up0Vote Down
    I have no idea.

    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.

Sign In or Register to comment.