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()

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.

Great, Thanks !

ReplyDelete