Ghost in the Shellcode 2014 - PapSmear writeup

This was a reversing task for 150 points. There was a python script which asked for a serial. If the serial we enter is accepted, we get a key. Here is the original source: https://gist.github.com/balidani/f91d5011365aea897768

The source is kind-of obfuscated, but not too badly. After making things prettier, this is what we came up with:

#!/usr/bin/python
from collections import defaultdict as d
from itertools import count as c
from operator import mul as m

def generate_primes():
    _b, __b = [], d(list)

    _c = 1
    for a in c():
        if a < len(_b): _c = _b[a]
        else:
            _c += 1
            while _c in __b:
                for b in __b[_c]: __b[_c+b]+=[b]
                del __b[_c]
                _c += 1
            __b[_c+_c]+=[_c]
            _b.append(_c)
        yield _c

def prime_factors(n):
    for _c in generate_primes():
        if _c > n: return
        _d = 0
        while n % _c == 0: _d, n = _d + 1, n / _c
        if _d != 0: yield _c

def relative_prime(x, y): 
    # return ___a(x * y) == ___a(y) * ___a(x)
    from fractions import gcd
    return gcd(x, y) == 1

def in_bounds(i, j):
    if not 10000 < i < 100000:
        return False
    if not 100 <= j <= 999:
        return False
    return True

def is_prime(n):
    import math
    if n < 2:
        return False
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 1
    return True

def main():
    try:
        c = raw_input('Serial: ').split('-')
        
        if len(c) != 6: 
            raise
        for x in range(0, 6, 2):
            # c[x] is 5 chars long, c[x+1] is 3
            if not in_bounds(int(c[x]),int(c[x+1])):
                raise 

            # Tests if c[x] is a prime
            if not is_prime(int(c[x])):
                raise

            # Tests whether c[x] and c[x+1] are relative primes
            if not relative_prime(int(c[x]), int(c[x+1])):
                raise

            # c[x] and c[x+1] have to be unique
            if len([y for y in c if y == c[x]]) > 1:
                raise
            if len([z for z in c if z == c[x+1]]) > 1: 
                raise

        c.reverse()

        for k in range(7,10):
            a,b = int(c.pop()),int(c.pop())
            for x in [a+b*n for n in range(k)]:
                if not is_prime(x):
                    raise

        with open('flag.txt','r') as f:
            print f.read()
    except:
        print 'Bzzt. Wrong!'
 
if __name__ == '__main__': 
    main()

Basically, we need to enter 3 sections that consist of a large (5 char long) and a small (3 char long) number. The large numbers all have to be prime. The second part of the algorithm checks that all the numbers of the form a+b*n are prime, where a is the big number, b is the small number and n goes from 0 to k; k is 7 for the first part, 8 for the second and 9 for the third. Based on this, it is pretty straightforward to brute force a serial.

Additionally, one of my teammates discovered a very nice trick to bypass the part that makes sure we entered 3 different sections. The numbers are compared in string form, and so we can prepend a 0 to them and they will appear different. Since int() uses base 10 by default, this isn't a problem in python (other languages may detect octal notation). In the end, we couldn't use this method, it didn't work remotely for some reason.

I wrote this script to brute force a serial:

def serial_test(b, s, k):
    for x in [b+s*n for n in range(k)]:
        if not x in big_primes:
            return False
    return True

def main():

    primes = generate_primes()
    p = primes.next()

    while p < 10000:
        p = primes.next()
    while p < 100000:
        big_primes.append(p)
        p = primes.next()

    for s in range(100, 1000):
        print s
        for b in big_primes:
            if serial_test(b, s, 9):
                print b, s

This script was rather slow, it took about 2-3 seconds to check a single s value (with k=9). We could have made tons of changes to make it fast, but we decided not to waste time and just ran this in parallel. In the end we found 3 values that work up to k=9, though we only needed k=8 and k=7 for two of these. The resulting serial was: 61637-420-10859-210-10861-840. Sending this to the server resulted in a key: "ThesePrimesAreNotIllegal". 

Thanks to AKG and KT, and the whole SpamAndHex (Lite) team. Thanks to the Ghost in the Shellcode team for making this amazing CTF, we had lots of fun.