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

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

${\displaystyle P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}},\qquad (1)}$

де ${\displaystyle P_{n},C_{n},K_{n}}$ — n-ні біти тексту, шифротексту й ключа відповідно.

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

Ідея лінійного криптоаналізу — визначити вирази виду (1), які мають високу або низьку ймовірність виникнення. Якщо алгоритм шифрування має високу частоту виконання рівняння (1), або навпроти, рівняння виконується с низькою частотою, тоді це свідчить про бідну здатність рандомізації шифру. Якщо вірогідність виконання рівняння (1) дорівнює p, тоді ймовірність зміщення p − 1/2. Чим більше величина вірогідності зміщення |p − 1/2|, тим краща застосованість лінійного криптоаналізу з меншою кількістю відкритих текстів, необхідних для атаки[1][4].

Є декілька видів атак лінійного криптоаналізу[5][6][7]. Розглядається алгоритм Мацуі: початково для кожного раунду шифру знаходиться лінійна апроксимація з найбільшою ймовірністю зміщення. Отриманні вирази об'єднуються в спільну для всіх раундів лінійну апроксимацію, вірогідність зміщення якої дозволяє знайти лема про набігання знаків.

Далі розглядається алгоритм знаходження найкращої лінійної апроксимації для одного раунду. В блочних шифрах аналіз переважно концентрується на S-блоки, оскільки вони є нелінійною частиною шифру. Через те, що S-блок приймає на вході m бітів і повертає n бітів, від криптоаналітика потрібно побудувати 2^m+n апроксимацій. Щоб знайти ймовірність для однієї апроксимації, на вхід S-блоку даються усі 2^m можливих вхідних значень і йде підрахунок, скільки разів дана апроксимація вірна для вхідних і вихідних бітів. Отримана кількість збігів ділиться на 2^m. В алгоритмі DES найбільшу ймовірність зміщення має лінійна апроксимація для таблиці S₅, у якій четвертий з шести вхідних бітів дорівнює XOR над усіма чотирма вихідними бітами з ймовірністю 12/64[8][4]. Для повнораундового DES отримано співвідношення з ймовірністю виконання 1/2 + 2⁻²⁴[9].

Лінійний криптоаналіз має одну дуже корисну властивість: при певних умовах (наприклад, коли про відкритий текст відомо, що він складається з символів в кодуванні ASCII) можна звести співвідношення (1) до рівняння виду[10][11]

${\displaystyle C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \ldots \oplus K_{k_{c}}}$.

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

Хоча апроксимацію з найбільшим відхиленням від 1/2 не важко знайти для одного раунду, виникає проблема з обчисленням вірогідності зміщення при екстраполюванні методу на повнораундовий шифр. В принципі, це вимагало б від криптоаналітика переглянути всі можливі комбінації відкритих текстів й ключів, що є неможливим. Рішення цієї проблеми — зробити ряд припущень та наблизити вірогідність, використовуючи лему про набігання знаків. Нехай ми отримали лінійні апроксимації ${\displaystyle F_{i}\,(1\leq i\leq n)}$ для різноманітних раундів, які дорівнюють 0 з ймовірністю ${\displaystyle p_{i}}$. Тоді ймовірність того, що загальна лінійна апроксимація ${\displaystyle F_{1}\oplus F_{2}\oplus \dots \oplus F_{n}}$ дорівнює нулю, дорівнює[1][4]

${\displaystyle P={\frac {1}{2}}+2^{n-1}\prod _{i=1}^{n}(p_{i}-{\frac {1}{2}}).}$

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

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

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

• На 8-раундовий DES знадобилось 2²¹ відомих відкритих текстів. Атака зайняла 40 секунд.
• На 12-раундовий DES знадобилось 2³³ відомих відкритих текстів та 50 годин.
• На 16-раундовий DES було потрібно 2⁴³ відомих відкритих текстів та 50 днів.

2001 році Паскаль Жюно (фр. Pascal Junod) провів ряд експериментів, щоб визначити складність атаки. В результаті виявилось, що в дійсності атака на 16-раундовий DES може успішно застосовуватися при наявності 2³⁹—2⁴¹ відомих текстів[13].

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

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

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

1. Лінійний криптоаналіз діє проти алгоритму RC5 у випадку, якщо шуканий ключ шифрування потрапляє до класу слабких ключів[14].
2. Алгоритми NUSH та NOEKEON також розкриваються методом лінійного криптоаналізу[15][16][17].
3. Розширення лінійного криптоаналізу, засноване на некорельованих між собою лінійних апроксимаціях, можливо для розкриття 6-раундових AES-192 і AES-256, а також 13-раундового CLEFIA-256[6].