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 N, and the prompt tells us that e=65537). We therefore want to somehow recover either the decryption key d or the factorization of N.

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)
>>> pow(s2, e, N)

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 x, it is just computing the value x^{d} \bmod N (this way, the signature can be verified with the public key e). Probably when the box breaks, one of these values (x, d, or N) 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 d that is changing to some d', then we have both x^{d} \bmod N and x^{d'} \bmod N. Dividing these modulo N, we can compute x^{d-d'} \bmod N. Now, if d and d' really do differ by just a single bit, then d-d' either equals 2^{k} or -2^{k} for some integer k between 0 and 1024 (the bit length of N). So we can verify our suspicion by computing the set of powers \{x^{2^k} \bmod N | 0 \leq k < 1024\} \cup \{x^{-2^k} \mod N | 0 \leq k < 1024\} and checking if our quotient x^{d-d'} lies in it. Luckily, it does!

What information does this tell us about d? Well, if a single bit was flipped and d-d' = 2^{k}, then the kth bit of d must be 1. Likewise, if d-d' = -2^{k}, then the kth bit of d must be 0. So from each incorrect signature, we can learn one of the bits of d (and once we have all of the bits of d, 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:
    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'
        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
                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
                assert d_bits[bit_loc]==1
            print 'WARNING: quot not in tps or itps'

print 'cur d:', get_d()

Using this d, 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)
>>> long_to_bytes(_)

2 thoughts on “CSAW Quals 2016 – Broken Box

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s