Цель и задачи дисциплины.

Введение в методы криптоанализа

Я хочу начать разговор о новой дисциплине с напоминания о предназначении специалиста, которым вы должны стать, окончив полный курс обучения в университете. Ваша подготовка включает 4-х летнее обучение по программе бакалавра по направлению 0915 ²Освітньо-кваліфікаційної характеристики² стандарта высшего образования 2002 года - ²Компьютерная інженерія² по специализации ²Захист інформації в компьютерних системах та мережах². Стандартом предусматривается также дополнительный этап подготовки со сроком обучения 1 год на базе 4-х летней профессиональной подготовки с квалификационным уровнем магистр по компьютерным системам и сетям, который как раз и начинается сегодня для вас. После окончания этого этапа Вы получите квалификацию аналитик компьютерных сетей.

Выпускники специализации ²Захист інформації в компьютерних системах та мережах², как записано в стандарте, должны знать защищенные информационные технологии разнообразного назначения, уметь создавать системы и средства защиты информации в компьютерных системах и сетях, которые применяются в банковской и бизнесовой сферах, предпринимательстве, в органах государственного управления, на предприятиях различных форм собственности, а также в глобальных системах информационного обмена данными Интернет, Экстранет и др.

При построении учебных программ этого направления подготовки мы исходили из того, что работа выпускника кафедры будет связана с администрированием безопасности информационно-управляющих систем различного назначения и их компонентов: интернет-серверов, корпоративных и локальных сетей, систем ²Клиент-банк², локальных систем безбалансных и балансных отделов коммерческих банков, внутриплатежных и межбанковских платежных систем. Вы должны будете быть готовыми создавать и поддерживать защищенные информационные технологии, в частности, системы электронного документооборота, бухгалтерского учета, электронной коммерции, а также разрабатывать и эксплуатировать программные, программно-аппаратные и аппаратные средства криптографической защиты информации. Мы при построении учебного плана исходили также из того, что ваша подготовка должна позволять вам работать в органах государственного и ведомственного управления на таких должностях как администратор доступа информационных систем и сетей, инженер-аналитик компьютерных систем и сетей, инженер защищенных автоматизированных систем управления производством. На специалистов, прошедших магистерскую подготовку, мы смотрим и как на наш резерв (потенциал), из которого мы будем отбирать претендентов в аспирантуру кафедры. Их в будущем ожидает научная и преподавательская деятельность.

Сегодня я вас начинаю знакомить с новой дисциплиной, дополнительного этапа вашей специальной подготовки. Она называется ²Методы криптоанализа².

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

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

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

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

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

Основные задачами курса "Методы криптоанализа блочных шифров" сформулированы в учебной программе следующим образом:

- передать студентам знания по современным методам криптоанализа шифров и систем защиты информации.

- научить студентов использованию основных положений теории криптоанализа при решении задач оценки криптографических свойств и показателей шифров;

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

На дисциплину отводится 108 часов учебного времени, в числе которых 28 (14) лекции, 3 двухчасовых практических занятия, 3 четырехчасовые лабораторные работы, 2 расчетных контрольных задания, и ко всему этому объему учебной нагрузки запланировано 62 часа самостоятельной работы.

1.2 Краткая характеристика современного этапа развития криптографии[1]⁾

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

Началом развития современного этапа развития криптографии следует считать появление стандарта шифрования данных (Data Encryption Standard - DES), разработанного в 70-х годах прошедшего столетия специалистами из ИБМ. На это же время приходится революционный прорыв в классической криптографии, связанный с появлением принципиально новой идеологии криптосистем с открытым ключом, который открыл новые криптографические задачи и позволил найти принципиально новые решения задач классических. Шифр DES на тот период стал триумфом классической криптографии, представивший собой изящное техническое решение по защите информации, обладающее одновременно и высокой эффективностью (шифрование и дешифрование выполняются быстро) и убедительной надежностью (если ключ неизвестен, то нет способа раскрытия шифра).

Более чем 20 лет Стандарт Шифрования Данных (DES) считался американским государственным стандартом шифрования конфиденциальной, но несекретной информации. Став фактически всемирным стандартом, DES был опубликован в 1977 г. как FIPS PUB 46. Каждые пять лет он подвергался экспертизе Национальным Бюро по Стандартам (NBS), впоследствии переименованным в Национальный Институт Стандартов и Технологии (NIST). Первая экспертиза была проведена в 1983 г., и DES был переутвержден, как пригодный стандарт. Вторая экспертиза произошла в 1988 г., и этот стандарт был переиздан как FIPS PUB 46-1. Третья экспертиза была проведена в 1993 г., в результате которой DES как стандарт опять был переиздан в виде FIPS 46-2. В последней третьей версии FIPS 46-3 тройной DES был предложен как пригодный альтернативный алгоритм, обеспечивающий более высокий уровень защиты.

С момента публикации стандарта началось интенсивное изучение и всесторонние исследование показателей его стойкости многими заинтересованными специалистами. Большое внимания было уделено поиску ²лазеек² (вложенных слабостей), но время показало, что их в шифре нет. Именно на этом шифре практически начала отрабатываться и развиваться современная методология выполнения криптоаналитических атак, составившая основу рассматриваемого научного направления.

Следует отметить, что время подтвердило перспективность принципов, использованных при построении шифра DES, и довольно высокий запас его надежности, позволивший ему ²продержаться² более 20 лет. Большинство атак на него, обнаруженных за время его применения, требуют либо большого количества известных/выбранных текстов, либо большого времени вычислений. И, тем не менее, сообщение о специализированных аппаратных средствах, построенных Electronic Frontier Foundation (EFF) для исчерпывающего поиска DES ключей в 1997 г. послужило еще одним доказательством того, что шифр DES завершил свое существование, и NIST не может больше поддерживать использование DES. Конечно, за прошедшее время были предложены и проанализированы и многие другие решения (IDEA, SAFER, RC5, LOKI¢89, FEAL, A5 Skipjack,.Blowfish, советский ГОСТ 28147-89 и др.)

В январе 1997 г. NIST заявил о разработке преемника шифра DES, называемого Advanced Encryption Standard (AES) [2], предназначенного для использования, по меньшей мере, в течение следующих 30 лет. NIST был обнародован набор минимальных требований для алгоритмов-кандидатов и на симпозиуме, проведенном 15 апреля 1997 г. были рассмотрены разнообразные критические мнения по нему.

12 сентября 1997 г. NIST опубликовал свое официальное обращение сделать всемирно и бесплатно доступный, несекретный открытый алгоритм шифрования. Алгоритм должен быть блочным шифром с секретным ключом со 128-битовым размером блока и допускать использование переменных размеров ключа 128, 192 и 256 битов. Допускались и большие размеры блока и ключа. Предупреждалось, что безопасность, стоимость (вычислительная эффективность) и характеристики реализации должны быть наиболее важными критериями отбора. К конечному сроку представления, 15 января 1998 г. всего в NIST был предложен 21 алгоритм-кандидат. 15 из них были допущены, как отвечающие минимальным требованиям (Таблица 1.1). Эти 15 алгоритмов были представлены во время первой AES Конференции, проведенной 20–22 августа 1998 г., и обращение на подачу комментариев было выпущено NIST с целью помощи в принятии решения по выбору алгоритмов для следующего раунда (этапа) анализа. В общей сложности в обсуждении приняло участие более 50 организаций, Кроме того, независимые исследования по просьбе NIST проводили несколько научных центров СШФ и группа специалистов самого Института стандартизации.

Таблица 1.1: Первоначальные AES кандидаты.

# - множество значений относятся к 128-, 192- и 256-битным ключам

22 марта 1999 г. NIST финансировал проведение Второй Конференции по AES, целью которой было: представление первого раунда результатов анализа 15-ти AES кандидатов для обсуждения связанных вопросов (безопасность, эффективность и структурная гибкость) и для выдачи указаний по кандидатам, которые должны быть выбраны для следующей оценки. 15 апреля 1999 г. были объявлены алгоритмы-финалисты для второго раунда анализа: MARS, RC6, Rijndael, Serpent и Twofish. Эти пять шифров-финалистов были подвергнуты дальнейшему анализу во втором туре пересмотра.

Третья конференция по AES была проведена 10-12 апреля 2000 г. в Нью-Йорке с целью представления и обсуждения результатов этого анализа. Открытое обсуждение по алгоритмам-финалистам было проведено 15 мая 2000 г. 2 октября 2000 г. NIST объявил о выборе шифра Rijndael как нового AES.

Конечный период обсуждения по FIPS завершился 29 мая 2001 г. и 26 ноября 2001 г. был выпущен документ FIPS-197 с официальным описанием AES [2].

Главным итогом проекта AES стало принятие в США нового стандарта блочного симметричного шифрования FIPS-196.

Вторым значимым событием этих лет стало проведение проекта в рамках IST Программы «Технология Информационных Обществ» Европейского Комитета, названного NESSIE (Новые Европейские Схемы Подписи, Целостности и Шифрования) [179]. Идеей проекта стало выдвижение портфеля перспективных криптографических примитивов. Цель проекта была сформулирована как широкое распространение его результатов и достижение консенсуса на их основе (путем использования соответствующего фора (проектный промышленный комитет, 5-я Базовая Программа и разнообразные комитеты по стандартизации)). Партнерами NESSIE были: Katholieke Universiteit Leuven (Бельгия), ´Ecole Normale Sup´erieure (Франция), Royal Holloway (Великобритания), Siemens AG (Германия), Technion (Израиль), Universit´e Catholique de Louvain (Бельгия) и Universitetet i Bergen (Норвегия).

Масштаб Проекта NESSIE стал намного шире, чем AES; целью NESSIE стал выбор примитивов, обеспечивающих конфиденциальность, целостность данных и аутентификацию. В Таблице 1.2. представлен список только кандидатов в блочные шифры.

В январе 2000 г. началась первая фаза проекта NESSIE. В марте 2000 г. было выпущено открытое обращение по выдвижению кандидатов, и 13-14 ноября 2000 г. в К.U. Leuven, Бельгии была проведена первая конференция NESSIE по предварительной оценке представленных алгоритмов. Эта фаза завершилась в 2001 г. Вторая фаза началась 12-13 сентября 2001 г. со второй конференции NESSIE, проведенной в Royal Holloway, Лондоне. Третья конференция была проведена в Мюнхене, Германии, 6-7 ноября 2002 г.

Последняя конференция была проведена в Луанде, Швеция, 25 февраля 2003 г. Окончательное решение по портфелю NESSIE для блочных шифров включало шифр Misty 1 для 64-битного размера блока, AES и Camellia для 128-битного размера блока, а также SHACAL-2 для 256-битного[2]⁾ блочного размера.

Проект NESSIE мотивировал анализ четырех кандидатов блочного шифра: SAFER++, Hierocrypt-3, Hierocrypt-L1 и IDEA.

Таблица 1.2: Первоначальные NESSIE кандидаты блочного шифра.

Отмечу здесь также и проведение в это же время и японского проекта, однако я уже на нем задерживаться не буду.

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

1.3 Криптоанализ и стандартизация алгоритмов шифрования[3]⁾. Краткая характеристика харьковской криптографической школы.

Значительная роль алгоритмов шифрования при защите электронной информации в массовом масштабе обусловила необходимость принятия стандартов шифрования, из которых наиболее известным и широко используемым является американский федеральный стандарт DES, принятый в середине 1970-х годов и послуживший аналогом для российского стандарта ГОСТ 28147-89. В настоящее время эти стандарты уже устарели и не соответствуют современным требованиям по скорости преобразования данных []. Напомним, что в DES используется 56-битный секретный ключ, который в настоящее время не может обеспечить достаточной стойкости к атаке, основанной на переборе возможных значений ключа, тем более, что для этого стандарта были найдены криптоаналитические атаки, сложность которых оказалась меньше прямого перебора ключей. Недостатком российского стандарта считается сложность его аппаратной реализации. Еще одним существенным недостатком шифра ГОСТ 28147-89 отмечается также то, что в нем используются секретные долговременные элементы, к которым относятся таблицы замены, поставляемые ²в установленном порядке². По общепринятым криптографическим требованиям стойкость алгоритма должна основываться только на секретности легко сменяемого элемента - ключа. К тому же оба шифра обладают низкой стойкостью к атакам на основе случайных аппаратных ошибок. Эта атака является актуальной для шифров, применяемых в интеллектуальных электронных карточках. В этом типе нападений предполагается, что нарушитель имеет возможность оказать на шифратор внешнее физическое воздействие и вызвать одиночные случайные ошибки в регистрах, содержащих данные, при выполнении процедуры шифрования.

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

