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
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`).
Author
You are right, fixed it. Thanks!