Ларс Рамкильд Кнудсен (англ. Lars Ramkilde Knudsen; 21 февраля 1962(19620221), Дания) — выдающийся датский математик и криптоаналитик, профессор кафедры математики в Датском техническом университете (англ. Technical University of Denmark). В область интересов входит разработка и анализ блочных шифров, хеш-функции и коды аутентичности сообщений.

Биография

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

В 1992 году получил степень магистра, а уже в 1994 — степень доктора наук^[1]. С 1997 по 2001 год работал в университете города Берген (англ. University of Bergen), Норвегия . В данный момент Кнудсен — профессор, заведующий кафедрой математики в Датском техническом университете (англ. Technical University of Denmark). Возглавляет группу криптоаналитиков университета. Один из руководителей исследовательского центра FICS (Foundations in Cryptology and Security).

Во всём мире известен благодаря знаменитым атакам на шифры SAFER и Square. Является одним из основателей криптоанализа невозможных дифференциалов и интегрального криптоанализа. Кнудсен также впервые предложил использовать усечённые дифференциалы для атак на 6-раундовый DES. В дальнейшем этот метод был использован и для атак на Skipjack и SAFER с усечённым числом раундов.

Известно также, что его число Эрдёша равно 3.

Интегральный криптоанализ

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

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

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

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

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

Этот метод нашёл широкое применение и был использован в атаках на шифры IDEA, Khufu and Khafre, E2, разновидности Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac, Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, и SHACAL-2.

Наиболее известные работы

• 1996 год — вместе с Бартом Пренелем (англ. Bart Preneel) предложил способ создания хеш-функций, основанных на блочных шифрах. В работе Кнудсен продемонстрировал новую атаку LOKIDBH, которая разбила последний подкласс широкого класса эффективных хеш-функций, ранее предложенных в литературе.

• Рассмотрел нелинейные приближения в линейном криптоанализе и получил обобщение криптоаналитических методов Мацуи. Это позволило достичь большей гибкости в криптоатаках. Достижения были продемонстрированы на примере атаки на LOKI91.

• Подробно исследовал шифр SAFER на устойчивость^[2]. Разработал атаку, которая привела к значительной модификации алгоритма шифрования и появлению SAFER-SK (в шутку друзья Ларса расшифровывали SK как Stop Knudsen, хотя в действительности это означает Strengthened Key schedule).

• 1997 год — в статье «The Block Cipher Square»^[3] предложил атаку на 128-битный шифр Square, которая положила начало новой ветви криптоанализа — интегральному криптоанализу. Подробно исследовал шифр IDEA с урезанным количеством раундов. Опубликовал работу, посвящённую слабостям этого алгоритма.

• 1998 год — в команде разработчиков (Росс Андерсон, Эли Бихам) предложил симметричный блочный алгоритм шифрования Serpent^[4], который стал одним из финалистов второго этапа конкурса AES. Разработал алгоритм шифрования DEAL^[5], основанный на DES.

• 1999 год — вёл исследования по быстрому аппаратному шифрованию.

• 2000 год — совместно с Вилли Мейером (англ. Willi Meier) опубликовал подробный анализ очередного кандидата AES — RC6.

• 2001 год — инициировал исследования в области он-лайн шифров и Hash-CBC конструкций. Занимался исследованием устойчивости алгоритма Skipjack.

• 2002 год — выступил с докладом «Достижения в области криптографии» на EUROCRYPT 2002, а также занимался цифровыми подписями и кодами, исправляющими ошибки. Исследовал безопасность шифров Фейстеля с шестью раундами и менее.

• 2003—2004 годы — исследовал 3gpp-MAC и RMAC, а также выступал на конференциях ESORICS и AES.

• 2005 год — опубликовал концепцию криптографической хеш-функции Smash, а также разработал атаки на MD2 и RMAC.

• 2007 год — опубликовал подробный анализ хеш-функции CRUSH.

• 2009 год — выступил на EUROCRYPT с докладом о рандомизации для усиления защищённости цифровых подписей, а также на CRYPTO с докладом о криптоанализе C2.

Всего Ларс Кнудсен опубликовал более 70 работ по очень широкому спектру тем, таких как R-MAC схема, хеш-функции SHA-1 и MD2, множество блочных шифров — DES, DFC, IDEA, ICE, LOKI, MISTY, RC2, RC5, RC6, SC2000, Skipjack, Square и SAFER. Выступал на конференциях также с докладами по помехоустойчивым кодам. Участвовал в разработках систем навигации роботов.

Последователи и коллеги

В данный момент Ларс Кнудсен возглавляет криптографическую группу в Датском Техническом Университете. В эту рабочую группу входят:

• Грегор Линдер (англ. Gregor Leander)
• Эрик Ценнер (англ. Erik Zenner)
• Правин Гаураварам (англ. Praveen Gauravaram)
• Кристиан Матусевич (англ. Krystian Matusiewicz)
• Сорен Стефен Томсен (англ. Søren Steffen Thomsen)
• Джулия Боргхоф (англ. Julia Borghoff)
• Валери Гаутхаер Умана (англ. Valerie Gauthier Umana)

Примечания