Відкрити головне меню

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

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

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

Принцип роботиРедагувати

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

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

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

 

де  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 бітів, від криптоаналітика потрібно побудувати 2m+n апроксимацій. Щоб знайти ймовірність для однієї апроксимації, на вхід S-блоку даються усі 2m можливих вхідних значень і йде підрахунок, скільки разів дана апроксимація вірна для вхідних і вихідних бітів. Отримана кількість збігів ділиться на 2m. В алгоритмі DES найбільшу ймовірність зміщення має лінійна апроксимація для таблиці S5, у якій четвертий з шести вхідних бітів дорівнює XOR над усіма чотирма вихідними бітами з ймовірністю 12/64[8][4]. Для повнораундового DES отримано співвідношення з ймовірністю виконання 1/2 + 2−24[9].

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

 .

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

Лема про набігання знаків (Piling-up lemma[en])Редагувати

Хоча апроксимацію з найбільшим відхиленням від 1/2 не важко знайти для одного раунду, виникає проблема з обчисленням вірогідності зміщення при екстраполюванні методу на повнораундовий шифр. В принципі, це вимагало б від криптоаналітика переглянути всі можливі комбінації відкритих текстів й ключів, що є неможливим. Рішення цієї проблеми — зробити ряд припущень та наблизити вірогідність, використовуючи лему про набігання знаків. Нехай ми отримали лінійні апроксимації   для різноманітних раундів, які дорівнюють 0 з ймовірністю  . Тоді ймовірність того, що загальна лінійна апроксимація   дорівнює нулю, дорівнює[1][4]

 

Отримання бітів ключаРедагувати

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

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

ЗастосуванняРедагувати

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

Застосування до DESРедагувати

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

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

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

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

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

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

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

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

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

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

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

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

ПриміткиРедагувати

  1. а б в г Matsui, 1993
  2. Фергюсон, Шнайер, 2004, с. 82
  3. Heys, Howard M.; Tavares, Stafford E. (1996-03-01). Substitution-permutation networks resistant to differential and linear cryptanalysis. Journal of Cryptology (en) 9 (1). с. 1–19. ISSN 0933-2790. doi:10.1007/bf02254789. Процитовано 2017-12-13. 
  4. а б в г Heys, 2002
  5. а б Matsui, 1994
  6. а б в Bogdanov, Andrey; Rijmen, Vincent (2014-03-01). Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Designs, Codes and Cryptography (en) 70 (3). с. 369–383. ISSN 0925-1022. doi:10.1007/s10623-012-9697-z. Процитовано 2017-12-13. 
  7. а б Knudsen, Lars R.; Mathiassen, John Erik (2000-04-10). A Chosen-Plaintext Linear Attack on DES. Fast Software Encryption (en) (Springer, Berlin, Heidelberg). с. 262–272. ISBN 3540447067. doi:10.1007/3-540-44706-7_18. Процитовано 2017-12-13. 
  8. Matsui, 1993, с. 389
  9. Matsui, 1993, с. 397
  10. Matsui, 1993, с. 389, 394
  11. Kruppa H., Syed Umair Ahmed Shah (1998). Differential and Linear Cryptanalysis in Evaluating AES Candidate Algorithms. 
  12. Matsui, 1993, с. 387
  13. а б в Junod, Pascal (2001-08-16). On the Complexity of Matsui’s Attack. Selected Areas in Cryptography (en) (Springer, Berlin, Heidelberg). с. 199–211. ISBN 354045537X. doi:10.1007/3-540-45537-x_16. Процитовано 2017-12-13. 
  14. Heys H. M. (1997). Linearly weak keys of RC5. ISSN 0013-5194 ISSN 0013-5194. doi:10.1049/EL:19970601. 
  15. Wenling Wu. Linear cryptanalysis of NUSH block cipher (English). Science in China Series F: Information Sciences. ISSN 1674-733X ISSN 1674-733X. doi:10.1360/02YF9005. 
  16. Knudsen L., Raddum H. (2001). On Noekeon. NES/DOC/UIB/WP3/009/1. Public report of the NESSIE project. 
  17. Security Evaluation of NESSIE First Phase (D13). Архів оригіналу за 11 серпень 2017. 
  18. Röck A., Nyberg K. (April 11-15, 2011). Exploiting Linear Hull in Matsui's Algorithm. The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Proceedings. 
  19. Matsui, Mitsuru (1994-05-09). On correlation between the order of S-boxes and the strength of DES. Advances in Cryptology — EUROCRYPT'94 (en) (Springer, Berlin, Heidelberg). с. 366–375. ISBN 9783540601760. doi:10.1007/bfb0053451. Процитовано 2017-12-13. 
  20. Olsen, J.; Scholtz, R.; Welch, L. (November 1982). Bent-function sequences. IEEE Transactions on Information Theory 28 (6). с. 858–864. ISSN 0018-9448. doi:10.1109/tit.1982.1056589. Процитовано 2017-12-13. 
  21. Forrié R. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition. 
  22. 1958-, Goldwasser, S. (Shafi), (1990). Advances in cryptology--CRYPTO '88 : proceedings. Berlin: Springer-Verlag. ISBN 9780387971964. OCLC 20933886. 
  23. Nyberg, Kaisa (1991-04-08). Perfect nonlinear S-boxes. Advances in Cryptology — EUROCRYPT ’91 (en) (Springer, Berlin, Heidelberg). с. 378–386. ISBN 3540464166. doi:10.1007/3-540-46416-6_32. Процитовано 2017-12-13. 
  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 9783540572206. OCLC 29186866. 
  25. Advances in Cryptology — AUSCRYPT '92 | SpringerLink (en-gb). doi:10.1007/3-540-57220-1. 
  26. Adams, Carlisle M. (1997-11-01). Constructing Symmetric Ciphers Using the CAST Design Procedure. Designs, Codes and Cryptography (en) 12 (3). с. 283–316. ISSN 0925-1022. doi:10.1023/a:1008229029587. Процитовано 2017-12-13. 

Див. такожРедагувати

ЛітератураРедагувати

Додаткові джерелаРедагувати