Last active
May 13, 2020 02:19
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#-*- 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." | |
''' |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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