ESTATE Mode of Authenticated Encryption
Energy efficient and Single-state Tweakable block cipher based MAC-Then-Encrypt, or ESTATE in abbreviation, is a tweakable block cipher based authenticated encryption scheme that employs MAC-then-Encrypt style of construction. ESTATE is a --- single-state, --- inverse-free, --- RUP secure construction that does not require any field multiplications. The design is motivated from SUNDAE [1]. To instantiate ESTATE, we propose two dedicated tweakable block ciphers TweGIFT and TweAES. As the names suggest, TweGIFT is a tweakable variant of the GIFT [2] block cipher, where as TweAES is a tweakable variant of the AES [3] block cipher. Both these tweakable block ciphers are explicitly designed for efficient processing of small tweaks of size 4 bits.
Features
1. Nonce-misuse Resistant: ESTATE is a nonce-misuse resistant authenticated cipher and provides full security even with the repetition of nonce. Alternatively said, it can be viewed as a deterministic authenticated encryption where the nonce is assumed to be the first block of the associated data.
2. Single State: ESTATE has a state size as small as the block size of the underlying cipher (in addition to state for the master key and round key), and it ensures good implementation characteristics both on lightweight and high-performance platforms.
3. Inverse-Free: ESTATE is an inverse-free authenticated encryption algorithm. Both encryption and decryption algorithms do not require any decryption call to the underlying tweakable block cipher. This significantly reduces the overall hardware footprint in combined encryption-decryption implementations.
4. Almost No-Overhead: Apart from the tweakable block cipher call it requires just 128-bit XOR per block of data, which seems to be the minimum required overhead.
5. Optimal : ESTATE requires (a+2m) many
primitive invocations to process an a block associated-data
(including the nonce) and m block message. Chakraborti et al. [4] showed that this is the optimal number of non-linear primitive calls required for deterministic authenticated
encryption.
6. Short message Efficiency : The optimality on the number of calls and almost no overhead help it to get very high performance for short messages. For example, to process 128-bit nonce, 128 bit AD and 126 bit message, we only need 4 calls of underlying tweakable block cipher.
7. RUP Secure: We separate the block cipher
invocations for the OFB functions and the first tweakable
block cipher input invocation by the usage of different
tweaks. This essentially helps us to provide RUP security [5] The operation is an
for ESTATE, making it much more robust in constraint
devices. Here, we note that a related construction SUNDAE
lacks this feature. We note that RUP security is very much
relevant for lightweight devices which do not have high
buffer to hold a bigger message.
Mode Specification
ESTATE authenticated encryption mode receives an (1)
128-bit encryption key K, (2) an 128-bit nonce N, (3) an
associated data A of arbitrary length, (4) and a message M
of arbitrary length as inputs, and returns a (5) ciphertext
C of same length as that of the message, and (6) an 128-bit
tag T.
ESTATE is a (short tweak) tweakable block cipher based authenticated encryption mode that employs MAC-then-Encrypt paradigm, where a CBC style message authentication is done on the nonce, associated data and message to generate the tag. The tag is then used as an initial value in the OFB mode of encryption to generate the ciphertexts. For the purpose of domain separations, ESTATE uses 4-bit short tweaks.

Figure 1: ESTATE Mode of Authenticated Encryption for a
associated data blocks and m message blocks

