The Basics of Crypto 5: Stream Ciphers

Stream ciphers are symmetric key ciphers similar to block ciphers but operate in a very different way. A stream cipher takes the key and some other sets of random data and uses them to produce a string of random bits of equal length to the plaintext (also known as the keystream) which is then XORed against the plaintext similarly to how a one time pad works.

To clear up what a nonce is in the context of cryptography, it means "number used once". You should only use the nonce once because if you used it twice (or more times) and someone decrypted the first cipher text they could recover the keysteam and use it to decrypt all other plaintexts encrypted with the same keysteam.

There are two types of stream cipher we will be covering in this instalment (stateful and counter based) and then we will briefly cover hardware and software based stream ciphers.

The Difference Between Stateful and Counter Based Stream Ciphers

In reality there is not a great amount of difference between stateful and counter based stream ciphers although the minor differences that do exist have some meaningful affects. The difference is essentially whether the counter is secret or not, stateful ciphers keep the counter (referred to as the state in this context) secret where counter based ciphers do not. This in practise means that the stateful cipher uses the nonce, key and the state to generate a stream of random bits and then updates the state for each iteration until the key steam is equal to the length of the plaintext. A counter based cipher creates the keystream through combining the nonce, counter and key until the keysteam is equal in length to the plaintext.

Hardware Stream Ciphers

Hardware in relation to cryptography is generally focussed around application specific integrated circuits (ASICs), programmable logic devices (PLDs) and field programmable gate arrays (FPGAs) and if you are reading this and thinking "this sounds a lot like the stuff used in cryptocurrencies" then you can probably guess where this series is going!

The hardware implementation of a cipher is an electronic circuit specially designed to implement one specific algorithm and can not be used for anything else. This renders it useless for most normal applications and as such is dedicated hardware for cryptographic purposes.

Feedback Shift Registers (FSR)

Feedback shift registers are heavily utilised in hardware based cryptography as they are reliable and well understood. An FSR is essentially an array of bits and an update function. These bits are stored in memory (most likely in a dedicated register) and to get each bit the register is left shifted by 1 bit and then the update function is performed on the register. The left-shift operator (<< X) causes the bits in shift-expression to be shifted to the left by the number of positions specified by additive-expression. The bit positions that have been vacated by the shift operation are normally zero-filled however in this context they are set as the output of the FSR update function. In the example below the values are coloured to help keep track of them (i.e. the red values are always the same value):

Consider the below example where the update function XORs all the bits together and the initial value is 0101:

0101

The update function now runs predicting:

f(0101) = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0

These bits are all now shifted one place to the left with the result of the XOR (0) being added as the new bit giving the current state:

1010

The update function is then run again producing the following:

f(1010) = 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0

All bits are now shifted to the left again with the result of the update being added as the new bit producing the new state of:

0100

After a number of iterations we will return to our initial state (in this instance it is 5, obviously this is a simplified example for demonstration purposes and a real FSR would take many more) this is called the period of the FSR. It is advisable to use an FSR with a large period value if you intend to implement one for real world application.

Linear Feedback Shift Registers (LFSR)

A linear feedback shift register is similar to a standard feedback shift register except that it performs an additional liner (hence the title) mathematical operation on a set of bits chosen to maximise the period of the LFSR, they are very fast and have historically been used in the generation of stream ciphers and as such are included here. I will not be going into LFSRs in much detail as they are inherently insecure however more information can be found about them here. It is possible to improve the security of an LFSR by implementing a non linear function alongside the linear function however there are still attacks that can compromise these. Information on two of these attacks can be found here and here.

Non Linear Feedback Shift Registers (NFSR)

Non linear feedback shift registers work very similar to LFSRs except that instead of a linear feedback function they have a non linear feedback function. This in reality means that instead of just using a XOR like the LFSR the feedback function can include AND and OR operations as well. This has positives and negatives, the positive being that they are cryptographically stronger than LFSRs and the negatives being that for operations with a large bit size it is impractical to calculate the period size of the NFSR. However this problem can be overcome by combining the maximum period achieved by the LFSR and the cryptographic security provided by the NFSR which is how the Grain-128a cipher operates.

Grain-128a takes a 128 bit key and a 96 bit nonce. A pre-output function has an internal state size of 256 bits consisting of a 128 bit NFSR and a 128 bit LFSR. Producing a minimum period of 2^128 -1 and at the same time the NFSR provides cryptographic strength. A further non linear filter function runs alongside the NFSR in order to further increase cryptographic strength. An image detailing the Grain-128a algorithm can be seen below:

At the time of writing there are no known methods for cracking the grain-128a encryption scheme when implemented properly.

Software Based Stream Ciphers

Software based stream ciphers use the standard set of instructions provided by the hardware they are running on in order to carry out the necessary operations. They are not dissimilar to any other piece of software running on a machine in the way that they are treated by the hardware. Software based stream ciphers are obviously slower than the hardware based counterparts however they are cheaper to implement as they do not require dedicated hardware.

Two notable software based stream ciphers are RC4 (used in TLS and WEP, this cipher is insecure and should not be used anymore) and Salsa20/ChaCha which is better. AES-CTR is also very popular however it is a block cipher modified to function as a stream cipher and was covered in the previous instalment of this series. RC4 is vulnerable to numerous attacks more details of which can be found here.

The core function of Salsa20/ChaCha maps a 256-bit key, a 64-bit nonce, and a 64-bit counter to a 512-bit block of the key stream. This gives Salsa20/ChaCha the unusual advantage that the user can efficiently seek to any position in the key stream in constant time. More information on Salsa/ChaCha can be found here. At the time of writing there are no practical attacks against the Salsa20/ChaCha cipher.