PlaidCTF 2015 – Crypto/Parlor2

After going bankrupt last year, the folks behind parlor from last year have decided to set up a new betting service!
PlaidCTF 2015 – Crypto/Parlor2

We were given a gambling application where we could choose some modulus [latex] \text{mod }o[/latex]. This modulus would be used by the server to compute a random number [latex] r (\text{mod }odds)[/latex], which we have to guess over 100 tries. Each guess has to be accompanied by some bet $[latex]b[/latex]. For every correct guess, we were awarded [latex] odds\times b[/latex]. We were given $[latex]100[/latex] and to win the flag, we need to accumulate 1 billion dollars.

Upon inspection of the server code provided, this is the general game flow:

Generate some DSA key pair for communicating with the server.
Encrypt our DSA public key using the provided server RSA public key.
Send the RSA-encrypted DSA public key.
Send some bet amount $[latex]b[/latex], which can be our total accumulated amount at most.
Send the “bet odds” [latex]odds[/latex], which is the modulus for the server-generated random number [latex]r[/latex].
Encrypt a guess [latex]g[/latex] using an RSA public key from a key pair that we generate. Guesses are of the form “I hereby commit to a guess of g“
Sign the guess [latex]g[/latex] using our DSA private key.
Send the encrypted guess and the guess signature.
The server invokes self.verify_guess to check that the DSA signature of the encrypted guess is valid and stores the encrypted guess in self.enc_guess.
We receive the random number [latex]r[/latex] generated by the server using os.urandom(5).
Send the corresponding RSA private key to decrypt the encrypted guess that we sent in step 8.
If the decryption in step 11 fails, the game terminates.
If [latex]r\equiv g^\prime (\text{mod }odds)[/latex], where [latex]g^\prime[/latex] is the decrypted guess, then we win $[latex](odds\times b)[/latex]. Otherwise, we lose $[latex]b[/latex].
Repeat from step 4, for a maximum of 100 times.

The main thing to note here is step 6 and 11: we can generate any RSA public/private key pair to encrypt our guess. If we set our modulus to [latex]odds=2[/latex], then we have two possible plaintexts “I hereby commit to a guess of 0/1“. Can we find some ciphertext [latex]c[/latex] and two different RSA private keys [latex]d_1\neq d_2[/latex] such that when we receive the random number [latex]r[/latex] from the server, we send the corresponding private key [latex]d[/latex] so that RSA decryption [latex]c^d[/latex] gives the plaintext that containing the correct guess for [latex]r (\text{mod } odds)[/latex]?

Since we have only two relatively short plaintexts and we control the RSA keypair generation, it was rather straightforward to perform the following:

Search for a modulo [latex]m[/latex] such that we can find all prime roots to [latex]m[/latex] easily, for some sufficiently large [latex]m[/latex] (greater than both plaintexts)
Generate a ciphertext that is padded with null bytes to match the size of [latex]m[/latex].
Find [latex]d[/latex] for the first plaintext by solving the discrete logarithm in a brute-force manner.
Repeat step 3 for the second plaintext.

For step 3, we brute-force the exponent as such:

def dlp_brute(x, y, modulus, primes):
  prime_prod = int(np.prod(primes))
  candidates = list()
  for p in primes:
    candidate = None
    try_exp = prime_prod/p
    try_x = pow(x, try_exp, modulus)
    try_y = pow(y, try_exp, modulus)
    for exponent in range(p):
      if pow(try_x, try_y, modulus) == try_y % modulus:
         candidate = exponent
         break
    if candidate:
      candidates.append(candidate)
  return chinese_remainder(candidates, primes)

def chinese_remainder(cd, pr):
  cd_prod = int(np.prod(cd))
  sum = 0
  for i in range(len(cd)):
    x = cd_prod/pr[i]
    sum += a[i] * inverse_modulo(x, pr[i]) * x
  return sum % cd_prod

