"After going bankrupt last year, the folks behind parlor from last year have decided to set up a new betting service!" The challenge presented the user with a gambling application which allowed you to choose an 'order' N. The user made a guess, then the server calculated
(random #)mod(N). If your guess was right you won money, after getting enough, you got the flag.
There were two solutions to this challenege.
(Python scripts for server and client linked at the bottom.)
1) Logic bug in the server code (unintended solution?)
2) Find the vulnerability in the RSA implementation
For both solutions you had to write a client to authenticate with the server.
from Crypto.PublicKey import RSA, DSA from Crypto.Cipher import PKCS1_OAEP from socket import socket
_server_pub_enc = RSA.importKey('-----BEGIN PUBLIC KEY-----####-----END PUBLIC KEY-----') server_pub_enc = PKCS1_OAEP.new(_server_pub_enc) server_pub_sig = DSA.construct([###,###,###,###])
generate your own DSA key pair & encrypt that with server_pub_enc
dsaKey = DSA.generate(1024) dsaStr = ",".join(map(str, (dsaKey.publickey().y, dsaKey.publickey().g, dsaKey.publickey().p, dsaKey.publickey().q))) rsaSize = _server_pub_enc.size() rsaChunkSize = 128-2-40 encoded = ",".join([server_pub_enc.encrypt(dsaStr[i:i+rsaChunkSize]).encode('hex') for i in range(0, len(dsaStr), rsaChunkSize)]) conn.send(encoded+"\n")
The first vuln: Now you're authenticated, send the server the 'order' it should use as the modulus. You can either always send a '1' so the number to guess will always be a 0 or send a '2' so the number to guess will always be either 1 or 0. This makes gambling easier, but you don't get any money as it would cyclically subtract - turns out gambling isn't that easy. Choose order of 2 and be right only 50% of the time, but accumulate some money.
if self.monies >= 1000000000: self.request.send("Holy shit you have a lot of money. Here's a flag: XXXXXXXXXXXXXXX\n")
r = int(os.urandom(5).encode("hex"),16) if self.guess == r%o: self.request.send("Congratulations! You have won $%d!\n"%(o*m)) self.monies += o*m
If you choose an order of '1' so you can guess right 100% of the time, you don't end up with any money. We chose an order of '2'. The server notifies the player that he cannot bet more than he has (i.e. $100) - however the server fails to stop the player from betting that much or checking if
current_money - bet < 0.
self.request.send("How much money would you like to bet?(You have $%d)\n"%self.monies) m = getn(self.request) if m > self.monies: self.request.send("You don't have that much money...\n") if m < 0: self.request.send(" :| \n") return 0 else: break self.monies -= m
Steps to flag:
Using an 'order' of '2' you can guess with a 50% certainty that the
(random #)mod(N) will be either a 0 or a 1. Initially, you send the server an encrypted guess which is decrypted after the server sends you the random number it chose.
For decryption, the server requests a private key (an RSA N and d) to recover your origional guess. Therefore you must choose a cipher text such that for different private key pairs
(N,d,e) the server will decrypt your ciphertext to recover one of two plaintexts.
m0 = "I hereby commit to a guess of 0"
m1 = "I hereby commit to a guess of 1"
Steps to flag:
\x00to size of N
(d,e)pairs for each message using the prime roots and discrete log brute force
(d,e)pair which cooresponds to the result of the modulus
INTENDED SOLUTION SCRIPT
cryptoDSA sophia$ sage solv.py Congratulations! You have won $2000000000! Holy shit you have a lot of money. Here's a flag: 'i_think_casinos_are_kinda_dumb' How much money would you like to bet? (You have $1000000100)
The decimal representation of m0 and m1 were 1 apart. Also a '0' would give the same result as '000', the same is true for '1' and '00001'. Each addition of this padding (leading '0's) resulted in the decimal equivalent of
(M)256+49 for a rightmost '1'.
sage: int("I hereby commit to a guess of 0".encode('hex'),16) 129203506129973995043701291062067805528377916943475206639318379866075045936L sage: int("I hereby commit to a guess of 1".encode('hex'),16) 129203506129973995043701291062067805528377916943475206639318379866075045937L
Initially, I tried using this padding to see if an N could be chosen such that an m0 with arbitrary padding could wrap around N, d times to result in
dec(m0)+1 or a
dec(m1). Problem with this is if N is constructed as a function of a padded m0, the roots of N are still unknown (given the addition of 48). This makes calculating
phi(N) in order to compute
ed = 1mod(phi(N)) equivalent to solving the discrete log problem - clearly not the indtended solution :P