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

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

В 1992 году получил степень магистра, а уже в 1994 — степень доктора философии^[5]. С 1997 по 2001 год работал в Бергенском университете, Норвегия. С 2001 по 2022 год являлся профессором в Техническом университете Дании^[4]. Был дважды избран директором Международной ассоциации криптографических исследований (IACR) с января 2001 года по декабрь 2003 года и с января 2004 года по декабрь 2006 года. C 2003 по 2010 год был помощником редактора журнала о криптологии, являющемся официальным журналом IACR. С 2005 года является членом Датской академии технических наук (ATV)^[4]. В 2013 году был избран членом (Fellow) IACR^[6] и стал сооснователем компании Dencrypt A/S, а позднее — PiiGuard ApS, специализирующихся на технологиях безопасной связи^[4]. В период активности исследовательского центра FICS (Foundations in Cryptology and Security) был одним из его руководителей^[7]. С февраля 2022 по март 2023 года занимал должность старшего консультанта в Министерстве обороны Дании^[4]. С апреля 2023 года — профессор в Университете Южной Дании^[4].

Ларс Кнудсен принимал активное участие в конкурсе на новый криптостандарт AES. На нём он был единственным криптоаналитоком, который представлял сразу два проекта DEAL (Норвегия, Канада) и Serpent (Великобритания, Израиль, Норвегия). Казус с тем обстоятельством, что Кнудсен везде фигурирует как представитель Норвегии, объясняется чрезвычайной мобильностью датского ученого, за несколько последних лет перед конкурсом уже успевшего поработать во Франции, Швейцарии и Бельгии. На момент проведения конкурса AES Ларс преподавал криптологию в университет Бергена, Норвегия.

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

• 2021 — Рыцарь ордена Даннеброг.
• 2013 — избран членом (Fellow) IACR за «фундаментальный вклад в разработку и криптоанализ симметричных примитивов, а также за службу ассоциации».
• 2013 — премия IBM Faculty Award для поддержки создания магистерской программы по кибербезопасности в Техническом университете Дании.
• 2010 — первая премия на конкурсе «Немецкая премия в области IT-безопасности» (нем. Deutscher IT-Sicherheitspreis) за создание сверхлёгкого блочного шифра PRESENT^[8].
• 2005 — член Датской академии технических наук (ATV).

Во всём мире Ларс Кнудсен известен благодаря знаменитым атакам на шифры SAFER и SQUARE, его работам по криптоанализу невозможных дифференциалов и интегрального криптоанализа. Кнудсен впервые предложил использовать усечённые дифференциалы для атак на 6-раундовый DES. В дальнейшем этот метод был использован и для атак на Skipjack и SAFER с усечённым числом раундов. Также Ларс разработал шифры DEAL и Serpent (последний вместе с англичанином Россом Андерсоном и израильтянином Эли Бихамом). Внёс вклад в развитие легковесной криптографии, став соавтором блочных шифров PRESENT^[9] и PRINCE^[9]. Ещё одной разработкой Кнудсена является 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^[10]. Сам алгоритм состоял из 6 раундов, включающих 4 операции, линейное преобразование строк, нелинейную замену байт, транспонирование и сложение с ключом. Они выбрали атаку на основе подобранного открытого текста. Основная идея заключалась в выборе наборов текста. Было обнаружено, что из 256 выбранных открытых текстов найдутся два, которые однозначно определят ключ шифрования с подавляющим успехом, если бы шифр состоял из 4 раундов. Затем атака была продолжена на 5 и 6 раунды и успешно завершена, хотя и была невозможна из-за отсутствия современных технологий. Тем не менее, она считалась актуальной, так как она считалась одной из самых быстрых.

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

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

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

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

