This is an old revision of the document!
PRIMJER -Zadatak s Hacknite platforme - DSA
U zadatku je implementirana specifikacija DSA (“Digital Signature Algorithm”). Kao unos se traži poruka te parametri “r” i “s”. Kako bi se flag ispisao poruka mora biti postavljena na “flag” te funkcija verificiraj mora vratiti true.
if verificiraj(r, s):
if "flag" in poruka:
print("Poruka verificirana")
print(os.environ["flag"])
Ranjivost programa nalazi se u provjerama nad parametrima “r” i “s”.
if r==0 or s==0 or r==q or s==q:
return False
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 “r” i “s” moraju biti 0 < “r” < “q” te 0 < “s” <“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.