В последние годы разработка и стандартизация постквантовых криптосистем становятся важнейшей задачей в области информационной безопасности. Одним из ключевых проектов в этом направлении является инициатива Национального института стандартов и технологий США (NIST), направленная на выбор алгоритмов, способных противостоять угрозам со стороны квантовых компьютеров и обеспечить защиту данных в будущем. Одним из таких кандидатов стала криптосистема Kyber, в частности её вариант Kyber-512, заявленный как обеспечивающий уровень защиты, сопоставимый с AES-128, что является минимальным требуемым стандартом для широкого применения. Однако в 2023 году возникли серьёзные сомнения относительно корректности оценки безопасности Kyber-512, вызвавшие бурное обсуждение в криптографическом сообществе и поставившие под вопрос решения NIST. Основная проблема, выявленная исследователями, заключается в некорректном способе сложения вычислительных затрат, что привело к ошибочным итоговым числам и завышенным гарантиям безопасности для Kyber-512.
Конкретно, в расчетах NIST допущено грубейшее нарушение математических принципов: вместо того, чтобы складывать два критически важных параметра затрат — вычислительные ресурсы и расходы на доступ к памяти — была произведена их умножение. Психологически и технически этот момент напоминает классические ошибки в арифметике, когда неправильно складывают или умножают значения, игнорируя смысловую нагрузку. Например, возьмём простой пример из школьного курса: если два человека красят забор, и первый окрашивает его за 120 минут, а второй за 240 минут, то вместе они справятся быстрее, и ответ — 80 минут, а не 360 минут. Подобные ошибки в криптографических расчетах могут привести к аналогичным искажениям конечных выводов по безопасности. В случае Kyber-512 ошибка состоит в том, что оценки затрат на вычисления внутри части атаки и оценки затрат, связанных с большими массивами памяти, воспринимались как умножаемые величины, хотя по смыслу и технически их нужно было складывать.
Это привело к тому, что итоговая оценка сложности атаки оказалась многократно завышенной, создавая иллюзию большей безопасности, чем это соответствует реальным параметрам. В результате Kyber-512 была объявлена соответствующей требованиям категории 1 в стандартах NIST, то есть сопоставимой с AES-128 по уровню безопасности. Интересно отметить, что сам NIST при этом придерживался двух различных моделей затрат: «локальной», с учетом реальных затрат на доступ к памяти, и «нелокальной», где память считается доступной без дополнительных расходов. Для оценки NTRU-509, более гибкой и часто более производительной альтернативы Kyber, применялась «нелокальная» модель, которая показала, что она не достигает нужного уровня безопасности, что стало одной из причин её исключения из списка стандартизируемых систем. В то же время Kyber-512 защищали, ссылаясь на эффекты затрат памяти, которые по «локальной» модели поднимали оценку безопасности, хотя эта модель по факту не применялась для конкурентов.
Такое двойное измерение нельзя считать справедливым. Еще одной важнейшей проблемой является ограниченность параметров Kyber. В отличие от NTRU и его вариаций, которые предоставляют широкий набор параметров с гибкой масштабируемостью безопасности и размером ключей, Kyber предлагает очень узкий выбор параметров, жестко привязанных к размерности, кратной 256. Это ограничивает возможность точной настройки алгоритма под требования конкретных приложений и приводит к необходимости делать резкие скачки между вариантами Kyber-512, Kyber-768 и Kyber-1024. Такой подход противоречит одним из основных критериев, которые NIST первоначально объявлял как предпочтительные — гибкость и масштабируемость криптографических схем.
Кроме того, сопоставление эффективности показывает, что меньшие параметры NTRU, например NTRU-509 и NTRU-677, демонстрируют большую гибкость, в ряде случаев меньшие размеры публичных ключей и сопоставимый или более высокий уровень безопасности, чем Kyber-512, который в свою очередь обладает более узким диапазоном и, что главное, недостаточным уровнем безопасности, если честно пересчитывать затраты на атаки. В плане производительности NTRU проигрывает Kyber только по части времени генерации ключей, что в современных системах часто не играет ключевой роли, так как ключи могут переиспользоваться, а существуют оптимизации, снижающие затраты на этот этап. Сравнительный анализ, опубликованный экспертами, выявил многочисленные случаи манипуляций и выборочного подхода в представлении данных NIST. Ключевые неучтенные или приниженные параметры защиты и производительности Kyber-512 были компенсированы именно искусственным завышением безопасности посредством некорректного умножения затрат, а конкурирующие варианты NTRU были или исключены, или представлены в невыгодном свете. Помимо самой ошибки в вычислениях, большое беспокойство вызывает закрытость процесса принятия решений.
Запросы на получение дополнительной информации и раскрытие данных от исследователей неоднократно игнорировались, несмотря на юридические требования по открытости. Министерство юстиции США пришлось подать судебные иски с целью вынудить NIST и NSA раскрыть факты. Обнародованные позже документы показали сильную вовлеченность американской разведки в процесс стандартизации, что для сообщества вызвало еще больше вопросов о прозрачности и объективности выбора. Сложность оценки безопасности Kyber-512 усугубляется постоянно появляющимися улучшениями в атаках на решетчатые криптосистемы и отсутствие единого и устоявшегося подхода к учету всех факторов затрат, в том числе к эффективным моделям учета затрат на память, параллелизм и оптимизации. Кроме того, новые работы показывают, что ряд ранее предполагавшихся улучшений могут не работать или иметь другие ограничения, создавая огромную неопределенность в оценке реальной безопасности.
Важный аспект — неопределенность в том, насколько Kyber-512 действительно обеспечивает предписанный уровень безопасности в свете всех новых исследований. Несмотря на заявления, что Kyber-512 соответствует требованиям AES-128, при более строгом анализе и корректном суммировании затрат на вычисления и память она может уступать и не соответствовать заявленному уровню безопасности. Это очень опасно при внедрении стандарта для массовых применений, так как недооценка рисков приводит к потенциальной компрометации защищаемых данных. Одним из ключевых призывов специалистов является отказ от стандартизации Kyber-512 из-за недостаточной доказательной базы безопасности и неточностей в расчетах. Вместо этого рекомендуется сосредоточиться на более надежных и гибких алгоритмах, таких как различные варианты NTRU, которые обладают более понятной структурой безопасности, доказанными свойствами и разнообразием параметров.
Общий вывод из сложившейся ситуации — необходимость более тщательного, открытого и независимого анализа безопасности криптосистем, особенно с учетом быстро меняющейся обстановки в области постквантовой криптографии. Стандартизация должна опираться не на ошибочные и математически некорректные выкладки, а на прозрачные и воспроизводимые процедуры с участием международного сообщества экспертов. Важно отметить, что ошибки такого масштаба показывают, сколь непростой и рискованный путь развития стандартов в области криптографии. Невнимание к фундаментальным деталям и желание удовлетворить определённые политические или коммерческие интересы могут привести к серьёзным изъянам и поставить под угрозу безопасность сотен миллионов пользователей. Для российских и международных специалистов критически важно внимательно изучать все аспекты уязвимостей и оценок безопасности, не просто полагаться на авторитеты и официальные заявления.
История с Kyber-512 еще раз подчеркивает, что математическая строгость — это основа доверия в криптографии. В ближайшем будущем предстоит провести более глубокие исследования и выработать новые методы оценки затрат на атаки с учетом всех современных реалий вычислений и памяти. Только такие обстоятельства позволят гарантировать действительно надежную защиту и построить стандарты, способные противостоять появлению квантовых компьютеров и другим вызовам. Благодаря вниманию к подробностям и критическому подходу к оценкам удастся преодолеть текущие проблемы и сделать следующий этап криптографической эволюции более безопасным и прогнозируемым.
