В лаборатории криптографии российской ИТ-компании «Криптонит» (входит в «ИКС Холдинг») разработали новый алгоритм атаки на постквантовые криптосистемы, которые строятся на основе кодов, исправляющих ошибки. Новый алгоритм позволяет уточнить оценку защищённости подобных криптографических механизмов. В некоторых случаях он работает с меньшими вычислительными затратами и позволяет выявлять уязвимости на стадии проектирования, ещё до начала дорогостоящих тестов.
Любой криптографический механизм нуждается в оценке стойкости: необходимо понимать, сколько вычислительных операций потребуется злоумышленнику для взлома. С приближением эры квантовых компьютеров эта задача становится критичной для классической криптографии, поэтому разрабатываются постквантовые схемы, устойчивые к атакам с использованием новейших технологий. Значительная часть таких перспективных алгоритмов опирается на теорию кодов, исправляющих ошибки, например, алгоритм Мак-Элиса. От их надёжности напрямую зависит гражданская криптография, которая обеспечивает сохранность банковских переводов пользователей и защищает деньги в процессе каждой транзакции. Злоумышленник с мощным квантовым компьютером сможет подделывать цифровые подписи, перехватывать банковские транзакции и любые другие данные, которые передаются через интернет и в других сетях связи.
Суть нового метода атаки заключается в поиске скрытых закономерностей внутри линейных кодов. Криптограф Иван Чижов, заместитель руководителя лаборатории криптографии по научной работе в компании «Криптонит», сосредоточился на анализе квадратичных форм, т.е. уравнений второй степени, которые обращаются в ноль на столбцах порождающей матрицы кода. Особую опасность представляют составные квадратичные формы: те, что распадаются в произведение двух более простых линейных уравнений. Если атакующему удаётся найти в коде такие составные формы, он получает рычаг для потенциального взлома криптосистемы. Иван не только предложил алгоритм поиска этих «слабых мест», но и математически описал условия, при которых они возникают.
«Мы разработали способ взлома, способный стать угрозой для неправильно спроектированных постквантовых криптографических механизмов, — пояснил Иван Чижов. — Сейчас вычислительная сложность такого нападения на стандартизированные параметры астрономически высока, и мгновенного взлома не происходит. Однако сам факт существования метода заставляет пересматривать требования к защите, чтобы обеспечить запас прочности».
Практическая ценность работы заключается не только в обнаружении уязвимостей, но и в создании условий для их предотвращения. Как отмечает автор, исследование позволяет сократить затраты на стандартизацию целого семейства постквантовых алгоритмов, математически выявить в них некоторые потенциальные уязвимости ещё на ранней стадии и точнее подобрать оптимальные параметры постквантовых схем шифрования. Это означает, что разработчики смогут отсеивать заведомо слабые варианты кодов ещё до начала дорогостоящего практического анализа.
Метод поможет сделать личные, финансовые и медицинские данные более защищенными в эпоху квантовых вычислений.