Журнал "Information Security/ Информационная безопасность" #1, 2019

логий США (NIST), организо- вавшего площадку для подачи предложений по стандартиза- ции и обсуждения посткванто- вых криптографических схем. (Отметим, что данное меро- приятие формально не является конкурсом, поскольку пред- усматривает не выдвижение и награждение победителя, а лишь определение набора опти- мальных синтезных решений для дальнейшего исследования и перспективной стандартиза- ции, но носит все его черты, поэтому далее будем употреб- лять выражение "конкурс NIST".) Прием заявок на участие в кон- курсе NIST завершен 30 ноября 2017 г. Всего поданы описания 69 криптографических механиз- мов, разработанных авторскими коллективами из различных стран, в том числе междуна- родными. В апреле 2018 г. состоялся симпозиум, подводя- щий итог этапу приема заявок. Решения, поданные для уча- стия в конкурсе NIST, реализуют следующие механизмы: циф- ровую подпись, шифрование, инкапсуляцию ключей и выра- ботку общего ключа. Учитывая опыт ранее проводимых NIST конкурсов на создание блочного шифра (AES) и хэш-функции (SHA-3), комплекс работ по ана- лизу предложений и созданию новых стандартов может занять до пяти лет. NIST предъявляет требования по стойкости к участникам кон- курса как формальные (т.е. нали- чие строгого обоснования на основе предположения о слож- ности решения некоторой зада- чи), так и практические (оценка трудоемкости криптоанализа). Рассмотрим сначала первые. Асимметричные системы шифрования Для асимметричных систем шифрования (перечислены от слабых требований к сильным): l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе подобранного открытого текста (IND-CPA); l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе подобранного шифрованного текста (IND- CCA); l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе (неадаптивно) подобранного открытого текста (IND-CPA1); l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе (неадаптивно) подобранного шифрованного текста (IND-CCA1); l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе адаптивно подобранного открытого текста (IND-CPA2); l стойкость к угрозе различе- ния шифртекстов относительно атаки на основе адаптивно подобранного шифртекста (IND- CCA2). Электронная подпись Для схем подписи интерес представляют следующие поня- тия стойкости (перечисленные от слабых требований к силь- ным): l сильная стойкость к подделке относительно атак на основе подобранных сообщений (SUF- CMA); l стойкость к экзистенциальной подделке относительно атак на основе подобранных сообщений (EUF-CMA). Практическая стойкость Определения практической стойкости, заданные требова- ниями NIST, предусматривают пять уровней стойкости (см. табл. 1). Всего на конкурс подано 69 заявок, 14 из них уже ото- званы авторами или взломаны, на 13 схем опубликованы атаки (не всегда приводящие к их компрометации или отзыву). Одна из заявок, поданная Д. Бернштейном с соавторами, носит явно сатирический характер, в ней предлагается использовать RSA с экспонен- циальным размером ключей; так, для пятого уровня стойко- сти предполагается использо- вать ключи размером более 1 Гбайт. Криптосхемы на основе тео- рии решеток (рис. 1) основаны на ряде сложных задач, в их числе NP-задачи поиска крат- чайшего вектора (SVP) и поиска ближайшего вектора (CVP); задача обучения с ошибками (LWE; RLWE) и задача поиска наименьшего целочисленного решения системы линейных алгебраических уравнений (SIS). В числе конкурсантов NIST следующие криптосхемы осно- ваны на теории решеток 3 : Com- pact 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, Rain- bow, SRTPI (*), DME. Основанные на хэшировании схемы подписи используют раз- работанные еще в конце 1970-х гг. идеи одноразовой подписи Лампорта и Винтерни- ца, адаптируя их для построения многоразовой схемы подписи на основе древовидной струк- туры хэш-значений специально- го вида. Эту идею в том или ином виде применяют следую- щие конкурсанты NIST: SPHINCS+, GravitySPHINCS. На сложной задаче поиска пути в графе изогений между 34 • ТЕХНОЛОГИИ В последнее время про- водимые международным криптографическим сообще- ством исследования в обла- сти синтеза постквантовых криптоалгоритмов интенси- фицировались благодаря усилиям Национального института стандартов и тех- нологий США (NIST), орга- низовавшего площадку для подачи предложений по стандартизации и обсужде- ния постквантовых крипто- графических схем. Основные синтезные решения, применяемые кон- курсантами NIST: l использование теории целочисленных решеток; l использование кодов, исправляющих ошибки; l использование многочле- нов от многих переменных; l использование криптогра- фических хэш-функций; l использование изогений на суперсингулярных эллип- тических кривых; l узкоспециализированные задачи (проблемы сопря- женного поиска (Search Pro- blem) или операции в груп- пах кос (Braid Groups), алгебра октонионов, много- члены Чебышёва и т.д). 3 Здесь перечеркнуты назва- ния отозванных или взло- манных схем, символ (*) после названия схемы обо- значает наличие атаки (не обязательно полностью компрометирующей схему) на нее (см. M.-J. Saarinen, (Most) Post-Quantum Bugs are just Plain Old Bugs, CTCrypt 2018 Rump Ses- sion). 4 1994 год, В.М. Сидельни- ков (1940–2008). Рис. 1. Криптосистемы на решетках на примере RLWE