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

В Википедии есть статьи о других людях с фамилией Кнудсен.

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

Ларс Рамкильд Кнудсен
Дата рождения	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/…
Медиафайлы на Викискладе

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

Биография

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

В 1992 году получил степень магистра, а уже в 1994 — степень доктора философии. С 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

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 получаемой методом «грубой силы». Изменяя модель немного(например, путём увеличения размера внутреннее памяти, а также путём введения выходных преобразований), можно получить функцию сжатия и, таким образом, хеш-функцию, для которой безопасность может быть доказана на основе вероятных предположений, сформулированных Кнудсеном. Предлагаемый им метод являлся как лучшим на текущий момент (а именно скорость шифрования равной ${\frac {1}{4}}$ или 4 для хеширования одного блока), так и обеспечивал высокий уровень безопасности, или более высокую эффективность при тех же уровнях безопасности. Для большого значения встроенной памяти, скорости близки к тем, которые могут быть получены. Кроме того, хеш-функция обеспечивает высокую степень параллелизма, которая даст ещё более эффективную реализацию.

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

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

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

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

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

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

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

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