Кнудсен, Ларс

Ларс Рамкильд Кнудсен
Дата рождения	21 февраля 1962(1962-02-21) (62 года)
Страна	Дания
Род деятельности	криптолог, специалист в области информатики, профессор
Научная сфера	математика, криптография, теория информации
Место работы	Датский технический университет
Альма-матер	Орхусский университет
Научный руководитель	Иван Дамгорд[вд]
Известен как	автор множества криптоатак, разработчик шифров SAFER и SQUARE, один из основателей интегрального криптоанализа и криптоанализа невозможных дифференциалов
Награды и премии	IACR Fellow[вд] (2013)
Сайт	www2.mat.dtu.dk/people/L… dtu.dk/service/telefonbo… orbit.dtu.dk/en/persons/…
Медиафайлы на Викискладе

Ларс Рамкильд Кнудсен (21 февраля 1962 (1962-02-21)) — датский математик и исследователь в области криптографии, профессор кафедры математики в Датском техническом университете. Его исследования включают в себя разработку и анализ блочных шифров, хеш-функции и коды аутентичности сообщений (MACs).

Кнудсен — один из основателей криптоанализа невозможных дифференциалов^[англ.] и интегрального криптоанализа. Ларс является одним из разработчиков Grøstl.

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

В 1992 году получил степень магистра, а уже в 1994 — степень доктора философии.^[1] С 1997 по 2001 год работал в Бергенском университете, Норвегия. Был дважды избран директором Международной ассоциации криптографических исследований (IACR) с января 2001 года по декабрь 2003 года и с января 2004 года по декабрь 2006 года. C 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 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, означающее «Усиленное расширение ключа».

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

В своей статье «Hash functions based on block ciphers and quaternary codes»^[3](«Хеш-функции, основанные на блочных шифрах и четвертичных кодах») Ларс Кнудсен показал, что разработка эффективной хеш-функции с минимальной встроенной памятью на основе m — битного блочного шифра представляет собой трудную задачу. Более того, ни одна из рассмотренным им хеш-функций не обеспечивала защиты лучше, чем 2^m получаемой методом «грубой силы». Изменяя модель немного(например, путём увеличения размера внутреннее памяти, а также путём введения выходных преобразований), можно получить функцию сжатия и, таким образом, хеш-функцию, для которой безопасность может быть доказана на основе вероятных предположений, сформулированных Кнудсеном. Предлагаемый им метод являлся как лучшим на текущий момент (а именно скорость шифрования равной ${\displaystyle {\frac {1}{4}}}$ или 4 для хеширования одного блока), так и обеспечивал высокий уровень безопасности, или более высокую эффективность при тех же уровнях безопасности. Для большого значения встроенной памяти, скорости близки к тем, которые могут быть получены. Кроме того, хеш-функция обеспечивает высокую степень параллелизма, которая даст ещё более эффективную реализацию.

RMAC^[4] — система аутентификации на основе блочных шифров. В настоящее время алгоритмы блочного шифра, одобренные, чтобы использоваться в RMAC, являются AES и тройной-DES. В своей работе Кнудсен проанализировал эту систему и получил, что схема позволяет атаковать некоторый контроль над одним из двух ключей основного блочного шифра и это позволяет предпринять несколько связно-ключевых атак на RMAC. Также он описал эффективное нападение на RMAC при использовании с тройной-DES и общую атаку на RMAC, которая может быть использована по поиску одного ключа из двух быстрее, чем полный перебор. Его атака на RMAC-DES требует ${\displaystyle 2^{16}}$ набранных сообщений, которая практически возможна с сегодняшней скоростью обработки.

В своей работе Кнудсен исследовал фальсификацию и атаку на ключ восстановления на аутентификационной схеме 3gpp-MAC^[5], предложенной в 3gpp спецификацию. Он предложил три основных класса атак. Атаки в первом классе используют большое количество «выбранных MACs», во втором классе используют большое количество «известных MACs», а в третьем классе требуется большое количество проверок MAC, но очень мало «известных MACs» и совсем не требуют «выбранных MACs». Первый класс предоставляет как фальсификацию, так и атаку на ключ восстановления, в то время как, второй и третий классы только атаку на ключ. Принимаются во внимание, как простые ключи(single-key), так и двойные ключи(two-key). Атака фальсификации имеет отношение к обоим видам ключей, в то время как, атака на ключ восстановления относится только ко второму варианты(two-key).

