|
НАЦIОНАЛЬНИЙ ТЕХНIЧНИЙ УНIВЕРСИТЕТ УКРАЇНИ
“ КИЇВСЬКИЙ ПОЛIТЕХНIЧНИЙ IНСТИТУТ “
БАРДIС НIКОЛАС
( Грецiя )
УДК 681.322
РОЗРОБКА ПIДХОДУ I ЗАСТОСУВАННЯ АПАРАТУ БУЛЕВИХ
ФУНКЦIЙ ДЛЯ АНАЛIЗУ I СИНТЕЗУ ЕФЕКТИВНИХ
КРИПТОГРАФIЧНИХ АЛГОРИТМIВ ЗАХИСТУ IНФОРМАЦIЇ
Cпецiальнiсть 05.13.13 - Обчислювальнi машини, системи та мережi
Автореферат дисертацiї на здобуття наукового ступеня
кандидата технiчних наук
Київ - 1998
Дисертація є рукопис.
Робота виконана у Національному Технічному Університеті України (НТУУ) “Київський Політехнічний Інститут”
на кафедрі обчислювальної техніки.
Науковий керівник - Член-кореспондент НАН України,
доктор технічних наук, професор
Самофалов Костянтин Григорович,
професор кафедри обчислювальної техніки НТУУ
Офіційні опоненти:
- Доктор технічних наук, професор Брюхович Євгеній Iванович завідуючий відділом інституту кібернетики ім.В.М.Глушкова НАН України.
- Кандидат технічних наук Селігей Олександр Мінович, начальник конструкторського бюро НВО “Електронмаш”.
Провідна установа :
Iнститут проблем реєстрації інформації НАН України.
Відділ проблемно-орієнтованих інформаційно-обчислювальних систем.
Захист відбудеться 25.01.1999 р. в 14:30 на засіданні спеціалізованної ради Д26.002.02 в Національному Технічному Університеті України “Київський Політехнічний Інститут” (м.Київ, пр.Перемоги, 37, корп.18, ауд.306)
Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 252056, м.Київ, пр.Перемоги, 37, Вченому секретарю НТУУ “КПI”.
З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України “КПI”.
Автореферат розісланий 25 грудня 1998 р.
Вчений секретар
спеціалізованої вченої ради М.М. Орлова
АНОТАЦIЯ
Метa дисертацiйної роботи полягає в розробцi засобу оцiнки рiвня захищеностi криптографiчних алгоритмiв захисту iнформацiї на основi їx аналiзу на рiвнi булевих функцiй, а також в створеннi ефективних засобiв формального синтезу булевих функцiй, як функцiональної основи цього класу алгоритмiв та генераторiв псевдовипадкових послiдовностей.
Для досягнення поставленої мети в дисертацiї проведене наступне:
- Аналiз криптографiчних алгоритмiв захисту iнформацiї, протоколiв їх практичного використання та методiв порушення захисту для визначення можливостей реалiзацiї вимог до рiвня захищеностi iнформацiї засобами обчислювальної технiки.
- Теоретичне обгрунтування пiдходу та розробка ефективного засобу оцiнки рiвня защищеностi криптографiчних алгоритмiв захисту iнформацiї на основi аналiзу еквiвалентної їм системи булевих рiвнянь.
- Теоретичне обгрунтування та розробка методiв формального цiльового синтезу булевих функцiй з заданими криптографiчними властивостями, зокрема функцiй, що задовольняють критерiю максимуму повної та умовної ентропiї (Strict Avalanche Criterion - або скорочено - SAC-критерiю ).
- Дослiдження та розробка органiзацiї процесiв обчислень значень систем булевих функцiй криптографiчного захисту iнформацiї на унiверсальних та спецiалiзованих засобах обчислювальної технiки.
- Дослiдження криптостiйкостi icнуючих алгоритмiв захисту iнформацiї та визначення рiвня їх захищеностi шляхом одержання еквiвалентних алгоритмам систем булевих функцій та визначення рiвня вiдповiдностi їх криптографiчних характеристик запропонованим критерiям.
- Розробка алгоритмiв та програм синтезу булевих функцiй, еквiвалентних криптографiчним алгоритмам захисту iнформацiї, а також алгоритмiв та програм для визначення криптографiчних характеристик булевих функцiй.
На захист виноситься наступне
- Пiдхiд i засiб оцiнки рiвня захищеностi криптографiчних алгоритмiв на основi цiльового аналiзу еквiвалентної системи булевих функцiй рiвнянь. До тaкої системи рiвнянь завжди може бути зведено будь-який алгоритм криптографiчного захисту iнформацiї, що має блочну структуру.
- Базовi теореми, тверження i наслiдки, що встановлюють умови вiдповiдностi булевих функцiй критерию максимуму повної та умовної ентропiї ( Strict Avalanche Criterion ), по алгебраїчнiй нормальнiй формi функцiї.
- Метод синтезу балансних SAC-функцiй, який забезпечує, в порiвняннi з вiдомими пiдходами, мiнiмiзацiю часу для одержання функцiй такого класу з високами показниками нелiнiйностi.
- Метод синтезу алгебраїчних нормальних форм булевих SAC-функцiй нульового та вищого порядкiв, який не потребує об’ємiв пам’ятi, експонцiйно залежних вiд числа змiнних i дозволяє одержувати SAC-функцiї вiд великої кiлькостi змiнних (бiльше сотнi).
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальнiсть теми.
Широке впровадження комп’ютерних технологiй, розвиток систем комп’ютерних телекомунiкацiй та iнтегрованих систем обробки даних зумовлюють важливiсть пошуку нових пiдходiв до вирiшення проблеми захисту iнформацiї. Виходячи з сучасного стану розвитку iнформатики та комп’ютерних технологiй, проблему забезпечення надiйного захисту iнформацiї в комп’ютерних мережах, iнтегрованих системах обробки iнформацiї та програмних продуктiв, як об’єктiв авторського права, слiд розглядати, як важливу складову частину поступального розвитку комп’ютерних технологiй.
Основним елементом бiльшостi cучасних систем захисту iнформацiї є криптографiчне перетворення iнформацiї. Швидке зростання продуктивностi cучасних засобiв обчислювальної технiки та можливостi органiзацiї паралельного вирiшення задач криптоаналiзу на об’єднаних у мережi комп’ютерах рiзко знижує рiвень захищеностi багатьох традицiйних криптографiчних алгоритмiв. До цього слiд додати значнi успiхи, зробленi в останнi роки в галузi теоретичного криптоаналiзу, що також вимагає суттєвого перегляду icнуючих та розробки нових криптографiчних алгоритмiв захисту iнформацiї виходячи з нових концептуальних позицiй.
Одним з напрямiв розвитку нових концепцiй захисту iнформацiї, iнтерес до якого останнiми рокам помiтно пiдвищився, є функцiональний аналiз алгоритмiв криптографiчного перетворення iнформацiї. Зростання практичного iнтересу до функцiонального
аналiзу систем захисту iнформацiї зумовлено в першу чергу прогресом обчислювальної технiки, новими технологiчними можливостями, як в планi аналiзу iснуючих алгоритмiв, так i в планi задач розробки нових алгоритмiв. Незважаючи на досить значне число публiкацiй з питань функцiонального аналiзу криптографiчних алгоритмiв захисту iнформацiї, до теперiшнього часу залишаються не розв’язаними ряд важливих проблем, таких, зокрема як проблема оцiнки з єдиних методичних позицiй рiвня захищеностi криптографiчних алгоритмiв, насамперед вiд аналiтичних та комбiнованих методiв порушення захисту. Потребують дальшого вирiшенння i важливi для практики задачi автоматизованого cинтезу криптостiйких алгоритмiв. Зокрема широко застосовуємий метод одержання SAC-функцiй через спектральне перетворення Уолша вiдзначається невеликою продуктивнiстю та накладає значнi технологiчнi обмеження на одержання SAC-функцiй вiд великої кiлькостi змiнних, оскільки об’єм потрібноі для реалізації цього методу пам’яті експоненційно залежить від кількості змінних.
Таким чином, дослiдження способiв оцiнки захищеностi криптографiчних алгоритмiв з позицiй функцiонального аналiзу на рiвнi булевих функцiй, розробка методiв формального синтезу булевих функцiй з заданими криптографiчними властивостями є актуальними i мають теоретичне та практичне значення.
Методи дослiджень грунтуються на використаннi теорiї булевих функцiй, теорiї iнформацiї, теорiї множин, методiв комбiнаторики, а також теорем, твержень та наслiдкiв, що доведенi в дисертацiї. Основнi результати пiдтвержуються експериментальними дослiдженнями практичного застосування програмних продуктiв, що базуються на розроблених теоретичних положеннях, засобах та методах .
Наукова новизна
- Запропоновано новий пiдхiд до вирiшення актуальної задачi об’єктивної оцiнки рiвня захищеностi криптографiчних алгоритмiв, суть якого полягає в аналiзi криптографiчних властивостей системи булевих функцiй, що є еквiвалетною дослiджуємому алгоритмовi.
- Cформульованi та доведенi теореми, тверження та наслiдки, які встановлюють за алгебраїчною нормальною формою булевих функцiй наявнiсть у них специфiчних криптографiчних властивостей, що зумовлюють високу криптостiйкiсть алгоритмiв захисту iнформацiї побудованих на таких булевих функцiях.
- Розроблено метод синтезу алгебраїчних нормальних форм булевих SAC-функцiй нульового та вищого порядкiв, який не потребує об’ємiв пам’ятi експонцiйно залежних вiд числа змiнних i дозволяє одержувати SAC-функцiї вiд великої кiлькостi змiнних ( бiльше сотнi).
- Запропоновано метод формалiзованого синтезу булевих функцiй, що вiдповiдають критерiю максимуму повної та умовної ентропiї (балансних SAC-функцiй), що генерують бiльш якiснi у криптографiчному вiдношеннi функцiї, а також забезпечують значно бiльшу продуктивнicть в порiвняннi з вiдомими методами одержання SAC -функцiй.
Практична цiннicть результатiв дисертацiйної роботи полягає у тому, що застосування запропонованого засобу оцiнки рiвня захищеностi криптографiчних алгоритмiв дозволяє суттєво пiдвищити надiйнiсть перевiрки криптостiйкостi алгоритмiв захисту iнформацiї . Розробленi методи формалiзованого синтезу SAC-функцiй доведенi до практичної реалiзацiї у виглядi програм і їх застосування дозволяє значно прискорити процес розробки нових криптографiчних алгоритмiв захисту iнформацiї, забезпечуючи при цьому бiльшу криптостiйкicть алгоритму.
Достовiрнiсть теорем, твержень та висновкiв пiдтвержується теоретичним обрунтуванням і результатами експериментальних дослiджень.
Апробацiя роботи Основнi результати дисертацiйної роботи обговорювалися на мiжнароднiй конференцiї “Cучаснi проблеми робототехнiки та обчислювальної технiки” (Грецiя, Афiни, 10-14 вересня 1997 р.)
Публiкацiї Основнi результати дисертацiйної роботи опублiковано в 5 статтях.
Структура на обсяг дисертацiї. Дисертацiйна робота складається з вступу, чотирьох роздiлiв, заключної частини та додаткiв, що викладенi на 132 сторiнках друкованого тексту, мiстить 5 малюнкiв, 4 таблиць, список лiтератури з 150 найменувань.
У вступi обгрунтовується актуальнiсть теми дисертацiйної роботи, формулюється мета та задачi дослiдження, основнi положення, що виносяться на захист.
В першому роздiлi викладена загальна характеристика алгоритмiчних методiв захисту iнформацiї, розлянутi протоколи їх використання, що дозволило сформулювати вимоги що до рiвня захищеностi та органiзацiї практичного обчислення алгоритмiв криптографiчного захисту iнформацiї. Запропонована класифiкацiя задач та алгоритмiв криптографiчного захисту iнформацiї, виконано їх порiвняльний аналiз. Проведено аналiз методiв порушення захисту стосовно найбiльш вживаних на практицi алгоритмiв, дослiджено питання вибору критерiїв оцiнки алгоритмiв з точки зору рiвня забезпечуємого захисту та практичної реалiзацiї з використанням унiверсальних i спецiaлiзованих обчислювальних засобiв.
В другому роздiлi викладена концептуальна основа загального методу об’єктивної оцiнки криптостiйкостi алгоритмiв захисту iнформацiї через визначення складностi розв’язання еквiвалентної cистеми булевих рiвнянь, до якої завжди може бути зведено будь-який блоковий алгоритм криптографiчних перетворень. Визначенi критерiї практичної оцiнки складностi вирiшення еквiвалентної системи булевих рiвнянь. Дослiдженi теоретичнi аспекти визначення нелiнiйностi булевих функцiй та функцiй, що вiдповiдають критерiю максимуму повної та умовної ентропiї. Cформульованi задачi аналiзу та синтезу cистем булевих функцiй, що забезпечують криптостiйкicть алгоритму.
В третьому роздiлi виконано теоретичне дослiдження булевих функцiй, що відповідають критерiю максимуму умовної ентропiї (Strict Avalanche Criterion - або скорочено - SAC) - функцiй, які лежать в основi cинтезу криптостiйких алгоритмiв захисту iнформацiї. На основi одержаних теоретичних положень запропонованi та дослiдженi формальнi методи побудови функцiй цього класу. Зокрема розроблено методи синтезу балансових SAC-функцiй, а також метод одержання SAC-функцiй високих порядкiв, що не наклає технологiчних обмежень на синтез функцiй вiд великої кiлькостi змiнних.
В четвертому роздiлi з використанням запропонованого способу оцiнки рiвня захищеностi криптографiчних алгоритмiв виконано детальний аналiз найбiльш поширених на практицi зворотних та незворотних алгоритмiв: DES та SHA. Досліджено практичні аспекти реалізаціє криптографічних алгоритмів на універсальних та спеціалізованих обчислювальних засобах.
У висновках наведенi основнi теоретичнi та практичнi результати роботи, рекомендацiї щодо їхнього використання.
ОСНОВНИЙ ЗМIСТ РОБОТИ
В сучасних системах захисту iнформацiї криптографiчними алгоритмами забезпечується вирiшення слiдуючих задач:
- захист вiд несанкцiонованого читання iнформацiї, що передається по мережам або зберiгається в пам’ятi iнтегрованих комп’ютерних систем;
- забезпечення достовiрностi та тотожностi iнформацiї в мережах та iнтегрованих системах, тобто захист вiд несанкцiонованої змiни iнформацiї;
- захист програмних продуктiв, як об’єктiв промислової власності вiд несанкцiонованого копiювання та використання;
- аутентифiкацiя користувачiв комп’ютерних мереж, iнтегрованих баз даних та систем обробки iнформацiї.
Всi алгоритми криптографiчного перетворення iнформацiї доцiльно роздiлити на двi групи: зворотнi, для яких визначено процедури як прямого, так i зворотнього перетворення; незворотнi - тобто такi, для яких визначено тiльки процедури прямого перетворення, результатом якого є цифрова сигнатура, причому вважається, що визначення зворотньої процедури являє собою складною, з обчислювальної точки зору, проблемою, в зв’язку з чим, цей класс алгоритмiв часто називають одностороннiм. Зворотнi алгоритми, в свою чергу, роздiляються на симетричнi ( пряме та зворотнє перетворення виконується з використанням одних i тих же ключiв) та несиметричнi ( пряме та зворотнє перетворення виконується з використанням рiзних ключiв, причому в зв’язку з тим, що тiльки один з цих рiзних ключiв має бути закритим, цей клас алгоритмiв часто називають алгоритмами з вiдкритим ключем).
Критерiй якостi алгоритму має враховувати як рiвень захищеностi, так i можливостi досягнення високої продуктивностi криптографiчного кодування з використанням унiверсального мiкропроцесора. Найбiльш складною є проблема визначення об’єктивного рiвня захищеностi алгоритму вiд спроб розкриття. Стосовно зворотнiх алгоритмiв на практицi криптоаналiзу найчастiше зустрiчаються такi двi задачi:
- вiдновлення вихiдного тексту повiдомлення, якщо заданi закодований текст повiдомлення та використовуємий алгоритм при невiдомому ключi;
- визначення невiдомого ключа, за умовою, що задано вихiдний та закодований тексти, а також використовуємий алгоритм;
Якщо перша з цих задач може бути вирiшена тiльки з використанням методiв статистичного аналiзу та пiдбору, то рiшення другої, яке само по собi cуттєво простiше, може бути реалiзовано або методами пiдбору, або ж аналiтичними методами. Разом з тим, на практицi криптоаналiзу частiше зустрiчається друга задача, оскiльки iснує чимало протоколiв iдентифiкацiї та обмiну ключами, що припускають передачу по лiнiї як вiдкритого тексту, так i його зашифрованого варiанту.
Стосовно до незворотнiх алгоритмiв, задача розкриття формулюється як задача вiднадходження тексту, обчислення сигнатури якого по вiдомому алгоритму забезпечує одержання заданого коду хеш-сигнатури. Для вирiшення цiєї задачi застосовуються методи пiдбору та аналiтичного визначення процедури зворотнього перетворення.
Таким чином, найбiльш вживаним на практицi методом руйнування захисту є пiдбор. Його практичне застосування вимагає значних обчислювальних ресурсiв. Бiльш дiєвим являється комбiноване використання аналiтичних методiв та направленого пiдбору у виглядi зокрема методiв диференцiйного криптоаналiзу та методiв лiнiйної апроксимацiї. Найпошириним засобом протидiї методам пiдбору є збiльшення розрядностi криптографiчного перетворення. Але цей простий засiб, окрiм зниження продуктивностi практично не впливає на криптостiйкicть алгоритму проти аналiтичних методiв руйнування захисту. Тому важливою задачею є визначення об’єктивного рiвня криптостiйкостi алгоритму саме до аналiтичних методiв та синтез вiдповiдних алгоритмiв.
Для вирiшення цiєї проблеми пропонується дослiджувати систему булевих функцiй, яку завжди можна поставити у вiдповiднiсть алгоритму криптографiчного перетворення. Практично всi алгоритми, що використовуються в системах захисту iнформацiї мають блокову структуру, тобто  -розрядний двоiчний вектор  результату перетворення залежить вiд кiнцевого числа вхiдних бiтiв ( -розрядного вектору  вхiдного повiдомлення та  -розрядного вектора  ключа ). Незалежно вiд дослiджуємого криптографiчного алгоритму розряди  вектора  завжди можуть бути представленi системою булевих функцiй:
 ( 1 )
