CTF(x) 2016 - little crypto gambler (Crypto 150)


Challenge:

Challenge accepted! Here are the contents of gamble_server.py:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#/usr/bin/env python
from Crypto.Random import random, atfork
from Crypto.Util.number import *

import SocketServer,threading,os,time
import signal

from secret1 import FLAG

PORT = 3001

def isInt(x):
    try:
        int(x)
        return True
    except ValueError:
        return False

def createRandom():
    mbl = getRandomRange(65,100)
    m = getPrime(mbl)
    abl = getRandomRange(64,mbl)
    a = getPrime(abl)
    c = getRandomRange(0, m)
    s = getRandomRange(1, m)
    return Rand(m, a, c, s)

class Rand:
    def __init__(self, m, a, c, s):
        self.s = s
        self.a = a
        self.c = c
        self.m = m
    def next(self):
        self.s = (self.a*self.s+self.c)%self.m
        return self.s

class incoming(SocketServer.BaseRequestHandler):
    def handle(self):
        atfork()
        req = self.request

        def recvline():
            buf = ""
            while not buf.endswith("\n"):
                buf += req.recv(1)
            return buf
        signal.alarm(120)

        req.sendall("#############################\n")
        req.sendall("Welcome to the Gambling game!\n")
        req.sendall("#############################\n")
        req.sendall("\n")

        money = 20
        random = createRandom()
        while True:
            req.sendall("You currently have $%d\n"%money)
            req.sendall("How much would you like to bet?: \n")
            bet = recvline()
            if isInt(bet):
                bet = int(bet)
                if bet>=1 and bet<=money:
                    req.sendall("Guess a number!: \n")
                    guess = recvline()
                    if isInt(guess):
                        guess= int(guess)
                        rand = random.next()
                        if guess==rand:
                            req.sendall("You won the bet!\n")
                            money += bet
                            req.sendall("You now have $%d\n"%money)
                            req.sendall("\n")
                            if money>=10**6:
                                req.sendall("Wow! You're a millionaire!\n")
                                req.sendall(FLAG+"\n")
                            req.sendall("Would you like to play again? (Y/N): \n")
                            if recvline().strip()=="Y":
                                random = createRandom()
                                continue
                            else:
                                break
                        else:
                            req.sendall("You lost the bet!\n")
                            req.sendall("You should have guessed %d. :(\n"%rand)
                            money -= bet
                            if money==0:
                                req.sendall("You're all out of money! You lose!\n")
                                break
                            else:
                                req.sendall("Would you like to play again? (Y/N): \n")
                                if recvline().strip()!="Y":
                                    break
                    else:
                        req.sendall("Invalid input!\n")
                        break
                else:
                    req.sendall("Invalid bet!\n")
                    break
            else:
                req.sendall("Invalid input!\n")
                break
        req.sendall("Bye!\n")
        req.close()

class ReusableTCPServer(SocketServer.ForkingMixIn, SocketServer.TCPServer):
  pass

SocketServer.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", PORT), incoming)

print "Server listening on port %d" % PORT
server.serve_forever()

Here, we see that the server is using a Linear Congruential Generator (LCG) to generate the values which we must guess correctly. Each value of the LCG is generated by the equation s = a*s + c mod m. The crux of this challenge is obviously to break this deterministic LCG and win a million dollars.

After spending some time Googl-ing on how to break LCGs, I arrived at this article: http://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator. Essentially, it outlined the steps to deriving the modulo m used in the LCG using a list of sequential values generated by the LCG. The more values we have from the generator, the higher our chances of guessing m correctly. This probability of guessing the correct m increases exponentially with the number of values we have from the LCG. Here's the gist of the article:
To recover m, define tn = sn+1 - sn and un = |tn+2 tn - t2n+1|; then with high probability you will have m = gcd(u1, u2, ..., u10). 10 here is arbitrary; if you make it k, then the probability that this fails is exponentially small in k.
After we recover m, we can then solve for the other values a and c by using simple mathematics (taking the difference of two linear equations to solve for a, then solve for c using any linear equation). The procedures for deriving m, a and c are found in the following script (functions get_m, get_a and get_c respectively):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#!/usr/bin/env python

from pwn import remote, context
from gmpy import gcd, mpz, invert

class Rand:
 def __init__(self, m, a, c, s):
  self.s = s
  self.a = a
  self.c = c
  self.m = m
 def next(self):
  self.s = (self.a*self.s+self.c)%self.m
  return self.s

def play(r):
 r.recvlines(2)
 r.sendline('1')
 r.recvline()
 r.sendline('-1')
 r.recvline()
 n = r.recvline()
 val = n.split()[4][:-1:]
 r.recvline()
 r.sendline('Y')
 return int(val)

def play_winning(R, money):
 r.recvlines(2)
 r.sendline(str(money))
 r.recvline()
 ans = R.next()
 print ans
 r.sendline(str(ans))
 r.recvline()
 n = r.recvline()
 print n
 money = int(n.split()[-1][1::])
 r.recvlines(2)
 r.sendline('Y')
 return money

def gcd_list(list):
 return reduce(gcd, list)

def get_m(values):
 ts = []
 us = []
 for i in range(len(values)-1):
  ts.append(values[i+1]-values[i])
 for i in range(len(ts)-2):
  u = abs(ts[i+2]*ts[i] - ts[i+1]**2)
  us.append(mpz(u))
 return gcd_list(us)

def get_a(values, m):
 s1 = values[-3]
 s2 = values[-2]
 s3 = values[-1]
 return (s3-s2)*invert(s2-s1, m) % m

def get_c(s2, a, s1, m):
 return (s2 - (a*s1)) % m

def earn_money(n, money):
 values = []
 for i in range(n):
         values.append(play(r))
 m = get_m(values)
 a = get_a(values, m)
 c = get_c(values[-1], a, values[-2], m)
 R = Rand(m, a, c, values[-1])
 money -= n
 return play_winning(R, money)

r = remote('problems.ctfx.io', 7000)
r.recvlines(4)

money = 20
while money < 10**6:
 money = earn_money(9, money)

r.interactive()

Once we have the values s, m, a and c, we can feed these values into the state of a new LCG and predict the subsequent values of the LCG. Through trial-and-error, I found that having 9 values from the LCG is sufficient for me to confidently crack the internal states of the LCG. Since the LCG is changed after every win, I would have to lose 9 times to crack the new LCG before I can make another win again. I repeat this process until I win a million dollars.


ubuntu@ip-172-31-44-184:~$ ./solve_gambling.py
[+] Opening connection to problems.ctfx.io on port 7000: Done
265548323598859298228951
You now have $22

582594150210093906792577606
You now have $26

185307495524279141881747400
You now have $34

13490776267391019846212534902
You now have $50

45214055598801949350163676
You now have $82

95428133070001256857144
You now have $146

819952376328745222686
You now have $274

4120332492040394179954336
You now have $530

59976926929378774488325950
You now have $1042

57754657059890014411
You now have $2066

28562325926640009950908244985
You now have $4114

205565100739498863054029879
You now have $8210

114243976780970982998268516
You now have $16402

28995781959247438092214280
You now have $32786

6724874612108703528021095299
You now have $65554

20215947640690481057710033
You now have $131090

150546913020991016592524
You now have $262162

35456704237120406328565
You now have $524306

1367734563475682188570698452
You now have $1048594

[*] Switching to interactive mode
ctf(cr4cking_LCGs_4_fun_&_prof1t)

WooohoooO! We win! =)

Comments

Post a Comment