Лаборатория TJCTF CTF 2016 - earphones [misc 155]

Progressor
, 3 июня 2016

Дан зашифрованный флаг и сто равенств вида :

IONBGmcquy & fkpDdiTNxy ^ mzkirabTWJ | vSqZRztsJa ^ uGgiknmEjy | xoSIgvqmdH & FxGckrWdLm & HYBLyJWogU ^ rMxRyBwZAg + RWSvxhHlEg = sMJfBSPOjY

Операции в равенстве выполняются слева направо, без учета приоритета операций. Регистр важен. Шифр - преобразование из множества a-zA-Z в множество 0-9.

Зашифрованный флаг: Flag = gWT ZYv za gdT WbR ZSX ZZa Ghr WWZ gbQ ZZJ te GRd Nz dnF gjI gdk gYH GYz dAA GrQ ZZb ZnC GWT Ggg Zbv dnc Wqq qrh WqO gbU grQ aa gVP dGT GnL gZE gQl dbE qZH ay Wqj dqM tu gZB gdo gds zi WYq qji Gbm qjt GWx qZF Zrn dnT gQN qQa gVd WGu qGX dgq ZQQ ZVf ZZs ZVt ty aK aO gQz dbO gYo ZWJ qgi dQD gjZ qVs dGY drd qWh dhd qrQ GGF zD Wnv qbW qhA gRZ dby ZqW gQB dGg Gqj WZl ZYY dGK WQo WAW ZQU qYL Zde ZWn zm dVL dVE Zgo ZSP

Перебор в лоб - слишком большой. Идея в том, чтоб сократить перебор и количество операций.

Сокращение вариантов перебора.

  1. Различная длина чисел в правой части равенств => лидирующие нули не пишутся => все первые буквы слов не ноль. Символ j=0
  2. Флаг содержит много троек букв и немножко двоек => используются маленькие буквы в ascii (начинаются с 97)
  3. Первые буквы в двойках во флаге - 9, вторые - {7,8,9}
  4. Первые буквы в тройках - 1, вторые - {0,1,2}. Не должно превышать 128.
  5. Из формата флага получаем несколько точных значений: tjctf{...}
  6. Некоторые индивидуальные ограничения, например для одинаковых пар букв в тройках.

Сокращение количества операций.

Некоторую информацию можно получить из равенств вручную. Поскольку числа зашифрованы в десятичной системе, то работать напрямую на уровне бит можем только с последним битом - битом четности. Для этого бита: если последняя операция в левой части - конъюнкция с 0, то справа должен быть ноль: обратно, если справа в бите единица, то слева должна быть единица (из таблицы истинности конъюнкции). Тоже самое для дизъюнкции, с заменой 0 на 1.

Вручную также можно пройти дальше и захватить больше операций из равенства. Для бита четности можно проследить и операции xor (xor 1 => смена бита), и операции обычного сложения (четное + нечетное равняется нечетному и т.д.). Знание четности сокращает количество вариантов вдвое для последней буквы числа в общем случае.

Перебор

После того, как сократили количество вариантов перебора, начинаем сам перебор. Перебор я делал только для двух небольших подмножесв зашифрованных слов: для последних слов левой части равенства, если последняя операция логическое И или ИЛИ. Динамически составляем строчку, описывающую несколько вложенных циклов, и исполняем ее через eval. Далее идея - рассматриваем случай с последней операцией конъюнкция - если для всех допустимых вариантов перебора в левой части равенства для какого-то бита всегда значение 0, то и справа он должен быть всегда ноль, поэтому исключаем варианты, которые дают в правой части равенства единицу для этого бита. После такого анализа может получиться, что это выполняется только для одного единственного допустимого варианта перебора для некоторой буквы шифртекста. Мы заменяем эту расшифрованную букву на ее найденное значение и повторяем весь анализ снова. После нескольких итераций у меня расшифровался весь флаг (это оказался набор случайных букв). Код приводить не буду, он путанный и неинформативный.