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, ili naredbom: 
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. Funkcija će vratiti nulu za 0 i q (koji nisu dozvoljeni), ali također i za sve višekratnike q (npr. 2*q) koji jesu dozvoljeni.

To znači da ako vrijednost parametra s postavimo na 2*q tada će vrijednost varijable w biti 0, što pak znači da će i vrijednost varijabli u1 i u2 također biti 0, a vrijednost varijable v biti 1. Kako bi verifikacija prošla, v mora biti jednak r . Vrijednost r možemo postaviti na 1, tako da zadatak možemo riješiti postavljanjem vrijednosti r na 1, a vrijednosti s na 2*q , a u poruci m napišemo “flag” .