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

Ларс Рамкильд Кнудсен
англ. Lars Ramkilde Knudsen
Дата рождения:	21 февраля 1962(1962-02-21) (50 лет)
Место рождения:	Дания
Научная сфера:	математика, криптография, теория информации
Место работы:	Датский технический университет
Альма-матер:	Университет города Орхус
Известен как:	автор множества криптоатак, разработчик шифров SAFER и Square, один из основателей интегрального криптоанализа и криптоанализа невозможных дифференциалов

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

Атака на шифр 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^[2]. Сам алгоритм состоял из 6 раундов, включающих 4 операции, линейное преобразование строк, нелинейную замену байт, транспонирование и сложение с ключом. Они выбрали атаку на основе подобранного открытого текста. Основная идея заключалась в выборе наборов текста. Было обнаружено, что из 256 выбранных открытых текстов найдутся два, которые однозначно определят ключ шифрования с подавляющим успехом, если бы шифр состоял из 4 раундов. Затем атака была продолжена на 5 и 6 раунды и успешно завершена, хотя и была невозможна из-за отсутствия современных технологий. Тем не менее, она считалась актуальной, так как она считалась одной из самых быстрых.

Хэш-функция, основанная на блочном шифре

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

Исследование RMAC

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

Исследование 3gpp-MAC

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

Анализ хеш-функции CRUSH

Структура хеш-функции 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, 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)

Литература

• Шнайер Б. Глава 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.
• Lars Knudsen and Bart sPreneel 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.

Примечания

1. ↑ Lars Knudsen (1 июля 1994). «Block Cipher — Analysis, Design and Applications, Ph.D. Thesis, 1994.» (PDF). Проверено 2009-11-26.
2. ↑ Joan Daemen, Lars Knudsen and Vincent Rijmen (1997). «The block cipher Square» (PDF/PostScript).
3. ↑ Lars Knudsen and Bart Preneel (1996). «Hash functions based on block ciphers and quaternary codes» (PDF/PostScript).
4. ↑ Lars R. Knudsen and Tadayoshi Kohno (2007). «Analysis of RMAC» (PDF/PostScript).
5. ↑ Lars R. Knudsen and Chris J Mitchell (2003). «Analysis of 3gpp-MAC and two-key 3gpp-MAC».
6. ↑ Matt Henricksen and Lars R. Knudsen (2007). «Cryptanalysis of the CRUSH Hash Function» (PDF/PostScript).
7. ↑ Lars Knudsen. «A Key-schedule Weakness in SAFER K-64». Проверено 2009-11-26.
8. ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. «The Block Cipher SQUARE» (PDF). Проверено 2009-11-26.
9. ↑ Lars Knudsen, Eli Biham, Ross Anderson. «Serpent: A New Block Cipher Proposal» (PDF). Проверено 2009-11-26.
10. ↑ Lars Knudsen (21 февраля 1998). «DEAL — A 128-bit Block Cipher» (PDF/PostScript) (Department of Informatics, University of Bergen, Norway). Проверено 2009-10-26.

Ссылки

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