Sårbarhet i implementeringar av post-kvantkrypteringsalgoritmen Kyber

En sårbarhet har identifierats i implementeringen av Kyber-krypteringsalgoritmen, som vann tävlingen om kvantresistenta kryptografiska algoritmer, vilket gör det möjligt för sidokanalattacker att rekonstruera hemliga nycklar baserat på att mäta tiden för operationer under dekryptering av chiffertexten som tillhandahålls av angriparen. Problemet påverkar både referensimplementeringen av nyckelinkapslingsmekanismen CRYSTALS-Kyber KEM och många tredjepartskrypteringsbibliotek med Kyber-stöd, inklusive pqcrypto-biblioteket som används i Signal messenger.

Kärnan i sårbarheten, som fått kodnamnet KyberSlash, ligger i användningen av divisionsoperationen "t = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;". i processen att avkoda meddelandet, där dividenden innehåller det hemliga värdet "t" av typen "dubbel", och delaren är det välkända offentliga värdet KYBER_Q. Problemet är att tiden för divisionsoperationen inte är konstant och i olika miljöer beror antalet CPU-cykler som utförs för division på indata. Således, baserat på förändringen i operationstid, kan man få en uppfattning om vilken typ av data som används i uppdelningen.

Daniel J. Bernstein, en välrenommerad kryptografiexpert, har lyckats producera en fungerande demonstration av attackens konceptuella bevis. I två av de tre experiment som utfördes, när koden kördes på ett Raspberry Pi 2-kort, var det möjligt att helt återskapa den privata Kyber-512-nyckeln baserat på mätningarna av dataavkodningstiden. Metoden kan även anpassas för Kyber-768- och Kyber-1024-nycklar. För att attacken ska lyckas är det nödvändigt att den chiffertext som angriparen tillhandahåller bearbetas med samma nyckelpar och att operationens exekveringstid kan mätas korrekt.

En annan läcka (KyberSlash2) har upptäckts i vissa bibliotek, vilken också uppstår på grund av användningen av ett hemligt värde vid division. Skillnaderna från det första alternativet ligger i anropet i krypteringsstadiet (i funktionerna poly_compress och polyvec_compress), och inte under dekryptering. Det andra alternativet kan dock vara användbart för attacker endast i fall där proceduren används vid omkrypteringsoperationer, där utdata från den krypterade texten anses vara konfidentiell.

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

• zig/lib/std/crypto/kyber_d00.zig (22 december),
• pq-kristaller/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 inte initialt är sårbara:

• boringssl/krypto/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-kristaller/kyber/avx2,
• pqclean/crypto_kem/kyber*/avx2.

Sårbarheten är fortfarande ouppdaterad i biblioteken:

• antontutoveanu/kristaller-kyber-javascript,
• Argyle-programvara/kyber,
• debian/src/liboqs/instabil/src/kem/kyber,
• kudelskisecurity/crystals-go,
• mupq/pqm4/crypto_kem/kyber* (endast 20 sårbarhetsvariant åtgärdad den 1 december),
• PQClean/PQClean/crypto_kem/kyber*/aarch64,
• PQClean/PQClean/crypto_kem/kyber*/clean,
• randombit/botan (endast 20 sårbarhetsvariant åtgärdad den 1 december),
• rustpq/pqcrypto/pqcrypto-kyber (den 5 januari lades korrigeringen till i libsignal, men sårbarheten är ännu inte åtgärdad i själva pqcrypto-kyber).

Källa: opennet.ru