Sårbarhet i implementationer av den post-kvantiska krypteringsalgoritmen Kyber

I implementeringen av Kyber, en krypteringsalgoritm som vann tävlingen om kvantmotståndskraftiga kryptografier, har en sårbarhet upptäckts som möjliggör attacker genom externa kanaler för återskapande av hemliga nycklar baserat på tidsmätningar av operationer under avkodning av den krypterade text som tillhandahålls av angriparen. Problemet påverkar både den referensimplementering av nyckelinpackningsmekanismen CRYSTALS-Kyber KEM och många tredjeparts kryptografibibliotek med stöd för Kyber, inklusive biblioteket pqcrypto som används i meddelandeprogrammet Signal.

Sårbarhetens kärna, som har kodnamnet KyberSlash, ligger i användningen av delningsoperationen "t = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;" under avkodning av meddelandet, där t innehåller ett hemligt värde av typen "double" och divisorn är det allmänt kända publika värdet KYBER_Q. Problemet är att tiden för delningsoperationen inte är konstant och antalet CPU-cykler som utförs för delningen beror på ingångsvärdena i olika miljöer. Därför kan man, baserat på variationerna i operationstider, få en uppfattning om datan som används under delningen.

Daniel Bernstein, en erkänd expert inom kryptografi, lyckades förbereda en fungerande demonstration av möjligheten att genomföra en attack i praktiken. I två av tre genomförda experiment, när koden kördes på ett Raspberry Pi 2, lyckades man helt återskapa den hemliga nyckeln Kyber-512 baserat på tidsmätningar av datadekodning. Metoden kan också anpassas för nycklarna Kyber-768 och Kyber-1024. För att lyckas med attacken krävs att den krypterade texten som angriparen ställer in behandlas med samma nyckelpar och att man kan mäta utförandetiden exakt.

I vissa bibliotek har ytterligare en läcka identifierats (KyberSlash2), som också uppstår på grund av användning av ett hemligt värde vid division. Skillnaderna från den första varianten handlar om anrop vid kryptering (i funktionerna poly_compress och polyvec_compress), och inte vid dekryptering. Den andra varianten kan dock visa sig vara användbar för attacker endast i fall när proceduren används i operationer för återkryptering där utdata av den krypterade texten betraktas som konfidentiell.

Sårbarheten har redan åtgärdats i biblioteken:

• zig/lib/std/crypto/kyber_d00.zig (22 december),
• pq-crystals/kyber/ref (30 december),
• symbolicsoft/kyber-k2so (19 december),
• cloudflare/circl (8 januari),
• aws/aws-lc/crypto/kyber (4 januari),
• liboqs/src/kem/kyber (8 januari).

Bibliotek som ursprungligen inte var utsatta för sårbarheten:

• 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.

Sårbarheten förblir oåtgärdad i biblioteken:

• antontutoveanu/crystals-kyber-javascript,
• Argyle-Software/kyber,
• debian/src/liboqs/unstable/src/kem/kyber,
• kudelskisecurity/crystals-go,
• mupq/pqm4/crypto_kem/kyber* (20 december åtgärdades endast 1 variant av sårbarheten),
• PQClean/PQClean/crypto_kem/kyber*/aarch64,
• PQClean/PQClean/crypto_kem/kyber*/clean,
• randombit/botan (20 december åtgärdades endast 1 variant av sårbarheten),
• rustpq/pqcrypto/pqcrypto-kyber (5 januari fix lades till i libsignal, men i själva pqcrypto-kyber är sårbarheten hittills inte åtgärdad).

Källa: opennet.ru