Paper 2026/2918

Nonlinear Invariant Attacks on Full CRAFT: Chosen-Tweak Key Recovery

Roberto Civino
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.