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.)
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
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.
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:
[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.
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); } }