IT Security Lab The Playground for IT Security Specialists and Pentesters

Image encryption with polyalphabetic ciphers – experimental approach

You see, the truth is I am not a cryptography geek at all. But it is happening that from time to time some question suddenly arises right in front of my eyes. And I just literally can't stop thinking until I would find an answer. You know this feeling, aren't you? It happened that one of things which recently did not give me a chance to sleep was closely related to cryptography.

I was quite curious about the data encryption algorithms. I asked myself: ok, text or data are basically complex patterns with some "regularities". So what about the data after encryption? Maybe there are some regularities too? If yes - what are they and how they may be discovered? Ciphered data we are often dealing with - are just bunch of letters and/or numbers. I don't know about you, but A4 page full with strange characters is not specially informative for me. ;) I would be good to find a way to make data well... more "visual". Did I say visual... So maybe we may use colours to emphasize some pieces of information? Hold on, what if we may play with images as data patterns and see what may happen with them after being encrypted? Human eye is a great tool for detecting some regularities. Maybe they can be found somewhere there? In addition we may also use some statistical tools to look at data from another angle. Couple of evenings and voila - I made a little research in this area and would like to share the results and my way of thinking with you. So if you don't afraid find yourself reading long text - come with me.

Objectives

1. Check if images may act as easy-recognizable data patterns to test the strengths of encryption algorithms: by "visual analysis" and also from statistical analysis's point of view.
2. Assure the right understanding of what "well encrypted" data really is.
3. Compare different encryption algorithms (polyalphabetic substitution, XOR, RC5, Serpent).

Introduction. Polyalphabetic cipher - what the hell is it?

As we will be dealing with the polyalphabetic substitution cipher - I would like to make a short review what is it and how it works. (FYI: for your convenience in all further illustrations you'd see - every unique character in a table has a unique colour.)

So in its simplest form the polyalphabetic substitution cipher rule looks like this:

Here the alphabet contains only letters [A..H] with 7 dictionaries (just to make it easier to understand). Btw, this thing is also well known as Vigenere's Square. The version of the Vigenere's cipher for the full alphabet may looks like this:

But now let's come back to our first tiny [A..H] cipher and define either a repetitive or running key and try to encrypt our data. :) See the example with the repetitive key: (1234) which is used to pick up appropriate alphabet for substitutions.

Source data:     A A A B B B C C C D D D E E E F F F
Repetitive key:  1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
Encrypted data:  A B C E B C E F C E F G E F G A F G 

You see how it works, right? Decryption is basically a reversing of the operation described above using the same key (that's why it's called "symmetric").

Now we may do the same but with the runnig key, which is much better. Why? Because it's a sequence of random numbers! Promises promises..., but where to get those numbers? Well you can roll a dice ;) but we are dealing with computers, so we may use a pseudorandom generator algorithms available with virtually every programming language. The trick is to set exactly the same initial random seed for a generator, so the sequence of numbers (which looks pretty random) will be exactly the same for encryption and decryption. Every source letter then would have a corresponding random number which will be used for selecting an appropriate alphabet. So a random seed number is the key. Ok, I am writing sample function which will generate a sequence I need. See the following pseudocode:

randomize(12345); //--- this is my key used to initialize generator

for i=0 to 100 do
begin
   print rand(1, 7); //--- generate random number from 1 to 7
end;

This is the sequence I may get:

 154427447163624441627243312534216261...

Now let's encrypt the message with this technique:

Source data:     A A A B B B C C C D D D E E E F F F
Running key:     1 5 4 4 2 7 4 4 7 1 6 3 6 2 4 4 4 1
Encrypted data:  A E D E C H F F A D A F B F H A A F

Looks nice isn't it! The encrypted string looks very different from the original one, so this would not be an easy peanut to crack, oh no. But hold your seatbelts my friend - now we may complicate life for cryptanalyst even more! Let us use slightly modified version of the encryption table:

See the difference? Previously every row (a dictionary) was kind of "shifted" one cell left and a first character was "wrapped" to the end. Here every row still contains all characters we need [A..H] but their positions in the alphabet are random. So we may combine this technique with the one described above (running key) which gives us really strong cipher which basically would require two things for the encryption/decryption: 1) the RND generator's initial seed and the 2) dictionaries table. (The table also may be generated by some algorithm, of course). So let's encrypt our simple message with the running key and modified substitution table:

