PapSmear (Gits CTF 2014) [очень просто]

К сожалению, весь GitS я проспал, но через несколько дней я наткнулся на задание, и по инерции начал решать.

Нужно было получить флаг, исходник сервиса прилагался:

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

_b, __b = [], d(list)

def _a():
    _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 __a(n):
    for _c in _a():
        if _c > n: return
        _d = 0
        while n % _c == 0: _d, n = _d + 1, n / _c
        if _d != 0: yield _c

def main():
    ___a = lambda n: int(reduce(m, (1 - 1.0 / p for p in __a(n)), n))
    ____a = lambda x,y: ___a(x*y)==___a(y)*___a(x)
    _____a = lambda i,j: ((1<<14)-(3*(1<<11))-(1<<8)+(1<<4)<i<1<<17>>1|1077<<5 and 2**6|9<<2<=j<=1023&39|31<<5)
    try:
        c = raw_input('Serial: ').split('-')
        if len(c) != 6: raise
        for x in range(0,6,2):
            if not _____a(int(c[x]),int(c[x+1])) or (___a(int(c[x]))!=int(c[x])-1) or not ____a(int(c[x]),int(c[x+1])): raise
            if len([y for y in c.__iter__() if y==c[x]])>>1 or len([z for z in c.__iter__() 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)]:
                y = [p for p in __a(x)]
                if not (len(y)==1 and y[0]==x): raise
        with open('flag.txt','r') as f:
            print f.read()
    except:
        print 'Bzzt. Wrong!'

if __name__ == '__main__': main()

После некоторого разбора невнятный файл не так уж и сложен. Разберу по порядку:

Функция _a() является генератором простых чисел. Её использует функция __a(n), которая возвращает простые делители числа n.

A3 = ___a = lambda n: int(reduce(m, (1 - 1.0 / p for p in  __a(n)), n))

Эта лямбда-функция (пусть она будет A3) вычисляет значение от числа n по формуле:

img1

Где d1, d2, …,dk — как раз те самые простые делители числа n, которые вычисляются при помощи __a.

A4 = ____a = lambda x,y: ___a(x*y)==___a(y)*___a(x)

Следующая функция A4 (используемая в сервисе с отрицанием) вычисляет, являются ли два числа взаимно простыми, ведь равенство нарушается, когда функция __a отсекает одинаковые делители у произведения x*y.

A5 = _____a = lambda i,j:
((1<<14)-(3*(1<<11))-(1<<8)+(1<<4)<i<1<>1|1077< 2**6|9<<2<=j<=1023&39|31<<5)

Последняя функция A5(x, y) хоть и выглядит очень грозной, является самой безобидной. Если присмотреться, то можно увидеть следующее:

A5 = _____a = lambda i,j: ((1<<14)-(3*(1<<11))-(1<<8)+(1<<4) < i < 1<<17>>1|1077<<5 
 and 2**6|9<<2 <= j <= 1023&39|31<<5)

Константы легко вычисляются, что позволяет упростить функцию:

A5 = _____a = lambda i,j: 10000<i<100000 and 100<=j<=999

После чего программа спрашивает “серийный номер”, состоящий из 3 пар по два элемента. Для каждой такой пары он проверяет три свойства:

• Первый элемент должен содержать 5 цифр, второй — три:

not _____a(int(c[x]),int(c[x+1]))

Отчего серийник имеет вид XXXXX-XXX-XXXXX-XXX-XXXXX-XXX

• Первый элемент должен быть простым числом:

(___a(int(c[x]))!=int(c[x])-1)

• Числа должны быть взаимно простыми:

not ____a(int(c[x]),int(c[x+1]))

Следующая проверка не позволяет повторения чисел в пределах серийного кода, выполняется для каждой из трех пар:

len([y for y in c.__iter__() if y==c[x ]])>>1 or

len([z for z in c.__iter__() if z==c[x+1]])>>1

После чего для них выполняется проверка:

for x in [a+b*n for n in range(k)]:
 y = [p for p in __a(x)]
 if is_simple(y): raise

Где k принимает значения 7, 8, 9 для каждой пары соответственно.
Из этого следует, что пары, подходящие для более старших разрядов кода будут подходить для более младших. С учетом всего вышесказанного очень легко осуществить перебор всех значений. Я решил не генерировать простые числа, а использовать готовый список:

curl http://primes.utm.edu/lists/small/100000.txt | \
  grep -v [a-z] | sed -e 's/[^0-9]\+/\n/g' | grep -v ^$ > plain

Список для перебора первых элементов:

cat plain.txt | grep ^[0-9][0-9][0-9][0-9][0-9]$ > list-a

И соответствующих им вторым:

seq 100 999 > list-b

Перебирал вот таким скриптом:

import sys

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True

for b in (int(x) for x in open('list-b').readlines()):
  for a in (int(y) for y in open('list-a').readlines()):
    made = 0
    broke = False
    for j in [a+b*n for n in range(int(sys.argv[1]))]:
      if not is_prime(j):
        broke = True
        break
      else:
        made += 1
    if not broke:    print("%d %d" % (a, b))

Получить первые пары можно так:

python gen.py 7 | tee result-1

После чего, ради экономии времени можно ограничить список
перебора:

awk '{print $1}' result-1 > list-a

И получить остальные пары:

python gen.py 8
python gen.py 9

Любой ключ, составленный из этих не повторяющихся пар, подходит. Пример правильного кода: 22697-210-53299-420-10861-840
Флаг — ThesePrimesAreNotIllegal, явная отсылка к нелегальным простым числам 🙂

Задание оказалось очень простым, за что справедливо получало жалкие 150 баллов.

3 Comments

 Add your comment
  1. Где же ты был, когда за это баллы давали! 🙂
    Интересно, а код был вручную обфусцирован или есть какие-то тулзы для обфускации прог на Питоне?

    • Да он тут и не сильно и обфусцирован. Просто запутанный алгоритм, необычное форматирование, короткие названия переменных и функции, заткнутые в лямбды. Хотя, что-то подобное гугл находит

      >Где же ты был, когда за это баллы давали?
      Я же сказал, что спал…

  2. отличные статья)

    выложили часть writeups по phd, вот сижу посыпаю голову пеплом https://ctftime.org/writeups

Leave a Comment

Your email address will not be published.

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.