Для вирiшення задач криптоаналiзу стосовно зворотнiх алгоритмів, тобто за умови, що заданi вектори  та  , cистема (1) булевих функцій породжує систему булевих рiвнянь яка має бути розв’язана вiдносно компонент вектора  . Стосовно незворотнiх алгоритмiв, вiдомi вектори  та  i цiллю криптоаналiзу є вiднаходження колiзiруючого  -розрядного вектора   такого, що  . Вирішення цієї задачі також можна розглядати, як процесс розв’язання відносно  системи булевих рівнять, в яку перетворюється система булевих функцій (1). Тобто, незалежно від класу криптографічного алгоритму задача порушення його захисту в математичному плані зводиться до розв’язання системи булевих рівнянь, на яку перетворюється система (1) булевих функцій, що еквівалентна досліджуємому алгоритмові. Таким чином, складнiсть задачi аналiтичного криптоаналiзу можна оцiнювати за складнiстю розв’язання відповідноі системи булевих рівнянь, що може бути одержана з системи (1) булевих функцій, еквiвалентної алгоритму.
Вiдомо, що розв’язання систем нелiнiйних булевих рiвнянь (1) в загальному випадку являє собою досить складну математичну задачу, проте при недостатньо криптостiйкому алгоритмi застосуванням спецiальних прийомiв система (1) може бути суттєво спрощена i в кiнцевому рахунку розв’язана комбiнованим використанням аналiтичних методiв та направленого пiдбору. Зокрема, якщо рiвняння системи (1) мають малу нелiнiйность, то можуть бути застосованi методи лiнiйної апроксимацiї, що на практицi дозволить на багато порядкiв зменшити число варiантiв пiдбору. Виконаний в роботi аналiз показав, що основними критерiями складностi розв’язання системи булевих рiвнянь, до якої зводиться при криптоаналізі еквівалентна система (1) являються:
- кiлькiсть рiвнянь -
 ;
