Линейный криптоанализ - NiNa.Az

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

Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Также пригоден для атак на потоковые шифры.

Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем.

Принцип работы

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

Построение линейных уравнений

Смысл алгоритма состоит в получении соотношений следующего вида:

${\displaystyle P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}},\qquad (1)}$

где ${\displaystyle P_{n},C_{n},K_{n}}$ — n-ые биты текста, шифртекста и ключа соответственно.

Данные соотношения называются линейными аппроксимациями. Вероятность P справедливости такого соотношения для произвольно выбранных битов открытого текста, шифртекста и ключа примерно равна 1/2. Такими соотношениями, вероятность которых заметно отличается от 1/2, можно пользоваться для вскрытия алгоритма.

Идея линейного криптоанализа — определить выражения вида (1), которые имеют высокую или низкую вероятность возникновения. Если алгоритм шифрования имеет высокую частоту выполнения уравнения (1), или напротив, уравнение выполняется с низкой частотой, то это свидетельствует о бедной способности рандомизации шифра. Если вероятность выполнения уравнения (1) равна p, то вероятность смещения p − 1/2. Чем больше величина вероятности смещения |p − 1/2|, тем лучше применимость линейного криптоанализа с меньшим количеством открытых текстов, необходимых для атаки.

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

Далее рассматривается алгоритм нахождения наилучшей линейной аппроксимации для одного раунда. В блочных шифрах анализ преимущественно концентрируется на S-блоки, так как они являются нелинейной частью шифра. Так как S-блок принимает на входе m битов и возвращает n битов, от криптоаналитика требуется построить 2^m+n аппроксимаций. Чтобы найти вероятность для одной аппроксимации, на вход S-блоку даются все 2^m возможных входных значений и идёт подсчёт, сколько раз данная аппроксимация верна для входных и выходных битов. Полученное количество совпадений делится на 2^m. В алгоритме DES наибольшую вероятность смещения имеет линейная аппроксимация для таблицы S₅, в которой четвёртый из шести входных битов равен XOR над всеми четырьмя выходными битами с вероятностью 12/64. Для полнораундового DES получено соотношение с вероятностью выполнения 1/2 + 2⁻²⁴.

Линейный криптоанализ имеет одно очень полезное свойство: при определённых условиях (например, когда об открытом тексте известно, что он состоит из символов в кодировке ASCII) можно свести соотношение (1) к уравнению вида:

${\displaystyle C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \ldots \oplus K_{k_{c}}.}$

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

Лемма о набегании знаков

Хотя аппроксимацию с наибольшим отклонением от 1/2 не сложно найти для одного раунда, возникает проблема с вычислением вероятности смещения при экстраполировании метода на полнораундовый шифр. В принципе, это потребовало бы от криптоаналитика просмотреть все возможные комбинации открытых текстов и ключей, что невыполнимо. Решение этой проблемы — сделать ряд предположений и приблизить вероятность, используя ^[англ.]. Пусть мы получили линейные аппроксимации ${\displaystyle F_{i}\,(1\leq i\leq n)}$ для различных раундов, которые равны 0 с вероятностью ${\displaystyle p_{i}}$. Тогда вероятность того, что общая линейная аппроксимация ${\displaystyle F_{1}\oplus F_{2}\oplus \dots \oplus F_{n}}$ равняется нулю, равна

${\displaystyle P={\frac {1}{2}}+2^{n-1}\prod _{i=1}^{n}(p_{i}-{\frac {1}{2}}).}$

Получение битов ключа

Как только получена линейная аппроксимация, можно применить прямой алгоритм и, используя пары открытый текст-шифртекст, предположить значения битов ключа. При этом логично использовать максимально эффективное соотношение, то есть такое, для которого отклонение вероятности P от 1/2 максимально.

Для каждого набора значений битов ключа в правой части уравнения (1) вычисляется количество пар открытый текст-шифртекст T, для которых справедливо равенство (1). Тот кандидат, для которого отклонение T от половины количества пар открытый текст-шифртекст — наибольшее по абсолютному значению, полагается наиболее вероятным набором значений битов ключа.

Применение

Линейный криптоанализ изначально разрабатывался для атак на блочные шифры, но применим и к потоковым. Самим разработчиком было подробно изучено его применение к DES.

Применение к DES

Эксперименты Мицуру Мацуи по атакам по открытому тексту (вычисления проводились на HP9750 66 МГц) дали следующие результаты:

