Введение

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

В наше время широко распространены блочные алгоритмы шифрования, такие как AES, “Кузнечик” и др. Одним из потенциально эффективных способов проведения атак на них является линейный криптоанализ. Основную концепцию данного метода изложил Мицуру Мацуи (Mitsuru Matsui) в работе “Linear Cryptoanalysis Method for DES Cipher” [1] в 90х годах. Суть данного метода будет изложена в разделе 2 данной статьи.

В качестве примера эффективного использования данного метода представлен линейный криптоанализ блочного алгоритма шифрования NUSH [2], краткая справка по которому будет приведена ниже.

Основы линейного криптоанализа

Как было написано выше суть линейного криптоанализа изложена в “Linear Cryptoanalysis Method for DES Cipher”. При использование линейного криптоанализа предполагается, что известна структура шифра и что криптоаналитик обладает достаточной статистической выборкой “шифротекст-открытый ключ”, полученной на одном ключе.

После выполнения перечисленных выше требований структуру алгоритма заменяют простой линейной функцией. Как правило анализ линейных функций куда проще, чем нелинейных функций самого шифра, что может свести задачу анализа шифра к анализу его линейной модификации. Далее из полученной системы функций криптоаналитик угадывает биты ключа с определенной вероятностью.

Пусть <x,y> = x_1*y_1+x_2*y_2+...+x_n*y_n скалярное произведение двоичных векторов по модулю 2. И пусть P,C,K открытый текст, шифротекст и ключ соответственно.

Определение 1

Линейным приближением шифра называется соотношение L:

$<P,\alpha>\oplus<C,\beta>=<K,\gamma>$

которое выполняется с вероятностью $1 \backslash 2 + \varepsilon$ Величина $\varepsilon$ преобладанием линейного соотношения, а векторы $\ \alpha, \beta, \gamma$ - называются масками.

Из определения несложно видеть, что для увеличения вероятности отгадывания ключа требуется увеличивать преобладание.

По мимо этого для приведенного ниже примера нам потребуется знание леммы Мацуи.

Лемма Мацуи (Pilling-up лемма, лемма “О набегании знаков”)

Пусть X_i где $1 \leq i \leq n$ - независимые случайные величины, принимающие значения из $\mathbb {Z}_2$ . Пусть

$P \{X_i = 0\} = 1 \backslash 2 + \varepsilon_i$

где $1 \leq \varepsilon_i \leq 1 \backslash 2$ . Тогдаслучайная величина $X_1 \oplus X_2 \oplus ... \oplus X_n$ принимает значение 0 с вероятностью $1 \backslash 2 + \varepsilon$ , где $\varepsilon = 2^{n-1} \prod^{n}_{i=1} \varepsilon_i$

Следствие 1: если $\varepsilon_j = 0$ , где $j \in \overline{1,n}$ то итоговое преобладание равно нулю.

Доказательство можно найти по ссылке.

NUSH

В 2000 году был объявлен европейский исследовательский проект для определения безопасных шифровальных алгоритмов NESSIE одним из участников, которого выступал блочный алгоритм симметричного шифрования, разработанный Анатолием Лебедевым и Алексеем Волчковым для российской компании LAN Crypto – NUSH. Алгоритм имеет несколько вариантов, отличающихся количеством раундов и длиной ключа (64, 128, 192 и 256 битов).

Его отличительной особенностью от других участников являлось отсутствие S- и P-блоков, а само шифрование проводилось только с использованием арифметических операций (XOR, AND и т.д.). В результате чего процесс шифрования ожидаемо проходит быстро. Это легко показать, если вспомнить, что сложность битовых операций O(k) , где k – битовая длина модуля.

Шифрование

Пусть N = 4n — длина шифруемого блока открытого текста P = P_0 P_1 P_2 P_3 . После чего выбирается по расписанию KS_i (start key) на основе ключа К. Затем побитово добавляется к исходному тексту: $a_0 b_0 c_0 d_0 = P_0 P_1 P_2 P_3 \oplus KS_0 KS_1 KS_2 KS_3$ . На следующем этапе происходит r-1 задаваемых уравнениями, в которых KR_i (subKey) - раундовые подключи, # — побитовая конъюнкция или дизъюнкция, выбираемая в соответствии с расписанием, C_i,S_i известные константы, $\gg j$ — циклический сдвиг вправо на j бит:

