# AlexCTF: CR5: Bring weakness - 300 pts

Get random numbers

# cat get.py 
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

r = remote(host, port)

for i in xrange(4):
 print give_me_the_next_number()

r.close()
# python get.py
855109115
895402096
2391280583
300480802

Linear congruential generator

random_n+1 = ((a * random_n) + c) % m
a = multiplier
c = increment
m = modulus

Get modulus

# cat get_modulus.py
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

def egcd(a, b):
 if a == 0:
  return (b, 0, 1)
 else:
  g, y, x = egcd(b % a, a)
 return (g, x - (b // a) * y, y)

results = []

for i in xrange(20):
 r = remote(host, port)
 last = give_me_the_next_number()
 current = give_me_the_next_number()
 tn = current - last
 last = current
 current = give_me_the_next_number()
 tn1 = current - last
 last = current
 current = give_me_the_next_number()
 tn2 = current - last
 u = abs(tn2*tn - tn1**2) # Important
 r.close()
 results.append(u)

print results

for i in xrange(0, 19):
 print egcd(results[i], results[i+1])[0]

# python get_modulus.py
[312571317250000395, 2949916660717308525, 640738713015133065, 435603004762385760, 2439656571633178950, 11411209872061185300L, 6407385815891338380, 610020832043386185, 1779427408702485555, 149150577634188375, 3371733426053132880, 402697709832197265, 2394242682672509175, 854013216788180865, 829159057095801915, 2030937970488420525, 9719562562552278360L, 4544082617950022895, 157160975107204845, 5385743285459484420L]
12884901885
12884901885
4294967295
8589934590
42949672950
17179869180
4294967295
4294967295
4294967295
4294967295
4294967295
4294967295
55834574835
4294967295
30064771065
4294967295
12884901885
244813135815
12884901885

Modulus = 4294967295 == 2**32 -1

Solve the equation with Wolfram Alfa and get (a, c)

r0 = 855109115
r1 = 895402096
r2 = 2391280583
r3 = 300480802
m = 4294967295
r1 = ((a*r0) + b) mod m
r2 = ((a*r1) + b) mod m
r3 = ((a*r2) + b) mod m

a = 6771334847
c = 6621298821

Get the flag

# cat get_flag.py
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

def guess_the_next_number(number):
 next = lcg(number)
 r.sendlineafter('2: Give me the next number\n', '1')
 r.sendlineafter('Next number (in decimal) is\n', str(next))
 return next

def lcg(seed):
 a = 6771334847
 c = 6621298821
 m = 4294967295
 return ((seed * a) + c) % m

r = remote(host, port)

seed = give_me_the_next_number()

for i in range(10):
 print seed
 seed = guess_the_next_number(seed)

print r.recvline()
r.close()

# python get_flag.py
604672456
322278383
3842182927
2626463750
2042127376
830485493
3402655117
2936071940
3380135806
3463756493
flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}

References

https://en.wikipedia.org/wiki/Linear_congruential_generator
http://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator