CSAW Quals 2016 – Broken Box (Crypto 300 + 400)

I made a RSA signature box, but the hardware is too old that sometimes it returns me different answers… can you fix it for me?}

e = 0x10001

nc crypto.chal.csaw.io 8002

Summary: fault attack on RSA signatures, factoring using private exponent exposure.

In these two challenges we were given black-box access to a RSA signing (decryption oracle). We need to decrypt a given flag, but the oracle allows only to sign values in range 0-9999. Moreover, sometimes it gives different signatures for same values, because there are some faults due to “hardware errors” mentioned in the description.

Part 1

The simplest fault attacks on RSA are attacks on RSA-CRT, where by using gcd we can factor the modulus. However we tried to apply them and they failed. Therefore, it is probably not RSA-CRT scheme there.

By sampling signatures of, let’s say number 2, we can find that there are about 1000 unique values. It matches the size of the modulus in bits. Then it may be that the server flips some single bit of the secret exponent sometimes. There was a similar challenge already at this year’s Plaid CTF, but there we didn’t get enough bits.

Here’s how we can check our hypothesis: if we get $s = 2^{d \oplus 2^k} \mod{N}$ for some $k$, we can guess $k$ and check if $(s\times 2^{\pm 2^k})^e \mod N = 2$. If this condition holds, then we learn one bit from the secret exponent, depending on the sign of $\pm k$.

Indeed, the following script waits to collect all unknown bits and prints the flag for the first part:

import ast
from sock import Sock
from libnum import *
 
N = 172794691472052891606123026873804908828041669691609575879218839103312725575539274510146072314972595103514205266417760425399021924101213043476074946787797027000946594352073829975780001500365774553488470967261307428366461433441594196630494834260653022238045540839300190444686046016894356383749066966416917513737
E = 0x10001
sig_correct = 22611972523744021864587913335128267927131958989869436027132656215690137049354670157725347739806657939727131080334523442608301044203758495053729468914668456929675330095440863887793747492226635650004672037267053895026217814873840360359669071507380945368109861731705751166864109227011643600107409036145468092331
C = int(open("flag.enc").read())
 
f = Sock("crypto.chal.csaw.io 8002")
f.send_line("2")
f.read_until("no")
 
def sign(val):
    f.send_line("yes")
    f.send_line("%d" % val)
    sig, mod = map(int, f.read_until_re(r"signature:(\d+), N:(\d+)\s").groups())
    assert mod == N
    return sig
 
try:
    bits, vals = ast.literal_eval(open("dump").read())
except:
    bits, vals = {}, []
vals = set(vals)
 
print len(bits), "known bits"
num = 2
 
gs = {
    num * pow(num, (1 << e) * E, N) % N
    : e for e in xrange(0, 1030)
}
gsi = {
    (num * invmod(pow(num, (1 << e) * E, N), N)) % N
    : e for e in xrange(0, 1030)
}
 
while 1:
    if len(bits) >= 1024:
        print len(bits), "known", set(range(1025)) - set(bits), "unknown"
        d = sum(1 << e for e, b in bits.items() if b)
        print "Try:", `n2s(pow(C, d, N))`
 
    sig = sign(num)
    if sig in vals:
        continue
    vals.add(sig)
    test = pow(sig, E, N)
    if test in gs:
        bits[gs[test]] = 0
        print "bit[%d] = 0" % gs[test]
    if test in gsi:
        bits[gsi[test]] = 1
        print "bit[%d] = 1" % gsi[test]
    open("dump","w").write(`(bits, list(vals))`)
    print len(bits), "known bits"

The flag: flag{br0k3n_h4rdw4r3_l34d5_70_b17_fl1pp1n6}

Part 2

In the second part, the server has faults only in the 300 least significant bits of the secret exponent.

There is an LLL-based attack when more than quarter of the secret exponent bits are known. You can read more about these attacks in an awesome paper “Twenty Years of Attacks on the RSA Cryptosystem” by Dan Boneh (page 11):

$$ed – k\phi(N) = 1, ~\mbox{where}~ k < e$$ $$ed - k(N - p - q + 1) = 1$$ $$ed - k(N - p - q + 1) \equiv 1 \pmod {2^l}, ~\mbox{where}~ l = 300$$ $$ped - k(Np - p^2 - N + p) \equiv p \pmod {2^l}$$ We can guess $k < e$ and then we have a quadratic equation on the least significant bits of $p$. We can solve this quadratic equation bit-by-bit by solving it modulo 2, 4, 9, etc.

After finding 300 least significant bits of $p$, we can use Coppersmith method for finding small roots of polynomials modulo $p$: assume we know $t$ and $r$ such that $p = rx + t$. In our case $r$ is $2^{300}$. We multiply both sides by inverse of $r$ modulo $N$: $r^{-1}p = x + r^{-1}t \pmod{N}$. We see that x is a small root of polynomial $x + r^{-1}t$ modulo $p$ and so we can compute it with the Coppersmith’s method.

Here’s the full code (Sage):

from sage.all import *
 
N = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709
E = 97
C = 96324328651790286788778856046571885085117129248440164819908629761899684992187199882096912386020351486347119102215930301618344267542238516817101594226031715106436981799725601978232124349967133056186019689358973953754021153934953745037828015077154740721029110650906574780619232691722849355713163780985059673037
L = 300
 
bits = [0, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 16, 17, 18, 19, 22, 23, 25, 26, 27, 31, 32, 33, 35, 36, 39, 40, 41, 44, 45, 46, 48, 49, 52, 54, 55, 56, 60, 62, 63, 64, 67, 68, 72, 73, 74, 76, 80, 82, 83, 85, 88, 89, 91, 92, 93, 94, 98, 99, 101, 108, 109, 113, 115, 116, 117, 118, 119, 122, 128, 129, 131, 132, 133, 135, 142, 143, 144, 147, 152, 153, 156, 157, 160, 164, 166, 167, 168, 169, 170, 175, 177, 180, 181, 182, 185, 186, 189, 192, 193, 194, 195, 196, 197, 199, 202, 203, 205, 207, 208, 209, 211, 213, 215, 216, 217, 219, 220, 221, 222, 223, 225, 226, 227, 230, 233, 234, 235, 236, 238, 240, 242, 246, 247, 249, 252, 253, 255, 263, 264, 265, 266, 268, 271, 272, 273, 275, 276, 280, 285, 287, 288, 293, 294]
dlow = sum(2**e for e in bits)
 
x = PolynomialRing(Zmod(N), names='x').gen()
 
mod = 1 << L
imod = inverse_mod(mod, N)
 
def solve_quadratic_mod_power2(a, b, c, e):
    roots = {0}
    for cure in xrange(1, e + 1):
        roots2 = set()
        curmod = 1 << cure
        for xbit in xrange(2):
            for r in roots:
                v = r + (xbit << (cure - 1))
                if (a*v*v + b*v + c) % curmod == 0:
                    roots2.add(v)
        roots = roots2
    return roots
 
 
for k in xrange(1, E):
    a = k
    b = E*dlow - k*N - k - 1
    c = k*N
    for plow in solve_quadratic_mod_power2(a, b, c, L):
        print "k", k, "plow", plow
        roots = (x + plow * imod).small_roots(X=2**(215), beta=0.4)
        print "Roots", roots
        if roots:
            root = int(roots[0])
            kq = root + plow * imod
            q = gcd(N, kq)
            assert 1 < q < N, "Fail"
            p = N / q
            d = inverse_mod(E, (p - 1) * (q - 1))
            msg = pow(C, d, N)
            # convert to str
            h = hex(int(msg))[2:].rstrip("L")
            h = "0" * (len(h) % 2) + h
            print `h.decode("hex")`
            quit()

And for $k=53$ we get the flag: flag{n3v3r_l34k_4ny_51n6l3_b17_0f_pr1v473_k3y}.

2 comments

    • gsingh93 on September 19, 2016 at 10:04
    • Reply

    When you say `s x 2^k`, do you mean `s x 2^(2^k)`? The latter should flip the bit of the exponent, if I understand correctly (depending on the sign of `k`).

    1. You are right, fixed it. Thanks!

Leave a Reply

Your email address will not be published.