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:

• Vals: 11000710321405755819, 15528335171484875594 (Hack with “bill buchanan”). Try;
• Vals: 4631302920610762569, 9029862388220783183 (Hack with “aa..aaa”). Try;
• Vals: 7889442131011666962, 17198922559134839433 (Hack with “happy xmas”). Try;