Here is what those three images illustrate:
The first image is the plaintext. The second and third images are encrypted with a block cipher. The second one uses the block cipher without applying an encryption mode. The third one applies the exact same cipher with the cipher block chaining mode.
A block cipher encrypts data in fixed blocks. The old Data Encryption Standard (DES) encrypted 8-byte blocks. That is the size I use in these examples. The newer Advanced Encryption Standard (AES) uses 16-byte blocks.
Despite the encryption, we clearly see the smiley face in the second image. This is because the features in the image are larger than the cipher's block size.
In the third image, we don't just apply the block cipher to the image byte-by-byte, or block-by-block. Instead we mix the ciphertext of the previous block in with the plaintext we want to encrypt. This mixing causes the ciphertext to change from block to block, even when encrypting several blocks colored red, white, blue, or black. Thus, the image appears as random colored noise.
A properly encrypted image should look like random colored noise, with no visible patterns.
I used Matlab to develop my stream cipher example because Matlab handles images easily. There is built-in support for reading and writing common image formats like JPEG, GIF, and TIFF. Matlab also uses the obvious internal representation for an image: a 3D array. Two dimensions give the height and width in pixels, and the third provides 3 primary colors for each pixel. To make the whole thing work, I took the following steps
The hardest part was creating the block cipher. My initial web searches brought me to various garbage pages intended to capture academics looking for course materials. So I gave up before I managed to find Matlab's AES Toolbox, which implements the Advanced Encryption Standard.
Instead, I built a somewhat-functional version of RC4 and adapted it to behave (pretty much) like a 64-bit block cipher.
Let's start with the example plaintext. It is a 128 x 128 pixel image with three 8-bit color values. Here it is double sized for other graphics uses:
Yes, I know. RC4 is not a block cipher.
On the other hand, RC4 consists of maybe 3 dozen lines of code. There are simple block ciphers out there, but they usually rely on massive tables to represent S boxes or other transformation operations. It seemed easy, in theory, to implement RC4 in Matlab and then find a way to make it behave like a block cipher.
For this experiment, the "block cipher" needs one capability: when I give it a particular block of input, it will always yield that particular block of output. For best results, no two inputs should yield the same output. That would be fatal for a block cipher, but I can tolerate that in this example if it happens in only a tiny number of cases.
A real block cipher needs to work in both directions: I should be able to 'decrypt' the ciphertext back into the plaintext. However, my examples work fine without being able to decrypt. The 'block cipher' really works more like a hash than a cipher, except that I'm working with really small blocks.
Strictly speaking, I can't say that I successfully implemented RC4 in Matlab. This is embarrassing, given how simple RC4 is, but it's true. I implemented two Matlab functions:
These are superficially identical to RC4 descriptions I've found on the Internet. The functions were adapted from a C implementation but do not yield the same results as the C version. See below for a further discussion of the problems, along with links to Matlab source code for the functions.
The first attempt failed, but it failed in a visually interesting way.
To demonstrate block cipher modes, I don't really need a block cipher. All I need is a one-way hash that takes a fixed block size (8 bytes seems good) and emits the same block size.
I constructed the "rc4set" function which took an 8-byte vector and generated 8 separate one-byte results. Strictly speaking, there is no "key" in this algorithm. But each 8-byte input will produce a specific 8-byte output. Since I'm not decrypting, I don't care if it's reversible.
To encrypt the image, I wrote a nasty function that iterates through the image a row at a time. Since each pixel contains 3 bytes, I encrypt 2 2/3 pixels in one block of encryption. Here is what I got when I simply applied the block encryption directly:
This looks reasonable. We apply the block cipher to the pixels a row at a time. Since the pixels fall on odd boundaries with respect to encryption blocks, we get the corrugated effect. Even encrypted, the smiley face is obvious since its graphical features are much larger than the crypto block size.
Trouble arose when I tried to apply the CBC mode.
In cipher block chaining, you use exclusive-or (xor) to mix the ciphertext of the previously encrypted block with the plaintext of the next block. You then encrypt the mixed data to yield the ciphertext. In theory this should scramble the ciphertext so that there are no obvious patterns.
In fact, here's what I got:
The smiley face is much too apparent. CBC isn't exactly rocket science, so that couldn't be the problem. While I haven't analyzed this very much, I think we're seeing a very short cycle in my hastily constructed block cipher. After all, I'm running RC4 with a 64-bit key, and people rarely use it with less than a 128-bit key.
It's interesting that the failure exposes itself so clearly when encrypting a graphic!
If the problem is caused by ill-use of RC4, I ought to improve things by increasing the key size. So I rewrote the "rc4set" function to intermix 8 random bytes with the 8 input bytes. This yields 16 bytes (128 bits), a much more reasonable RC4 key.
Then I applied the new function to the image:
This still displays the degraded - but visible - smiley face. The image still has the corrugated effect, as expected, since we are still encrypting 2 2/3 pixels per 8-byte encryption block.
The real test comes when we apply CBC:
I don't know if this will stand up to serious cryptanalysis, but "it looks pretty random to me." At least, it's good enough for a graphical example.
Here is my attempt to implement RC4 in Matlab.
These functions seem to produce a tolerable stream cipher, but they do not implement an interoperable version of RC4. I tested the outputs against the RC4 implementation (a C program) listed in Wikipedia. The key schedule function in C yields a different key schedule than the one I get from Matlab. I haven't tested it extensively with different keys, but here's what I find: bytes 2 through 9 of the key schedule are randomly swapped with 8 other bytes in the key schedule.
I spent several hours checking the intermediate results and I can't find the problem. If anyone else does, please share the secret with me.
In any case, I concluded that the cipher works well enough to simulate a block cipher, so I used it to produce my examples.
Here are the source files - each link below takes you to a .txt file containing the procedure's source code.
Note: these functions are stored with a .txt suffix, but they are in fact properly formatted Matlab ".m" files. WordPress took umbrage at my using the .m suffix, so I added the .txt to bypass its concerns. Simply remove the ".txt" suffix to turn the files back into .m files.
Acceptable Use: These are tiny text files and it's pointless to assert ownership over them, especially since they don't work correctly. I would sincerely appreciate it if someone would figure out what's wrong and share the corrected files with me. It's either a flaw in my understanding of obvious-looking Matlab operations, or it's a problem with Matlab itself (unlikely).