• На 8-раундовый DES понадобилось 2²¹ известных открытых текстов. Атака заняла 40 секунд.
• На 12-раундовый DES понадобилось 2³³ известных открытых текстов и 50 часов.
• На 16-раундовый DES потребовалось 2⁴³ известных открытых текстов и 50 дней.

В 2001 году Паскаль Жюно (фр. Pascal Junod) провёл ряд экспериментов, чтобы определить сложность атаки. В результате оказалось, что в действительности атака на 16-раундовый DES может успешно применяться при наличии 2³⁹—2⁴¹ известных текстов.

При большом количестве раундов шифра линейный криптоанализ, как правило, используется вместе с методом «грубой силы» — после того, как определённые биты ключа найдены с помощью линейного криптоанализа, проводится исчерпывающий поиск по возможным значениям остальных битов. У такого подхода есть несколько оснований: во-первых, наилучшие линейные аппроксимации позволяют найти значения лишь некоторых битов ключа, во-вторых, количество требуемых открытых текстов в таком случае меньше, а перебор оставшихся битов ключа занимает меньше времени.

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

Применение к другим методам шифрования

Помимо DES и FEAL, известны и другие алгоритмы, подверженные линейному криптоанализу, например:

1. Линейный криптоанализ действует против алгоритма RC5 в случае, если искомый ключ шифрования попадает в класс слабых ключей.
2. Алгоритмы NUSH и NOEKEON также вскрываются методом линейного криптоанализа.
3. Расширение линейного криптоанализа, основанное на некоррелирующих между собой линейных аппроксимациях, применимо для вскрытия 6-раундовых AES-192 и AES-256, а также 13-раундового CLEFIA-256.

Защита от линейного криптоанализа

Для атаки на блочный шифр с помощью линейного криптоанализа достаточно, как было описано выше, получить линейное соотношение, существенно смещённое по вероятности от 1/2. Соответственно, первая цель при проектировании шифра, стойкого к атаке, — минимизировать вероятностные смещения, убедиться, что подобное соотношение не будет существовать. Другими словами, необходимо сделать так, чтобы блочный шифр удовлетворял строгому лавинному критерию (СЛК). Говорят, что блочный шифр удовлетворяет СЛК, если при любом изменении текста или ключа в получающемся шифртексте ровно половина битов меняет своё значение на противоположное, причём каждый бит изменяется с вероятностью 1/2. Обычно это достигается путём выбора высоко нелинейных S-блоков и усилением диффузии.

Данный подход обеспечивает хорошее обоснование стойкости шифра, но, чтобы строго доказать защищённость от линейного криптоанализа, разработчикам шифров необходимо учитывать более сложное явление — эффект линейных оболочек (англ. linear hull effect). Следует заметить, что шифры, которые оптимальны против некоторого узкого класса атак, обычно слабы против других типов атак. К примеру, известно расположение S-блоков в DES, при котором существенно увеличивается стойкость к линейному криптоанализу, но ухудшается стойкость к дифференциальному криптоанализу.

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

См. также

• Дифференциальный криптоанализ

Примечания

