## 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](#pl-version)
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](doit.py) 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](public_server.py) 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)%Nif 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, gknowing 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](solve.py).
###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](doit.py) 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](public_server.py) 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)%Nif 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, gwiedzą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](solve.py)
