This is an old revision of the document!
PRIMJER -Zadatak s Hacknite platforme - DSA
Tomislav je napisao aplikaciju za verifikaciju digitalnih potpisa. Želi da pregledaš izvorni kod i testiraš je li nekako moguće zaobići verifikaciju. Dostupan ti je izvorni kod programa, a na njegov servis se možete spojiti naredbom nc chal.platforma.hacknite.hr 13011 ako koristite Linux odnosno telnet chal.platforma.hacknite.hr 13011 ako koristite Windows
U zadatku je implementiran DSA (“Digital Signature Algorithm”).
Kao unos se traži poruka te parametri “r” i “s”. Kako bi riješili zadatak, moramo programu dati digitalno potpisanu poruku koja sadrži string “flag” i koja prolazi validaciju digitalnog potpisa (digitalni potpis čine parametri “r” i “s”). Budući da nemamo privatni ključ, ne možemo jednostavno potpisati poruku nego moramo pronaći nekakvu ranjivost u programu.
Kod za verifikaciju je sljedeći:
def verificiraj(r, s): if r==0 or s==0 or r==q or s==q: return False w = modinverz(s, q) m = int(sha256(M).hexdigest(), 16) u1 = (m * w) % q u2 = (r * w) % q v = (pow(g, u1, p) * pow(y, u2, p)) % p % q if v == r: return True
Po DSA specifikaciji (koju je moguće pronaći npr. na Wikipediji) “r” i “s” moraju zadovoljavati uvjete
0 < "r" < "q"
te
0 < "s" <"q"
Vidimo da je implementacija u zadatku malo drukčija, ne provjerava se jesu li “r” i “s” manji od vrijednosti q.
def euklidov_prosireni(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = euklidov_prosireni(b % a, a)
return (g, x - (b // a) * y, y)
def modinverz(a, m):
g, x, y = euklidov_prosireni(a, m)
return x % m
Funkcija koja određuje vrijednost w jest modinverz. Ukratko, modinverz interno koristi Euklidov algoritam kako bi se pronašao modularni inverz broja “a” mod “m”. Modularni inverz “k” jest broj za koji vrijedni (“k”*“a”) mod “m” == 1. Ako takav broj ne postoji vraćena je 0. Npr. ako je vrijednost “a” postavljena na 0, ne postoji broj “k” koji će zadovoljiti uvjet zbog čega će i sami “k” biti 0.
Kako bi verifikacija bila uspješna potrebno je zadovoljiti uvjet “v” == “r”. Vrijednost “v” određena je, među ostalom, umnoškom rezultata funkcija pow() čiji su eksponencijali “u1” i “u2”. Kada bi parametri “u1” i “u2” bili jednaki 0, obije funkcije bi vratile 1 pa bi samim time vrijednost v bila 1 (što je unutar dozvoljene domene “r”). Zbog toga je rješenje da se “w” postavi na vrijednost 0 jer će “u1” i “u2” će također biti 0 i time dobiti “v” == 1.
Otprije, zaključili smo da je “w” nula kada “s” nema modularni inverz. Neke od vrijednosti koje nikad nemaju inverz su npr. 0, q, 2*q, 3*q itd… Zbog neispravnih provjera nad parametrima vrijednost veće od “q” su dozvoljene stoga je rješenje npr. “s” = 2*q.