Лаборатория ASIS CTF Quals 2016 - QROP [139]

Progressor
, 10 May 2016

Whose idea was to multiply these QR codes? Give me the originals already!

Дано несколько картинок в формате png, на картинках угадываются QR коды. Как видно из названий файлов и описания задания, над картинками проводились операции xor (или difference) и multiply (дизъюнкция).

f_3_QR + f_1_QR.png
f_3_QR + f_2_QR.png
f_3_QR x f_1_QR.png
f_3_QR x f_2_QR.png
f_4_QR + f_3_QR.png
f_4_QR x f_3_QR.png
f_5_QR + f_3_QR.png
f_5_QR x f_3_QR.png
f_6_QR + f_1_QR.png
f_6_QR + f_2_QR.png
f_6_QR + f_3_QR.png
f_6_QR + f_4_QR.png
f_6_QR + f_5_QR.png
f_6_QR x f_1_QR.png
f_6_QR x f_2_QR.png
f_6_QR x f_3_QR.png
f_6_QR x f_4_QR.png
f_6_QR x f_5_QR.png

Для примера:

f6 + f1: 

f6 x f1: 

Итак, видим, что нужно восстановить 6 картинок. Для картинок f3 и f6 есть все попарные ксоры(+)  и дизъюнкции(x).

Первоначальный план был решить эту систему уравнений относительно шести неизвестных, пока до меня не дошло, что это не система уравнений:).

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

AB = AxB + (A+B)

И план такой: имеем попарные дизъюнкции и конъюнкции для f3 и f6 картинок. Считаем белый пиксель нулем, черный единицей. По таблице истинности дизъюнкции, единственный ноль - когда оба аргумента ноль, то есть если в картинке-дизъюнкции белый пиксель, то он белый в обеих исходных картинках. Для конъюнкции наоборот, если пиксель черный, то он черный для обеих исходных картинок. Так что берем картинку с красным фоном и начинаем вносить в нее белые пиксели из попарных дизъюнкций. После этого начинаем цикл по попарным конъюнкциям - и берем оттуда черные пиксели.

В реальности, только белых пикселей хватило, чтобы восстановить и распознать qr код с шестой картинки:

Когда я добавил туда черные пиксели из конъюнкций, qr код изменился незначительно:

После этого просто ксорим восстановленную шестую картинку с "f_6_QR + f_1_QR.png" и получаем первую картинку, ну и потом последовательно все остальные. QR код сам исправляет некоторое количество ошибок, так что всё получилось.