Статья Игра в секретики. Как я восстановил схему генерации флагов на локальном CTF

[neonh4ze]

Игра в секретики. Как я восстановил схему генерации флагов на локальном CTF

Привет, XSS!

Являясь студентом кафедры компьютерной безопасности, время от времени я принимаю участие в различных мероприятиях, посвященных ИБ — как официальных, так и более самодеятельных. Сегодня я хотел бы рассказать историю, которая произошла со мной на одном из неофициальных ивентов в моем институте осенью прошлого года. История эта связана с победой во внутривузовской CTF-кампании через раскрытие системы генерации флагов. Далее по тексту ты найдешь: щепотку криптографии, дружелюбные иероглифы формул модульной арифметики, немного разработки на Python и развязку в духе "Hack the Planet!" локального масштаба.

Поехали!

Предыстория

Некоторые приглашенные преподаватели моей кафедры имеют привычку организовывать миниатюрные «показательные» CTF-выступления внутри коллектива студентов курса. Нетрудно догадаться о цели проведения таких мероприятий: концепция «вербовки» новых сотрудников а-ля Cicada 3301 стара как мир. Я и четверо моих друзей также решили скоротать время в одном из последних подобных соревнований.

Правила были просты: четыре команды по пять человек максимум и три «раунда», в каждом из которых тебе и твоей команде предлагается пять тасков на различные области знания (Crypto, Reverse, PWN, Forensics, Stego — все по классике). По окончании каждого из таких раундов капитан команды собирает завоеванные флаги в кучу и отправляет их на сервер преподавателя, от которого получает Proof-of-Evidence завершенния текущего этапа (по словам преподавателя, секретное слово генерируется криптографически на основании промежуточных флагов). Финальный секрет озвучивается (на ушко) админу всея пати, а он, в свою очередь, триггерит для тебя и твоей команды начало следующего раунда. Победа достается команде, первой решившей все задачи.

Ключевая особенность такой, казалось бы, слишком заумной системы сдачи флагов заключается в следующем: условный эндпоинт API, куда нужно стучаться, чтобы получить свое секретное слово, доступен в течении одной минуты каждый час соревнования. Другими словами, даже если вы со своей тимой собрали все флаги из всех пяти тасков текущего раунда, но опоздали в «окно» доступности преподавательского сервера, вам придется ждать еще туеву хучу времени, чтобы перейти на следующий этап.

Добавление в игру временного фактора открывает дополнительный (хоть и не предусмотренный изначально) вектор атаки: если узнать алгоритм порождения финального секрета, можно значительно сократить общее время прохождения тасков и обеспечить себе временнóе преимущество, которое в дальнейшем с высокой вероятностью может решить исход встречи в вашу пользу.

Это и было сделано :смайл:

Пороговые схемы разделения секрета

