Криптоанализ

Криптоанализ — это изучение криптографических алгоритмов и методов. Базовая цель — тем или иным способом сломать криптографические алгоритмы. Например, атакующий мог получить сведения о некоторых шифртекстах и соответствующих им открытых текстах. Затем он пытается использовать эту информацию для нахождения использованного ключа. В другой постановке предполагается, что у атакующего есть только некоторые шифртексты, по которым нужно найти ключ. Всегда предполагается, что атакующий знает все детали процессов шифрования и расшифрования; неизвестен только секретный ключ. Если это предположение нельзя делать, метод шифрования считается очень слабым.

Рассмотрим шифр замены. Теперь каждое вхождение буквы ’e’ в открытом тексте шифруется как одна и та же буква в шифртексте, скажем ’Å’. Поскольку ’e’ — самая распространенная буква в английском языке, ’Å’ должна быть одной из самых распространенных букв шифртекста. Поэтому можно предположить, что распространенные буквы в шифртексте соответствуют распространенным буквам языка открытого текста, и использовать это для обоснованных догадок о том, как шифруется каждая буква. Такой криптоаналитический подход называется частотным анализом.

Тот же подход нельзя использовать против OTP. Если ключ выбран случайно, то 0 и 1 в шифртексте появляются в среднем одинаково часто. Это происходит независимо от того, насколько часто 1 встречается в открытом тексте. Фактически любой шифртекст мог бы получиться из любого открытого текста при подходящем ключе. Предположим, что известный бит шифртекста равен C. Тогда соответствующий бит открытого текста мог бы быть либо C, если бит ключа равен нулю, либо 1-C, если бит ключа равен единице. Поэтому знание шифртекста не дает атакующему новой информации об открытом тексте. Это означает, что OTP является безусловно безопасным.

Для OTP мы применили постановку, где атакующий знает только шифртекст. Если атакующий знает и шифртекст, и соответствующий открытый текст, он может легко восстановить использованный ключ. Однако взлом OTP в такой постановке не релевантен, потому что восстановленный ключ не используется для шифрования ничего, кроме открытого текста, который атакующий уже знает.

Режимы работы

Блочный шифр, например AES, используется для шифрования блоков определенного размера. Что делать, если сообщение длиннее этого размера?

Самый простой способ зашифровать длинное сообщение — взять первый блок, зашифровать его с использованием ключа и получить первый блок шифртекста, затем взять второй блок, зашифровать его с тем же ключом и получить второй блок шифртекста и т. д. Этот подход является одним из режимов работы блочного шифра и называется Electronic Codebook (ECB). Он самый простой, но часто может быть сломан частотным анализом. Атакующий замечает, что если один и тот же блок открытого текста зашифрован дважды, то два шифртекста также одинаковы. Это происходит, например, если открытый текст содержит распространенный короткий шаблон вроде 'OK'.

Другие режимы работы избегают этой проблемы, используя дополнительный вход помимо открытого текста и ключа. Например, для этой цели могут использоваться ранее вычисленные блоки шифртекста или счетчики. В нашем HTTPS-примере (TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384_256 bit keys,TLS 1.2) используется алгоритм AES в Galois/Counter Mode. Длина ключа — 256 бит.

Следующие 3 упражнения нужно выполнять по порядку.

Атака padding oracle

Атака padding oracle показывает, что крошечного количества дополнительной информации может быть достаточно, чтобы сломать шифр.

Ранние версии реализаций CBC-расшифрования возвращали отправителю сообщение об ошибке, если padding отправленного сообщения был корректным. Если у нас есть возможность отправлять собственные сообщения в расшифровщик, этой информации достаточно, чтобы сломать шифрование CBC. Более того, взлом не зависит от лежащего в основе блочного шифра.

Предположим, что у нас есть oracle, который по шифртексту сообщает, имеет ли расшифрованное сообщение корректный padding. Обратите внимание, что мы не видим расшифрованное сообщение, а только наблюдаем, является ли padding корректным.

Предположим, что у нас есть два блока шифртекста $C_1$ и $C_2$, каждый длиной 8. Запишем $A = decrypt(C_2)$. Из предыдущего упражнения мы знаем, что $P_2 = C_1 \oplus A$. Если мы можем найти $A$, то можем найти $P_2$.

Сосредоточимся на поиске последнего байта в $A$. Для $A[8]$ существует 256 возможных значений. Рассмотрим 256 разных шифртекстов вида $(M_i, C_2)$, где $M_i$ — массив нулей, кроме последнего элемента, где $M_i[8] = i$. Пусть $Q_i = M_i \oplus A$ будет 2-м блоком расшифрованного сообщения $(M_i, C_2)$.

Обратите внимание, что $Q_i[8]$ различается для каждого $i$; существует индекс $c$, для которого $Q_c[8] = 1$. Если мы знаем $c$, то можем вывести $A[8]$, поскольку $A[8] = c \oplus 1$.

Мы не знаем $c$, но знаем, что, поскольку $Q_c[8] = 1$, $(M_c, C_2)$ имеет корректный padding. Поэтому, чтобы найти $c$, можно проверить каждый $(M_i, C_2)$ с oracle и посмотреть, какие шифртексты дают корректный padding.

Есть небольшое осложнение: oracle может найти несколько сообщений с корректным padding. Например, если $Q_j[7] = Q_j[8] = 2$ или $Q_j[6] = Q_j[7] = Q_j[8] = 3$, то $(M_j, C_2)$ имеет корректный padding. Обратите внимание, что $Q_i[7]$ не меняется при изменении $i$. Это означает, что oracle может найти максимум 2 сообщения с корректным padding (понимаете почему?).

Получается следующий подход. Мы проверяем 256 шифртекстов $(M_i, C_2)$, чтобы увидеть, какие из них имеют корректный padding. Если такой только один, мы нашли $c$ и можем найти $A[8]$. Если их два, скажем $c$ и $j$, нужно понять, какой из них какой. Это можно сделать, изменив $M_c[7]$ и $M_j[7]$ на другое значение, например выполнив xor с 1. Это изменит 7-й байт расшифрованного сообщения. Пусть $M'_c$ и $M'_j$ будут измененными шифртекстами. Тогда $(M'_c, C_2)$ все еще будет давать корректный padding, а $(M'_j, C_2)$ больше не будет иметь корректный padding, поскольку последний и предпоследний байт в расшифрованном сообщении больше не совпадают. Итого, мы можем найти $c$ и решить $A[8]$.

После того как $A[8]$ найден, можно перейти к поиску $A[7]$. Для этого задаем $M_i[8] = A[8] \oplus 2$ и $M_i[7] = i$. С помощью oracle можно найти индекс $c$, для которого $Q_c[7] = A[7] \oplus c = 2$, что дает корректный padding. Обратите внимание, что, в отличие от случая с последним байтом, oracle найдет только один индекс (понимаете почему?). Нахождение $c$ позволяет решить $A[7]$. Теперь можно перейти к $A[6]$, задав $M_i[8] = A[8] \oplus 3$, $M_i[7] = A[7] \oplus 3$ и $M_i[6] = i$. Мы продолжаем, пока не найдем $A$, что даст нам $P_2$.

Если шифртекст содержит больше двух блоков, скажем $C_1, \ldots, C_n$, мы можем расшифровать каждый отдельный блок, например $C_j$, запуская предыдущую процедуру для каждой пары $(C_{j - 1}, C_j)$.

Не забудьте проверить свои баллы в индикаторе в правом нижнем углу материала!