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

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).

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.

Design Rationale of Tweakable Block Ciphers:  The basic idea is to expand the small tweak using a suitable linear code of high distance and then inject it in the internal block cipher (AES and GIFT resp.) state after certain interval. The implementation is done using very low tweak state and without any tweak schedule (only tweak expansion). The tweak expansion and the tweak injection is done by minimizing the area and the energy keeping the differential probability as good as the original block cipher counterparts.

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:

The minimum number of active S-boxes is 40 for the entire construction. 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^-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.

It is possible to mount a (i) Boomerang attack on 7-rounds of TweAES including four tweak injections that starts from the tweak injection and (ii) Impossible differential attack on 8-rounds of TweAES. Both the two attacks against reduced-round variants that start from the middle of the 4-round core. Because security of TweAES-128 using tweak difference relies on the fact that the large-weight tweak difference will diffuse fast in the subsequent 2 rounds, those reduced-round analysis will not threaten the security of the full TweAES-128.

Integral attacks collect 2⁸ distinct values for a particular byte or distinct 2³² 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⁸ distinct values for any byte.

Meet-in-the-middle attacks exploit the 4-round truncated differentials 1->4->16->4->1 and focus on the fact that the number of differential characteristics satisfying this differential is at most 2⁸⁰. 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¹²⁰ 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

From the summary of results in Table 2, we can observe the overhead introduced by the extra components required for the mode of operation. In terms of LUTs, the overhead is 618 LUTs in ESTATE[TweAES] and 623 in ESTATE[TweGIFT]. In terms of flip-flops, we observe that the overhead in ESTATE[TweGIFT] is almost two times that in ESTATE[TweAES]. The overheads are introduced by an input multiplexer to the cipher, two 128-bit XORs to compute the MAC and OFB modes, one additional multiplexer to select the correct output between tag or plaintext/ciphertext, and finally the control unit that also generates the corresponding tweak values.

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

From Table 3, it can also be observed that as the length of the message increases the throughput tends to the values presented in Table 2. To conclude, we can say that in terms of speed ESTATE[TweAES] is better, while in terms of area ESTATE[TweGIFT] is a better option.

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