Tables of various kinds... Stripping Table and a Substitution Table

This week I would like to write about a couple of tables, the kind I am stripping paint off of and substitution tables... I'll start by giving a short update on the paint stripping going on with serious Klean-Strip KS-3 Premium Stripper action. To give you a quick visual reminder of what I am doing check out This Recent Picture of the table and also This One (click on the links!). Anyway the weather has cleared up a bit so I was able to do the paint stripping in the back of the house instead of in the front where I had some shielding from the rain. As you might be able to see in the below picture one side of the table has had the paint stripped off (right side) and the other side still has some ugly pink paint. That didn't last long as two coats of the paint stripper got most of the paint and primer off the left side.
  

In my estimation I should do at least one more coat of the stripper over all the tough spots to get what remains of the primer and little bits of paint off. Then I'll have to start on the sanding... not going to be fun on all the curved surfaces but promises to be a richly rewarding penultimate step in coating removal.

Moving right along at a feverish pace I'd like to write a bit about substitution tables and diffusion. Yes I know this is boring to most of my faithful readers, not being at all as exciting is stripping paint of tables (wait 'till I write about paint drying!) but substitution tables and cryptographic confusion interest me. Again to start off with some quick reminders of what in the world I am writing about HERE is a link to my last post somewhat related to this topic. Kinda also related to this is a Wikipedia entry about this as well (click HERE for that if interested).
  
Substitution tables are just lookup tables that are used to substitute one input value for another different value. As I wrote about in the Difference Distribution Table post that I linked to above and tricked you into clicking on again here there are some important structures to consider when designing a substitution table. The obvious idea would be to fill the table up with random numbers, when you index in you get a random number out! This is great until you use the same table over and over again. Patterns in the input to the table will give you patterns in the random numbers you get out of the table because if the most common input number is 6 for example, and 6 gets substituted for 11 then the most common output will be 11. Anyway that is one issue with the tables in addition to what I wrote about in THIS post. OK if you clicked on that last link it again took you to the same page - I just thought it would be funny to link to the same page three times! Ha Ha! I promise not to do that anymore. To summarize... usually in a substitution table you index into the table based on the value you are going to substitute and get whatever value is in the table at that location. If the input is 1 you grab the first value, if the input is 34 you grab the 34th value etc... if you have a string of 34's as the inputs then you get a string of whatever the 34th value is as the outputs.

Anyway I have been thinking about and tinkering around with this idea of using one or maybe two substitution tables and indexing into them based on the input data. This idea incorporates the Sawtooth idea that I wrote about some time ago in that it 'moves across' the input data from left to right then back through the changed input data right to left. I have not done too many tests in Excel on this one nor have I written any fancy Visual Basic code to play with it. I did do a spreadsheet to play around with it a bit though... here is the basic idea:

Take a few byte sized input values, lets say 4 of them called inputs A, B, C, and D.  Just for fun and to keep it simple say the values for these are 2, 3, 4 and 5 in order. Now have a substitution table handy that has 256 numbers in it from 0 to 255 all mixed up in a random order with no numbers repeating. For what I am thinking here the order doesn't really matter but having all the numbers different ant not in order is important.

OK now index into the table the first value A or 2 in this case. Whatever the 2nd number in the table is that is the new value of A. Now get the second number which is 3 and instead of indexing into the table to the third place - index in to the 5th value - that 5th value is the new value of B. Why the 5th value? Because the first value of A was 2 and three more into the table is 5. The next value is 4 so go into the table 4 more places and you are at the 9th value - that is the new value for C. The last input number is 5 so go in 5 more places starting from the 9th place and you get the 14th value as the new value for D.
  
At this point you have four new values for A, B, C and D and each new value depends on the previous values. If you were to do this again but change the value of B, this time the value for B would be different but so would the values for C and D because of the additive way that you index into the table. So changing the value of one number would change the values of all the numbers that come after it.

That was so much fun lets do it again! But this time to mix it up a bit lets go in reverse order and lets ExclusiveOr the numbers instead of just substituting them. Here we go: Take the new value for D that we got above and index into the table that many locations (whatever D is) and ExclusiveOr whatever number is in that location with the value of D. Now add the value of C from above to whatever D was and go that far into the table and ExclusiveOr that value with whatever C was. Do it again for B and A.

OK so now at this point because we went and substituted A, B, C, and D, adding in the values to index the first time and then with the new values we went in reverse order all the values now depend on all the other values. Another way to look at this is (as I mentioned above) changing B would change C and D when we go back in reverse order that changed B value would now change the value of A. So after having done this forward additive indexing and reverse additive indexing into the substitution table all the new values would depend on all the input values. Changing any one of the input numbers would tend to change all the output numbers.
  
Let me anticipate your next question - why Exclusive Or the second time through?  I was wondering this myself and I think I have 2 answers to that question. The first one is the way addition works.  For a second lets pretend that we don't do the ExclusiveOr. Lets also say in the second indexing operation you have the first two values of 4 and 6. These index into the table to the 10th location so the output is the 10th number. Now lets pretend some more and imagine that the first two numbers have changed to 8 and 2. Those now also index into the 10th location. So the first two numbers have changed but the third number is still the 10th value from the table. This is undesirable.

