Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active May 13, 2020 02:19
Show Gist options
  • Save hellman/a9854751bb489fb69e8267b8eea01f39 to your computer and use it in GitHub Desktop.
Save hellman/a9854751bb489fb69e8267b8eea01f39 to your computer and use it in GitHub Desktop.
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