Let's Failcrypt 2
Zadanie
Zadanie takie samo, jak Let's Failcrypt, ale tym razem mamy ograniczenie e > 65537.
Rozwiązanie
Zrobimy coś podobnego jak w części 1, ale najpierw trzeba coś zauważyć. Z tw. Eulera, dla względnie pierwszych a i n mamy: (phi - Funkcja Eulera)
⇓
aphi(n) + 1 ≡ a (mod n)
Pozostaje wylosować takie nonce, żeby sig oraz sig - nonce były względnie pierwsze, ale okazuje się, że zwykle tak jest. Ostatnim problemem jest policzenie phi(sig - nonce), ale także tutaj raz na kilkanaście prób otrzymujemy liczbę z którą Sage sobie radzi. Kod rozwiązania (nie chciało mi się implementować timeoutów, więc trzeba odpalić kilka razy aż trafi na liczbę którą da radę sfaktoryzować, czasami też wywali się na tworzeniu certyfikatów, co można poprawić wywalając checka w bilbiotece od RSA. Ale po odpowiedniej liczbie prób tak czy inaczej zadziała):
#!/bin/python2
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
from sage.all import euler_phi
import requests
import re
pattern = re.compile('Take this nonce: (.+) and sign with your RSA key.')
def __gcd(x, y):
while(y):
x, y = y, x % y
return x
def get_signature_record(domain):
from dnsknife import resolver
ans = resolver.query(domain, 'TXT')
txt = ans.response.answer[0][0].strings[0]
return bytes_to_long(txt)
def verify_signature(pubkey, signature, nonce):
pubkey = RSA.importKey(pubkey)
e, n = pubkey.e, pubkey.n
# Don't allow weak keys
if e < 65537:
return False
return pow(signature, e, n) == nonce
def verify(pubkey, domain, nonce):
return verify_signature(pubkey, get_signature_record(domain), nonce)
def get_nonce_session():
r = requests.get('https://failcrypt2.ecsc19.hack.cert.pl/')
nonce = int(re.search(pattern, r.text).group(1) , 16)
session = r.cookies['session']
return [nonce, session]
domain = "crypto.legit-service.ovh"
sig = 69652904871897821472183980483739811079341753893561761327070812091923231785899489652896157669669507587458401009228978259408204706276670753919975140850280030223767922199087641241921416001554872048271328614288968166632445276064459059733006891002904038810054234972139730618071021672122606450686569981612121078067
while True:
s = get_nonce_session()
nonce = s[0]
print("Nonce: {}".format(nonce))
gcd = __gcd(sig, sig - nonce)
print("GCD: {}".format(gcd))
if(gcd > 1):
continue
print("Calculating phi of {}".format(sig- nonce))
phi = euler_phi(sig - nonce)
print("Result: e {} n {}".format(phi + 1, sig - nonce))
print("Cookie: {}".format(s[1]))
if(pow(sig, phi + 1, sig - nonce) == nonce):
print("Result verifired")
else:
print("Result wrong O_o")
continue
cert = RSA.construct((sig - nonce, phi + 1)).publickey().exportKey().decode()
print(cert)
print("Solution: {}".format(x))
print("Cert: ")
print(cert)
Następnie wystarczy przekleić ciasteczko oraz certyfikat na stronę i otrzymujemy flagę:
ecsc19{crypto-challenges-are-hard-without-unintended-solutions}
No Comments