• 1996 год — вместе с Бартом Пренелем (англ. Bart Preneel) предложил способ создания хеш-функций, основанных на блочных шифрах. В работе Кнудсен продемонстрировал новую атаку LOKIDBH, которая разбила последний подкласс широкого класса эффективных хеш-функций, ранее предложенных в литературе.
• Рассмотрел нелинейные приближения в линейном криптоанализе и получил обобщение криптоаналитических методов Мацуи. Это позволило достичь большей гибкости в криптоатаках. Достижения были продемонстрированы на примере атаки на LOKI91.
• Подробно исследовал шифр SAFER на устойчивость^[15]. Разработал атаку, которая привела к значительной модификации алгоритма шифрования и появлению SAFER-SK (в шутку друзья Ларса расшифровывали SK как Stop Knudsen, хотя в действительности это означает Strengthened Key schedule).
• 1997 год — в статье «The Block Cipher Square»^[16] предложил атаку на 128-битный шифр SQUARE, которая положила начало новой ветви криптоанализа — интегральному криптоанализу. Подробно исследовал шифр IDEA с урезанным количеством раундов. Опубликовал работу, посвящённую слабостям этого алгоритма.
• 1998 год — в команде разработчиков (Росс Андерсон, Эли Бихам) предложил симметричный блочный алгоритм шифрования Serpent^[17], который стал одним из финалистов второго этапа конкурса AES. Разработал алгоритм шифрования DEAL^[18], основанный на 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.
• 2010 год — стал соавтором сверхлёгкого блочного шифра PRESENT, за создание которого был удостоен первой премии на конкурсе «Немецкая премия в области IT-безопасности». В этот же период был вовлечён в разработку хеш-функции Grøstl, кандидата в конкурсе SHA-3.
• 2011 год — разработанная при его участии хеш-функция Grøstl вошла в пятёрку финалистов конкурса SHA-3^[19][20]. В соавторстве с Мэтью Робшоу опубликовал книгу «The Block Cipher Companion»^[21].
• 2012 год — представил работу о блочном шифре с низкой задержкой PRINCE и выступил председателем 19-й Международной конференции по избранным областям криптографии (SAC 2012)^[21].
• 2013 год — опубликовал статьи «Slender-Set Differential Cryptanalysis» и «Lightweight Block Ciphers: A Survey» в журнале Journal of Cryptology^[21]. Стал соучредителем компании Dencrypt A/S, специализирующейся на технологиях безопасной связи.
• 2014 год — опубликовал статью «Dynamic Encryption» в журнале Journal of Cyber Security and Mobility^[21].
• 2015 год — в соавторстве представил исследование «Security of the AES with a Secret S-box» на конференции FSE 2015, в котором анализировалась безопасность AES при использовании секретного S-блока^[22].
• 2017 год — стал соавтором статьи «Reflections on the S-Box of Streebog», исследующей криптографические свойства S-блока российского стандарта хеширования «Стрибог»^[23].
• 2020 год — опубликовал работы, посвящённые использованию квантовых компьютеров для криптоанализа, в частности, для атаки на блочный шифр SMS4 и для анализа обобщённых сетей Фейстеля^[21].
• 2024 год — представил на конференции SecureComm 2024 исследование об атаках повторной идентификации на методы маскировки данных.

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

С апреля 2023 года Ларс Кнудсен является профессором в Университете Южной Дании, где работает в Институте Мэрска Мак-Кинни Мёллера и входит в состав Центра промышленного программного обеспечения (SDU Center for Industrial Software, CIS). В центре он является контактным лицом по направлению криптологии^[24].

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

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

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

Под научным руководством Ларса Кнудсена защитили диссертации и работали в качестве постдокторантов несколько специалистов, сделавших заметную карьеру в академической среде и индустрии кибербезопасности. Среди них:

• Мартин Альбрехт (англ. Martin Albrecht) — работал с Кнудсеном в качестве постдокторанта. В настоящее время является профессором кибербезопасности в Королевском колледже Лондона и главным научным сотрудником в SandboxAQ. Известен анализом безопасности реально используемых криптографических систем, таких как OpenSSH, Amazon EC2, Telegram и Matrix^[25][26].
• Штефан Кёльбль (англ. Stefan Kölbl) — был аспирантом и постдокторантом под руководством Кнудсена. В настоящее время работает криптографом в Google. Является соавтором пермутации Gimli, шифра Pyjamask и семейства легковесных блочных шифров SKINNY^[27].
• Кристиана Петерс (англ. Christiane Peters) — была постдокторантом в криптографической группе Технического университета Дании, где работал Кнудсен. В настоящее время — архитектор безопасности в Google, где её основное внимание сосредоточено на стратегии и внедрении постквантовой криптографии в Google Cloud. Является соавтором «Classic McEliece», одного из финалистов конкурса постквантовой криптографии, проводимого NIST^[28][29].
• Тиге Тиссен (англ. Tyge Tiessen) — защитил PhD под руководством Кнудсена в 2017 году. Является автором и соавтором работ по симметричной криптографии, включая анализ шифров для многосторонних вычислений (MPC) и гомоморфного шифрования (FHE)^[30][31].
• Юлия Боргхофф (англ. Julia Borghoff) — была постдокторантом в группе Кнудсена в Техническом университете Дании. Защитила диссертацию на тему криптоанализа легковесных шифров и участвовала в анализе шифров PRINCE, C2 и Trivium^[32].