Методи прискореного криптоаналізу блокових симетричних шифрів на основі аналізу показників стійкості зменшених моделей прототипів

Размещено на http://www.allbest.ru/

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

УДК 681.3.06:519.248.681

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

МЕТОДИ ПРИСКОРЕНОГО КРИПТОАНАЛІЗУ БСШ НА ОСНОВІ АНАЛІЗУ ПОКАЗНИКІВ СТІЙКОСТІ ЗМЕНШЕНИХ МОДЕЛЕЙ ПРОТОТИПІВ

Спеціальність: 05.13.21 - системи захисту інформації

ОЛЕШКО ОЛЕГ ІВАНОВИЧ

Харків 2010

Дисертацією є рукопис.

Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.

Науковий керівник:доктор технічних наук, професор Бондаренко Михайло Федорович, ректор Харківського національного університету радіоелектроніки, м. Харків

Офіційні опоненти:

доктор технічних наук, професор Сорока Леонід Степанович, в.о. ректора Академії митної служби України, м.Дніпропетровськ

доктор технічних наук, професор Олексійчук Антон Миколайович, професор Інституту спеціального зв'язку та захисту інформації Національного технічного університету України «Київський політехнічний інститут», м. Київ

Захист відбудеться «07» грудня 2010р. о 10 годині на засіданні спеціалізованої вченої ради К 64.052.05 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14; т. (057) 7021-016.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки (просп. Леніна, 14).

Автореферат розісланий «06» листопада 2010 р.

Вчений секретар спеціалізованої вченої ради М.М. Рожицький

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Симетричні шифри сьогодні є одним із основних інструментів, що забезпечують криптографічний захист інформаційного простору держави. Їх надійність і досконалість роблять вирішальний вплив на підтримку незалежності і суверенітету країни. В умовах постійно зростаючих обчислювальних криптографічних можливостей конкурентів і спецслужб зберігає свою актуальність завдання постійного вдосконалення технології блокового симетричного шифрування, що направлена на підтримку показників надійності систем захисту інформації на належному рівні.

Відповідного адекватного розвитку вимагають методи і методики оцінки показників стійкості блокового симетричного шифрування і, зокрема, стійкість до найпотужніших криптоаналітичних атак: диференційного і лінійного криптоаналізу. Особливе значення набуває розвиток цього напряму в умовах гострої необхідності прийняття в Україні стандарту блокового симетричного шифрування (БСШ). Відсутність національного стандарту - це мимовільне свідоцтво слабкості власної криптографічної школи або свідоцтво відставання національної наукової думки від передових технологій в області захисту інформації. Нарешті, це - свідоцтво недовіри до власних наукових досліджень і розробок.

Відмічене визначає актуальність теми дисертаційної роботи, направленої на вдосконалення методик оцінки показників стійкості БСШ до атак диференційного і лінійного криптоаналізу в інтересах, в першу чергу, підвищення якості і надійності експериментальних рішень по побудові блокових симетричних шифрів, представлених на національний конкурс, а також на користь пошуку нових перспективних рішень і розробок.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до планів наукових досліджень Харківського національного університету радіоелектроніки. Автор роботи приймав участь в розробці БСШ Мухомор в ЗАО ІІТ, який був представлений як один з кандидатів у конкурсі по відбору кандидатів на звання національного стандарту блокового симетричного шифрування в частині обґрунтування показників стійкості й оцінки поданих рішень.

Дисертація узагальнює наукові результати, отримані при безпосередній участі автора в роботах, які проводилися при виконанні держбюджетних науково-дослідних робіт:

– НДР № 237-1 (№0109U002573) «Напрями, методи і засоби вдосконалення і розвитку національної інфраструктури відкритих ключів (включаючи систему електронного цифрового підпису)» ;

– НДР №09-06 (№0109U002498) «Дослідження та розробка комбінованих інфраструктур з відкритими ключами на основі використання існуючих ІВК та системи на ідентифікаторах».

Мета та задачі досліджень. Метою досліджень є удосконалення методів оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу.

Для досягнення поставленої мети в роботі вирішені такі основні задачі.

1. Аналіз і узагальнення прийомів і методів оцінки стійкості сучасних БСШ до атак диференційного і лінійного криптоаналізу.

2. Аналіз відомих підходів і методів оцінки показників випадковості підстановок.

3. Розробка математичного апарату і відповідної методики визначення законів розподілу ймовірностей переходів XOR таблиць диференційних різниць і таблиць лінійних апроксимацій.

4. Обґрунтування методики прискореного криптоаналізу БСШ на основі розробки і дослідження властивостей зменшених моделей БСШ.

5. Узагальнення і доповнення за необхідністю результатів розробки зменшених моделей найбільш перспективних рішень по побудові БСШ, у тому числі і БСШ, представлених на український конкурс.

6. Виконання порівняльного аналізу показників випадковості відібраного набору зменшених моделей БСШ.

7. Обґрунтування вдосконалених критеріїв (показників) стійкості до атак диференційного і лінійного криптоаналізу.

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

Об'єктом досліджень є процеси криптографічних перетворень з використанням блокових симетричних шифрів.

Предметом досліджень є методи криптоаналізу БСШ на основі аналізу показників стійкості зменшених моделей прототипів.

