crypto_tonnerre

Tonnerre (Crypto, 200 points, 119 solves)

We were pretty sure the service at tonnerre.pwning.xxx:8561 (source) was totally secure. 
But then we came across this website and now we’re having second thoughts... 
We think they store the service users in the same database?

###ENG PL

This task consisted of two parts: website vulnerable to SQL injection and server authenticating via zero knowledge proof protocol specifically Secure Remote Password protocol.

Using script we quickly exploited the SQL vulnerability to dump information about the only user stored in database: username, verifier and salt (although we didn't need salt).

The next part was forcing server script to authenticate us and get the flag. The idea of zero knowledge proof is that the server aka verifier knows a secret and challenges the user to prove that the user also knows the secret. This has to happen without disclosing the secret itself so no part of the secret should ever be transmitted. The general approach to this problem is that the verifier provides a random task that can be solved only by someone with secret.

In our case the server prompted us for some number (denoted as pC) and calculated:

c=(pC*v)%N
if c not in forbidden set:
	r=random(2,N-3)
	pS=(g**r)%N
	res=(pS+v)%N
	secret=((pC*b)**r)%N
	key=f(res, secret)

It then sent us res and asked for resulting key.

We know N and g from the source code, while v is the verifier value we extracted via SQL injection.

It is easy to see that if we know res, we can calculate pS. This is because pS has to be less than N (it is reminder from division modulo N) and we know the value of v which is in the same order as N. This implies that pS+v has to be between v and 2N-1 and thus the modular division reminder of res=(pS+v) mod N can be:

• Bigger than v which means that pS was small enough that the sum pS+v did not exceed N and this means the pS = res - v
• Smaller than v and this means the actual sum was greater than N and got cut by modulo and therefore pS = res - v + N

Our case was the second one.

Now the task can be stated as follows:

Given pS, N, v, g
knowing pS=g**r % N,
 find (pC*v)**r % N for any pC.

We can see that the numbers we need to find and the one we know are quite similar - they are both something to the power of r modulo N. If we make bases equal, we would succeed. Indeed, it is quite easy to find solution of equation:

pC*v=g (mod N)

We can multiply both sides by modular inverse of v mod N and get:

pC*v*modinv(v)=g*modinv(v) (mod N)
pC=g*modinv(v) (mod N)

Unfortunately, this solution would not be accepted, as this particular pC is in forbidden set. So are also the obvious solutions like pC=0 which would give 0**r % N = 0

Since the only thing we can use is the value of g**r (mod N) it's clear that the pC*v has to be connected with g. We also know that the most natural operation when dealing with modular powers are powers so we figure that we could square our "known" equation, to get:

pS**2=(g**2)**r (mod N)

So we know the value of (g**2)**r (mod N) and we need to convince the server to ask us to provide this value, so we need to provide such pC so that pC*v mod N == g**2 mod N

Repeating steps above to this equation, we get:

pC=(g**2)*modinv(v) (mod N)

And therefore is we provide such pC the server will ask us for the value of:

(pC*v)**r = ((g**2)*modinv(v)*v)**r = (g**2)**r = (g**r)**2 = pS**2 (mod N)

And since we know pS, the task is solved and the flag is PCTF{SrP_v1_BeSt_sRp_c0nf1rm3d} - actual implementation is here.

###PL version

Zadanie składało się z dwóch części: strony podatnej na SQL injection oraz serwera autentykującego za pomocą zero knowledge proof protocol, konkretnie Secure Remote Password protocol.

Korzystając ze skryptu szybko exploitowalismy podatność SQL i pobralismy informacje na temat jedynego użytkownika z nazy danych - username, verifier i salt (akurat salt nie był nam potrzebny).

Następny krok to zmuszenie skryptu serwera aby nas zautentykował i podał flagę. Idea zero knowledge proof polega na tym, ze server czyli verifier zna pewien sekret i daje użytkownikowi do rozwiązania zadanie które ma potwierdzić że użytkownik także zna sekret. To musi odbywać się bez odkrycia sekretu więc żadna jego część nie może zostać transmitowana. Ogóle podejście do tego problemu polega na tym, że verifier generuje losowe zadanie możliwe do rozwiązania tylko przez kogoś z sekretem

W naszym przypadku serwer pytał o pewną liczbę (oznaczoną dalej jako pC) i obliczał:

c=(pC*v)%N
if c not in forbidden set:
	r=random(2,N-3)
	pS=(g**r)%N
	res=(pS+v)%N
	secret=((pC*b)**r)%N
	key=f(res, secret)

Następnie przesyłał nam wartość res i pytał o wynikowy klucz.

Wiemy ile wynoszą N oraz g z źródła serwera, podczas gdy v zostało przez nas wyciągnięte z bazy danych przez SQL Injection.

Łatwo zauważyć że jeśli znamy res to możemy łatwo policzyć pS. Wynika to z faktu, że pS musi być mniejsze od N (to reszta z dzielenia przez N) oraz znamy wartość v która jest tego samego rzędu co N. To oznacza, że pS+v musiby być pomiędzy v i 2N-1 a z tego wynika że reszta z dzielenia modulo res=(pS+v) mod N może być:

• Większa od v co znaczy, że pS było małe i suma nie przekroczyła N i tym samym pS = res - v
• Mniejsza od v co znaczy, że suma była większa od N i została obcięta przez modulo i tym samym pS = res - v + N

W naszym przypadku prawdziwa była sytuacja numer 2.

Teraz zadanie można przedstawić jako:

Mając dane pS, N, v, g
wiedząc że pS=g**r % N,
 znajdź (pC*v)**r % N dla pewnego pC.

Możemy zauważyć, że liczby których szukamy i które znamy są dość podobne - i tutaj i tutaj mamy r-te potęgi modulo N. Gdybyśmy mogli ustalić identyczne podstawy potęg rozwiązalibyśmy zadanie. Łatwo wyliczyć potrzebną wartość pC z równania:

pC*v=g (mod N)

Możemy obustronnie pomnożyć to przez modinv v mod N i dostajemy:

pC*v*modinv(v)=g*modinv(v) (mod N)
pC=g*modinv(v) (mod N)

Niestety takie rozwiązanie znajduje się w zbiorze zabronionych wartości dla pC. Podobnie jest z innymi oczywistymi rozwiązaniami jak pC=0 które dałoby łatwe do przewidzenia 0**r % N = 0

Jako że jedyna wartość którą możemy wykorzystać to g**r (mod N) jest jasne że pC*v musi mimo wszystko być powiązane z g. Wiemy też, że najbardziej naturalną operacją kiedy mamy do czynienia z potęgowaniem jest potęgowanie, dochodzimy więc do wniosku, że moglibyśmy podnieść znane równanie do kwadratu dostając:

pS**2=(g**2)**r (mod N)

Wiemy więc teraz ile wynosi (g**2)**r (mod N) i potrzebujemy przekonać serwer aby spytał nas o tą właśnie wartość, więc musimy dostarczyć takie pC że pC*v mod N == g**2 mod N

Wykonujac kroki podobne jak powyżej dla nowego równania dostajemy:

pC=(g**2)*modinv(v) (mod N)

I tym samym jeśli podamy tak wyliczone pC serwer zapyta nas o:

(pC*v)**r = ((g**2)*modinv(v)*v)**r = (g**2)**r = (g**r)**2 = pS**2 (mod N)

A wartość pS jest nam znana więc zadanie jest rozwiązane i flaga to PCTF{SrP_v1_BeSt_sRp_c0nf1rm3d} - całe rozwiązanie dostępne tutaj