КУРС САМОПОДГОТОВКИ ПО КРИПТОАНАЛИЗУ БЛОЧНЫХ ШИФРОВ

Брюс Шнайер, перевод Быбин С.С. ЗАО "ТЕЛРОС"

Публикации, доступные в интернет и упоминаемые в работе (локальная копия).

1. Введение

Со времени написания “Прикладной криптографии”, меня часто просят порекомендовать книгу по криптоанализу. Я с сожалением отвечаю, что пока это несколько хороших книг по криптографии, нет книг, хороших или плохих, по криптоанализу. Это пробел, который я не смогу заполнить в ближайшем будущем, криптоанализ такая быстро развивающаяся отрасль, что любая книга о методах криптоанализа устареет к моменту издания. И даже если книга будет содержать что-нибудь актуальное, этого будет слишком мало для обучения криптоанализу.

Существует только один путь обучения криптоанализу - через практику. Студент просто взламывает алгоритм за алгоритмом, исследуя новые методы и модифицируя существующие. Изучение результатов криптоанализа помогает, но не заменяет опыт.

Это рождает другой вопрос: Где получить практику? Интернет бесконечный источник посредственных алгоритмов, некоторые можно даже найти в академической литературе, но начинающий студент - криптоаналитик не имеет возможности определить, какой алгоритм подходит для обучения, а какой превосходит его возможности. Ответ только один - пробовать взламывать уже взломанные алгоритмы (без подглядывания в результаты взлома).

Сейчас вопрос становится так: какие шифры необходимо попробовать взломать и в какой последовательности? Эта статья - моя попытка ответа на этот вопрос и, я надеюсь, это поможет изучению криптоанализа.

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

Для этого я составил список опубликованных алгоритмов и результатов криптоанализа в определенном порядке - по типу криптоанализа и сложности. Задача студента прочитать описание алгоритма и попытаться воспроизвести результат опубликованного криптоанализа. (Определенно более сложно изучать криптоанализ по академическим публикациям, чем по выжимкам в книгах, но чем раньше обучаемый начнет читать академические публикации, тем лучше). Некоторые результаты из других публикаций могут также служить ключом к ответу.

Ключ к ответу никогда не окончателен, вполне возможно, что другие, более эффективные атаки будут опубликованы. Некоторые публикации по криптоанализу содержат ошибки и неточности. Студенты должны завершить этот курс собственными публикациями.

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

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

Уроки расположены по порядку, но порядок не является обязательным. Первые уроки просты, но потом я попробовал все перемешать. Студенты должны почувствовать свободу в пропуске уроков, которые трудны для них и в последующем вернуться к ним, или даже пропустить некоторые совсем. Это тоже не мое изобретение для студентов, полностью окончивших один урок перед переходом к следующему. Умные студенты способны выполнять несколько уроков за раз.

Желаю удачи.

2. Какие существуют методы “взлома” шифров

Взлом шифра не обязательно метод поиска практических путей для перехватчика в целях восстановления открытого текста из шифртекста. В академической криптографии правила значительно ослаблены. Взлом шифра это просто найденная слабость в шифре, которая может использоваться проще, чем простой перебор. Никогда не забывайте, что простой перебор может требовать 2^128 шифрований, а атака - 2^110 шифрований для вскрытия. Взлом может также требовать нереального количества частично известного или выбранного открытого текста 2^56 блоков или нереальных объемов хранилища – 2^80. Просто поймите, что шифр может иметь только “сертификационную уязвимость”, свидетельствующую, что шифр не соответствует заявлениям.

Успешный криптоанализ может подразумевать взлом шифра с уменьшенным количеством раундов (к примеру, 8 раундовый DES против полного, 16 раундового) или упрощенного варианта шифра. Большинство взломов начиналось с криптоанализа варианта с уменьшенным количеством раундов и в конечном итоге (может быть через несколько лет) распространенного на полный шифр. Фактически, взлом версии шифра с уменьшенным количеством раундов часто публикуемый результат.

3. Почему блочные шифры?

Академические исследования в блочных шифрах развиваются различными путями с исследованиями по потоковыми шифрами. Работы по блочным шифрам традиционно имеют более четкий алгоритм (со специфическими параметрами и именами) или взлом этих алгоритмов. Работы по потоковым шифрам часто имеют более общий характер и техники анализа, с общими примерами и применениями. Пока криптоанализ потоковых шифров менее важен, чем блочных и военные считают его более важным - это более трудный путь курса, проводимого по академическим работам. Хороший обзор работ по потоковым шифрам доступен в онлайне: http://www.rsasecurity.com/rsalabs/technotes