- ентропiя кожної з булевих функцiй, які складають систему (1): cкладнiсть її роз’язання тим бiльша, чим бiльша ентропiя кожної з функцiй, причому умовою максимальної ентропiї є баланснiсть булевої функцiї.
- нелiнiйнiсть - тобто хемiнгова вiдстань до найближчої лiнiйної булевої функцiї: чим бiльша нелiнiйнiсть функцiй, що складають систему (1), тим складнiшим є її розв’язання;
- попарна незалежність кожної пари булевих функцiй, які складають систему (1). Для забезпечення складностi розв’язання cистеми рiвнянь (1) необхiдною умовою є досягнення некорельованості значень компонент вихідного вектору
 , що забезпечеється максимальним значенням умовної ентропiї булевих функцій, побудованих композицією пар булевих функцiй, які складають систему (1) ;
- максимальне значення умовної ентропiї кожної з булевих функцiй вiдносно будь-якої iз змiнних, на яких визначена функцiя. Виконання цієї умови робить неефективним розв’язання систем булевих рівнянь за методом виключення змінних. Формально, булева функцiя
 визначена на множинi   набoрiв  змiнних  ,  задовольняє критерiю максимуму умовної ентропiї або SAC- критерiю , якщо виконується:
 (2)
З точки зору синтезу нових, стiйких до аналiтичних методiв розкриття, алгоритмiв, то найбiльш суттєвою проблемою є одержання SAC-функцiй. В роботi виконано теоретичне дослiдження цього важливого для систем захисту iнформацiї класу булевих функцiй, що дозволило розробити ряд методiв одержання таких функцiй.
Будь-яка булева функцiя  завжди може бути представлена в виглядi:
 (3)
