Hack The Vote 2016 - SMTPresident (Crypto 400) - RSA private key partial exposure attack
#-*- coding:utf-8 -*- | |
""" | |
Hastad's broadcast attack (CRT + root in integers) | |
""" | |
import os, re | |
from collections import defaultdict | |
from libnum import * | |
os.system("cat emails/* >ems") | |
os.system('for f in pubkeys/*; do echo $f; openssl asn1parse -in "$f"; echo; done >pubs') | |
E = 17 | |
id2mod = {} | |
s = open("pubs").read() | |
for id, mod in re.findall(r"pubkeys/(\w+).*?:(\w{31,})\n", s, re.DOTALL): | |
id2mod[id] = int(mod, 16) | |
by_date = defaultdict(list) | |
s = open("ems").read() | |
for to, date, cipher in re.findall(r"From: hillary@hillaryclinton.com\nTo: (\w+)@dnc\.gov\nDate: ([\d\/]+)\nEncryption Type: RSA-2048\nContent: (\w+)\n", s): | |
by_date[date].append((to, cipher)) | |
res = ["?"] * 256 | |
for date, ms in by_date.items(): | |
print date, len(ms), "msgs" | |
rems = [] | |
mods = [] | |
for to, ct in ms: | |
mod = int(id2mod[to]) | |
rems.append(int(ct, 16)) | |
mods.append(mod) | |
c = solve_crt(rems, mods) | |
m = nroot(c, E) | |
assert m ** E == c | |
m = n2s(m) | |
print `m` | |
for i, ch in enumerate(m): | |
if ch != "#": | |
assert res[i] == "?" or res[i] == ch | |
res[i] = ch | |
print `"".join(res)` | |
''' | |
Result (original challenge): | |
"Subject: My Fellow DNC Members\nContent: Keep this safe <MISSING>28957315881597123396979748976302152737640887970674976745386517370413418317681873, that's the key we agreed on." | |
Updated challenge: | |
"Subject: My Fellow DNC Members\nContent: Keep this safe <MISSING>2639379129745732820221924615242186617297578211853941290720519611109981302570690707136540905365393, that's the key we agreed on." | |
''' |
""" | |
Factor modulus using leaked 97 decimal digits of the private exponent. | |
""" | |
from sage.all import * | |
E = 0x10001 | |
P = 10 | |
L = 97 | |
mod = P**L | |
if 1: | |
# challenge | |
E,C,N = ( | |
65537, | |
87665974403152400345077381042571867203077473579612727463205456268600381221618179611248607088507602087157265518990896363173685899474912182298625946170635296927561663847805847731206803355029791082718223576008877104264333178661813748793094344203660848361984558481618464944063264037203726200290655461741881134514, | |
109953083145254169793901343426857013906448850647350805103097555822991450991149833383628768990343421456495764531203068401400677799368578354290451972122801174043112323616414199027325725325866843315718644407844904985836004549165811110165566509278440906043886301390114317150851453061813590430159605716700830406237, | |
) | |
dlow = 2639379129745732820221924615242186617297578211853941290720519611109981302570690707136540905365393 | |
p = q = None | |
start_k = 1 | |
# hint: the wanted K is 34716 | |
else: | |
# local test: generate random case | |
p = next_prime(randint(1, 2**512-1)) | |
q = next_prime(randint(1, 2**512-1)) | |
N = p * q | |
print "p", p | |
print "q", q | |
print float(log(p, N)) | |
print float(log(q, N)) | |
phi = (p-1)*(q-1) | |
D = inverse_mod(E, phi) | |
C = pow(0x31337, E, N) | |
dlow = D % (P**L) | |
print "K=", E * D // phi | |
start_k = E * D // phi | |
def solve_quadratic_mod_power(a, b, c, p, e): | |
roots = {0} | |
for cure in xrange(1, e + 1): | |
roots2 = set() | |
curmod = p**cure | |
for xbit in xrange(p): | |
for r in roots: | |
v = r + (xbit * p**(cure - 1)) | |
if (a*v*v + b*v + c) % curmod == 0: | |
roots2.add(v) | |
roots = roots2 | |
return roots | |
def calc_epsilon(N, X, beta): | |
return float(beta**2 - log(2*X)/log(N)) | |
x = PolynomialRing(Zmod(N), names='x').gen() | |
imod = inverse_mod(mod, N) | |
for k in xrange(start_k, E): | |
a = k | |
b = E*dlow - k*N - k - 1 | |
c = k*N | |
for plow in solve_quadratic_mod_power(a, b, c, p=P, e=L): | |
print "k", k, "plow", plow | |
assert (a * plow**2 + b*plow + c) % mod == 0 | |
# poly = (x * mod + plow) but .small_roots want it to be monic, | |
# so multiply by inverse of mod (modulo N) | |
poly = (x + plow * imod) | |
# 0.49 to catch both primes, or 0.5 to catch the highest only | |
beta = 0.5 | |
# math.log(2**512/10**97, 2): 189.77297479592588 | |
# so 2**200 is enough | |
epsilon = calc_epsilon(N=N, X=2**193, beta=beta) | |
roots = poly.small_roots(beta=beta, epsilon=epsilon) | |
if not roots: | |
continue | |
print "Roots", 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) | |
print msg | |
# convert to str | |
h = hex(int(msg))[2:].rstrip("L") | |
h = "0" * (len(h) % 2) + h | |
print `h.decode("hex")` | |
quit() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment