Contents






LOCUS Mode of Authenticated Encryption

Lightweight OCb with rUp Security, or LOCUS in abbreviation, is a tweakable block cipher based authenticated encryption scheme that employs OCB style of construction. LOCUS is a  --- lightweight,  ---online, ---  parallel, ---  beyond the birthday bound secure secure construction that achieves INT-RUP security.  The design is motivated from OCB [1]. To instantiate LOCUS, we propose a small-tweak tweakable block cipher TweGIFT. As the names suggest, TweGIFT is a tweakable variant of the GIFT [2] block cipher. This tweakable block cipher is explicitly designed for efficient processing of small tweaks of size 4 bits.


Contents
  • 1 Features
  • 2 Mode Specification
  • 3 Tweakable Block Cipher
  • 4 Instantiation
  • 5 Rationale
  • 6 Security
  • 7 Cryptanalysis
  • 8 Comparative Study

    • Features

    1. High Security: The use of nonce-based encryption key and masking key ensures that LOCUS-AEAD achieves beyond the birthday bound security. In fact, both of them achieve the optimal security level, DT = O(2n+κ), where D and T denote the data and time complexity, respectively. Here D < 2n, and T < 2κ are obvious conditions.

    2. Light-weight: Similar to LOTUS-AEAD, LOCUS-AEAD achieves the NIST lightweight standardization requirements with 64-bit block ciphers. This reduces the overall state size of the AEAD candidates, when instantiated with ultra-lightweight block ciphers. Our dedicated tweakable block cipher, TweGIFT-64, is a perfectly suitable candidate for this.

    3. High Performance: LOCUS-AEAD preserves the inherent high performance features of OCB. It is single pass and fully parallelizable.

    5. INT-RUP Secure : Most of the existing block cipher based modes, notably OCB, OTR, COFB [6], SUNDAE [2], do not provide any security in RUP model. This might be an issue in memory-constrained lightweight environments or low-latency real-time streaming protocols. Our proposals solves the prob- lem partially as they provide integrity security under RUP model.

    6. Versatility :  Probably, the single most important feature of our proposals is their scope of applicability. At one end of the spectrum, the parallelizability of LOCUS-AEAD make them a perfect candidate for applications in high performance infrastructures. On the other end, their overall state size is competitively small with respect to many existing lightweight candidates, which makes them suitable for low-area hardware implementations.  

    Mode Specification

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

    LOCUS is a (short tweak) tweakable block cipher based authenticated encryption mode that employs OCB paradigm, where a nonce based key is derived and updated for the encryption of each block. For the purpose of domain separations, LOCUS uses 4-bit short tweaks.

    Figure 1: Associated data processing of LOTUS Authenticated Encryption

    Figure 2: Encryption of LOCUS Authenticated Encryption

    Specification of TweGIFT

    This is a tweakable variant of GIFT-64-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-64-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.

    Rationale

    1. Choice of the Mode: Our primary goal is to design a lightweight AEAD that should be efficient, provides high performance capability and performs reasonably well in low-end devices as well. For efficiency, the AEAD should be one pass. To obtain high performance capability, we aim for parallelizability. In addition, we demand integrity in RUP model. This is specially useful for memory-constrained lightweight applications. Here we start with the popular mode OCB. Similar to OTR, OCB also satisfies the first two properties. OCB is online, one-pass and parallelizable. However, OCB is insecure under the RUP model. This motivates us to design an AE mode which is structurally as simple as OCB but achieves RUP security while keeping the primary features, such as efficiency and parallelism, intact. The new proposal LOCUS-AEAD replace one block cipher call by two calls. The rationale behind this modification is the observation that the intermediate state between the two block cipher invocations can be used to generate a checksum, which is completely hidden and hence cannot be controlled by the adversary (even if the adversary is allowed to make RUP queries). This hidden checksum ensures integrity security in RUP model. The additional block cipher call per message block increases the number of block cipher calls from to (2m + 1) to process an m-block message. However, this seems optimal as for any INT-RUP secure parallel AEAD mode, at least (2m + 1) non-linear invocations are necessary to process an -block message.

    The associated data processing phase is based on a simple variant of the hash layer of PMAC, and the computation is completely parallel. The associated data processing can be done in parallel with the plaintext and/or ciphertext processing in order to maximize the performance in parallel computing environments.

    OCB generates the tag using the checksum (simple XORs) of all the plain text blocks and the output of the processed associated data. However, two separate states are required to hold the message checksum and the AD checksum. We obtain INT-RUP security, by using an intermediate checksum (hidden to the adversary) instead of the plaintext checksum. Moreover, we do not store the intermediate checksum and AD checksum separately. Rather, we XOR the two checksums, which means that in a sequential im- plementations, the intermediate checksum can be computed on top of the AD checksum. This reduces the overall state size by size of one block.

    A notable change in LOCUS-AEAD is the use of nonce and position dependent keys. OCB has only birthday bound security on the block size. This is because the security is generally lost once the input/output of any two distinct block cipher calls matches, as the two calls share the same encryption key. In LOCUS-AEAD, we overcome the birthday bound barrier by changing the key and tweak pair for each block cipher call. So even if there is a collision among inputs/outputs, the security remains intact, as the block cipher keys or tweaks are distinct. In fact, our modes are secure up to data complexity of 2n, and time complexity of 2k, and combined data-time complexity up to 2n+κ (see section 3 for more details). This, in turn, helps us to construct AEAD algorithms with the desired security level using an ultra-lightweight block cipher TweGIFT-64.

    2. Choice of the TBC: The main motivation behind TweGIFT-64 is the lack of a good short-tweak tweakable block cipher, which is essential for instantiating LOCUS-AEAD. There are some extremely good tweakable block cipher candidates, most notably SKINNY [4], but they are designed to handle general purpose tweaks, and hence not optimized for very short tweaks of size 4 bits. In contrast, TweGIFT-64 is especially designed on top of the GIFT-64-128 block cipher to handle such small tweak values.

    For the tweak expansion, we use a simple linear code that converts a 4-bit tweak value into an 8-bit codeword. The linear code is described below: This linear code has two advantages: (i) it is a distance 4 code, and (ii) it is very simple and requires only 7 XOR operations. We use two copies of the codeword to get a 16-bit codeword, which has distance 8. As we will see in the cryptanalysis, this high distance linear code ensures good differential characteristics for TweGIFT-64.

    We choose to inject the expanded tweak into the block cipher state by masking it to the third bit of each nibble. This bit position has been chosen as the other three positions are already masked by the round key and round constant bits. The tweak injection at intervals of 4 rounds ensures very low differential probability for TweGIFT-64.

    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.

    Submissions Privacy Authenticity
    Time Data (in bytes) Time Data (in bytes)
    LOCUS [TweGIFT] 2128 264 2128 264

    Cryptanalysis


    Here we provide the security analysis on TweGIFT-64 in the related-key setting. Without exploiting the tweak, TweGIFT-64 offers exactly the same security as the original GIFT-64-128. Hence we focus our attention on the attacks that exploit the tweak injection. The exact security bound, e.g. the lower bound of the number of active S-boxes and the upper bound of differential characteristic probability, can be obtained by using various tools based on MILP and SAT, however to derive such bounds for the entire construction with 128-bit key difference is often infeasible. Here we focus on the feature that the tweak expansion function ensures a large number of active bits at the expanded tweak. This implies that differential trails with non-zero tweak difference will have a relatively large number of active S-boxes around the tweak injection. This motivates us to evaluate the tight bound of the differential characteristic probability for the 2-round transformation followed by the tweak injection and another 2-round transformation, which we call ``4-round core". Let p core be the maximum differential characteristic probability of the 4-round core. Then, the probability for the entire construction is upper bounded by (p core) 6 because 28 rounds of TweGIFT-64 contain six sequence of the 4-round core (see Fig. 3).

    Figure 3: Sequence of 4-round core in TweGIFT-64.

    We used the MILP based tool to derive p core. It turned out that the p core is 2−16, hence the maximum differential characteristic probability of 28 rounds can be upper bounded by 2−16×6= 2−96. This can also be viewed that the maximum differential characteristic probability reaches 2−16×4= 2−64 and we have 8 rounds for the margin. One of the best differential trails for the 4-round core with probability 2−16 is fully specified in Table 3.2. The tweak expansion ensures that the number of active bits in the expanded tweak is at least 8 when the tweak difference is non-zero. We note that, in the very middle round, both AddRoundKey and AddTweak are performed. However the key bits and tweak bits are XORed to different bit positions of the state. Thus, they cannot cancel each other to avoid affecting the state.

    NIST Light-weight Competition: Why LOCUS?

    Here we provide a comparative study LOCUS-AEAD with other Parallel AE modes and depicts the advantages of our mode over other designs. Typically, the comparison is made with all the other parallel modes that are submitted to NIST which includes Flex-AEAD, LAEM, LILLIPUT-AE, PYJAMASK, QAMELEON, SKINNY AEAD.

    Construction Primitive
    size     		State
    size     		Rate RUP Secure Ciphertext Expansion
    LOCUS 64 (4-bit tweak) 324 1 YES 64
    Flex-AEAD 128 768 1/3 NO 128
    LAEM 128 384 1/2 NO 64 per message block
    LILLIPUT-AE 128 (192-bit tweak) 704 1 NO 128
    PYJAMASK 128 (192-bit tweak) 704 1 NO 128
    QAMELEON 128 (128-bit tweak) 640 1 NO 128-255
    SKINNY-AEAD 128 (256-bit tweak) 764 1 NO 128


    References

    1. ^ 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.
    2. ^ 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.
    3. ^ NIST FIPS 197. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication, 197, 2001.
    4. ^ 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.
    5. ^ 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.
    | Template by HTML5 Templates