Lightweight Stream Ciphers

From CryptoLUX
Jump to: navigation, search

Lightweight stream ciphers are lightweight cryptographic primitives. We list on this page stream ciphers of historical or practical importance (A5/1, E0) as well as profile 2[note 1] ciphers of the eSTREAM portfolio.

Designing Stream Ciphers

Description and Desirable Properties

Given a key K and an initialization vector IV, a stream cipher generates a keystream, i.e. a stream of bits which are simply xored with the plaintext to generate the ciphertext. Such ciphers are called synchronous if the keystream is independent of the ciphertext or asynchronous if it does. Asynchronous ciphers can be used for authenticated encryption.

The IV is known by the attacker and may also be controlled by her. It must "impossible" to retrieve the key even if large parts of the keystream are available. Furthermore, if the cipher is based on an internal state updated every time a part of the keystrem is generated (most stream ciphers correspond to this description), then the internal state must be large enough to prevent so-called Time-Memory-Data Trade-off based attacks. For instance, A5/1 is vulnerable to such an attack[1].

Possible Components

A simple way to build a stream cipher is to use a regular block cipher in counter-mode. However, the most common method to initialize an internal state of n bits using the key and initialization vector and then repeat the following:

  1. Generates b bits of keystream using the content of the internal state.
  2. Apply a function to update the internal state.

A possible method to build an internal state easy to update is to use so-called Feedback Shift Registers (FSR). These are arrays of words which, at each round, are updated as follows:

  1. The content of some fixed cells (the taps) is used to compute a new word w.
  2. The content of the array is shifted to the left so its last element is discarded.
  3. w is inserted in the first cell.

If the function used to compute w is linear, we have a Linear FSR or LFSR. Otherwise, we have a Non-linear FSR or NFSR. The Feedback with Carry Shift Register used by the FCSR-based stream-ciphers is another such construction. The words can be bits (most of the cases) but it is not necessary.

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 IV size attacks/weaknesses Technology used area (#GE) throughput (Mb/s @ 100kHz) power consumption (µW) reference (implementation)
A5/1 Unkown 19-bits + 22-bits + 23-bits LFSR's 64 0
  • TMD trade-off[1]
-- -- -- -- --
ChaCha Bernstein[2] cr.yp.to 256 bits 256 64
  • Differential attack (6-7 rounds)[3]
-- -- -- -- --
E0 Bluetooth SIG 25-bits + 31-bits + 33-bits + 39-bits LFSR's 128 0
  • Conditionnal correlation[4]
-- -- -- -- --
F-FCSR-16 v3 Arnault et al. SAC 09[5] one 256-bits FCSR 128 128 -- -- -- -- --
F-FCSR-H v3 Arnault et al. SAC 09[5] one 160-bits FCSR 80 80
Grain Hell et al. IJWMC 07[6] 80-bits LFSR + 80-bits NFSR 80 64
  • Linear approximations[7]
  • Dynamic cube testers[8]
0.13 µm 1294 ∕ 3239 0.10 / 1.60 3.3 / 9.3 [GB 07][9]
IEEE IS 06[10] 128-bits LFSR + 128-bits NFSR 128 96 1857 / 4617 0.10 / 3.20 4.3 / 14.8
MICKEY v2 Babbage et al. NSCD 08[11] Two 100-bits LFSR's 80 0-80 0.13 µm 3600 -- -- ECRYPT[13]
Two 160-bits LFSR's 128 0-128 -- -- -- --
SNOW 3G Johansson et al. 3GPP 06[14] 512 bits (16 32-bit words) 128 128
  • Multiset distinguisher[15]
-- -- -- -- --
Trivium De Cannières et al. NDSC 08[16] 288 bits (three LFSR's) 80 80
  • Algebraic (Bivium)[17]
  • Conditionnal differential[18]
0.13 µm 2599 / 2801 / 4921 0.10 / 0.80 / 3.20 5.6 / 6.4 / 14.3 [GB 07][note 3][9]

Descriptions

A5/1

This cipher is still used today in the GSM protocol and is more than two decades old. It has a small key size and, even worse, cryptanalysis of the cipher exist allowing practical attacks. This cipher is broken (see [BSW01][1], among other) and is on this page because of its wide use rather than the quality of its design.

The registers are irregularly clocked: each one has a control bit and, at each iteration, the registers with a control bit equal to the majority of all the control bits are clocked. However, this system leads to a loss of entropy as different register states can lead to identical states.

ChaCha

  • Article: ChaCha, a variant of Salsa20, cr.yp.to'08[2]
  • Authors: Bernstein, Daniel J.

ChaCha is a variant of the stream cipher Salsa20[19]. Salsa20 was selected to be part of the eSTREAM portfolio. ChaCha uses the same structure as Salsa but the round function is modified. In particular, all operations only have two operands. The pseudo-code for a "quarter round" of ChaCha is provided below, where "⊞" denotes addition modulo 232, "⊕" denotes XOR and "<<<" denotes a rotation to the left. The default number of rounds, like for Salsa, is 20.

a ⊞= b; d ⊕= a; d <<<= 16;
c ⊞= d; b ⊕= c; b <<<= 12;
a ⊞= b; d ⊕= a; d <<<= 8;
c ⊞= d; b ⊕= c; b <<<= 7;

E0

E0 is a lightweight streamcipher which is very widely used because it is used by the Bluetooth protocol. It is based on 4 regularly clocked LFSR's and 4-bits Finite State Machine, the "blender" FSM.

There has been several attacks on E0 and, while they are much more efficient than brute-force, they are not yet practical due to the large amount of keystream required.

FCSR-based Stream-Ciphers

An example of simple FCSR.
  • Article: A new approach for FCSRs, SAC 09[5]
  • Authors: Arnault, F., Berger, T., Lauradoux, C., Minier, M., & Pousse, B.

The first stream ciphers based on a component called FCSR were introduced in[20] and were part of the eSTREAM final Profile 2 portfolio[note 1]. However, the were practically broken by Hell and Johansson[21], which caused their removal from this list. The designers then published two other iterations of their design. In the last one (the one we are interested in), they changed significantly the structure of the FCSR. A FCSR is (now) a Feedback Shift Register with cells of b bits where, at each clock, a cell can updated in two ways:

  1. if it receives no feedback (m4 on the figure on the right) then its content at time t+1 is the content of the previous cell (m0 in the case of m4) at time t.
  2. if it does receive a feedback, then it has an added memory of b bits corresponding to carry bits. The (possibly shifted) feedback, the previous cell and the content of the carry cell at time t are added bitwise: the small weight bit is the new value of the cell at t+1 and the large weight bit is stored in the carry cell.

The aim is to have a FSR which is not updated linearly. Furthermore, the authors prove that the internal state of the FCSR is on its main cycle after about log(n) clockings, n being the total length of the register, meaning that clocking the FCSR is the same as applying a permutation on its internal state and thus that no entropy is lost. However, there can be a significant amount of collisions during the very first clockings, before the main cycle is reached. These were used to attack GLUON.

To generate the stream, some of the cells are xored after rotations and generate the stream (filtering operations). The FCSR has a so-called 2-adic structure which is broken by the use of xor here.

The lightweight hash function GLUON is also based on a FCSR. It can be seen as a T-Sponge were the update function is a derivative of these stream ciphers.

F-FCSR-H v3

The FCSR used by this instance has 1 bit per cell, 82 feedbacks, and 8 bits are filtered at each call of the filter. The cipher itself requires 80-bits key and 80-bits IV.

F-FCSR-16 v3

The FCSR used by this instance has: 1 bit per cell, 130 feedbacks, 16 bits are filtered at each call of the filter. The cipher itself requires 128-bits key and 128-bits IV.

Grain

Grain-80
Grain-128
  • Article: A stream cipher proposal: Grain-128 (Grain-128), IEEE IS 06[10] and Grain: a stream cipher for constrained environments (Grain-80), IJWMC 07[6]
  • Authors: Hell, M., Johansson, T., Maximov, A. (only Grain-128) , & Meier, W.

Grain is part of the eSTREAM portfolio, profile 2[note 1]. It is based on two different FSR's whose clocking influence each other in such a way that the update is not linear and a non-linear combining function which generates the key stream from the content of the FSR's. However, the system can still be linearized in a way which leads to actual cryptanalysis[7].

Grain is one of the inspirations for the design of the lightweight hash function QUARK.

MICKEY v2

The structure of MICKEY.
  • Article: The MICKEY stream ciphers, New Stream Cipher Designs 08[11]
  • Authors: Babbage, S., & Dodd, M.

MICKEY is based on two LFSR which are irregularly clocked. Hong and Kim[12] found a Time-Memory-Data tradeoff with sampling attack on the first version of the cipher and identified a loss of entropy: if we consider the content of the two LFSR's like one element of an appropriately sized space, the output of the function used to update shrinks as it is iterated. As a counter-measure against these two issues, the designers updated MICKEY to MICKEY v2, a version relying on identical mecanism but with a significantly larger space size.

MICKEY is part of the eSTREAM portfolio, profile 2[note 1]. While implementation results are available for MICKEY v1 in [GB 07][9], these are not valid for MICKEY v2.

SNOW 3G

The SNOW 3G stream cipher.
  • Article: Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2& UIA2. Document 2: SNOW 3G Specifications, 3GPP 2006[14]
  • Authors: Thomas Johansson and Patrik Ekdahl

SNOW 3G is a stream cipher chosen by the 3GPP consortium. It uses a 128-bit key and a 128-bit IV. It is an updated version of SNOW and SNOW 2.0.

It is based on a LFSR with 16 cells of 8 bits each and a finite state machine (FSM). The LFSR is updated using finite field arithmetic to compute the feedback cell. The finite state machine uses the S-Box and the MixColumn operation of the AES, although the field in which MixColumn is computed is not always the same.

Trivium

The Trivium stream cipher.
  • Article: Trivium, New Stream Cipher Designs 08[16]
  • Authors: De Canniere, C., & Preneel, B.

Trivium is part of the eSTREAM portfolio, profile 2[note 1].

To bridge the gap between the theoretical understanding of block ciphers and stream ciphers, the authors adapt the framework used by the designers of block ciphers to the design of stream ciphers. The paper where trivium is introduced[16] contains an extensive theoretical study of this approach and trivium is simply a suggested output for such a process. In particular, the limitation of the linear correlations between the bits was one of the main focus. Although the general idea is to reuse block cipher components such as, in particular, S-boxes, the fact that the bits of the keystream are generated one at a time would imply the use of 1x1 S-box. Instead, the designers use a xor with bits from an external (though perhaps biased) source. In trivium, there are three LFSR which are preceded by a "S-box" consisting in the logical AND of the last bits of the two other LFSR's.

This algorithm has a key size and an IV size of 80 bits and an internal state size of 288 bits but the authors also provide a weaker target for cryptanalysis which uses only two LFSR's: Bivium.

Trivium is one of the inspirations for the design of the lightweight block ciphers KTANTAN and KATAN.

Notes

  1. 1.0 1.1 1.2 1.3 1.4 The eSTREAM portfolio is divided in two profiles as explained on the eSTREAM webpage.

    The eSTREAM portfolio ciphers fall into two profiles.

    • Profile 1 contains stream ciphers more suitable for software applications with high throughput requirements.
    • Profile 2 stream ciphers are particularly suitable for hardware applications with restricted resources such as limited storage, gate count, or power consumption.

    While some of the submissions to eSTREAM were submitted for both profiles, none made it to the two final portfolios which tends to indicate that optimizing a design for hardware and software at the same time is no easy task.

  2. To the best of our knowledge.
  3. The measures correspond to respectively a 1-bit datapath, an 8-bits datapath and a 64-bits datapath.

References

  1. 1.0 1.1 1.2 Biryukov, A., Shamir, A., & Wagner, D. (2001, January). Real time cryptanalysis of A5/1 on a PC. In Fast Software Encryption (pp. 1-18). Springer Berlin Heidelberg. pdf at springer.com
  2. 2.0 2.1 Bernstein, D.J, The Salsa20 family of stream ciphers (2008) pdf at cr.yp.to
  3. Aumasson, J. P., Fischer, S., Khazaei, S., Meier, W., & Rechberger, C. (2008, February). New features of Latin dances: analysis of Salsa, ChaCha, and Rumba. In Fast Software Encryption (pp. 470-488). Springer Berlin Heidelberg. pdf at springer.com
  4. Lu, Y., Meier, W., & Vaudenay, S. (2005, January). The conditional correlation attack: A practical attack on Bluetooth encryption. In Advances in Cryptology–CRYPTO 2005 (pp. 97-117). Springer Berlin Heidelberg. pdf at springer.com
  5. 5.0 5.1 5.2 Arnault, F., Berger, T., Lauradoux, C., Minier, M., & Pousse, B. (2009, January). A new approach for FCSRs. In Selected Areas in Cryptography (pp. 433-448). Springer Berlin Heidelberg. pdf at eprint.iacr.org
  6. 6.0 6.1 Hell, M., Johansson, T., & Meier, W. (2007). Grain: a stream cipher for constrained environments. International Journal of Wireless and Mobile Computing, 2(1), 86-93. pdf at ecrypt.eu.org
  7. 7.0 7.1 Berbain, C., Gilbert, H., & Maximov, A. (2006, January). Cryptanalysis of grain. In Fast Software Encryption (pp. 15-29). Springer Berlin Heidelberg. pdf at ecrypt.eu.org
  8. Dinur, I., & Shamir, A. (2011, January). Breaking Grain-128 with dynamic cube attacks. In Fast Software Encryption (pp. 167-187). Springer Berlin Heidelberg. pdf at eprint.iacr.org
  9. 9.0 9.1 9.2 Good, T., & Benaissa, M. (2007). Hardware results for selected stream cipher candidates. State of the Art of Stream Ciphers, 191-204. pdf at crypto.rub.de
  10. 10.0 10.1 Hell, M., Johansson, T., Maximov, A., & Meier, W. (2006, July). A stream cipher proposal: Grain-128. In Information Theory, 2006 IEEE International Symposium on (pp. 1614-1618). IEEE. pdf at psu.edu
  11. 11.0 11.1 Babbage, S., & Dodd, M. (2008). The MICKEY stream ciphers. In New Stream Cipher Designs (pp. 191-209). Springer Berlin Heidelberg. pdf at springer
  12. 12.0 12.1 12.2 Hong, J., & Kim, W. H. (2005). TMD-tradeoff and state entropy loss considerations of streamcipher MICKEY. In Progress in Cryptology-INDOCRYPT 2005 (pp. 169-182). Springer Berlin Heidelberg. pdf at springer
  13. ECRYPT European Network of Excellence in Cryptology II Lightweight Stream Cipher Lounge, http://www.ecrypt.eu.org/lightweight/index.php/Stream_ciphers
  14. 14.0 14.1 UEA2&UIA, I. A. (2006). Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2& UIA2. Document 2: SNOW 3G Specifications. Version: 1.1. ETSI. pdf at qtc.jp
  15. Biryukov, A., Priemuth-Schmid, D., & Zhang, B. (2010, January). Multiset collision attacks on reduced-round SNOW 3G and SNOW 3G. In Applied Cryptography and Network Security (pp. 139-153). Springer Berlin Heidelberg. pdf at springer.com
  16. 16.0 16.1 16.2 De Canniere, C., & Preneel, B. (2008). Trivium. In New Stream Cipher Designs (pp. 244-266). Springer Berlin Heidelberg. pdf at springer
  17. McDonald, C., Charnes, C., & Pieprzyk, J. (2007). An Algebraic Analysis of Trivium Ciphers based on the Boolean Satisfiability Problem. IACR Cryptology ePrint Archive, 2007, 129. pdf at eprint.iacr.org
  18. Knellwolf, S., Meier, W., & Naya-Plasencia, M. (2012, January). Conditional differential cryptanalysis of Trivium and KATAN. In Selected Areas in Cryptography (pp. 200-212). Springer Berlin Heidelberg. pdf at springer.com
  19. Bernstein, D.J, The Salsa20 family of stream ciphers (2005). eSTREAM submission. pdf at cr.yp.to
  20. Arnault, F., & Berger, T. P. (2005, January). F-FCSR: design of a new class of stream ciphers. In Fast Software Encryption (pp. 83-97). Springer Berlin Heidelberg. pdf at springer
  21. Hell, M., & Johansson, T. (2008). Breaking the F-FCSR-H stream cipher in real time. In Advances in Cryptology-ASIACRYPT 2008 (pp. 557-569). Springer Berlin Heidelberg. pdf at lu.se