Stream Ciphers

A stream cipher is an encryption scheme which treats the plaintext symbol-by-symbol (e.g. by bit, byte, or letter)

Security in stream ciphers is based upon a changing keystream rather than a complex function.

Keystreams

A key stream is, simply put, an effectively infinite stream of symbols that are used to permute the input

Mechanism

A stream cipher typically has $M = C = A$. That is to say that the message space, cipher space, and alphabet are identical.

A stream of input symbols $$m_1\ m_2\ m_3\ \cdots$$ is encrypted with the keystream $$e_1\ e_2\ e_3\ \cdots$$ to generate $$E_{e_1}\left(m_1\right)\ E_{e_2}\left(m_2\right)\ \cdots$$

Types

The Vernam Cipher

This is a stream cipher defined on $A=\{0,1\}$. Symbols in the keystream are combined with corresponding symbols in the message stream with exclusive-or.

This cipher is easily implemented in Haskell as:

1
2
vernam :: Key -> Plaintext -> Ciphertext
vernam = zipWith (/=) -- /= is equivalent to xor in a boolean context

This cipher is self-inverting, so to compute the inverse we would use

1
2
vernam' :: Key -> Ciphertext -> Plaintext
vernam' = zipWith (/=)

And yes: that is the same as the original function but with the types swapped. In fact I'm presuming that Ciphertext and Plaintext are both simply type aliases for String (as is Key) so both functions are entirely identical.

One Time Pad

If the key stream is chosen genuinely randomly and only ever used once then this cipher is a one time pad. Such a cipher has been proven to be unconditionally secure (as secure as it is possible to be).

The reasons we don't just use this for everything are many:

Feedback Shift Registers

FSRs are used to generate pseudo-random keystreams from (probably random) seeds.

An FSR consists of a function $f$ of $n$ inputs and a queue $q$ of $n$ values.

At each step of computation, an FSR adds the first element in the queue to the output then calculates $f\left(q\right)$ and pushes the result onto the back of the queue.

This could be implemented in Haskell as follows:

1
2
3
4
5
6
7
8
-- | fsr produces an infinite, pseudorandom 'a'stream from a
--   function f and a seed q.
--   For a classical FSR use 'a' = 'Bool'
--   Would be more efficient with a doubly linked list.
fsr :: ([a] -> a) -> [a] -> [a]
fsr f fq@(s1:q) = sn:(fsr f q')
    where sn = f fq
          q' = q ++ [sn]

Linear FSRs

An LFSR is an FSR with function $f$ determined by $$C\left(X\right) = 1 + c_1X + c_2X^2 + \cdots + c_nX^n$$ but you should ignore this function: it's more simple as: $$s_j=\left(c_1s_{j-1}+c_2s_{j-2}+\cdots+c_ns_{j-n}\right)\mod 2$$ which still looks a little complicated. It helps to understand that in a binary situation these $c_n$s are also binary.

As a result this is understood as a function which selects some positions in the queue and sums them $\mod 2$.

Apparently there's an elegant algebraic theory behind LFSRs that shows how to construct good ones (with nice statistical properties) but they are still insecure when a known-plaintext attack is possible.

In practical applications one would add some controlled non-linearity.

Back to Computer Security