Лаборатория RuCTF 2011 Quals. Crypto 300

Progressor
, 28 February 2011

Дана картинка и задание - "Английским поэтам и не снилось!". На картинке - черно-белая мешанина пикселей. 

Видим, что "пиксель" - это квадратик рамером 4х4 пикселя. Нигде не смещены, все нормально, можно с ними работать как с пикселями. Опять же глазами видно, что выделяются блоки по 8х8 "пикселей". Таким образом, размер картинки 1280х1888 пикселей, или 320х472 "пикселя", или 40х59 блоков. Считаем статистику блоков - их слишком много разных, то есть просто подстановка блок<->символ не катит. При этом замечаем, что чисто черных блоков намного больше чем других - их там больше ста. Рисуем новую картинку, на которую помещаем только чисто черные блоки - получаем довольно регулярную структуру. Ломаем мозг, ничего не придумываем.

Потом приходит мысль: один блок это аж 8х8 бит, зачем столько много. Решил посчитать статистику черных и белых пикселей в блоках - получаем число от 0 до 64. Группируем по этим числам и считаем статистику - мм, что-то есть. Причем черных опять же больше всех, и есть еще один белый и он в самом конце картинки. Имеем - 64 числа от 1 до 64, и уникальный единственный символ в конце. Это наводит на безумную мысль, что количеством черных пикселей в блоках закодирована строчка base64, а в конце дополняющий символ "=" (он может быть только в конце, от 0 до 3 штук). Лезем в википедию, смотрим формат base64, а именно порядок символов в алфавите. В соответствии с ним пытаемся составить строку, декодируем - получаем фигню. Меняем черные биты на белые, составляем, декодируем - получается фигня. Но в этой фигне пристальный взгляд среди непечатных символов усматривает куски печатных символов, похожие на слова, приемлемо разделенные пробелами. Долгая медитация над этим текстом - а решал я дооолго - вдруг преобразовала нечто вроде "nzci:k" в "znick:". Оп! Быстренько пишем переставлялку символов в каждой паре - получаем куски осмысленного текста!

Но нечитаемые символы никуда не делись. Стало ясно, что мы на верном пути, но как раскодировать остальное? Долгие мытарства, повороты картинки, зеркальное отображение, перетасовка алфавита - безрезультатно. В очередной раз исправляя свою программку, я нечаянно не исправил индексы циклов, и с оригинальным алфавитом натравил на оригинальную картинку. И тут получил другую часть текста! Стал думать, почему такое произошло, и тут вспомнил, что над base64 можно издеваться, вставляя-убирая символы. Поскольку 3 символа исходного текста кодируются 4 символами в base64, изменения в пределах четверки символов кодированного текста скажутся только на трех соответствующих символах исходного текста, остальное останется без изменений. Но если вставлять или убирать кодированные символы, мы нарушаем разбиение на четверки и корраптится весь последущий текст. Тут так и было - вставлялись левые символы, текст корраптился, но как только левых символов оказывалось кратное 4 число, то текст восстанавливался - вот вам и куски печатного текста среди непечатного. Вопрос - какие символы левые? Начал сначала на глаз удалять символы и декодировать, получал все новые куски текста. А потом вспомнил про регулярную структуру из черных блоков. Просто все такие блоки удалить нельзя - все же валидный символ, но на картинке было видно две диагонали из этих квадратиков. Их-то я и удалил и получил всю The Infamous RuCTF Poem. Ну совсеееем было непонятно, что делать с этим текстом, а дело было вечером - и я лег спать.

Утром в универе набросились свежими мозгами толпой на этот текст. Две версии - либо какие-то уравнения, либо программа. Выбрали версию с программой. Вроде как есть переменные, присваивания, что-то похожее на запись-считывание... Пока анализировали вручную, я вбил-таки в гугл строчку "Speak your mind". Ничего. Вбил "You are as small as a fine tiny small cunning happy honest King!" и получил ссылки на эзотерический язык программирования Shakespeare! Вот оно. Потом мы еще 20 минут искали транслятор, читали спецификацию и заменяли znick на Romeo, bay на Othello... Запускаем и получаем ответ. Вуаля.