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

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

  4. I just stumbled in this thread, and frankly I cannot understand what all the fuss is about. You can do exactly the same with Melissa O’Neill’s PCG generators, as they are very easy to predict. The code below when executed and dumped in hex gives

        00000000  98 06 19 c7 65 5b ce 68  f2 41 47 84 50 cf ba fa  |....e[.h.AG.P...|
        00000010  a9 eb 2d 00 67 a3 34 af  5a e7 70 31 4b ae a3 38  |..-.g.4.Z.p1K..8|
        00000020  03 98 b2 b5 39 0d 05 e3  98 db 33 9f b7 d4 9d b7  |....9.....3.....|
        00000030  2c 29 12 34 52 66 ce b7  01 ca 96 3f f3 eb cf 7a  |,).4Rf.....?...z|
        00000040  d9 76 81 e9 36 e7 06 2b  c6 94 0c 66 d0 96 d6 82  |.v..6..+...f....|
        00000050  5f b1 c6 18 50 24 19 64  db 0a de 7b 27 28 ab 81  |_...P$.d...{'(..|
        00000060  0f 31 0b 5c 37 bd 10 ec  1e 04 da ae 18 ce 9d 4d  |.1.\7..........M|
        00000070  ff 5c fd 43 fd e6 24 70  23 94 8f 8b 41 0a 89 eb  |.\.C..$p#...A...|
        00000080  3e 20 4a 6f 68 6e 20 44  2e 20 43 6f 6f 6b 20 3c  |> John D. Cook <|
        00000090  03 f6 4e 49 4a 39 fa 15  e1 3c 9f e7 bc 78 a9 c0  |..NIJ9...<...x..|
        000000a0  ea ea e2 46 65 65 63 b5  81 1b 76 01 c9 28 8b 6d  |...Feec...v..(.m|
        000000b0  ec a2 0c a4 6b e1 33 d0  55 6f 8a db 49 73 a7 38  |....k.3.Uo..Is.8|
        000000c0  6d 33 8c 5b 9a 88 39 ff  70 90 ff 8f 5d 0a a6 75  |m3.[..9.p...]..u|
    

    The code is here (PCG generator + initial state):

        #include <stdio.h>
        #include <stdint.h>
        typedef __uint128_t uint128_t;
        // -------
        // PCG code Copyright by Melissa O'Neill
        typedef __uint128_t pcg128_t;
        #define PCG_128BIT_CONSTANT(high,low) ((((pcg128_t)high) <state = rng->state * PCG_DEFAULT_MULTIPLIER_128 + PCG_DEFAULT_INCREMENT_128;
        }
    
        static inline uint64_t pcg_output_xsh_rs_128_64(pcg128_t state) {
                return (uint64_t)(((state >> 43u) ^ state) >> ((state >> 124u) + 45u));
        }
    
        static inline uint64_t pcg_oneseq_128_xsh_rs_64_random_r(struct pcg_state_128* rng) {
                pcg_oneseq_128_step_r(rng);
                return pcg_output_xsh_rs_128_64(rng->state);
        }
    
        int main(int argc, char* argv[]) {
                struct pcg_state_128 rng;
                rng.state = (__uint128_t)0x216c549ced70826b << 64 | 0x1b900f7fadcc7c16;
                for(;;) {
                        uint64_t output = pcg_oneseq_128_xsh_rs_64_random_r(&rng);
                        fwrite(&output, sizeof(output), 1, stdout);
                }
        }
    

Comments are closed.