Lightweight Stream Ciphers
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.
Contents
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 socalled TimeMemoryData Tradeoff 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 countermode. However, the most common method to initialize an internal state of n bits using the key and initialization vector and then repeat the following:
 Generates b bits of keystream using the content of the internal state.
 Apply a function to update the internal state.
A possible method to build an internal state easy to update is to use socalled Feedback Shift Registers (FSR). These are arrays of words which, at each round, are updated as follows:
 The content of some fixed cells (the taps) is used to compute a new word w.
 The content of the array is shifted to the left so its last element is discarded.
 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 Nonlinear FSR or NFSR. The Feedback with Carry Shift Register used by the FCSRbased streamciphers is another such construction. The words can be bits (most of the cases) but it is not necessary.
Summary
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  19bits + 22bits + 23bits LFSR's  64  0 

          
ChaCha  Bernstein^{[2]}  cr.yp.to  256 bits  256  64 

          
E0  Bluetooth SIG  25bits + 31bits + 33bits + 39bits LFSR's  128  0 

          
FFCSR16 v3  Arnault et al.  SAC 09^{[5]}  one 256bits FCSR  128  128 

          
FFCSRH v3  Arnault et al.  SAC 09^{[5]}  one 160bits FCSR  80  80  
Grain  Hell et al.  IJWMC 07^{[6]}  80bits LFSR + 80bits NFSR  80  64 

0.13 µm  1294 ∕ 3239  0.10 / 1.60  3.3 / 9.3  [GB 07]^{[9]}  
IEEE IS 06^{[10]}  128bits LFSR + 128bits NFSR  128  96  1857 / 4617  0.10 / 3.20  4.3 / 14.8  
MICKEY v2  Babbage et al.  NSCD 08^{[11]}  Two 100bits LFSR's  80  080 

0.13 µm  3600      ECRYPT^{[13]}  
Two 160bits LFSR's  128  0128          
SNOW 3G  Johansson et al.  3GPP 06^{[14]}  512 bits (16 32bit words)  128  128 

          
Trivium  De Cannières et al.  NDSC 08^{[16]}  288 bits (three LFSR's)  80  80 

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 pseudocode for a "quarter round" of ChaCha is provided below, where "⊞" denotes addition modulo 2^{32}, "⊕" 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 4bits Finite State Machine, the "blender" FSM.
There has been several attacks on E0 and, while they are much more efficient than bruteforce, they are not yet practical due to the large amount of keystream required.
FCSRbased StreamCiphers
 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:
 if it receives no feedback (m_{4} on the figure on the right) then its content at time t+1 is the content of the previous cell (m_{0} in the case of m_{4}) at time t.
 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 socalled 2adic 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 TSponge were the update function is a derivative of these stream ciphers.
FFCSRH 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 80bits key and 80bits IV.
FFCSR16 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 128bits key and 128bits IV.
Grain
 Article: A stream cipher proposal: Grain128 (Grain128), IEEE IS 06^{[10]} and Grain: a stream cipher for constrained environments (Grain80), IJWMC 07^{[6]}
 Authors: Hell, M., Johansson, T., Maximov, A. (only Grain128) , & 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 nonlinear 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
 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 TimeMemoryData 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 countermeasure 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
 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 128bit key and a 128bit 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 SBox and the MixColumn operation of the AES, although the field in which MixColumn is computed is not always the same.
Trivium
 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, Sboxes, the fact that the bits of the keystream are generated one at a time would imply the use of 1x1 Sbox. 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 "Sbox" 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.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.
 ↑ To the best of our knowledge.
 ↑ The measures correspond to respectively a 1bit datapath, an 8bits datapath and a 64bits datapath.
References
 ↑ ^{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. 118). Springer Berlin Heidelberg. pdf at springer.com
 ↑ ^{2.0} ^{2.1} Bernstein, D.J, The Salsa20 family of stream ciphers (2008) pdf at cr.yp.to
 ↑ 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. 470488). Springer Berlin Heidelberg. pdf at springer.com
 ↑ 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. 97117). Springer Berlin Heidelberg. pdf at springer.com
 ↑ ^{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. 433448). Springer Berlin Heidelberg. pdf at eprint.iacr.org
 ↑ ^{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), 8693. pdf at ecrypt.eu.org
 ↑ ^{7.0} ^{7.1} Berbain, C., Gilbert, H., & Maximov, A. (2006, January). Cryptanalysis of grain. In Fast Software Encryption (pp. 1529). Springer Berlin Heidelberg. pdf at ecrypt.eu.org
 ↑ Dinur, I., & Shamir, A. (2011, January). Breaking Grain128 with dynamic cube attacks. In Fast Software Encryption (pp. 167187). Springer Berlin Heidelberg. pdf at eprint.iacr.org
 ↑ ^{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, 191204. pdf at crypto.rub.de
 ↑ ^{10.0} ^{10.1} Hell, M., Johansson, T., Maximov, A., & Meier, W. (2006, July). A stream cipher proposal: Grain128. In Information Theory, 2006 IEEE International Symposium on (pp. 16141618). IEEE. pdf at psu.edu
 ↑ ^{11.0} ^{11.1} Babbage, S., & Dodd, M. (2008). The MICKEY stream ciphers. In New Stream Cipher Designs (pp. 191209). Springer Berlin Heidelberg. pdf at springer
 ↑ ^{12.0} ^{12.1} ^{12.2} Hong, J., & Kim, W. H. (2005). TMDtradeoff and state entropy loss considerations of streamcipher MICKEY. In Progress in CryptologyINDOCRYPT 2005 (pp. 169182). Springer Berlin Heidelberg. pdf at springer
 ↑ ECRYPT European Network of Excellence in Cryptology II Lightweight Stream Cipher Lounge, http://www.ecrypt.eu.org/lightweight/index.php/Stream_ciphers
 ↑ ^{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
 ↑ Biryukov, A., PriemuthSchmid, D., & Zhang, B. (2010, January). Multiset collision attacks on reducedround SNOW 3G and SNOW 3G^{⊕}. In Applied Cryptography and Network Security (pp. 139153). Springer Berlin Heidelberg. pdf at springer.com
 ↑ ^{16.0} ^{16.1} ^{16.2} De Canniere, C., & Preneel, B. (2008). Trivium. In New Stream Cipher Designs (pp. 244266). Springer Berlin Heidelberg. pdf at springer
 ↑ 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
 ↑ Knellwolf, S., Meier, W., & NayaPlasencia, M. (2012, January). Conditional differential cryptanalysis of Trivium and KATAN. In Selected Areas in Cryptography (pp. 200212). Springer Berlin Heidelberg. pdf at springer.com
 ↑ Bernstein, D.J, The Salsa20 family of stream ciphers (2005). eSTREAM submission. pdf at cr.yp.to
 ↑ Arnault, F., & Berger, T. P. (2005, January). FFCSR: design of a new class of stream ciphers. In Fast Software Encryption (pp. 8397). Springer Berlin Heidelberg. pdf at springer
 ↑ Hell, M., & Johansson, T. (2008). Breaking the FFCSRH stream cipher in real time. In Advances in CryptologyASIACRYPT 2008 (pp. 557569). Springer Berlin Heidelberg. pdf at lu.se