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!!!