Лаборатория ASIS CTF Quals 2016 - Broadcasting [74]

Progressor
, 10 мая 2016

Far away from earth, a few weird buddies want to send a message to their friends in earth! We managed to grab 124 messages!! Nevertheless some noisy stuff worked against us, can you decode the message?

Итак, имеем 124 сообщения по 38 байт. После сбора всевозможной статистики, появилась идея, что передается всё-таки одно сообщение 124 раза с разными преобразованиями - и скорее всего, это флаг.Наш козырь в том, что флаг начинается с символов "ASIS{". 

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

Затем я заметил, что самый популярный символ на первой позиции среди всех сообщений -  ">" - в битах 00111110. А мы хотим получить символ "A" - 01000001. Количество подряд идущих нулей и единиц насторожило, и следующие символы подтвердили догадку:

10101100 10110110 10101100 10000100
01010011 01001001 01010011 01111011
S        I        S        {

Первая строка бит - самые популярные символы из сообщений на соотвествующих позициях, вторая строка бит - то, что хотели бы получить.

То есть правило преобразования - инверсия всех бит и обнуление первого бита - (X^255)&127.

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