4. Предварительные условия

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

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

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

4.1. Исторические предпосылки

Криптоанализ докомпьютерных алгоритмов шифрования практически не применим для анализа современных алгоритмов, но является интересным чтением и хорошим примером взаимоотношения требований и трюков криптоанализа. Я не рассматриваю это как обязательное требование, но интересующиеся студенты могут прочитать Helen Fourche Gaines, Cryptanalysis: A Study of Ciphers and their Solution (Dover Publications, 1939). Также интересны книги, написанные William F. Friedman и перепечатанные Aegean Park Press: Elements of Cryptanalysis; Military Cryptanalysis, части I, II, III, и IV; The Riverbank Publications, части I, II, and III; и Military Cryptanalytics, часть I, книга 1 и 2, и часть II, книги 1 и 2. Aegean Park Press на http:// www.aegeanparkpress.com/books/.

Внимательное изучение книги David Kahn, The Codebreakers, обязательно для понимания истории криптографии. Я ее настоятельно ее рекомендую.

5. Получение материалов курса

Работы, использованные в этом курсе, труды многих различных конференций. Я остерегаюсь малопонятных публикаций, но без исключений собираю их. Эта коллекция такова, что многие хорошие блочные шифры не входят в нее: CAST является типичным примером. Пожалуйста, не делайте исключений по причине ясности силы или слабости алгоритма, это просто материал для анализа.
Практически все работы взяты из материалов конференции Springer-Verlag, опубликованных в серии комментариев к лекциям по компьютерным наукам (LNCS). Большинство университетских библиотек подписаны на эту серию. Как минимум, студент должен иметь CD-ROM, содержащий материалы конференций Crypto и Eurocrypt (доступны через Springer-Verlag) и труды серии Fast Software Encryption (FSE). Значительно больше работ в этих трудах заслуживают внимания, чем приведенные в списке ниже.

Я поддерживаю веб-страницу http://www.counterpane.com со ссылками на работы в интернете. CD-ROM с трудами FSE и мой web-ресурсом возможно содержит почти весь курс.

6. Курс

6.1. Исходные данные

Прочитайте минимум два источника из следующего:

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

6.2. Основы криптоанализа

Попробуйте провести криптоанализ следующих упрощенных алгоритмов:

Все эти алгоритмы описаны в книге Брюса Шнайера «Прикладная криптография» и в A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997). Если Вы не можете взломать один из вариантов, приведенный в списке, с какими дополнительными упрощениями Вы сможете его взломать? Может Вы сможете взломать вариант с еще более уменьшеным количеством раундов?

6.3. Криптоанализ FEAL

