Powerball

Category: Crypto
Points: 200
Description: Introducing ångstromCTF Powerball, where the Grand Prize is a flag! All you need to do is guess 6 ball values, ranging from 0 to 4095. But don’t worry, we’ll give one for free!

Interesting RSA challenge which I liked. The premise of the challenge is that that server picks 6 numbers between 0-4095 and we have to guess them in order. Now if you wanna do that brute force aint gonna happen. But they do give us some interesting over info.

Firstly they give us n and e which are public key values for rsa:

n: 24714368843752022974341211877467549639498231894964810269117413322029642752633577038705218673687716926448339400096802361297693998979745765931534103202467338384642921856548086360244485671986927177008440715178336399465697444026353230451518999567214983427406178161356304710292306078130635844316053709563154657103495905205276956218906137150310994293077448766114520034675696741058748420135888856866161554417709555214430301224863490074059065870222171272131856991865315097313467644895025929047477332550027963804064961056274499899920572740781443106554154096194288807134535706752546520058150115125502989328782055006169368495301
e: 65537

Next lets take a look at the main code that we will be interested in.


def handle(self):
    self.write(welcome)
	balls = [getRandomRange(0, 4096) for _ in range(6)]
	x = [getRandomRange(0, n) for _ in range(6)]
	self.write('x: {}\n'.format(x).encode())
	v = int(self.query(b'v: '))
	m = []
	for i in range(6):
		k = pow(v-x[i], d, n)
		m.append((balls[i]+k) % n)
	self.write('m: {}\n'.format(m).encode())
	guess = []
	for i in range(6):
		guess.append(int(self.query('Ball {}: '.format(i+1).encode())))
	if balls == guess:
		self.write(b'JACKPOT!!!')
		self.write(flag)
	else:
		self.write(b'Sorry, those were the wrong numbers.')

So it firstly picks the 6 balls. Then 6 random numbers between 0 and n stores it in x and sends it to us.

Asks us for a value v

Then does some rsa stuff and sends us back m

SO it gives the hint that they let us have 1 ball number for free, and that makes sense if we can set k to 0 that means this line:

m.append((balls[i]+k) % n)

Would just return thhe balls[i] since it cannot be bigger than n. Now this works but it doesn’t help with the other 5 balls.

At this point I thought, well why did they give us the ‘e’ value then in the public key if it’s not being used in the code. Hmm, we need to do some decrypting. Now because of the relationship of d & e in rsa we can invoke this relationship

pow(m, d, n) = c
pow(c, e, n) = m

Which then it follows that in the calculation:

k = pow(v-x[i], d, n)
v - x[i] = pow(k, e, n)

We have all the other values in the second equation except for k and if we can get k we can work out the ball value from m as long as it is not bigger than n

m.append((balls[i]+k) % n)

So how do we work out what k is? Brute force 🙂 Since there is only 4096 values the ball can be we can then check if the k value matches the relationship in v – x[i] = pow(k, e, n) and if it does then wew we got the ball! If we don’t find one then we need to try again with another set of values

def calculateBalls(m, x, v):
    for i in range(4096):
        k = m - i
        if ( pow(k, e, n) == v - x):
            return i
    return -1

Now I just put this all together in a python script to automate the whole thing here:

from pwn import *

e = 65537
n = 24714368843752022974341211877467549639498231894964810269117413322029642752633577038705218673687716926448339400096802361297693998979745765931534103202467338384642921856548086360244485671986927177008440715178336399465697444026353230451518999567214983427406178161356304710292306078130635844316053709563154657103495905205276956218906137150310994293077448766114520034675696741058748420135888856866161554417709555214430301224863490074059065870222171272131856991865315097313467644895025929047477332550027963804064961056274499899920572740781443106554154096194288807134535706752546520058150115125502989328782055006169368495301


# Function to check all possible values of the ball
def calculateBalls(m, x, v):
    for i in range(4096):
        k = m - i
        if ( pow(k, e, n) == v - x):
            return i
    return -1

#Loop until we get the flag
while True:
    con = remote("54.159.113.26", 19001)
    
    # Get the x value array
    x = eval('[' + con.recvline_endswith(']').split('[')[1]) 
    
    con.recvuntil(':')
    
    # send the first value in the x array, not neccessary but yolo
    v = x[0]
    con.sendline(str(v))
    
    # get the returned m array
    m = eval('[' + con.recvline().split('[')[1])
    
    balls = []
    
    # check each value to try get the ball  values with x[i], m[i] and v
    for index, value  in enumerate(m):
        balls.append( calculateBalls(value, x[index], v))
    
    #Check if we got all the values
    print(balls)
    if -1 in balls:
        con.close()
        continue
        
    #send the ballllls    
    #con.interactive() 
    for i in range(6):
        con.recvuntil(':')
        con.sendline(str(balls[i]))
    
    con.interactive()
    
    #con.interactive()

Eventually you will get the flag 🙂

FLAG:

actf{no_more_free_oblivious_transfers}