Lightweight Authenticated Encryption

From CryptoLUX
Jump to: navigation, search

Lightweight authenticated ciphers are lightweight cryptographic primitives.

Design Principles

Description

The aim is to provide simultaneously encryption and authentication in one primitive and in one pass. Authentication allows communicating entities to ensure that their communication has not been modified or tampered with. This verification is based on the computation of a so-called tag associated to the transmitted data which cannot be generated in reasonable time unless a secret is known.

The generation of the tag can be done separately from the encryption but the primitives listed on this page perform both operations at the same time.

Stream-Cipher Based

One possible way to achieve this is to use a special stream-cipher like PHELIX[1] which uses the plaintext to update its internal state. The MAC can then be derived from the internal state of the stream-cipher once encryption is finished.

Duplexed Sponge

The duplexed sponge.

The duplexed sponge[2] is based on the use of a sponge as a stream-cipher in the way described above, i.e. by incorporating blocks of plain text in the computation of the internal state. This structure is best described by a figure (on the right, taken from the original paper[2]): σi corresponds to the ith block of plain text, Zi to the ith block of cipher text, r to the rate of the sponge, c to its capacity and f to its update function.

The duplexed sponge is actually a construction with broader applications than just authenticated encryption. When used for this purpose, the construction is called SpongeWrap.

This construction can also be further specialized as has been suggested by Andreeva et al.[3] (APE construction) and can be lightweight as long, of course, as the permutation used is.

Summary

