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.
A key stream is, simply put, an effectively infinite stream of symbols that are used to permute the input
A stream cipher typically has
A stream of input symbols
- Synchronous: The keystream is generated independently of the texts (plain and cipher)
- Self-Synchronising: The keystream is generated as a function of the key and a fixed amount of previous ciphertext.
The Vernam Cipher
This is a stream cipher defined on
This cipher is easily implemented in Haskell as:
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
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:
- We have to generate truly random data (not easy)
- We have to securely communicate the keys
- The key must be as long as the message
Feedback Shift Registers
FSRs are used to generate pseudo-random keystreams from (probably random) seeds.
An FSR consists of a function
At each step of computation, an FSR adds the first element in the queue
to the output then calculates
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]
An LFSR is an FSR with function
As a result this is understood as a function which selects some positions
in the queue and sums them
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.