Figure 2: sESTATE Mode of Authenticated Encryption for a
associated data blocks and m message blocks
Tweakable Block Ciphers
TweAES: This is a tweakable variant of AES-128-128 block cipher that accepts short tweaks of length 4. The 4-bit initial tweak is first expanded to an 8-bit value using a linear code that generates code words of hamming distance 4. All the operations of TweAES is identical to AES-128-128 except that we inject the 8-bit extended tweak after the add round key operation at an interval of 2 rounds.
TweAES-6: This is a reduced variant of TweAES, where instead of 10 rounds, 6 rounds are used. The tweak addition is done after round 2 and 4.
TweGIFT: This is a tweakable variant of GIFT-128-128 block
cipher that accepts short tweaks of length 4. The 4-bit
initial tweak is first expanded to an 32-bit value using a
linear code that generates code words of hamming distance 4.
All the operations of TweAES is identical to GIFT-128-128
except that we inject the 32-bit extended tweak after the
add round key operation at an interval of 5 rounds.
Recommended Instantiations
ESTATE[TweAES]: This AEAD scheme obtained by instantiating ESTATE mode of operation with TweAES block cipher. Here the size of the key, nonce and tag are 128 bits each. We recommend ESTATE TweAES-128, as the primary version.
ESTATE[TweGIFT]: This AEAD scheme is obtained by instantiating ESTATE mode of operation with TweGIFT block cipher. Here the size of the key, nonce and tag are 128 bits each. We recommend ESTATE TweGIFT-128, for hardware-oriented ultra-lightweight applications.
sESTATE[TweAES-6]: This AEAD scheme is obtained by instantiating ESTATE mode of operation with TweAES-128 block cipher. Here also, the size of the key, nonce and tag are 128 bits each. We recommend sESTATE TweAES-128-6, for higher throughput demanding, and energy- constrained applications.
Rationale
1. Choice of the Mode: Our basic goal is to design an ultra-lightweight mode, which is especially efficient for short messages, and secure against nonce misuses. For this, we choose SIV as base and then introduce various tweaks to make the construction single-state and inverse free, much in the same vein as in the case of SUNDAE.
2. Choice of the TBC: We use tweakable block cipher with 4-bit tweak primarily for the purpose of various domain separations such as the type of the current data (associated data or message), completeness of the final data block (partial or full), whether the associated data and/or message is empty etc. Note that, without the use of these tweaks, these domain separations would cost a few constant field multiplications and/or additional block cipher invocations, which would in turn increase the hardware footprint as well as decrease the energy efficiency and throughput for short messages.
3. Choice of TweAES and TweGIFT: For both these versions, we expand the tweak in such a way that the extended tweak has very high distance and the extension can be done using only 7 bit XOR operations. We choose the tweak positions and the interval of the tweak injection with the primary goal that the tweakable versions should have similar security level as the underlying block ciphers, while minimizing the tweak injection overhead.
4. Choice of the Tweaks: We use tweak 0 for all the block ciphers used in the OFB part and all the intermediate block ciphers in the FCBC function. Since tweAES and tweGIFT with zero tweaks are essentially AES and GIFT respectively, no additional overhead is introduced in the software for longer messages due to the use of tweakable block ciphers. Tweak value 1 is used for the first block cipher invocation in the FCBC function so that the adversary does not have any control over the inputs of the intermediate block ciphers. This essentially ensures the RUP security of the mode. sESTATE always uses tweak 15 for the round-reduced block ciphers to maximize the distance with other tweaks, most importantly tweak 0 whose inputs and outputs are observed through OFB. In this way, we make tweAES-6 with tweak value 15 and tweAES with tweak value 0 as much independent as possible.
Security
The security levels of our recommended instanstiations are presented below in the Table. Of note is the fact that we do not restrict the adversary to be nonce-respecting, and same nonce can be used for all the queries, without any degradation of the security. All these versions are equally secure in nonce-misusing scenario. Further we claim both privacy and integrity security under RUP model, where the decryption algorithm releases unverified plaintext. Note that sESTATE[TweAES-6] allows a little bit less data and time limits than ESTATE[TweAES] due to the use of round-reduced variant of TweAES.
Submissions | Privacy | Authenticity | ||
---|---|---|---|---|
Time | Data (in bytes) | Time | Data (in bytes) | |
ESTATE [TweAES] | 2128 | 264 | 2128 | 264 |
ESTATE [TweGIFT] | 2128 | 264 | 2128 | 264 |
sESTATE [TweAES-6] | 2112 | 260 | 2112 | 260 |
Cryptanalysis
1. TweAES: In TweAES, the expanded tweak is injected in every 2 rounds. We evaluate the minimum number of differentially and linearly active S-boxes for the 4-round core. When the tweak input has a non-zero difference, the expanding function ensures that at least 4 bytes are affected by the tweak difference. We modeled the problem of finding the differential trail with minimum number of active S-boxes by MILP and experimentally obtain the following results:
2. TweAES-6: In TweAES-6, the number of rounds is reduced from TweAES by considering that the attackers do not have full control over the block cipher invocation in the modes. From this background, we do not analyze the security of TweAES-6 as a standalone tweakable block cipher, but show that the number of active S-boxes is sufficient to prevent attacks. As a result of running the MILP-based tool, it turned out that the differential trail achieving the minimum number of active S-boxes with some non-zero tweak difference is 20. Given that the maximum differential probability of the AES S-box is 2-6, the probability of the differential propagation is upper bounded by 2-120. Because our mode does not allow the attacker to make 2120 queries, it is impossible to perform the differential cryptanalysis.
3. TweGIFT: In this expansion, the 4-bit tweak
expands to 8 bits and those 8 bits are copied three times to
achieve a 32-bit tweak. When the 4-bit tweak has some
non-zero difference, the expanded 32-bit tweak is ensured to
have at least 16 active bits, which ensures at least 16
active S-boxes in 2 rounds around the tweak injection. Owing
to the large state size and a large number of active
S-boxes, it is infeasible to find the tight bound of the
maximum probability of the differential characteristic for
the 10-round core by using MILP. The tool so far provided
that the maximum probability of the differential
characteristic is upper bounded by 2-64.5. Given
that the entire TweGIFT consists of 40 rounds and thus
contains 4 of the 10-round cores, the upper bound of the
entire construction is 2-258, which is sufficient
to resist the attack.
Hardware Performance
We implemented ESTATE[TweAES] and ESTATE[TweGIFT], as well as the standalone versions of TweAES and TweGIFT. All of them are round-based architectures (the data-path size is 128-bit).
Primitive | LUTs | FFs | Slices | Freq (MHz) |
Clock Cycle | Throughput (MBPS) |
---|---|---|---|---|---|---|
TweAES | 1617 | 524 | 574 | 328.27 | 11 | 3819.87 |
ESTATE[TweAES] | 2235 | 679 | 1110 | 314.71 | 20 | 2014.14 |
TweGIFT | 790 | 408 | 336 | 597.59 | 41 | 1865.65 |
ESTATE[TweGIFT] | 1413 | 698 | 616 | 580.11 | 80 | 928.27 |
The throughput for ESTATE[TweGIFT] is more than 50% lower than ESTATE[TweAES]. This is because the number of cycles to process one block is much more significant for ESTATE[TweGIFT] based construction, 80 cycles against 20 cycles in ESTATE[TweAES]. In terms of hardware area, we can see that ESTATE[TweAES] is around 40% higher than ESTATE[TweAES]. This can be explained by the nature of GIFT which was designed to be ultra-lightweight. The same behavior is observed for stand-alone implementations of the block ciphers. ESTATE is also efficient for shorter messages, as evident from Table 3 which gives the throughput for message lengths between 16 bytes to 1024 bytes.
MODE | 16B | 32B | 64B | 128B | 512B | 1024B |
---|---|---|---|---|---|---|
ESTATE[TweAES] | 1681.04 | 1918.24 | 1965.02 | 1989.28 | 2007.87 | 2011.00 |
ESTATE[TweGIFT] | 905.54 | 916.72 | 922.41 | 925.29 | 927.45 | 927.82 |
It is important to note that these implementations are a first attempt at showcasing the efficiency/low-area features of ESTATE. There are many possibilities for optimization, mainly related to the optimization of the underlying cipher. For instance, take the case of TweAES. There are many ways to do a small footprint implementation of AES, which could be applied to TweAES as well. For example, using a smaller data-path, say 32-bit, and T-tables instance of S-Boxes. For TweGIFT, one can explore different degrees of serialization from bit-serial to round-based implementations. Another direction that we can explore is the implementations in constrained devices like automotive and low power FPGAs, and small, 8-bit or 16-bit micro-controllers.
ESTATE in the light of NIST Competition
Here we provide a comparative study ESTATE with other SIV based AE modes and depicts the advantages of ESTATE over other designs. Typically, the comparison is made with all the other SIV based candidates that are submitted to NIST which includes Limdolen, SIV-Rijndael256, SIV-TEM-PHOTON, SUNDAE-GIFT and TRIFLE. Here we use the notation BC-n to denote a block-cipher with block size n. Similarly we use TBC-n-t (or tBC-n-t) to denote a tweakable block cipher (short-tweak) with block size n and tweak size t.
Construction | Primitive | State size |
# Primitive invokation |
Multiplication Free |
RUP Secure |
---|---|---|---|---|---|
ESTATE | tBC-128-4 | 260 | (a+2m) | YES | YES |
Limdolen | BC-128 | 384 | (a+2m) | NO | NO |
SIV-Rijndael256 | tBC-256-4 | 388 | (a+2m) | YES | YES |
SIV-TEM-PHOTON | TBC-256-132 | 516 | (a+2m) | YES | YES |
SUNDAE-GIFT | BC-128 | 256 | (a+2m+1) | NO | NO |
TRIFLE | BC-128 | 384 | (a+2m+2) | NO | NO |
References
- ^ Subhadeep Banik, Andrey Bogdanov, Atul Luykx, and Elmar Tischhauser. Sundae: Small universal deterministic authenticated encryption for the internet of things. IACR Transactions on Symmetric Cryptology, 2018(3):1–35, Sep. 2018.
- ^ Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption. In Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, pages 321–345, 2017.
- ^ NIST FIPS 197. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication, 197, 2001.
- ^ Avik Chakraborti, Nilanjan Datta, and Mridul Nandi. On the optimality of non-linear computations for symmetric key primitives. J. Mathematical Cryptology, 12(4):241–259, 2018.
- ^ Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, and Kan Yasuda. How to securely release unverified plaintext in authenticated encryption. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, pages 105–125, 2014.