Методи досліджень. При виконанні дисертаційної роботи використовувалися наступні методи: теорії ймовірностей, математичної статистики, комбінаторики і системного аналізу, методів статистичних випробувань, методів булевої алгебри. Методи системного аналізу використовувалися при обґрунтуванні вдосконаленої методики криптоаналізу БСШ на основі вивчення і порівняльної оцінки показників стійкості зменшених моделей.

Наукова новизна отриманих результатів дисертаційної роботи полягає в наступному:

1. Розвинено підхід до оцінки показників стійкості БСШ на основі оцінки властивостей і показників розроблених зменшених моделей прототипів.

2. Виконані оригінальні докази двох принципових теорем про закони розподілу переходів XOR таблиць диференційних різниць і таблиць лінійних апроксимацій.

3. На основі виведених математично і перевірених експериментально показників випадковості підстановлювальних перетворень запропоновані аналітичні співвідношення для визначення показників стійкості БСШ до атак диференційного і лінійного криптоаналізу.

4. Результатами досліджень підтверджено, що БСШ, представлені на Український конкурс, за показниками стійкості до атак диференційного і лінійного криптоаналізу повторюють властивості шифру Rijndael - переможця конкурсів AES і Nessie.

Практичне значення отриманих результатів полягає в наступному:

1. Визначені формули для розрахунків законів розподілу ймовірностей переходів XOR таблиць диференційних різниць і зсувів таблиць лінійних апроксимацій.

2. Запропоновані розрахункові співвідношення для оцінки максимальних значень повних диференціалів і лінійних корпусів БСШ.

3. Розроблені і програмно реалізовані зменшені моделі двох шифрів, представлених на український конкурс: Калина і Мухомор, що дозволяють реалізувати методику прискореного криптоаналізу прототипів. (Акт впровадження).

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

5. Підтверджена прогресивність нової методики прискореного криптоаналізу на основі порівняльної оцінки показників стійкості зменшених моделей прототипів.

6. Запропонований новий показник порівняння ефективності рішень по побудові конструкцій БСШ на основі визначення числа циклів зашифрування, після якого шифр набуває властивостей випадкової підстановки.

Особистий внесок здобувача. Дисертація є результатом самостійної роботи автора. У роботах, написаних в співавторстві, здобувачу належить: у [1] постановка статистичного експерименту і статистична обробка результатів експериментальних досліджень по оцінці диференційних властивостей міні-шифрів BABY-ADE і BABY-AES; [2] участь в розробці і підготовці специфікації шифру «Мухомор»; [3] участь в розробці і обґрунтуванні показників блокового симетричного шифру «Мухомор»; [4] виконання досліджень по оцінці стійкості шифру «Мухомор» до атак диференційного і лінійного криптоаналізу; [5] участь у виведенні розрахункових співвідношень при здобутті виразу для закону розподілу ймовірностей переходів XOR таблиць випадкових підстановок; [6] участь у виведенні розрахункового співвідношення для визначення значень зсувів таблиць лінійних апроксимацій випадкових підстановок і виконанні експериментів по перевірці збігу теоретичних значень отриманого закону розподілу ймовірностей з реальними даними; [7] участь у виконанні досліджень криптографічних показників S-блоків зменшених моделей шифрів за допомогою апарату булевої алгебри і комбінаторних методів теорії підстановок.

Апробація результатів. Основні положення дисертаційної роботи і результати досліджень докладалися і обговорювалися на конференціях: «УкрКрипт-97. Науково-практична конференція з питань криптографічного захисту інформації» (Одеса, 1997); «Правове, нормативне і метрологічне забезпечення системи захисту інформації в Україні» (Київ, 1998); X ювілейна Міжнародна науково-практична конференція "Безпека інформації в інформаційно-телекомунікаційних системах" (Київ, 2007); Перша Міжнародна науково-технічна конференція «Комп'ютерні науки і технології» (Бєлгород, 2009); X International Conference TCSET'2010 (Lviv-Slavske, 2010).

Публікації. Результати дисертаційної роботи опубліковані в 7 статтях в наукових журналах і збірках наукових праць, які входять в перелік наукових фахових видань України, і в 5 матеріалах і тезах наукових конференцій.

Структура та обсяг дисертації. Робота складається зі вступу, чотирьох розділів, висновків і двох додатків. Загальний обсяг дисертації складає 184 сторінки, з яких основний зміст викладень на 164 сторінках друкарського тексту, 12 рисунків, 28 таблиць. Список використаних джерел складається з 114 найменувань на 11 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі до дисертації обґрунтовано актуальність проблеми, сформульовано мету роботи, дано стислу анотацію отриманих результатів, визначено їх наукову новизну і практичне значення.

У першому розділі розглядаються особливості сучасного етапу розвитку технологій блокового симетричного шифрування. Наголошується, що і сьогодні блокові симетричні шифри виступають одним із основних інструментів у вирішенні завдань захисту інформації як державного, так і приватного сектора економіки. Зосереджується увага на тому, що в даний час в Україні все ще відсутній національний стандарт БСШ, і тимчасово дозволений до використання стандарт колишнього СРСР ГОСТ 28147-89, прийнятий в 1989 році (сьогодні перезатверджений як ДСТУ ГОСТ 28147:2009). Робиться висновок, що завдання прийняття вітчизняного стандарту БСШ, який задовольняє найбільш жорстким вимогам безпеки і враховує останні досягнення в області криптоаналізу і криптозахисту БСШ, вже давно набуло для України проблемного характеру. На його вирішення направлені кроки, що робляться останнім часом. Вони виразилися в проведенні внутрішньоукраїнського конкурсу з висунення і відбору кандидатів на національний стандарт блокового симетричного шифрування. Особливе значення в цих умовах набуває освоєння і розробка методик, що дозволяють прискорити аналіз запропонованих рішень і підвищити довіру до результатів такого аналізу. Велика увага в цих роботах відводиться опрацюванню питань забезпечення доказової стійкості криптоалгоритмів, особливо до атак диференційного і лінійного криптоаналізу.

Для подолання труднощів аналізу повномасштабних моделей (алгоритмів) і прискорення їх аналізу на кафедрі БІТ ХНУРЕ останнім часом вивчаються можливості використання для цих цілей підходу, що базується на розробці і дослідженні зменшених моделей прототипів, для яких наявних обчислювальних ресурсів виявляється вже цілком достатньо. У роботі ставиться задача вивчення і дослідження можливостей і перспектив застосування цього підходу, оцінки можливостей використання результатів аналізу зменшених моделей для формування вдосконаленої методики оцінки показників стійкості до атак диференційного і лінійного криптоаналізу, що мають рівень доказової безпеки.

У другому розділі виконується аналіз властивостей шифруючих перетворень, що розглядаються як випадкові підстановки. Наводиться математичний апарат, необхідний для розуміння наступних розділів роботи: відомості з математичної теорії перестановок і теорії випадкових підстановок. Представлені розрахунки, які визначають правомірність і доцільність використання асимптотичних показників випадковості підстановок (числових характеристик асимптотичних законів розподілу інверсій, зростань і циклів) для формування об'єктивних критеріїв по їх відбору.

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

В роботі вдалося розвинути підхід, який дозволяє підійти до оцінки максимальних значень переходів XOR таблиць і зсувів таблиць лінійних апроксимацій випадкових підстановок теоретичним шляхом. В основі розвиненого підходу лежать дві маловідомі фахівцям теореми, знайдені в роботах Luka O'Connor-а, що дозволяють розрахунковим шляхом отримати закони розподілу переходів XOR таблиць і зсувів таблиць лінійних апроксимацій випадкових підстановок. Повні докази відповідних теорем в цих роботах були або відсутні, або були дуже фрагментарними, а в окремих фрагментах складними для розуміння (наприклад, доказ спарюючої леми). Крім того, по текстам оригіналів зустрічалися погрішності і неточності. Відчувши важливість цих результатів, було поставлено задачу з побудови більш прозорих і зрозумілих їх доказів із подальшою прив'язкою до результатів, що цікавлять нас. Ця робота була успішно виконана, і викладені в роботі докази двох теорем пропонуються як результати, що претендують на оригінальність, теоретичну та практичну корисність і цінність. Тут ми коротко викладемо їх сутність і наведемо підсумки порівняння теоретичних (розрахункових) і експериментальних даних.

При розгляді диференційних властивостей випадкових підстановок вважається, що є бієктивним m-бітним відображенням і позначає безліч всіх таких відображень, відомих в математичній літературі як симетрична група. Через позначено значення XOR таблиці (її клітинки) для пари значень різниць входів і виходів , , підстановки .

XOR таблиця підстановки розглядається як матриця , у якої , Для m-бітної підстановки р XOR таблиця має наступну загальну форму

Основний інтерес представляє підматриця , яка відповідає частині XOR таблиці із входами, що приписуються до ненульових характеристик.

Ймовірність події, що полягає у тому, що значення диференційної таблиці випадково взятої підстановки р порядку для переходу вхідної різниці у відповідну вихідну різницю буде дорівнювати 2k (значення клітинок XOR таблиці завжди парні) позначена як .

Перша з доведених теорем, що пов'язана з диференційними показниками випадкових підстановок, в роботі представлена у вигляді:

Теорема 1. Для будь-яких ненульових фіксованих в припущенні, що підстановка вибрана рівноімовірно з множини і ,

(1)

де функція визначається виразом

(2)

Наводиться детальний доказ виразу (1), якого немає в роботі Luka O'Connor-а. Крім того, в запропонованій версії доказу для розрахунку функції використано вираз

,(3)

