Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Лінійний криптоаналіз



План:


Введення

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

Лінійний криптоаналіз був винайдений японським криптології Міцуру Мацуї (Mitsuru Matsui). Запропонований ним у 1993 р. (на Еврокріпте-93) алгоритм був від початку спрямований на розтин DES і FEAL. Згодом лінійний криптоаналіз був поширений і на інші алгоритми. На сьогоднішній день поряд з диференціальний криптоаналіз є одним з найбільш поширених методів розкриття блокових шифрів. Розроблено атаки на блокові і потокові шифри.

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


1. Принцип роботи

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

1.1. Побудова лінійних рівнянь

Сенс алгоритму полягає в отриманні співвідношень наступного вигляду:

P_ {i_1} \ oplus P_ {i_2} \ oplus ... \ Oplus P_ {i_a} \ oplus C_ {j_1} \ oplus C_ {j_2} \ oplus ... \ Oplus C_ {j_b} = K_ {k_1} \ oplus K_ {k_2} \ oplus ... \ Oplus K_ {k_c}, (1)

де P n, C n, K n - n-ті біти тексту, шіфротекста і ключа.

Дані співвідношення називаються лінійними апроксимаціями. Для довільно обраних біт відкритого тексту, шіфротекста і ключа ймовірність справедливості такого співвідношення P приблизно дорівнює 1/2. Такими співвідношеннями, ймовірність яких помітно відрізняється від 1/2 можна користуватися для розтину алгоритму.

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

У блокових шифри аналіз переважно концентрується на S-боксах, так як вони є нелінійною частиною шифру. Найбільш ефективне однораундовое співвідношення для алгоритму DES використовує властивість таблиці S5. Другий вхідний біт таблиці дорівнює результату операції XOR над усіма вихідними бітами з вірогідністю 3/16 (зміщення в 5/16 щодо 1/2). А для полнораундового DES відомо співвідношення, що виконується з імовірністю 1/2 + 2 -24.

Лінійний криптоаналіз має одне дуже корисна властивість - при певних умовах можна звести співвідношення (1) до рівняння виду:

C_ {j_1} \ oplus C_ {j_2} \ oplus ... \ Oplus C_ {j_b} = K_ {k_1} \ oplus K_ {k_2} \ oplus ... \ Oplus K_ {k_c}.

Тут відсутні біти відкритого тексту, тобто можна побудувати атаку на основі тільки шіфротекста. Така атака є найбільш практичною.


1.1.1. Piling-up lemma

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

P = \ frac {kg} {am} * jjot + 2 ^ {n-1} \ prod_ {i = 1} ^ {n} (p_i - \ frac {1} {2}).


1.2. Отримання бітів ключа

Як тільки отримана лінійна апроксимація, можна застосувати прямий алгоритм і, використовуючи пари відкритий текст-шіфротекст припустити значення бітів ключа. При цьому логічно використовувати максимально ефективне співвідношення, тобто таке, для якого відхилення ймовірності P від 1/2 максимально.

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


2. Застосування

Лінійний криптоаналіз спочатку розроблявся для атак на блокові шифри, але застосовний і до потоковим. Самим розробником було докладно вивчено його застосування до DES.

2.1. Застосування до DES

Експерименти Міцуру Мацуї по атакам з відкритого тексту (обчислення проводилися на HP9750 66МГц) дали наступні результати [1] :

  • 8-ми раундовий DES зламується за допомогою 21 лютого відомих відкритих текстів. Це зайняло у Мацуї 40 секунд.
  • 12-ти раундовий DES зламується за допомогою 2 33 відомих відкритих текстів. На це знадобилося 50 годин.
  • На 16-ти раундовий DES потрібно 2 47 відомих відкритих текстів. Дана атака зазвичай не практична. Однак, метод працює швидше, ніж вичерпний пошук 56-ти бітного ключа.

Сучасна обчислювальна техніка здатна виконувати злом швидше.

Вельми часто лінійний криптоаналіз використовується разом з методом "грубої сили" - після того, як певні біти ключа знайдені за допомогою лінійного криптоаналізу, проводиться вичерпний пошук по можливим значенням решти біт. Для злому DES подібним чином потрібно 2 43 відкритих текстів.

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

Що стосується атак по шіфротекста, Мацуї були отримані наступні результати:

  • Якщо відкритий текст складається з англійських пропозицій у кодуванні ASCII, то 8-ми раундовий DES можна зламати, використовуючи тільки 29 лютого шіфротекста.
  • Якщо відкритий текст складається з будь-яких символів ASCII, то 8-ми раундовий DES зламується за допомогою 2 37 шіфротекста.

2.2. Застосування до інших методів шифрування

Крім DES і FEAL, відомі й інші алгоритми, піддані лінійному криптоаналіз, наприклад:

  1. Лінійний криптоаналіз діє проти алгоритму RC5 у випадку, якщо шуканий ключ шифрування потрапляє в клас слабких ключів.
  2. Алгоритми NUSH і Noekeon також розкриваються методом лінійного криптоаналізу.
  3. Деякі варіанти алгоритму DES ( DESX, DES з незалежними підключити і Biham-DES) розкриваються лінійного криптоаналізу.

На сьогоднішній день, від нових шифрів потрібен доказ стійкості до лінійного криптоаналізу.


3. Захист від лінійного криптоаналізу

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

Даний підхід забезпечує хороше обгрунтування стійкості шифру, але щоб строго довести захищеність від лінійного криптоаналізу, розробникам шифрів необхідно враховувати більш складне явище - ефект лінійних оболонок (linear hull effect).

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


Примітки

  1. Mitsuru Matsui "Linear Cryptanalysis Method for DES Cipher" - www.springerlink.com/content/92509p5l4ravyn62/

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Криптоаналіз
Диференціальний криптоаналіз
Лінійний функціонал
Лінійний двигун
Лінійний прискорювач
Лінійний ізолятор
Лінійний код
Лінійний список
Лінійний пошук
© Усі права захищені
написати до нас