Теоретичною основою розроблених методiв побудови алгебраїчних нормальних форм булевих SAC - функцiй являється наступна, доведена в роботi теорема.
Теорема Для того, щоб булева функцiя  задовольняла SAC необхiдно i достатньо, щоб кожна з  функцiй  була балансною.
Використовуючи цю теорему в роботi доведено важливе для практики положення:
Булева функцiя  задовольняє SAC-критерiю, якщо цьому критерiю задовольняє функцiя  , а функцiя  є лiнiйною функцiєю, або, що те ж саме: додавання до SAC-функцiї лiнiйної функцiї не порушує її вiдповiднiсть SAC- критерiю.
Виходячи з наведеної теореми задача одержання SAC-функцiї трансформується в задачу вiднаходження системи  балансних булевих функцiй от  змiнних:
 (4)
где  - множина  всiх можливих значень булевих змiнних  . Булева функция, що задовольняє SAC-критерiю формується у виглядi:
 (5)
На основi наведених теоретичних засад розроблена методика формального одержання алгебраїчної нормальної форми SAC -функцiї, яка полягає в послiдовному виконаннi cлiдуючих дiй:
- Множина змiнних
 раздiляється на двi непересічних між собою пiдмножини:  та  .
- Довiльним чином задається вiдношення
 , що спiввiдносить кожний елемент множини  одному з елементiв множини  . Практично це вiдношення визначає множину пар елементiв множин  та  .
