In the implementation of the Kyber encryption algorithm, which won the competition of cryptographic algorithms resistant to brute force on a quantum computer, a vulnerability was identified that allows side-channel attacks to recreate secret keys based on measuring the time of operations during decryption of the ciphertext provided by the attacker. The problem affects both the reference implementation of the CRYSTALS-Kyber KEM key encapsulation mechanism and many third-party Kyber-enabled encryption libraries, including the pqcrypto library used in the Signal messenger.
The essence of the vulnerability, which received the code name KyberSlash, is in the use of the division operation βt = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;β in the process of decoding a message, in which the dividend contains the secret value βtβ with type βdoubleβ, and the divisor is the well-known public value KYBER_Q. The problem is that the time of a division operation is not constant, and in different environments the number of CPU cycles performed for division depends on the input data. Thus, based on changes in operation times, one can get an idea of ββthe nature of the data used in division.
Daniel J. Bernstein, a well-known expert in the field of cryptography, was able to prepare a working demonstration of proof that the attack could be carried out in practice. In two of the three experiments conducted, when running code on the Raspberry Pi 2 board, it was possible to completely recreate the Kyber-512 private key based on measuring the data decoding time. The method can also be adapted for Kyber-768 and Kyber-1024 keys. To successfully carry out an attack, it is necessary that the ciphertext specified by the attacker be processed using the same key pair and that the execution time of the operation can be accurately measured.
Another leak (KyberSlash2) has been identified in some libraries, which also occurs due to the use of a secret value when performing division. The differences from the first option come down to the call at the encryption stage (in the poly_compress and polyvec_compress functions), and not during decryption. However, the second option may be useful for an attack only in cases where the procedure is used in re-encryption operations in which the output of the ciphertext is considered confidential.
The vulnerability has already been fixed in the libraries:
- zig/lib/std/crypto/kyber_d00.zig (December 22),
- pq-crystals/kyber/ref (December 30),
- symbolicsoft/kyber-k2so (December 19),
- cloudflare/circl (January 8),
- aws/aws-lc/crypto/kyber (January 4),
- liboqs/src/kem/kyber (8 January).
Libraries not initially affected by the vulnerability:
- 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.
The vulnerability remains unpatched in the libraries:
- antontutoveanu/crystals-kyber-javascript,
- Argyle-Software/kyber,
- debian/src/liboqs/unstable/src/kem/kyber,
- kudelskisecurity/crystals-go,
- mupq/pqm4/crypto_kem/kyber* (On December 20, only 1 version of the vulnerability was fixed),
- PQClean/PQClean/crypto_kem/kyber*/aarch64,
- PQClean/PQClean/crypto_kem/kyber*/clean,
- randombit/botan (On December 20, only 1 vulnerability was fixed),
- rustpq/pqcrypto/pqcrypto-kyber (a fix was added to libsignal on January 5, but the vulnerability has not yet been fixed in pqcrypto-kyber itself).
Source: opennet.ru