1. Побудова лінійних рівнянь [ правити | правити код ]
2. Лемма про набіганні знаків [ правити | правити код ]
3. Отримання бітів ключа [ правити | правити код ]
4. Застосування до DES [ правити | правити код ]
5. Застосування інших методів шифрування [ правити | правити код ]

Наше деловое партнерство www.banwar.org

open wikipedia design.

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

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

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

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

Побудова лінійних рівнянь [ правити | правити код ]

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

P i 1 ⊕ P i 2 ⊕ ⋯ ⊕ P ia ⊕ C j 1 ⊕ C j 2 ⊕ ⋯ ⊕ C jb = K k 1 ⊕ K k 2 ⊕ ⋯ ⊕ K kc, (1) {\ 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)}

де P n, C n, K n {\ 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 найбільшу ймовірність зсуву має лінійна апроксимація для таблиці S5, в якій четвертий з шести вхідних бітів дорівнює XOR над усіма чотирма вихідними битами з ймовірністю 12/64 [8] [4] . Для полнораундового DES отримано співвідношення з ймовірністю виконання 1/2 + 2-24 [9] .

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

C j 1 ⊕ C j 2 ⊕ ⋯ ⊕ C j b = K k 1 ⊕ K k 2 ⊕ ... ⊕ K k c. {\ 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 не складно знайти для одного раунду, виникає проблема з обчисленням ймовірності зсуву при екстраполюванні методу на полнораундовий шифр. В принципі, це вимагало б від криптоаналитика переглянути всі можливі комбінації відкритих текстів і ключів, що неможливо виконати. Вирішення цієї проблеми - зробити ряд припущень і наблизити ймовірність, використовуючи лемму про набіганні знаків [En] . Нехай ми отримали лінійні апроксимації F i (1 ≤ i ≤ n) {\ displaystyle F_ {i} \, (1 \ leq i \ leq n)} для різних раундів, які дорівнюють 0 з ймовірністю p i {\ displaystyle p_ {i}} . Тоді ймовірність того, що загальна лінійна апроксимація F 1 ⊕ F 2 ⊕ ⋯ ⊕ F n {\ displaystyle F_ {1} \ oplus F_ {2} \ oplus \ dots \ oplus F_ {n}} дорівнює нулю, дорівнює [1] [4]

P = 1 2 + 2 n - 1 Π i = 1 n (p i - 1 2). {\ 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] .

Лінійний криптоаналіз спочатку розроблявся для атак на блокові шифри, але застосуємо і до потоковим. Самим розробником було детально вивчено його застосування до 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 і NOEKEON також розкриваються методом лінійного криптоаналізу [15] [16] [17] .
3. Розширення лінійного криптоаналізу, засноване на некоррелірующіх між собою лінійної апроксимації, можна застосувати для розтину 6-раундовий AES -192 і AES-256, а також 13-раундового CLEFIA -256 [6] .

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

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

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

1. ↑ 1 2 3 4 Matsui, 1993 .
2. ↑ Фергюсон, Шнайер, 2004 , С. 82.
3. ↑ Heys HM , Tavares SE Substitution-permutation networks resistant to differential and linear cryptanalysis // Journal of Cryptology / I. Damgård - Springer Science + Business Media , International Association for Cryptologic Research , 1996. - Vol. 9, Iss. 1. - P. 1-19. - ISSN 0933-2790 - doi: 10.1007 / BF02254789
4. ↑ 1 2 3 4 Heys, 2002 .
5. ↑ 1 2 Matsui, 1994 .
6. ↑ 1 2 3 Bogdanov A. , Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers // Des. Codes Cryptogr. - Springer US , 2014. - Vol. 70, Iss. 3. - P. 369-383. - ISSN 0925-1022 - doi: 10.1007 / S10623-012-9697-Z
7. ↑ 1 2 Knudsen L. , Mathiassen JE A Chosen-Plaintext Linear Attack on DES // Fast Software Encryption : 7th International Workshop, FSE 2000 New York, NY, USA, April 10-12, 2000. Proceedings / G. Goos , J. Hartmanis , J. v. Leeuwen et al. - Berlin : Springer Berlin Heidelberg , 2001. - P. 262-272. - ( Lecture Notes in Computer Science ; Vol. 1978) - ISBN 978-3-540-41728-6 - ISSN 0302-9743 - doi: 10.1007 / 3-540-44706-7_18
8. ↑ Matsui, 1993 , С. 389.
9. ↑ Matsui, 1993 , С. 397.
10. ↑ Matsui, 1993 , С. 389, 394.
11. ↑ Kruppa H. , Syed Umair Ahmed Shah Differential and Linear Cryptanalysis in Evaluating AES Candidate Algorithms - тисяча дев'ятсот дев'яносто вісім.
12. ↑ Matsui, 1993 , С. 387.
13. ↑ 1 2 3 Junod P. On the Complexity of Matsui's Attack // Selected Areas in Cryptography : 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16-17, 2001. Revised Papers / S. Vaudenay , AM Youssef - Springer Berlin Heidelberg , 2001. - P. 199-211. - 364 p. - ( Lecture Notes in Computer Science ; Vol. 2259) - ISBN 978-3-540-43066-7 - ISSN 0302-9743 - doi: 10.1007 / 3-540-45537-X_16
14. ↑ Heys HM Linearly weak keys of RC5 // IEE Electronics Letters - IEEE , 1997. - Vol. 33, Iss. 10. - P. 836-837. - ISSN 0013-5194 - doi: 10.1049 / EL: 19970601
15. ↑ Wu W. , Feng D. Linear cryptanalysis of NUSH block cipher // Science in China Series F: Information Sciences - Science China Press , 2002. - Vol. 45, Iss. 1. - P. 59-67. - ISSN 1674-733X - doi: 10.1360 / 02YF9005
16. ↑ Knudsen L. , Raddum H. On Noekeon : NES / DOC / UIB / WP3 / 009/1. Public report of the NESSIE project - 2001.
17. ↑ Security Evaluation of NESSIE First Phase (D13) (неопр.) (Недоступна посилання). Дата обігу 2 грудня 2015. Читальний зал 11 серпня 2017 року.
18. ↑ Röck A. , Nyberg K. Exploiting Linear Hull in Matsui's Algorithm // WCC 2011 : The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Proceedings - 2011 року.
19. ↑ Matsui M. On correlation between the order of S-boxes and the strength of DES // Advances in Cryptology - EUROCRYPT '94 : Workshop on the Theory and Application of Cryptographic Techniques Perugia , Italy, May 9-12, 1994 Proceedings / AD Santis - Berlin : Springer Berlin Heidelberg , 1995. - P. 366-375. - ISBN 978-3-540-60176-0 - doi: 10.1007 / BFB0053451
20. ↑ Olsen JD , Scholtz RA , Welch LR Bent-function sequences // IEEE Trans. Inf. Theory / F. Kschischang - IEEE , 1982. - Vol. 28, Iss. 6. - P. 858-864. - ISSN 0018-9448 - doi: 10.1109 / TIT.1982.1056589
21. ↑ Forrié R. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition // Advances in Cryptology - CRYPTO '88 : Proceedings / S. Goldwasser - New York City : Springer New York , 1990. - P. 450-468. - ( Lecture Notes in Computer Science ; Vol. 403) - ISBN 978-0-387-97196-4 - ISSN 0302-9743 - doi: 10.1007 / 0-387-34799-2
22. ↑ Nyberg K. Perfect nonlinear S-boxes // Advances in Cryptology - EUROCRYPT '91 : Workshop on the Theory and Application of Cryptographic Techniques Brighton , UK, April 8-11, 1991. Proceedings - Berlin : Springer Berlin Heidelberg , 1991. - P. 378-386. - ISBN 978-3-540-54620-7 - doi: 10.1007 / 3-540-46416-6_32
23. ↑ Seberry J. , Zhang X. Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion (Extended Abstract) // Advances in Cryptology - AUSCRYPT '92 : Workshop on the Theory and Application of Cryptographic Techniques Gold Coast , Queensland, Australia, December 13-16, 1992 Proceedings / J. Seberry , Y. Zheng - Berlin : Springer Berlin Heidelberg , 1993. - P. 143-155. - ( Lecture Notes in Computer Science ; Vol. 718) - ISBN 978-3-540-57220-6 - ISSN 0302-9743 - doi: 10.1007 / 3-540-57220-1
24. ↑ Adams CM Constructing Symmetric Ciphers Using the CAST Design Procedure // Des. Codes Cryptogr. - Springer US , 1997. - Vol. 12, Iss. 3. - P. 283-316. - ISSN 0925-1022 - doi: 10.1023 / A: 1008229029587

• Matsui M. Linear Cryptanalysis Method for DES Cipher // Advances in Cryptology - EUROCRYPT '93 : Workshop on the Theory and Application of Cryptographic Techniques Lofthus , Norway, May 23-27, 1993 Proceedings / T. Helleseth - 1 - Berlin : Springer Berlin Heidelberg , 1993. - P. 386-397. - 465 p. - ( Lecture Notes in Computer Science ; Vol. 765) - ISBN 978-3-540-57600-6 - ISSN 0302-9743 - doi: 10.1007 / 3-540-48285-7_33
• Matsui M. The First Experimental Cryptanalysis of the Data Encryption Standard // Advances in Cryptology - CRYPTO'94 : 14th Annual International Cryptology Conference Santa Barbara, California, USA August 21-25, 1994 Proceedings / YG Desmedt - Berlin : Springer Berlin Heidelberg , 1994. - P. 1-11. - ( Lecture Notes in Computer Science ; Vol. 839) - ISBN 978-3-540-58333-2 - ISSN 0302-9743 - doi: 10.1007 / 3-540-48658-5_1
• Heys HM A Tutorial on Linear and Differential Cryptanalysis // Cryptologia - Taylor & Francis , 2002. - Vol. 26, Iss. 3. - P. 189-221. - ISSN 0161-1194 - doi: 10.1080 / 0161-110291890885
• Нільс Фергюсон, Брюс Шнайер . Практична криптографія = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - М.: Діалектика, 2004. - 432 с. - 3000 екз. - ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .