Диференційні характеристики шифру DES

 

Харківський національний університет радіоелектроніки

(повне найменування вищого  навчального закладу) 

 

Факультет Комп’ютерної інженерії та управління

(повне найменування інституту,  назва факультету (відділення))

 

Кафедра Безпеки  інформаційних технологій

(повна назва кафедри  (предметної,  циклової комісії))

 

 

 

 

 

 

Пояснювальна  записка

до бакалаврської роботи

Бакалавр

(освітньо-кваліфікаційний  рівень)

 

на тему:

«Диференційні характеристики шифру DES»

 

 

 

Виконав: студент 4 курсу, групи

БІКС-09-1

напряму підготовки (спеціальності)         

6.170101, Безпека  інформаційних та  комунікаційних систем    

        (шифр  і назва напряму підготовки, спеціальності)

 

 

Кобиліна Ю.І.

Керівник    Лисицька І.В.

Рецензент  Філіпенко І.В.

 

 

Харків - 2013 року

 

Харківський національний університет радіоелектроніки

^{(повне  найменування вищого  навчального закладу)}

Інститут, факультет, відділення Комп’ютерної інженерії та управління

Кафедра, циклова комісія Безпеки інформаційних технологій

Освітньо-кваліфікаційний  рівень Бакалавр

Напрям підготовки 6.170101 Безпека інформаційних та комунікаційних систем

                                                                                                                              (шифр і назва)                                            

Спеціальність  

                                                                                                             (шифр і назва)                                            

 

 

                                                                                    ЗАТВЕРДЖУЮ

                                                                               Завідувач кафедри БІТ

                                                         _________ д.т.н., проф. І.Д. Горбенко

(підпис)

                                                           “____”_________________2013 року

 

 

 

З  А  В  Д  А  Н  Н  Я

НА БАКАЛАВРСЬКУ АТЕСТАЦІЙНУ РОБОТУ СТУДЕНТУ

 

Кобиліной Юлії Ігорівні                     

                                        ( прізвище, ім’я, по батькові)

1. Тема бакалаврської роботи: «Диференційні характеристики шифру DES»

керівник бакалаврської  атестаційної роботи

Лисицька  Ірина Вікторовна, д.т.н., професор   

                     ( прізвище, ім’я, по батькові, науковий ступінь, вчене звання)

затверджені наказом вищого навчального закладу від “21”квітня 2013 року № 600 СТ.

2. Строк подання студентом бакалаврської атестаційної роботи

“   17   ”     06      20      13     року

3. Вихідні дані бакалаврської атестаційної роботи: матеріали з опису та аналізу методів автентифікації особи по райдужній оболонці ока.

4. Зміст розрахунково-пояснювальної записки (перелік питань, які потрібно розробити):

Вступ.

1 Актуальність методів автентифікації.

2 Огляд інтелектуальних методів обробки біометричних зображень.

3 Методи виділення локальних особливостей біометричних образів.

4 Імітаційне моделювання досліджених методів.

5 Охорона праці.

Висновки.

 

5. Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень): презентаційні матеріали у вигляді слайдів.

6. Матеріали, що заборонені  до відкритого оголошення та  їх гриф: відсутні.

7. Консультанти розділів  бакалаврської роботи.

Розділ	Прізвище, ініціали консультанта	Підпис, дата
		завдання видав	завдання прийняв
1,2,3,4	Винокурова О.А.
5	Березуцька Н.Л.

 

8. Дата видачі завдання «   »              20   р.

 

 

КАЛЕНДАРНИЙ ПЛАН

 

№з/п	Назва етапів бакалаврської  роботи	Термін виконання етапів бакалаврської роботи	Примітка
11	Аналіз предметної області, збір та обробка інформації	20.03 – 05.04	Виконано
22	Обробка зібраної літератури	06.04 – 22.04	Виконано
33	Вивчення можливостей  модульних нейронних мереж	21.04 – 05.05	Виконано
44	Аналіз методу автентифікації особи по радужній оболонці ока	06.05 – 10.05	Виконано
55	Імітаційне моделювання  можливостей системи автентифікації особи по райдужній оболонці ока  на основі модульних нейронних мереж	11.05 – 24.05	Виконано
66	Виконання завдання з розділу  «Охорона праці»	25.05 – 05.06	Виконано
77	Оформлення пояснювальної  записки	05.06 – 07.06	Виконано

 

 

                                                                 Студент      ____________  Довгань К.А.

                                                                                                                                            ( підпис )                   (прізвище та ініціали)

Керівник  бакалаврської роботи   ____________  Винокурова О.А.

                                                                                                                                            ( підпис )                      (прізвище та ініціали)

 

РЕФЕРАТ

 

 

