Paper 2026/2918
Nonlinear Invariant Attacks on Full CRAFT: Chosen-Tweak Key Recovery
Abstract
A nonlinear invariant is a Boolean function of the state that every round preserves, up to a constant, for a class of keys. It then relates plaintext and ciphertext with correlation one, whatever the number of rounds. Finding one is in general a problem about the whole state. We study a family of invariants of the tweakable block cipher CRAFT for which this problem splits into independent pieces. Each function reads half of the state linearly and the other half through components of the S-box, one nibble at a time, so that the condition for a round to preserve it becomes one small condition per S-box, read once from the algebraic normal form of the S-box. The family can therefore be analysed by hand and enumerated by computer. The simplest member uses a single quadratic component of the S-box and survives all thirty-two rounds on a class of $2^{108}$ keys. Allowing cubic components and a pattern that alternates between even and odd rounds yields an invariant that survives all thirty-two rounds for half of all keys, with suitably chosen tweaks. Both classes are determined exactly, and a computer classification shows that none in the family is larger. Since the conditions are periodic with the tweakey, these invariants pass any number of rounds, not only the thirty-two of CRAFT, so increasing the round count would not remove them. The invariants give key recovery. Almost every key of CRAFT satisfies a great many of them at once, and the classification yields a library of hundreds of thousands. Running the library against an unknown key and collecting the linear relations each invariant reveals recovers, for essentially every key, an average of 61.3 of the 64 low key bits with about $2^{14.5}$ chosen-tweak queries and negligible time. Over a sample of 5000 random keys every one was broken, the remaining search staying below the 124-bit security claim in every case. All programs and data that reproduce these results are available in a public repository.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- nonlinear invariantCRAFTweak keystweakable block cipherskey recovery
- Contact author(s)
- math @ robertocivino it
- History
- 2026-11-21: last of 2 revisions
- 2026-11-16: received
- See all versions
- Short URL
- https://ia.cr/2026/2918
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2918,
author = {Roberto Civino},
title = {Nonlinear Invariant Attacks on Full {CRAFT}: Chosen-Tweak Key Recovery},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2918},
year = {2026},
url = {https://eprint.iacr.org/2026/2918}
}