Writing Your Name in the Sand: A Magic Trick With Random Numbers
In random number generation, we need to make sure that every single random value produced is equally probable. If not, we can gain an advantage in having a higher chance of predicting future values. Much of this relates to how random the seed value is for the random number generator algorithm. For example, we could have a random number generator that took the square of a running value and then took a modulo of M:
This is the Blum Blum Shub method [here], and where M=pq. Overall, p and q are prime numbers, and where p = 3 (mod 4) and q= 3 (mod 4). An example is:
>>> p=7
>>> q=11
>>> M=p*q
>>> x0=5
>>> x1=(x0**2)%M
>>> x2=(x1**2)%M
>>> x3=(x2**2)%M
>>> x4=(x3**2)%M
>>> print (x1,x2,x3,x4)
25 9 4 16
And so, if we can get an edge on the creation of the random number, we could end up millionaires. Thus, our random numbers should not really leak any information back on the seeds that we have used to generate the numbers. Otherwise, an adversary could guess how they were generated and perhaps guess future ones.
Well, let’s look at a random number generator and see if we can hack it.
Xoroshiro128+
Xoroshiro128+ is one of the fastest Pseudorandom number generators (PRNGs). It was created in 2016 by David Blackman and Sebastiano Vigna and requires two 64-bit unsigned integers as seeds [sample run]:
Seed 1: 74254124354025
Seed 2: 74398021324531
0 0x8732c65698dcL '\xdc\x98V\xc62\x87'
1 0x5f111e6e4815f86L '\x86_\x81\xe4\xe6\x11\xf1\x05'
2 0xc6f92404ee3bbe46L 'F\xbe;\xee\x04$\xf9\xc6'
3 0x4e6fb549d473d685L '\x85\xd6s\xd4I\xb5oN'
4 0xb8d3732bf3fc92ceL '\xce\x92\xfc\xf3+s\xd3\xb8'
5 0x584ddf04552308daL '\xda\x08#U\x04\xdfMX'
6 0x5b25d45d6350e6a8L '\xa8\xe6Pc]\xd4%['
7 0x9dd6e25a5f4c2964L 'd)L_Z\xe2\xd6\x9d'
8 0x4c3b9cfaff5d8368L 'h\x83]\xff\xfa\x9c;L'
9 0xb49f882106f12258L 'X"\xf1\x06!\x88\x9f\xb4'
And so we take two random seed values, and can then produce a random sequence. The code is here:
But, watch, I can determine some random messages [here]:
Seeds (12367730189591718825, 18127581570428703238)
0 0xa7351c7982cf3daf '¯=Ï\x82y\x1c5§'
1 0x656c707041206e41 'An Apple'
2 0x7961442041 'A Day'
3 0xb2f3ab65f678cf83 '\x83Ïxöe«ó²'
4 0x473c44a6c92818b7 '·\x18(ɦD<G'
5 0xd632d96cc745bd4a 'J½EÇlÙ2Ö'
6 0x4266815dbc316054 'T`1¼]\x81fB'
7 0xbe92a8de48abd944 'DÙ«HÞ¨\x92¾'
8 0x48183e8df662ee45 'Eîbö\x8d>\x18H'
9 0x66c9ff1266a00f05 '\x05\x0f\xa0f\x12ÿÉf'
The code-cracker uses the Microsoft Z3 library:
import z3
import binascii
# Code derived from https://gist.github.com/karanlyons/805dbcc9e898dbd17e06f2627d5f9111
def bin2chr(data):
result = ''
while data:
char = data & 0xff
result += chr(char)
data >>= 8
return result
class Xoroshiro128Plus(object):
def __init__(self, seed):
self.seed = seed
@staticmethod
def rotl(x, k):
return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)
def next(self):
s0 = self.seed[0]
s1 = self.seed[1]
result = (s0 + s1) & 0xffffffffffffffff
s1 ^= s0
self.seed[0] = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
self.seed[1] = self.rotl(s1, 36)
return result
def sym_xoroshiro128plus(solver, sym_s0, sym_s1, mask, result):
s0 = sym_s0
s1 = sym_s1
sym_r = (sym_s0 + sym_s1)
condition = z3.Bool('c0x%0.16x' % result)
solver.add(z3.Implies(condition, (sym_r & mask) == result & mask))
s1 ^= s0
sym_s0 = z3.RotateLeft(s0, 55) ^ s1 ^ (s1 << 14)
sym_s1 = z3.RotateLeft(s1, 36)
return sym_s0, sym_s1, condition
def find_seed(res_masks):
start_s0, start_s1 = z3.BitVecs('start_s0 start_s1', 64)
sym_s0 = start_s0
sym_s1 = start_s1
solver = z3.Solver()
conditions = []
for result, mask in res_masks:
sym_s0, sym_s1, condition = sym_xoroshiro128plus(solver, sym_s0, sym_s1, mask, result)
conditions.append(condition)
if solver.check(conditions) == z3.sat:
model = solver.model()
return (model[start_s0].as_long(), model[start_s1].as_long())
else:
return None
word1=b"An Apple"[::-1]
word2=b"A Day"[::-1]
val1=binascii.hexlify(word1)
val2=binascii.hexlify(word2)
print(val1)
print(val2)
val1=int.from_bytes(word1,byteorder='big')
val2=int.from_bytes(word2,byteorder='big')
print ("Solving ...")
res=find_seed([(0x0, 0x0), (val1, 0xffffffffffffffff),(val2, 0xfffffffffffffffff)])
print ("Seeds",res)
generator = Xoroshiro128Plus([res[0],res[1]])
for i in range(10):
val=generator.next()
print (i,hex(val),'\t',repr(bin2chr(val)))
Conclusions
Can you generate your own name in Xoroshiro128+? Here’s mines:
If you want to try a few, they are here: