Контакты
Подписка
МЕНЮ
Контакты
Подписка

О некоторых тенденциях развития постквантовой криптографии

Сергей Гребнев, 31/05/19

 

 

Читателю предлагается обзор основных направлений и перспектив стандартизации криптографических механизмов защиты информации, стойких как относительно классических, так и квантовых методов анализа (так называемых постквантовых криптографических алгоритмов), прежде всего на основе материалов мероприятий, проводимых американским Национальным институтом стандартов и технологий (NIST). Обозначен ряд проблем, возникающих перед отечественным криптографическим сообществом ввиду перспективы создания квантового вычислителя.

 

В настоящее время как за рубежом, так и в Российской Федерации ведутся активные исследования в области квантовых вычислений. Создание компьютера, реализующего квантовую модель вычислений (квантового компьютера) повлечет негативные последствия для ряда криптографических механизмов. В частности, на квантовом компьютере можно реализовать с полиномиальной сложностью алгоритмы факторизации и дискретного логарифмирования в произвольной группе (метод Шора), что в перспективе может привести к компрометации всех асимметричных криптографических схем, стойкость которых обосновывается предположением о сложности решения указанных задач, в том числе схем RSA, Диффи – Хеллмана и цифровых подписей ECDSA и ГОСТ Р 34.10–2012. При этом прорыва в области криптоанализа симметричных криптосхем не ожидается, поскольку известные в настоящее время квантовые алгоритмы анализа хэш-функций и блочных шифров (метод Амбайниса для поиска коллизий и метод Гровера для поиска прообраза) по-прежнему имеют экспоненциальную сложность, хотя и меньшую, чем классические.

При этом специалисты по-разному оценивают перспективы создания действующих образцов квантового вычислителя с характеристиками, достаточными для решения задач практического криптоанализа. Прогнозные оценки сроков создания таких квантовых компьютеров составляют от 10 до 40 лет , некоторые особо пессимистично настроенные ученые считают физические препятствия на пути создания квантовых вычислителей непреодолимыми.

Основной характеристикой мощности квантового вычислителя является количество кубитов – элементарных блоков. Задавая условие задачи как начальное состояние системы кубитов, составляющих квантовый вычислитель, и производя над ними серию предписанных квантовым алгоритмом преобразований, в результате финального измерения состояния системы кубитов получают решение задачи. При этом однако возникают значительные трудности инженерно-физического характера, связанные с необходимостью противодействия физической деградации кубитов в процессе вычислений и проведения точных измерений их состояния.

Для успешной факторизации числа N, являющегося секретным ключом криптографической системы RSA, метод Шора требует приблизительно 4/3logN кубитов и полиномиальное количество операций. В настоящее время нормативно-методические документы, регулирующие применение системы RSA, рекомендуют использование чисел длиной 2048 и более битов, таким образом, провести практически успешный криптоанализ можно будет на квантовом вычислителе мощностью не менее 2730 кубитов.

Существующие коммерческие прототипы квантовых компьютеров, в том числе разрабатываемые фирмами IBM и D-Wave, в основном предназначены для решения оптимизационных задач и не подходят для целей криптоанализа. Отметим, что в январе текущего года фирма IBM представила "персональный" 20-кубитовый квантовый вычислитель, смонтированный в корпусе объемом около 9 м3. Квантовые вычислители фирмы D-Wave, используемые в том числе Google и NASA, имеют, по утверждениям фирмы-производителя, до 1152 кубитов, сгруппированных в несколько кластеров, однако характер их внутренних топологических связей позволяет утверждать о наличии значительных ограничений в реализованной в данных устройствах модели квантовых вычислений.

Направления синтеза криптографических схем, стойких относительно анализа как с использованием классических, так и квантовых вычислений, получили общее название “постквантовая криптография”. Первая международная конференция PQCrypto, посвященная этим направлениям, состоялась в 2006 г. и с тех пор проводится каждые 1–2 года.

