You are here

Matlab, RC4, and Crypto-Graphics

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.

Developing the Example

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

  • Create a block cipher in Matlab
  • Apply the block cipher to 8-bit values stored in a 3D matrix
  • Create procedures to apply the cipher using a block cipher mode, like CBC

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:

 

Plaintext smiley face used in block encryption examples

RC4 in Matlab

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:

  • rc4key - takes a vector of byte values and returns a 256-byte key schedule vector.
  • rc4out - takes the key schedule and 2 state variables (i and j) and returns the next byte of key stream, along with an updated key schedule and state variables.

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.

A First Attempt at an RC4 "Block Cipher"

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:

 

Block cipher encryption, ECB mode, with a badly behaved cipher

 

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:

 

Failed CBC Encryption

 

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!

A Better RC4 "Block Cipher"

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:

 

smileyecbb

 

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:

 

Smiley face effectively enciphered with a block cipher and CBC m

 

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.

RC4 Matlab Files

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.

  • rc4key - takes a vector of byte values and returns a 256-byte key schedule vector.
  • rc4out - takes the key schedule and 2 state variables (i and j) and returns the next byte of key stream, along with an updated key schedule and state variables.
  • rc4set - takes an 8-byte input vector, uses it as part of the key, and generates 8 bytes of key stream. This plays the role of a trivial block cipher in creating these examples, though the function really serves as a block-oriented one-way hash.

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).

Post category: 

Comments

The ECB image I believe - same as the ECB encrypted linux penguin logo on the wikipedia article on this.

However the CBC mode and RC4 images - has to be a mistake or misunderstanding about how you use those modes, there should be nothing whatsoever visible - both should look like white noise.

Adam

Regarding the Wikipedia example: originally, the white noise image included a comment admitting that it was not produced by applying the block mode to the plaintext. The white noise image was, in fact, white noise. The image may have been replaced since then, but there's no way to tell. I've been working on this example to produce images that were actually the result of applying a block cipher mode.

I posted the failed mode image because the mistake displays itself so clearly. Most of the time, it's hard for a novice to see a cryptographic failure. However, the failure is not a mode failure. This is an RC4 problem, probably caused by using too small of a key: only 64 bits. Back when browsers used so-called 40-bit keys, they incorporated lots of salt to make the actual key length 128 bits. My successful example used the same mode logic, but the RC4 key was built from 64 bits of input and 64 bits of salt.

After I'd worked up this example I finally stumbled across AES implemented in Matlab, so now I'm thinking about redoing it all with AES.

dear sir

I m intresting in audio signal security, Im working now in cpyptography (using block cipher methods for audio security) can You help me, i need AES matlab code source please

with my best wishis

You can find AES in Matlab if you look elsewhere.

can you teach me this whole procedure in detail ?
i have an image and i want to learn how to encrypt it if i am provided with s boxes on top are you familiar with voice encyption and video encryption

If you want to experiment with encryption procedures in Matlab, then simply download the function files using your browser. Remove the .txt suffix from the file names, leaving Matlab's .m suffix. Then load them into Matlab. The functions work like any other user-defined Matlab function.

If you want to encrypt images and video in order to protect them from disclosure, then you should not be using RC4. Use an existing application program that encrypts files, or use volume encryption, like TrueCrypt.

I'm only using RC4 and Matlab to construct some simple crypto examples, not to protect data.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer