Ларс Кнудсен

Інтегральний криптоаналіз — це вид криптоаналізу, який частково можна застосовувати для атак на блочні шифри, засновані на підстановлювально-перестановлювальних мережах. Він був сформульований Ларсом Кнудсеном в процесі пошуку атаки на шифр SQUARE, тому в літературі його часто називають Square-атакою. Метод був розширений і застосований на подібні з Square шифри CRYPTON, Rijndael, і SHARK. Модифікації Square-атаки також були застосовані до шифрів Hierocrypt-L1, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER ++, KHAZAD і FOX (зараз званий IDEA NXT).

Інтегральний криптоаналіз, побудований на принципі розгляду набору відкритих текстів, в яких одна частина залишається константою, а друга варіюється усіма можливими способами. Наприклад, атака може використовувати набір із 256 відкритих текстів, в яких всі, крім 8 біт, варіюються. Очевидно, що XOR цього набору дорівнює нулю. XOR відповідного набору шифротексту дає нам інформацію про роботу алгоритму шифрування. Такий метод використання великого набору відкритих текстів замість пари, як в диференціальному криптоаналізі, дав назву «інтегральний».

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

Ця методика була вперше описана Ларсом Кнудсеном в заявці на конкурс AES по шифру DEAL. Назву методиці дали Елі Біхам, Алекс Бірюков і Аді Шамір на конференції CRYPTO'98.

Цей метод знайшов широке застосування і був використаний в атаках на шифри IDEA, Khufu і Khafre, E2, різновиди Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac (cipher), Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, і SHACAL-2[3].

SAFER K-64 є ітеративно блочним шифром. Алгоритм працює з 64-бітовим блоком і 64-бітових ключем. Кнудсен виявив слабке місце в розподілі ключів. Їх генерація в алгоритмі була зовсім важкою. Першим підключитися має сам ключ користувача. Наступні підключення генеруються процедурою ${\displaystyle K_{i+1}=\left({K_{i}<<<3i}\right)+c_{i+1}}$. Операція <<< — циклічний зсув вліво на 3 біти всередині кожного байта ключа.

Константа ${\displaystyle c_{i}}$ тримується із формули ${\displaystyle c_{ij}=45^{45^{((9i+j){\mbox{ mod }}256)}{\mbox{ mod }}257}{\mbox{ mod }}257}$, де j — номер байта константи ${\displaystyle c_{i}}$. Слабкість цього алгоритму полягала в тому, що майже для кожного ключа знайдеться не менше одного (іноді навіть 9) іншого ключа, який при шифруванні якогось іншого повідомлення дає нам той же самий шифрований текст, тобто ${\displaystyle F(M_{1},K_{1})=F(M_{2},K_{2})}$. Кнудсен встановив, що число різних відкритих текстів, які шифруються однаковими шифротекстами, приблизно ${\displaystyle 2^{22}}$ — ${\displaystyle 2^{28}}$ із можливих ${\displaystyle 2^{64}}$ текстів. У підсумку за допомогою аналізу від ${\displaystyle 2^{44}}$ до ${\displaystyle 2^{47}}$ відкритих текстів можна знайти 8 біт вихідного ключа, що складається з 64 біт. Потім цей алгоритм був вдосконалений самим Кнудсеном до SAFER SK-64[3].

Існує жарт, що SK розшифровується як Stop Knudsen, або в перекладі «Зупинити Кнудсена». Він з'явився внаслідок того, що новий алгоритм робив атаку Кнудсена безуспішною. Насправді, SK розшифровується як Strengthened Key Schedule, що означає «Посилене розширення ключа».

У 1997 році Ларс Кнудсен разом зі своїми колегами Йоаном Дайменом (англ. Joan Daemen) і Вінсентом Рейменом (англ. Vincent Rijmen) розробили атаку на блочний шифр SQUARE[4]. Сам алгоритм складався із 6 раундів, що включають 4 операції, лінійне перетворення рядків, нелінійну заміну байт, транспонування і складання з ключем. Вони вибрали атаку на основі підібраного відкритого тексту. Основна ідея полягала в виборі наборів тексту. Було виявлено, що з 256 обраних відкритих текстів знайдуться два, які однозначно визначать ключ шифрування із переважним успіхом, якби шифр складався із 4 раундів. Потім атака була продовжена на 5 і 6 раунди й успішно завершена, хоча й була неможлива через відсутність сучасних технологій. Тим не менш, вона вважалася актуальною, так як вона вважалася однією з найшвидших[3].

У своїй статті «Hash functions based on block ciphers and quaternary codes»[5] («Хеш-функції, засновані на блочних шифрах і четвертинних кодах») Ларс Кнудсен показав, що розробка ефективної хеш-функції з мінімальною вбудованою пам'яттю на основі m — бітного блочного шифру є важким завданням. Більш того, жодна з розглянутих ним геш — функцій не забезпечувала захисту краще, ніж 2^m, яку одержано методом «грубої сили». Змінюючи трохи модель (наприклад, шляхом збільшення розміру внутрішньої пам'яті, а також шляхом введення вихідних перетворень), можна отримати функцію стиснення і, таким чином, геш-функцію, для якої безпека може бути доведена на основі ймовірних припущень, сформульованих Кнудсеном. Пропонований ним метод був найкращим на той момент (а саме швидкість шифрування, рівна 1/4 або 4 для гешування одного блоку), так і забезпечував високий рівень безпеки, або більш високу ефективність при тих же рівнях безпеки. Для великого значення вбудованої пам'яті, швидкості близькі до тих, які можуть бути отримані. Крім того, геш-функція забезпечує високий ступінь паралелізму, яка дасть ще більш ефективну реалізацію[3].