More Excel Fun (nothin better on a rainy day)

Continuing in the pursuit of things I'm not very good at or understand very well, I decided to mess around a bit more with Excel and the Diffusion "thing" that I have been thinking and writing about. I got a bit bored with the 'Sawtooth' idea and decided to play with the Pseudo-Hadamard Transform. Specifically I decided to see how it works on 32 bit words or 4 bytes at a time. It's an easy thing to do with 16 bits or two bytes but 4 bytes isn't as straight forward in Excel. So to do this I wrote another Visual Basic script in Excel that will take the values in 4 cells (each a byte) then combine them into two 16 bit values. It then does the math Mod 2^16 and parses the values out into 4 new cells (each a byte). The code accepts 5 values from Excel, the first 4 are the byte values to do the calculation with and the 5th value is to determine which of the 4 output bytes to return. I posted the code at the end of this post.

What I noticed once I had done this is how crappy it seems to be at mixing or diffusing the  changes in the values when you are looking at one byte at a time. I shouldn't say crappy because I probably wrote the code wrong and I'm not doing the math correctly!! Ha Ha! Anyway what I got was a function that seems to work when I check the math by hand. Below is a few examples of what happens when you change various Input Values and how the Output Values change.

INPUT		1	0	0	0
OUTPUT		2	0	1	0

INPUT		0	2	0	0
OUTPUT		0	4	0	2

INPUT		0	0	3	0
OUTPUT		3	0	3	0

INPUT		0	0	0	4
OUTPUT		0	4	0	4

The interesting thing is that if you change one value in the input, two values change in the outputs. You can change the values of the inputs to whatever you want but almost always each input changes just the values in the locations above. For example looking at the first chart above with the value of 1 in the left input row it is changing the values in the locations noted by the 2 and the 1 in the output row below it. In the second chart the value of 2 in the input row is changing the values in the locations marked with the 4 and the 2. In fact I created a spreadsheet that runs through all the input values and for every input value the changes follow the above charts with the exception below:

INPUT		0	128	0	0
OUTPUT		1	0	0	128

INPUT		0	129	0	0
OUTPUT		1	2	0	129

So looking at the two above charts the value of 128 in the second input byte from the left is changing different output values than it did in the first set of charts. When the second input value from the left goes to 129 and above it is back to changing the second and fourth output values from the left. (but it leaves the first output byte larger by 1 from then on). Wow!! This is exciting!

I suppose another way to look at what is going on here is this:

INPUT		A	B	C	D
OUTPUT		(A|C)	(D|B)	(A|C)	(D|B)

So the input in each location noted with a letter is having an effect on the output that has the same letter. Assuming you ignore the oddball change when the second input from the left is 128 and it changes the first output from the left by 1.

One problem in my opinion with doing this is only one input value is changing two of the output values. Ideally I would like to have all the output values change if one of the input values has changed. Thinking about this I decided to make two transforms in parallel with each acting on the input bytes rotated by location to the left one place. Here is a similar chart showing that:

INPUT		B	C	D	A
OUTPUT		(B|D)	(C|A)	(B|D)	(A|C)

Notice that the locations of A, B, C and D are all shifted. So imagine you have 4 input values A, B, C and D. They are 'loaded' into the chart locations above and simultaneously calculated causing the outputs to change in each location. Then the outputs from both transforms are Exclusive Or'd together to get the 4 output byte values:

OUTPUT	(A|C)	(D|B)	(A|C)	(D|B)
OUTPUT	(B|D)	(C|A)	(B|D)	(A|C)
XOR	(ABCD)	(ABCD)	(ABCD)	(ABCD)

Or something like that anyway. The reason I bring it up is because I did just that in a spreadsheet ;) So anyway it's not very interesting if you just take the exact same values for A, B, C, and D and put them into the same transforms and exclusive or the outputs together. What I decided to do is take the values A,B,C and D and put them into the first transform then take those values and swap the upper and lower bits (Nibble Swap). That way the the inputs to the two transforms are different but related to each other. If A changes then it's "Nibble Swapped" value will change too. An example is the value 12 decimal which  = 1100 in Binary. If you look at 12 in 8 bit binary (with the nibbles separated for clarity) it's 0000 1100. If you swap the nibbles it becomes 1100 0000 which = 192 decimal.

One obvious thing to mention is some values don't change when you swap the nibbles.

Obviously 0 = 0000 0000 and 255 = 1111 1111 don't change when you swap the nibbles. Neither does 17 = 0001 0001 or 85 = 0101 0101. In fact anything that is a multiple of 17 doesn't change when you swap the nibbles so I decided to fix that by performing a logical NOT (inversion) on all the values that don't change when you swap them. So 0 becomes 255, 255 becomes 0, 17 becomes 238 and 85 becomes 170. Wow!! This is exciting!! I posted the code for doing this special Nibble Swap at the end of this post.

Anyway that is what I have been up to this rainy weekend. I have not done a whole lot of testing on the above idea to see if it really does mix up the data and 'diffuse' it over the entire 4 byte output. I did write some simple scripts to run through a few thousand input values and checked for output changes and it seems to work pretty good.

On interesting thing to note about this is that the two transforms could actually be done in parallel if this were to be implemented in some kind of real time encryption system. I suppose that one method would be to take the 4 input values and substitute them with two different substitution (look-up) tables. This would be a lot better than using the Nibble Swap to get a different value for the second transform. So the A value could be substituted in two tables for 2 new values with each new value going into a transform - one being position rotated to the left. That way the values are different but would change if the A byte value changed. The subject of cryptographic substitution tables is best left for another day.

Visual Basic Code for Pseudo-Hadamard Transform (32 bit word)

Function PHT(A As Long, B As Long, C As Long, D As Long, Place As Long)
' Pseudo Hadamard Transform 16 bit words
' Shift A <<8 and C <<8 then Or C and D with them
' create Temp to hold left value
' check Place to figure out which byte is req'd as output
' December 2009 http://ottobelden.blogspot.com
Dim Left As Long
Dim Temp As Long
Dim Right As Long
Left = (A * 256) Or B
Right = (C * 256) Or D
Temp = Left
Left = (2 * Left) + Right Mod 65536
Right = Temp + Right Mod 65536
If Place = 1 Then
    Left = Int(Left And 65280) / 256
    PHT = Left
    End If
If Place = 2 Then
    Left = Left And 255
    PHT = Left
    End If
If Place = 3 Then
    Right = Int(Right And 65280) / 256
    PHT = Right
    End If
If Place = 4 Then
    Right = Right And 255
    PHT = Right
    End If
End Function

Nibble Swap with logical Not

Function SHIFTD(Value As Byte)
' Swap upper nibble for lower
' if swapping doesn't change value
' then invert (NOT) value
' December 2009 http://ottobelden.blogspot.com
Dim LN As Byte
Dim RN As Byte
RN = Int(Value / 16)
LN = (Value And 15) * 16
If Value = (LN Or RN) Then
    Value = Not (LN Or RN)
    SHIFTD = Value
Else
    SHIFTD = LN Or RN
End If
End Function