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

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

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

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций

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

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

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

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

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

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

Существующие коммерческие прототипы квантовых компьютеров, в том числе разрабатываемые фирмами 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 предъявляет требования по стойкости к участникам конкурса как формальные (т.е. наличие строгого обоснования на основе предположения о сложности решения некоторой задачи), так и практические (оценка трудоемкости криптоанализа). Рассмотрим сначала первые.

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

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

  • стойкость к угрозе различения шифртекстов относительно атаки на основе подобранного открытого текста (IND-CPA);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе подобранного шифрованного текста (IND-CCA);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе (неадаптивно) подобранного открытого текста (IND-CPA1);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе (неадаптивно) подобранного шифрованного текста (IND-CCA1);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе адаптивно подобранного открытого текста (IND-CPA2);
  • стойкость к угрозе различения шифртекстов относительно атаки на основе адаптивно подобранного шифртекста (IND-CCA2).

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

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

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

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

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


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

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

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


В числе конкурсантов NIST следующие криптосхемы основаны на теории решеток3: 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.

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


К числу основанных на задачах теории кодирования конкурсантов 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, схема Мацумото – Имаи.


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

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

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

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

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

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

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

  1. Для шифрования с открытым ключом и инкапсуляции ключа: BIKE, Classic McEliece, CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (производная схема от LEDAkem/LEDAp-kc), 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 г. меморандум7 Агентства национальной безопасности США в явном виде предлагает американским разработчикам средств криптографической защиты информации, не успевшим к настоящему времени внедрить в свои продукты криптографические алгоритмы, основанные на операциях на эллиптических кривых, воздержаться от их реализации, чтобы сэкономить ресурсы для предполагаемого в ближайшем будущем перехода на постквантовые алгоритмы), заставляет тщательно проверять новые стандарты, разрабатываемые в рамках программ этой организации, во избежание повторения скандальной истории с алготитмом выработки псевдослучайных п о следов ательностей Dual_EC_DRBG, который был стандартизирован вопреки возражениям ряда исследователей, указавших на его очевидные уязвимости, что в дальнейшем потребовало отзыва стандарта.

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

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

___________________________________________
1 B. Schneier, NSA Plans for a Post-Quantum World, https://www.schneier.com /blog/archives/2015/08/n sa_plans_for_a.html, 2015.
2 M. Dyakonov, The Case Against Quantum Computing, https://spec- trum.ieee.org/computing/h ardware/the-case-against- quantum-computing, 2018.
3 Здесь перечеркнуты назва- ния отозванных или взло- манных схем, символ (*) после названия схемы обо- значает наличие атаки (не обязательно полностью компрометирующей схему) на нее (см. M.-J. Saarinen, (Most) Post-Quantum Bugs are just Plain Old Bugs, CTCrypt 2018 Rump Ses- sion).
4 1994 год, В.М. Сидельников (1940–2008).
5 Несостоятельность использования групп кос для построения стойких криптосхем была показана в 2014 г. российским специалистом М.М. Глуховым (1930–2018).
6 https://csrc.nist.gov/news/ 2019/pqc-standardization- process-2nd-round-candidates
7 Cryptography Today https://www.nsa.gov/ia/pr ograms/suiteb_cryptograp- hy/index.shtml, 2015.

Опубликовано: Журнал "Information Security/ Информационная безопасность" #1, 2019
Посещений: 499

Приобрести этот номер или подписаться
  Автор

Сергей Гребнев

Сергей Гребнев

Эксперт ТК 26

Всего статей:  2

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций