Уязвимость в реализациях постквантового алгоритма шифрования Kyber

В реализации алгоритма шифрования Kyber, победившего на конкурсе криптоалгоритмов, стойких к подбору на квантовом компьютере, выявлена уязвимость, допускающая проведение атак по сторонним каналам для воссоздания секретных ключей на основе измерения времени операций во время расшифровки предоставленного атакующим шифротекста. Проблема затрагивает как эталонную реализацию механизма инкапсуляции ключей CRYSTALS-Kyber KEM, так и многие сторонние библиотеки шифрования с поддержкой Kyber, в том числе библиотеку pqcrypto применяемую в мессенджере Signal.

Суть уязвимости, которая получила кодовое имя KyberSlash, в использовании в процессе декодирования сообщения операции деления «t = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;», в которой делимое содержит секретное значение «t» с типом «double», а делитель общеизвестное публичное значение KYBER_Q. Проблема в том, что время операции деления не является константой и в различных окружениях число выполняемых для деления циклов CPU зависит от входных данных. Таким образом, на основании изменения времени операций можно получить представление о характере используемых при делении данных.

Дэниэл Бернштейн (Daniel J. Bernstein), известный эксперт в области криптографии, сумел подготовить рабочую демонстрацию доказательства возможности совершения атаки на практике. В двух из трёх проведённых экспериментов при выполнении кода на плате Raspberry Pi 2 удалось полностью воссоздать закрытый ключ Kyber-512 на основании измерения времени декодирования данных. Метод также может быть адаптирован для ключей Kyber-768 и Kyber-1024. Для успешного проведения атаки необходимо, чтобы задаваемый атакующим шифротекст обрабатывался с использованием одной и той же пары ключей и чтобы можно было точно измерить время выполнения операции.

В некоторых библиотеках выявлена ещё одна утечка (KyberSlash2), которая также возникает из-за использования секретного значения при выполнении деления. Отличия от первого варианта сводятся к вызову на стадии шифрования (в функциях poly_compress и polyvec_compress), а не во время расшифровки. При этом второй вариант может оказаться полезным для атаки только в случаях использования процедуры в операциях повторного шифрования, в которых вывод зашифрованного текста считается конфиденциальным.

Уязвимость уже устранена в библиотеках:

• zig/lib/std/crypto/kyber_d00.zig (22 декабря),
• pq-crystals/kyber/ref (30 декабря),
• symbolicsoft/kyber-k2so (19 декабря),
• cloudflare/circl (8 января),
• aws/aws-lc/crypto/kyber (4 января),
• liboqs/src/kem/kyber (8 января).

Библиотеки, изначально не подверженные уязвимости:

• boringssl/crypto/kyber,
• filippo.io/mlkem768,
• formosa-crypto/libjade/tree/main/src/crypto_kem,
• kyber/common/amd64/avx2,
• formosa-crypto/libjade/tree/main/src/crypto_kem/kyber/common/amd64/ref,
• pq-crystals/kyber/avx2,
• pqclean/crypto_kem/kyber*/avx2.

Уязвимость остаётся неисправленной в библиотеках:

• antontutoveanu/crystals-kyber-javascript,
• Argyle-Software/kyber,
• debian/src/liboqs/unstable/src/kem/kyber,
• kudelskisecurity/crystals-go,
• mupq/pqm4/crypto_kem/kyber* (20 декабря исправлен только 1 вариант уязвимости),
• PQClean/PQClean/crypto_kem/kyber*/aarch64,
• PQClean/PQClean/crypto_kem/kyber*/clean,
• randombit/botan (20 декабря исправлен только 1 вариант уязвимости),
• rustpq/pqcrypto/pqcrypto-kyber (5 января исправление добавлено в libsignal, но в самом pqcrypto-kyber уязвимость пока не исправлена).

Источник: opennet.ru