Очікує на перевірку

Ларс Кнудсен

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Ларс Рамкільд Кнудсен
Lars Ramkilde Knudsen
Народився21 лютого 1962(1962-02-21) (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(19620221)) — данський математик і дослідник в області криптографії, професор кафедри математики в Данському технічному університеті. Його дослідження включають в себе розробку й аналіз блочних шифрів, геш-функцій і кодів автентичності повідомлень (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 — бітного блочного шифру є важким завданням. Більш того, жодна з розглянутих ним геш — функцій не забезпечувала захисту краще, ніж 2m, яку одержано методом «грубої сили». Змінюючи трохи модель (наприклад, шляхом збільшення розміру внутрішньої пам'яті, а також шляхом введення вихідних перетворень), можна отримати функцію стиснення і, таким чином, геш-функцію, для якої безпека може бути доведена на основі ймовірних припущень, сформульованих Кнудсеном. Пропонований ним метод був найкращим на той момент (а саме швидкість шифрування, рівна 1/4 або 4 для гешування одного блоку), так і забезпечував високий рівень безпеки, або більш високу ефективність при тих же рівнях безпеки. Для великого значення вбудованої пам'яті, швидкості близькі до тих, які можуть бути отримані. Крім того, геш-функція забезпечує високий ступінь паралелізму, яка дасть ще більш ефективну реалізацію[4].

Примітки

[ред. | ред. код]
  1. Montenegro A. ORCID Public Data File 2023 — 2023. — doi:10.23640/07243.24204912.V1
  2. а б в Математичний генеалогічний проєкт — 1997.
  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.]