Source data:     A A A B B B C C C D D D E E E F F F
Running key:     1 5 4 4 2 7 4 4 7 1 6 3 6 2 4 4 4 1
Encrypted data:  B A C H D G D D D G E G C G F A A D

Try to crack this one, dude. ;) Just FYI:  this is how the encryption table may looks like for the full A...Z charset and sample 22 different alphabets:

Ok, I hope everything described above was easy and clear. Now bell is ringing, so it's time to come to something slightly more complicated. Forget the boring text - let's play with images!

"The owls are not what they seem"* Encrypting images.

Every raster image can be treated as the sequence of bytes (or data stream) where every pixel is represented by three components: R, G, B. Every component has a value 0 - 255. There is no need to go deep into image data formats, we would use this one (24 bit RGB bitmap) as a simplest to understand and easiest to handle programmatically. See the illustration below:

If the data in selected pixels will be read as a sequence - this is what we would have for the first row of pixels:

R: 175		R: 144		R: 157		R: 167		R: 169
G: 137		G: 96		G: 108		G: 118		G: 112
B: 3		B: 3		B: 8		B: 6		B: 15

Sample data stream:

...175, 137, 3, 144, 96, 3, 157, 108, 3, 167, 118, 6, 169, 112, 15, ...

Each value is actually a one byte. Ok, so now we may use same approach as described in the previous chapter to encode/decode images. The only difference now is that the "alphabet" we are dealing with not [A...Z] - 26 values, but [0..255] - 256 values. The rest remains exactly the same. So let's define sample table which will be used for a binary data encryption (in this case - our images):

The length of every dictionary is fixed and equal to 256 elements. We assume that every "alphabet" (row) in this case is an array of bytes with values [0..255] placed in random order. The method of accessing appropriate value is also the same. See the example: how to get the substitution number for the source = 4, where the dictionary ID = 6.

We may manipulate numbers of such dictionaries in the table (we may use the only one substitution dictionary or thousands of them) and see how it helps us to encrypt our data. Cool. Now we have to answer one more question before starting our experiments. And the question is:...

What does it mean: "proper encryption"?

Ok, this is a source image:

Sample image 1

...and this is a kind of "encrypted" version. Here every byte is XOR'ed (or inverted). It is not the same as the original image, but can you recognize it?

Sample image 2

Of course you do! To say "it is encrypted" you would expect to have a result of our encryption function similar to random noise. So every RGB component of each pixel is a random number in between 0 and 255.

Sample image 3

Of course this, what may looks like random, can actually contains the hidden data. And this is exactly what we want.

So what is the difference image 3 and image 2? Obviously you see something on the first one and see nothing on the second. But let's try to count numbers of the same bytes in the image 2 and image 3 and build a frequency distribution curves. Yes, this is about Gaussian curve and I am telling you, don't be afraid, we will draw it right now:

The green one - is the distribution curve of random noise. The red one - is our image. Feel the difference? ;) Let's take a look at another example:

The image is different and the distribution (red line) is changed correspondingly. Now let's see something very simple:

Here the distribution is completely screwed, does not look as bell curve at all (note the red line again).

So now we know that:

• Statistical analysis may give us some interesting information about the image.
• The closer encrypted data to random noise (visually and statistically) - the better (the less chance some hidden patterns may be found there).

And now, ladies and gentleman...

The Experiment.

The small program was written, which naturally may be downloaded from [here] to test everything described above (you can get the binary and the source code in Delphi). User interface is rather self-descriptive, so let's start experimenting.

First image and one substitution dictionary is used.

Each time you click [encrypt] button - the program does the following:

• New random seed number is generated.
• Based on this number - the substitution tables (dicitionaries) are generated.
• Based on this number - the running key is generated.
• Program takes selected original image, encrypts it using the selected algorithm and its parameters and renders the result.
• Program calculates statistics and draws the distribution curve for the encrypted image. Program also draws reference curves for a "virtual image" of the same size 300x200 pixels: 1) green one - for pseudo-random numbers, generated by a function 2) blue one - curve for true random numbers (I borrowed some data from here).
• Program also takes encrypted image and decrypts it, aiming to test if everything works correctly.

The function used for the reference curve is a combination of a Fibonacci sequence (with lags of 97 and 33, and operation "subtraction plus one, modulo one") and an "arithmetic sequence" (using subtraction).

Ok, do you see the red curve? Looks familiar to the one you've seen before isn't it? Do you understand why? We are using the one substitution table only (one dictionary), so for every source byte there is a one possible substituted byte. So bytes are different, but the frequencies remains the same! Now look at the encrypted image - you still see something there, especially if you would press [Encrypt] button couple of times (or press [AutoRun]). So definitely the encryption method is far from ideal.

Now move the slider [Nr of dictionaries] to the right and see what happened.

The more dictionaries is in use - the more variations are for each of the source bytes. Now leave the program configured for 100 substitution tables and switch to another image:

Interesting, isn't it. The image is very simple, so even by having 100 different substitution tables (!!!) you can still recognize source pattern in encrypted data (press [Encrypt] button couple of times). Now let's try to increase the number of dictionaries.

Notice how the red curve becomes more and more close to the reference one. But even having 1000 dictionaries you can still find the combination where you can see a shadow of something in encrypted data. Keep attention to the right part of the encrypted image - it's slightly more dark then the left one.

There is another interesting way to catch "regularities" in encrypted image. You can play with the width and height of the image, changing it correspondingly. Because the data stream you have - may not contain the information about the width and height of the image hidden in (just a pure stream of bytes).

Once again - a human eye is our best detector. Move the slider to 100 dictionaries and select image 3. Then uncheck the checkbox [Decrypted], so the encrypted image will be copied here directly.

Move the cursor to the right side of the bottom image, then click and drag it to the right. You would notice that the image width is increasing and height is decreasing automatically. In effect the same number of bytes is rendered in the rectangle of different (continuously changing) proportions now. You immediately notice the diagonal lines - similar to the old broken TV with a wrong synchronization. You see - there is kind of pattern there! Play a little with altering image size. By changing width/height relation you may surprisingly quickly find the right combination.

Ok, now let's try to play the same game with one of the industry-standard algorithms, like RC5. Now you might see what the really good encryption is.

See the red curve now? Almost ideally overlaps the referenced ones. And don't expect to find any patterns in encrypted data this time (well, you may try of course...).

Ok, this is it. You may play with the program by yourself or modify the source code and add some new cool features. Hope it helped you a little bit better understand some ideas about data encryption combined with image processing. Don't forget to drop me a line in case you like the text, or even (or especially) if you think it's lame. Anyway - enjoy! :)

0100001101111001011100100110111001100110011100100010000001110011011...

cyrnfr sbyybj guvf yvax uggcf://plorefrphevglpunyyratr.bet.hx/834wgc.ugzy

please follow this link https://cybersecuritychallenge.org.uk/834jtp.html

104
237
205
236
78
44
142
...

14(0E)=? 172(AC)=? 78(4E)=r 110(6E)=s 237(ED)=o 205(CD)=n

104	C	67	-37
237	o	111	-126
205	n	110	-95
236	g	103	-133
78	r	114	36
44	a	97	53
142	t	116	-26
174	u	117	-57
141	l	108	-33
44	a	97	53
142	t	116	-26
45	i	105	60
237	o	111	-126
205	n	110	-95
...

Character "C" encrypted: 104 -> 01101000
Character "C" decrypted:  67 -> 01000011

Character "o" encrypted: 237 -> 11101101
Character "o" decrypted: 111 -> 01101111