My implementation of a stream cipher with a basic pseudo-random generator for the keystream can be found here

How it works

Stream ciphers work by taking a original message, and using the bitwise exclusive-or (XOR) operation on it with a keystream of equal length. The result will be a cipher stream which doesn’t resemble the original in anyway. This can then be sent over some unsecure network and because of how the XOR operation works, by using the same keystream with the now cipher stream, the original message is revealed.

The keystream must be as long as the message. And if the message is some data file, then this could be Gigabytes long! Therefore rather than sharing keystreams, a key seed is shared. This is fed into a pseudo-random keystream generator both participants both have. As a pseduo-random generator will generate the same set sequences from a common seed, both participants will generate an identical keystream.

Perfect Secrecy

A one-time pad is a term used for a keystream that is random across the whole of the orginal message, with no repeating patterns. Further, the keystream is not used across multiple exchanged messages. A one-time pad keystream is a requirement for perfect secrecy. If perfect secrecy is achieved, the only possibly successful attack would be to brute force the keystream. Which for any reasonable length message would be not realistically possible as the complexity increases exponentially. Even if the message is below some safe threshold, just pad out either end of the message with a sufficient amount of garbage values. This is provided the keystream generation method is unkown to the attacker, otherwise they would only need to bruteforce the seed, which will have a much smaller range of values.

I really like stream ciphers. They are so simple conceptually and can provide perfect secrecy if used correctly! But have their limits… [Explain disadvantages]

A many-time pad is when the keystream repeats itself within or between messages. The cipher streams generated from the same keystreams can be processed to reveal information of the many-time pad keystream and therefore original messages.

There is still a lot of work involved with discovering the keystream with a many time pad. I’m not aware of any programs that can do it autonomously but tools can be used along with human intuition to discover it. I may investigate and discuss these methods and tools further in a future post. But if you’re interested take a look at the video here

Exchanging Keys

So for a stream cipher to be used, a seed value must be shared between two participants who also have a common method for generating the keystream. This is a problem and a safe/secure method needs to be decided on.

Here are some possible methods: * The seed could be communicated with through the same network as the messages. This is not safe as obviously if the messages can be seen, so can the seed. * It could be hidden with some other encryption method, but then that method will be the new weakness and point of attack. * The participants could meet in person, and physically exchange the seed. Probably one of the safest ways outside of the “cryptography world” but obviously physical concerns. * Two synchonized PRGs with same seed. I think this works really well however problematic if messages go missing or systems powerdown/program crash then will need setting up again.

An idea I thought of, though I’m sure many have before. Would be to come up with a little equation agreed upon by the participants on how to calculate the seed using changing universally obtainable values. An example would be the current date. As each new day begins, the current date which can comprise of the year, month, day is input into some equation.

Let’s call it:

seed = 3 * year + 2 * month + 1 * day

This would work reasonably well, as a new keystream would be used each day. However, if more than one message is sent that day, this will loose perfect secrecy. I think this could be taken account for by adding to the equation a value for the number of the message sent that day.

seed = 3 * year + 2 * month + 1 * day + 10 * messageID

Now a new keystream will be generated for each new message that day by each participant. As long as they both have the same method/Pseudo-random generator for generating the keystream and follow the agreed upon seed generation, common one-time pads should be achievable between participants.

More Advance Discussion

Now there is still a lot of interest and concern with the method of generating the keystream using Pseudo-random generators. Apparently not all pseduo-random generators are regarded as semantically secure. For a generator to be semantically secure, the chance of predicting the next bit should be negligible. Otherwise this predictability can be abused by an attacker.

This topic will be continued in a future blog.