Ларс Кнудсен
Ларс Рамкільд Кнудсен | |
---|---|
Lars Ramkilde Knudsen | |
Народився | 21 лютого 1962 (62 роки) |
Країна | Королівство Данія |
Діяльність | криптолог, інформатик, професор |
Alma mater | Оргуський університет |
Галузь | математика |
Заклад | Данський технічний університет[1] Берґенський університет |
Науковий керівник | Ivan Damgårdd |
Аспіранти, докторанти | Søren Steffen Thomsend[2] Christian Rechbergerd[2] Martin M. Lauridsend[2] |
Нагороди | |
Особ. сторінка | www2.mat.dtu.dk/people/Lars.R.Knudsen/ |
Ларс Кнудсен у Вікісховищі |
Ларс Рамкільд Кнудсен (англ. Lars Ramkilde Knudsen) (21 лютого 1962) — датський математик і дослідник в області криптографії, професор кафедри математики в Датському технічному університеті (англ. Technical University of Denmark). Його дослідження включають в себе розробку й аналіз блочних шифрів, геш-функцій і кодів автентичності повідомлень (MACs).
Кнудсен — один із засновників криптоаналізу неможливих диференціалів і інтегрального криптоаналізу. Ларс є одним з розробників Grøstl.
Біографія
Ларс Кнудсен народився 21 лютого 1962 року в Данії. Його кар'єра почалася з кількох ранніх робіт в банківській сфері. Однак, в 1984 році Ларс вступив в Данський Університет Орхуса (англ. Aarhus University). Вивчав математику й інформатику, за порадою свого наукового керівника Айвана Б'ерре Дамгарда (англ. Ivan Bjerre Damgard). За словами Ларса, саме завдяки своєму науковому керівнику, він зробив вибір на користь вивчення диференціального криптоаналізу.
У 1992 році отримав ступінь магістра, а вже в 1994 — ступінь доктора філософії[3]. З 1997 по 2001 рік працював в Бергенському університеті, Норвегія. Був двічі обраний директором Міжнародної асоціації криптографічних досліджень (IACR) з січня 2001 року по грудень 2003 року і з січня 2004 року по грудень 2006 року. З 2003 по 2010 рік був помічником редактора журналу про криптології, що є офіційним журналом IACR. Виступав на конференціях і семінарах IACR. Його доповіді прослуховували на 7 наукових конференціях. В даний момент Кнудсен — професор, завідувач кафедрою математики в Технічному університеті Данії. Очолює групу криптоаналітиків університету і є одним з розробників шифрів, криптографічних протоколів IEEE з криміналістики й безпеки. Один з керівників дослідного центру FICS (Foundations in Cryptology and Security).
Ларс Кнудсен брав активну участь в конкурсі на новий криптостандарта AES. На ньому він був єдиним кріптоаналітиком, який представляв відразу два проекти DEAL (Норвегія, Канада) і Serpent (Велика Британія, Ізраїль, Норвегія). Казус з тією обставиною, що Кнудсен всюди фігурує як представник Норвегії, пояснюється надзвичайної мобільністю датського вченого, за кілька останніх років перед конкурсом вже встиг попрацювати у Франції, Швейцарії і Бельгії. На момент проведення конкурсу AES Ларс викладав криптологію в університет Бергена, Норвегія.
Відомо також, що його число Ердеша дорівнює 3.
Наукові дослідження
У всьому світі Ларс Кнудсен відомий завдяки знаменитим атакам на шифри SAFER і SQUARE, його роботам по криптоанализу неможливих диференціалів і інтегрального криптоаналізу. Кнудсен вперше запропонував використовувати усічені диференціали для атак на 6-раундовий DES. Надалі цей метод був використаний і для атак на Skipjack і SAFER з усіченим числом раундів. Також Ларс розробив шифри DEAL і Serpent (останній разом з англійцем Россом Андерсоном і ізраїльтянином Елі Біхамом). Ще однією розробкою Кнудсена є Grøstl, хеш-функція, один з п'яти фіналістів конкурсу NIST SHA-3.
Інтегральний криптоаналіз
Інтегральний криптоаналіз — це вид криптоаналіза, який частково можна застосовувати для атак на блочні шифри, засновані на підстановлювально-перестановлювальних мережах. Він був сформульований Ларсом Кнудсеном в процесі пошуку атаки на шифр SQUARE, тому в літературі його часто називають Square-атакою. Метод був розширений і застосований на подібні з Square шифри CRYPTON, Rijndael, і SHARK. Модифікації Square-атаки також були застосовані до шифрів Hierocrypt-L1, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER ++, KHAZAD і FOX (зараз званий IDEA NXT[en]).
Інтегральний криптоаналіз побудований на принципі розгляду набору відкритих текстів, в яких одна частина залишається константою, а друга варіюється усіма можливими способами. Наприклад, атака може використовувати набір із 256 відкритих текстів, в яких всі, крім 8 біт, варіюються. Очевидно, що XOR цього набору дорівнює нулю. XOR відповідного набору шифротексту дає нам інформацію про роботу алгоритму шифрування. Такий метод використання великого набору відкритих текстів замість пари, як в диференціальному криптоаналізі, дав назву «інтегральний».
Криптоаналіз неможливих диференціалів
Криптоаналіз неможливих диференціалів є різновидом диференціального криптоаналізу, застосованого до блочним шифрів. У звичайному диференціальному криптоаналізі розглядається різниця, що має деяку кінцеву ймовірність, в криптоаналізі неможливих диференціалів — різниця, що має ймовірність 0, тобто «неможлива».
Ця методика була вперше описана Ларсом Кнудсеном в заявці на конкурс AES по шифру DEAL. Назву методиці дали Елі Біхам, Алекс Бірюков і Аді Шамір на конференції CRYPTO'98.
Цей метод знайшов широке застосування і був використаний в атаках на шифри IDEA, Khufu і Khafre, E2, різновиди Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac (cipher)[en], Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, і SHACAL-2[4].
Атака на шифр SAFER
SAFER K-64 є ітеративно блочним шифром. Алгоритм працює з 64-бітовим блоком і 64-бітових ключем. Кнудсен виявив слабке місце в розподілі ключів. Їх генерація в алгоритмі була зовсім важкою. Першим підключитися має сам ключ користувача. Наступні підключення генеруються процедурою . Операція <<< — циклічний зсув вліво на 3 біти всередині кожного байта ключа.
Константа получається із формули , де j — номер байта константи . Слабкість цього алгоритму полягала в тому, що майже для кожного ключа знайдеться не менше одного (іноді навіть 9) іншого ключа, який при шифруванні якогось іншого повідомлення дає нам той же самий шифрований текст, тобто . Кнудсен встановив, що число різних відкритих текстів, які шифруються однаковими шифротекстами, приблизно — із можливих текстів. У підсумку за допомогою аналізу від до відкритих текстів можна знайти 8 біт вихідного ключа, що складається з 64 біт. Потім цей алгоритм був вдосконалений самим Кнудсеном до SAFER SK-64[4].
Існує жарт, що SK розшифровується як Stop Knudsen, або в перекладі «Зупинити Кнудсена». Він з'явився внаслідок того, що новий алгоритм робив атаку Кнудсена безуспішною. Насправді, SK розшифровується як Strengthened Key Schedule, що означає «Посилене розширення ключа».
Атака на шифр SQUARE
У 1997 році Ларс Кнудсен разом зі своїми колегами Йоаном Дайменом (англ. Joan Daemen) і Вінсентом Рейменом (англ. Vincent Rijmen) розробили атаку на блоковий шифр SQUARE[5]. Сам алгоритм складався з 6 раундів, що включають 4 операції, лінійне перетворення рядків, нелінійну заміну байт, транспонування і складання з ключем. Вони вибрали атаку на основі підібраного відкритого тексту. Основна ідея полягала в виборі наборів тексту. Було виявлено, що з 256 обраних відкритих текстів знайдуться два, які однозначно визначать ключ шифрування з переважним успіхом, якби шифр складався з 4 раундів. Потім атака була продовжена на 5 і 6 раунди й успішно завершена, хоча й була неможлива через відсутність сучасних технологій. Тим не менш, вона вважалася актуальною, так як вона вважалася однією з найшвидших[4].
Хеш-функція, заснована на блочному шифрі
У своїй статті «Hash functions based on block ciphers and quaternary codes»[6] («Хеш-функції, засновані на блочних шифрах і четвертинних кодах») Ларс Кнудсен показав, що розробка ефективної хеш-функції з мінімальною вбудованою пам'яттю на основі m — бітного блочного шифру є важким завданням. Більш того, жодна з розглянутих ним хеш — функцій не забезпечувала захисту краще, ніж 2^m, яку одержано методом «грубої сили». Змінюючи трохи модель (наприклад, шляхом збільшення розміру внутрішньої пам'яті, а також шляхом введення вихідних перетворень), можна отримати функцію стиснення і, таким чином, хеш-функцію, для якої безпека може бути доведена на основі ймовірних припущень, сформульованих Кнудсеном. Пропонований ним метод був як найкращим на поточний момент (а саме швидкість шифрування, рівній або 4 для хешування одного блоку), так і забезпечував високий рівень безпеки, або більш високу ефективність при тих же рівнях безпеки. Для великого значення вбудованої пам'яті, швидкості близькі до тих, які можуть бути отримані. Крім того, хеш-функція забезпечує високу ступінь паралелізму, яка дасть ще більш ефективну реалізацію[4].
Примітки
- ↑ Montenegro A. ORCID Public Data File 2023 — 2023. — doi:10.23640/07243.24204912.V1
- ↑ а б в Математичний генеалогічний проєкт — 1997.
- ↑ Lars Knudsen. Block Cipher — Analysis, Design and Applications, Ph.D. Thesis, 1994. (PDF). — . Процитовано 2009-11-26.
- ↑ а б в г Алгоритмы шифрования. Специальный справочник
- ↑ Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square (PDF/PostScript). — .
- ↑ 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. 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.