Уязвимост в реализациите на постквантовия алгоритъм за криптиране Kyber

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

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

Даниел Бернщейн (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