# ESTATE Mode of Authenticated Encryption

**E**nergy efficient and

**S**ingle-state

**T**weakable block cipher based M

**A**C-

**T**hen-

**E**ncrypt, 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: A**part 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.

Along with ESTATE, we also define a lighter version of ESTATE, called sESTATE where we use two tweakable block ciphers: E and F**(a round-reduced variant of E)**. We use F (except the last call for AD and message).

## 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] | 2^{128} |
2^{64} |
2^{128} |
2^{64} |

ESTATE [TweGIFT] | 2^{128} |
2^{64} |
2^{128} |
2^{64} |

sESTATE [TweAES-6] | 2^{112} |
2^{60} |
2^{112} |
2^{60} |

## 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:

^{-6}, the probability of the differential propagation is upper bounded by 2

^{-240}. Security of full TweAES is based on the fact that the heavy weight of the expanded tweak is propagated through 2 rounds in forward and backward. We call those operations

*4 rounds core.*We argue that the reduced-round versions of TweAES in which the first or the last round is located in the middle of the 4-round core can be attacked for relatively long rounds. Owing to this unusual setting, the attacks here do not threaten the security of full TweAES.

^{8}distinct values for a particular byte or distinct 2

^{32}values for a particular diagonal. Integral attacks exploiting the tweak is difficult because the tweak will not affect all the bits in each byte, which prevents to collect 2

^{8}distinct values for any byte.

^{80}. The large-weight of the expanded tweak in TweAES does not allow such sparse differential trails, which makes it hard to be exploited in the meet-in-the-middle attack.

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 2^{120} 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.