SIDH и SIKE: архитектура и криптоанализ

Сверхсингулярный изогенный протокол Диффи—Хеллмана (SIDH), предложенный Жао и Де Фео в 2011 году, — это протокол обмена открытыми ключами, аналогичный протоколу Диффи—Хеллмана, но использующий изогении над сверхсингулярными эллиптическими кривыми. Обе стороны начинают с одной и той же сверхсингулярной кривой E над Fp2. Алиса вычисляет секретную изогению phi_A: E -> E_A (случайное ядро в подгруппе 2^a-кручения), публикует E_A и образы образующих подгруппы кручения Боба при отображении phi_A. Боб вычисляет phi_B: E -> E_B (случайное ядро в подгруппе 3^b-кручения), публикует E_B и образы образующих подгруппы кручения Алисы при отображении phi_B. Алиса использует опубликованные Бобом данные, чтобы вычислить phi_A': E_B -> E_AB; Боб вычисляет phi_B': E_A -> E_AB. Обе стороны получают j(E_AB) в качестве общего секрета.

Специальная форма простого числа в SIDH: p = 2^a * 3^b * f - 1 (f — небольшой кофактор для проверки простоты) — гарантирует, что кривая E над Fp2 обладает необходимой структурой кручения. Для SIKEp434 (уровень NIST 1, 128-битная постквантовая стойкость): p = 2^216 * 3^137 - 1, a = 216, b = 137. Это означает, что Алиса проходит 216 шагов изогений степени 2, а Боб — 137 шагов изогений степени 3. Размеры ключей: открытый ключ Алисы состоит из E_A и двух точек Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 байта. SIKEp751 рассчитан на 192-битную классическую и 128-битную квантовую стойкость и имеет открытые ключи размером 564 байта. Это самые маленькие открытые ключи среди всех кандидатов NIST PQC — ценой скорости, которая в 100–1000 раз ниже.

SIKE (сверхсингулярная изогенная инкапсуляция ключа) — защищённый от IND-CCA2 KEM, построенный на основе SIDH с использованием преобразования Фудзисаки—Окамото. SIKE.Encaps: выбрать случайное сообщение m, вычислить (c0 = открытый ключ SIDH с начальным значением m, c1 = H2(m) XOR pk), отправить (c0, c1). SIKE.Decaps: восстановить m из c0 с помощью секретного ключа, проверить c1, повторно вычислить (c0, c1), чтобы проверить согласованность, выдать K = H3(m, c0). Преобразование FO превращает обмен, защищённый от CPA, в KEM, защищённый от CCA2. SIKE участвовал во всех четырёх раундах конкурса NIST PQC (2017–2022), выдерживая обширный криптоанализ, — пока в июле 2022 года не появилась разрушительная классическая атака.

С 2011 по 2022 год SIDH выдерживал значительные усилия криптоаналитиков. Лучшими известными атаками на SIDH были: (1) общий алгоритм SSIP: O(p^{1/4}) в классическом случае и O(p^{1/6}) в квантовом случае с использованием алгоритма Тани; (2) атака «встреча посередине» на пути изогений: O(p^{1/4}) в классическом случае, как и для SSIP; (3) алгоритмы полиномиального времени для атак на определённые структуры (ван Оорсхот—Винер), неприменимые к SIDH. Десятки статей анализировали безопасность SIDH, и за 11 лет не было найдено ни одной классической или квантовой атаки полиномиального времени. Эта история сделала SIKE убедительным финалистом NIST. В конечном итоге взлом произошёл не из-за прямой атаки на SSIP, а благодаря использованию дополнительных сведений о точках кручения SIDH.

30 июля 2022 года Воутер Кастрик и Томас Декрю опубликовали препринт, в котором показали классическую атаку полиномиального времени на SIDH. Атака использует дополнительные сведения, содержащиеся во вспомогательных точках кручения SIDH phi_A(P_B), phi_A(Q_B): по существу, эти сведения раскрывают действие phi_A на подгруппе 3^b-кручения. В сочетании с кривой-образом E_A это позволяет восстановить ядро phi_A (а значит, и саму phi_A), применяя методы теории эллиптических кривых с комплексным умножением и изогений Ришело. Для SIKEp434 атака выполнялась на ноутбуке за 62 минуты — хотя этот набор параметров должен был обеспечивать 128-битную постквантовую стойкость. В течение нескольких дней независимые исследователи подтвердили атаку и распространили её на все параметры SIDH.

Конструкция SIDH требовала, чтобы обе стороны публиковали образы базисных точек кручения другой стороны при применении своей секретной изогении. Это было необходимо для работы протокола: без phi_A(P_B) и phi_A(Q_B) Боб не мог перенести свою изогению на кривую Алисы, чтобы вычислить общий секрет. Однако эти дополнительные сведения, раскрывающие действие phi_A, ограниченное подгруппой 3^b-кручения, оказались катастрофически более информативными, чем предполагалось. Атака Кастрика—Декрю использует кривые рода 2 (изогении Ришело), чтобы перенести задачу на объекты большего рода, где ограниченное действие полностью определяет phi_A. Эта утечка обусловлена самой структурой SIDH и не может быть устранена без изменения фундаментальной конструкции протокола.

