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);
  }
  num_read = fread(buf, 1uLL, 128, fp);
  fclose(fp);
  long2bytes(&flag_bytes, buf, num_read);

  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_add(modulus, modulus, 1LL);
  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}