Interested Article - Линейный криптоанализ

aoibhe
  • 2020-08-15
  • 1

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

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

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

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

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

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

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

P i 1 ⊕ P i 2 ⊕ ⋯ ⊕ P i a ⊕ C j 1 ⊕ C j 2 ⊕ ⋯ ⊕ C j b = K k 1 ⊕ K k 2 ⊕ ⋯ ⊕ K k c , ( 1 ) {\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)}

где P n , C n , K n {\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 5 , в которой четвёртый из шести входных битов равен XOR над всеми четырьмя выходными битами с вероятностью 12/64 . Для полнораундового DES получено соотношение с вероятностью выполнения 1/2 + 2 −24 .

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

C j 1 ⊕ C j 2 ⊕ ⋯ ⊕ C j b = K k 1 ⊕ K k 2 ⊕ … ⊕ K k c . {\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 не сложно найти для одного раунда, возникает проблема с вычислением вероятности смещения при экстраполировании метода на полнораундовый шифр. В принципе, это потребовало бы от криптоаналитика просмотреть все возможные комбинации открытых текстов и ключей, что невыполнимо. Решение этой проблемы — сделать ряд предположений и приблизить вероятность, используя . Пусть мы получили линейные аппроксимации F i ( 1 ≤ i ≤ n ) {\displaystyle F_{i}\,(1\leq i\leq n)} для различных раундов, которые равны 0 с вероятностью p i {\displaystyle p_{i}} . Тогда вероятность того, что общая линейная аппроксимация F 1 ⊕ F 2 ⊕ ⋯ ⊕ F n {\displaystyle F_{1}\oplus F_{2}\oplus \dots \oplus F_{n}} равняется нулю, равна

P = 1 2 + 2 n − 1 ∏ i = 1 n ( p i − 1 2 ) . {\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 21 известных открытых текстов. Атака заняла 40 секунд.
  • На 12-раундовый DES понадобилось 2 33 известных открытых текстов и 50 часов.
  • На 16-раундовый DES потребовалось 2 43 известных открытых текстов и 50 дней.

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

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

В отличие от дифференциального криптоанализа, которому требуются выбранные открытые тексты, метод довольствуется известными открытыми текстами, что существенно увеличивает его область применения. Однако и в линейном криптоанализе иногда бывает полезно использовать выбранные открытые тексты вместо известных. Например, для 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. ↑ .
  2. , с. 82.
  3. Heys H. M. , (англ.) // / — Springer Science+Business Media , International Association for Cryptologic Research , 1996. — Vol. 9, Iss. 1. — P. 1—19. — ISSN ; —
  4. ↑ .
  5. ↑ .
  6. ↑ , Rijmen V. (англ.) // — , Springer Science+Business Media , 2014. — Vol. 70, Iss. 3. — P. 369—383. — ISSN ; —
  7. ↑ Knudsen L. R. , (англ.) // : 7th International Workshop, FSE 2000 New York, NY, USA, April 10–12, 2000 Proceedings / , J. Hartmanis , , B. Schneier — Berlin: , 2001. — P. 262—272. — (; Vol. 1978) — ISBN 978-3-540-41728-6 — ISSN ; —
  8. , с. 389.
  9. , с. 397.
  10. , с. 389, 394.
  11. , (англ.) — 1998.
  12. , с. 387.
  13. ↑ (англ.) // : 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16–17, 2001 Revised Papers / , — Berlin, Heidelberg, New York City, London: , 2001. — P. 199—211. — 364 p. — (; Vol. 2259) — ISBN 978-3-540-43066-7 — ISSN ; —
  14. Heys H. M. (англ.) // — , 1997. — Vol. 33, Iss. 10. — P. 836—837. — ISSN ; —
  15. , (англ.) // — , Springer Science+Business Media , 2002. — Vol. 45, Iss. 1. — P. 59—67. — ISSN ;
  16. Knudsen L. R. , (англ.) : NES/DOC/UIB/WP3/009/1. Public report of the NESSIE project — 2001.
  17. (неопр.) . Дата обращения: 2 декабря 2015. Архивировано из 11 августа 2017 года.
  18. , (англ.) // : The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Proceedings — 2011.
  19. (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italy, May 9–12, 1994 Proceedings / — Berlin: , 1995. — P. 366—375. — ISBN 978-3-540-60176-0 —
  20. , , (англ.) // / — IEEE , 1982. — Vol. 28, Iss. 6. — P. 858—864. — ISSN ; —
  21. (англ.) // : Proceedings / S. Goldwasser — New York City: , 1990. — P. 450—468. — (; Vol. 403) — ISBN 978-0-387-97196-4 — ISSN ; —
  22. (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991. Proceedings / — Berlin: , 1991. — P. 378—386. — ISBN 978-3-540-54620-7 —
  23. , (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Gold Coast, Queensland, Australia, December 13–16, 1992 Proceedings / , — Berlin: , 1993. — P. 143—155. — (; Vol. 718) — ISBN 978-3-540-57220-6 — ISSN ; —
  24. (англ.) // — , Springer Science+Business Media , 1997. — Vol. 12, Iss. 3. — P. 283—316. — ISSN ; —

Литература

  • (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / — 1 — Berlin: , 1993. — P. 386—397. — 465 p. — ISBN 978-3-540-57600-6 —
  • (англ.) // : 14th Annual International Cryptology Conference Santa Barbara, California, USA August 21–25, 1994 Proceedings / — Berlin: , 1994. — P. 1—11. — (; Vol. 839) — ISBN 978-3-540-58333-2 — ISSN ; —
  • Heys H. M. (англ.) // — United States of America: Taylor & Francis , 2002. — Vol. 26, Iss. 3. — P. 189—221. — ISSN ; —
  • Нильс Фергюсон, Брюс Шнайер . Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. : Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

aoibhe
  • 2020-08-15
  • 1

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

The title for the last searches