# s1protocol – Pwn2Win 2020 CTF

Points: 303 (dynamic) Solves: 18

## TL;DR

1. Reverse the binary and figure out the cryptosystem
2. Given `N` and `enc_flag`, find the flag such that `enc_flag = pow(N+1, flag, N**3*(N+1))`
3. Just do `((enc_flag % (N**2)) - 1)//N` to trivially get the flag

## Reversing

We are given a statically linked, stripped binary. Library signatures can often help in figuring out most of the functions used in cases like this. We tried to apply both Ghidra Function ID and FLIRT signatures with no success. We simply could not find the correct versions of GMP/libc used.

We tried this database for Ghidra Function IDs, and this and this for FLIRT signatures. We used this script to make FLIRT signatures work on Ghidra

And a few others. Here is a video from LiveOverflow explaining how to use function signatures.

Fortunately, the code was simple and the used library functions were gueassable:

``````int main(int argc, const char **argv, const char **envp)
{
do
{
get_random_bytes(y, 21); /* Random 168 bit pattern in p */
for ( i = 0; i < 128 / 21; ++i )
copy_pattern(rand + i * 21, y, 21);
get_random_bytes(rand + i * 21, 128 % 21); /* Add r (16 random bits) to p */
long2bytes(&prime1, rand, 128);
set_bit_at(&prime1, 8 * 128 - 2);
set_bit_at(&prime1, 8 * 128 - 1);
set_bit_at(&prime1, 0LL);
}
while ( !mpz_probab_prime_p(&prime1, 0x1Eu) );

do
{
get_random_bytes(rand, 128);
long2bytes(&prime2, rand, 128);
set_bit_at(&prime2, 8 * 128 - 2);
set_bit_at(&prime2, 8 * 128 - 1);
set_bit_at(&prime2, 0LL);
}
while ( !mpz_probab_prime_p(&prime2, 30u) );

fp = fopen("flag.txt", "r");
if ( !fp )
{
puts("Error opening file!", "r", v6);
exit(1LL);
}
fclose(fp);

get_random_bytes(rand, 128 - 1);
long2bytes(&h, rand, (128 - 1));

mpz_mult(modulus, &prime1, &prime2);
mpz_mult(mega, modulus, modulus);
mpz_mult(mega, modulus, mega);
mpz_powm(&h, &h, modulus, mega);
mpz_mult(mega, modulus, mega);

mpz_powm(&flag_enc, modulus, &flag_bytes, mega);
printf("%Zd\n\n", modulus);
printf("%Zd\n\n", &h);
printf("%Zd\n\n", &flag_enc);
return 0;
}
``````

First, the primes are generated. `q` is a prime generated in the usual way. `p` has a pattern of 168 bits that repeats 6 times (the first loop in the program is copying that pattern to a buffer that will contain the whole number `p`). The remaining `16` bits of `p` are random (well, except the lsb of course, which must be 1 because `p` is prime).

Next, it reads the `flag` from flag.txt and computes `mega = (N)^3 * (N+1)` and finally `flag_enc = (N+1)^flag mod mega` . The program ends after printing 3 numbers. `N+1` (first), `flag_enc` (third) and the second number you can safely ignore. We later found that the number was there because this challenge was an attempt to implement a cryptosystem similar to Paillier

`N=24873956958658402268767683103493059896705299540675048547193795288445376056675974746836994045550208950377561438045299653683756857105762284046700057257044778523863095409390382049154376271272054943837723148622450408029389494774175445756568213417919195725130474727174628849316519649758004047082836095165350139241058167015090602339726250580015660699904551403507821949156006918652616841989957152257987416669296535546243917804424508781976452089018525704521989449529550926409771357879685458344231307480394377651973499196053459100169309910822372188138310059463352985798139208816853247052829533726918240148879918230116779685881`

`flag_enc=18428399105595996961515811921707990727653260717642658712541834420088167386326987692951440881093688002508631713852063965061978677459437797320689251640992533223046518522072918900604464580409030532404259008544091928774177996128300208606156442339760752372514205635729970619382245049361626001780876752343960460705755403955090210024052934657669571113565239017807119768566276056775218484758035399676233915466621817119550578315271532965059678226523430899165741630373578006128272176988094952317075115159339084659193844799374916026767640630203728921037804701086905310586626229116392558599728591815848492690767516766143234423322495778101432963236834024277390567571475345191723405794849522539171353783810253837884044941425519617224922655791140543165196313620440415711725128392000722618420294150169733992258565931055118945208142949559648780073069549527195230142366972701405667756245661827274130023407442375062577405959630643238924040304451652297183959561499281166658115035522581592610055569148021012398195643177094967096428642292809342669777213190447833845067670326283024646372655558839943529587701206915598083204372271902663259579792750144591006987281419196927135806018068565132654908969559786696669667315961886187385442163534480866732123864742170197665381529254809256159962467704689821540233085472974540416603149400800721664345995487295132334125825493454734414260955214929887987277730666481584050558313649862480554901213277814662444795994876156575572927134077195421987446166331797316932052426748860511416605096827562871516417748467511042807410788879367694082147491443814128415863382238475852086736746881424190205259481314481019058897925764815245709212647407265895705060482652071388956545434794149541739912429471155975267179726823164755144189931523049837200489136287872440178738146309234111751991607853550502113678543223192106904436736756952523123394440305176551507936718060308541642453863817745252003422632545905058611880601574558213477294878566628312900177620646056123584081993396735772307746743031229684838785421720292706316599476094606488343258717774802351006514880362063033571885253083937582238610492891038979311741724662422971164`

## Factoring N

We spent a few hours trying to factor N. We managed to do it but it revealed to be useless, or at least there is a much simpler way to get the flag. For the curious ones, here is how we factored N:

Let `y` be the random 168 bit pattern in `p` that repeats 6 times. `r` the 16 random bits (`p` lsbs) where `r & 1 == 1` because `p` is prime,

Then, we can say `p = y*K + r` where `K = 2^16 + 2^(16+168) + 2^(16+168*2) + ... + 2^(16+168*5)` This means that `N = (y*K + r)*q = y*K*q + r*q` and therefore `N % K = r*q % K` so if we bruteforce `r` we know that `q % K = (N % K)*r^(-1) % K` Let `x` be number of times that `q` wraps around `K` so that `q = (q % K) + x*K`. `x` is a 168 bit number because `K` is a 856 bit number and `q` is a 1024 bit number.

We know now that `N = p*q = (y*K + r)*((N % K)*inverse(r, K) + x*K)` where the only unknowns are `x` and `y` and they are both small (168 bits each). Factoring N can then be reduced to finding small roots of the following polynomial: `P(x,y) = (y*K + r)*((N % K)*inverse(r, K) + x*K) - N`. Using Coron’s reformulation, we can find these roots and therefore our factorization.

We used the following script to factor N in 10 minutes using 8 cores: solve.sage

## Get the flag

The only thing you had to do to get the flag after reversing the binary was this:

Expanding `flag_enc` yields `N^flag + flag*N^(flag-1) + ... + flag*N + 1 mod mega` Given that `N^2` is a factor of `mega`, we can compute `flag_enc mod N^2 = flag*N + 1 mod N^2` which is simply `flag*N + 1` because that number is smaller than `N^2`.

To get the flag, just subtract 1 and divide by N…

flag: CTF-BR{the_S1_Protocol_1s_pa1lli3r_but_w3ird_and_puzzle}