Stream Ciphers part A

These are lecture notes from my Computer Science course.

What are Stream Ciphers

Using a key ‘stream’ to encode plaintext. For example the Vernam Cipher works by generating a random bit stream and then XORing that stream on a bit by bit basis. The same bit stream can be generated by the receiver and then XORing that with the encrypted stream to get the plaintext back.

Linear Feedback Shift Registers

For generating a random stream. Bit shift a set of bits and xor the values to insert a new bit at one end. We want the stream to be random looking, and so the stream should not repeat itself too quickly. These shift registers are essentially finite state machines so must repeat themselves eventually. The maximal period for an n-bit register is 2^n-1. Some ‘tap sequences’ (the start stuff I think) give less than that.

Even with 64-bits, it’s not safe. Once you know a very small amount of plaintext then you can calculate the corresponding key stream for that amount of plaintext. Say you know 32-bits of it; you only then need to try 2^32 combinations for the rest.

So LFSRs are rubbish, but very easy to implement and execute quickly. Maybe we can fix it; use a different way of extracting the key stream (currently just taking the bit that falls off the end)? Or combine several streams.

Using a function on the LFSR register

A boolean function on n-inputs can be represented in minimal sum (XOR +) of products (AND .) form. Um. Apparently this is just like Karnaugh maps. Apparently.

You can also do the same by having multiple LSFR streams, and then using a similar function on the output of those. But beware; if your function is just something like stream1 XOR stream2 and the streams are 32-bits, then although the key size is 64-bits, you really only have 32-bits of information.

tl;dr – using linear functions is bad. Even some non-linear functions are practically linear functions (don’t just add XOR x1.x2.x3 to the end as then it’s only non-linear 1 time (when x1 x2 and x3 are all 1s)

This entry was posted in cry, lecture. Bookmark the permalink.