Как уже было отмечено выше, в 1998-2000 гг, когда стало окончательно ясно, что алгоритм DES уже исчерпал свои возможности, США, сохраняя первенство в этом направлении, провели всемирный (открытый!) конкурс на принятие нового стандарта - Advanced Encryption Standard (AES). Конкурс успешно завершился. Победителем стал бельгийский шифр Rijndal. Сильную конкуренцию победителю составили шифры RC-6 и Tofish. Вслед за этим конкурсом был объявлен аналогичный европейский конкурс (NESSI). Еще раз важно отметить, что в процессе открытого обсуждения проектов предлагаемых шифров и примитивов, их всестороннего анализа и сравнения был осуществлен существенный прорыв не только в теории криптографии, в развитии новых подходов к разработке и построению шифров, но и в развитии практических методов криптоанализа.

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

Поэтому архиважной задачей для Украины является быстрое освоение современных технологий защиты информации, выход на уровень создания и принятия собственных стандартов, что, несомненно, способствовало бы укреплению ее суверенитета и независимости. Проблема разработки скоростных шифров, соответствующих современным мировым требованиям и тенденциям уже декларирована и в Украине [ ], и работы в этом направлении уже развернуты. В частности просматривается возрастание технологических требований к алгоритмам шифрования. Ставится задача - при сохранении требования обеспечения гарантированной стойкости реализовать высокую скорость шифрования как при программной (более 100 Мбит/с), так и при аппаратной (более 1000 Мбит/с) реализациях. При этом ставится условие, чтобы устройства шифрования по своей стоимости были доступными массовому пользователю. Дополнительно актуализируется необходимость обеспечения стойкости алгоритмов к ряду нетрадиционных атак, например, к атаке на основе случайных аппаратных ошибок.

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

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

Потребности практической информатики привели к тому, что вопросы защиты информации вышли за границы ведомственных интересов, так как оказалось, что в защите нуждается не только военная и государственная информация, а также любая другая (коммерческая или частная) информация. Зарубежная открытая криптографическая школа сложилась уже в середине 70-х годах прошедшего столетия. В Украине (как и в России), открытая криптография начала активно формироваться в середине 1990-х годов. В настоящее время прикладная криптографическая тематика прочно вошла в такие журналы, как Всеукраинский Межведомственный Научно-технический сборник Радиотехника, г. Харьков; Безопасность информации, г. Киев; и ряд др. Уже имеются десятки национальных патентов на изобретения в области шифрования. Регулярно проводятся конференции по безопасности информации, на которых, как правило, рассматриваются и вопросы шифрования. Одним из крупных научных и учебных центров в области изучения и разработки криптографических средств и методов защиты информации на Украине выступает сегодня кафедра БИТ, на которой вы проходите обучение. Ученые кафедры принимают непосредственное участие в выполнении ряда программ государственного значения, в том числе и в программах по разработке и обоснованию стандартов криптографической защиты информации. У нас имеются предложения и по построению алгоритмов шифрования собственной разработки. Ведутся собственные интенсивные работы по освоению и развитию теоретических и практических методов криптоанализа. В дисциплине, которую я предлагаю вашему вниманию, как раз и предполагается передать вам накопленный нашими специалистами опыт в этой области. Понятно, что за отведенное на дисциплину учебное время вряд ли удастся подробно остановиться на всех известных к настоящему времени методах и подходах. Поэтому предполагается вам изложить ряд наиболее важных и принципиальных на наш взгляд результатов хотя бы в обзорном плане. Более детальная проработка отдельных вопросов будет отдана вам на самостоятельное изучение. Предполагается за основу взять проблемный метод обучения, в основе которого будет лежать формулировка для каждого из вас индивидуального задания, связанного уже с более детальным, глубоким освоением одного из методов криптоанализа и доведением его до программной реализации.

Блочные шифры

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

For more information on the subject, see [41], [54], references therein and the references given in this chapter.