Ларс Кнудсен

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

Ларс Рамкільд Кнудсен
Lars Ramkilde Knudsen
Народився	21 лютого 1962(1962-02-21) (62 роки)
Країна	Данія
Діяльність	криптолог, інформатик, професор
Alma mater	Оргуський університет
Галузь	математика
Заклад	Данський технічний університет Берґенський університет
Науковий керівник	Ivan Damgårdd
Аспіранти, докторанти	Søren Steffen Thomsend Christian Rechbergerd Martin M. Lauridsend
Нагороди	член Міжнародної асоціації криптологічних дослідженьd (2013)
Особ. сторінка	www2.mat.dtu.dk/people/Lars.R.Knudsen/
Ларс Кнудсен у Вікісховищі

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

Біографія

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

У 1992 році отримав ступінь магістра, а вже в 1994 — ступінь доктора філософії. З 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).

Інтегральний криптоаналіз, побудований на принципі розгляду набору відкритих текстів, в яких одна частина залишається константою, а друга варіюється усіма можливими способами. Наприклад, атака може використовувати набір із 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.

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

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

Константа $c_{i}$ тримується із формули $c_{ij}=45^{45^{((9i+j){\mbox{ mod }}256)}{\mbox{ mod }}257}{\mbox{ mod }}257$, де j — номер байта константи $c_{i}$. Слабкість цього алгоритму полягала в тому, що майже для кожного ключа знайдеться не менше одного (іноді навіть 9) іншого ключа, який при шифруванні якогось іншого повідомлення дає нам той же самий шифрований текст, тобто $F(M_{1},K_{1})=F(M_{2},K_{2})$. Кнудсен встановив, що число різних відкритих текстів, які шифруються однаковими шифротекстами, приблизно $2^{22}$ — $2^{28}$ із можливих $2^{64}$ текстів. У підсумку за допомогою аналізу від $2^{44}$ до $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 для гешування одного блоку), так і забезпечував високий рівень безпеки, або більш високу ефективність при тих же рівнях безпеки. Для великого значення вбудованої пам'яті, швидкості близькі до тих, які можуть бути отримані. Крім того, геш-функція забезпечує високий ступінь паралелізму, яка дасть ще більш ефективну реалізацію.

Література

• 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.]