TL;DR
This paper introduces TWEAKEY, a novel framework for designing tweakable block ciphers that unifies the concepts of key schedules and tweak inputs. It presents STK, a subclass of TWEAKEY, which offers efficient and secure designs like Deoxys-BC and Joltik-BC, and also shows how to efficiently tweak the AES block cipher with Kiasu-BC.
What Problem Does This Paper Address?
Block ciphers are fundamental building blocks in cryptography, but their security is often analyzed under the assumption of a fixed, secret key. However, in many real-world applications, such as disk encryption, the block cipher needs to be randomized with an additional public input called a "tweak" without changing the secret key. Existing methods for creating tweakable block ciphers often fall short in either efficiency, security (especially beyond the birthday bound), or ease of analysis, particularly when dealing with related-key or related-tweak attacks. This paper aims to bridge this gap by proposing a unified framework, TWEAKEY, that simplifies the design and analysis of tweakable block ciphers, offering efficient and secure solutions.
Methods
The core contribution is the TWEAKEY framework, which extends the concept of key-alternating ciphers. It treats both the secret key and the public tweak as a unified "tweakey" input. This unified input is processed through a series of rounds, each involving:
- Subtweakey Extraction (g): A function that extracts a portion of the tweakey.
- Internal State Update (f): The main round function of the cipher, often based on an existing block cipher's round.
- Tweakey State Update (h): A function that updates the remaining tweakey material for the next round.
Within TWEAKEY, the authors propose STK (Superposition TWEAKEY), a subclass designed for AES-like ciphers. STK uses finite field multiplications with distinct coefficients to prevent cancellations between different tweakey words, simplifying security analysis. For AES-like ciphers, STK specifies:
- g: XORing subtweakeys and round constants.
- h: Nibble-wise permutation and multiplication by distinct coefficients in GF(2^n).
- f: The AES round function.
They also present Kiasu-BC, a simpler construction that directly tweaks AES-128 by XORing the 64-bit tweak into the top two rows of the internal state at each round, without altering the AES key schedule.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Unified Tweakey Input: Treating keys and tweaks as a single "tweakey" simplifies the design and analysis of tweakable block ciphers, especially for key-alternating structures.
- STK's Coefficient Strategy: Using distinct coefficients in finite field multiplications within the tweakey schedule is crucial for preventing trivial cancellations and enabling more straightforward security analysis, even for multiple tweakey words.
- Beyond Birthday-Bound Security: The proposed constructions aim for security beyond the birthday bound, which is a significant advantage over many existing tweakable block cipher schemes.
- AES-Tweakability: Kiasu-BC demonstrates that it's possible to efficiently tweak a well-established cipher like AES-128 without a complete redesign, offering a practical solution for existing systems.
- Trade-off between Efficiency and Security: The paper highlights how design choices in the tweakey schedule directly impact both performance and the difficulty of cryptanalysis.
Key Results
- Deoxys-BC: A 128-bit tweak/key block cipher based on the AES round function, offering improved performance and security over existing AES-based tweakable ciphers. It achieves around 1.3 cycles/byte in OCB3 mode on Intel Haswell.
- Joltik-BC: A lightweight 64-bit block cipher based on an AES-like round function, designed for hardware implementations, estimated to require around 1500 GE.
- Kiasu-BC: A simple and efficient tweakable variant of AES-128 for 64-bit tweaks. It achieves performance comparable to AES in OCB3 mode (around 0.75 c/B) while providing full 128-bit security.
- Security Margins: The proposed ciphers offer significant security margins against related-tweakey differential attacks (at least 4 rounds for Deoxys-BC, 8 for Joltik-BC) and meet-in-the-middle attacks (e.g., 4 rounds for Deoxys-BC-256, 21 for Joltik-BC-192).
Limitations and Future Work
- Proof of Soundness: The authors suggest that generalizing existing proofs for key-alternating ciphers to the TWEAKEY framework would be valuable.
- Optimized Nibble Permutations: Further research into finding better nibble position permutations (h') for STK could enhance security and efficiency.
- 128-bit Tweak for AES: Directly tweaking AES-128 with a 128-bit tweak while maintaining its original key schedule remains a challenging open problem.
- Efficient Key Schedules: The paper reiterates the general challenge of designing simple, secure, and efficient key schedules for AES-like ciphers that allow for human-readable proofs.
Summary updated