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

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

Лінійний криптоаналіз був винайдений японським криптологом Міцуру Мацуі (яп. 松井 充 Мацуі Міцуру) . Запропонований ним у 1993 році (на конференції Eurocrypt '93) алгоритм був від самого початку спрямований на розкриття DES і FEAL. Згодом лінійний криптоаналіз був поширений і на інші алгоритми. На сьогодні разом з диференціальним криптоаналізом є одним з найбільш розповсюджених методів розкриття блочних шифрів. Розроблені атаки на блочні та потокові шифри.

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

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

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

Побудування лінійних виразів

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

${\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|, тим краща застосованість лінійного криптоаналізу з меншою кількістю відкритих текстів, необхідних для атаки.

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

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

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

${\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}}}$.

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

Лема про набігання знаків (^[en])

Хоча апроксимацію з найбільшим відхиленням від 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}}$ дорівнює нулю, дорівнює

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

1. Matsui, 1993.
2. Фергюсон, Шнайер, 2004, с. 82.
3. Heys, Howard M.; Tavares, Stafford E. (1 березня 1996). . Journal of Cryptology (англ.). Т. 9, № 1. с. 1—19. doi:10.1007/bf02254789. ISSN 0933-2790. Архів оригіналу за 8 червня 2018. Процитовано 13 грудня 2017.
4. Heys, 2002.
5. Matsui, 1994.
6. Bogdanov, Andrey; Rijmen, Vincent (1 березня 2014). . Designs, Codes and Cryptography (англ.). Т. 70, № 3. с. 369—383. doi:10.1007/s10623-012-9697-z. ISSN 0925-1022. Архів оригіналу за 13 червня 2018. Процитовано 13 грудня 2017.
7. Knudsen, Lars R.; Mathiassen, John Erik (10 квітня 2000). . Fast Software Encryption (англ.). Springer, Berlin, Heidelberg. с. 262—272. doi:10.1007/3-540-44706-7_18. ISBN . Архів оригіналу за 14 квітня 2018. Процитовано 13 грудня 2017.
8. Matsui, 1993, с. 389.
9. Matsui, 1993, с. 397.
10. Matsui, 1993, с. 389, 394.
11. Kruppa H., Syed Umair Ahmed Shah (1998). (PDF). Архів оригіналу (PDF) за 14 грудня 2017.
12. Matsui, 1993, с. 387.
13. Junod, Pascal (16 серпня 2001). . Selected Areas in Cryptography (англ.). Springer, Berlin, Heidelberg. с. 199—211. doi:10.1007/3-540-45537-x_16. ISBN . Архів оригіналу за 14 квітня 2018. Процитовано 13 грудня 2017.
14. Heys H. M. (1997). . doi:10.1049/EL:19970601. ISSN 0013-5194 ISSN 0013-5194. Архів оригіналу за 23 жовтня 2018. {{}}: Перевірте значення |issn= ()
15. Wenling Wu. Linear cryptanalysis of NUSH block cipher (English) . Science in China Series F: Information Sciences. doi:10.1360/02YF9005. ISSN 1674-733X ISSN 1674-733X. {{}}: Перевірте значення |issn= ()
16. Knudsen L., Raddum H. (2001). (PDF). NES/DOC/UIB/WP3/009/1. Public report of the NESSIE project. Архів оригіналу (PDF) за 3 березня 2016.
17. (PDF). Архів оригіналу (PDF) за 11 серпня 2017.
18. Röck A., Nyberg K. (April 11-15, 2011). (PDF). The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Proceedings. Архів оригіналу (PDF) за 22 липня 2016.
19. Matsui, Mitsuru (9 травня 1994). . Advances in Cryptology — EUROCRYPT'94 (англ.). Springer, Berlin, Heidelberg. с. 366—375. doi:10.1007/bfb0053451. ISBN . Архів оригіналу за 16 червня 2018. Процитовано 13 грудня 2017.
20. Olsen, J.; Scholtz, R.; Welch, L. (November 1982). . IEEE Transactions on Information Theory. Т. 28, № 6. с. 858—864. doi:10.1109/tit.1982.1056589. ISSN 0018-9448. Архів оригіналу за 11 червня 2018. Процитовано 13 грудня 2017.
21. Forrié R. (PDF). Архів оригіналу (PDF) за 15 грудня 2017.
22. 1958-, Goldwasser, S. (Shafi), (1990). Advances in cryptology--CRYPTO '88 : proceedings. Berlin: Springer-Verlag. ISBN . OCLC 20933886.
23. Nyberg, Kaisa (8 квітня 1991). . Advances in Cryptology — EUROCRYPT ’91 (англ.). Springer, Berlin, Heidelberg. с. 378—386. doi:10.1007/3-540-46416-6_32. ISBN . Архів оригіналу за 15 грудня 2017. Процитовано 13 грудня 2017.
24. 1944-, Seberry, Jennifer,; 1962-, Zheng, Yuliang, (1993). Advances in cryptology--AUSCRYPT '92 : Workshop on the Theory and Application of Cryptographic Techniques, Gold Coast, Queensland, Australia, December 13-16, 1992 : proceedings. Berlin: Springer-Verlag. ISBN . OCLC 29186866.
25. Advances in Cryptology — AUSCRYPT '92 | SpringerLink (en-gb) . doi:10.1007/3-540-57220-1.
26. Adams, Carlisle M. (1 листопада 1997). . Designs, Codes and Cryptography (англ.). Т. 12, № 3. с. 283—316. doi:10.1023/a:1008229029587. ISSN 0925-1022. Архів оригіналу за 15 грудня 2017. Процитовано 13 грудня 2017.

Див. також

• Диференційний криптоаналіз

Література

• Matsui M. Linear Cryptanalysis Method for DES Cipher. — Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth. — .
• Matsui M. The First Experimental Cryptanalysis of the Data Encryption Standard. — 14th Annual International Cryptology Conference Santa Barbara, California, USA August 21–25, 1994 Proceedings / Y. G. Desmedt — Berlin: Springer Berlin Heidelberg, 1994. — .
• Heys H. M. [[[d:Q21804716|Q21804716: A Tutorial on Linear and Differential Cryptanalysis]] A Tutorial on Linear and Differential Cryptanalysis]. — Taylor & Francis, 2002.. — DOI:10.1080/0161-110291890885.
• Нільс Фергюсон, Брюс Шнайер. Практична криптографія = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. : Діалектика, 2004. — 3000 прим. — , .

Додаткові джерела

• Linear Cryptanalysis of DES [ 22 жовтня 2017 у Wayback Machine.]
• A Tutorial on Linear and Differential Cryptanalysis [ 26 листопада 2018 у Wayback Machine.]
• A tutorial on linear (and differential) cryptanalysis of block ciphers [ 10 грудня 2017 у Wayback Machine.]
• "Improving the Time Complexity of Matsui's Linear Cryptanalysis", improves the complexity thanks to the Fast Fourier Transform [ 4 березня 2016 у Wayback Machine.]