В последнее время проводимые международным криптографическим сообществом исследования в области синтеза постквантовых криптоалгоритмов интенсифицировались благодаря усилиям Национального института стандартов и технологий США (NIST), организовавшего площадку для подачи предложений по стандартизации и обсуждения постквантовых криптографических схем. (Отметим, что данное мероприятие формально не является конкурсом, поскольку предусматривает не выдвижение и награждение победителя, а лишь определение набора оптимальных синтезных решений для дальнейшего исследования и перспективной стандартизации, но носит все его черты, поэтому далее будем употреблять выражение “конкурс NIST”.) Прием заявок на участие в конкурсе NIST завершен 30 ноября 2017 г. Всего поданы описания 69 криптографических механизмов, разработанных авторскими коллективами из различных стран, в том числе международными. В апреле 2018 г. состоялся симпозиум, подводящий итог этапу приема заявок.

Решения, поданные для участия в конкурсе NIST, реализуют следующие механизмы: цифровую подпись, шифрование, инкапсуляцию ключей и выработку общего ключа. Учитывая опыт ранее проводимых NIST конкурсов на создание блочного шифра (AES) и хэш-функции (SHA-3), комплекс работ по анализу предложений и созданию новых стандартов может занять до пяти лет.

NIST предъявляет требования по стойкости к участникам конкурса как формальные (строго доказуемые на основе предположения о сложности решений некоторой задачи), так и практические. Рассмотрим сначала первые.

Асимметричные системы шифрования

Для асимметричных систем шифрования (перечислены от слабых требований к сильным):

  • стойкость к угрозе различения шифртекстов относительно атаки на основе подобранного открытого текста (Indistinguishability Against Chosen Plaintext Attack, IND-CPA);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе подобранного шифрованного текста (Indistinguishability Against Chosen Ciphertext Attack, IND-CCA);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе (неадаптивно) подобранного открытого текста (Indistinguishability Against (non-adaptive) Chosen Plaintext Attack, IND-CPA1);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе (неадаптивно) подобранного шифрованного текста (Indistinguishability Against (non-adaptive) Chosen Ciphertext Attack, IND-CCA1);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе адаптивно подобранного открытого текста (Indistinguishability Against Adaptive Chosen Plaintext Attack, IND-CPA2);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе адаптивно подобранного шифрованного текста (Indistinguishability Against Adaptive Chosen Ciphertext Attack, IND-CCA2).

Электронная подпись

Для схем подписи интерес представляют следующие понятия стойкости (перечисленные от слабых требований к сильным):

  • сильная стойкость к подделке относительно атак на основе подобранных сообщений (Strong Unforgeability under Chosen Message Attacks, SUF-CMA);
  • стойкость к экзистенциальной подделке относительно атак на основе подобранных сообщений (Existentially Unforgeability under Chosen Message Attacks, EUF-CMA).

Практическая стойкость

Определения практической стойкости, заданные требованиями NIST, предусматривают пять уровней стойкости.

grebnev_tab1

Для каждой заявки должно быть предоставлено формальное доказательство стойкости, предложены наборы параметров для некоторых (необязательно всех) уровней стойкости.

Всего на конкурс подано 69 заявок, 14 из них уже отозваны авторами или взломаны, на 13 схем опубликованы атаки (не всегда приводящие к их компрометации или отзыву).

Одна из заявок, поданная Д. Бернштейном с соавторами, носит явно сатирический характер, в ней предлагается использовать RSA с экспоненциальным размером ключей; так, для пятого уровня стойкости предполагается использовать ключи размером более 1 Гбайт.

Перечислим теперь основные синтезные решения, применяемые конкурсантами NIST:

  • использование теории целочисленных решеток;
  • использование кодов, исправляющих ошибки;
  • использование многочленов от многих переменных;
  • использование криптографических хэш-функций;
  • использование изогений на суперсингулярных эллиптических кривых;
  • узкоспециализированные задачи (проблемы сопряженного поиска (Search Problem) или операции в группах кос (Braid Groups), алгебра октонионов, многочлены Чебышёва и т.д).

