Кнудсен Ларс

Ларс Рамкільд Кнудсен (англ. Lars Ramkilde Knudsen) (21 лютого 1962(19620221)) — данський математик і дослідник в області криптографії, професор кафедри математики в Данському технічному університеті. Його дослідження включають в себе розробку й аналіз блочних шифрів, геш-функцій і кодів автентичності повідомлень (MACs).

Ларс Рамкільд Кнудсен
Lars Ramkilde Knudsen
Народився	21 лютого 1962(1962-02-21) (62 роки)
Країна	Королівство Данія
Діяльність	криптолог, інформатик, професор
Alma mater	Оргуський університет
Галузь	математика
Заклад	Данський технічний університет^[1] Берґенський університет
Науковий керівник	^d
Аспіранти, докторанти	^d^[2] ^d^[2] ^d^[2]
Нагороди	^d (2013)
Особ. сторінка	www2.mat.dtu.dk/people/Lars.R.Knudsen/
Ларс Кнудсен у Вікісховищі

Кнудсен — один із засновників криптоаналізу неможливих диференціалів і . Ларс є одним з розробників .

Біографія

Ларс Кнудсен народився 21 лютого 1962 року в Данії. Після короткотривалої роботи в банківській сфері, в 1984 році Ларс вступив в Орхуський університет (англ. Aarhus University). Вивчав математику й інформатику, за порадою свого наукового керівника Айвана Б'єрре Дамгарда (англ. Ivan Bjerre Damgard). За словами Ларса, саме завдяки своєму науковому керівнику, він зробив вибір на користь вивчення диференціального криптоаналізу.

У 1992 році отримав ступінь магістра, а вже в 1994 — ступінь доктора філософії. З 1997 по 2001 рік працював в Бергенському університеті, Норвегія. Був двічі обраний директором Міжнародної асоціації криптографічних досліджень () з січня 2001 року по грудень 2003 року та з січня 2004 року по грудень 2006 року. З 2003 по 2010 рік був помічником редактора журналу з криптології, що є офіційним журналом IACR. Виступав на конференціях і семінарах IACR. Його доповіді прослуховували на 7 наукових конференціях. В даний момент Кнудсен — професор, завідувач кафедри математики в Данському технічному університеті. Очолює групу криптоаналітиків університету і є одним із розробників шифрів, криптографічних протоколів IEEE з криміналістики й безпеки. Один з керівників дослідного центру (Foundations in Cryptology and Security).

Ларс Кнудсен брав активну участь в конкурсі на новий криптостандарт AES. На конкурсі він був єдиним криптоаналітиком, який представляв відразу два проекти: (Норвегія, Канада) і Serpent (Велика Британія, Ізраїль, Норвегія). Казус з тією обставиною, що Кнудсен всюди фігурує як представник Норвегії, пояснюється надзвичайною мобільністю данського вченого, оскільки за кілька останніх років перед конкурсом він встиг попрацювати у Франції, Швейцарії і Бельгії. На момент проведення конкурсу AES Ларс викладав криптологію в університет Бергена, Норвегія.

Відомо також, що його число Ердеша дорівнює 3.

Наукові дослідження

У всьому світі Ларс Кнудсен відомий завдяки знаменитим атакам на шифри SAFER і SQUARE, його роботам з криптоаналізу неможливих диференціалів та інтегрального криптоаналізу. Кнудсен вперше запропонував використовувати усічені диференціали для атак на 6-раундовий DES. Надалі цей метод був використаний і для атак на і SAFER із усіченим числом раундів. Також Ларс розробив шифри і Serpent (останній разом з англійцем Россом Андерсоном і ізраїльтянином Елі Біхамом). Ще однією розробкою Кнудсена є Grøstl, геш-функція, один з п'яти фіналістів конкурсу NIST SHA-3.

Інтегральний криптоаналіз

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

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

Криптоаналіз неможливих диференціалів

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

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

Цей метод знайшов широке застосування і був використаний в атаках на шифри IDEA, , , різновиди Serpent, MARS, Twofish, Rijndael, CRYPTON, ^[en], Hierocrypt-3, TEA, XTEA, , , Camellia, і .

Атака на шифр SAFER

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.

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

Атака на шифр SQUARE

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

Геш-функція, заснована на блочному шифрі

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

Примітки

1. Montenegro A. ORCID Public Data File 2023 — 2023. — doi:10.23640/07243.24204912.V1
   d:Track:Q123508386
2. Математичний генеалогічний проєкт — 1997.
   d:Track:Q829984
3. Lars Knudsen. Block Cipher — Analysis, Design and Applications, Ph.D. Thesis, 1994. (PDF). — . Архівовано з джерела 10 липня 2007. Процитовано 2009-11-26.
4. Алгоритмы шифрования. Специальный справочник. Архів оригіналу за 12 квітня 2018. Процитовано 14 березня 2022.
5. Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square (PDF/PostScript). — .^{[недоступне посилання]}
6. Lars Knudsen and Bart Preneel. Hash functions based on block ciphers and quaternary codes (PDF/PostScript). — .^{[недоступне посилання]}

Література

• Matt Henricksen and Lars R. Knudsen. Cryptanalysis of the CRUSH Hash Function.
• Lars R. Knudsen and Tadayoshi Kohno (1991). Analysis of RMAC.
• Lars Knudsen and Bart Preneel. Hash functions based on block ciphers and quaternary codes.
• Lars Knudsen and Chris J Mitchell. Analysis of 3gpp-MAC and two-key 3gpp-MAC.
• Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square.

Посилання

Алгоритмы шифрования. Специальный справочник [Архівовано 12 квітня 2018 у Wayback Machine.]