Writeup: WPICTF 2018 - Bitpuzzler

nc bitpuzzler.wpictf.xyz 31337

This challenge was resolved after the end of the CTF.

On connection the server will output a C source code like this:

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

inline int64_t pmod(int64_t x) {
    int64_t v = x % 745018031;
    if(v < 0)
        return v + 745018031;
    else
        return v;
}

int main(int argc, char** argv) {
    int64_t x;
    scanf("%ld", &x);
    x = pmod(x);
    x = pmod(x + 544945418);
    x = pmod(x - 413537559);
    x = pmod(x + 742620753);
    x = pmod(x + 521496552);
    x = pmod(x * 217323223);
    x = pmod(x + 555632816);
    x = pmod(x * 150026081);
    x = pmod(x * 488682886);
    x = pmod(x * 438027182);
    x = pmod(x - 277961190);
    x = pmod(x + 733382750);
    x = pmod(x * 365221180);
    x = pmod(x * 206951831);
    x = pmod(x * 206787839);
    x = pmod(x + 466722489);
    x = pmod(x + 590127514);
    x = pmod(x + 729286233);
    x = pmod(x - 511866912);
    x = pmod(x * 62049651);
    x = pmod(x + 651782087);
    x = pmod(x * 84167258);
    x = pmod(x * 534841468);
    x = pmod(x - 152376404);
    x = pmod(x - 708647451);
    x = pmod(x * 402510031);
    x = pmod(x + 684952081);
    x = pmod(x + 157356094);
    x = pmod(x + 581217174);
    x = pmod(x * 494995445);
    x = pmod(x * 413245049);
    x = pmod(x - 465738152);
    x = pmod(x - 445076249);
    x = pmod(x * 634818015);
    x = pmod(x + 311971388);
    x = pmod(x * 395815216);
    x = pmod(x - 228527650);
    x = pmod(x - 390982625);
    x = pmod(x * 167525229);
    x = pmod(x - 67124720);
    x = pmod(x + 196498368);
    x = pmod(x - 389321179);
    x = pmod(x * 407769339);
    x = pmod(x - 668656066);
    x = pmod(x + 737252782);
    x = pmod(x * 563677494);
    x = pmod(x * 381498309);
    x = pmod(x - 162841870);
    x = pmod(x * 221177751);
    x = pmod(x * 186322169);
    x = pmod(x - 273857766);
    x = pmod(x * 714646597);
    x = pmod(x + 528983903);
    x = pmod(x + 161261126);
    x = pmod(x + 580072051);
    x = pmod(x + 73562406);
    x = pmod(x * 580917844);
    x = pmod(x * 333982766);
    x = pmod(x * 26464204);
    x = pmod(x + 444910125);
    x = pmod(x - 211161758);
    x = pmod(x + 857150);
    x = pmod(x + 151241230);
    x = pmod(x * 460103625);
    x = pmod(x + 349965546);
    x = pmod(x + 336647433);
    x = pmod(x - 651868703);
    x = pmod(x - 560457375);
    x = pmod(x - 310027822);
    x = pmod(x * 173984028);
    x = pmod(x * 743346575);
    x = pmod(x - 257680324);
    x = pmod(x - 193467970);
    x = pmod(x - 37222260);
    x = pmod(x - 719528370);
    x = pmod(x + 455833225);
    x = pmod(x - 694794023);
    x = pmod(x + 40785744);
    x = pmod(x + 485999702);
    x = pmod(x * 467215786);
    x = pmod(x + 143033673);
    x = pmod(x - 203472932);
    x = pmod(x * 509780859);
    x = pmod(x + 651949322);
    x = pmod(x * 178249781);
    x = pmod(x - 318931279);
    x = pmod(x + 402539290);
    x = pmod(x + 737886610);
    x = pmod(x * 206810936);
    x = pmod(x + 277968593);
    x = pmod(x * 210016962);
    x = pmod(x - 30673877);
    x = pmod(x * 385367916);
    x = pmod(x * 502168498);
    x = pmod(x - 450292458);
    x = pmod(x - 315721957);
    x = pmod(x * 555742689);
    x = pmod(x * 575672494);
    x = pmod(x + 678057901);
    x = pmod(x * 128401438);
    x = pmod(x + 277859141);
    if(x == 737645692) {
        printf("Success\n");
        return 0;
    } else {
        printf("Failure\n");
        return 1;
    }
}
----

and will awaits for an input: the x that after all that operations is equal to 737645692.
At each connection operations and numbers will are randomized so after parsing correctly each raw is time to reverse the pmod function.

The pmod constant (in the above example is 745018031) is always a prime number so, using the Fermat’s Little Theorem, is possible to reverse operation with * operator.

For example, if a = 2 and p = 7, then 27 = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7.

The other ones weren’t a big problem:

(a +/- x) % m = b
x = (b +/- a) % m

The result is the below python script.

#!/usr/bin/env python3
from pwn import log, remote
import math
import re
import sys


def switch_op(op):
    case = {
        "+": "-",
        "-": "+",
        "*": "/",
        "/": "*",
    }
    return case.get(op)


# Connect and readall
r = remote('bitpuzzler.wpictf.xyz', '31337')

# 82 Rounds
for z in range(82):
    log.info("Round: {}".format(z))
    line = r.recvuntil("}\n----").decode()
    log.info(line)
    # Read: int64_t v = x % 1403906831;
    pmod_val = int(re.findall("int64_t v = x % (\d*);", line)[0])

    # First pmod skipped (is a prime number) => just get pmod_val
    # Read all: x = pmod(x * 1291394425);
    ops = re.findall("x = pmod\(x (.) (\d*)\);", line)

    # Read: if(x == 297265140) {
    result = int(re.findall("\(x == (\d*)\)", line)[0])

    x = result
    for op in reversed(ops):
        try:
            if op[0] == "*":
                # Fermat to solve the inverse pmod
                inv_pmod = pow(int(op[1]), pmod_val - 2, pmod_val)
                # (prev_result * inv_pmod) % pmod_val
                o = "({} * {}) % {}".format(x, inv_pmod, pmod_val)
            else:
                # (prev_result +/- arg) % pmod_val
                o = "({} {} {}) % {}".format(x, switch_op(op[0]), int(op[1]),
                                             pmod_val)
            x = int(eval(o))
        except Exception as e:
            print(e)
            print(o)
            sys.exit(-1)

    # Send result
    r.sendline(str(x).encode())
    line = r.recvuntil("CORRECT!").decode()
    if not "CORRECT!" in line:
        log.warning("Execution stopped: WRONG RESULT!")
        log.warning(o)
        break

# GET FLAG!
log.success(r.recvall().decode().strip())

After 82 rounds the challenge is completed and the server will output the flag.

Flag

WPI{R1NG$_@ND_F13LDS_M@KE_M3_W@NT_T0_D13}