Cybercamp 2018 quals: “Unnecessary redundancy”

Intro

As a frequently player on cybergames and ctf’s this year wanted play on prequal of Cybercamp CTF 2018 organized by INCIBE. This allows me to take a snapshot of the maturity and quality of both platforms and challenges, apart from having a good time solving some problems (not always played as tunelko :))

Challenge

On this challenge they give us two files, a corrupted RSA private key and a secret.txt. First thing is replace base64 asterisks given by organizers by a simple slash to fill the encoding padding.

-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAMSwf+/I42wFwNpDQiGuv0fb9w5Ria2JJAjzrYEYKp4HAKB8nXxm
yGx6OWAhI+4PYFYT3pf95J/mg5buCvP19fMCAwEAAQJAKuxRnyR57PL8eSVAY1Vd
TPNF4QwOPZ62DHYRISEC++UtRemqE1eBPkRgswiJ91+r9y8EnVw/SvL4GYQmeovS
sQIhAOq8Heinxe4udriNOd35SgJV9e87YglCCIfCoAirR0qtAiEA1oIMcKaiRiUj
2S/Q4YFTNySdT+fH16huoSQrEapD9x8/////////////////////////////////
77//////////////////////////////////////////////////////////////
////////////////////////////////////////////
-----END RSA PRIVATE KEY-----

We need to recover final part of the key (slash part) as much data as possible. RSA private key  tipically follow an PKCS#1 scheme or format.

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

if we parse data we have with openssl we can extract n,e,d,p and q:

$ openssl asn1parse -in key.pem 
    0:d=0  hl=4 l= 315 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=2 l=  65 prim: INTEGER           :C4B07FEFC8E36C05C0DA434221AEBF47DBF70E5189AD892408F3AD81182A9E0700A07C9D7C66C86C7A39602123EE0F605613DE97FDE49FE68396EE0AF3F5F5F3
   74:d=1  hl=2 l=   3 prim: INTEGER           :010001
   79:d=1  hl=2 l=  64 prim: INTEGER           :2AEC519F2479ECF2FC79254063555D4CF345E10C0E3D9EB60C7611212102FBE52D45E9AA1357813E4460B30889F75FABF72F049D5C3F4AF2F81984267A8BD2B1
  145:d=1  hl=2 l=  33 prim: INTEGER           :EABC1DE8A7C5EE2E76B88D39DDF94A0255F5EF3B6209420887C2A008AB474AAD
  180:d=1  hl=2 l=  33 prim: INTEGER           :D6820C70A6A2462523D92FD0E1815337249D4FE7C7D7A86EA1242B11AA43F71F
Error in encoding
139985901871296:error:0D07207B:asn1 encoding routines:ASN1_get_object:header too long:../crypto/asn1/asn1_lib.c:101:

So we have only to make rest operations with help of python:

#!/usr/bin/python

import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64

# present values on key.pem 
e = 0x010001
n = 0xC4B07FEFC8E36C05C0DA434221AEBF47DBF70E5189AD892408F3AD81182A9E0700A07C9D7C66C86C7A39602123EE0F605613DE97FDE49FE68396EE0AF3F5F5F3
p = 106173580239682931389627142547722999257831171755485751420548914984291463023277
q = 97024725573258981352721169214486148772531836683230815123426383547032318244639


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None
    else:
        return x % m

# we need to recover this values on private key
dp = modinv(e, (p - 1))
dq = modinv(e, (q - 1))
qi = modinv(q, p)
phi = (p - 1) * (q - 1)
d = modinv(e, phi)


def generate_pem(n, e, d, p, q, dP, dQ, qInv):
    template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for x in [0, n, e, d, p, q, dP, dQ, qInv]:
        seq.setComponentByPosition(len(seq), pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return template.format(base64.encodestring(der).decode('ascii'))

key = generate_pem(n, e, d, p, q, dp, dq, qi)
key
f = open("somevalid.key", "w")
f.write(key)
f.close()

Once we generate our valid private key we’ll be able to read the flag:

$ cat somevalid.key 
-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAMSwf+/I42wFwNpDQiGuv0fb9w5Ria2JJAjzrYEYKp4HAKB8nXxmyGx6OWAhI+4P
YFYT3pf95J/mg5buCvP19fMCAwEAAQJAKuxRnyR57PL8eSVAY1VdTPNF4QwOPZ62DHYRISEC++Ut
RemqE1eBPkRgswiJ91+r9y8EnVw/SvL4GYQmeovSsQIhAOq8Heinxe4udriNOd35SgJV9e87YglC
CIfCoAirR0qtAiEA1oIMcKaiRiUj2S/Q4YFTNySdT+fH16huoSQrEapD9x8CIQC2/WOLhY8FeO9Q
O7hK1RXe8EhC8VYhxXqE6zJ6z5tKGQIgZkLLQWz/EWelRmXYM5kenbwzzqMVj0b5rpJ6gcpk6ksC
IQDk7SB3+YXESMSY0iXCoJjwxOjoCfRPCbeCrka+0s2pyw==
-----END RSA PRIVATE KEY-----
$ cat secret.txt | openssl rsautl -decrypt -inkey somevalid.key 
flag{gk83h280fwlo2}