Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

Stream and Block Ciphers

When it comes to computer encryption techniques, we tend to think of two basic types of cipher: stream and block.

One Time Pad

Before we look at stream and block ciphers, we need to look at one of the least efficient, yet most perfect encryption techniques ever designed: the One Time Pad.

Suppose every letter of the alphabet is assigned a number between 0 and 25. You have a message that you want to encrypt, so you generate another message the exact same length as the original, but with one major difference: this message is 100% RANDOM. Every letter in the second message is chosen randomly, so there’s no way for an attacker to guess what any given letter of that message would be.

Then, you shift each letter of the first message by the number value of the second message. Because there’s no way to know what any letter of the second message was, there’s no way to guess the original message from the encrypted message.

Perfect!

…well, not so perfect. Unfortunately for us, there are two major issues with the one time pad encryption:

1. You need to safely get the random message to your intended recipient(s)

2. You need to create a NEW random pad EVERY TIME you send a new message, or the advantages fall apart

The first issue is probably the biggest – if you can’t safely send the first message, how on earth do you expect to safely send the second? But even if you DO have a way to get the second message safely to the other side (maybe you share it in person with the recipient), you need a new pad for every message. Between these issues, there’s just no reliable way to use a One Time Pad in the digital world.

Stream Ciphers

A Stream Cipher produces a random or semi-random stream which is used to encrypt your data in transmission. This technique is probably closest to the one-time-pad, because we basically create a not-exactly-random one-time-pad for every message, and we expect the recipient to be able to produce the same not-exactly-random one-time-pad on their end.

Most stream ciphers basically work like this:

1. Define a complicated algorithm that can produce an endless stream of what looks like random values

2. “Seed” the algorithm with a password which sets the initial value of the algorithm

3. Run the algorithm until you’re done sending messages

As an easy example, suppose I wanted to send you some numbers, but I didn’t want anyone else to see them. I could use a simple math problem like this:

y = x^3 + x ^ 2 + 3

Our “password” can be the number 5. We can create a stream like this:

x = 5

y = 125 + 25 + 3 = 153

x = 153

y = 153^3 + 153^2 + 3

x = y

This will create a stream of digits that can look reasonably random (unless you’re a math whiz, of course). I can use this algorithm to create a stream of digits that I just add to the numbers that I want to send you (subtracting 10 when necessary, of course). On your end, you create the same stream of digits and just subtract them from what I sent you, and PRESTO! You have the numbers I wanted you to get.

Block Ciphers

The easiest ciphers are probably block ciphers. For these, we apply an algorithm a bunch of times on our data, and we send it out. The Playfair cipher, Vigenere cipher, and Caesar cipher are all examples of classic block ciphers, and they show the biggest problem:

It’s not that hard to find patterns in a simple block cipher.

If I shift every letter in a message by 13 letters, I guarantee you that a computer could figure out the pattern faster than I could type out the message. Because there are only so many ways to apply a block cipher, you can usually pick out the patterns and solve it fairly quickly.

Unless…you use a few simple ciphers, and you repeat them in a special order.

If I were to shift the first half of a message based on the first letter, then rotate it 13 spaces right, then repeat until I’d covered the entire message three times, it would look basically random. It’ll be harder to find any patterns (because common techniques look for some kind of repetition, which we beat with prime-number rotations), and the message is still pretty easy to to decrypt if you know the algorithm.

A mathematician named Claude Shannon identified that the key aspects of a good encryption are confusion and diffusion, which when applied allow a small change in the input to become a substantial and spread-out change in the output. Because (at least in theory) our block cipher will produce such a change, we can be reasonably sure that it will successfully encrypt our messages. A better example would, of course, be the DES standard, which we will look at soon.

The Best Cipher

Which is better: block ciphers or stream ciphers? The correct answer is…no.

Stream ciphers are great, but the algorithm can be fairly easy to guess.

Block ciphers are great, but the algorithm can be fairly easy to guess.

The correct answer is to create an algorithm that COMBINES stream cipher techniques and block cipher techniques to produce something that is easy for the intended recipient to decrypt, but isn’t worth an attacker’s time to figure out.

photo by: