Kyber Cryptanalysis
Attacks against CRYSTALS-Kyber.
Last updated
Attacks against CRYSTALS-Kyber.
Last updated
BKW-type and Linearization Attacks: Not applicable due to the specific nature of Kyber’s security assumptions and the number of LWE samples available.
BKZ Attacks: Relevant for attacking Kyber; involves solving the Small Vector Problem (SVP) using lattice reduction techniques.
Primal Attacks: Involve creating a unique smallest vector problem (uSVP) instance and solving it using BKZ algorithms.
Security Estimates: Originally estimated at 151.5 (Kyber 512). Updated estimates suggest reduced security levels: 138.2 with sieve costs, and 137.5 with the G6K model.
Security Threshold: Required security level is at least 143, raising concerns about Kyber’s parameter effectiveness.
KECCAK-Based Components: Kyber uses KECCAK-based primitives like SHAKE and SHA3. Attacks would need to compromise KECCAK or the random-oracle model.
Attack Viability: Current understanding suggests that attacks on Kyber’s symmetric primitives are unlikely to be successful.
Design Defenses:
"Against-All-Authority" Approach: Each public key has a regenerated matrix A, preventing multiple keys from being compromised if one key is exposed.
Public Key Hashing: Hashing the public key into a pre-key K and a coin r to protect against precomputed attacks.
Effectiveness: These design choices aim to defend against multi-target attacks, though no formal claims are made regarding this scenario.
Chosen Ciphertext Attacks: Adversaries create ciphertexts to trigger decryption failures, which can potentially leak information about the secret key.
Fujisaki-Okamoto (FO) Transform: Used by Kyber to reject invalid ciphertexts and prevent secret key leakage.
Valid Ciphertext Attacks: Failures can occur due to randomness issues in error term generation, potentially revealing information about the secret key.
Failure Boosting: Techniques to improve attack viability, especially under minimal multi-target protection and assuming quantum computing capabilities.
Weak Ciphertext Attacks: Collect failures to determine error positions and simplify the LWE problem. The probability of valid ciphertext failure is very low, making this attack impractical.
Weak Key Attacks: Focus on identifying keys that cause frequent decryption failures. Steps involve precomputation, querying multiple users, and statistical analysis to recover secret keys. Attacks can be adjusted for Kyber’s uneven distribution in noise and error terms.
Timing Attack Overview: Exploits variations in execution time to infer secret keys.
Kyber's Resistance: Kyber is designed to be time-constant, avoiding timing leakage from conditional branches and table look-ups. It uses small 16-bit inputs which reduces the risk from non-time-constant multipliers.
Modular Reductions: Use of Montgomery and Barrett reductions to mitigate timing leakage through modular reductions.
SASCA Overview: Uses single-trace attacks by profiling side-channel leakage from operations and applying belief propagation to recover secret keys.
Targeting NTT: SASCA can exploit Non-Uniform Time Transformation (NTT) operations to recover keys by profiling and template matching.
Targeting KECCAK: SASCA can also target KECCAK operations used in Kyber for key generation and encapsulation. Attacks focus on sequential KECCAK operations.
Encoding Process: Involves hashing, generating keys and seeds, and using SHAKE-256 for key generation.
Sim et al. Attack: Targets encoding by analyzing power consumption related to masking values. Success achieved by classifying power traces into two groups based on mask values and recovering messages.
AI-based Attacks: AI techniques are used to break higher-order masked implementations of Kyber. Deep learning models are trained to recover messages by leveraging cyclic rotations of the intercepted message to increase leakage.
Recursive Learning: Applied for training AI models on higher-order masked implementations by extending lower-order models.
LDPC Overview: Uses sparse parity-check codes to recover secret coefficients from a single side-channel measurement. Benefits include source compression and error correction.
Application to Kyber: Framework improves upon basic attacks by combining secret coefficient recovery with LDPC codes, requiring fewer traces for effective recovery.
Timing Attacks: Exploit timing variations, mitigated by constant-time implementations.
SASCA: Uses profiling and belief propagation for single-trace attacks on operations like NTT and KECCAK.
Message Encoding Attacks: Analyze power consumption variations related to masking.
Deep Learning: Employs AI to handle higher-order masking attacks and uses cyclic rotations to enhance recovery.
LDPC Codes: Utilize sparse codes to improve the efficiency of side-channel attacks and reduce trace requirements.
Concept: Exploits differences in electromagnetic emissions based on the bit values being processed.
Application: Used to retrieve the secret key or message from Kyber by manipulating ciphertext parts and analyzing emission differences.
Procedure:
Set specific bits in ciphertext parts uuu and vvv to isolate a single bit of the key.
Collect traces and analyze emissions to determine the value of the secret key bit.
Repeat for all bits to recover the entire key.
Results:
For Kyber512, 2560 traces are needed with a high success rate (99%) and an average recovery time of about 11 minutes.
Countermeasures: Masking complete decryption can be effective but is performance-costly. Improvements include parallelizing attacks and targeting different Kyber procedures.
Concept: Uses power consumption variations during polynomial multiplication algorithms to deduce secret values.
Application: Effective on Kyber's decapsulation process, especially for operations like base multiplication and Number Transform Theory (NTT).
Procedure:
Collect power samples with known inputs and guess secret values.
Compute intermediate values and correlate Hamming weight with power traces.
Find the secret value with the highest correlation.
Results:
With 50 to 100 ciphertexts, the probability of key recovery exceeds 99%.
Countermeasures: Masking can be used but results in a performance slowdown. Alternatives include using ephemeral settings or regenerating secret keys frequently.
EM Attack: Requires delicate setup but can be highly effective. Countermeasures involve masking but can be costly.
CPA: Effective with a moderate number of ciphertexts. Defense strategies include ephemeral key settings or frequent key regeneration.
Concept: Intentionally introducing faults during decryption to cause errors that can reveal secret information.
Impact on Kyber: Faults in Kyber's FO transform can propagate errors through the system, making it possible to deduce secret keys or messages.
Concept: A fault attack that generates and solves a system of inequalities over the secret key by faulting operations in a cryptographic algorithm.
Procedure:
Faults are introduced in specific operations (e.g., t1, t2, t3, A1, A2).
The attack leverages the system of inequalities generated by faults to deduce the secret key.
Roulette attacks on Kyber focus on the decapsulation process and use assembly-level operations and specific components like the double GS butterfly in the INTT layer.
Results:
For 5 out of 9 instruction skips, the output is uniformly distributed, making it ideal for attack.
Effective even against masking and blinding techniques, though countermeasures may slow down the attack.
Delvaux's implementation of Roulette on a ChipWhisperer board with clock glitches took around 5 days for an unoptimized implementation, with 20 fault injections required for a successful attack.
Countermeasures:
Masking and blinding techniques are less effective as they require adaptation to fault models.
Delvaux’s linear system solver improves computational efficiency and error tolerance.
Concept: Focuses on recovering secret keys from decryption faults with high error tolerance.
Procedure:
Uses belief propagation (BP) to recover key bits and integrate partially recovered data into a lattice problem.
Employs techniques like Kannan’s embedding and lattice reduction (e.g., BKZ) to handle LWE problems.
Integrates recovered coefficients into LWE equations to reduce dimensionality and improve recovery chances.
Results:
Compared to Roulette, this method reduces the number of correct inequalities needed by almost half.
Faster and effective in scenarios with higher error tolerance, though it might not outperform Roulette in all aspects.
Countermeasures:
Techniques such as ciphertext-filtering and using additional computational resources can enhance performance.
Ongoing Improvement: Attacks and defenses against Kyber and lattice-based cryptography will continue to evolve.
Research Incentive: Encourages researchers and developers to enhance defenses and explore new strategies for improving cryptographic security in the post-quantum era.