Диференціальний криптоаналіз блоково-динамічного алгоритму шифрування
ВСТУП
Широкомасштабне використання обчислювальної техніки і телекомунікаційних систем у рамках територіально розподіленої мережі, перехід на цій основі до безпаперової технології, збільшення обсягів оброблюваної інформації, розширення кола користувачів і багато інших причин приводять до якісно нових можливостей несанкціонованого доступу до ресурсів і даних інформаційних систем, до їхньої високої уразливості. Саме тому методи захисту інформації постійно вдосконалюються з урахуванням попереднього досвіду і використанням позитивних властивостей відомих алгоритмів.
ПОСТАВЛЕННЯ ЗАВДАННЯ
Для проведення аналізу візьмемо, що відомі відкрите повідомлення та шифрований текст, що йому відповідає, а також алгоритм блоково-динамічного шифрування[1,2] з відповідним криптографічним протоколом [3]. Необхідно знайти Р-блок, S-блоки, ключ, необхідну кількість відритих текстів і трудомісткість розкриття блоково-динамічного шифру, наявність слабких ключів та імовірність їх появи.
РЕЗУЛЬТАТИ
Згідно з джерелом [4] для злому блоково-динамічного шифру методом диференціального аналізу необхідно 224 Пар відкритого тексту. Для 4-раундового блоково-динамічного шифру трудомісткість становить 232, при 6 раундах - трудомісткість 267, при 7 раундах - трудомісткість 2131.
На основі даних проведений регресійний аналіз залежності трудомісткості Е від кількості раундів r при використанні диференціального криптоаналізу блоково-динамічного шифрування. Результати цього аналізу наведені на рис. 1, де суцільною лінією показана експериментальна крива, а штриховою - теоретична, передбачена за допомогою рівняння регресії експоненціального типу, наведеного на вільній ділянці графіка. Для зручності оцінювався показник х степеня 2 замість самої трудомісткості. Отримане значення квадрата коефіцієнта кореляції R2=0,9732 свідчить про достатньо точні значення коефіцієнтів регресійного рівняння.
Рисунок 1 - Залежність показника х ступеня 2 трудомісткості е від кількості раундів
Одержане регресійне рівняння відносно Х має вигляд
. (1)
Для трудомісткості Е рівняння регресії має вигляд
. (2)
Застосовуючи рівняння (1), (2), можна спрогнозувати трудомісткість розкриття блоково-динамічного шифру з числом раундів більше 7.
Таким чином, при здійсненні атаки за допомогою диференціального криптоаналізу для варіантів блоково-динамічного шифру з кількістю раундів більше 5 його ефективність поступається методу повного перебору, середня трудомісткість якого при довжині ключа m=56 становить 256-1=255. Тому диференціальний криптоаналіз не є ефективним для повного 16 раундового блоково-динамічного шифру.
Для кожного короткого ключа є принаймні один еквівалентний більш довгий ключ; наприклад, A, AA, AAA і т. д. є еквівалентними ключами. Тобто еквівалентними ключами блоково-динамічного шифру є ключі, що складаються з цілої кількості періодичних частин, і при шифруванні однакових даних цими ключами отримується однаковий шифротекст, що обумовлено особливістю блоково-динамічного алгоритму.
Для позначення еквівалентності будемо використовувати знак еквівалентності ~, наприклад ABAB~AB, AABAABAAB~AAB.
Очевидно, що для відкриття еквівалентного ключа меншої довжини трудомісткість суттєво знижується, що дає підставу вважати такий ключ слабким. Назвемо такий ключ слабким ключем 1-го роду.
Визначимо імовірність появи ключа, що має еквівалентний йому, але меншої довжини.
Для довжини ключа m=2 символи "еквівалентні ключі" мають вигляд: AA~A, BB~B і т. д. Кожний символ алфавіту ключа може утворити таку пару однакових символів. Всього таких пар однакових символів може бути 256 (розмір алфавіту ASCII та ANSI). Загальна кількість можливих пар становить 2562. Тому імовірність появи еквівалентного ключа при m=2 становить
.
При m=3 еквівалентні ключі мають вигляд AAA~A, BBB~B і т. д. Тому імовірність появи еквівалентного ключа при m=3 становить
.
При m=4 еквівалентні ключі можуть мати вигляд, як AAAA~A, BBBB~B і т. д., так і ABAB~AB, BCBC~BC і т. д. Тому імовірність появи еквівалентного ключа при m=4 становить
.
При m=5 еквівалентні ключі мають вигляд: AAAAA~A, BBBBB~B і тд. Тому імовірність появи еквівалентного ключа при m=5 становить
.
Аналізуючи отримані результати, не важко помітити, що для парної та непарної довжини ключа закономірності імовірності Появи еквівалентного ключа відрізняються.
Для парної довжини ключа закономірність імовірності появи еквівалентного ключа має вигляд
, (3)
Тобто є постійною.
Для непарної довжини ключа закономірність імовірності появи еквівалентного ключа має вигляд
, (4)
Тобто залежить від довжини ключа.
На основі результатів досліджень автора [4] відомо, що при відомих S-блоках диференціальний криптоаналіз може розкрити Р-масив за допомогою
(5)
Вибраних відкритих текстів.
На основі формули (5) побудуємо графік залежності кількості відкритих текстів kВТ, необхідних для злому блоково-динамічного шифру методом диференціального криптоаналізу залежно від кількості раундів r. Цей графік зображений на рис. 2. Вісь ординат представлена у логарифмічній системі координат. На цьому графіку горизонтальними штрихпунктирними лініями показані характеристики сучасних модулів оперативної пам'яті та жорстких дисків.
З графіка, зображеного на рис. 2, бачимо, що для розміщення відкритих текстів в оперативній пам'яті комп'ютера, об'єму оперативної пам'яті сучасних персональних комп'ютерів достатньо лише для злому 3-раундового варіанта блоково-динамічного шифру методом диференціального криптоаналізу.
Рисунок 2 - Графік залежності кількості відкритих текстів KВТ, необхідних для злому блоково-динамічного шифру
При розміщенні відкритих текстів на жорсткому диску комп'ютера, об'єму жорстких дисків сучасних персональних комп'ютерів достатньо лише для злому 4-раундового варіанта блоково-динамічного шифру методом диференціального криптоаналізу, при цьому різко впаде швидкодія злому тому, що жорсткі диски значно повільніші за оперативну пам'ять.
Встановлено, що для деяких слабких ключів, які генерують погані S-блоки, тобто S-блоки, в яких принаймні 2 елементи збігаються. (вірогідність вибору такого ключа становить pII=2-14). Назвемо ці ключі слабкими ключами 2-го роду. Трудомісткість розкриття Р-масиву, утвореного слабким ключем 2-го роду, обчислюється за формулою [4]:
. (6)
Порівняємо залежність трудомісткості Е злому блоково-динамічного шифру методом диференціального криптоаналізу для звичайного (2) та слабкого ключа (6) залежно від кількості раундів, побудувавши відповідний графік залежності (рис. 3), де суцільна лінія відповідає звичайному ключу, штрихова - слабкому ключу. Для зручності по осі ординат показник х степеня 2 замість самої трудомісткості Е.
Аналіз графіка, наведеного на рис. 3, показав, що трудомісткість Е злому блоково-динамічного шифру методом диференціального криптоаналізу для слабкого ключа значно нижча, ніж для звичайного, причому зі зростанням кількості раундів r ця різниця зростає.
Рисунок 3 - Графік залежності трудомісткості Е злому блоково-динамічного шифру методом диференціального криптоаналізу для звичайного () та слабкого ключа (---) від кількості раундів r
До імовірності появи слабкого ключа 1-го роду (еквівалентного ключа) рІ додамо імовірність появи слабкого ключа 2-го роду рІІ і отримаємо загальну імовірність появи слабкого ключа р3:
. (7)
Для парного значення довжини ключа загальну імовірність появи слабкого ключа р3.парн становить
. (8)
Для непарного значення довжини ключа загальну імовірність появи слабкого ключа р3.непарн становить
. (9)
Імовірність появи звичайного (неслабкого) ключа q можна обчислити за формулою, як для імовірності сумісних подій:
(10)
Використовуючи формули (2), (6), (8), (10), можна вивести узагальнену формулу трудомісткості взлому блоково-динамічного шифру методом диференціального криптоаналізу, на основі знаходження середнього пропорційного до імовірності сумісних подій:
, (11)
Де Е(зв), Е(сл) - трудомісткості відкриття звичайного та слабкого ключа відповідно.
ВИСНОВКИ
У результаті проведеного диференціального криптоаналізу блоково-динамічного шифру було визначено імовірність появи слабких ключів 1-го та 2-го роду, яка суттєво змінюється від парності розміру та довжини ключа, яка знаходиться в межах.... Встановлено, що кращу криптостійкість мають ключі (серед слабких) з непарним розміром ключа. Визначено також кількість відкритих текстів, необхідних для диференціального криптоаналізу блоково-динамічного шифру, в кількості..., залежно від кількості раундів. Для повного (16-раундового) варіанта блоково-динамічного шифру такий об'єм оперативної пам'яті на сьогоднішній день є недосяжним. Знайдено також залежність трудомісткості диференціального криптоаналізу блоково-динамічного шифру як для слабкого, так і для звичайного ключа, а також виведено узагальнену формулу для знаходження трудомісткості, яка для повного (16-раундового) варіанта блоково-Динамічного шифру становить, що унеможливлює його відкриття диференціальним методом криптоаналізу. Крім того, при здійсненні атаки за допомогою диференціального криптоаналізу для варіантів блоково-динамічного шифру з кількістю раундів більше 5 його ефективність поступається методу повного перебору.
Summary
A possibility of implementation of the differential analysis to examine a steady of the block-dynamic ciphering algorithm has been considered. It was proved, that the proposed algorithm is firm enough against differential method of cryptographic analysis.
СПИСОК ЛІТЕРАТУРИ
- 1 С. М. Білан, І. М. Шварц. Вдосконалення алгоритму Blowfish з метою підвищення криптостійкості та швидкодії під час передачі інформації по каналах зв'язку //Реєстрація, зберігання та обробка даних. - 2005. - №1, Т.7. - С. 97-102. 2 Деклараційний патент на винахід №8897, кл. 7H04L 9/04. Спосіб блочного шифрування даних // С. М. Білан, І. М. Шварц; Опубл. 15.08.05. - Бюл. № 8. 3 С. М. Білан, І. М. Шварц. Криптографічні протоколи блокового-динамічного шифрування // Математичне моделювання. - 2005. - №1(13) - С. 71-73. 4 Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. - 2-е издание. - М.: Дело, 2003. - 524с.
Похожие статьи
-
В основе развития этого класса методов лежит утверждение, что анализ речи, основанный на модели слуха человека, будет более успешным, чем анализ,...
-
Опасным производственным фактором называется такой производственный фактор, воздействие которого на работающего в определенных условиях ведет к травме...
-
К методам этого типа относятся, прежде всего, класс методов обработки зашумленных речевых сигналов, которые используют квазипериодичность речевого...
-
Пожарная безопасность - Разработка и исследование алгоритма очистки речевого сигнала
Особое внимание к пожарной безопасности является обоснованным, так как в случае пожара будет нанесен значительный материальный ущерб (даже если в...
-
Введение - Разработка и исследование алгоритма очистки речевого сигнала
Алгоритм очистка речевой сигнал Записанный или передаваемый по проводным или радиоканалам с помощью различных технических средств, звуковой, в частности,...
-
Ентропійний КФЕ Для оцінки функціональної ефективності СПР широко використовуються ентропійні нформаційні критерії. Наприклад, за Шенноном такий...
-
Другим классом методов обработки зашумленных речевых сигналов основанных на использовании статистических моделей речевого сигнала являются методы, в...
-
Во временной области Класс методов цифровой обработки зашумленных речевых сигналов, который основан на построении математических моделей речевых сигналов...
-
Введение - Способы реализации алгоритмов цифровой обработки сигналов
Цифровой обработкой сигналов принято называть в вычислительной технике арифметическую обработку последовательностей равноотстоящих во времени отсчетов....
-
Методы борьбы с "музыкальным тоном" - Разработка и исследование алгоритма очистки речевого сигнала
Одна из проблем метода спектрального вычитания - так назывемый " Музыкальный Тон" . Он появляется вследствие того, что коэффициенты STFT шумовых сигналов...
-
Экономическая оценка проекта - Разработка и исследование алгоритма очистки речевого сигнала
1. Календарное планирование. Опытно-конструкторская разработка (ОКР) в себя пять этапов: 1. Техническое задание 2. Техническое предложение 3. Эскизный...
-
Алгоритм сжатия JPEG 2000 и его отличия от JPEG - Стандарт и алгоритм сжатия стандарта JPEG 2000
Алгоритм JPEG-2000 разработан той же группой экспертов в области фотографии, что и JPEG . Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG...
-
Опис портів введення-виведення MS DOS може працювати з трьома паралельними пристроями (LPT1 - LPT3). Для підключення використовується стандартне...
-
Характеристика продукта - Разработка и исследование алгоритма очистки речевого сигнала
Разработанная система средств очистки речевого сигнала предназначена для получения высококачественного речевого сигнала. Основной задачей системы...
-
Структуры алгоритмов бездатчикового управления - Бездатчиковое управление электроприводом
Как было сказано выше, алгоритм бездатчикового управления ВД разбивается на три подзадачи: определение начального положения ротора двигателя, разгон...
-
Выбор алгоритма бездатчикового управления - Бездатчиковое управление электроприводом
Существует множество, способов оценки положения ротора синхронной машины без помощи датчика положения ротора. Среди них можно выделить два подхода:...
-
Алгоритм коррекции допусков на технические параметры авиационных радиоэлектронных комплексов
В работе осуждаются особенности исследований статистической зависимости между контролируемыми параметрами авиационных радиоэлектронных комплексов (РЭК)....
-
В планировании осуществления перевозок выделяют: 1. Перспективное (стратегическое) планирование - отличительной особенностью его является период...
-
Этап 1. Пусть имеется исходный зашумленный сигнал, состоящий из чистого речевого сигнала и некоррелированного аддитивного шума, который определяется...
-
Система, поддерживающая ARTCP, может быть также совместима с TCP. Для этого, инициатор соединения, поддерживающий ARTCP, помещает в заголовке...
-
Технологічний процес складання і контролю функціонування виробів PEA являє собою дуже складну систему, яка складається з множини функціональних одиниць і...
-
Динамическое шумоподавление - Разработка и исследование алгоритма очистки речевого сигнала
Для решения практической задачи шумоочистки целесообразно использовать методы динамического шумоподавления, основанные на использовании характеристик...
-
В настоящей главе анализируются особенности методов, основанных на вычитании амплитудных спектров, для очистки речевых сигналов от стационарных и...
-
В настоящей главе анализируются особенности, свойства и характеристики речевых сигналов. Виды шумов акустических помех и искажений, а так же особенности...
-
Призначенням базового алгоритму навчання LEARNING [8] є оптимізація геометричних параметрів контейнерів класів розпізнавання, які відновлюються на...
-
Розробка алгоритму роботи пристрою - Автоматичний регулятор температури
Після пуску та ініціалізації регістрів мікроконтролера виконується найтриваліша ініціалізація РК-дисплея. Далі перевіряється стан прапора установки. Якщо...
-
Анализ напряженности труда - Разработка и исследование алгоритма очистки речевого сигнала
Напряженность трудового процесса оценивают в соответствии с настоящими "Гигиеническими критериями оценки условий труда по показателям вредности и...
-
Так як використовується РКІ - Winstar WG12864A-NYJ, який має досить великі розміри, розмір друкованої плати обираємо таким же (93х70 мм) з отворами для...
-
Измерения проводятся бригадой операторов в составе: трех дикторов: двое мужчин и одна женщина (далее Д1, Д2 и Д3); трех аудиторов: двое женщин и мужчина...
-
Алгоритм роботи датчика тиску з цифровим управлінням По включенню живлення виконується тестування всіх блоків, що складають керуючий модуль, здійснюється...
-
Стандарт сжатия JPEG 2000 и система ROI - Стандарт и алгоритм сжатия стандарта JPEG 2000
Одно из успешных применений вейвлетов - их использование для сжатия изображений. Многочисленные исследования в этом направлении вылились в конце концов в...
-
Измерения узнаваемости голоса диктора методом парных сравнений проводит бригада операторов в составе: пяти дикторов: трех мужчин и двух женщин (далее Д1,...
-
На втором этапе измерений речи артикуляционным методом проводится цикл измерений. Цикл измерений включает в себя результат приема всех аудиторов от всех...
-
Программно ШИМ реализован с использованием таймера/счетчика микроконтроллера. После включения питания и окончания процедуры сброса, контроллер переходит...
-
В настоящей главе проводится оценка качества очистки речевых сигналов от стационарных и квазистационарных шумов непрерывных импульсных помех и искажений...
-
Адаптивные компенсаторы помех - Разработка и исследование алгоритма очистки речевого сигнала
Этот класс методов цифровой обработки зашумленных сигналов основан на использовании, помимо собственно зашумленного сигнала, который подлежит очистке,...
-
На основании разработанных этапов работы алгоритма спектрального вычитания и в соответствии ГОСТ 19.701-90 (ИСО 5807-85) "Схемы алгоритмов, программ,...
-
Описываемый алгоритм (оригинальное название Minimum Mean-Square Error estimation) впервые был предложен в работе. Как и вычитание спектров алгоритм...
-
Предлагаемый в данной работе новый протокол Adaptive Rate Transmission Control Protocol (ARTCP) заимствует некоторые механизмы от протокола TCP. В ARTCP...
-
Розглянемо блок-схему типових технологічних процесів складання, монтажу і контролю друкованих вузлів, що приведена на рис.2.2. Як очевидно з блок-схеми,...
Диференціальний криптоаналіз блоково-динамічного алгоритму шифрування