${ for ( i=1...r-1 ) \\ a_i = b_{i-1} b_i=((c_i \oplus (KR_{i-1}+C_{i-1}))+b_{i-1}) \gg S_{i-1} \\ c_i = d_{i-1} \\ d_i = a_i \oplus (b_i \# d_i)}$

Последняя итерация отличается от основных только отсутствием перестановки после вычисления выражений в правых частях равенств:

${a_r = a_{r-1} + (c_r \# d_{r-1}) \\ b_r = b_{r-1} \\ c_r = ((c_{r-1} \oplus (KR_r+C_{r-1})+b_{r-1})) \gg S_{r-1} \\ d_r = d_{r-1}}$

Выход: зашифрованный блок $M_0 M_1 M_2 M_3 = a_r b_r c_r d_r \oplus KF_0 KF_1 KF_2 KF_3$

Расшифрование

На первом итерации происходит

${d_{r-1} = d_r \\ b_{r-1} = b_r a_{r-1} = a_r - (c_r \# d_{r-1}) \\ a_{r-1} = a_r - (c_r \# d_r{r-1}) \\ c_{r-1} = c_r \gg (n- S_{r-1}) }$

После чего происходит r-1 итерация

${ for(i=r-1...1) \\ d_{i-1} = c_i \\ b_{i-1} = a_i \\ a_{i-1} = d_i - (b_i \# c_{i-1}) \\ c_{i-1} = (b_i \gg (n-S_{i-1}))-KR_{i-1}-a_{i-1}}$

Линейный криптоанализ NUSH

Из алгоритма шифрования, приведенного выше, следует, что с вероятностью 1 выполняется

${ a_i[0] = b_{i-1}[0] \quad (1) }$

Тогда обозначим через $f(x,y)=x \# y$ булевую функцию. Легко можно убедиться, что сложение по модулю два не изменяется соотношение вероятностей для p=0.75 или p=0.25 . Таким образом мы имеем линейную апроксимацию с p=0.75 или p=0.25 для d_i :

${d_i = a_{i-1}[0] \oplus b_i[0] \oplus d_{i-1}[0] \quad (2)}$

Используя (1) и (2) получаем линейную апроксимацию раундовой функции с вероятностью p=0.75

$a_i[0] \oplus b_i[0] \oplus d_i[0] = a_{i-1}[0] \oplus b_{i-1}[0] \oplus d_{i-1}[0] \oplus \theta \quad (3)$

где $\theta = 0$ если # “AND” и $\theta = 1$ если # “OR”.

Теперь получим связь между внутренними значениями открытого текста, шифротекста и ключа.

Рассмотрим связь между $a_1[0] \oplus b_1[0] \oplus d_1[0]$ и между открытым текстом и ключом. Из алгоритма шифрования получаем, что S_0 = 4 , b_1[0] зависит от c_0[0-4] , b_0[0-4] , KR_0[0-4] и . Здесь

означает последние 5 бит c_0 . Следовательно $a_1[0] \oplus b_1[0] \oplus d_1[0]$ зависит от a_0[0-4] , b_0[0] , c_0[0] , d_0[0-4] , KR_0[0-4] и C_0[0-4] . И эту зависимость можно выразить через функцию

f_1 :

$a_1[0] \oplus b_1[0] \oplus d_1[0] = f_1 \begin{pmatrix} P_0[0], P_1[0-4], P_2[0-4], P_3[0], \\ KS_0[0], KS_1[0-4], KS_2[0-4], KS_3[0], KR_0[0-4] \end{pmatrix} \quad (4)$

Можно получить связь для $a_2[0] \oplus b_2[0] \oplus d_2[0]$ и для открытого текста с ключом. Действую аналогичным образом получим, что $a_2[0] \oplus b_2[0] \oplus d_2[0]$ зависит только от $P_3[0] \oplus KS_0[0]$ , $P_2[0-11] \oplus KS_1[0-11]$ , $P_1[0-11] \oplus KS_2[0-11]$ , $P_0 [0-7] \oplus KS_2[0-7]$ , KR_0 [0-11] и KR_1[0-7] .И эту зависимость можно выразить через функцию f_2 :

$a_2[0] \oplus b_2[0] \oplus d_2[0] = f_2 \begin{pmatrix} P_0[0-7], P_1[0-11], P_2[0-11], P_3[0], \\ KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_1[0-7] \end{pmatrix} \quad (5)$

Можно получить связь для $a_3[0] \oplus b_3[0] \oplus d_3[0]$ и для открытого текста с ключом. Действую аналогичным образом получим, что $a_3[0] \oplus b_3[0] \oplus d_3[0]$ зависит только от , KS_0[0-11] , KS_1 , KS_2 , KS_3 , KR_0 , KR_1[0] и KR_2[0-11] . И эту зависимость можно выразить через функцию f_3 :

$a_3[0] \oplus b_3[0] \oplus d_3[0] = f_3(P, KS_0[0-11], KS_1, KS_2, KS_3, KR_0, KR_1, KR_2[0-11]) \quad (6)$

Теперь определим связь между $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ и для открытого текста с ключом. Из алгоритма расшифрования известно, что

${ d_{32}[0] = c_{33}[0] \\ b_{32}[0] = a_{33}[0] \\ a_{32}[0] = d_{33}[0] \oplus (b_{33}[0] \& c_{32}[0])} \quad { \space \\ (7)}$

Следовательно $a_{32}[0] b_{32}[0] c_{32}[0] d_{32}[0]$ зависит только от $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ . А они в свою очередь выражаются через $a_{34}[0], b_{34}[0], c_{34}[0], d_{34}[0]$ и через $KR_{33}[0]$ . Прослеживая и дальше связь между промежуточными значениями получим, что $a_{35}[0,1], b_{35}[0,1], c_{35}[0,1], d_{35}[0,1]$ зависят от $a_{36}[0,1], b_{36}[0,1], c_{36}[0,1], d_{36}[0,1]$ и от $KR_{35}[0]$ .

Резюмируя последние пару абзацев получим, что $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ зависит от M_0[0,1] , M_1[0-2] , M_2[0,12] , M_3[0,1] , KF_0[0] , KF_1[0,12] , KF_2[0-2] , KF_3[0,1] , $KR_{33}[0]$ , $KR_{34}[0]$ , $KR_{35}[0]$ , , . И эту зависимость можно выразить через функцию f_4 :

$a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0] = f_4 \begin{pmatrix} {M_0[0,1], M_1[0-2], M_2[0-12], M_3[0,1], \\ KF_0[0,1], KF_1[0-12], KF_2[0-2], KF_3[0,1], \\ KR_{33}[0], KR_{34}[0], KR_{35}[0] } \end{pmatrix} \quad (8)$

А зависимость для $a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0]$ можно записать через f_5 :

$a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0] = f_5 \begin{pmatrix} {M_0[0-9], M_1[0-11], M_2[0-12], M_3[0,1], \\ KF_0[0,1], KF_1[0-12], KF_2[0-11], KF_3[0-9], \\ KR_{32}[0], KR_{33}[0], KR_{34}[0], KR_{35}[0-9] } \end{pmatrix} \quad (9)$

Теперь перейдем непосредственно к линейному криптоанализу. Принимая во внимание (3) заметим, что 29-раундовая линейная апроксимация

$a_2[0] \oplus b_2[0] \oplus d_2[0] = a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0] \quad (10)$

содержит вероятность $1/2+2^{-30}$ согласно лемме Мацуи. Эта линейная апроксимация может быть записана через введенные ранее функции

${f_2(P, KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_1[0-7]) = \\ = f_5 \begin{pmatrix} {M, \\ KF_0[0,1], KF_1[0-12], KF_2[0-11], KF_3[0-9], \\ KR_{32}[0], KR_{33}[0], KR_{34}[0], KR_{35}[0-9] } \end{pmatrix}} { \space \\ \space \\ \quad (11)}$

Из расписания ключей NUSH известно, что (11) содержит m_0 -бит ключа. Восстановим их по алгоритму, приведенному ниже.

Шаг 1. Для каждого кандидата в ключи $K^i(i=1,...,2^{m_0})$ через T_i обозначим кол-во открытых текстов, удовлетворяющих (11).

Шаг 2. Если T_j максимальное значение из всех T_i , тогда сохранить K^j .

Шаг 3. Остальные биты ключа ключа восстанавливаются, используя урезанную линейную апроксимацию раундов или методом исключения.

Вывод

В статье представлена основная концепция линейного криптоанализа и рассмотрен пример его применения в анализе алгоритма шифрования NUSH.

Литература

1. Mitsuru Matsui, Linear cryptoanalysis method for DES cipher, Advances in Cryptogy-Eurocrypt’93, Berlin: Springer-Verlag, 1993, 386-397.

2. Wu Wenling & Feng Dengguo, Linear cryptoanalysis of NUSH block cipher, Science in China (Seria F), February 2002, Vol. 45, № 1.

3. M. Heys, A Tutorial on Linear and Differential Cryptoanalysis, Cryptologia, June 2001, Vol. 26 №3.

4. https://www.youtube.com/watch?v=nEHVfeaPjNw

Линейный криптоанализ на примере блочного алгоритма шифрования NUSH