Facebook CTF 2019 keybaseish Writeup

Facebook CTF 2019 featured quite a fair number of challenges. I played this weekend (and spent far more time than I’d like to admit) with some coworkers and interns. Here’s the writeup to the crypto challenge keybaseish.

---

Visiting the website gave me the following landing page:

Trying to register a new account gives an error:

Poking around doesn’t yield much, as this is a crypto challenge and not a (eeuuugh) web challenge. However, I was pretty sure that the Forgot your password? option was where I’d find the flag:

First thing I did was take a look at the Twitter page given:

The Twitter handle @baseishcoinfou1 only has a few tweets. Based off of the description given on the Forgot your password? page, I assume I have to somehow spoof myself as that baseishcoinfou1 guy to log in.

The script given to generate a signature from the pin on the page:

sign.py

from Crypto.PublicKey import RSA
from Crypto import Random

def print_twitter(sig):
    sig_str = str(sig)
    n = (len(sig_str) / 255) + 1
    chunks, chunk_size = len(sig_str), int(len(sig_str)/n) + 1
    tweets = [ sig_str[i:i+chunk_size] for i in range(0, chunks, chunk_size) ]
    print("Please post these signature strings as public twitter posts from your accout:")
    for ndx in range(len(tweets)):
        print ('  "PRF{}/{}:{}"'.format(ndx+1, len(tweets), tweets[ndx]))

def main():
    rng = Random.new().read
    print('Enter challenge pin from site: ')
    pin = input()
    print('Signing "{}" with a new RSA key....'.format(pin))
    RSAkey = RSA.generate(1024, rng)
    signature = RSAkey.sign(int(pin), rng)
    key_params = RSAkey.__getstate__()
    print_twitter(signature[0])
    print('\\n\\nPlease input your public key on the web form:')
    print('  "{}:{}"'.format(key_params['e'], key_params['n']))
    print('\\n\\n')

if __name__ == '__main__':
    main()

Looks like a simple RSA problem! I like RSA problems since they’re (more or less) straightforward and simple if you understand the math behind RSA.

Just to test the script, I ran it:

python sign.py
Enter challenge pin from site:
181017
Signing "181017" with a new RSA key....
Please post these signature strings as public twitter posts from your accout:
  "PRF1/2:12616772997099881092375957326003990137779551590105056359724007346007270008590031540842987916830146724788896698376238275605644665709297153261025689486677058"
  "PRF2/2:1568999222098812125219384637167519141955275734978704095636241686766565034894108909513705239180738446930042084402798058928111360197321674943244865943473114"
\n\nPlease input your public key on the web form:
  "65537:145747811796572471696747097157677997611648214067955469374447752842447868280985991728977790393206040581952310449663503299506235400385799969481411870524508083265137943592770093338719137641828543820981124371367546988503982540558023348323871125943787522195565603427560680045189757271148997310447224805702675483099"
\n\n

Somehow, I feel like there weren’t supposed to be escapes for the newlines, but oh well. Everything seems to check out here.

So the idea seems to be that by supplying the website with a public key that matches the signature with a given pin, then I can verify my identity. This is pretty poor security, obviously, especially given the fact that I have control over the exponent (which I stupidly overlooked for at least several hours). The equation for the signature is as follows:

pin = signature^e mod n

I have the pin given to me by the website, the signature from the Twitter page of baseishcoinfou1, and the exponent. All I need is a valid n.

For the exponent, I’ll choose 5. Why 5? It is relatively low and means that when I exponentiate the signature, the n can be represented by the same number of bits. Basically:

kn + pin = signature^e

In my case, I’m going to assume k = 1, making the problem very trivial. In effect:

n = signature^e - pin

I wrote a short Python script to calculate this:

solve.py

# Signature from the Twitter page of baseishcoinfou1
signature = 43522081190908620239526125376626925272670879862906206214798620592212761409287968319160030205818706732092664958217053982767385296720310547463903001181881966554081621263332073144333148831108871059921677679366681345909190184917461295644569942753755984548017839561073991169528773602380297241266112083733072690367

# Pin given by the "Forgot your password?" page
pin = 181017

# Low exponent
e = 5

print '%d:%d' % (e, pow(signature, e) - pin)

Running the script yields the following public key:

5:156152259934610603327242777109298638373934572320003018946780705593035129444427250712903196953268692654576940252842426080729553952653677882004392693966587497895771126063209172520687408155983845138814448218643812756870429001677159139697312185528286445629870220439486395991895413533025617686453330864683812555753179156400433858871091471963735884941049381029699284926525734780530683371637232542486580601832498002442370205259218637335066255536340402863614960635863279257288993952331758568563539255171752333659803630559976542479997459049186400474006649599261061239561731085004017823362429679461455596473090496147014713630612514413037251048846131962952608974559597665037989589516588758915639505296076818565509671460227096392858914958248349719519761080165615153613390888909577250254133864459387364823840496709605537195438529272540877498372727188018102166924786597538072319044503910010189326796934513137869684765977644563798377464844285519970335294217160696344254550102370879793030817756422968722131250375494110628633064924047523515038128770714301615363185342011455425978139447595336835379107137242896370138133354739730815895341370949542102301040465958437918589288157598747503502123011375289921007339937318514618737528870366815796019608309972031321180211231027906387141262192775078672105433479871010768651433527003348326639168952600370384527925162635252188830536959099871687232387447443824170080109823399109258223217519865552564954330502656132579024379460503613264612232039663908389480448494284442261160415871697947245392343456421606992172540775590

When inputting this as the public key into the form, I get the flag.