67325

Коди автентифікації на основі БСШ та їх властивості

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-07

411.63 KB

3 чел.

Лекція № 16 о (4.2 ) з

Дисципліни     «Прикладна криптологія»

Тема лекції

«Коди автентифікації на основі БСШ та їх властивості »

                            ОСНОВНІ НАВЧАЛЬНІ ПИТАНННЯ

16.1 Визначення та класифікація кодів автентифікації повідомлень

16.2  Оцінки стійкості МАС кодів при імітації та підміні

Додаток А Приклади оцінки стійкості КАП

Завдання для самостійної роботи:

  1.  доопрацювати лекцію;
  2.  розібрати задачі із додатку А 

Джерела, що рекомендуються  до самостійної роботи

  1.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Монографія (електронний варіант). Харків, ХНУРЕ, 2011 р.
  2.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний конспект лекцій. Харків, ХНУРЕ, 2011 р.
  3.  Горбенко І. Д. Гриненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник. Ч.1. Криптографічний захист інформації - Харків: ХНУРЕ, 2004 - 368 с.
  4.  Горбенко Ю.І., Горбенко І.Д. Інфраструктури відкритих ключів . Системи ЕЦП. Теорія та практика. Харків.  Форт. 2010 , 593с.

Додаткова лтература

1.В. Задірака . Компьютерная криптологія. Підручник. К, 2002 ,504с.

2. А. Менезис, П. Ван Аршот, С. Ватсон. Руководство по прикладной криптографии CRC Press, 1997, электронная копия, 662 с

3. Брюс Шнайер. Прикладная криптография. М., изд. Триумф. 2002 г., 797 с

16.1 Визначення та класифікація кодів автентифікації повідомлень

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

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

Сутність режиму обчислення КАП(МАС).  Інформація розбивається на блоки довжиною L бітів. Перший блок перед зашифруванням складається з ключем автентифікації Ка довжиною L бітів. Потім кожен  блок зашифрується в блоковому режимі з використанням вихідного ключа зашифрування Кз. Процес повторюється для усіх блоків. При цьому перед зашифруванням Мі блоку він складається з Сі-1 блоком криптограми. Таким чином, останній блок Сп залежить від усіх Мі блоків, ключа автентифікації та ключа зашифрування, тобто:

.  

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

М1

М2

М3

Мп

БСШШ

БСШ

БСШ

БСШ

С1

С2

С4

С3

Кш

Кш

Кш

Кш

Ка

Рисунок 1– Алгоритм зашифрування зі зв’язком за шифрованим текстом

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

.

Необхідно зазначити, що одночасно з формуванням імітоприкладки здійснено

зашифрування повідомлення М. При цьому довжина зашифрованого повідомлення дорівнює довжині вихідного повідомлення, тобто автентифікацію здійснено без збільшення довжини зашифрованого повідомлення. Особливістю цього режиму є те, що додатково використовується ключ автентифікації. Якщо повідомлення не має зашифровуватися, то в цьому випадку до нього додається імітоприкладка і довжина автентифікованого повідомлення збільшується на lб=128 бітів, а саме автентифіковане повідомлення має вигляд {M, Іімп}. Основною перевагою такого методу автентифікації є висока швидкість перетворення і, як наслідок, можливість обчислення значення імітоприкладки в реальному плині часу. Основним недоліком є те, що використовувані ключі Кз та Ка є симетричними, а тому не дозволяють реалізувати захист на основі моделі взаємної недовіри.

Визначення кодів автентифікації повідомлень. Згідно  [274], МАС код це функція відображення : , де – простір ключів, – простір повідомлень, а   – простір МАС значень для . Для заданих значень ключа та повідомлення , функція виробляє МАС значення .

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

Узагальнена модель ітеративного МАС коду для під блоків визначається таким алгоритмом ітеративних обчислень:

,

,                                                                                      (4.23)

.

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

При побудові КАП (МАС) можна виділити такі основні підходи:

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

МАС коди, що побудовані на основі блокового шифру, використовують шифрування в режимі зчеплення шифр текстів[ 273, 142, 4, 13 ].

Визначення 4..1 МАС код, що використовує блоковий шифр у СВС режимі визначається виразом .

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

Але основна CBC- конструкція є вразливою до атаки типу exor підробки і отже може використовуватися лише в додатках, де повідомлення мають фіксовану довжину. Також існують декілька більш захищених різновидів цього алгоритму: EMAC та RMAC схеми. EMAC код використовує додаткове шифрування вихідного результату перетворень, ключ для цієї операції шифрування може бути отримано із ключа MAC. RMAC алгоритм заміняє останнє шифрування на шифрування з двома ключами. Безпечність цих конструкцій може бути доведено за умови, що основний блоковий шифр є псевдовипадковим [275]. Усі ці схеми містяться в ISO/IEC 9797-1, що є міжнародним стандартом для кодів автентифікації повідомлень, що використовують блокові шифри [94].

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

Визначення 4.2. HМАС код визначається виразом .

Для визначення 4.2 ключ доповнюється нульовими бітами до повного блоку, opad та ipad – постійні значення. Автор роботи  [276] та інші  довели безпечність цієї конструкції базуючись на таких припущеннях:

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

В деякому змісті альтернативою HMAC кодам є MDX-MAC конструкції [277], які засновані на MD5, SHA та RIPEMD геш - функціях. Тут, основна геш - функція перетворена в МАС код за рахунок внесення невеликих модифікацій: включення секретного ключа на початок, на кінець та до кожного кроку ітераційного обчислення геш - функції. Захищеність MDX-MAC може бути доведено за умови, що основна функція стискання є псевдовипадковою.

Замітимо, що HMAC та MDX-MAC алгоритми включено до ISO/IEC 9797-2 [95].

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

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

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

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

Визначення та вимоги безпечності до кодів автентифікації повідомлень.

Розглянемо випадок, коли зловмисник може підробити повідомлення для МАС коду , якщо, не знаючи випадкового ключа , він здатен створити нове повідомлення та МАС значення таке що .

Визначення 4.4 [1]. МАС код є – секретним, якщо, при випадково взятому ключі , зловмисник не може підробити нове повідомлення за час із імовірністю вищою від навіть якщо він (на свій вибір) має змогу отримати значень МАС кодів інших повідомлень.

Залежно від інформації, доступної зловмисникові, розрізняють такі типи атак на коди автентифікації повідомлень[142. 273, 11- 13 ]:

- Атака з відомим текстом. Зловмисник має можливість досліджувати деякі відкриті тексти та відповідні їм значення коду автентифікації повідомлень.

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

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

"Злом" алгоритму МАС коду може мати різні наслідки:

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

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

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

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

Відомі на той час атаки на коди автентифікації повідомлення розглянуті в [273].

Розглянемо ці атаки детальніше.

Угадування коду автентифікації повідомлення (Guessing of the MAC). Це пряма атака на алгоритм МАС коду полягає у виборі довільного нового повідомлення, і згодом угадування значення коду автентифікації повідомлення. Вона може бути  зроблена такими способами :

  1.   вгадування МАС коду безпосередньо з імовірністю успіху ;
  2.   вгадування ключа, з подальшим обчислення значення МАС коду, з імовірністю успіху .

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

Вичерпний пошук ключа (Exhaustive Key Search). Це також  пряма атака, що може застосовуватися до будь-якого алгоритму. Атака вимагає приблизно відомих пар текст-MAC для даного ключа. Намагаючись визначити ключ, один за одним перебираються всі ключі. Очікуване число випробувань, що призведе до злому МАС алгоритму, дорівнює . На відміну від попередньої атаки, цю атаку можна здійснювати поза сеансом зв'язку (off-line).

Підробка, що заснована на внутрішній колізії (Internal Collision Based Forgery). Наслідок цієї атаки полягає в тому, що якщо виявити внутрішню колізію (збіг проміжних результатів при обчисленні значень МАС кодів), її можна використати, для підробки МАС коду на окремому обраному тексті.

