The Avalanche Criterion  (AC) is a process that happens in block ciphers.   Objectively, you look to measure the amount of change in the output bits of a cipher when you change only one input bit. Loosely speaking, the strict avalanche criterion (SAC) is the most desired version of this affect, but good AC is generally speaking sufficient.

There are two components to this project.

1. Write a short essay outlining what AC and SAC is.   You will need to use more than just the Wikipedia entry about this, but that would certainly be a start. There are many pieces of informa- tion about AC and SAC available on the web, some better than others (of course!). This component of the project is easily the shorter of the two, but you will need to truly understand the concept properly to give a meaningful answer to the second component.

2. You are now going to study avalanche criteria on something quite small and simple: namely, where we use a linear substitution cipher as a block cipher. How to do so is described below. Ultimately, your goal is to analyze the linear substitution cipher for AC and conclude whether, in your opinion, the linear substitution cipher offers good AC or not.  Your report should give a reasoned answer as to why you end up with the conclusion you make.  During your analysis, you may or may not observe some instances of a linear substitution cipher producing SAC (say, for a specific choice of key). If you do, you should absolutely report this. If you do not, you should also make a statement to that effect.

Within this question is a hidden problem: Namely, how do you measure AC and SAC? There are a number of sensible ways to do so. This is something you will have to determine as part of your study. To this end, within your project description you must include a section detailing what you decided to use for measuring AC, and why you think it is a reasonable way to measure it.

How to use a linear substitution cipher as a block ciper

We design a block cipher on bit blocks of length k .  To use a linear substitution cipher, we need to do three things:

• Choose the bit length k . We will then be working with integers modulo N = 2k .

• Choose the key for the encryption function: this is a pair of integers (a,b), where 1 ≤ a ≤ N − 1 is odd and 0 ≤ b ≤ N − 1 is any number.

This determines the encryption function: Ea,b (x) = ax+b mod N . Changing the choice of the pair (a,b) clearly changes the encryption function E .

• We also need to be able to convert integers to bit strings.  This is literally the application of the division algorithm for finding the base expansion with base 2. This was covered in the first week’s lecture on the Division Algorithm and it’s Applications.  You should re-watch that if you don’t recall – it is pretty much the first application described in that lecture – but basically, for binary, it involves repeated division by 2.

So how do those 3 things gives us a block cipher?  Let me show you using just 2 bits, and additionally give you a starter on how to go about analyzing AC.

We set k = 2 and so N = 22  = 4.  There are consequently 2 choices for a (either 1 or 3), and 4 choices for b (0,1,2,3). I will choose a = 3, b = 2.

The encryption function for this example is therefore E(x) = 3x + 2 mod 4.  I can now look at every result from this function: The message space involves just the four numbers 0 ≤ x ≤ N − 1 = 3. We have

x    '→    E(x)

0    '→    2

1    '→    1

2    '→    0

3    '→    3

I now convert my inputs and outputs into binary sequences using the base expansion technique, and reproduce the table:

x    '→    E(x)

This final table represents the linear subsitution cipher acting as a block cipher on 2 bit blocks.

If I now want to look at the AC, then I want to look at how changing 1 bit in the input changes the output. For example, changing one bit of input from an initial input of 00 will either produce an input of 01 or 10, and I look at how the output changes. Below I have tabulated all of the possibilities:

From this, I can see that the number of bits that changes per 1 bit of input changing was 1 .5 on average. If I wanted to analyze a 2 bit linear substitution cipher for AC, I would need to do this for every choice of possible key. There are 8 possible keys in this example and after doing the above for each of them, I would find that this cipher looks quite good.  However, this is not a surprise, because at least 1 output bit has to change whenever I change an input bit because the cipher is a bijection – that means for a 2 bit linear cipher, I was always guaranteed a minimum change of 50% of the output bits when I changed an input bit. When I increase k, I am still going to be guaranteed at least 1 bit of change for the same reason, but I am not guaranteed any more than that via this argument. That is why we need to do an analysis for larger bit lengths.

For your project, you must analyze at least the case k  = 3, and preferably k  = 4 as well.  Writing some code in whatever is your preferred programming language will make this much simpler (and you’ll probably be able to analyze even larger bit lengths if you so desire). It is possible to do the k = 3 case completely by hand, but it does take a good amount of time (there are 32 possible encryption functions in that case, hence the reason it is a decent amount of work!). Of course, I would absolutely recommend you do this with some programming, but ultimately it is up to you.  I will say that without looking at k = 4 too, you cannot really say a lot.