Boston Key Party CTF 2017: RSA Buffet Solver

solve.py

from secretsharing import PlaintextToHexSecretSharer as SS
from Crypto.PublicKey import RSA as pycrypto_RSA
from Crypto.Cipher import PKCS1_OAEP, AES
from timeout_decorator import timeout
from scryptos import *
import itertools
import primefac
import gmpy

def factor_fermat(n):
  @timeout(1)
  def inner(n):
    p = primefac.fermat(n)
    return [p, n // p]
  try:
    return inner(n)
  except:
    return []



keys = [RSA.import_pem(open('key-%d.pem' % i).read()) for i in xrange(10)]
ciphertexts = [open('ciphertext-%d.bin' % (i + 1), 'rb').read() for i in xrange(5)]

priv = []

p4 = 2758599203L # for key-2

for x, y in itertools.combinations(keys, 2):
  if x.n == y.n:
    continue
  g = gcd(x.n, y.n)
  if g != 1:
    print '[+] gcd: %s / %s' % (keys.index(x), keys.index(y))
    priv += [RSA(x.e, x.n, g, x.n // g)]
    priv += [RSA(y.e, y.n, g, y.n // g)]

for x in keys:
  if x.n % p4 == 0:
    print '[+] factordb: %s' % keys.index(x)
    priv += [RSA(x.e, x.n, p4, x.n // p4)]
  r = factor_fermat(x.n)
  if len(r) != 0:
    priv += [RSA(x.e, x.n, int(r[0]), int(r[1]))]
    print '[+] fermat: %d' % keys.index(x)

SS_data = []

for c in ciphertexts:
  header = c[:512]
  iv = c[512:512 + 16]
  body = c[512 + 16:]
  for key in priv:
    k = pycrypto_RSA.construct((key.n, key.e, key.d, key.p, key.q))
    try:
      d = PKCS1_OAEP.new(k).decrypt(header)
      SS_data += filter(lambda x: not x.startswith('Congrat'), AES.new(d, AES.MODE_CFB, iv).decrypt(body).split('\n'))
      break
    except Exception, e:
      pass

SS_data = filter(lambda x: len(x) > 0, SS_data)

for i in xrange(4):
  print repr(SS.recover_secret(SS_data[i::4]))

solve_log

Mon Feb 27 08:37:15 JST 2017 ~/Downloads/bkpctf/cr150 100%
> time python solve.py 
[+] gcd: 0 / 6
[+] fermat: 1
[+] factordb: 2
"And another one's down, and another one's down, and another one bites the dust!\n"
"Three's the magic number!  FLAG{ndQzjRpnSP60NgWET6jX}\n"
'1}MxnmDO)@:u\tY"^a\x0bi8f(6 ba4,zw)0qg?%~a%.0Z2cZp*7JI%m/KwH[8>f\nc\n%r%w<6\'~YL`*%uHsz;hg<aN?97.B8'
'4\x0cQ}~\r"\tzC6yqTtZS1b\\srA mRN~ Q\rqy{}5vERB%7n]:^pQ&iH.k5vQS81xWq|#c^|$bqzx_(!EV(c'

real    0m9.337s
user    0m9.292s
sys     0m0.012s

Summary: Factoring 3 RSA Keys + Recover Secret Share Scheme

We given 10 RSA Public Keys and 5 Ciphertexts. Ciphertexts are Encrypted by AES, That decryption key is encrypted by RSA-OAEP. Moreover, i-th plaintext is "split" to (i, 5) threshold scheme ciphertext before encryption. The flag is in 3rd plaintext (from description), so we need to break at least 3 RSA keys.

As a result, I factorize 3 RSA Keys as follows:

• Key-0 and Key-6 has common divisor. (but I decrypted ciphertext only one...)
• Key-1 can factor by Fermat Method.
• Key-2 has very small prime factor, so can factor by factordb.com or ECM Method.
• Key-3 can Wiener's Attack, but I realized it after solved this challenge...

Well, we got a 3 plaintext and recover a 3rd plaintext using secretsharing module.

Flag: FLAG{ndQzjRpnSP60NgWET6jX}