Difference Distribution Table (DDT) in Excel...

It has been a few days since I have had time to post anything here on my Blog, not because I have not been doing things but I have just been busy with the holidays and the New Year... But now that I have a few spare moments I'd like to write about some more fun Excel programming that I have been doing!!!

In the exciting world of cryptography there is a concept called Differential Cryptanalysis. If you click on the link it will take you to a Wikipedia explanation of what it is. My uneducated explanation of how it works goes something like this: If you have 2 different inputs to a cipher they will give you 2 different outputs. This holds true for either the entire cipher or just part of it and for this explanation the cipher key is the same for each input.

What someone can do is look at the differences between several inputs to a cipher and at the same time look for common output differences for each. If you see that a certain input difference frequently causes a certain output difference you have some information about how the cipher is working for that particular key. The trick when looking at input differences that make certain output differences is how likely those differences are. So really what you are doing is looking for certain differences in the outputs of a cipher that are very likely caused by certain input differences. Once you have found those you can make an educated guess about either what the input is or what key might have been used to encrypt everything. This type of attack usually doesn't give you the actual key or the actual input but it allows you to narrow down what the most likely key or input might be.
Usually when looking at a cipher in this way you would break the cipher down into small pieces and look for how differences propagate through various parts of the cipher. Most often what is looked at is the substitution tables of a cipher and that is what this blog post is about!!! I know I'm rambling a bit here...

(Click on the pic for a better view)

A Difference Distribution Table is a chart of how often input differences make output differences for a part of a cipher - in this case a substitution table.  These tables are also good for wallpaper as they tend to go on and on and on... (kinda like my blog posts) For my Excel DDT I have used one byte values for the inputs and one byte values for the outputs.

Here is how the chart above works: Along the top of the chart are columns numbered 0 to 255 representing all the output differences. Down the left hand side of the chart are similar numbers from 0 to 255 representing all the input differences.

The first step is to pick a couple of different inputs, lets say that they are 4 decimal  (100 binary) and 2 decimal (010 binary). Once you have picked a couple of inputs you  figure out the difference between them by exclusive or-ing them together.The binary difference (Exclusive Or) between 4 and 2 is:

100 = 4

010 = 2

110 = 6

So the input difference is 6 in this case, note that value for later.

 

The next step is to figure out what each of those inputs gets 'changed to' when you encipher them. In this case the change is a substitution based on a lookup table. Lets pretend that the value of 4 gets substituted to 28 and a value of 2 gets substituted to 34. If you Exclusive Or 28 and 34 you get 62. Note that value for later.

  

Now you have the two difference values that you need. The input difference in this case is 6 and the corresponding output differences in this case is 62. All you need to do now is go down the left hand side of the chart to row 6 (input difference) and across the top of the chart to column 62 (output difference) and add 1 to whatever value is there. Once you have done that go through every possible combination of input differences and figure out the output difference for each, updating the values in the chart. The chart at that point contains entries of the number of times each difference pair has occurred (how often in other words you get an input to output difference)

Once the chart has been filled up with all the values based on all possible inputs it's ready to use!!! Yeah! How is this chart used? One might look for really large or possibly really small values in the chart. In keeping with the example above lets say that a whole bunch of input combinations whose difference is 6 ended up making a whole bunch of output differences of 62. If that were to happen the Difference Distribution Chart would have a large value in row 6 column 62. That would mean that while the cipher is doing it's thing there is a greater than even change that the output would be 62 because so many different input pairs make that difference. In short you want the values in the chart to be very close to the same... no really big or small numbers.

Anyway that is an update on what I have been doing. Please excuse my haphazard writing style... below is the Excel Visual Basic code I wrote to create the above chart. The substitution table that I used is one I got off the internet...

Enjoy!!!!

Microsoft Excel VB Code for Byte Sized Difference Distribution Table

Sub DDT()

' This Macro will index into a column of values in

' the sheet that are substitutions (sub table)

' running thru all combinations of substitutions

' Xor'ing the values indexed and the sub'd values

' plotting them into a (big) frequency DDT.

' January 2010 http://ottobelden.blogspot.com

'

'These constants locate stuff on the sheet

Dim SubCol As Byte      ' Column where Sub Table is
Dim OffS As Byte        ' Vertical offset to Sub Table
Dim OffI As Byte        ' Vert chart Offset (Row)
Dim OffO As Byte        ' Horiz chart Offset (Column)
SubCol = 2              ' Sub Table is at Column 2(=B)
OffS = 10               ' Sub Table Starts at Row 10
OffI = 10               ' Chart starts at Row 10
OffO = 5                ' Chart Starts at Column 5 (=E)

'

'These variables are for calculations

Dim InputV As Long      ' Xor'd value of 2 inputs
Dim OutputV As Long     ' Xor'd value of sub'd inputs
Dim OutA As Long        ' One Sub'd value
Dim OutB As Long        ' Other Sub'd Byte

'

' Turn screen updating off and note start time

Application.ScreenUpdating = False
Cells(4, 2) = Time
For Input1 = 0 To 255
    ' Index into Table = OutA
    OutA = Cells((OffS + Input1), SubCol)
    For Input2 = 0 To 255
        ' Index into Table = OutB
        OutB = Cells((OffS + Input2), SubCol)
        ' Input V = Xor of Input's + Chart Offset Vert

        ' OutputV = Xor of sub'd values + Chart offset Horiz

        InputV = (Input1 Xor Input2) + OffI
        OutputV = (OutA Xor OutB) + OffO
        ' Index into chart and increment value
        Cells(InputV, OutputV) = Cells(InputV, OutputV) + 1
    Next Input2
Next Input1

' Turn screen updating on and note end time

Application.ScreenUpdating = True
Cells(5, 2) = Time
End Sub