Пояснювальна записка  містить 70 сторінка, 19 рисунків, 8 таблиць, 15 джерел, 2 додатки.

Об’єкт дослідження –  метод автентифікації особи, використовуючи сегментацію контурів радужної оболонки людського ока.

Предмет дослідження –  модульні нейронні мережі і їх використання для автентифікації людини.

Мета роботи – провести дослідження модульних нейронних  мереж, а також вивчити можливість використання цих мереж для розпізнавання  райдужної оболонки людського ока.

Методи дослідження –  моделювання різних архітектур модульної  нейронної мережі, виділення райдужної  оболонки ока з використанням  нормалізації та сегментації зображення, отримання результатів та порівняння їх між собою.

 

БІОМЕТРИКА, МОДУЛЬНІ НЕЙРОННІ МЕРЕЖІ, СЕГМЕНТАЦІЯ, НОРМАЛІЗАЦІЯ, МОДЕЛЬ ДАУГМАНА, ПЕРЕТВОРЕННЯ, ЗОБРАЖЕННЯ РАЙДУЖНОЇ  ОБОЛОНКИ ОКА, НЕЙРОНИ.

 

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ  И СОКРАЩЕНИЙ

 

 

АС	–	автоматизированная система
БСШ	–	блочный симметричный шифр
ВС	–	вычислительная система
ИТС	–	информационно-телекоммуникационная система
КС	–	компьютерная система
ПК	–	персональный компьютер
ПО	–	программное обеспечение
ТД	–	таблица дифференциалов
AES	–	advanced encryption standard
DES	–	data encryption standard
LAT	–	linear approximation table
MADP	–	maximum average of differential probability
MALP	–	maximum average of linear probability
XOR	–	exclusive OR

ВВЕДЕНИЕ

 

 

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

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

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

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

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

Целью данной работы является обоснование подхода к исследованию показателей случайности полных версий БСШ на примере шифра DES . Сам подход заключается в совпадении дифференциальных и линейных свойств БСШ с соответствующими свойствами случайной подстановки.

 

 

1 ПЕРСПЕКТИВЫ ИСПОЛЬЗОВАНИЯ  БЛОЧНЫХ СИММЕТРИЧНЫХ ШИФРОВ  В СОВРЕМЕННЫХ СИСТЕМАХ ЗАЩИТЫ  ИНФОРМАЦИИ

 

 

        Оценка  стойкости БСШ является основной  задачей, которую необходимо решить  перед принятием решения о  практическом применении рассматриваемого  шифра. Под «стойкостью» алгоритма  шифрования подразумевается соответствие  его свойств следующим требованиям,  которые принято считать основными,  при проектировании современного  БСШ [6, 7]:

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

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

3) Практическая защищенность  алгоритма шифрования от силовых  атак, которая может достигаться  за счет использования симметричных  блочных криптопреобразований над  блоками длиной не менее 128 бит и с длиной применяемого  ключа не меньше 128 бит (в некоторых  случаях 192 или 256 бит).

4) Отсутствие слабых ключей, а так же подозрений на существование  ключей, при которых сложность  криптоаналитической атаки меньше, чем сложность атаки методом  «грубой силы».

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

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

Анализируя вышеприведенные  требования и принимая во внимание положение о проведении открытого  украинского конкурса на новый национальный стандарт блочного симметричного шифрования [7], можно откорректировать 3 пункт  требований к БСШ следующим образом:

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

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

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

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

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

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

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

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

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

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

Самой эффективной и самой  сложной является атака полного  перебора, или метод «грубой силы». Она основана на полном переборе всех возможных ключей. Эта атака эффективна при небольшом размере ключа, так как количество возможных  вариантов для ключа длиной n составляет 2n, т.е. для шифров, удовлетворяющих современным требованиям, сложность такой атаки составляет не менее 2^-128 операций шифрования.