def inverse_modulo(x, modulus):
  return extended_euclidean_gcd(x, modulus)[1]

def extended_euclidean_gcd(a, b):
  x = s1 = 1
  y = r1 = 0
  while b:
    integ, fract = a / b, a % b
    r2 = x - integ * r1
    s2 = y - integ * s1
    a, b = b, fract
    x, y, r1, s1 = r1, s1, r2, s2
  return a, x, y

We encrypt using a null byte and pad the plaintext with OAEP:

key = RSA.construct(long(N), 1L, 1L, 0L, 0L)
rsa = PKCS1_OAEP.new(key)
ciphertext = rsa.encrypt(c)
y = Crypto.Util.number.bytes_to_long(ciphertext)

then we brute force the exponent using dlp_brute(x, y, n, possible_primes). If d and n-1 are coprime (that their gcd is 1), then we can compute the corresponding e by

e = inverse_modulo(d, n - 1) % (n - 1)

This gives us two keypairs (each with [latex]d, e, n[/latex]), each corresponding to a guess of 0 or 1. We observe the random value sent by the server and determine which guess do we need to win, and we send that corresponding private key. In this manner, we can bet the maximum amount of money every time since we are guaranteed to win. This allows the server to successfully decrypt the ciphertext we sent earlier and pass the guess check, giving us the flag:

Holy shit you have a lot of money. Here's a flag: 'i_think_casinos_are_kinda_dumb'

Note: To use the application, we had to first generate a DSA public/private key pair and encrypt the DSA public key with the server’s public RSA key. The format of the DSA public key had to be in the format that was expected by pycrypto‘s DSA.construct(), which is a string with parameters in the order y, g, p, q, delimited by a comma ‘,‘.

from socket import socket
from Crypto.PublicKey import DSA, RSA
from Crypto.Cipher import PKCS1_OAEP

_server_pub_enc = RSA.importKey('-----BEGIN PUBLIC KEY-----\nMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDGRrsdIqf8K39Ncwzsi9k2lr5G\nJ8aEFkYGrYqOQRbU5xOReMj8wWHgnSUC0fjH0gjffGiUC2HfrrNIQvXKGiSBetOu\nIWOmFiESG8IhrPyvLwX53NbMWeCihzbYGJxGyiL0bvDHxqDxzuvteSaEfNm1miPA\nQ9rs5vFnHM0R3kFjdQIDAQAB\n-----END PUBLIC KEY-----')
server_pub_enc = PKCS1_OAEP.new(_server_pub_enc)
server_pub_sig = DSA.construct([6492988819243051335053735606322819439099395961135352303030066825351059776939776358522765113843576255727411249922052441719518573282010295240606387519552263L,5720927070571587652595864015095152811124313453716975619963331476834195150780326792550956895343289380256771573459290257563350163686508250507929578552744739L,6703916277208300332610863417051397338268350992976752494932363399494412092698152568009978917952727431041521105933065433917303157931689721949082879497208537,1022875313346435070370368907571603203095488145799L])

conn = socket()
conn.connect(('52.6.11.111', 4321))
conn.recv(4096) # parlor2 banner
server_dsa = conn.recv(4096)

dsa = DSA.generate(1024)
dsa_pub = ','.join([str(x) for x in [dsa.publickey().y, dsa.publickey().g, dsa.publickey().p, dsa.publickey().q]])

server_rsa_bytes = _server_pub_enc.size()/8
sha1_bytes = 160/8
server_rsa_oaep_chunk_bytes = server_rsa_size - sha1_bytes*2 - 2
encrypted_dsa_pub_chunks = list()
for i in range(0, len(dsa_pub), server_rsa_chunk_size):
    encrypted_dsa_pub_chunks.append(server_pub_enc.encrypt(dsa_pub[i:i+server_rsa_chunk_size).encode('hex'))
conn.send('.'.join(encrypted_dsa_pub_chunks) + '\n')

Leave a Reply Cancel reply