Представляется, что все современные криптоаналитические атаки работают против FEAL. Сначала прочитайте алгоритм: A. Shimizu and S. Miyaguchi, «Fast Data Encipherment Algorithm FEAL» (Advances in Cryptology | EUROCRYPT '87 Proceedings, Springer-Verlag, 1988, pp. 267{278). Попробуйте взломать его. Некоторые атаки Вы можете найти в: B. Den Boer, «Cryptanalysis of F.E.A.L.» (Advances in Cryptology | EUROCRYPT '88 Proceedings, Springer-Verlag, 1988, pp. 275{280); H. Gilbert and P. Chasse, «A Statistical Attack on the FEAL-8 Cryptosystem» (Advances in Cryptology | CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 22{33); and A. Tardy-Corfdir and H. Gilbert, «A Known Plaintext Attack of FEAL-4 and FEAL-6» (Advances in Cryptology | CRYPTO '91 Proceedings, Springer- Verlag, 1992, pp. 172{182). Вы также можете заново открыть дифференциальный и линейный криптоанализ, если Вы почуствовали затруднения в этом.

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

Прочитайте главы с 1 по 5 E. Biham and A. Shamir, Dierential Cryptanalysis of the Data Encryption Standard (Springer-Verlag, 1993). Если Вы не сможете найти эту книгу, читайте E. Biham and A. Shamir, «Dierential Cryptanalysis of the Full 16-Round DES» (Advances in Cryptology | CRYPTO '91 Proceedings, Springer-Verlag, 1992, стр. 487{496).

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

Произведите атаку на FEAL используя дифференциальный криптоанализ. Одно из решений, в котором впервые говорится о дифференциальной атаке S. Murphy, «The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts» (Journal of Cryptology, V. 2, N. 3, 1990, стр. 145{154). Такде см. главу 6 E. Biham and A. Shamir, Dierential Cryptanalysis of the Data Encryption Standard (Springer-Verlag, 1993).

6.6. Дифференциальный криптанализ LOKI-89

Первая версия LOKI сейчас называется LOKI-89. Читайте L. Brown, J. Pieprzyk, and J. Seberry, «LOKI: A Cryptographic Primitive for Authentication and Secrecy Applications» (Advances in Cryptology | AUSCRYPT '90 Proceedings, Springer-Verlag, 1990, стр. 229{236). Найдите дифференциальную атаку. Решание в L.R. Knudsen, «Cryptanalysis of LOKI» (Advances in Cryptology | ASIACRYPT '91, Springer-Verlag, 1993, стр. 22{35). В книге Бихама и Шамира также обсуждается этот криптанализ.

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

Прочитайте M. Blaze and B. Schneier, «The MacGun Block Cipher Algorithm» (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, стр. 97{110). Попробуйте взломать шифр. Дифференциальная атака описана в V. Rijmen and B. Preneel, «Cryptanalysis of MacGun» (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, стр. 353{358). Существует много других атак, часть из которых не опубликовывалась. Этот алгоритм достоин затрат времени, и даже возврата к нему по завершению курса. При этом вы сможете изучить новые техники и открыть другие атаки.

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

Прочитайте опиасние Khafre в R.C. Merkle, «Fast Software Encryption Functions» (Advances in Cryptology | CRYPTO '90 Proceedings, Springer-Verlag, 1991, стр. 476{501). Попробуйте взломать его. Дифференциальная атака описана в E. Biham and A. Shamir, «Dierential Cryptanalysis of Snefru, Khafre, REDOC II, LOKI, and Lucifer» (Advances in Cryptology | CRYPTO '91 Proceedings, Springer-Verlag, 1992, стр. 156{171). См. также книгу Бихамаи Шамира.

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

Предшественником алгоритма IDEA был PES, см. X. Lai and J. Massey, «A Proposal for a New Block Encryption Standard» (Advances in Cryptology | EUROCRYPT '90 Proceedings, Springer-Verlag, 1991, стр. 389{404). Попробуйт взломать его используя дифференциальный криптоанализ. Результаты (и изменения с их учетом) в X. Lai, J. Massey, and S. Murphy, «Markov Ciphers and Dierential Cryptanalysis» (Advances in Cryptology | CRYPTO '91 Proceedings, Springer-Verlag, 1991, стр. 17{38).

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

Прочитайте M. Matsui, «Linear Cryptanalysis Method for DES Cipher» (Advances in Cryptology | EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, стр. 386{397). Попробуйте улучшить этот результат. Решение в M. Matsui, «The First Experimental Cryptanalysis of the Data Encryption Standard» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, стр. 1{11).

6.11. Линейный криптоанализ FEAL

Попробуйте взломать FEAL используя технику линейного криптоанализа. Решение в M. Matsui and A. Yamagishi, «A New Method for Known Plaintext Attack of FEAL Cipher» (Advances in Cryptology | EUROCRYPT '92 Proceedings, Springer-Verlag, 1993, стр. 81{91), и K. Ohta and K. Aoki, «Linear Cryptanalysis of the Fast Data Encipherment Algorithm» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, стр. 12{16). См. Также S. Moriai, K. Aoki, and K. Ohta, «Improving the Search Algorithm for the Best Linear Ex-pression» (Advances in Cryptology | CRYPTO '95 Proceedings, Springer-Verlag, 1995, стр. 157{170).

6.12. Условные дифференциальные характеристики

Условные характеристики введены в работе I. Ben-Aroya и E. Biham, «Differential Cryptanalysis of Lucifer» (Advances in Cryptology | CRYPTO '93 Proceedings, Springer-Verlag, 1994, стр. 187{199). Прочитайте разделы 1 - 3, по алгоритму и условным характеристикам. Попробуйте найти атаку перед чтением раздела 4. Читайте начиная с 5 раздела. Попробуйте найти атаку перед прочтением оставшейся части работы.

6.13. Криптоанализ чередующимися связанными ключами

Ознакомьтесь с результатами атаки против LOKI-89 и LOKI-91 в E. Biham, «New Types of Cryptanalytic Attacks Using Related Keys» (Journal of Cryptology, V. 7, N. 4, 1994, стр. 229{246). Если вы не можете найти журнал, читайте черновую копию (Advances in Cryptology | EUROCRYPT '93, Springer-Verlag, 1994, стр. 398{ 409). Вариант атаки на DES описан в разделе 5 (раздел 6 в версии Eurocrypt).

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

Прочитайте S. Langford и M. Hellman, «Diferential-Linear Cryptanalysis» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, стр. 17{26). Попробуйте применить эту технику к FEAL. Решение есть в K. Aoki и K. Ohta, «Dierential-Linear Cryptanalysis of FEAL-8» (IEICE Transactions: Fundamentals of Electronics, Communications, and Computer Sciences (Japan), V. E79-A, N. 1, 1996, стр. 20{27). Желаю удачи в его поиске, это японский журнал.

6.15. Взаимосвязь между линейным и дифференциальным криптоанализом

Прочитайте E. Biham, «On Matsui's Linear Cryptanalysis» (Advances in Cryptology | EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, стр. 398{412), и F. Chabaud and S. Vaudenay, «Links Between Differential and Linear Cryptanalysis»" (Advances in Cryptology | EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, стр. 356{365).

6.16. Дифференциальный криптоанализ высших порядков

Если вы сможете найти, прочитайте X. Lai, «Higher Order Derivatives and Dierential Cryptanalysis» (Communications and Cryptograpy, Kluwer Academic Publishers, 1994, стр. 227-233). Прочитайте раздел 4 L.R. Knudsen, «Truncated and Higher Order Dierentials» (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, стр. 196-211).

6.17. Дифференциальный криптоанализ высших порядков шифров на основе рюкзака

Читайте K. Nyberg и L.R. Knudsen, «Provable Security Against Dierential Cryptanalysis» (Journal of Cryptology, V. 8, N. 1, 1995, стр. 27-37). Шифр в разделе 5 назван шифром рюкзака, попробуйте взломать его используя дифференциальный криптоанализ высших порядков. Проблема также описана в K. Kiefer, «A New Design Concept for Building Secure Block Ciphers» (Proceedings of Pragocrypt '96, CTU Publishing House, 1996, стр. 30-41. Хорошее решение приведено в T. Shimoyama, S. Moriai, и T. Kaneko, «Improving the Higher Order Dierential Attack and Cryptanalysis of the KN Cipher» (Information Security. First International Workshop ISW '97 Proceedings, Springer-Verlag, 1998, стр. 32-42).

6.18. Множественная линейная аппроксимация

Прочитайте B. Kaliski Jr., и M. Robshaw, «Linear Cryptanalysis Using Multiple Approximations» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer- Verlag, 1994, стр. 26-39). Попробуйте взломать FEAL используя эти приемы. Одно из решений описано в B. Kaliski Jr., and M. Robshaw, «Linear Cryptanalysis Using Multiple Approximations and FEAL» (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, стр. 249-264)

6.19. Криптоанализ TWOPRIME

Прочитайте C. Ding, V. Niemi, A. Renvall, и A. Salomaa, «TWOPRIME: A Fast Stream Ciphering Algorithm» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 88-102). TWOPRIME настоящий блочный шифр. Попробуйте взломать его используя все виды атак. Результаты есть в D. Coppersmith, D. Wagner, B. Schneier, и J. Kelsey, «Cryptanalysis of TWOPRIME» (Fast Software Encryption, 5th International Workshop Proceedings, Springer-Verlag, 1998, стр. 32-48).

6.20. Криптоанализ Blowfish

Прочитайте B. Schneier, «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)» (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, стр. 191-204), и попробуйте взломать Blowfish. Некоторые результаты опубликованы в S. Vaudenay, «On the Weak Keys in Blowfish» (Fast Software Encryption, 3rd International Workshop Proceedings, Springer- Verlag, 1996, стр. 27-32). Это также дифференциальная атака против Blowfish в тезисах V. Rijmen.

6.21. Криптоанализ ICE

Прочитайте M. Kwan, «The Design of ICE Encryption Algorithm» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 69-82). Дифференциальная атака описана в B. Van Rompay, L.R. Knudsen, и V. Rijmen, «Dierential Cryptanalysis of ICE Encryption Algorithm» (Fast Software Encryption, 5th International Workshop Proceedings, Springer-Verlag, 1998, стр. 270-283.

6.22. Криптоанализ LOKI-91

LOKI был переделан, новая версия названа LOKI-91. прочитайте L. Brown, M. Kwan, J. Pieprzyk, и J. Seberry, «Improving Resistance to Dierential Cryptanalysis and the Redesign of LOKI» (Advances in Cryptology | ASIACRYPT '91 Proceedings, Springer-Verlag, 1993, стр. 36-50). Посмотрите все разновидности криптоанализа, некоторые результаты есть в L.R. Knudsen, «Cryptanalysis of LOKI-91» (Advances in Cryptology | AUSCRYPT '92, Springer-Verlag, 1993, стр. 196-208). Линейная атака (на LOKI-91 и LOKI-89) приведена в T. Tokita, T. Sorimachi, и M. Matsui, «Linear Cryptanalysis of LOKI and s2DES» (Advances in Cryptology | ASIACRYPT '94, Springer-Verlag, 1995, стр. 293-303).

6.23. Криптоанализ CMEA

Прочитайте разделы 1 и 2 в D. Wagner, B. Schneier, и J. Kelsey, «Cryptanalysis of the Cellular Message Encryption Algorithm» (Advances in Cryptology | CRYPTO '97 Proceedings, Springer-Verlag, 1997, стр. 526-537). Попробуйте взломать алгоритм перед завершением прочтения работы.

6.24. Криптоанализ IDEA

IDEA был описан (тогда он назывался IPES) в X. Lai, J. Massey, S. Murphy, «Markov Ciphers and Dierential Cryptanalysis» (Advances in Cryptology | EUROCRYPT '91 Proceedings, Springer-Verlag, 1991, стр. 17-38). Простейший анализ позволит найти слабые ключи, один из ответов есть J. Daemen, R. Govaerts, and J. Vandewalle, «Weak Keys for IDEA» (Advances in Cryptology | CRYPTO '93 Proceedings, Springer-Verlag, 1994, стр. 224-231). Попробуйте другие атаки, некоторые решения есть в W. Meier, «On the Security of the IDEA Block Cipher» (Advances in Cryptology | EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, стр. 371-385), и P. Hawkes and L. O'Connor, «On Applying Linear Cryptanalysis to IDEA» (Advances in Cryptology | ASIACRYPT '96, Springer-Verlag, 1996, стр. 105-115).

6.25. Усеченный дифференциал

Прочитайте L.R. Knudsen, «Truncated and Higher Order Dierentials» (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, стр. 196-211), Разделы 1 - 4. Попробуйте применить техники усечения дифференциала перед прочтением результатов в разделе 5. Попробуйте взломать SAFER используя усеченые дифференциалы. Результаты в L.R. Knudsen and T.A Berson, «Truncated Dierentials of SAFER» (Fast Software Encryption, 3rd International Workshop Proceedings, Springer-Verlag, 1996, стр. 15-26).

6.26. Дифференциальный анализ связаных ключей

Прочитайте J. Kelsey, B. Schneier, и D. Wagner, «Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES» (Advances in Cryptology | CRYPTO '96 Proceedings, Springer-Verlag, 1996, стр. 237-251). Попробуйте применить эти техники для 3-Way, DES-X, и TEA перед чтением J. Kelsey, B. Schneier, и D. Wagner, «Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DESX, NewDES, RC2, and TEA» (Information and Communications Security, First International Conference Proceedings, Springer-Verlag, 1997, стр. 203-207).

6.27. Обобщение линейного криптоанализа

Прочитайте C. Harpes, G. Kramer, and J. Massey, «A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma» (Advances in Cryptology | EUROCRYPT '95 Proceedings, Springer-Verlag, 1995, стр. 24-38), C. Harpes and J. Massey, «Partitioning Cryptanalysis» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 13-27). Попробуйте применить методику к DES перед прочтением приложения С во второй работе. Прочитайте разделы с 1 по 4 в B. Kaliski Jr. и M. Robshaw, «Linear Cryptanalysis Using Multiple Approximations» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, стр. 26-39). Попробуйте применить методику к LOKI91 перед чтением раздела 5.

6.28. Криптоанализ Akelarre

Прочитайте G. Alvarez, D. De la Guia, F. Montoya, and A. Peinado, «Akelarre: A New Block Cipher Algorithm» (Workshop on Selected Areas in Cryptography (SAC'96) Workshop Record, Queens University, 1996, стр. 1-14). Попробуйте взломать алгоритм. Результаты есть в L.R. Knudsen и V. Rijmen, «Two Rights Sometimes Make a Wrong» (Workshop on Selected Areas in Cryptography (SAC '97) Workshop Record, School of Computer Science, Carleton University, 1997, стр. 213-223) и в N. Ferguson and B. Schneier, «Cryptanalysis of Akelarre» (Workshop on Selected Areas in Cryptography (SAC '97) Workshop Record, School of Computer Science, Carleton University, 1997, стр. 201-212). Если вы не сможете найти другое, описание Akelarre есть в последней работе.

6.29. Отбеливание

Прочитайте J. Kilian and p. Rogaway, «How to Protect DES Against Exhaustive Key Search» (Advances in Cryptology | CRYPTO '96 Proceedings, Springer-Verlag, 1996, стр. 252-267).

6.30. Теория линейного и дифференциального криптоанализа

Прочитайте следующие работы:

6.31. Криптоанализ VINO

Прочитайте A. Di Porto and W. Wolfowicz, «VINO: A Block Cipher Including Variable Permutations» (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, стр. 205-210). Результатов криптоанализа не было опубликовано, попробуйте первым.

6.32. Интерполяционная атака

Прочитайте разделы с 1 по 3.3 в T. Jakobsen and L. Knudsen, «The Interpolation Attack on Block Ciphers» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 28-40). Прочитайте про модификацию SHARK в разделе 3.4, попробуйте взломать его перед прочтением оставшейся части работы.

6.33. Атака на не эпиморфные функции раундов

Прочитайте E. Biham and A. Biryukov, «An Improvement of Davies' Attack on DES» (Advances in Cryptology | EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, стр. 461-467). Несколько хуже B. Rijmen, B. Preneel, and E. DeWin, «On Weaknesses of Non-surjective Round Functions» (Designs, Codes, and Cryptography, V. 12, N. 3, 1997, стр. 253-266).

6.34. Криптоанализ Khufu

Прочитайте описание Khufu в R.C. Merkle, «Fast Software Encryption Functions» (Advances in Cryptology | CRYPTO '90 Proceedings, Springer-Verlag, 1991, стр. 476-501). Попробуйте взломать его. Анализ есть в H. Gilbert and P. Chauvaud, «A Chosen-Plaintext Attack on the 16-Round Khufu Cryptosystem» (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, стр. 359-368.)

6.35. Криптоанализ SAFER

Прочитайте J. L. Massey, «SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm» (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, стр. 1-17). Попробуйте провести атаку на шифр. Резултаты можно найти:

6.36. Операционные режимы

Прочитайте E. Biham, «On Modes of Operation» (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, стр. 116-120) и E. Biham, «Cryptanalysis of Multiple Modes of Operation» (Advances in Cryptology | ASIACRYPT '94 Proceedings, Springer-Verlag, 1995, стр. 278-292). Прочитайте разделы 1 и 2 в E. Biham, «Cryptanalysis of Ladder-DES» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 134-138). Попробуйте взломать эту конструкцию до завершения чтения работы. Также прочитайте D.Wagner, «Analysis of Some Recently Proposed Modes of Operation» (Fast Software Encryption, 5th International Workshop Proceedings, Springer- Verlag, 1998, стр. 254-269), и попробуйте взломать конструкцию перед завершением чтения анализа.

6.37. Усовершенстованный криптоанализ IDEA

Попробуйте взломать IDEA используя усеченные дифференциалы и линейно-дифференциальные характеристики. Результаты есть в J. Borst, L.R. Knudsen, and V. Rijmen, «Two Attacks on Reduced IDEA» (Advances in Cryptology | EUROCRYPT '97, Springer- Verlag, 1997, стр. 1-13) и в P. Hawkes, «Dierential-Linear Weak Key Classes of IDEA» (Advances in Cryptology | EUROCRYPT '98 Proceedings, Springer- Verlag, 1998, стр. 112-126).

6.38. Криптоанализ TEA

Прочитайте D. Wheeler and R. Needham, «TEA, a Tiny Encryption Algorithm» (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, стр. 97-110). Никаких криптоанализов, за исключнием подбора ключей, не было опубликовано, попробуйте быть первым.

6.39. Криптоанализ RC5

Прочитайте R.L. Rivest, «The RC5 Encryption Algorithm» (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, стр. 86-96). Попробуйте взломать RC5. Некоторые результаты есть в:

6.40. Криптоанализ MISTY

Прочитайте M. Matsui, «New Structure of Block Ciphers with Provable Security Against Dierential and Linear Cryptanalysis» (Fast Software Encryption, 3rd International Workshop Proceedings, Springer-Verlag, 1996, стр. 205-218) и M. Matsui, «New Block Encryption Algorithm MISTY» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 54-68). Результаты криптоанализа опубликованы только на японском: H. Tanaka, K. Hisamatsu, and T. Kaneko, «Higher Order Dierential Attack of MISTY without FL Functions» (The Institute of Electronics, Information, and Communication Engineers, ISEC98-5, 1998).

6.41. Криптоанализ Square

Прочитайте J. Daemen, L. Knudsen, and V. Rijmen, «The Block Cipher Square» (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, стр. 149-165), исключая раздел 6. Попробуйте провести атаку на этот шифр перед прочтнением 6 раздела.

6.42. Представление AES

В 1998, Национальный институт стандартов и технологии (National Instutute of Standards and Technology) объявил конкурс на блочный шифр для замены DES. Было приянто 15 заявок, из которых 5 было отобрано на второй раунд. Прочитать об этом процессе и претендентах можно на сайте NIST, на котором имеются ссылки на особенности построения кандидатов и различные работы по криптоанализу: http://www.nist.gov/aes/. Взломайте, что сможете и отправьте в NIST результаты. Это ваш шанс сделать вклад в будущий стандарт шифрования.

7. Выводы

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

Как криптоаналитики определяют из многих и многих шифров, изобретаемых каждый год, некоторые из еоторых публикуются, некоторые патентуются, а некоторые остаются проприетарными, какие достойны изучения? Они смотрят происхжодение алгоритмов. Если алгоритм предложен тем, кто показывал, что он может взлаывать алгоритмы, он изучал специальную литературу, возможно использованную в этом курсе и опубликовал несколько атак на свои собственные алгоритмы, которые не были открыты ранее, то более вероятно, что это изобретен безопасный шифр, чем в случае, когда кто-то прочитал литературу по диагонали и что-то изобрел. В большинстве случаев разработчик верит в безопасность своего шифра, а в этом случае его мнение чего-нибудь стоит. Криптоаналитики также смотрят на сопутствующую документацию. Опять разработка проста, а анализ труден. Разработка, которая включала множество атак )взломов) упрощенных вариантов, версий с уменьшенным количеством раундов, альтернативных реализаций, показывает, что разработчик знал, что делал, когда разрабатывал шифр. Когда мы разрабатывали Twofish, мы провели свыше 1000 человекочасов криптоанализа. Мы написали книгу, состаящую главным образом из криптоанализа. Так, уровень этой работы таков, что позволяет проектировать новые шифры. Только после этого уровня можно начинать криптоанализ шифров сторонних разработчиков. Это «цена билета» туда.

Любой может создать алгоритм, который не сможет сам взломать. Это не очень трудно. Что трудно, так это криптоанализ. И только опытный криптоаналитик может создать хороший шифр. И существет только один способ получить этот опыт - анализировать шифры других людей.

8. Библиографический очерк

Брюс Шнайер CTO компании Counterpane Internet Security, Inc., консалтинговой фирмы по вопросам безопасности, и консультант по криптографии. Он спроектировал алгоритм Blowfish, по прежнему остающегося не взломанным после нескольких лет криптоанализа, и алгоритма шифрования Twofish, вошедшего в состав финалистов AES. Шнайер автор «Прикладной криптографии» (Applied Cryptography (John Wiley & Sons, 1994 and 1996)), проводит семинары в этой области. Сейчас вторая редакция «Прикладной криптографии» издана тиражом 100000 экземпляров и переведена на 3 языка. Now in its second edition, Applied Cryptography has sold over 100,000 copies worldwide and has been translated into three languages. Его работы появлялись на многих международных конференций. Он частый автор статей и лекций по криптографии, компьютерной безопасности и приватности.

Хостинг от uCoz