A vulnerability has been discovered in the Kyber encryption algorithm, which won the competition for quantum-resistant cryptographic algorithms. This vulnerability allows for side-channel attacks to reconstruct secret keys based on the timing of operations during the decryption of ciphertext provided by an attacker. The issue 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, dubbed KyberSlash, lies in the use of a division operation during message decoding: "t = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;", where the dividend contains the secret value "t" of type "double", while the divisor is the well-known public value KYBER_Q. The problem is that the timing of the division operation is not constant and in various environments, the number of CPU cycles executed for division depends on the input data. Thus, by measuring the timing of operations, one can infer the nature of the data used during the division.
Daniel Bernstein, a well-known expert in the field of cryptography, has successfully prepared a working demonstration of the possibility of mounting a practical attack. In two out of three experiments conducted on a Raspberry Pi 2 board, he was able to fully reconstruct the Kyber-512 private key based on the timing measurements of the data decoding. The method can also be adapted for Kyber-768 and Kyber-1024 keys. For a successful attack, the ciphertext provided by the attacker must be processed using the same key pair, and the execution time of the operation must be accurately measurable.
Another leak (KyberSlash2) has been identified in some libraries, which also arises from the use of a secret value during division. The differences from the first variant boil down to the call during the encryption stage (in the poly_compress and polyvec_compress functions), rather than during decryption. The second variant may be useful for an attack only in cases where the procedure is used in re-encryption operations, where the output of the ciphertext is considered confidential.
The vulnerability has already been fixed in the following 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 (January 8).
Libraries initially unaffected 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 unfixed in the following libraries:
- antontutoveanu/crystals-kyber-javascript,
- Argyle-Software/kyber,
- debian/src/liboqs/unstable/src/kem/kyber,
- kudelskisecurity/crystals-go,
- mupq/pqm4/crypto_kem/kyber* (only one variant of the vulnerability was fixed on December 20),
- PQClean/PQClean/crypto_kem/kyber*/aarch64,
- PQClean/PQClean/crypto_kem/kyber*/clean,
- randombit/botan (only one variant of the vulnerability was fixed on December 20),
- rustpq/pqcrypto/pqcrypto-kyber (a fix was added on January 5 in libsignal, but the vulnerability in pqcrypto-kyber itself is still not fixed).
Source: opennet.ru
