Manipulating a random number generator
With some random number generators, it's possible to select the seed carefully to manipulate the output. Sometimes this is easy to do. Sometimes it's hard but doable. Sometimes it's theoretically possible but practically impossible.
In my recent correspondence with Melissa O'Neill, she gave me an example that seeds a random number generator so that the 9th and 10th outputs produce the ASCII code for my name.
Here's the code. The function next is the xoroshiro128+ (XOR/rotate/shift/rotate) random number generator. The global array s contains the state of the random number generator. Its initial values are the seeds of the generator.
#include <cstdio>#include <cstdint>// xoroshiro generator taken from// http://vigna.di.unimi.it/xorshift/xoroshiro128plus.cuint64_t s[2];static inline uint64_t rotl(const uint64_t x, int k) {return (x << k) | (x >> (64 - k));}uint64_t next(void) {const uint64_t s0 = s[0];uint64_t s1 = s[1];const uint64_t result = s0 + s1;s1 ^= s0;s[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); // a, bs[1] = rotl(s1, 36); // creturn result;}int main() { freopen(NULL, "wb", stdout); s[0] = 0x084f31240ed2ec3f; s[1] = 0x0aa0d69470975eb8; while (1) { uint64_t value = next(); fwrite((void*) &value, sizeof(value), 1, stdout); }}
Compile this code then look at a hex dump of the first few outputs. Here's what you get:
cook@mac> gcc xoroshiro.cppcook@mac> ./a.out | hexdump -C | headf7 4a 6a 7f b8 07 f0 12 f8 96 e1 af 29 08 e3 c8 |.Jj.........)...|15 0e b0 38 01 ef b2 a7 bb e9 6f 4d 77 55 d7 a0 |...8......oMwU..|49 08 f2 fc 0c b2 ea e8 48 c2 89 1b 31 3f d7 3d |I.......H...1?.=|11 eb bc 5e ee 98 b6 3b d9 d1 cc 15 ae 00 fc 2f |...^...;......./|3e 20 4a 6f 68 6e 20 44 2e 20 43 6f 6f 6b 20 3c |> John D. Cook <| d1 80 49 27 3e 25 c2 4b 2a e3 78 71 9c 9e f7 18 |..I'>%.K*.xq....|0b bb 1f c6 1c 71 79 29 d6 45 81 47 3b 88 4f 42 |.....qy).E.G;.OB|7c 1c 19 c4 22 58 51 2d d7 74 69 ac 36 6f e0 3f ||..."XQ-.ti.6o.?|78 7f a4 14 1c bc a8 de 17 e3 f7 d8 0c de 2c ea |x.............,.|a2 37 83 f9 38 e4 14 77 e3 6a c8 52 d1 0c 29 01 |.7..8..w.j.R..).|
(I cut out the line numbers on the left side to make the output fit better horizontally on the page.)
Not only did one pair of seed values put my name in the output, another pair would work too. If you change the seed values to
s[0] = 0x820e8a6c1baf5b13;s[1] = 0x5c51f1c4e2e64253;
you'll also see my name in the output:
66 9d 95 fe 30 7c 60 de 7c 89 0c 6f cd d6 05 1e |f...0|`.|..o....|2b e9 9c cc cd 3d c5 ec 3f e3 88 6c a6 cd 78 84 |+....=..?..l..x.|20 12 ac f2 2b 3c 89 73 60 09 8d c3 85 68 9e eb | ...+<.s`....h..|15 3e c1 0b 07 68 63 e5 73 a7 a8 f2 4b 8b dd d0 |.>...hc.s...K...|3e 20 4a 6f 68 6e 20 44 2e 20 43 6f 6f 6b 20 3c |> John D. Cook <|3f 71 cf d7 5f a6 ab cf 9c 81 93 d1 3d 4c 9e 41 |?q.._.......=L.A|0d b5 48 9c aa fc 84 d8 c6 64 1d c4 91 79 b4 f8 |..H......d...y..|0c ac 35 48 fd 38 01 dd cc a4 e4 43 c6 5b e8 c7 |..5H.8.....C.[..|e1 2e 76 30 0f 9d 41 ff b0 99 84 8d c1 72 5a 91 |..v0..A......rZ.|06 ea f2 8e d7 87 e5 2c 53 a9 0c a0 f4 cd d1 9b |.......,S.......|
Note that there are limits to how much you can manipulate the output of an RNG. In this case the seed was selected to produce two particular output values, but the rest of the sequence behaves as if it were random. (See Random is as random does.)