## Sunday, January 19, 2014

### 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:
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.

#### 1 comment:

1. Great, Thanks !