Now do the same thing we just did but with the ExclusiveOr. This time the numbers of 4 and 6 get us to the 10th value which we ExclusiveOr with 6 to get some number. The next time we have the values of 2 and 8 that also get us to the 10th number but this time we ExclusiveOr with 8 and get some different number than we got the first time. Pretty cool... now the second reason I happen to have forgottan but off the top of my head I would guess that I was thinking that ExclusiveOr'ing with the table value instead of just substituting it makes it harder to work backwords.... if you knew the 4 output values of the table with the ExclusiveOr it would be harder to go back and figure out what the input values were.
 
Anyway that is about all I want to write about tables today. I'm pretty sure that the paint stripping and table base will work when I finally finish it but I'm not sure about my substitution table idea... more on that later!!!

Stripping Paint Off The Table Base (In The Rain)

Even thought the holidays have been over for almost a month I still feel like I am trying to catch up on things. Mostly I believe this feeling is because of the seemingly endless rain and the cold darkness of night time coming early. Despite this Otto Jr. and I managed to get some work done on the table that I wrote about last week. As I mentioned in that post I have decided to make a table from a base that has been kicking around my house for some time now. I actually have 2 of these bases so if anyone would like a table let me know and I'll make one for you!

  

Here is a picture of the table base as it looked last week PICTURE.

Here is a picture of how it looks today!

As always you can click on the picture for a bigger and more detailed view. Essentially all that has changed since last week is we have started to strip off all the ugly pinkish paint to reveal the cheap and ugly looking pine wood underneath.  I'm not sure how much of an improvement this is or will be but I can always paint it again if I don't like it! Actually I think the wood grain no matter how bad it is will still look better than the paint that it had on it.

You can't really tell from the picture but we stripped off most all of the paint on one side of the base. We did this using Klean-Strip KS-3 Premium Stripper that you can buy at the hardware store. I have never used this particular brand before and I thought that this would be a good opportunity to give it a try. The instructions say to use it at temperatures above 65F and it was 49F here today so right off the bat we were doing things wrong! Because of the warnings on the can for this stuff about fumes and ventilation we decided to do the work outside (this is the In The Rain part). No matter I suppose, it seemed to work pretty good. I was ready for a nasty workout in getting this paint off because I sanded another piece of wood that was related to this table base and it was a lot of work. There are several coats of paint and primer on this making it hard to get down to bare wood.

 

This stripper worked pretty good at getting the top layers of paint off in one application and scraping with plastic scrapers. A second coat on top of what was left after the first cut through the primer and I can see wood in most all places. The second coat of stripper I used a wire brush / scraper combination to clean out the cracks and the rounded turned surfaces and crevices. Using a brush with a caustic nasty chemical like paint stripper is never a good idea as the brush bristles always flick toxic debris off onto everything so don't do that.

After scraping and brushing for an hour or so we called it done for today. We used some old rags soaked in water to get what little was left off the surfaces and clean it up. There is still some noticeable primer and bits of paint really stuck on there but I think possibly one more coat of stripper and some light sanding will get it back to bare wood.

As I mentioned above I'm not sure that this is going to look any better than the pinkish paint or just painting it but I want to give it a try. It's a good project for my son and I to work on together and even if it doesn't look great it is still fun. I am considering staining this piece if the grain looks somewhat OK once all the paint is off... maybe coloring it some with paint and staining... also carving some neat stuff like gargoyles and scary faces on the flat parts... all depends on my mood as we get closer to finishing it. Oh yeah before I forget we are also going to put a table top on top of it and I need to make that too.

Thanks for reading another one of my semi-coherent rambling posts.. have fun over and out!!

Salvaged Table Base and the beginning of a new project

It's still cold here in sunny California and my garage is a mess... nevertheless I think I am going to start a new project. I have several irons in the fire right now and the last thing I need is another one but "necessity is the mother of invention" or in this case at least the mother of a table.

 

I happen to have this table base that I am not using and was considering burning it on a non-spare-the-air-day but because it has a lot of nasty smoke generating paint and I think it's neat I'm going to turn it into a table.

 

This thing is about 26" tall and it has some nice features. For one thing it sits flat (something to look for in four legged standing things) and it's hollow. I like the hollow part because I think I would like to have a cantilevered top that can be extended on rails. Being hollow will allow me to add some heavy ballast weight to the inside and help prevent messy tip-overs. A cantilevered table would be a good addition to my unorthodox furniture collection because I don't have a dining room table (dining room is a converted office) and I have a hard time finding flat surfaces to eat on. Usually sitting on the couch with a pizza or holding plates of food in my lap isn't the best thing especially when I have guests.

 

Anyway I thought that I would post a picture of it before I start stripping the paint off and drilling holes into it. As it undergoes it's metamorphosis from salvaged woodwork into high tech industrial practical furniture I'll post more pictures and maybe even throw in a few of my garage once I get it cleaned up.

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