Я опущу подробности объяснений, почему у нас была четкая уверенность в верности догадки о выборе используемого алгоритма (для этого нужно быть знакомым с составителем CTF'а лично, хе-хе), однако факт применения пороговой схемы разделения секрета для нас был практически очевиден. Оставалось лишь определиться с конкретным криптографическим методом, и выбор пал на схему разделения секрета по Шамиру, как самую легко реализуемую на практике. Члены команды продолжили решать таски, в то время как я решил попробовать восстановить алгоритм генерации общего секрета на основе уже имеющихся данных за крайний раунд.

Схема разделения секрета Шамира

Схема Шамира — это такая криптографическая (k,n)-пороговая схема разделения секретного сообщения, при использовании которой только k из n сторон могут восстановить сообщение без потерь. Главный принцип данного метода — возможность интерполяции многочлена степени k-1 через k точек для восстановления исходного секрета.

За всеми этими умными словами скрывается простая идея: чтобы разделить сообщение на k зашифрованных частей необходимо и достаточно:

1. Представить разделяемый секрет в виде числа. Неважно, каким именно способом это будет сделано, главное только, чтобы этот способ был обратимым. Первое, что приходит на ум: перевести из ASCII в HEX. Назовем получившееся число M.
2. Выбрать простое число p, которое выступить генератором конечного поля, p > M.
3. Построить многочлен степени k-1 над данным полем. То есть все операции будут производиться по модулю p.
4. Вычислить значения (называемые «тенями») построенного многочлена в n различных точках, отличных от 0. Значения «иксов» не играют роли, поэтому можно взять числа просто по порядку от 1 до n.

На этом все! Каждой из k сторон выдается пара (x, y), где x — аргумент многочлена, y — его значение (или «тень») при данном значении аргумента. Также стороны знают степень многочлена и значение генератора p. Остальная информация о проведенной операции разделения секрета стирается.

Таким образом, обладая условной точкой (x, y) в прямоугольной системе координат, каждый из обладателей исходного секрета владеет необходимой крупицой информации для его восстановления. Восстановление тоже проходит не сложно: после того, как все стороны «скинут» в общую кучу свою разделяемую часть, будет легко заново построить первоначальный многочлен: либо через решение системы уравнений, либо интерполяцией того самого полинома Лагранжа. Здесь отлично видно, почему извлечь секретное сообщение не представляется возможным в случае, когда количество «скинутых» осколков секрета меньше k: система уравнений попросту не решится однозначно.

За конкретным примером отправляю читателя прямиком на вики.

Графическая интерпретация

В качестве графического примера, улучшающего понимание вопроса, можно представить такую ситуацию: чтобы однозначно задать прямую на плоскости нужно ровно две точки (см. рис. 1). Если точка будет одна, прямых через нее может быть проведено бесконечно много. Однако общее количество точек на прямой — то есть количества частей, на сколько можно разделить сообщение — есть число (n), большее двух (k), что и отражает суть (k,n)-пороговой схемы.

Рисунок 1 — Прямую на плоскости можно однозначно задать по двум (k=2) точкам, однако общее количество точек на прямой — частей, на сколько можно разделить секрет — заведомо больше двух (n>=2) (источник — ru.wikipedia.org)

Аналогичный пример можно привести для параболы.

Однако следует помнить, что примеры выше — всего лишь абстракции для облегчения понимания функционирования схемы, не более, потому что в реальной жизни используется арифметика над конечным полем, где геометрическую интерпретацию изобразить не так просто.

Реализация на Python

Итак, мы отвлеклись. Чтобы испытать нашу теорию, я нашел и установил стороннюю либу для питонов, которая позволяет разделять (и, соответственно, восстанавливать) сообщения в разных форматах, следуя схеме Шамира. Как окажется в последствии (когда я прогуглю о "Secret Sharing Schemes" более подробно), схемы реализации разделения секретов для Python доступны еще много где: от самопальных разработок на коленке до довольно мощных проектов типа PyCryptodome в лице модуля Crypto.Protocol.secret_sharing.

Но в тот момент главным для меня была скорость написания PoC'а, поэтому я остановился на первой ссылке гугла, а именно на модуле secret-sharing.

Восстановление секрета

Флаги к заданиям имели вид FLAG-{<BASE58_TEXT>}. Кодировка Base58, полагаю, была использована для исключения возможности разночтений флага (так делают в кошельках Bitcoin, к слову).

На этот момент у было пять флагов с прошлого раунда:

• FLAG-{9ERQNGRcjoTq7MPfgTVejtzSNv33f3ietAorhZk7Se2zeytDWSr3YfDgAzY6jLDinXnreakt8RpUcdRGqxC35pgxkZXDeokZm17DrSY46imouKHekQ65hEXZkDHcZXTbeAE52R9Um38LZdw4zQqqBCC7MDgCUfFyWPeeqHvcCk24c66iM6aJ1E9CJw7Tj65T74ASYM4dVfoeQg7qFC7gyMT8jdEhzmHB5psTNfg53422iVFmnG7vnoNd84}
• FLAG-{94xDeQNWNVi2613QaYiNvPjpzsFP8aygF4c817bH7veBSuy7JsR6zhFitLgdddE7S8wjFutmLXDu3L79kfwhi3xrsVj9Pug2i3ZP4tKNK8UoXmJZ3tsigw9CVFo9HXS7CmPoaBxA1FAghPJBcT629d5ktAm7F7v3n2vd8PoXTEkENvmxqvPfMBuHf7PeoNpvdUUogouFb6F7ZgSY5hiwKefmovCoHTENUFmw49CHDfHQVmNS8tS1uTNJ4x}
• FLAG-{9EVdrpc9dTb1XkCNMpsifXHyH1ohXBcxCHXux5BzpL3eN5ND18RWeNnvCqvmdDCVs6eFcb2H7dejhtHjyiiBfVUyTg8SSPBTvHkLVQSGFF7vgRX6gJtQRCsv64oDBLHztmEqJrYoQZxrEacgKxgYUa1riedPjEPbQSstkCPzoAt8XpsZu67kvwwkfp3g84cFe4SYMZjcTuxFwT4MvNwjQw3UR1JryJr9jR728dZ4ufTt6kTcjJ6F1KTA4M}
• FLAG-{9Yr73zHw5YeGpNJyChAytgNJUW2W5qc984AnXJFaisV41954TcqmRqEAHpKCucHjyHHmujumA4pnXvCs6thmTZeH5Nq9cxhMrLdRUpishqNwkkkKqb1s6tCrHf1ojC5CTiNpfSW8NE7KwS8BAaNJf7WCptVo69YF2sqYAF9VWKXphBr1sMUfmqenSmoRndbo3H792QAfrrhXwDyEKGASLv2d7Skf8M5TXwHiScrFGVkiKKFWQEszXmn8GF}
• FLAG-{952T7YxKh5LtySTDf2L2ZLMe15TXBYyf5wjCrzCWSW6HpSzQoARsCVRBb86ADriiefXd2PnqMG742RnS7T4jAknV4egKcydPyfMytfgrNxYvjpi6je44hrLFnYLSDxdcEdBv6PCifuZkRkHYA2nWybGQGcSWVqX8Z51ePSQYjx51caJFEnrvEX38Sbvsu6yCFZrBrJZMk4kWB8N7hZNVFfvKTgMNvg3wpxUgzRzHnzFLfZ7CUxWmJZ9oQb}

Я установил два сторонних пакета — secret-sharing и base58:

$ pip install secret-sharing base58

И попробовал восстановить секрет так, как предлагает мануал (выбрал класс BitcoinToB58SecretSharer, а значения аргументов — от 2 до 6):

>>> from secretsharing import BitcoinToB58SecretSharer
>>> shares = [
...     '2-9ERQNGRcjoTq7MPfgTVejtzSNv33f3ietAorhZk7Se2zeytDWSr3YfDgAzY6jLDinXnreakt8RpUcdRGqxC35pgxkZXDeokZm17DrSY46imouKHekQ65hEXZkDHcZXTbeAE52R9Um38LZdw4zQqqBCC7MDgCUfFyWPeeqHvcCk24c66iM6aJ1E9CJw7Tj65T74ASYM4dVfoeQg7qFC7gyMT8jdEhzmHB5psTNfg53422iVFmnG7vnoNd84',
...     '3-94xDeQNWNVi2613QaYiNvPjpzsFP8aygF4c817bH7veBSuy7JsR6zhFitLgdddE7S8wjFutmLXDu3L79kfwhi3xrsVj9Pug2i3ZP4tKNK8UoXmJZ3tsigw9CVFo9HXS7CmPoaBxA1FAghPJBcT629d5ktAm7F7v3n2vd8PoXTEkENvmxqvPfMBuHf7PeoNpvdUUogouFb6F7ZgSY5hiwKefmovCoHTENUFmw49CHDfHQVmNS8tS1uTNJ4x',
...     '4-9EVdrpc9dTb1XkCNMpsifXHyH1ohXBcxCHXux5BzpL3eN5ND18RWeNnvCqvmdDCVs6eFcb2H7dejhtHjyiiBfVUyTg8SSPBTvHkLVQSGFF7vgRX6gJtQRCsv64oDBLHztmEqJrYoQZxrEacgKxgYUa1riedPjEPbQSstkCPzoAt8XpsZu67kvwwkfp3g84cFe4SYMZjcTuxFwT4MvNwjQw3UR1JryJr9jR728dZ4ufTt6kTcjJ6F1KTA4M',
...     '5-9Yr73zHw5YeGpNJyChAytgNJUW2W5qc984AnXJFaisV41954TcqmRqEAHpKCucHjyHHmujumA4pnXvCs6thmTZeH5Nq9cxhMrLdRUpishqNwkkkKqb1s6tCrHf1ojC5CTiNpfSW8NE7KwS8BAaNJf7WCptVo69YF2sqYAF9VWKXphBr1sMUfmqenSmoRndbo3H792QAfrrhXwDyEKGASLv2d7Skf8M5TXwHiScrFGVkiKKFWQEszXmn8GF',
...     '6-952T7YxKh5LtySTDf2L2ZLMe15TXBYyf5wjCrzCWSW6HpSzQoARsCVRBb86ADriiefXd2PnqMG742RnS7T4jAknV4egKcydPyfMytfgrNxYvjpi6je44hrLFnYLSDxdcEdBv6PCifuZkRkHYA2nWybGQGcSWVqX8Z51ePSQYjx51caJFEnrvEX38Sbvsu6yCFZrBrJZMk4kWB8N7hZNVFfvKTgMNvg3wpxUgzRzHnzFLfZ7CUxWmJZ9oQb'
... ]
>>> BitcoinToB58SecretSharer.recover_secret(shares)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "secretsharing/sharing.py", line 123, in recover_secret
    secret_int = points_to_secret_int(points)
  File "secretsharing/sharing.py", line 55, in points_to_secret_int
    free_coefficient = modular_lagrange_interpolation(0, points, prime)
  File "secretsharing/polynomials.py", line 75, in modular_lagrange_interpolation
    numerator = (numerator * (x - x_values[j])) % prime
TypeError: unsupported operand type(s) for %: 'int' and 'NoneType'

И получил какую-то ошибку в математике. Облом. Попробовал сделать то же самое, вручную распаковав Base58-значения в числа и передав их функции points_to_secret_int напрямую:

>>> from secretsharing import points_to_secret_int
>>> from base58 import b58decode
>>> shares = [(i+2, int(b58decode(share.split('-')[-1]))) for i, share in enumerate(shares)]
>>> shares
[(2, 368187175636948697128010679216113169692417477377668360266597915164889432614152885070269315608072373232293422243964179872040452423142043333931906388680500281950010609835787003726718711L), (3, 224939571178205505546098472251553395036844521528935578144180355374264250751092046295099660643794758263674388692371937322324894684890986278502585327528377689094487672073574381457969991L), (4, 389572449784738548545773031523453331978114979715009063395002758617346072539494444212917767813804760948548769162589715097968622443636294356818356918227903419974958573584442003519548776L), (5, 504049251997271561034336833267126471056785194053780496037537113926792746992006341360860139625922575009201572084459115033413181714569462738049432599495148143716563227330581744384323188L), (6, 245085694543075208418794444329265851748802951479593899764465520397236875865350578945296910707457854913084197041009688839435538011402526644087045005043117094426416937062476160199792990L)]
>>> points_to_secret_int(shares)
528541488436268003457954907207912499660859898155088108931094827024485375660200902201381551179510556622257006027919562914727441134206436235902486792827143827559198951095172796578243748L

После этого что бы я ни делал, у меня не получалось перевести это число в осмысленный текст — все время получался нечитаемый мусор. Значит, где-то была ошибка в логике восстановления секрета. Что я делаю неправильно? Единственная ошибка могла быть в значениях аргументов «координат», ведь, как ты помнишь, они необязательно должны начинаться с начала и идти по порядку...

Какое еще детерминированное представление о «порядке» рабочих станций может иметь сервер преподавателя? На ум напрашивается только IP-адрес машины. Ну или MAC, но почему-то IP на подсознательном уровне звучало более достоверно. По крайней мере, хотелось так думать, ведь для этого типа адресов существует готовый метод трансляции в число :смайл:

Функция socket.inet_aton как раз этим и занимается: переводит IP-адрес из привычной нотации (4 октета, разделенных точкой) в struct in_addr (или сырые питоновские байты в нашем случае). Допустим, IP моего ПК был 172.16.0.10, тогда в числовом виде это выглядело бы так:

>>> from socket import inet_aton
>>> from struct import unpack
>>> unpack('!L', inet_aton('172.16.0.10'))[0]
2886729738

Здесь я использую квалификатор !, который определяет big-endian порядок байт (т. к. именно он используется в этих ваших сетевых делах), и функцию struct.unpack, которая обеспечивает человеческий вид полученной структуры.

Диапазон IP-адресов компьютеров моей команды: 172.16.0.10-14, поэтому с помощью следующего скрипта можно восстановить секретный флаг на локальной машине без необходимости обращения к преподскому серваку:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Usage: python2 shamir_recover_secret.py

from socket import inet_aton
from struct import unpack

from secretsharing import points_to_secret_int
from base58 import b58decode
from binascii import unhexlify

shares = [
    ('172.16.0.10', '9ERQNGRcjoTq7MPfgTVejtzSNv33f3ietAorhZk7Se2zeytDWSr3YfDgAzY6jLDinXnreakt8RpUcdRGqxC35pgxkZXDeokZm17DrSY46imouKHekQ65hEXZkDHcZXTbeAE52R9Um38LZdw4zQqqBCC7MDgCUfFyWPeeqHvcCk24c66iM6aJ1E9CJw7Tj65T74ASYM4dVfoeQg7qFC7gyMT8jdEhzmHB5psTNfg53422iVFmnG7vnoNd84'),
    ('172.16.0.11', '94xDeQNWNVi2613QaYiNvPjpzsFP8aygF4c817bH7veBSuy7JsR6zhFitLgdddE7S8wjFutmLXDu3L79kfwhi3xrsVj9Pug2i3ZP4tKNK8UoXmJZ3tsigw9CVFo9HXS7CmPoaBxA1FAghPJBcT629d5ktAm7F7v3n2vd8PoXTEkENvmxqvPfMBuHf7PeoNpvdUUogouFb6F7ZgSY5hiwKefmovCoHTENUFmw49CHDfHQVmNS8tS1uTNJ4x'),
    ('172.16.0.12', '9EVdrpc9dTb1XkCNMpsifXHyH1ohXBcxCHXux5BzpL3eN5ND18RWeNnvCqvmdDCVs6eFcb2H7dejhtHjyiiBfVUyTg8SSPBTvHkLVQSGFF7vgRX6gJtQRCsv64oDBLHztmEqJrYoQZxrEacgKxgYUa1riedPjEPbQSstkCPzoAt8XpsZu67kvwwkfp3g84cFe4SYMZjcTuxFwT4MvNwjQw3UR1JryJr9jR728dZ4ufTt6kTcjJ6F1KTA4M'),
    ('172.16.0.13', '9Yr73zHw5YeGpNJyChAytgNJUW2W5qc984AnXJFaisV41954TcqmRqEAHpKCucHjyHHmujumA4pnXvCs6thmTZeH5Nq9cxhMrLdRUpishqNwkkkKqb1s6tCrHf1ojC5CTiNpfSW8NE7KwS8BAaNJf7WCptVo69YF2sqYAF9VWKXphBr1sMUfmqenSmoRndbo3H792QAfrrhXwDyEKGASLv2d7Skf8M5TXwHiScrFGVkiKKFWQEszXmn8GF'),
    ('172.16.0.14', '952T7YxKh5LtySTDf2L2ZLMe15TXBYyf5wjCrzCWSW6HpSzQoARsCVRBb86ADriiefXd2PnqMG742RnS7T4jAknV4egKcydPyfMytfgrNxYvjpi6je44hrLFnYLSDxdcEdBv6PCifuZkRkHYA2nWybGQGcSWVqX8Z51ePSQYjx51caJFEnrvEX38Sbvsu6yCFZrBrJZMk4kWB8N7hZNVFfvKTgMNvg3wpxUgzRzHnzFLfZ7CUxWmJZ9oQb')
]

shares = [(unpack('!L', inet_aton(ip))[0], int(b58decode(share))) for ip, share in shares]
secret = hex(points_to_secret_int(shares))[2:-1]
print unhexlify(secret)

Рисунок 2 — Результат выполнения скрипта "shamir_recover_secret.py"

Победа! На всё-про-всё ушло около получаса, а выигранное время оказало существенное преимущество на наше продвижение по рейтинговой таблице.

Разделение секрета

После всей этой истории я задумался, каким образом можно было бы использовать собственные значения аргументов с помощью библиотеки secret-sharing: из коробки она не позволяет задавать произвольные «иксы».

Для добавления такого функционала я подправил интерфейс библиотеки и сохранил вывод git diff во внешний файл-патч. Теперь можно пропатчить локальную копию либы и переустановить ее через pip:

$ git clone https://github.com/blockstack/secret-sharing && cd secret-sharing
... Копируем "changes.patch" в рабочую директорию ...
$ patch -p1 < changes.patch
$ pip install --upgrade --no-deps --force-reinstall .

А затем уже можно воспользоваться таким простым скриптом, чтобы сгенерить нужные флаги для тасков в своем диапазоне «иксов»:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Usage: python2 shamir_split_secret.py

from socket import inet_aton
from struct import unpack

from secretsharing import secret_int_to_points
from base58 import b58encode
from binascii import hexlify

ip_addr = [
    '172.16.0.10',
    '172.16.0.11',
    '172.16.0.12',
    '172.16.0.13',
    '172.16.0.14',
]

x_values = [unpack('!L', inet_aton(ip))[0] for ip in ip_addr]

secret = 'ЭТО_ПРИМЕР_СЕКРЕТНОГО_СООБЩЕНИЯ_ДЛЯ_XSS_IS_!'
int_secret = int(hexlify(secret), 16)

shares = secret_int_to_points(int_secret, 5, 5, x_values=x_values)
print 'Shares:\n\n%s\n' % shares

print 'Flags:\n'
for _, y in shares:
    print 'FLAG-{%s}\n' % b58encode(str(y))

Рисунок 3 — Результат выполнения скрипта "shamir_split_secret.py"

Вместо заключения

Вот таким нехитрым образом (практически методом «пол-палец-потолок») был раскрыт способ получения секретного слова для триггера нового этапа CTF-мероприятия в обход обращения к управляющему серверу.

Спасибо за внимание, всем добра!