Криптосхемы на основе теории решеток (см. пример соответствующей схемы выработки общего ключа на рис. 1) основаны на ряде сложных задач, в их числе NP-задачи поиска кратчайшего вектора (SVP) и поиска ближайшего вектора (CVP); задача обучения с ошибками (LWE; RLWE) и задача поиска наименьшего целочисленного решения системы линейных алгебраических уравнений (SIS).

grebnev_ris1В числе конкурсантов NIST следующие криптосхемы основаны на теории решеток¹: Compact LWE, CRYSTALS-KYBER, Ding Key Exchange, EMBLEM and R.EMBLEM, FrodoKEM, HILA5 (*), KCL (pka OKCN/AKCN/CNKE), KINDI, LAC, LIMA, Lizard, LOTUS, NewHope, NTRUEncrypt, NTRU-HRSS-KEM, NTRU Prime, Odd Manhattan, Round2, Round5, SABER, Three Bears, Titanium, CRYSTALS-DILITHIUM, DRS (*), FALCON, pqNTRUSign, qTESLA.


¹ Здесь перечеркнуты названия отозванных или взломанных схем, символ (*) после названия схемы обозначает наличие атаки (не обязательно полностью компрометирующей схему) на нее (см. M.-J. Saarinen, (Most) Post-Quantum Bugs are just Plain Old Bugs, CTCrypt 2018 Rump Session).


Задачи теории кодирования рассматривались в криптографии с конца 1970-х гг., так, схема МакЭлиса хотя и взломана для ряда частных случаев российскими специалистами², при условии использования кодов Гоппы остается стойкой.


² 1994 год, В.М. Сидельников (1940--2008).


Схема приведена на рис. 2.

grebnev_ris2

К числу основанных на задачах теории кодирования конкурсантов NIST относятся: BIG QUAKE, BIKE, Classic McEliece, DAGS (*), Edon-K (*), HQC, LAKE, LEDAkem, LEDApkc, Lepton, LOCKER, McNie, NTS-KEM, Ouroboros-R, QC-MDPC KEM, Ramstake, RLCE-KEM (*), RQC, pqsigRM, RaCoSS (*), RankSign (*).

Следующая идея – использование NP-полной задачи решения системы многочленов от многих переменных – исследуется с точки зрения синтеза криптосхем с середины 1980-х гг. (см. пример на рис. 3). В то же время разработаны различные практически эффективные методы для решения этой задачи (XL-метод, F4, F5 и др.), многие из криптосхем, построенных на данной задаче, были успешно атакованы (вспомним системы HFE, Мацумото – Имаи).

grebnev_ris3

К числу основанных на этой задаче конкурсантов NIST относятся: CFPKM, Giophantus (*), DualModeMS, GeMSS, Gui, HiMQ-3, LUOV, MQDSS, Rainbow, SRTPI (*), DME.

Основанные на хэшировании схемы подписи используют разработанные еще в конце 1970-х гг. идеи одноразовой подписи Лампорта и Винтерница, адаптируя их для построения многоразовой схемы подписи на основе древовидной структуры хэш-значений специального вида. Эту идею в том или ином виде применяют следующие конкурсанты NIST: SPHINCS+, GravitySPHINCS.

На сложной задаче поиска пути в графе изогений между суперсингулярными эллиптическими кривыми основана схема SIKE.

К прочим примитивам относятся WalnutDSA (*) (группы кос³), pqRSA (юмор), Guess Again (*), HK17 (*), Mersenne-756839, RVB (*), Picnic.


³ Несостоятельность использования групп кос для построения стойких криптосхем была показана в 2014 г. российским специалистом М.М. Глуховым (1930--2018).


30 января 2019 г. NIST опубликовал перечень кандидатов, прошедщих на второй этап конкурса. В их число вошли следующие схемы:

  1. Для шифрования с открытым ключом и инкапсуляции ключа: BIKE, Classic McEliece, CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (производная схема от LEDAkem/LEDApkc), NewHope, NTRU (производная схема от NTRUEncrypt/NTRU-HRSS-KEM), NTRU Prime, NTS-KEM, ROLLO (производная схема от LAKE/LOCKER/Ouroboros-R), Round5 (производная схема от Hila5/Round2), RQC, SABER, SIKE, Three Bears.
  2. Для схем цифровой подписи: CRYSTALS-DILITHIUM, FALCON, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow, SPHINCS+.

