dxdt.ru: занимательный интернет-журнал

В ML-KEM (ранее – Kyber) возможен вариант, когда корректно полученные сторонами секреты не совпадут. В стандарте NIST это называется Decapsulation failure. То есть, сами криптографические примитивы, составляющие ML-KEM, срабатывают всегда – выводят 256-битное значение. Но с некоторой (чрезвычайно малой) вероятностью принимающая сторона, расшифровывающая секрет, может получить значение, не совпадающее с тем, которое отправлено. “Чрезвычайно малая вероятность” тут означает 2^(-164.8). Выглядит более чем несущественным параметром. Но рассматривать сам факт наличия такой “погрешности” можно с разных сторон.

Многие криптографические алгоритмы хороши тем, что, математически, там никакой ошибки быть не может: если шаги выполнены верно, то и результат всегда строго совпадает. Это один из фундаментальных принципов использования алгебры в криптографии: нельзя проверить все 2^256 элементов и записать их в один массив, но можно использовать обозримые свойства структуры группы, чтобы гарантировать, что результаты операций с любыми сочетаниями этих 2^256 элементов не разойдутся.

Строго говоря, и в ML-KEM упомянутая “погрешность” оказывается в ряду заданных результатов алгоритма, просто, определяется она на другом уровне. Более того, при практической реализации алгоритмов, не имеющих встроенных “погрешностей”, эти самые погрешности постоянно возникают и из-за ошибок в программах, и даже из-за ошибок в работе оборудования. Особенно, если говорить о вероятностях порядка 2^(-165) – казалось бы, тут и без всяких Rowhammer какой-нибудь залётный нейтрон может вызвать реакцию, которая переключит пару битов в модуле памяти. Нейтрон, конечно, может помешать, но это будет не то же самое, что и внесение обязательного сбоя непосредственно в логику алгоритма.

Адрес записки: https://dxdt.ru/2024/12/25/14487/