- Будуються k булевих функцiй
 ,  ,  причoму  , у виглядi:
 (6) причому функцiї  i  вибираються довiльно.
- Будуються
 булевих функцiй  ,  ,  причoму  , у виглядi:
 (7)
де  - функцiя, що вибирається довiльним чином i не залежить вiд  .
- Вiдшукувана булева SAC-функцiя
 може буди одержана як диз’юнкція всiх кон’юнкцiй змiнних xi и ранiш одержаниx часткових балансних булевих функцiй 
 (8)
Доведено, що запропонований метод забезпечує одержання SAC-функцiї, максимальнa степiнь термiв якої cтановить  при гарантованiй нелiнiйностi  . Доведенi теоретичнi засади можуть слугувати за основу розробки методiв побудови SAC-функцiй високих порядкiв.
Нижче наведено запропонований в роботi метод генерацiї SAC-функцiй m- порядка:
- Множина змiнних
 подiляється на двi пiдмножини: та  , причому кiлькiсть змiнних в кожнiй з пiдмножин має бути не меншим за  .
- Визначається множина
 пар змiнних, що не належать одночасно множинам  та  , причому кiлькiсть пар, в якi входить кожна iз змiнних  має бути не меншим за  , а самi пари, що входять до множини  не повиннi повторюватися.
- SAC-функцiя
 - го порядку формується в такому виглядi:
| 