Summary of the main characteristics of the current lightweight block ciphers
Presentation Cryptographic Properties Implementation Properties
name designers reference (design) internal state key size Nonce/IV size attacks Technology used area (#GE) throughput (Kb/s @ 100kHz) power consumption reference (implementation)
ACORN[note 1] Wu CAESAR (14)[4] 293 128 128 -- -- -- -- --
ALE Bogdanov et al. FSE 13[5] 128 128 128
  • LOCAL attack (full primitive)[6]
  • Leaked-state-forgery attack[7]
65nm 2579 / 2700 -- -- Specification[5]
ASC-1 Jakimoski et al. SAC 12[8] 0[note 3] 128 0 65nm 4793 / 5517 -- -- ALE specification[5]
ASCON[note 1] Dobraunig et. al. CAESAR (14)[9] 320 96 96 -- -- -- -- --
128 128
C-QUARK Aumasson et al. DIAC 12[10] 384 256 64 90 nm 4000 / 8875 8.33 / 266.67 -- Specification[10]
FIDES Bilgin et al. CHES 13[11] 160 80 80
  • To appear (FSE 14)
90 nm 793 / 2922 10.64 / 500 -- Specification[11]
192 96 96 1001 / 6673 12.77 / 600 --
Hummingbird-2 Engels et al. SaP 12[12] 128 128 64
  • Related key (full primitive)[13]
0.13 µm 3220 / 2332 / 2159 -- 1.93 / 1.845 / 1.73[note 4] Specification[12]
Joltik[note 1] Jean et. al. CAESAR (14)[4] 64 128 (key+tweak) 128 (key+tweak) -- -- -- -- --
192 (key+tweak) 192 (key+tweak)
Ketje[note 1] Bertoni et. al. CAESAR (14)[14] 200 k ≤ 182 182-k -- -- -- -- --
400 k ≤ 382 382-k
LAC[note 1] Zhang et. al. CAESAR (14)[15] 80 (key state) + 64 (BC state) 64 80 -- -- -- -- --
Sablier[note 1] Zhang et. al. CAESAR (14)[15] 208 80 80 -- -- -- -- --
SCREAM & iSCREAM[note 1] Grosso et. al. CAESAR (14)[16] 128 (tweak state) + 64 (BC state) 128 128 [note 5] [note 5] [note 5] [note 5] Specification[16]

Descriptions

ACORN

Description of the internal state of ACORN.
  • Article: ACORN: a Lightweight Authenticated Cipher[4][note 1]
  • Authors: Wu, Hongjun

ACORN is based on 6 LFSR's having a total length of 293 bits. It uses 2 Boolean functions when computing the keystream bit and the feedback bit. These are called maj(x,y,z) and ch(x,y,z) and are part of the specification of SHA-2. ACORN-128 is intended to provide 128 bits of security for both encryption and authentication. Finally, the author claims that the hardware implementation cost is close to that of Trivium.

The design is inspired by that of hardware oriented streamciphers like Grain and Trivium.

ASC-1

Description of ASC-1.
  • Article: ASC-1: An authenticated encryption stream cipher, SAC 12[8]
  • Authors: Jakimoski, G., & Khajuria, S.

The design of this primitive is based on the LEX stream cipher[17]: the keystream corresponds to bytes of the internal state of the AES which are leaked. A quick description is given on the figure on the right. It only supports encryption of messages made of 3 blocks of 128 bits.

We argue that ASC-1 is secure by reducing [its] security to the problem of distinguishing the case when the round keys are uniformly random from the case when the round keys are generated by a key scheduling algorithm.

The construction is based on the concept of Leak-safe Almost XOR Universal (LAXU) hash function which can allow the construction of provably secure authenticated ciphers.

ASCON

  • Article: ASCON v1: Submission to the CAESAR Competition[9][note 1]
  • Authors: Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.

ASCON uses a sponge construction, although it uses a stronger keyed initialization and keyed finalization phase than usual. There are two suggested instances, ASCON-96 and ASCON-128, but the specification is more general (the different instances differ only by their rate). In both cases, the sponge uses an internal state of 320 bits.

The function used to update it consists in several iterations of three different operations: round constant addition, substitution layer, linear diffusion layer. The state is represented as an array of 5 lines of 64 bits. The substitution layer operates on columns using a 5x5 S-Box which can be implemented cheaply in hardware. The linear layer is applied on each line separately. For each, the operations consists in rotating the line in 3 different ways and then xoring the results.

ALE

Principle of ALE's authenticated encryption
  • Article: ALE: AES-Based Lightweight Authenticated Encryption, FSE 13[5]
  • Authors: Bogdanov, A., Mendel, F., Regazzoni, F., Rijmen, V., & Tischhauser, E.

It takes 128-bits key and nonce and the length of the plaintext is limited to 245 bytes. The overall structure is that of an authenticated stream-cipher.

The design of this primitive is based on the LEX stream cipher[17] and draws some inspiration from ASC-1 as well. It is based on the AES to use its high security and, should the instruction be available on the platform, the AES-NI assembly instructions. However, it has already been broken by Khovratovitch et al.[6] and Wu et al.[7].

C-QUARK

  • Article: Heavy Quark for secure AEAD, DIAC 12[10]
  • Authors: Aumasson, J. P., Knellwolf, S., & Meier, W.

Lightweigthness is not the main focus of this primitive since it relies on a heavier version of the sponge used in the QUARK family of lightweight hash functions and provide higher security. It uses a SpongeWrap structure. Its authors want to see if the reverse of the usual approach (building lightweight primitives from simpler versions of not-so-lightweight ones) is sane.

Despite a 256-bits key, it "only" claims 253 bits of security for the sake of the simplicity of the proofs used. The message length is limited to 264 blocks of 64-bits.

FIDES

  • Article: FIDES: lightweight authenticated cipher with side-channel resistance for constrained hardware, CHES 13[11]
  • Authors: Bilgin, B., Bogdanov, A., Knežević, M., Mendel, F., & Wang, Q.

It is a duplexed sponge using a permutation based on the AES. Defense against side-channel attacks was one of the design criteria and a custom masking scheme is provided which does not increase the area footprint too much. The permutation used to update the internal state has an AES-like structure but the matrix used in the MixColumns step is different and, depending on the version of the algorithm, the S-box used is 5x5 or 6x6. In both case, the S-boxes have optimal differential uniformity (i.e. they are APN).

Hummingbird-2

  • Article: The Hummingbird-2 lightweight authenticated encryption algorithm, SaP 12[12]
  • Authors: Engels, D., Saarinen, M. J. O., Schweitzer, P., & Smith, E. M.

Hummingbird-2 is, as its name indicates, a new iteration of the Hummingbird[18] primitive which was successfully attacked by Saarinen[19]. This cipher has an internal state which is initialized using the 64-bits IV. There is no key schedule: the same functions are applied to the internal state every time. At each clock, operations involving the key, the plain-text 16-bits block and the 128-bits internal state are performed to generate a block of ciphertext. Then, the same sort of operations are used to update the internal state using variables created during the cipher-text generation.

The only operations used are XOR, addition modulo 216 and a non-linear function called f which is based on 4 different S-boxes.

Joltik

  • Article: Joltik v1[20][note 1]
  • Authors: Jean, J., Nikolic, I. & Peyrin, T.

Joltik is a lightweight authenticated cipher based on 64-bits tweakable block cipher called Joltik-BC. There are two versions of the mode of operation built on top of it: one for nonce-respecting adversary and one for not nonce-respecting ones.

Joltik-BC has the same structure as the AES but the internal state has only 64 bits. The S-box used is the same as Piccolo (4x4) and the MDS matrix is different: it is also involutory and non-circulant. There are two versions of it: one has a combined key and tweak length of 128 bits, the other has 192.

Ketje

  • Article: CAESAR submission KETJE v1[14]
  • Authors: Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. & Van Keer, R.

Ketje is a lightweight variant of the winner of the SHA-3 competition, Keccak[21]. As such, it is relies on the sponge structure, more precisely on the so-called MonkeyWrap mode. To allow an implementation in memory constrained environment, the internal state of the sponge is made of only 200 (or 400) bits, giving raise to Ketje Jr (and Ketje Sr). Hence, the rates used are much smaller than in Keccak. In both versions, the permutations used are variants of that of Keccak.

LAC

  • Article: LAC: A Lightweight Authenticated Encryption Cipher[15][note 1]
  • Authors: Zhang, L., Wu, W., Wang, Y., Wu, S., Zhang, J.

LAC uses a structure similar to that of ALE and an internal primitive based on LBlock. It uses a key of 80 bits, a "public message number" (nonce) of 64 bits and tags of 64 bits.

It relies on a simplified version of LBlock called LBlock-s where the S-box used is unique (instead of 10 different ones) and the key-schedule is modified into being equivalent to a sparse GFS, just like TWINE. The key stream is generated by leaking 24 bits of the internal state after 8 rounds and another 24 bits after another 8 rounds. The 48-bits message block is xored with the keystream to obtain the ciphertext and also xored in the internal state.

Sablier

Description of the internal state of Sablier.
  • Article: Sablier v1[22][note 1]
  • Authors: Zhang, B., Shi, Z., Xu, C., Yao, Y. & Li, Z.

Sablier is a hardware oriented stream cipher which provides authentication. The key and nonce are both 80 bits long and the tag is made of 32 bits. Encryption speed in hardware is expected to be 16 times faster than Trivium encryption.

Just like SIMON, it relies only on bit rotations, logical AND and XOR. For instance, it uses the χ transformation of Keccak. Its high level behaviour is explained using a metaphor based on a sandglass ("sablier" in French), see the Figure on the right.

SCREAM & iSCREAM

Description of the TAE mode of encryption.
  • Article: SCREAM & iSCREAM, Side-Channel Resistant Authenticated Encryption with Masking[16][note 1]
  • Authors: Grosso, V., Leurent, G., Standaert, F.X., Varici, K., Durvaux, F., Gaspar, L. & Kerckhof, S.

Both ciphers are used in the so-called TAE mode (see Figure on the right) to provide authenticated encryption. They are a modified version of Robin and Fantomas[23]. Misuse resistance is not a goal. Scream and iScream are both 128-bit ciphers with 8-bit S-boxes and 16-bit L-boxes. Unlike Scream, iScream is an involutive cipher. They differ by the choice of the S- and L-boxes but their design are similar: they are tweakable variants of the LS-design.

Implementation complexities in both software and hardware are given by the authors.

Notes

  1. 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 This primitive is a candidate of the CAESAR competition.
  2. 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 To the best of our knowledge.
  3. It only supports encryption of messages of length 3x128 bits.
  4. These figures correspond to the peaks of power consumption.
  5. 5.0 5.1 5.2 5.3 The implementation properties given in Table 5 of the specification do not fit with the units we use. Thus, we refer the interested reader to page 11 of the specification.

References

  1. Whiting, D., Schneier, B., Lucks, S., & Muller, F. (2005). Fast encryption and authentication in a single cryptographic primitive. ECRYPT Stream Cipher Project Report, 27(200), 5. pdf at ssi.gouv.fr
  2. 2.0 2.1 Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2012, January). Duplexing the sponge: single-pass authenticated encryption and other applications. In Selected Areas in Cryptography (pp. 320-337). Springer Berlin Heidelberg. pdf at eprint.iacr.org
  3. Andreeva, E. and Bilgin, B. and Bogdanov, A. and Luykx, A. and Mennink, B. and Mouha, N. and Yasuda, K. 2013). APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography. Cryptology ePrint Archive, Report 2013/791. pdf at eprint.iacr.org
  4. 4.0 4.1 4.2 Wu, H. (2014) ACORN: a Lightweight Authenticated Cipher. Submission to the CAESAR competition. pdf at cr.yp.to
  5. 5.0 5.1 5.2 5.3 Bogdanov, A., Mendel, F., Regazzoni, F., Rijmen, V., & Tischhauser, E. (2013). ALE: AES-based lightweight authenticated encryption. Lecture Notes in Computer Science. pdf at dtu.dk
  6. 6.0 6.1 Khovratovich, D., & Rechberger, C (2013). The LOCAL attack: Cryptanalysis of the authenticated encryption scheme ALE. pdf at eprint.iacr.org
  7. 7.0 7.1 Wu, S., Wu, H., Huang, T., Wang, M., & Wu, W. (2013). Leaked-State-Forgery Attack against the Authenticated Encryption Algorithm ALE. In Advances in Cryptology-ASIACRYPT 2013 (pp. 377-404). Springer Berlin Heidelberg. pdf at springer.com
  8. 8.0 8.1 Jakimoski, G., & Khajuria, S. (2012, January). ASC-1: An authenticated encryption stream cipher. In Selected Areas in Cryptography (pp. 356-372). Springer Berlin Heidelberg. pdf at springer.com
  9. 9.0 9.1 Dobraunig, C., Eichlseder, M., Mendel, F. & Schläffer, M. (2014) ASCON v1: Submission to the CAESAR Competition. Submission to the CAESAR competition. pdf at cr.yp.to
  10. 10.0 10.1 10.2 Aumasson, J. P., Knellwolf, S., & Meier, W. (2012). Heavy Quark for secure AEAD. DIAC-Directions in Authenticated Ciphers, Sweden. pdf at 131002.net
  11. 11.0 11.1 11.2 Bilgin, B., Bogdanov, A., Knežević, M., Mendel, F., & Wang, Q. (2013). FIDES: lightweight authenticated cipher with side-channel resistance for constrained hardware. In Cryptographic Hardware and Embedded Systems-CHES 2013 (pp. 142-158). Springer Berlin Heidelberg. pdf at kuleuven.be
  12. 12.0 12.1 12.2 Engels, D., Saarinen, M. J. O., Schweitzer, P., & Smith, E. M. (2012). The Hummingbird-2 lightweight authenticated encryption algorithm. In RFID. Security and Privacy (pp. 19-31). Springer Berlin Heidelberg. pdf from rfid-cusp.org
  13. Saarinen, M. J. O. (2013). Related-key Attacks Against Full Hummingbird-2. IACR Cryptology ePrint Archive, 2013, 70. pdf at eprint.iacr.org
  14. 14.0 14.1 Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. & Van Keer, R. (2014) CAESAR submission KETJE v1. Submission to the CAESAR competition. pdf at cr.yp.to
  15. 15.0 15.1 15.2 Zhang, L., Wu, W., Wang, Y., Wu, S. & Zhang, J. (2014) LAC: A Lightweight Authenticated Encryption Cipher. Submission to the CAESAR competition. pdf at cr.yp.to
  16. 16.0 16.1 16.2 Grosso, V., Leurent, G., Standaert, F.X., Varici, K., Durvaux, F., Gaspar, L. & Kerckhof, S. SCREAM & iSCREAM, Side-Channel Resistant Authenticated Encryption with Masking. Submission to the CAESAR competition. pdf at cr.yp.to
  17. 17.0 17.1 Biryukov, A. (2005). A new 128-bit key stream cipher LEX. eSTREAM, ECRYPT Stream Cipher Project, Report, 13, 2005. pdf at ecrypt.eu.org
  18. Engels, D., Fan, X., Gong, G., Hu, H., & Smith, E. M. (2010). Hummingbird: ultra-lightweight cryptography for resource-constrained devices. In Financial Cryptography and Data Security (pp. 3-18). Springer Berlin Heidelberg. pdf at springer
  19. Saarinen, M. J. O. (2011, January). Cryptanalysis of Hummingbird-1. In Fast Software Encryption (pp. 328-341). Springer Berlin Heidelberg. pdf at mjos.fi
  20. Jean, J., Nikolic, I. & Peyrin, T. (2014) Joltik v1. Submission to the CAESAR competition. pdf at cr.yp.to
  21. Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2009). Keccak sponge function family main document. Submission to NIST (Round 2), 3. pdf at googlecode.com
  22. Zhang, B., Shi, Z., Xu, C., Yao, Y. & Li, Z. (2014) Sablier v1. Submission to the CAESAR competition. pdf at cr.yp.to
  23. Grosso, V., Leurent, G., Standaert, F.X. & Varici, K. (2014). LS-designs: Bitslice encryption for effcient masked software implementations. To appear in the proceedings of FSE 2014.