0xDEADBEEF

One of the early things I started doing with this blog, actually with the predecessor to this blog, was going through encryption examples longhand.  And I was going to start with a simple hash like MD5, except it turns out to be the opposite of simple.  So I decided to do DES, which seems to baseline a number of other common tools.

I got through 10 iterations of 16 and realized I’d been doing a step wrong since iteration 3.  Tossed that all away after months of trouble.  Then I started again, I got through 6 iterations and realized I was getting two arrays reversed on occasion.

Then I started on it AGAIN, with a plan to have my pages laid out to copy data A to B, 1 to 2, and keep everything in line.  Only by now, I’m no longer enthused by doing DES a third time.  It’s a serious PITA!  Add to that the issue that once I finish DES, this was one of the “easy” ones.  Which means the rest get harder. Un*x password files are saved via crypt, which is based on multiple passes of DES.

So after a year of doing 16 iterations of DES, I’d be moving on to doing 48 iterations of DES.  And then things would really get hard.  So I’m thinking this isn’t working.  I’ve now moved to what had originally been stage 2 plan, which was to develop scripts that would produce the longhand for looking at.  Hopefully I’ll get DES done in the next week or so.  I’ll post the script and the output if I get that working.

So, I screwed up the DES example somewhere I think.  I’m fairly sure, anyway.  Yeah.

Somewhere in:

First 8 iterations of DES Example

I made a mistake.  I’m fairly sure the setup was correct:

Initial DES Setup Steps

And the first few iterations:

DES Iteration 1

DES Iteration 2

DES Iteration 3

You can see where I botched R’(2) by shifting the wrong values around.

Then F(3), K(4), R’(4), C(6), K(6), F(5), R(5), R(8), D(9), K(9), F(8), R(9) …

DES Iteration 4

DES Iteration 5

DES Iteration 6-7

DES Iteration 8

Those are the errors I found while I was working.

I’m also fairly sure that at some point I started getting R and L confused, in F most likely, when I’m XOR’ing.  And I just didn’t have the … energy to go through it all to find the issue.  I may work it after thanksgiving, or I may restart it in a more structured manner that will force me o keep track of the C D L R in proper manners.

OTOH, If I ever get this done properly and find a good way of displaying it, this is basically what I started this blog for.  Showing the process, so that it’s easier to grasp, rather than just the mathematics and the sometimes hard-to-follow standards definitions.  Not that I’m looking forward to MD5, RSA or Blowfish, for example

So, as I was finishing iteration 9 (yeah, this is taking longer than anticipated, because frankly it’s a bit tedious and requires that I have some decent space on the train) I found myself making an error in structure.  I was XORing R(i-1) with F(i) to get R(i) , and it should be L(i-1) …

Which means I need to go back and review iterations 1-8 and make sure I didn’t make this mistake earlier.  And if I did, I have to restart from that point, because the math will propogate :/

It may be a few more weeks before this gets posted.  And I still need to figure out a good mechanism for displaying it rather than just table after table.  I may look into some kind of graphical table or something  ; I’d like to do some kind of overlaying of grids to the numbers to show, but that might take some fancy flash and I don’t have flash

I wanted to let folks know that I’m working on the DES example (nee demonstration).

I’m currently doing it while I’m on the train every day, usually in the evening now that the fall season is starting up and iTunes is having my shows again  But it’s slow, and some days I just feel like reading my book.

Anyway, each iteration takes ~3 half-sheets (I’m folding papers over and using half a sheet to write on, just because it gives me a contained space that’s easy to hold on to for writing). It looks like I can do 1.5-2 iterations a day at this point, but I’m only done with the 3rd iteration, so that may be over or under.  The first iteration took a day, then I finished the next two in one day give or take, but the XORs are starting to get more complex … Hopefully will be done by the end of the month, then I’ll have to work on typing it all in.  I want to get them posted in a row, though, so it’ll be a while before they start posting.

I did change the example some, however, so the old start is no longer relevant.

Starting from K(0):

57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36

Using our translation table for C

57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36

We are left with C(0)

0 1 1 1 1 0 1
1 1 0 1 1 0 1
0 1 0 1 1 1 1
1 0 1 1 1 1 1

Translation D

63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

1 0 0 0 1 1 1
0 1 1 0 0 1 1
0 0 1 0 0 0 1
1 0 0 0 1 1 1

Rotating C(0) to the left by 1 gives us C(1):

1 1 1 1 0 1 1
1 0 1 1 0 1 0
1 0 1 1 1 1 1
0 1 1 1 1 1 0

This simply moves the first bit to the end of the sequence. If the 4 lines are thought of as a single line, you take the first number and put it at the end, then break down into four lines again.

D(1), thusly, becomes

0 0 0 1 1 1 0
1 1 0 0 1 1 0
0 1 0 0 0 1 1
0 0 0 1 1 1 1

CD(1) is the merging of C(1) and D(1) (the 4 lines from C(1) followed by 4 more lines of D(1))

R 1 2 3 4 5 6 7
1 0 0 0 1 1 1 0
8 1 1 0 0 1 1 0
15 0 1 0 0 0 1 1
22 0 0 0 1 1 1 1
29 1 1 1 1 0 1 1
36 1 0 1 1 0 1 0
43 1 0 1 1 1 1 1
50 0 1 1 1 1 1 0

Using the K conversion table

14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32

We take the nth field from our CD(1) to define K(1)

0 0 0 0 0 1
0 1 0 1 1 0
0 0 1 1 1 1
1 0 1 1 1 0
1 1 1 0 1 1
1 0 1 1 0 1
0 1 1 0 1 1
1 0 0 1 1 1

With our initial Block

R 1 2 3 4 5 6 7 8
1 0 1 0 0 0 1 0 0
9 0 1 0 0 0 1 0 1
17 0 1 0 0 0 0 0 1
25 0 1 0 0 0 1 0 0
33 0 1 0 0 0 0 1 0
41 0 1 0 0 0 1 0 1
49 0 1 0 0 0 1 0 1
57 0 1 0 0 0 1 1 0

Using the L(0) translation table

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8

1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
1 1 1 0 1 0 1 1
0 1 1 0 0 1 1 0

The R translation Table:

57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

The resulting R(0) is such:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0

For the purposes of this exercise, we’re going to use the following information:

Data: ‘DEADBEEF’

0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 0 0 0 0 1
0 1 0 0 0 1 0 0
0 1 0 0 0 0 1 0
0 1 0 0 0 1 0 1
0 1 0 0 0 1 0 1
0 1 0 0 0 1 1 0

This is our initial 64-bit datablock

Key:0xDEADBEEF313371, layed out vertically

1 1 1 1 0 0 0 0
1 0 0 1 0 0 1 1
0 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 0 1 1 0 1 0 0
0 1 0 1 1 1 1 1

This gives us our 64-bit Key block, and every row has an even number of 1′s and 0′s, utilizing the 8th-bit of each word for parity.

Many people would have put this first, I realize.  Actually, had I thought of it, I might have too.

But I also think it makes a great deal of sense now.  Because now I can link the bits to their posts.  WHEE!

Setup (Initial Permutation)
Do 16x:

Process Key (Key Manipulations)
Process L & R with K through f (Main Algorithm)

Done
Finish (Final Permutation)

FINI

The demonstrated versions are going to be HUGE!  And start Tuesday!

After 16 cycles are complete, we take the L(16) and R(16), catenate them, and use the following Final Permutation to generate our encrypted 64-bit data block

40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25

Given the initial L(0) and R(0), we then develop L(1) and R(1)

L(i+1) = R(i)
R(i+1) = L XOR f(R(i),K(i+1))

For function f, R(i) is expanded from 32-bit to 48-bit R’(i)

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

R’(i) XOR K(i+1) (RK(i))is then broken into 8 6-bit chunks and permuted through S tables. (See S-Table post)

This permutation is then FURTHER permuted, which gives us the result (F(i)) of f(R(i),K(i+1))

16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25

F(i) is then XOR’d with L(i) (from WAAAY back), giving us the R(i+1).