1. Matsui, 1993.
2. Фергюсон, Шнайер, 2004, с. 82.
3. Heys H. M., Tavares S. E. Substitution-permutation networks resistant to differential and linear cryptanalysis (англ.) // Journal of Cryptology / I. Damgård — Springer Science+Business Media, International Association for Cryptologic Research, 1996. — Vol. 9, Iss. 1. — P. 1—19. — ISSN 0933-2790; 1432-1378 — doi:10.1007/BF02254789
4. Heys, 2002.
5. Matsui, 1994.
6. Bogdanov A., Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers (англ.) // Designs, Codes and Cryptography — Springer US, Springer Science+Business Media, 2014. — Vol. 70, Iss. 3. — P. 369—383. — ISSN 0925-1022; 1573-7586 — doi:10.1007/S10623-012-9697-Z
7. Knudsen L. R., Mathiassen J. E. A Chosen-Plaintext Linear Attack on DES (англ.) // Fast Software Encryption: 7th International Workshop, FSE 2000 New York, NY, USA, April 10–12, 2000 Proceedings / G. Goos, J. Hartmanis, J. van Leeuwen, B. Schneier — Berlin: Springer Berlin Heidelberg, 2001. — P. 262—272. — (Lecture Notes in Computer Science; Vol. 1978) — ISBN 978-3-540-41728-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-44706-7_18
8. Matsui, 1993, с. 389.
9. Matsui, 1993, с. 397.
10. Matsui, 1993, с. 389, 394.
11. Kruppa H., Shah S. U. A. Differential and Linear Cryptanalysis in Evaluating AES Candidate Algorithms (англ.) — 1998.
12. Matsui, 1993, с. 387.
13. Junod P. On the Complexity of Matsui’s Attack (англ.) // Selected Areas in Cryptography: 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16–17, 2001 Revised Papers / S. Vaudenay, A. M. Youssef — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 2001. — P. 199—211. — 364 p. — (Lecture Notes in Computer Science; Vol. 2259) — ISBN 978-3-540-43066-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-45537-X_16
14. Heys H. M. Linearly weak keys of RC5 (англ.) // Electronics Letters — IEEE, 1997. — Vol. 33, Iss. 10. — P. 836—837. — ISSN 0013-5194; 1350-911X — doi:10.1049/EL:19970601
15. Wu W., Feng D. Linear cryptanalysis of NUSH block cipher (англ.) // Science in China Series F: Information Sciences — Science China Press, Springer Science+Business Media, 2002. — Vol. 45, Iss. 1. — P. 59—67. — ISSN 1674-733X; 1869-1919
16. Knudsen L. R., Raddum H. On Noekeon (англ.): NES/DOC/UIB/WP3/009/1. Public report of the NESSIE project — 2001.
17. Security Evaluation of NESSIE First Phase (D13)  (неопр.). Дата обращения: 2 декабря 2015. Архивировано из оригинала 11 августа 2017 года.
18. Röck A., Nyberg K. Exploiting Linear Hull in Matsui's Algorithm (англ.) // WCC 2011: The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Proceedings — 2011.
19. Matsui M. On correlation between the order of S-boxes and the strength of DES (англ.) // Advances in Cryptology — EUROCRYPT '94: Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italy, May 9–12, 1994 Proceedings / A. D. Santis — Berlin: Springer Berlin Heidelberg, 1995. — P. 366—375. — ISBN 978-3-540-60176-0 — doi:10.1007/BFB0053451
20. Olsen J. D., Scholtz R. A., Welch L. R. Bent-function sequences (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1982. — Vol. 28, Iss. 6. — P. 858—864. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1982.1056589
21. Forrié R. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition (англ.) // Advances in Cryptology — CRYPTO ’88: Proceedings / S. Goldwasser — New York City: Springer New York, 1990. — P. 450—468. — (Lecture Notes in Computer Science; Vol. 403) — ISBN 978-0-387-97196-4 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34799-2
22. Nyberg K. Perfect nonlinear S-boxes (англ.) // Advances in Cryptology — EUROCRYPT ’91: Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991. Proceedings / D. W. Davies — Berlin: Springer Berlin Heidelberg, 1991. — P. 378—386. — ISBN 978-3-540-54620-7 — doi:10.1007/3-540-46416-6_32
23. Seberry J., Zhang X. Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion (Extended Abstract) (англ.) // Advances in Cryptology — AUSCRYPT '92: Workshop on the Theory and Application of Cryptographic Techniques Gold Coast, Queensland, Australia, December 13–16, 1992 Proceedings / J. Seberry, Y. Zheng — Berlin: Springer Berlin Heidelberg, 1993. — P. 143—155. — (Lecture Notes in Computer Science; Vol. 718) — ISBN 978-3-540-57220-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-57220-1
24. Adams C. M. Constructing Symmetric Ciphers Using the CAST Design Procedure (англ.) // Designs, Codes and Cryptography — Springer US, Springer Science+Business Media, 1997. — Vol. 12, Iss. 3. — P. 283—316. — ISSN 0925-1022; 1573-7586 — doi:10.1023/A:1008229029587

Литература

• Matsui M. Linear Cryptanalysis Method for DES Cipher (англ.) // Advances in Cryptology — EUROCRYPT ’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth — 1 — Berlin: Springer Berlin Heidelberg, 1993. — P. 386—397. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_33
• Matsui M. The First Experimental Cryptanalysis of the Data Encryption Standard (англ.) // Advances in Cryptology — CRYPTO’94: 14th Annual International Cryptology Conference Santa Barbara, California, USA August 21–25, 1994 Proceedings / Y. G. Desmedt — Berlin: Springer Berlin Heidelberg, 1994. — P. 1—11. — (Lecture Notes in Computer Science; Vol. 839) — ISBN 978-3-540-58333-2 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48658-5_1
• Heys H. M. A Tutorial on Linear and Differential Cryptanalysis (англ.) // Cryptologia — United States: Taylor & Francis, 2002. — Vol. 26, Iss. 3. — P. 189—221. — ISSN 0161-1194; 1558-1586 — doi:10.1080/0161-110291890885
• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.