CSAW Quals 2016 – Broken Box

In this Crypto challenge, we are given a link to a server implementing an RSA signature box, that will sign any number we provide between 0 and 1000. As the title indicates, this box is “broken”; in particular, sometimes it will output different signatures for the same number:

Input an number(0~9999) to be signed:2
signature:22611972523744021864587913335128267927131958989869436027132656215690137049354670157725347739806657939727131080334523442608301044203758495053729468914668456929675330095440863887793747492226635650004672037267053895026217814873840360359669071507380945368109861731705751166864109227011643600107409036145468092331, N:172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
Sign more items?(yes, no):yes
Input an number(0~9999) to be signed:2
signature:152634467197766294944528378462389218441871583443834345519496373329032422359831135390499248415245450771788918319206870509177784040619039419004834728447206198549783552316203831646453009094605291388458519660621927183336756297750589167848611913970264013753701808692568557838002605634391337941132554468117369960245, N:172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
Sign more items?(yes, no):no

We are also given a file “flag.enc” which presumably contains the RSA-encrypted flag (all queries seem to use the same value of , and the prompt tells us that ). We therefore want to somehow recover either the decryption key or the factorization of .

Well, the first thing we can check is to see what these signatures are signatures of.

>>> N = 172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
>>> s1 = 22611972523744021864587913335128267927131958989869436027132656215690137049354670157725347739806657939727131080334523442608301044203758495053729468914668456929675330095440863887793747492226635650004672037267053895026217814873840360359669071507380945368109861731705751166864109227011643600107409036145468092331
>>> s2 = 152634467197766294944528378462389218441871583443834345519496373329032422359831135390499248415245450771788918319206870509177784040619039419004834728447206198549783552316203831646453009094605291388458519660621927183336756297750589167848611913970264013753701808692568557838002605634391337941132554468117369960245
>>> e = 65537
>>> pow(s1, e, N)
2L
>>> pow(s2, e, N)
19774224542347826250418487251252200727108060100611925421644101000814693890815617773934645809006585490585757768163948992736479542098474024152584898759670505850544954972703254577892642704073724252240015560398840850320822992386708513637510921232977929379806573675784382090215917096687095598160460028316565044650L

Turns out that sometimes the box does correctly sign 2, but sometimes it either signs something else or something goes wrong in the signing process. Let’s think about what could possibly be going wrong.

When an RSA box computes a signature of some message , it is just computing the value (this way, the signature can be verified with the public key ). Probably when the box breaks, one of these values (, , or ) changes to something it shouldn’t, hopefully in some controlled way (say, flipping a single bit; this seems like the most likely thing malfunctioning hardware would do).

If it is that is changing to some , then we have both and . Dividing these modulo , we can compute . Now, if and really do differ by just a single bit, then either equals or for some integer between 0 and 1024 (the bit length of ). So we can verify our suspicion by computing the set of powers and checking if our quotient lies in it. Luckily, it does!

What information does this tell us about ? Well, if a single bit was flipped and , then the th bit of must be 1. Likewise, if , then the th bit of must be 0. So from each incorrect signature, we can learn one of the bits of (and once we have all of the bits of , we can decode the flag). This is implemented in the code below:

from Crypto.Util.number import *
from pwn import *
import time

true_sig = 22611972523744021864587913335128267927131958989869436027132656215690137049354670157725347739806657939727131080334523442608301044203758495053729468914668456929675330095440863887793747492226635650004672037267053895026217814873840360359669071507380945368109861731705751166864109227011643600107409036145468092331
N = 172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
e = 65537

assert pow(true_sig, e, N) == 2

two_inv = (N+1)/2
assert (2*two_inv)%N == 1

tps = [pow(2, 2**i, N) for i in xrange(1024)]
itps = [pow(two_inv, 2**i, N) for i in xrange(1024)]

true_sig_inv = inverse(true_sig, N)
assert (true_sig_inv*true_sig)%N==1

print 'done preprocessing'
print 'starting challenge'

d_bits = [-1]*1024
def get_d():
    return sum([2**i for i, v in enumerate(d_bits) if v==1])

conn = remote('crypto.chal.csaw.io', 8003)
while d_bits.count(-1)>0:
    conn.sendline('2')
    x = conn.recvline().split(':')
    sind = x.index('signature')
    curS = int(x[sind+1].split(',')[0])
    curN = int(x[sind+2])
    print 'S', curS
    print 'N', curN
    print '# bits left:', d_bits.count(-1)
    print 'cur d:', get_d()

    assert curN == N
    if curS == true_sig:
        print 'true signature'
    else:
        quot = (curS*true_sig_inv)%N
        if quot in tps:
            bit_loc = tps.index(quot)
            if d_bits[bit_loc]==-1:
                print 'found bit:', bit_loc
                d_bits[bit_loc]=0
            else:
                assert d_bits[bit_loc]==0
        elif quot in itps:
            bit_loc = itps.index(quot)
            if d_bits[bit_loc]==-1:
                print 'found bit:', bit_loc
                d_bits[bit_loc]=1
            else:
                assert d_bits[bit_loc]==1
        else:
            print 'WARNING: quot not in tps or itps'
    conn.sendline('yes')

print 'cur d:', get_d()

Using this , we can decode the flag.

>>> from Crypto.Util.number import *
>>> d = 131811419667704353419669934273801498497646935210532028120447799308664007960357278340261723808572637548407550908403239344903997788296564439667659716110934822412855421586673808904193606481137679044132688115472132575150399986901493501056787817443487153162937855786664238603417924072736209641094219963164897214757
>>> N = 172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
>>> flag = int(open('flag.enc', 'r').read())
>>> pow(flag, d, N)
14337636555117581912035284717398623438053794433568171094176959018630647515648078157769482917557656499837L
>>> long_to_bytes(_)
'flag{br0k3n_h4rdw4r3_l34d5_70_b17_fl1pp1n6}'