Немного веселой криптографии никогда не повредит, так что давай разберемся с одной из относительно простых, но юзабельных атак на так называемый двухразовый блокнот (two-time pad). Сначала, впрочем, пройдемся по терминологии и принципам работы шифра.
Одноразовый блокнот, или one-time pad (OTP), — это такой «поточный» шифр. Его суть сводится к тому, что исходные данные просто ксорятся (XOR) со случайным ключом. При этом ключ должен быть такой же длины, что и данные, и никогда повторно не использоваться. И все. Полученный текст зашифрован, и расшифровать его без ключа никто не сможет.
Как видишь, идея проста, но при этом надежна. Однако у этого шифра есть серьезный минус — ключ не должен повторяться (есть, конечно, и другие минусы, такие как проблемы распространения ключей, но для нашей задачки это не важно). Проблема усугубляется, когда необходимо часто передавать данные или данных много (например, когда этот метод шифрования используется в каком-нибудь сетевом протоколе). Если ключ применялся повторно, то возникает ситуация two-time pad — «блокнот» используется два и более раз. Если атакующий перехватил два сообщения, которые зашифрованы одним ключом, то он может попытаться провести атаку Crib Drag. Чтобы понять ее идею, давай пройдемся по всем пунктам шифрования данных.
Итак, у нас есть:
M1, M2 — первое и второе незашифрованные (изначальные) сообщения;
C1, C2 — первое и второе зашифрованные сообщения, известные атакующему;
K — ключ, который используется для шифрования обоих сообщений.Сообщения же шифруются следующим образом:
C1 = M1^K
C2 = M2^KКак ты знаешь, XOR — это простейшая операция и, что важно, «обратимая»:
K = C1^M1
K = C2^M2Получаем что-то вроде классического уравнения. Соединим части вместе:
C1^M1 = C2^M2Проще не стало. Но давай вспомним, что C1 и C2 известны атакующему, и сведем все в одну сторону:
M1 = C1^C2^M2Итого — мы видим, что любое из изначальных сообщений является результатом XOR С1, С2 и M2. «Уравнение» выглядит нерешаемым, но это не всегда так.
Возможность расшифровки сообщений требует от нас некоторых допущений и воображения. Но для начала необходимо вспомнить, что XOR — это побитовая операция. То, что мы ксорим одни байты, не влияет на другие байты.
Допущение заключается в том, что нам хоть что-то известно про передаваемые данные. Простейший вариант — мы предполагаем, что в сообщениях передается какой-то текст. Тогда внутри сообщений будут строчные и заглавные буквы, а также пробелы.
А теперь сама атака. Изначально мы имеем результат XOR C1 и C2 (для простоты назовем С12), а также предполагаем какое-то значение в M2 и ксорим его С12. При этом мы помним, что в M2 мы используем только буквы, но что важнее — в результате ксора M2 и С12 тоже должны быть буквы. Если их нет и мы видим какие-то другие символы, следовательно, предполагаемое значение отсутствует в изначальном сообщении (и в M1, и в M2) или оно находится в другой позиции. Таким образом, мы можем значительно сократить количество вариаций. Остается добавить, что человеческие языки тоже не отличаются абсолютной рандомностью: имея часть слова, мы можем с определенной точностью предположить его окончание; какие-то буквы появляются чаще, чем другие.
Пример можно еще больше упростить. Мы можем брать последовательно все буквы и подставлять во все позиции сообщения. Например, буква а:
M1[i]= С12[i]^'a'Если в результате (M1[i]) мы видим не букву, то мы можем быть уверены, что ни в M1, ни в M2 в этой позиции (i) нет буквы а.
С практической точки зрения этот пример может показаться нереалистичным. Но это не совсем так. При передаче большого количества данных повторы ключей случаются чаще, чем хотелось бы. Тогда атака превращается в many time pad, что еще больше сокращает вариативность изначальных данных. Эта техника, в частности, применяется для атак на протоколы PPTP и WEP.
К тому же данная атака может быть использована и в «обратном» виде, когда у нас есть одно сообщение, но с разными ключами. В таком случае она будет нацелена на получение значения ключа.
