PLAID CTF Crypto Challenge: 375pts

Challenge Description:

"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.

Stages to authenticate:

Solution Using Logic Bug:

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.

Steps to flag:

Solution Using Vulnerable RSA Implementation:

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:






Interesting Things:

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+48, and (M)256+49 for a rightmost '1'.

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