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.c

uint64_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, b
	s[1] = rotl(s1, 36); // c

	return 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.cpp
cook@mac> ./a.out | hexdump -C | head
f7 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.)

3 thoughts on “Manipulating a random number generator

  1. Extremely fascinating! But – no mention of how Melissa O’Neill determined which seed value would find your name. Did she brute force test? Or did she exploit some weakness in the algorithm?
    Inquiring minds need to know!
    Thanks,
    Tom

  2. A new paper out today by David Blackman & Sebastiano Vigna discusses the development of xoroshiro and introduces a new generator called xoshiro. For details please see http://xoshiro.di.unimi.it/

    xoshiro256** is a 64-bit generator with 256 bits of state and is 4-dimensionally equidistributed, so that every possible 32-byte sequence of four consecutive outputs occurs exactly once, except for all zeroes.

  3. John asked me to revisit this thread and comment. We can do the same thing with the brand new xoshiro256** PRNG. If we initialize the s[] array with { 0x73b024a52ec6c93b, 0xd086c84736eb5d51, 0x2d95409b286447ce, 0xfb74008d8c5e46a8 }, we get the following output:

    00000000  d1 9e b3 af 53 42 9a d8  84 ed 19 7d be a6 a8 62  |....SB.....}...b|
    00000010  9c 6d 9e 25 21 d5 80 87  e1 82 bd 08 54 f6 65 c0  |.m.%!.......T.e.|
    00000020  b1 cc f1 d0 1e a1 76 27  1d 75 3f 7e 60 1b 40 40  |......v'.u?~`.@@|
    00000030  04 1b 93 d4 5b 3a fa 49  a4 05 63 80 0f 12 b1 a8  |....[:.I..c.....|
    00000040  f5 bf 62 7c 01 89 1a 01  e8 22 78 1e e8 d8 80 0b  |..b|....."x.....|
    00000050  06 b3 00 32 8c 15 da 87  df 51 66 e1 d4 ee 96 51  |...2.....Qf....Q|
    00000060  68 bf 46 df 4b ae 88 ad  a5 4b 0d 23 1a 9c 37 ef  |h.F.K....K.#..7.|
    00000070  5b 61 5d 4b 53 77 19 3e  e0 3a 8e b1 ba 77 22 7d  |[a]KSw.>.:...w"}|
    00000080  3e 20 4a 6f 68 6e 20 44  2e 20 43 6f 6f 6b 20 3c  |> John D. Cook <|
    00000090  3e 20 20 43 6f 6e 73 75  6c 74 69 6e 67 20 20 3c  |>  Consulting  <|
    000000a0  a0 f0 1a 0a d1 9d 0c 77  56 23 b6 ce cd c8 59 cf  |.......wV#....Y.|
    000000b0  ee 53 75 f0 a5 50 df 3f  90 8d 88 32 e8 e7 6f ec  |.Su..P.?...2..o.|
    000000c0  34 e1 ec b7 40 af 19 82  eb d6 c1 b6 92 b2 0b 87  |4...@...........|
    000000d0  dc 36 85 b5 00 c3 af 8c  76 29 2a b4 b1 f4 94 cc  |.6......v)*.....|
    000000e0  1d 71 d8 b7 19 11 6d 1a  d9 e5 b5 84 e6 fa c1 43  |.q....m........C|
    000000f0  18 f3 08 10 4a fe af af  81 71 cb 30 70 4b dd 87  |....J....q.0pK..|
    

    [You may have to scroll to the right to see, but Melissa has seeded the generator so it will output my company name. — John]

    We can do this because, like its predecessor, xoshiro256** is trivially predictable. After observing exactly four outputs we can determine prior outputs and predict all future outputs.

Leave a Reply

Your email address will not be published. Required fields are marked *