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.
Također, vrijedi proučiti kako je implementirana funkcija modinverz.
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 modinverz računa multiplikativni modularni inverz pomoću proširenog euklidovog algoritma. Više o operaciji multiplikativnog modularnog inverza možete pročitati na poveznici.
Ono što je bitno, jest da će funkcija vratiti 0 ako multiplikativni modularni inverz nije definiran.