Write-up Конгресс (UgraCTF2021)

Вычислено с помощью https://t.me/ch4nnel1

Содержание:

• Разбор + история
• Решение
• Эпилог

Разбор

Анализ:

Заходим на сайт читаем что-то про международный съезд математиков и бла-бла-бла, плюс так как это на английском, читать это желания еще меньше.

Но видим большую белую манящую кнопку "Join Now", жмем-с на неё. Получаем какую-то форму регистрации.

Вводим свое имя, фамилию, юзернейм и пинкод от банковской карточки, так же отмечаем, что в форме очень красивые шрифты, и что им не нравится наш пинкод, как минимум по 10 причинам, нам нужно сократить и кол-во хотя бы до 5.

Пока пробуем ввести еще несколько пинов, понимаем, что они не могут начинаться с нуля. И еще вспомнив, что это таск на ppc, сразу приходит идея сделать брутфорс этих пинов, но стоит об этом подумать и тут...

План:

Подождав чуть-чуть и попробовав ввести снова, понимаем что брутфорс не поможет, так как задержка между попытками слишком большая.

Ну так как эта задача остается ppc, а брутфорс не поможет будем придумывать другой план. Первый из таких планов был собирать последовательности в текстовый файл, при этом по-тихоньку реализуя их на питоне, чтобы банить числа входящие в них.

Писал, писал я этот скрипт (great_math.py), добавлял последовательности, вводил чиселки на сайте. Как вдруг понял, что я слишком часто пользуюсь сайтом https://oeis.org/search, и что он знает почти все нужные последовательности. А так как составлять руками их слишком медленно (примерно после 25 написанных мною проверок, оставалось 8269/8999 чисел, что не вошли не в одну последовательность)

План2.0:

Теперь надо написать скрипт, который:

• делал запросы https://oeis.org/search, парсил страничку находил последовательность
• делал запросы https://congress.q.2021.ugractf.ru/register, получал описание последовательностей и искал их на https://oeis.org/search
• сохранял, загружал данные (процесс долгий -> потеря прогресса == большой потере времени)
• распарсил файлик с последовательностями, что я собрал во время написания первого скрипта
• ну и обрабатывал эти данные засылая на проверку в первую очередь самые редко встречающиеся числа

Скрипт (great_math_recount.py) был написан даже работал, но всё было как-то долго, так что он постоял пособирал различные последовательности...

И потом в какой-то миг, он выплюнул данные от https://congress.q.2021.ugractf.ru/register и остановился, это должно было произойти только в одном случае, когда скрипт нашел нужное число. Я посмотрел на верхнее число в табличке это было 9951, ввел его в форму и ничего, ну как ничего, 10 последовательностей как обычно. Я подумал: "Окей, я где-то прокололся". Перезапустил программу и она продолжила работать дальше, не прерываясь, после чего я еще больше был убежден что это какой-то баг.

Доп. таск "По потерянным следам":

Полез я что-то в код скрипта, и понял как я лоханулся причем по 3 причинам сразу:

• проверка на подходящее число была после анализа его последовательностей -> число пропадало с верхних строк таблицы
• не было вывода этого числа
• я запустил программу заново

Правильное число было, но это было не 9951, а число, что прошло проверку перед ним.

Остановив скрипт, перейдя на https://congress.q.2021.ugractf.ru/register и введя число 9951, получим соответствующие ему последовательности.

Найдем в файле сохранения (saveconf) несколько рядом стоящих последовательностей из этого списка, и найдем последовательность перед ними на https://oeis.org/search, в ней будет только одно число близкое к 9951 это 9935.

Введем его на сайт, он не ругается. "Юху!" Заполним поля.

Нажмем кнопку send и все, мы готовы ехать на конференцию, прихватив с собой флаг. (Стоп, а когда она? Вот поэтому и надо было читать начальную страницу.)

Решение

• понять что суицид брутфорс не выход
• найти сайт https://oeis.org/search и понять, что на нем можно искать последовательности
• написать скрипт удовлетворяющий хотя бы первым двум пунктам из План2.0
• очень долго ждать
• получить что прекрасное число есть 9935
• зарегистрироваться и получить флаг

Эпилог

Я еще при решение подозревал, что реализованный мной полубрут слишком долгий и сложный для таска на 200 поинтов (в разы сложнее ppc за 300). Как оказалось есть решения куда проще:

Авторское:

• найти сайт https://oeis.org/search и что проверяющая система использует его бд
• понять что на этом сайте можно искать последовательности содержащие число n. Или скачать с него архив со всеми последоваетльностями
• проверить все числа от 1000 до 9999, 9935 будет единственным числом содержащимся в 5 или менее последовательностях

By @baksist (Recon like):

• Найти это https://oeis.org/wiki/Frequency_of_appearance_in_the_OEIS_database
• И оттуда попробовать эти чиселки

Но настоящие *вставьте сюда что-то гордо звучащее* не ищут легких путей. Так что да, мой способ самый лучший.