1 Методи та механізми 2014. 1. 1 Основні послуги при застосуванні, уніфікація та стандартизація криптографічних перетворень
 Скачать 1.75 Mb.
|
|
.Якщо повідомлення, що має бути відновлене, довше ніж 20 байт, можна розраховувати на те, що деякі вимоги до форматування повідомлення становлять щонайменше 10 байтів натуральної збитковості. Тоді надлишок складе 20 байтів – друга частина підпису. У гіршому випаду, якщо натуральна збитковість відсутня, можна додати 10 байтів збитковості. Аналіз складності реалізації ЦП з відновленням повідомлення. У табл. 1.20 наведено значення числа операцій, що необхідно виконати для алгоритмів обчислення ЦП, які входять до [45, 46, 12]. Таблиця 1.20 - Число операцій, що виконуються при обчисленні підпису
У табл. 1.21 наведено значення числа операцій, що необхідно виконати для алгоритмів при перевірці ЦП. Таблиця 1.21 - Число операцій, що виконуються при перевірці підпису
У табл. 1.22 наведено значення числа операцій, що необхідно виконати для алгоритмів додавання та подвоєння в різних базисах. Таблиця 1.22 - Складність додавання та подвоєння в різних базисах
Сутність названих ЕП та властивості детальніше розглянуті в [20-22], а також в 6 розділі цієї монографії. Але необхідно відмітити, що основні види атак на ЕП та загроз залишаються такими ж, що і для ЕП з додатком. Особливість реалізації атак пов’язана зі зменшенням довжини ЕП та використанні різного характеру збитковості]. Також існує достатньо широкий клас групових та кільцевих підписів, їх сутність та застосування викладені в [ 20-22, 146] та розділі цієї монографії. 1.8 Сутність, вимоги, класифікація та стандартизація криптосистем типу функція гешування Функції гешування (ФГ) є примітивами, що використовуються в різних криптографічних і не криптографічних додатках для надання послуг з безпеки інформації. Але на практиці підтверджено, що найбільш інтенсивним та, в ряді випадків безумовно необхідним, є застосування ФГ для надання електронних довірчих послуг, що пов’язані е електронним підписом (ЕП) та криптографічними протоколами(КРП). Зважаючи на вказане історично ФГ приділялась велика увага, в тому числі національними та міжнародними організаціями стандартизації ISO та IEC[193, 194, 254-255,350, 407, 409]. Розроблено та застосовується значне число ФГ, різних за призначенням та характеристиками і можливостями. Підтвердженням цього є організації та проведення 5 - річного міжнародного проекту «NIST SHA-3 Competition» [196, 189] У цьому підрозділі розглядаються сутність, вимоги, класифікація та стан стандартизації криптосистем типу ФГ. Більш детально ФГ в контексті їх історичної появи та застосування, а також створення ФГ 21 - століття, розглядаються в 4 розділі цієї монографії. 1.8.1 Основні визначення, сутність та загальні вимоги до ФГ У 2007 році Національним інститутом стандартизації США (NIST), зважаючи на особливу актуальність і роль ФГ в криптографічних додатках, а також необхідність забезпечення необхідних властивостей, було розпочато відкритий конкурс на проект нового федерального стандарту гешування SHA-3, що отримав назву «NIST SHA-3 Competition» [410,346, 350,299,42-43]. Необхідність розробки проекту нового стандарту гешування перш за все була обумовлена появою повідомлень про успішну теоретичну побудову атак на такі функції гешування, як ГОСТ Р 34.11-94 (ДСТУ ГОСТ 34.311-2009) та SHA-1, що ще широко застосовувались у той час на практиці. Основні визначення відносно ФГ. Основними конструктивними елементами ЕП і кодів автентифікації повідомлень(КАП) є ФГ. Визначення названих ФГ та їх криптографічних властивостей розглянемо орієнтуючись на роботи [350, 346,42. 43, 346, 20-22]. Визначення 1. Функцією гешування називається функція відображення h: D → R, де область значень D = {0,1}*, а R ={0,1}n для деякого n ≥ 6. Визначення 2. Функцією стиснення називається функція відображення f: D → R, де D = {0,1}a × {0,1}b і R ={0,1}n для деяких a, b, n ≥ 1 і a + b ≥ n. Визначення 3. Ітераційною функцією гешування від функції стиснення f: ({0,1}n × {0,1}b) → {0,1}n є функція гешування h: ({0,1}b)* → {0,1}n, яка визначена як h(X6..Xt) = Ht, де Hi = f (Hi −1, Xi) при 1 ≤ i ≤ t (H0 = IV). ФГ – це ітеративні конструкції, що використовують функцію стиснення f, роблять попередню розбивку даних X на під блоки Xi та виконують зв’язування по зворотному входу проміжних результатів обчислення геш-значень. Стандартна модель ітеративної функції гешування визначена в ISO/IEC 10118-1[ 193 ]. На рис. 1.14 наведена загальна модель ітеративної функції гешування. Узагальнена модель ітеративної функції гешування для t під блоків визначається таким алгоритмом ітеративних обчислень: H0 = IV Hi = f (Hi – 1, Xi), 1 ≤ i ≤ t, (1.183) h(K, X) = g(Ht), де цифра IV позначає початкове значення, що може бути деякою константою, а g є вихідною результуючою функцією перетворення.  Рис. 1.14 Модель ітеративної функції гешування Безумовними вимогами до ФГ є їхня стійкість до обчислення прообразу, другого прообразу, а також стійкість до колізій [236, 350, 20-22]. Визначення 4. Стійкість до обчислення прообразу. Функція гешування h:{0,1}* → R є стійкою до обчислення прообразу (t, ε, Ih), якщо не існує ймовірнісного алгоритму Ih із вхідними значеннями X R і значеннями на виході Y {0,1}*, часом виконання менше (не більше) ніж t, де h(X) = Y та ймовірністю, не менше ніж оцінена при випадковому виборі Y та Ih. Вимога до ФГ, що наведена в визначенні 4, має важливе значення для систем автентифікації, що ґрунтуються на використанні геш-значення паролів і таємних ключів. Визначення 5. Стійкість до обчислення другого прообразу. Нехай S – кінцева підмножина {0,1}*. Функція гешування h:{0,1}*→ R є стійкою до обчислення другого прообразу із захищеністю (t, ε, S), якщо не існує ймовірнісного алгоритму Sh, з X R та X′ {0,1}* з часом виконання менше ніж t, де X′ ≠ X і h (X′) = h (X) і ймовірністю, не меншою ніж оцінена при випадковому виборі X і Sh. Стійкість функцій гешування до обчислення другого прообразу визначає безпеку систем автентифікації. Визначення 6. Стійкість до колізій. Функція гешування h: {0,1}* → R є стійкою до колізій із захищеністю (t, ε, R), якщо не існує ймовірнісного алгоритму Ch з відомими вхідними значеннями X, X′ {0,1}*, часом виконання менше ніж t, де X′ ≠ X і h (X) = h(X′) і ймовірністю, не меншою ніж оцінена при випадковому виборі Ch. Стійкість функцій гешування до колізій визначає безпеку систем автентифікації з цифровим підписом. Визначення 7. Функція гешування називається простою, або слабкою (одно направленою), якщо вона є стійкою тільки до обчислення прообразу та до обчислення другого прообразу. Визначення 8. Функція гешування називається сильною, або стійкою до колізій, якщо вона є стійкою до обчислення прообразу, стійкою до обчислення другого прообразу та стійкою до колізій. Визначення сильної функції гешування показує, що для неї обчислювано неможливо знайти яку-небудь колізію. Вона також забезпечує захист атак, що базуються на парадоксі «про день народження». 1.8.2 Класифікація атак на ФГ. В [20-22, 42-43, 346, 350, 109] визначені основні атаки на ФГ. Розглянемо їх. 1. Атака методом «груба сила»або атака на визначення випадкового (другого) прообразу може бути виконана для визначення прообразу за заданим геш - значенням. Вона може бути застосована також для визначення прообразу, що дає задане геш-значення. Сутність атаки полягає в послідовному або випадковому перебиранні вхідних повідомлень та порівнянні результату виконання функції гешування із заданим. Успіх атаки при рівно ймовірних появленнях геш-значень буде дорівнювати 2-n, де n – довжина геш-значення в бітах. Складність такої атаки оцінюється 2n – 1 операцій обчислення геш-значень. 2. Атака методом парадоксу «про день народження» може здійснюватись для знаходження двох різних повідомлень з однаковими геш - значеннями. Ця атака заснована на парадоксі «дня народження» і полягає в тому, що у двох генерованих множинах геш-значень, що містять n1 і n2 елементів відповідно, імовірність знаходження елементів, що збігаються, між цими множинами оцінюється виразами: P «1 – exp (–n1n2/ 2n). При n1 = n2 = 2n/2 складність атаки оцінюється як 2n/2 + 1 операцій обчислення геш-значень, а ймовірність успіху дорівнює: P =1 – 1/e (0.63). 3. Атака «зустріч посередині» є модифікацією атаки методом парадоксу «дня народження» і використовується для геш-функцій із циклічною структурою, якщо циклова функція  є такою, що інвертується стосовно проміжного значення  або блоку повідомлення  . Ця атака за складністю порівнюється з атакою методом парадоксу «дня народження».4. Атака з корекцією блоку може здійснюватись у випадку, якщо порушник має повідомлення і хоче змінити в ньому один або більше блоків без зміни геш-значення. Наприклад, функція гешування MD5 є вразливою до цієї атаки. 5. Атака з фіксованою точкою може застосовуватися за умови, що циклова функція  має одну чи декілька фіксованих точок. Фіксованою точкою називається блок повідомлення Xi, для якого виконується умова:f (Hi – 1, Xi) = Hi – 1, тобто існує блок повідомлення Xi, що не змінює проміжний результат Hi – 1. Тобто, у повідомлення X можна додавати або видаляти блоки Xi без зміни геш-значення. 6. Атака на базовий алгоритм шифрування може здійснюватись для атаки на функції гешування, що базуються на блокових симетричних шифрах 7. Диференційні атаки. Може бути реалізована засобом застосування диференційного криптоаналізу. Така атака є потужним інструментом для аналізу не тільки блокових шифрів, але також і функцій гешування. При такій атаці досліджується вплив різниці вхідних даних функцій стиснення на відповідні вихідні різниці. Колізія виникає, якщо вихідна різниця дорівнює нулю. 8. Аналітичні слабкості. Такі атаки поєднують звичайні методи оптимізації та крипто аналітичні методи аналізу. Особливість цих атак полягає в тому, що зміни контролюються тільки в деяких точках алгоритмів; на відміну від диференційного криптоаналізу, де аналізу піддаються всі спільні диференціали деякого ступеня. В табл. 1.23 наведено теоретичні значення обчислювальної стійкості функцій гешування. Таблиця 1.23 Обчислювальна стійкість функцій гешування
1.8.3 Основні застосування ФГ Аналіз показав, що у сучасній криптографії необхідно виділити такі додатки [20-22, 148, 193- 194, 254-255, 346, 350, ] ФГ (рис. 1.15): протоколи електронного підпису; контроль цілісності даних з використанням спільного секрету (наприклад ФГ HMAC); контроль цілісності даних без використання спільного секрету; генерація псевдовипадкових послідовностей; протоколи встановлення ключів; протоколи автентифікації по паролю тощо.  Рисунок 1.15 – Класифікація ФГ згідно криптографічних застосувань 1.8.4 Вимоги до функцій ґешування для криптографічних застосувань у алгоритмах ЕП ФГ знайшли найбільше застосування при побудові ЕП, де їх основна властивість стиску даних повинна бути органічно поєднувана із додатковими вимогами ЕП [20-23, 132, 143,148, 191, 218, 234, 235, 218 ]. Криптографічні перетворення типу ЕП, є досить повільними, тому їх важко застосувати до довгих повідомлень. Щоб уникнути складних обчислень можна обчислити деякий образ повідомлення – ґеш-значення, що має фіксовану довжину. Тому функції ґешування в суттєвій мірі використовуються як частина механізмів ЕЦП і забезпечувати вимоги, які висуваються до ЕП. Узагальнення вимог, на наш погляд, краще виконати [ 12, 20-22] використовуючи підходи, що ґрунтуються на застосуванні системи безумовних та умовних критеріїв. До безумовних критеріїв будемо відносити ті, виконання яких для криптографічних застосувань типу ґешування є обов’язковим, тобто безумовним. При обґрунтуванні та узагальненні вимог будемо вважати, що функція ґешування дозволяє обчислювати вихідне значення (ґеш - код) з довжиною hlen при довільній довжині lм вхідного повідомлення М. Проведені дослідження показали, що сучасні та перспективні функції ґешування мають неодмінно відповідати таким вимогам: - складність знаходження колізії
- складність відновлення прообразу М
– складність знаходження іншого прообразу
- складність знаходження колізії, усіченої на  символів
Наведені вимоги дозволяють ввести безумовні критерії оцінки j-ї функції ґешування для криптографічних застосувань. Можуть бути введені також умовні критерії. Детальніше безумовні та умовні критерії та їх застосування розглядаються в 4 розділі цієї монографії. 1.8.5 Основні ФГ, що знайшли розповсюдження Якщо орієнтуватись на стандарт ISO/IEC 10118, то необхідно виділити наступні підходи до побудування функції ґешування [193,194,254, 255 ]: на основі блокових симетричних шифрів; на асиметричних криптографічних перетвореннях; на основі спеціалізованих функцій ґешування; на основі sponge-структури, які можна також віднести до спеціалізованих функцій ґешування. Загальну класифікацію відомих ФГ наведено на рис. 1.16. Кожен з наведених на рис. 1.16 методів має свої переваги та недоліки, тому актуальною є задача обґрунтування підходів та методів побудування перспективної функції ґешування. Детальніше ФГ аналізуються в 4 розділі цієї монографії 1.8.6. Функції гешування, що розроблені за замовленням. Функції гешування за замовленням є функціями, спеціально розробленими для задач гешування. Вони оптимізують тимчасові витрати на обчислення, що пов’язані, насамперед, при виконанні алгоритму зі звертанням до пам’яті. Функції цього класу використовують алгоритми обчислень, що вперше реалізовані в проекті алгоритму MD4. У MD4-подібних алгоритмах поділяють повідомлення на блоки Xi та ланцюгову змінну Hi – 1 на 32-бітові слова або на 64-бітові слова для алгоритмів, запропонованих останнім часом. Функція стиснення модифікує ланцюгову змінну до нового значення Hi за допомогою поточного блоку повідомлення. Обчислення виконується за кроками. На кожному кроці змінюється попереднє значення, яке є словом ланцюгової змінної залежно від слова повідомлення або інших реєстрових значень. На кожному кроці обчислення функції стиснення виконується кілька циклів, і в кожному циклі слова блоку повідомлення використовують один раз. Основний крок алгоритму MD4 описується виразом вигляду: A = (А + f (B, C, D) + X[j] + y) << s[j]. (1.188)  Рисунок 1.16 – Основні види сучасних функцій ґешування Тут A, B, C, D – регістри, що містять чотири 32-бітових слова ланцюгової змінної. Операція «+» означає складання за модулем 232, та (…) << s-побітовий циклічний зсув слова на s позицій вліво. Нелінійна функція f визначає побітові обчислення, X[j] – слово повідомлення на j кроці, y – константа та s[j] – постійна зсуву. Функція f і константа y змінюються на кожному циклі обчислень. MD4 включає три цикли, що використовують мультиплексування, мажоритарну вибірку і функції виключне АБО (сума за модулем 2). Слова блоку повідомлення використовуються в обчисленнях на всіх кроках циклу. Кроки кожної операції є зворотними (можна виконати обчислення у зворотному порядку), але на останньому етапі обчислення функції стиснення здійснюється додаткова операція, що додає при обчисленні ланцюгової змінної Hi. Це робить функцію стиснення незворотною. Ланцюгова змінна Hi, що отримана на останньому кроці при обчисленні блоку повідомлення, який містить дані про довжину, є результатом гешування. На основі алгоритму MD4 зроблено кілька вдосконалень алгоритмів, що використовують для збільшення стійкості до прообразу та стійкості до колізії додаткові механізми. Ці ідеї включають збільшення числа циклів, деякі побітові операції на кроці обчислень і збільшення довжини ланцюгових змінних, що призводить до більш довгого значення функції гешування. Так, у сімействі SHA-1 використовується процедура розширення блоку повідомлення, що обчислює різницю слів на кожному кроці. У RIPEMD використовуються дві рівнобіжні схеми обчислення, які є модифікованими версіями MD4. У табл. 1.24 наведено порівняльні дані MD4-подібних алгоритмів. Таблиця 1.24 Параметри MD4-подібних функцій гешування
Функція гешування SHA-1 визначена у федеральному стандарті США FIPS 180-1, вона рекомендована NIST разом з DSA стандартом для цифрових підписів. NIST оновив цей стандарт, затвердивши стандарт FIPS 180-2, що включає, крім SHA-1, ще три нових функції гешування: SHA-2/256, SHA-2/384 і SHA-2/512, з функціями гешування відповідно з довжинами 256, 384 та 512 бітів. Додатково ANSI США прийняло також удосконалені банківські стандарти з відкритими ключами: стандарт Х9.30, у якому разом з DSA використовується алгоритм SHA-1 і стандарт Х9.31, у якому разом зі схемою RSA використовується алгоритм MDC-2. Також в ISO/IEC 10118 додатково введено функції гешування, що включені до FIPS 180-2. У частині ISO/IEC 10118-2 визначені функції гешування, що засновані на блокових шифрах у конструкції Matyas-Meyer-Oseas, у ній незалежний блоковий шифр в алгоритмі MDC-2 із двома й більше функціями використовується для обчислення значення геш-функції подвійної та потрійної довжини відповідно. Частина 10118-3 [194] визначає три замовлених алгоритми: RIPEMD-128, RIPEMD-160 і SHA-1. Ця частина стандарту на цей час переглянута. Окрім зазначених трьох алгоритмів, прийняті функції гешування: SHA-2/256, SHA-2/384, SHA-2/512 і Whirlpool. Частина 10118-4 [255] описує MASH-1 та MASH-2 функції гешування, що використовують модульну арифметику. Розглянемо перспективні функції гешування: Whirlpool та SHA-2/256, SHA-2/384, SHA-2/512. У табл. 1.25 і 1.26 подано характеристики, властивості та аналітичні результати оцінки швидкодії алгоритму Whirlpool у порівнянні з іншими відомими алгоритмами. З аналізу цих таблиць випливає, що Whirlpool уступає багатьом алгоритмам за швидкодією, але однією з головних переваг алгоритму Whirlpool залишається розмір геш-значення, що дорівнює 512 бітам. У табл. 1.26 подано дані, що показують витрати часу на обчислення геш-значення/ ініціалізацію програми/ ініціалізацію програми та її завершення. При цьому одиниці виміру такі: – час обчислення геш-значення виміряється в числі циклів процесора на байт; – час ініціалізації програми та її завершення – у числі циклів процесора. Стійкість алгоритму Whirlpool ґрунтується на виборі таблиці підстановок S і наявності квадратичних залежностей між вхідними і вихідними блоками таблиці, а також впливу числа циклів вбудованого блокового шифру на безпеку алгоритму. 1.8.7 Сутність та результати виконання міжнародного проекту NIST SHA-3 Competition Національним інститутом стандартизації (NIST) США у 2007 р. розпочато відкритий конкурс на проект нового федерального стандарту на ФГ, який отримав назву «NIST SHA-3 Competition» [350, 346, 42-43,109]. Потреба розробки нового стандарту гешування, що отримав назву SHA-3, обумовлена появою повідомлень про існування атак на функції гешування SHA-1 та MD5, які широко використовуються у світі, а також на ДСТУ ГОСТ 34.311- 2009[407]. Тому щоби запобігти ситуації, коли всі стандартизовані функції гешування можуть бути компрометованими, NIST США у 2007 році оголосив по суті міжнародний конкурс на перспективні ФГ. Окрім того, з точки зору практики, з’явилося ряд побажань, а скоріше вимог щодо підвищення швидкодії гешування, тобто зменшення складності обчислення функцій гешування. Зазначена вимога особливо актуальна з боку таких додатків як електронний цифровий підпис, вироблення псевдовипадкових послідовностей, криптографічні протоколи тощо. Таблиця 1.25 Характеристики функцій гешування
Таблиця 1.26 Продуктивність функцій гешування
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
;
;
;
.