Оцінка стійкості направленого шифру NTRU до атаки, заснованої на змінних значеннях часу розшифрування

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

68

ІSSN 0485-8972 Радиотехника. 2014. Вып. 176

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

Оцінка стійкості направленого шифру NTRU до атаки, заснованої на змінних значеннях часу розшифрування

УДК 621.391:519.2:519.7

А.П. Бубир, І.Д. Горбенко, д-р техн. наук

11.01.2014

Вступ

Нині суттєву актуальність має проблема підвищення швидкодії направленого шифрування. Але вона повинна бути вирішеною за умови забезпечення експоненційної складності криптоаналізу проти атаки типу «повне розкриття». Для її вирішення широке розповсюдження та використання отримали криптографічні механізми й протоколи направленого шифрування, що ґрунтуються на перетвореннях в кільцях, полях та групах точок еліптичних кривих. Як показує аналіз, усі вони є обчислювально складними, але тільки перетворення в групі точок ЕК забезпечує експоненційну складність атаки «повне розкриття».

Перспективним напрямом вирішення протиріччя, яке міститься в необхідності зменшення складності (збільшення швидкодії) прямого та зворотного криптоперетворень направленого шифрування, є застосування алгоритму направленого шифрування в фактор-кільцях, що отримав назву NTRU [1 - 3]. Підтвердження цьому є прийняття стандарту ANSI X9.98 [1] та значне його впровадження для направленого шифрування. Основний позитивний ефект, який досягається при використанні таких перетворень - це підвищення швидкодії на два-три десяткові порядки. Але, на наш погляд, стійкість даного класу асиметричних крипто перетворень вивчена недостатньо і маються відповідні сумніви відносно неї. Тому важливими як теоретичними так і практичними є завдання доведення криптографічної стійкості крипто перетворень в фактор - кільці. Серед атак, що вимагають відповідного аналізу відносно їх вразливості, є атаки, що засновані на аналізі часу розшифрування певного обсягу зашифрованої інформації [1, 3].

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

1. Загальна інформація про атаку

В NTRU [1] в процесі зашифрування та розшифрування використовуються дві геш-функції. Позначимо їх як G та H. На практиці зазвичай використовується SHA-1 або SHA-256 (в залежності від рівня стійкості). Ця атака заснована на тому факті, що кількість викликів SHA у якості складової геш-функції G залежить від вхідних даних. Таким чином, вимірюючи час розшифрування, криптоаналітик може отримати інформацію про дані, що були передані на вхід G, що, в свою чергу, розкриває інформацію про особистий ключ f.

Введемо наступні позначення:

;

На практиці при шифруванні за алгоритмом NTRUEncrypt вихідне повідомлення перетворюється у поліном спеціальним чином [1]. Процес шифрування із урахуванням такого перетворення виглядає так:

1) - вихідне повідомлення після процедури доповнення (padding);

2) - сеансовий ключ (зазвичай до повідомлення додають ще так звану «сіль» - рядок випадкових бітів, але для даної атаки обрана така схема генерації r);

3) - замасковане відображення M у якості елемента фактор - кільця.

Далі обчислюється шифротекст за вже відомим співвідношенням:

.(1)

Алгоритм розшифрування в першу чергу відновлює відображення повідомлення m' та вихідне повідомлення M та використовує їх для відновлення r та перевірки, що (m', e) - дійсна пара для алгоритму NTRUEncrypt.

1) - відновлення образу-кандидата m';

2) - розмаскування m' та отримання M;

3) - відновлення сеансового ключа r, що використовувався при шифруванні.

Тепер можна перевірити, чи дорівнює e значенню виразу . Якщо це не так, вважається, що виникла помилка розшифрування, і розшифроване повідомлення відкидається.

Основою цієї атаки є спосіб, у який G використовує SHA для отримання r з M. Зауважимо, що на етапі розшифрування e та m' повністю визначають M, і, таким чином, час на обрахунок . Також вимагається, щоб сеансовий ключ r був бінарним поліномом, що містить точно одиниць. Процес обчислення r з M, описаний у [2], може використовувати різну кількість ітерацій алгоритму SHA для різних значень M.

Те ж саме твердження справедливе і для процедури розшифрування: необхідна кількість викликів геш-функції SHA для відновлення ключа сеансу із пари образ повідомлення/криптограма може різнитись в залежності від значень пари (m', e).

2. Часовий слід шифротексту

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

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

,(2)

та введемо бінарну функцію , що приймає свої значення за наступним правилом:

(3)

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

Тому для даної пари далі будемо здійснювати обернення (ротації) виду . Визначимо також часовий слід пари як бінарний вектор

(4)

Часовий слід показує, скільки викликів потрібно для кожного обернення пари .

Нехай P - це ймовірність того, що випадково обрана вимагає не більше, ніж K викликів, а 1 - P - ймовірність того, що вимагається не менше, ніж K + 1 викликів геш-функції. Якщо ні P, ні 1 - P не є малими значеннями, ймовірність того, що дві пари та матимуть однакові часові сліди, є доволі малою. Знайдемо вираз для цієї ймовірності.

Ймовірність того, що співпадуть перші координати двох випадкових часових слідів, дорівнює:

. (5)

Тоді ймовірність того, що два часові сліди співпадають (тобто співпадають всі їхні координати), обчислюється так:

(6)

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

. (7)

3. Опис атаки

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

. (8)

Зауважимо, що саме цей набір відображень повідомлень абонент повинен отримати після розшифрування шифротекстів із набору . Тобто вважається, що ймовірність

є не дуже низькою.

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

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

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

Подібним чином крипто аналітик відсилає кожен з поліномів адресату і отримує значення . Помітимо, що

(9)

Отже, аналітик, маючи всі N значень функції , дізнається часовий слід для пари .

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

. (10)

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

4. Оцінка захищеності NTRU від даної атаки

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

До даної атаки потенційно вразливі всі існуючі реалізації алгоритму НШ NTRU. Опишемо детальніше, як саме використовується геш - функція сімейства SHA при генерації сеансового ключа r згідно із [2]. Зауважимо, що саме ця версія із деякими змінами та модифікаціями була покладена в основу стандартів IEEE P 1363.1 та ANSI X9.98 (основні відмінності - використання двійкових поліномів замість тернарних).

Алгоритм атаки.

1. Фіксується таке значення c, яке задовольняє умові 2^c > N. Це значення задане в [2] для кожного із наборів параметрів. Також обчислюються змінні та . b - це значення параметру с у байтах, nN - найменше кратне N, що є меншим за 2^c.

2. Визивається зазначена у наборі параметрів версія SHA, її вихід розбивається на сегменти довжиною b байт кожен. У кожному сегменті враховуються тільки с молодших бітів (інші 8b - c бітів вважаються рівними нулю), які перетворюються на цілі числа (кодування - little endian) . Тут t - таке ціле число, що tb дорівнює довжині виходу відповідної версії SHA.

3. За наступним алгоритмом згенерувати r:

(1) jList = {}

(2) Викликати геш - функцію SHA для отримання

(3) Loop

(4) If jList

then додати в jList

(5) If jList вже містить d_r елементів, вийти.

(6) Кінець циклу .

(7) Перейти на крок (2) для отримання більшої кількості значень i.

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

, (11)

, (12)

. (13)

Ймовірність того, що буде достатньо не більше, ніж s викликів SHA (тобто що st випадково обраних цілих чисел в діапазоні включають як мінімум d_r значень з діапазону , які відрізняються за модулем N) описується виразом

. (14)

Відмітимо, що формули цих ймовірностей є універсальними та можуть бути застосовані до всіх сучасних реалізацій NTRUEncrypt. Нами була виконана практична реалізація обчислень ймовірності того, що знадобиться не більше, ніж s викликів геш-функції згідно із формулами (11) - (14) для кожного із наборів параметрів згідно із стандартом ANSI X9.98. Результати обчислень представлені в таблиці. Також згідно із співвідношенням (6) були обраховані ймовірності того, що дві різні пари та матимуть однакові часові сліди (див. стовбці P_nonunique таблиці).

Зловмисник зацікавлений в якомога меншому значенні ймовірності спів падіння часових слідів P(T₁ = T₂). Тоді з дуже високою ймовірністю (а саме 1 - P(T₁ = T₂)) отриманий слід є унікальним, тобто була віднайдена дійсна пара . При цьому необхідність перевірки правильності відпадає.

Аналізуючи вираз (6), можна помітити, що найменшого значення ймовірність P(T₁ = T₂) досягає тільки тоді, коли ймовірність того, що буде достатньо не більше, ніж s викликів функції хешування, буде дорівнювати 0,5.

Висновки

1. Отримані експериментальні результати показали, що найкращі шанси на відновлення особистого ключа криптоаналітик мав би у випадку використання наборів параметрів ees659ep1 (рівень стійкості 112 бітів), ees677ep1, ees887ep1 (192 біти) та ees1171ep1 (256 бітів), але лише за умови, коли s дорівнює 4, 11, 6 та 8 відповідно.

2. Для запобігання атаці необхідно досягти постійного часу розшифрування за рахунок встановлення такої кількості викликів функції хешування s (в термінах стандарту ANSI X9.98 - параметр minCallsR), якої гарантовано (з ймовірністю, практично рівною одиниці) було достатньо для переважної більшості вхідних даних. Наприклад, для набору параметрів ees659ep1 при minCallsR = 4 атака завершиться успіхом з дуже високою ймовірністю, а вже при minCallsR = 5 вона стає практично нездійсненною (тому що ймовірність колізії часових слідів наближається до одиниці).

3. Розробники ANSI X9.98 вважають, що практично постійний час розшифрування може бути отриманий шляхом вибору такого параметру oLenMin, при якому ймовірність того, що знадобиться більше, ніж oLenMin октетів виходу, менша, ніж 2^-k, де k - рівень стійкості, oLenMin = minCallsR * hLen, hLen - довжина в октетах виходу геш-функції. Параметр minCallsR повинен бути таким найменшим цілим числом, що ймовірність того, що знадобиться більш, ніж oLenMin октетів, буде менша за 2^-k.

4. Розробники навмисно завищили значення параметру minCallsR для всіх наборів параметрів більше, ніж удвічі, щоб гарантовано унеможливити практичну реалізацію timing-атаки на поточну версію NTRUEncrypt та створити деякий запас стійкості на майбутнє. Для наведеного вище прикладу (набір параметрів ees659ep1) при теоретично достатньому для забезпечення стійкості значенні minCallsR = 5, 6 стандарт рекомендує використовувати при виробленні сеансового ключа r 11 ітерацій гешування за алгоритмом SHA-1.

Отже, реалізація алгоритму НШ NTRU із використанням наборів параметрів, описаних у стандартах ANSI X9.98, IEEE P 1363.1 є стійкою до даної атаки, тому вона може бути рекомендованою до застосування.

Список літератури

1. American National Standard for Financial Services ANSI X9.98-2010 Lattice Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry. - 2010. 3. Jens Hermans, Frederik Vercauteren, Bart Preneel. Speed records for NTRU. Режим доступу: www/ URL: https://www.securityinnovation.com/uploads/ntru_speed_benchmark_research.pdf. - 2010.

2. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. - Харків : ХНУРЕ, Форт, 2012. - 868 с.

3. Consortium for Efficient Embedded Security, Efficient Embedded Security Standard (EESS) #1 version 3, 2005. - Режим доступу: www/ URL: http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf.

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