Другой тип атаки –  атака методом встречи посередине. Если множество ключей криптоалгоритма  замкнуто относительно композиции, то для любых ключей z_i и z_j можно обнаружить ключ z_k такой, что результат шифрования любого текста последовательно на z_i и z_j будет равен шифртексту на ключе z_k, т.е:

              F(z_j,F(z_i, x))= F(z_k, x).                                                  (1.1)

 

       Можно  воспользоваться этим свойством.  Пусть нужно найти ключ z_{k .} Тогда для нахождения этого ключа, необходимо найти эквивалентную ему пару ключей z_i, z_{j .} Данный метод криптоанализа основан на "парадоксе днея рождения". Известно, что если считать, что дни рождения распределены равномерно, то в группе с 24 человек с достоверностью 0,5 у двух людей дни рождения совпадут. Пусть известен открытый текст x и его шифртекст у. Для текста x строим базу данных, которая содержит случайное множество ключей z| и соответствующих шифртекстов w=F(z|, x), и сортируем ее по шифртекстам w. Потом подбираем случайным образом ключи z|| для расшифрования текстов у и результат расшифрования v=F(z||, y) сравниваем с базой данных. Если текст v окажется равным одному из шифртекстов w, то ключи z| и z|| эквивалентны искомому ключу z. Этот же метод применяется, если множество ключей содержит в себе достаточно большое подмножество, являющееся полугруппой. Данный алгоритм является вероятностным. Тем не менее, существует и детерминированный аналог этого алгоритма. Он имеет название "giant step - baby step" и имеет такую же сложность .

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 ИССЛЕДОВАНИЕ ДИФФЕРЕНЦИАЛЬНЫХ  СВОЙСТВ БСШ DES

 

2.1 Понятие о дифференциальном  криптоанализе

 

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

        Для  построения атаки подбираются  пары открытых текстов (Р, Р'), имеющие определенное различие, или разность (difference) [8]. Здесь символ "-" обозначает операцию, обратную операции введения в цикловую функцию шифра подключа. В шифре DES такой операцией является побитовая сумма по модулю 2 (англ. XOR). Для обозначения этой операции будем использовать символ « ». Целесообразность применения операции, обратной относительно введения в цикловую функцию шифра подключа, состоит в исключении зависимости значений сформированных разностей от ключевых бит. В частности, для шифра DES при побитовом сложении текстов Р і Р' с ключом по модулю 2, разность Р - Р' (побитовая разность совпадает с побитовой суммой) не изменяется [8]:

                                      (2.1)

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

            Успеху подхода Эли Бихама  и Ади Шамира содействовало  и то, что все преобразования  шифра, кроме S-блоков, оказались линейными (начальная и конечная перестановки I, табличные перестановки E и P, и другие промежуточные операции). Это означает, что такие преобразования не вносят неопределенности в прохождение разностей. Вероятностный характер проведения разностей через циклы шифра представляют нелинейные преобразования, которые осуществляются S-блоками. В результате, изучение свойств S-блоков стало одним из главных этапов осуществления атак дифференциального криптоанализа на DES и другие блочные симметричные шифры.

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

                                                                                                         (2.2)

              При проведении разности через  несколько циклов шифрования  используется понятие многоцикловой  дифференциальной характеристики [8]. Многоцикловая характеристика  образуется  путем конкатенации одноцикловых  характеристик, которые удовлетворяют  условию сшивки    (значение входной разности текущего цикла совпадает со значением выходной разности предыдущего цикла ).

               Уместно напомнить здесь правило  формирования для шифра DES слова ( ) в i-м цикле из слова ( ) в i-1-м цикле [8]:

                                            , .   (2.3)

Соответственно этого  правила для дифференциальных характеристик  шифра DES (Фейстель-подобного шифра) всегда выполняется условие:

                                                ,   (2.4)

или в новых обозначениях:

                                              .    (2.5)

Это означает, что в процессе прохождения разностей через  три соседних цикла  разности на выходах правых полублоков разнесенных (на один цикл) циклов и   должны быть сбалансированными с входной разностью [8]. Вероятность r-цикловой дифференциальной характеристики определяется как произведение вероятностей, которые составляют ее одноцикловые характеристики с помощью формулы:

                                                 .    (2.6)

             Многоцикловые характеристики, в  которых входная разность равняется  выходной, называются итеративными [8], поскольку они могут быть  итеративно продолжены, т.е. могут  повторяться для покрытия необходимого  числа циклов (для DES возможны только итеративные характеристики с четным числом циклов).

             Пары  , которые определяются разностью на входе j-го цикла, и разностью после цикла j+i, называют i-цикловым дифференциалом, а последовательность значений , где каждое  – значение разности после k-го цикла, называется i-цикловой дифференциальной характеристикой, которая принадлежит i-цикловому дифференциалу . Вероятность i-циклового дифференциала   определяется как сумма вероятностей принадлежащих ему характеристик [8]:

. (2.7)

Поэтому всегда справедливо  такое неравенство:

                                                           .     (2.8)

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

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

Поскольку дифференциальный криптоанализ восстанавливает биты ключа на последнем цикле, то для  успешной атаки на шифр необходим  многоцикловый дифференциал (дифференциальная характеристика), покрывающий почти  все циклы шифра и обладающий вероятностью, которая значительно превышает значение 2^-n (n – размер ключа в битах). Соответственно вышесказанному, критерием защищенности r-циклового шифра от атак дифференциального криптоанализа считается выполнение неравенства:

 

                                            ,     (2.9)