Можно отметить, что эксперты NIST не высказали явного предпочтения при выборе базовых синтезных решений, исключив лишь наиболее экзотические (на которые и пришлась большая часть атак).

Следующим этапом будет внесение правок и улучшений в прошедшие на второй этап схемы, для этого отводится срок до 15 марта 2019 г.

Важным вопросом является эффективность предлагаемых на конкурс NIST схем. Необходимо отметить, что все без исключения схемы имеют размер параметров, длину ключей и, как правило, длину шифртекста (подписи, общего ключа) большую, чем у традиционных криптографических схем (RSA, ECDH, ECDSA) при равном (относительно классического вычислителя) уровне стойкости. Как правило, вычислительных ресурсов (процессорного времени, памяти) также требуется больше.

Таким образом, переход к постквантовой криптографии потребует для сохранения функциональности защищенных сетей обработки информации значительного увеличения выделяемых на криптографические преобразования вычислительных ресурсов.

Область постквантовой криптографии охвачена и в деятельности Международной организации по стандартизации/Международной электротехнической комиссии. Так, профильным техническом комитетом, отвечающим за стандартизацию механизмов обеспечения информационной безопасности, инициировано проведение работ по созданию установочного документа, в котором будут отражены основные направления создания постквантовых криптографических схем.

Заключение

Таким образом, международное сообщество активно готовится к наступлению постквантовой эры. Очевидна также необходимость подготовки  отечественной информационной инфраструктуры к появлению квантовых криптоаналитических вычислителей, для чего потребуется разработка семейства постквантовых стандартов в области криптографической защиты информации, учитывая, разумеется, и международный опыт. При этом, однако, надо принимать во внимание ряд следующих соображений.

  1. Российская система стандартизации традиционно придерживается использования криптографических механизмов, прошедших проверку временем: за длительный период исследований в данном механизме не должно быть найдено уязвимостей. История постквантовой криптографии же насчитывает в лучшем случае пять лет, за исключением схем NTRU, основанных на теории кодирования схем типа МакЭлиса и некоторых других.
  2. Определенная спешка, с которой NIST проводит мероприятия по внедрению постквантовой криптографии (так, опубликованный в 2015 г. меморандум Агентства национальной безопасности США в явном виде предлагает американским разработчикам средств криптографической защиты информации, не успевшим к настоящему времени внедрить в свои продукты криптографические алгоритмы, основанные на операциях на эллиптических кривых, воздержаться от реализации указанных алгоритмов, чтобы сэкономить ресурсы для предполагаемого в ближайшем будущем перехода на постквантовые алгоритмы), заставляет тщательно проверять новые стандарты, разрабатываемые в рамках программ этой организации, во избежание повторения скандальной истории со стандартом генерации псевдослучайных чисел Dual_EC_DRBG, который был стандартизирован вопреки возражениям ряда исследователей, указавших на его очевидные уязвимости, что в дальнейшем потребовало отзыва стандарта.
  3. Очевидно, что момент перехода к постквантовой криптографии потребует коренной перестройки всей базовой инфраструктуры информационной безопасности, всех средств криптографической защиты информации, использующих асимметричные криптографические алгоритмы, в частности инфраструктуры удостоверяющих центров. Учитывая объем затрат на данные мероприятия, решение о переходе к использованию постквантовой криптографии должно приниматься взвешенно, на основе точного прогноза развития мощности квантовых вычислителей.

Таким образом, необходимость разработки семейства постквантовых криптографических механизмов является важной, хотя на данный момент и не первоочередной задачей, которую предстоит решать не только в рамках Технического комитета "Криптографическая защита информации" (ТК 26), но и силами всего российского криптографического сообщества.

 

Темы:КриптографияТК 26Сергей ГребневКвантовая криптография
Комментарии

More...