який розглядається як наслідок співвідношення (1) (нам не була потрібна спарююча теорема, яку доводить Luka O'Connor). У роботі просто показується, що вирази (2) і (3) є еквівалентними.

Закон розподілу переходів XOR таблиць диференційних різниць виходить множенням (1) на число елементів підматриці

,(4)

а перехід до максимумів XOR таблиць диференційних різниць здійснюється на основі пошуку значень k, при яких вираз (4) дає значення рівне одиниці:

.

Таблиця 1 ілюструє порівняння результатів, отриманих розрахунковими і експериментальними шляхами. Аналіз значень з таблиці 1 свідчить про гарне узгодження експериментальних і слідуючих з теоретичних міркувань результатів. Одночасно в таблиці представлені результати апроксимації розрахункових даних за допомогою формули (4), для якої запропонована проста оцінка .

Таблиця 1 Порівняння розрахункових і експериментальних результатів

m		2 k	Експеримент
4	3,379 0,459	6 8	6,7 (m + 3)
5	3,08 1,708	6 8	7,94 (m + 3)
6	6,6 0,675	8 10	9,1 (m + 4)
7	2,641 0,221	10 12	10,3 (m + 4)
8	0,8748	12	11,4
9	3,474 0,248	12 14	12,5 (m + 4)
10	13,8495 0,99	12 14	13,4 (m + 4)
11	3,952 0,247	14 16	14,5 (m + 4)
12	15,787 0,987	14 16	15,3 (m + 4)

Для оцінки стійкості шифру до атак лінійного криптоаналізу вирішується задача визначення явного вигляду закону розподілу зсувів клітинок таблиць лінійних апроксимацій випадкових підстановок. Відзначимо ще раз, що і в цьому випадку близьку по постановці задачу нам вдалося знайти в роботах Luka O'Connor-а 1995-го року, в яких наводяться розрахункові співвідношення, які нас цікавлять, але без доказів. У дисертації пропонується власна версія доведення цієї теореми і авторська інтерпретація її результатів. В цьому випадку розглядається лінійна таблиця апроксимації для підстановки р порядку . Вона є таблицею розміру з елементами, що визначаються співвідношенням

,

де позначає i-тий біт n-бітного вектора, маски входів і виходів в таблицю і позначає операцію побітного логічного АБО.

У лінійному криптоаналізі цікавляться значеннями лінійної таблиці апроксимації підстановки порядку , які є відмінністю (зсувом) дійсного значення кожної клітинки на число, що є кореляцією між лінійними комбінаціями входів і виходів в S-блок. Тому розглядаються так звані лінеаризовані таблиці підстановок, що позначаються, як і визначаються виразом:

. (5)

В цьому випадку модуль в правій частині записаного співвідношення призводить до того, що значення у випадку , може бути отримане як при позитивному (), так і негативному зсуві (). Причому, можливі і нульові значення зсувів (), коли . Виходячи з наведених міркувань, приведемо тут вміст другої теореми в наступному вигляді: Теорема 2. Хай буде випадковим значенням зсуву лінійної апроксимаційної таблиці для пари її входів б и в, коли підстановка р вибрана рівноімовірно з множини і - ненульові. Тоді зсуви набувають лише парних значень і для

. (6)

У роботі ставиться задача визначення межі для найбільшого значення . Найбільше значення для відображення, узятого над всіма невиродженими і позначається

,

а позначає очікуване число елементів таблиці , що мають значення .

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

, (7)

(для додатних і від'ємних значень зсуву k результат буде один і той же). Середньому значенню максимуму таблиці підстановки, як випливає з зіставлення результатів обчислень ізіз експериментальними даними, відповідатиме значення, при якому виходить найменше значення , що перевищує або рівне одиниці, тобто для визначення необхідно знайти закруглене у бік збільшення до найближчого цілого вирішення рівняння

(8)

Варіанти вирішення рівняння (8) (методом підбору, який істотно спрощується при використанні результатів експериментів), разом з даними експериментів ілюструє таблиця 2.

Основним результатом цієї частини роботи слід вважати отримання аналітичних співвідношень для опису законів розподілу таблиць XOR диференційних різниць і зсувів таблиць лінійних апроксимацій випадкових підстановок, що є справедливими, як показує подальший аналіз, і для багатоциклових перетворень сучасних шифрів.

Змістовна частина висновків цього розділу зводиться до наступного:

1. Відомі в даний час критерії відбору випадкових підстановок по числу інверсій, зростань і циклів є дуже м'якими і не забезпечують відбір підстановок із властивостями, що повторюють властивості шифруючих перетворень. Встановлені межі проходять і підстановки, що значно відрізняються по своїм властивостям від характеристик шифрів.

2. Отримані в розділі закони розподілу ймовірностей випадкових підстановок для числа переходів таблиць XOR різниць і числа зсувів (заповнень) клітинок таблиць LAT (лінійних апроксимацій) дозволяють ввести більш суворі критерії відбору випадкових підстановок, що впритул наближають їх властивості до властивостей шифрів.

3. Отримані розрахункові співвідношення для середніх значень максимумів XOR таблиць і середніх значень максимумів таблиць лінійних апроксимацій дозволяють більш обґрунтовано підійти до оцінки показників стійкості шифрів, що використовують підстановки, до атак диференційного і лінійного криптоаналізу.

криптографічний блоковий симетричний шифр

Таблиця 2 Порівняння теоретичних та експериментальних результатів

n	2k*		Експеримент
4	4 6 8	3,89 1,118 0,017	5,498
6	12 14 16	9,013 1,7 0,239	14,48
8	32 34	2,12 0,7457	34,68
10	74 76	1,16 0,64	78,8
12	162 164	1,129 0,82	116,24
14	350 352	1,069 0,900	314
16	748 750	1,027 0,93	720

4. Констатується реальна можливість виконувати оцінки показників безпеки шифрів до атак диференційного і лінійного криптоаналізу розрахунковим шляхом, що є дуже важливим для своєчасного і якісного проведення експертизи рішень по конструкціях шифрів, представлених на український конкурс.

У третьому розділі обґрунтовується концепція реалізації прискорених методів криптоаналізу шифрів на основі використання результатів аналізу показників стійкості зменшених моделей БСШ.

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

Розвивається альтернативний підхід до виконання оцінки стійкості шифрів, що ґрунтується на основі вивчення властивостей і показників стійкості зменшених моделей відповідних прототипів. Якщо в зменшеній моделі вдається зберегти всі властивості і особливості побудови вихідної процедури криптоперетворень, то підсумкові результати, отримані для малого шифру, можна застосувати для оцінки властивостей шифру-прототипу.

Звичайно, тут відразу виникає питання про адекватність і правомірність переходу від властивостей малих моделей до властивостей їх прототипів.

Наводяться аргументи на захист запропонованого підходу і концепції, що розвивається, в цілому. Зокрема наголошується, що:

1. Багато сучасних шифрів, у тому числі Rijndael і, принаймні, три шифри з представлених на Український конкурс, допускають масштабування, тобто використані в них операції мають зменшені аналоги для всіх перетворень, що використовуються в шифрах;

2. Для 16-бітових версій шифрів, „зменшені” операції для яких стають виродженими (наприклад, при масштабуванні виходять підстановки з однобітовими або двобітовими переходами), ці операції можна замінити укрупненими, але еквівалентними за ефектом (наприклад, знову-таки підстановлювальними).

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

Нарешті, є можливість непрямого підтвердження правомірності і ефективності даного підходу шляхом зіставлення властивостей зменшених моделей добре відомих і вже достатньо повно вивчених шифрів (DES, ГОСТ) із властивостями відповідних шифрів-прототипів.

Для реалізації цієї концепції частина матеріалів розділу присвячена стислому опису зменшених моделей шифрів mini-AES, baby-Rijndael, mini-ADE, міні-Калина, міні-Мухомор, міні-Лабіринт, дві з яких розроблені за участю автора роботи. У всіх представлених моделях шифрів за основу взятий розмір бітового входу рівний 16-ти бітам. Це максимально можливий розмір, що дозволяє обчислювально реалізувати більшість із відомих на сьогоднішній час методів криптоаналізу.

Одним із поширених підходів при аналізі надійності симетричних блокових шифрів є вивчення групових властивостей шифруючих операцій. Із груповими (циклічними) властивостями шифруючих перетворень пов'язана і одна з важливих властивостей блокового шифру, який використовується у режимі лічильника - значення періоду шифруючої гами, що впливає на вибір системних характеристик відповідного профілю захисту інформації. У підрозділі, який завершує розділ, вирішується завдання вивчення комбінаторних властивостей шифруючих перетворень з метою перевірки відомого положення про приналежність підстановок, що породжуються симетричними блоковими шифрами, до підстановок випадкового типу. Зменшені моделі шифрів дозволяють легко вирішити це завдання. Робиться висновок, що для оцінки параметрів підстановок, що формуються за допомогою симетричних блокових шифрів, можна користуватися асимптотичними законами і значеннями відповідних параметрів.

Четвертий розділ присвячений розробці методик оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу на основі оцінки диференційних і лінійних показників зменшених моделей прототипів.

Спочатку наводяться матеріали узагальнювального характеру з огляду понять і визначень диференційного криптоаналізу. Обговорюються відомі принципи побудови атак диференційного криптоаналізу.

Наголошується, що при визначенні стійкості S-блоків| до атак диференційного криптоаналізу широко використовується поняття диференційної - рівномірності. Нагадаємо його тут.

Визначення 1. Хай буде S-блоком, де . Хай буде найбільшим значенням в диференційній таблиці S-блока (виключаючи перший вхід в перший рядок), а саме

.

Тоді говорять, що S-блок є диференційно-рівномірним і відповідно називають рівномірністю булевої функції .

Вочевидь, що диференційна рівномірність S-блока знаходиться в межах . S-блок вважається гарним по цьому показнику, якщо значення достатньо мале.

По аналогії з цим визначенням введено до розгляду поняття умовної -рівномірності шифруючого перетворення (умовної -рівномірності).

Визначення 2. Для блокового симетричного шифру , де K, M і C кінцеві множини, що позначають ключовий простір, простір повідомлень і простір шифртекстів, а - шифруюче перетворення таке, що для маємо , значення

називатимемо умовною - рівномірністю шифру.

Індекс k тут підкреслює, що перетворення для всіх є залежним від ключа ( обчислюється при фіксованому значенні ключа зашифрування).

Інтерес далі зосереджується на поведінці значення (для малих версій шифрів) при зміні числа циклів шифрування і зміні ключів зашифрування.

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

Викладається методика дослідження диференційних властивостей шифруючих перетворень на прикладі міні-версій шифрів ADE і AES. В її основі - побудова поциклової розгортки значень максимумів повних диференціалів для кожного з шифрів. Також у роботі викладається і методика обробки результатів статистичних експериментів з оцінки диференційних показників (умовної - рівномірності) шифрів, що розглядаються.

В ході досліджень було побудовано 1000 варіантів таблиць, кожна для випадково вибраного значення 16-бітового ключа зашифрування. Визначалися наступні показники:

- середнє по множині з 1000 випадково вибраних ключів зашифрування (по множині таблиць) значення -рівномірності r -циклового шифру

,

де - значення показника рівномірності (максимальне значення заповнення у кожній з таблиць) для r-циклового шифру з ключем зашифрування k, ;

- середньоквадратичне відхилення умовної - рівномірності для вибірки з 1000 ключів;

- абсолютні значення умовної -рівномірності r-циклового для вибірки з 1000 ключів;

- математичне очікування мінімальних значень максимумів числа переходів r-циклового шифру.

Для визначення моменту переходу шифру до асимптотичного значення -рівномірності використовувався метод довірчих інтервалів, що є методом математичної статистики, спеціально призначеним для побудови множини наближених значень невідомих параметрів імовірнісних розподілів.

Результати статистичних досліджень диференційних властивостей міні-шифрів baby-ADE і mini-AES наведені в таблицях 3 і 4. Характеристики, представлені в них, були отримані, як зазначено вище, при обробці 1000 реалізацій таблиць. Довірчий інтервал задавався рівнем значущості б = 0,01, що відповідає довірчій вірогідності Р = (1 б)·100% = 99%.

Наголошується, що диференційні властивості шифру baby-ADE не гірші за диференціальні властивості шифру mini-AES (дані по шифру baby-Rijndael дають показник ті ж 4-и цикли, що і у baby-ADE). Представляється, що ці висновки можна перенести і на повні версії шифрів.

Загалом, по представлених результатах робиться висновок, що для обох шифрів AES і ADE складність атаки диференційного криптоаналізу декілька менше складності атаки повного перебору ключів (для малих версій шифру не більше ніж в декілька десятків разів). Якщо це співвідношення зберігається і для великих шифрів, то шифри AES і ADE дійсно є практично стійкими до атак диференційного криптоаналізу.

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

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

Таблиця 3 - рівномірність r - циклового шифру

Шифр	Кількість циклів
	2	3	4	5	6	7	8
baby-ADE	3254 ±59	301,3 ±7,3	20,064 ±0,348	19,170 ±0,124	19,120 ±0,092	19,166 ±0,093	19,106 ±0,091
mini-AES	4955 ±24	640,6 ±4,6	43,066 ±0,999	20,538 ±0,202	19,082 ±0,093	19,122 ±0,092	19,122 ±0,096

Таблиця 4 - рівномірність r - циклового шифру при порядковому розгляді таблиць розподілу диференціалів

Шифр	Кількість циклів
	2	3	4	5	6	7	8
baby-ADE	61,2 ±0,5	13,475 ±0,047	11,3559 ±0,0006	11,3459 ±0,0004	11,3456 ±0,0004	11,3458 ±0,0004	11,3458 ±0,0004
mini-AES	77,3 ±0,2	16,103 ±0,01	11,4065 ±0,0012	11,3488 ±0,0004	11,3456 ±0,0004	11,3458 ±0,0004	11,3456 ±0,0004

Отримані в попередніх розділах роботи результати дозволили нетрадиційно підійти до оцінки показників стійкості блокових симетричних шифрів до атак диференційного і лінійного криптоаналізу (до формування показників доказової безпеки). Ці нові ідеї узагальнені в роботах, опублікованих останнім часом вченими кафедри БІТ. У підготовці обговорюваних далі матеріалів був задіяний і автор цієї роботи.

Найголовніший і несподіваний результат вивчення зменшених моделей полягає в тому, що загальноприйнята точка зору, що розробляється в багатьох роботах і полягає в тому, що лінійні і диференційні властивості шифрів безпосередньо пов'язані з властивостями S-блоків, використаних при їх побудові, виявилася не вірною, а точніше не зовсім вірною. Насправді результуючі (тобто ті, що виходять при використанні повного набору циклових перетворень) показники стійкості шифрів визначаються практично лише розміром бітового входу в шифр.

Другий важливий висновок, що слідує з виконаних досліджень, зводиться до того, що показники стійкості великих (повних реалізацій) шифрів до атак диференційного і лінійного криптоаналізу (таких шифрів, як Rijndael і багатьох інших відомих шифрів, а також шифрів Лабіринт, Калина, Мухомор, ADE, представлених на український конкурс з вибору національного стандарту шифрування) можуть бути отримані розрахунковим шляхом.

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

Наша позиція полягає в тому, що підсумкові (асимптотичні) показники стійкості (максимуми повного диференціала таблиць XOR різниць) сучасних БСШ, також як і максимуми лінійних таблиць апроксимацій цих шифрів не залежать ні від S-блоків, ні від числа циклів шифруючого перетворення, а залежать лише від розміру його бітового входу.

Підсумком розділу є обґрунтування розрахункових співвідношень для визначення показників стійкості БСШ до атак диференційного і лінійного криптоаналізу. Вони виходять з відповідних розрахункових співвідношень для визначення максимальних значень повних диференціалів і максимальних значень лінійних корпусів, які можуть бути отримані застосуванням законів (4) і (7), справедливих для випадкових підстановок, до шифрів, що розглядаються як випадкові підстановки.

Застосування співвідношення (4) до шифру з n-бітовим розміром входу дозволяє для максимального значення диференціальної вірогідності (максимальній вірогідності повного диференціала) записати вираз

 (9)

Нами запропоновано також розрахункове співвідношення, що є гарною апроксимацією співвідношень (4) і (9)

.

Відповідно для шифру з n-бітовим розміром входу максимальне значення лінійної вірогідності (максимальна вірогідність лінійного корпусу) представляється у вигляді

, (10)

де визначається з рівняння (8)

Приведемо тут також співвідношення, отримане на основі обробки результатів обчислювальних експериментів, яке є зручною заміною виконанню розрахунків по співвідношенню (10).

(11)

Таким чином, диференційні і лінійні властивості шифруючих перетворень сучасних блокових симетричних шифрів (при заявленому числі циклів перетворення) є одним з проявів властивостей випадкових підстановок, і в цьому сенсі шифр Rijendael і шифри, представлені на Український конкурс, є еквівалентними (невиразними). Всі вони реалізують найбільшу вірогідність максимуму повного диференціала (для 128 бітових версій) близьку до 2-120 і найбільшу вірогідність лінійного корпусу близьку до .

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

По цьому показнику, як свідчить аналіз зменшених версій розглянутих шифрів, перевагу слід віддати шифру Калина, який виходить на асимптотичне значення показника вже при чотирьох ітераціях. За ним впритул йдуть Rijendael і рішення, представлені на український конкурс.

Інший важливий висновок, який зроблений за результатами експериментів, полягає в тому, що при потужному (доцикловому) перетворенні і інші відомі рішення по побудові блокових шифрів, у тому числі і узагальнена SPN структура Х. Фейстеля (із істотно гіршим по ефективності, ніж застосоване в шифрі Rijendael лінійним перетворенням) забезпечує диференційні властивості (максимальну ймовірність повного диференціала), не поступливі шифру Rijendael і за швидкістю досягнення асимптотичних показників. Використання в таких структурах випадкових S-блоків забезпечить підвищену, в порівнянні з шифром Rijendael, стійкість до алгебраїчних атак.

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

ВИСНОВКИ

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

Загальним результатом досліджень, проведених в роботі, є обґрунтування нової концепції оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу.

Головним науковим результатом роботи слід вважати обґрунтування методики оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу на основі вивчення показників і властивостей зменшених моделей прототипів, що дозволяє перевірити відповідність доказовим показникам стійкості шифрів, отриманим розрахунковим шляхом.

Достовірність теоретичних результатів підтверджується збіжністю експериментальних даних, отриманих в результаті статистичних випробувань міні-версій шифрів, розрахунковим даним, що витікають з теоретично обґрунтованих співвідношень, а також несуперечність відомим результатам криптоаналізу БСШ, математичної теорії підстановок, теорії ймовірності і математичної статистики.

Висновки, сформульовані в роботі, полягають в наступному:

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

2. Сучасні БСШ за статистичними показниками при перевищенні числа циклів перетворення певного значення поводяться як випадкові підстановки. Вони повторюють за своїми показниками закони розподілу ймовірностей по числу циклів, інверсій і зростань, а також закони розподілу ймовірностей переходів XOR таблиць і таблиць лінійних апроксимацій випадкових підстановок відповідного порядку.

3. Для оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу пропонується використовувати число циклів перетворень, після якого закони розподілу ймовірностей набувають асимптотичних значень. Відповідно, показники стійкості БСШ можуть бути визначені з розрахункових співвідношень як максимальні значення повних диференціалів і лінійних корпусів. Ці показники є значеннями доказової безпеки БСШ, які свідчать про те, що показники стійкості сучасних шифрів поступаються по складності атакам повного перебору ключів (силовим атакам).

4. В цілому підтверджена плідність розвитку запропонованої прискореної методики оцінки стійкості БСШ до криптоаналітичних атак, яка заснована на вивченні показників і властивостей зменшених моделей прототипів.

Результатами досліджень підтверджено, що шифри, представлені на український конкурс з вибору претендента на національний стандарт БСШ, не поступаються по стійкості до атак диференційного і лінійного криптоаналізу шифру Rijndael, що вважається сьогодні одним з прогресивних рішень з побудови БСШ.

Як подальші напрями вдосконалення технології БСШ слід розглядати пошук і обґрунтування шифруючих перетворень, що мають більш високі показники збіжності до асимптотичних показників значень повних диференціалів і лінійних корпусів в порівнянні з шифром Rijndael.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Исследование дифференциальных свойств мини-шифров Baby-ADE и Baby-AES / В.И. Долгов, А.А. Кузнецов, Р.В. Сергиенко, О.И. Олешко // Прикладная радиоэлектроника - 2009. - № 3 - С. 252-257.

2. Перспективний блоковий симетричний шифр «Мухомор» - основні положення та специфікація / І.Д. Горбенко, М.Ф. Бондаренко, В.І. Долгов [та ін.] // Прикладная радиоэлектроника. -2007. - №2 - С. 147-157.

3. Обґрунтування вимог та розробка основних рішень з побудування та властивості перспективного БСШ «МУХОМОР» / М.Ф. Бондаренко, І.Д. Горбенко, В.І Долгов [та ін.] // Прикладная радиоэлектроника. -2007. - №2 - С. 174-185.

4. Криптостойкость шифра «МУХОМОР» / И.Д. Горбенко, В.И Долгов, В.И. Руженцев [и др.] // Прикладная радиоэлектроника. -2007. - №2 - С. 186-194.

5. Дифференциальные свойства случайных подстановок. / А.В. Тевяшев, Р.В. Олейников, О.И. Олешко, К.Е. Лисицкий // Прикладная радиоэлектроника. 2010. № 3. С. 326333.

6. Долгов В.И. Свойства таблиц линейных аппроксимаций случайных подстановок / В.И. Долгов, И.В. Лисицкая, О.И. Олешко // Прикладная радиоэлектроника. 2010. № 3. С. 334340.

7. Исследование криптографических свойств нелинейных узлов замены уменьшенных версий некоторых шифров / В.И. Долгов, А.А. Кузнецов, И.В. Лисицкая [и др.] // Прикладная радиоэлектроника. - 2009. - № 3 - С. 268-277.

8. Долгов В.И. Оценка метрических характеристик случайных таблиц подстановок / В.И. Долгов, И.В. Лисицкая, О.И. Олешко // УкрКрипт-97: наук.-практ. конф. - Одесса. - 1997. - С. 65.

9. Долгов В.И. Дифференциальный криптоанализ. Сущность и проблемы использования / В.И. Долгов, О.И. Олешко, Р.В. Олейников // Правове, нормативне та метрологічне забезпечення СЗІ в Україні: наук.-техн. конф., 9-11 червня 1998 р. - Київ. - 1998. - С. 224-226.

10. Анализ криптографической стойкости алгоритма шифрования «МУХОМОР» / В. Руженцев, М. Михайленко, О. Олешко, Р. Олейников // Безопасность информации в ИТС: Х междунар. науч.-практ. конф., 15-18 мая 2007 г. - Киев: Пуща-Озерная. - 2007. - С. 47-48.

11. К вопросу оценки стойкости БСШ к атакам линейного и дифференциального криптоанализа / В.И. Долгов, И.В. Лисицкая, О.И. Олешко [и др.] // Компьютерные науки и технологии: I междунар. науч.-техн. конф., 8-10 окт. 2009 г. - Белгород: ГиК. - 2009. - С. 35-39.

12. Roman Oliynykov Differential properties of random substitutions / Roman Oliynykov, Oleg Oleshko, Konstantin Lisitskiy // Proceedings of International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science, TCSET'2010, February 23-27, 2010. - Lviv-Slavske. - 2010. - P. 75.

АНОТАЦІЇ

Олешко О.І. Методи прискореного криптоаналізу БСШ на основі аналізу показників стійкості зменшених моделей прототипів - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук по спеціальності 05.13.21 системи захисту інформації. Харківський національний університет радіоелектроніки, Харків, 2010р.

Робота присвячена удосконаленню методів оцінки стійкості блокових симетричних шифрів до атак диференційного і лінійного криптоаналізу. У роботі розвивається підхід до аналізу показників стійкості БСШ на основі оцінки властивостей зменшених моделей прототипів.

В дисертаційні роботі обґрунтована методика оцінки стійкості БСШ до атак диференційного і лінійного криптоаналізу на основі вивчення показників і властивостей зменшених моделей прототипів, що дозволяє перевірити відповідність доказовим показникам стійкості шифрів, отриманим розрахунковим шляхом.

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

Ключові слова: блоковий симетричний шифр, S-блок, підстановка, таблиця диференційних різностей, таблиця лінійних апроксимацій.

Олешко О.И. Методы ускоренного криптоанализа БСШ на основе анализа показателей стойкости уменьшенных моделей прототипов - Рукопись.

Диссертация на соискание ученой кандидата технических наук по специальности 05.13.21 системы защиты информации. Харьковский национальный университет радиоэлектроники, Харьков, 2010.

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

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

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

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

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

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

Ключевые слова: блочный симметричный шифр, S-блок, подстановка, таблица дифференциальных разностей, таблица линейных аппроксимаций.

Oleshko O.I. Methods of fast cryptanalysis of symmetric block ciphers based on analysis of security strength of reduced prototypes. - Manuscript.

The thesis for scientific degree of Candidate of Technical Sciences on speciality 05.13.21 - Information security systems- Kharkiv National University of Radioelectronics, Kharkiv, 2010.

Work is devoted to improvement of estimation methods of symmetric block ciphers security to the attacks of differential and linear cryptanalysis. Here we develop the method of analysis based estimation of small prototypes model properties.

The method of estimation block ciphers security to the attacks of differential and linear cryptanalysis are grounded in the thesis work. We estimate block ciphers security by investigating characteristics and properties of small model prototypes, thus we check up accordance between theoretical and empirical values of block ciphers security.

We suggest using the number of transformation rounds to achieve asymptotic values of distribution laws. Accordingly we can measure the security level of block symmetric ciphers by calculating maximums of full differentials and linear corps.

Keywords: symmetric block cipher, S-box, substitution, difference distribution table, linear approximation table.

Размещено на Allbest.ru

...