5 июля 2022 года (до атаки Кастрика—Декрю) NIST объявил о первоначально выбранных для стандартизации алгоритмах PQC: ML-KEM (Кибер), ML-DSA (Дилитиум), SLH-DSA (SPHINCS+) и FN-DSA (Фалкон); SIKE в их число не вошёл, поскольку находился на втором раунде рассмотрения. Атака Кастрика—Декрю в июле 2022 года привела к тому, что NIST официально полностью исключил SIKE из дальнейшего рассмотрения. NIST заявил: "SIKE больше не рассматривается для стандартизации." Это было самым впечатляющим событием криптоанализа в конкурсе NIST PQC и показало, что даже схема, выдержавшая 11 лет анализа, может быть взломана благодаря принципиально новой математической идее.

В течение недели после атаки Кастрика—Декрю Томас Декрю и Лучано Майно (независимо друг от друга), а позднее Дамиен Робер опубликовали дальнейшие улучшения. Вариант атаки Робера использует ту же идею, но вычисляет кольцо эндоморфизмов E_A, а не восстанавливает ядро изогении напрямую, и с математической точки зрения его, возможно, проще описать. Столь быстрые независимые повторные открытия подтвердили, что атака Кастрика—Декрю выявила фундаментальную структурную слабость, а не какой-то малоизвестный трюк. Скорость появления последующих статей также отражала то, что многие исследователи изучали утечку через точки кручения SIDH как потенциальное направление атаки: они понимали, что это необычное раскрытие информации, но не могли его использовать, пока Кастрик и Декрю не нашли мост к кривым рода 2.

FESTA (быстрое шифрование на основе атак на сверхсингулярное кручение, 2023) — конструкция KEM, вдохновлённая SIDH, но не использующая вспомогательные данные о точках кручения. FESTA применяет другую структуру протокола: открытый ключ не содержит образов базиса кручения другой стороны; вместо этого секретная изогения фиксируется только с помощью кривой-образа (без дополнительных точек). FESTA выполняет шифрование с помощью изогений так, чтобы раскрывать меньше структурной информации. Предварительный анализ безопасности показывает, что FESTA избегает структуры атаки Кастрика—Декрю. Однако FESTA появилась недавно и подвергалась менее тщательному анализу, чем SIKE за 11 лет, поэтому сообщество исследователей изогений осторожно относится к внедрению новых схем до проведения всестороннего анализа.

Взлом SIKE даёт важные уроки. (1) Раскрытие дополнительных сведений опасно: дополнительные данные о точках кручения SIDH были необходимы протоколу, но привели к фатальной утечке информации. Проектировщики протоколов должны анализировать каждый фрагмент общедоступных данных, а не только основные значения. (2) История успешного противостояния атакам не является доказательством безопасности: 11 лет без известной атаки внушают уверенность, но не дают гарантии. Криптографические доказательства (сведение к чётко определённой трудной задаче) надёжнее, чем аргументы от авторитета или ссылка на успешное прохождение проверок. (3) Новые математические инструменты создают риски: в атаке Кастрика—Декрю использовались изогении Ришело рода 2 — инструмент из математики, который ранее не применялся в криптоанализе изогений. Криптоаналитики, изучающие новые примитивы, должны учитывать новые разделы математики.

Несмотря на взлом SIKE, криптография на основе изогений продолжает развиваться как научное направление. Подписи SQISign (177 байт для уровня 1) остаются самыми компактными из известных подписей PQC и используют другое предположение о трудности — задачу о кольце эндоморфизмов, на которую не влияет атака на SIDH. Протоколы на основе CSIDH используют структуру действия группы классов (коммутативные изогении) без утечки через точки кручения, хотя у CSIDH есть собственные проблемы: он медленнее прежнего SIDH, а анализ квантовой безопасности продолжается. Сообщество исследователей изогений рассматривает взлом SIKE как полезный опыт, углубивший понимание того, какие сведения необходимо скрывать в протоколах на основе изогений, — это ценные знания для проектирования будущих схем.

Какой аспект конструкции SIDH сделал возможной атаку Кастрика—Декрю?

SIDH использует чередующиеся цепочки изогений степеней 2^a и 3^b между двумя сторонами, обмениваясь образами дополнительных точек кручения для обеспечения обмена ключами. SIKE оборачивает SIDH преобразованием Фудзисаки—Окамото для обеспечения защиты от CCA2. У SIKE были самые маленькие ключи среди всех кандидатов NIST PQC (374 байта), но он работал в 100–1000 раз медленнее. После 11 лет анализа безопасности Кастрик—Декрю взломали SIKE в июле 2022 года с помощью изогений Ришело рода 2, использовав утечку через точки кручения. NIST исключил SIKE. FESTA избегает раскрытия сведений о точках кручения. SQISign продолжает использовать трудность задачи о кольце эндоморфизмов. Взлом SIKE показывает, что дополнительные общедоступные данные необходимо анализировать так же тщательно, как и основные значения протокола.