What Happened
Researchers using circle-linear cryptanalysis on the CRAFT lightweight block cipher found a significant weakness: 2^108 keys, about one in every 37 trillion trillion possible keys, show a detectable pattern at fourteen rounds. The squared correlation was 2^−44, stronger than the cipher's known linear hull attack, which affects all keys equally at 2^−62.12.
This isn't just theoretical. The team tested both the weak-key class and random keys. The weak keys behaved as predicted, while the random keys showed no correlation.
Timeline
The attack builds on Beyne's geometric framework for linear cryptanalysis over finite abelian groups, using a binary bibrace structure. Here's the analysis process:
Initial discovery: The Midori/CRAFT S-box has four probability-one relations in the bibrace group structure, forming a subgroup that the S-box preserves.
Trail construction: Within this subgroup, masks propagate deterministically. Researchers solved the minimum weight codeword problem through complete enumeration, finding optimal trails that restrict valid keys to a weak-key class.
Key class calculation: By analyzing the diffusion layer and key addition together, the team identified a weak-key class larger than expected. CRAFT's round constants don't restrict the attack.
Validation: At eighteen rounds, the distinguisher still works. At fourteen rounds, the correlation advantage is significant enough for practical exploitation within the weak-key class.
Which Controls Failed or Were Missing
Inadequate key space coverage analysis: The cipher's security evaluation assumed uniform strength across the key space. There was no mechanism to detect weak-key classes during key generation.
S-box design oversight: The S-box's probability-one relations within the bibrace group structure went undetected. Traditional linear cryptanalysis wouldn't reveal these properties.
Diffusion layer analysis gap: Evaluating the diffusion layer and key addition separately missed the combined effect that expands the vulnerable key class.
Round constant ineffectiveness: The round constants don't protect against this attack. Their values don't restrict the weak-key class or disrupt mask propagation.
What the Standards Require
FIPS 140-3 mandates that cryptographic modules use approved algorithms. For block ciphers, this means algorithms that have undergone rigorous cryptanalysis.
NIST SP 800-108 assumes the underlying cipher provides uniform security. Weak-key classes compromise key derivation functions built on top.
The ISO/IEC 18033-3 standard requires that security claims hold for all keys. A cipher with 2^108 weak keys out of 2^128 total keys fails to meet its security level claims for a small percentage of the key space. That sounds negligible until you're the payment processor using one of those keys.
PCI DSS Requirement 3.5.1 demands strong cryptography for protecting stored cardholder data. If your encryption key falls into a weak-key class, you're not meeting the requirement even if you're using an approved algorithm.
Lessons and Action Items
Implement weak-key detection at key generation. Your Key Encryption Key (KEK) generation process should test candidate keys against known weak-key classes before deployment. For CRAFT, you need a function to check if a proposed key is within the 2^108-key vulnerable class. This adds computational overhead but eliminates the risk of deploying a weak key.
Diversify cipher usage across your architecture. Don't rely on a single cipher for all operations. If CRAFT protects your tokenization vault and a weak-key class is discovered, you've got a single point of failure. Use AES-256 for cardholder data encryption, a different algorithm for token generation, and another for key wrapping. Cryptanalytic advances against one algorithm won't compromise your entire system.
Rekey based on cryptanalytic developments. When new attack methods emerge, even if they only affect a subset of keys, trigger a rekey evaluation. Your current key might be fine, but you need a process to verify that and document the decision.
Test your cryptographic implementations against academic literature. The circle-linear cryptanalysis method is in published research. Your security team should monitor cryptography conferences and journals, maintain a list of algorithms you use, and evaluate new attacks against your systems. This isn't a one-time audit; it's ongoing threat intelligence for your cryptographic stack.
Document your key space assumptions. Your risk assessment should state: "We assume uniform security across the entire key space for algorithm X." When that assumption breaks, you know which systems need reevaluation. Without documentation, you're guessing about your exposure after a new attack publishes.
The CRAFT weak-key class shows that cryptographic security isn't binary. An algorithm can be secure for most keys and weak for others. Your key management program needs to account for this reality, not assume it away.