В роботі  [277] показали, що внутрішню колізію для може бути знайдено, з використанням відомих пар текст-MAC та обраних текстів, де очікувані значення для і є такими (тут , позначає розмір у бітах пов'язаної змінної): , а , якщо вихід перетворення МАС коду є перестановкою; інакше, приблизно дорівнює .

Ключове відновлення на основі внутрішньої колізії (Internal Collision Based Key Recovery). Для ряду  функцій стискання, внутрішню атаку колізії можливо розширити до ключової атаки відновлення [278]. Ідея полягає в тому, щоб ідентифікувати одну або більше внутрішніх колізій; наприклад, якщо не є перестановкою для фіксованого , і внутрішня колізія після першого блоку повідомлення визначається рівнянням в якому та можливо є невідомим (передбачається, що залежать від ключа). Для деяких функцій стискання , можна одержати інформацію щодо секретного ключа, заснованого на таких відносинах.

Атака методом декомпозиції (Divide-and-Conquer Attack). Атака є спеціальним випадком ключового відновлення на основі внутрішньої колізії. Для деяких функцій стискання, які використовують два окремих ключа, можна використати внутрішні колізії для ключового відновлення [277]. Нехай ключі позначені як та . Загальна ідея полягає в тому, що порушник спочатку шукає деякі внутрішні колізії, а потім методом вичерпування визначає ключ , що зумовлює ці колізії. Після визначення для пошуку використовується вичерпний пошук. Тому  стійкість такого МАС коду залежить від його індивідуальних ключів, а не від їхньої загальної довжини. Вказана  атака менш практична, ніж простий вичерпний пошук ключа, оскільки необхідна велика кількість відомих пар текст - MAC.

Підробка Exor (Exor Forgery. Ця   підробка можлива, якщо значення обчислюється як функція та немає додаткового перетворення геш виходу. Найлегший варіант атаки вимагає одну відому пару текст - MAC. Припустимо, що вхід та його доповнююча версія складаються з одного блоку. Отже, якщо відомо , виходить що:

.    (4.24)

Таким чином, можна створити нове повідомлення (що буде підробкою) з тим же значенням МАС. Базова CBC-конструкція використовує обчислення та є вразливою до атаки типу exor підробки.

Визначення таємності та безпечності кодів автентифікації, оцінки колізійних характеристик розглянуті в [5, 106].

16.2  Оцінки стійкості МАС кодів при імітації та підміні

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

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

.    (4.25)

При рівно ймовірному виборі ключа, що еквівалентно вибору , необхідно враховувати розподіл МАС значень для конкретного повідомлення по ключовому просторі. Для імовірності імітації, що позначимо через імовірність імітації по ключу , справедливим є такий вираз:

,    (4.26)

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

Зрозуміло , що

.      (4.27)

Крім того,  всі записи в стовпцях масиву МАС кодів зустрічаються однакову кількість разів, маємо:

.      

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

.   (4.28)

Якщо не враховувати розподіл МАС значень для даного повідомлення по ключовому просторі, тоді ймовірність імітації позначимо як імовірність імітації по МАС значенню . Імітація через нав'язування МАС значення визначається тим, що з множини передбачуваних МАС кодів вибирається одне. Імовірність успіху буде визначатися виразом:

,    (4.29)

де – потужність множини можливих МАС значень для повідомлення .

Якщо МАС значення для повідомлення приймають повну множину значень , одержимо

.      

У загальному випадку справедлива така нижня границя:

.     (4.30 )

Якщо для повідомлення відомим є статистичний розподіл МАС значень, то оцінка для імовірності імітації по МАС значенню зводиться до оцінки імовірності імітації по ключу.

Верхня границя для імовірності імітації по МАС значенню буде визначається максимальним значенням по всьому простору повідомлень:

.   (4.31 )

Атака підміни заснована на тому, що порушник спостерігає та змінює його на , де . Імовірність підміни визначатиметься такою умовною імовірністю:

. (4.32 )

Вираз для імовірності підміни з використанням формули повної імовірності та статистики сприятливих спостережень матиме такий вигляд:

. (4.33 )

Верхня границя імовірності нав'язування шляхом підміни повідомлень та КАП визначається максимальною імовірністю успіху для всіх пар повідомлень, але  за умови рівно ймовірного вибору ключа.

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

Імовірність підміни за умови рівності визначається імовірністю колізії МАС коду та оцінюється виразом:

.(4.34 )

Для ймовірності підміни другого роду у випадку маємо:

(4.35)

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

16.3  Колізійні характеристики МАС кодів

Під стійкістю до колізій розуміють обчислювальну складність  знаходження двох повідомлень та таких, що[5, 12,13, 106  ]:

,     (4.36 )

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

Задача 1. Нехай є деяка функція перетворення повідомлення

,      (4.37 )

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

Задача 2. Нехай на виході перетворювача з повної множини значень формуються випадкових значень функції перетворення (4.37 1.14), причому та підкоряються рівно qмовірному закону розподілу. Нехай виконано експериментів, у кожному з яких отримано значень . Позначимо реалізації двох експериментів як та відповідно, причому та . Необхідно знайти ймовірність того, що ці множини містять у собі хоча б по одному елементу та , такі, що .

Розв’язання цих задач наведемо за результатами роботи [9].

Оцінка числа випробувань появи колізій . Проведений аналіз показав [106], що задача 1.1 може розв’язуватися з використанням «парадокса» про день народження, але при докладному розгляді з'ясувалося, що вона носить більш загальний характер. У нашому випадку є вибірка з значень цілочисленої випадкової величини з рівноймовірним законом розподілу, причому вона може приймати значення від 1 до , а . За цих умов необхідно знайти ймовірність того, що серед значень вибірки принаймні дві збігаються, тобто:

.

Для розв’язання задачі 1.1 знайдемо ймовірність того, що в групі з подій не відбудеться колізія, тобто співвідношення (1.13) не виконається жодного разу. Позначимо цю ймовірність як . Зрозуміло, що та складають повну групу подій, тобто:

та

.     (4. 38 )

Далі знайдемо загальну кількість  різних способів, якими можна одержати значень без повторень. Для першого елемента ми маємо значень без повторень, для другого , для третього – і т.д., для -го . Тому загальне число способів, при яких немає збігів виду (1.13) може розраховуватися як:

             (4.39 )

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

.      (4.40 )

Далі, ймовірність відсутності збігів можна оцінити співвідношенням числа варіантів без збігів (4.39) до загального числа варіантів (4.40), тобто:

.    (4.41  1.18)

Використавши вираз (4.38 ), маємо:

.     (4.42 )

Вираз (4.42) може бути використаний для оцінки необхідної ймовірності, проте бажано одержати загальний розв’язок рівняння (4.42), наприклад, для значення .

З цією метою представимо у вигляді:

   (4.43  )

Далі скористаємося тим, що для всіх [5] справедливим є:

.     (4.44 )

За малих значень (наприклад, ) можна вважати, що:

.     (4.45  )

Враховуючи це, перетворимо вираз (4.43), підставивши значення (4.45). У результаті маємо:

. (4.46 )

Позначимо , тобто ймовірністю, з якої має виникнути колізія. У результаті маємо:

,

або

.     (4.47)

Виконавши логарифмування (1.24), маємо:

.     (4.48 )

Перетворюючи (4.48), маємо:

,

або

.

У кінцевому виді одержуємо:

.     (4.49 )

Таким чином, отримано рівняння, в якому пов’язані три величини – число подій , загальне число подій та ймовірність , з якої повинна виникати колізія. Знаючи відповідне значення та можна одержати точний розв’язок.

Нехай , тоді з використанням (4.49) маємо:

.   (4.50)

Якщо рівняння (1.27) матиме вигляд:

.     (4.51)

Дамо оцінку значення , з огляду на те, що . З (4.49) отримаємо:

.     (4.52  )

При маємо:

та

.     (4.53)

За довільного значення з рівняння (4.52  1.29) одержимо:

.   (4.54  )

Співвідношення (4.54 ) дозволяє оцінити число перетворень (експериментів) , які необхідно здійснити для виникнення колізії з ймовірністю .

Порівнюючи отримані для значення, наприклад, (4.53 ) та (4.54 ) з оцінкою, що приводиться в [5]

,      (4.55 )

можна оцінити ступінь наближеності та можливість її застосування.

Додаток А Приклади оцінки стійкості КАП

Приклад 4.1. Нехай у якості використовується

геш-функція SHA-1, в якій , і нехай та . Використавши вираз (4.54   1.31), одержуємо:

У випадку (4.55   1.32) одержуємо:

.

Із приклада величину похибки, яку має оцінка (4.55   1.32), що широко застосовується для аналізу колізій.

 Оцінка ймовірності виникнення колізій . Спираючись на результати розв’язання задачі 4.1, розглянемо розв’язок задачі 4.2. Друга задача виникає за умови розгляду та вибору способів створення колізій [5, 106]. Наприклад, у нашій постановці це завдання має сенс, якщо розгляд відразу двох або більшого числа множин з - реалізацій дозволяє прискорити процес створення колізій або витягти корисну для крипто аналітика інформацію.

У нашому випадку подія може відбутися з імовірністю . Отже ймовірність того, що :

.     (4.56 )

Якщо містить у собі подій, то ймовірність того, що всі значення не дорівнюватимуть , може бути обчислена як:

.     (4.57  )

Ймовірність того, що хоча б одне значення дорівнюватиме , є:

.     (4.58 )

Нехай усі елементи – різні. Це справедливо, тому що , наприклад, . Тоді ймовірність того, що

та

.    (4.59 )

Далі, ймовірність того, що хоча б одна подія з і співпаде, є:

.    (4.60 )

Позначимо та скористаємося співвідношенням (4.45). У результаті одержимо

.   (4.61)

Таким чином, ймовірність того, що у двох множинах і хоча б по одному елементу співпаде:

.     (4.62)

Перетворивши (4.62 ), маємо:

.     (4.63 )

Логарифмуючи (4.63 ), отримаємо:

і далі

.

На закінчення одержимо

.     (4.64 )

Розглянемо часті випадки.

Нехай , тоді:

.    (4.65 )

При одержимо:

.    (4.66 )

Приклад 2. Нехай у якості геш-функції використовується геш-функція SHA-1, а .

Тоді

Отримані в ході розв’язання другої задачі результати дозволяють зробити такі висновки.

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

експериментів.

Проведемо оцінки значень і для використовуваного в Україні алгоритму симетричного блокового шифрування ГОСТ 28147-89. У четвертому режимі довжина криптографічної контрольної суми (імитовставки) дорівнює 64 бітам. Тому та . Якщо , використавши (1.31), одержимо:

.

Якщо , використавши (1.31), одержимо:

.

Якщо , використавши (1.30), маємо:

.

З урахуванням вимог до криптографічних алгоритмів блокового шифрування, викладених в [4, 11, 13 ], можна зробити висновок, що режим 4 виробітки імітовставки ГОСТ 28147-89 істотно підданий можливості створення колізій.

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

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

Отримані вході розв’язку задач результати дозволяють одержати як залежність від та , так і залежність від  та .


 

А также другие работы, которые могут Вас заинтересовать

20027. Коренной перелом в ходе второй мировой войны 15.6 KB
  Сталинградская битва 17 июля 19422 февраля 1943 По советскому плану уран окружение противника в районе сталинграда 19 ноября 1942 красная армия перешла в наступление и окр немецкую группировку под командованием Паулюса. 5 июля 1943 делится на два этапа оборонительные сражения и контрнаступление 12 июля 43 танковое сражение под Прохоровкой.
20028. Полный разгром фашистской германии и завершение 2 мировой войны 11.93 KB
  Январь 1944 снятие блокады Ленинграда 1944 корсуньшевченковская операция. Июньавгуст 1944 Белорусская операция Багратион была освобождена Белоруссия Латвия часть Литвы Август 1944 ЛьвовскоСандомирская операция освобождены: Львов Западная Украина Позже ЯсскоКишеневская операция освобождена: Молдавия и часть Румынии Апрель 1945 года Восточно –Прусская операция советские войска ступили в Кенинсберг Май 1945 заключительная Берлинская операция битва началась у Зееловских высот 2 мая – Берлинский гарнизон сдался В ночь с 89 мая ...
20029. СССР в 1945-1953. Восстановление экономики после ВОВ. Послевоенный сталинизм 14.66 KB
  В конце 1940 возникло ленинградское дело обвинение видных деятелей партии в намерении превратить ленинград в опору борьбы со сталиным были расстреляны Вознесенский Радионов Кузнецов. 1953 дело врачей было арестовано группа врачей кремлевской больницы по обвинению в том что она якобы повинны смерти жданова и пытались умертвить других государственных деятелей но со смертью сталина дело было прекращено.
20030. Послевоенный мир, его разделение на две системы. Переход в холодной войне 15.91 KB
  – ОВД Организация Варшавского ДоговораСССР. Гонка вооружений наращивание СССР и США количества вооружений с целью достижения качественного превосходства. В СССР эта политика проявлялась в создании железного занавеса системы международной самоизоляции. Причины холодной войны: Победа во II мировой войне привела к резкому усилению СССР и США.
20031. Попытки реформирования советской системы в 1950-60. Н.С Хрущев 17.59 KB
  С Хрущев. Борьба за личное лидерство длилась вплоть до весны 1958 но в итоге к власти пришел Хрущев.Начатая Хрущевым критика сталинизма привела к некоторой либерализации общественной жизни общества оттепель. Хрущева В 1954 г.
20032. СССР в период застоя(1964-1985) 14.54 KB
  к и в политической экономической и культурной жизни страны все было стабильно не было ничего нового. В культурной жизни зарождалось дессидентское движениенелегальные кружки интеллигенции выступающие за свержение коммунизма правительство полностью контролировало культурную жизнь странывыссылка из страны неугодных большевикам людейсолженицын плесецаявишневская 18 лет руководство брежнева перевели государство в состояние развала 1982Брежнев умирает с 18821884 правил Андропов а 18841885 Черненко общество жило от похорон до похорон...
20033. Перестройка-от частных преобразований к смене модели общественного развития(1985-1991) 14.85 KB
  В апреле 1985 –было объявлено о проведении масштабных реформ с целью изменения общества например в экономике курс на ускорениеэто повышение темпов экономического роста на базе научнотехнического прогресса Первыми перестроечными законами стала антиалкогольная компания и закон о госприемке но все эти меры не дали никаких результатов да и к тому же всю обстановку осложнила авария на чернобыльской АЭС 1986. Основная задача перестройки заключалась в придании экономике рыночных основ. Первым шагом к рыночной экономике стал закон о гос.
20034. Новая Россия в 90 годы 20 века 16.18 KB
  В середине 1980 административные структуры в союзных республиках начали борьбу за усиление собственной власти начались трения между коренными жителями и русскоязычным населением рухнул миф о дружбе народов СССРвыступление в казахстане столкновение в фергане наколились взаимоотношения грузии с абхазией с целью прекратить эти волнения горбачев задумал подписание нового союзного договора подписание которого было назначено на 20 августа 1991 19 авг. Начался антигосударственный переворот по радио было объявлено об отстранение президента...
20035. Гражданская война (1918-1920). Причины, этапы, итоги, последствия войны 16.63 KB
  Причинами гражданской войны в России можно считать противостояние двух политических лагерей – красных и белых красные –большевики бедные крестьяне и рабочие белые – зажиточное крестьянство офицеры казаки дворянство студенчество. Войны являлась прежде всего участие иностранных держав они поддерживали белыхиностранная интервенция. Многочисленные хорошо вооруженные и организованные за счет Антанты армии белых генералов взяли ее в кольцо. Декабрь 19201922 гокончательный разгром белого движения на юге России Причины победы красных в...