A Kyber encryption algorithm implementation, which won the competition for cryptographic algorithms resistant to attacks by quantum computers, has been found to have a vulnerability that allows attacks through side channels to recreate secret keys based on measuring the time of operations during the decryption of ciphertext provided by the attacker. The problem affects both the reference implementation of the CRYSTALS-Kyber KEM key encapsulation mechanism and many third-party encryption libraries supporting Kyber, including the pqcrypto library used in the Signal messenger.
The essence of the vulnerability, which has been codenamed KyberSlash, lies in the use of a division operation during the message decoding process: 't = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;'. Here, the dividend contains the secret value 't' of type 'double', while the divisor is the well-known public value KYBER_Q. The issue is that the time taken for the division operation is not constant and varies based on the input data, causing the number of CPU cycles executed for division to depend on it. Thus, by analyzing the time variations of these operations, information about the nature of the data used during division can be inferred.
Daniel Bernstein, a renowned expert in cryptography, managed to prepare a working demonstration proving the possibility of executing an attack in practice. In two of the three experiments conducted by running the code on a Raspberry Pi 2 board, it was possible to fully recreate the Kyber-512 private key based on the time measurements of data decoding. This method can also be adapted for the Kyber-768 and Kyber-1024 keys. For a successful attack, it is necessary that the ciphertext provided by the attacker be processed using the same key pair, and that the execution time of the operation can be measured accurately.
Néhány könyvtárban újabb adatszivárgás (KyberSlash2) került felfedezésre, amely szintén a titkos értékek felhasználásából adódik osztási műveletek során. A különbségek az első variánstól abban állnak, hogy a titkosítási szakaszban (a poly_compress és a polyvec_compress funkciókban) történik a hívás, nem pedig a dekódolás során. A második variáns hasznos lehet a támadások során, csak abban az esetben, ha az eljárást újra titkosítási műveletekben használják, ahol az elkészített titkos szöveg bizalmasnak számít.
A sebezhetőséget már eltávolították a könyvtárakból:
- zig/lib/std/crypto/kyber_d00.zig (december 22.),
- pq-crystals/kyber/ref (december 30.),
- symbolicsoft/kyber-k2so (december 19.),
- cloudflare/circl (január 8.),
- aws/aws-lc/crypto/kyber (január 4.),
- liboqs/src/kem/kyber (január 8.).
A kezdetben nem sebezhető könyvtárak:
- 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.
A sebezhetőség továbbra is javítatlan a következő könyvtárakban:
- antontutoveanu/crystals-kyber-javascript,
- Argyle-Software/kyber,
- debian/src/liboqs/unstable/src/kem/kyber,
- kudelskisecurity/crystals-go,
- mupq/pqm4/crypto_kem/kyber* (december 20-án csak 1 variánst javítottak),
- PQClean/PQClean/crypto_kem/kyber*/aarch64,
- PQClean/PQClean/crypto_kem/kyber*/clean,
- randombit/botan (december 20-án csak 1 variánst javítottak),
- rustpq/pqcrypto/pqcrypto-kyber (január 5-én a javítást hozzáadták a libsignal-hez, de a pqcrypto-kyber magában még nem javított sebezhetőséget).
Forrás: opennet.ru