Структура хеш-функции CRUSH^[6] показана на рисунке. Функция состоит их буфера данных (data buffer), компоненты биекционного выбора (Bijection Selection Component) логических (булевых) функций и биективной функции B (эффективного блочного шифра, для которого текст берется из буфера данных). Кнудсен показал, что CRUSH или более общий метод повторного деления на два (Iterated Halving) не удовлетворяют требованиям хороших хеш-функций или с точки зрения безопасности или выполнения. Он показал, как генерировать коллизии и вторые прообразы для использования Повторного деления на два (Iterated Halving). Возможность создания таких коллизий основана на функции B. Сложность этих атак является чрезвычайно малой и составляет всего лишь десяток расшифровок функции B, независимо от размера. Атаки применяются, когда используется любой блочный шифр, включая AES с 192-битовыми и AES c 256-битовыми ключами.

• 1996 год — вместе с Бартом Пренелем (англ. Bart Preneel) предложил способ создания хеш-функций, основанных на блочных шифрах. В работе Кнудсен продемонстрировал новую атаку LOKIDBH, которая разбила последний подкласс широкого класса эффективных хеш-функций, ранее предложенных в литературе.
• Рассмотрел нелинейные приближения в линейном криптоанализе и получил обобщение криптоаналитических методов Мацуи. Это позволило достичь большей гибкости в криптоатаках. Достижения были продемонстрированы на примере атаки на LOKI91.
• Подробно исследовал шифр SAFER на устойчивость^[7]. Разработал атаку, которая привела к значительной модификации алгоритма шифрования и появлению SAFER-SK (в шутку друзья Ларса расшифровывали SK как Stop Knudsen, хотя в действительности это означает Strengthened Key schedule).
• 1997 год — в статье «The Block Cipher Square»^[8] предложил атаку на 128-битный шифр SQUARE, которая положила начало новой ветви криптоанализа — интегральному криптоанализу. Подробно исследовал шифр IDEA с урезанным количеством раундов. Опубликовал работу, посвящённую слабостям этого алгоритма.
• 1998 год — в команде разработчиков (Росс Андерсон, Эли Бихам) предложил симметричный блочный алгоритм шифрования Serpent^[9], который стал одним из финалистов второго этапа конкурса AES. Разработал алгоритм шифрования DEAL^[10], основанный на 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^[англ.], MISTY1, RC2, RC5, RC6, SC2000, Skipjack, SQUARE и SAFER. Выступал на конференциях также с докладами по помехоустойчивым кодам. Участвовал в разработках систем навигации роботов.

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

• Андрей Богданов (англ. Andrey Bogdanov) — профессор,
• Кристиан Рехбергер (англ. Christian Rechberger) — профессор,
• Эльмар Тишхаузер (англ. Elmar Tischhauser) — профессор,

а также несколько постдоков и аспирантов.

• Шнайер Б. Глава 14. И ещё блочные шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 382—384. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Matt Henricksen and Lars R. Knudsen. Cryptanalysis of the CRUSH Hash Function (неопр.).
• Lars R. Knudsen and Tadayoshi Kohno. Analysis of RMAC (неопр.). — 1991.
• 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 (неопр.).

• Домашняя страница Ларса Кнудсена Архивная копия от 6 марта 2010 на Wayback Machine (англ.)
• Публикации Ларса Кнудсена Архивная копия от 9 декабря 2009 на Wayback Machine (англ.)
• Курс «защита информации», кафедра радиотехники(МФТИ)
• Конкурс на новый криптостандарт AES
• The Block Cipher Companion (Information Security and Cryptography) (англ.)
• Lars R. Knudsen’s work  (англ.)