• Home
• Music
• Books
• Problems
• Writeups
• Contact
• Blog

FourPass

This is my response to a certain telco’s OnePass. I call it “Fourpass” (because it takes *four* inputs instead of *one*).

I don’t think it’ll get accepted because it is so slow though…

Files given:

• token

First we need to understand what the token does. Throwing it into a python beautifier, we get

#!/usr/bin/python3.8
a, b, c, d = list(map(int, input().split()))
print(
    sum(
        filter(
            lambda x: x == 1,
            map(
                lambda x: (
                    lambda f: (lambda x: x(x))(lambda x: f(lambda *y: x(x)(*y)))
                )(lambda f: lambda x, y: x if not y else f(y, x % y))(*x),
                [(f, x) for f in range(a, b) for x in range(c, d)],
            ),
        )
    )
)

Notice that (lambda f:(...)) implements the Y combinator and it’s input is essentially the GCD algorithm. This tells us that lambda x:() implements GCD which can easily be verified in python.

Next, the array loops over all $a\le f<b,c\le x<d$ and then map computes GCD(f,x), then finally the filter and sum counts how many pairs have GCD $1$, i.e. coprime pairs. Hence we need to write an efficient algorithm to count the number of coprime pairs within a fixed range.

To solve this problem efficiently, we can simply implement an efficient algorithm for the function

$$f(A,B)=\left|\{(a,b)=1|0<a<A,0<b<B\}\right|$$

and then given $a,b,c,d$, we can compute $f(b,d)-f(a,d)-f(b,c)+f(a,c)$ and send to the server.

This can be done via inclusion-exclusion by counting pairs sharing one prime factor, primes sharing two, etc:

$$f(A,B)=AB-\sum _{p_i}\lfloor \frac{A}{p_i}\rfloor \lfloor \frac{B}{p_i}\rfloor +\sum _{p_i\ne p_j}\lfloor \frac{A}{p_i{p}_j}\rfloor \lfloor \frac{B}{p_i{p}_j}\rfloor +\dots$$

To make this efficient, we can precompute all the products up to a certain bound using a slightly modified Eratosthenes sieve:

for(i=2;i<MAX;++i){
    if(sieve[i] == -1)continue;
    if(sieve[i] == 0){
        for(j=2;i*j<MAX;++j){
            if(j%i==0)sieve[j*i]=-1;
            else{
                if(sieve[j*i]!=-1)sieve[j*i]++;
            }
        }
        sieve[i] = 1;
    }
}

Here the final result in sieve[i] would be the number of prime factors that i has, and -1 if i has a repeated factor.

Using this, we can compute $f$ pretty quickly, fast enough for the server to accept, giving us the flag:

Correct OTP. Have your flag: CTFSG{c_4_c0pR1me_Int3geRs}

We can optimize the solution a bit further by computing the output directly instead of having to call f four times, but this turns out to be fast enough.

The C script can be found at solver.c and to hook up to the server, I’ve written a quick pwntools script at solve.py.

Flag: CTFSG{c_4_c0pR1me_Int3geRs}