DES: Pre-setup

Crypts, Demonstration | Posted by attriel June 17th, 2008

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.

DES Overview

Crypts, Descriptions | Posted by attriel June 13th, 2008

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!

DES: Final Permutation

Crypts, Descriptions | Posted by attriel June 10th, 2008

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

DES: Main Algorithm

Crypts, Descriptions | Posted by attriel June 5th, 2008

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).

DES: S-Tables

Crypts, Descriptions | Posted by attriel June 4th, 2008

The 6-bits from RK(i) are then further mixed RK(i,0)RK(i,5) and RK(i,1..4), which provides a 4-bit response

The first and last bits define which ROW, and the middle 4-bits define the COLUMN

S(1)

RC 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

00

01

10

11

Full listings after the break

Read the rest of this entry »

DES: Key (K) Manipulations

Crypts, Descriptions | Posted by attriel April 24th, 2008

In order to encrypt our data, we start with a 64-bit key (KEY). This key is, actually, only 56 bits, with every 8th bit for parity.

From this 64-bit KEY we need to define two 24-bit blocks (C and D)

C(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

D(0)
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

From here, each C/D 1..16 are generated by Left Rotating the previous C/D according to the following table:
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1

Thus C(1) is LR(1) C(0), D(15) is LR(2) D(14), etc

We then catenate C and D (making it one longer block), and can now define our K with the following 56-to-48 bit conversion table

K(1)

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

DES: Initial Permutation

Crypts, Descriptions | Posted by attriel April 24th, 2008

DES operates on 64-bit blocks of data, equivalent to 8-characters.

The first step in a DES encryption is to munge the initial block to create two new datablocks

L(0)
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

R(0)
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

Data Encryption Standard (DES) pt 0

Crypts, Descriptions | Posted by attriel April 20th, 2008

I had gone through DES before, but in the end it’s such a LARGE process that the description was huge. The example was going to go on for days, or be virtually useless.

So, now I’m redoing it in a series of posts, with the intent that the smaller chunkiness will permit semi-reasonable walkthrough.

I can still foresee some issues herein, but they may be less insurmountable

Simple Ciphers Demonstrated

cyphers, Demonstration | Posted by attriel April 6th, 2008

Here we display the cipher wheel (this was annoyingly hard to make and I’m not too fond of how it turned out, so on the few occasions that something like this is used again I may move to a line ; but for simple ciphers, this really was the best way to go IMO). It’s easy to see how to convert a letter: simply find the letter on the outer ring, and write the letter from the inner ring.

For this example, we will encode the title of this post.

The first is “ROT-13 encoding,” which despite it’s name isn’t really an encoding. ROT-13 substitutes each letter with the letter 13 away (half an alphabet), which eliminates the need to define a direction in the shift. A becomes M, M becomes A. D becomes P, P becomes D.

Simple Cyphers ROT13

S transliterates to F, i<=>v, m<=>z,p<=>c, l<=>y,e<=>r. Thus Simple becomes Fvzcyr

Simple Ciphers Demonstrated
Fvzcyr Pvcuref Qrzbafgengrq

ROT 13 is convenient in that the cipher wheel can really be written with only half the wheel, since all mappings are bi-directional. S becomes an F and an F becomes an S. This also makes deciphering the message simple since, technically, you can simply re-cipher the text and it will revert to the original plaintext

Second is a “Rotation Cipher,” more commonly known as a “Caesar Cipher,” which is actually a more general version of ROT-13. A Rotation Cipher would generally be named with a direction and a number. ROT Right 5, or ROT-L-9. ROT-13 is a special case because L and R would be identical (26 letters, 13 is halfway around, either direction). Rotation Ciphers are frequently put on “secret decoder rings.”

Cimple Ciphers Rotate Right 5

In this instance we have S mapping to N, I to D, M to H, P to K, L to G, and E to Z. Simple becomes NDHKGZ

Simple Ciphers Demonstratred
Ndhkgz Xdkczmn Ynhjinomvomny

Rotate Right 5 is somewhat more complicated than ROT13, simply because the mappings are not bi-directional. However, given the S to N mapping, it is possible to deduce the full cipher. In fact, that is how I ciphered the “Ciphers Demonstrated” portion. C is two letters before E. E was Z, thus C is X. I was in Simple, as was P. H is immeditely before I, e occurs in both, R is one less than S, S appears in both. Thus only three letters needed to be “deduced” for enciphering “Ciphers”, and none was more than two letters off of a letter we had already. The same holds true for “Demonstrated”

The third is the generic case of “substitution cipher.” In this instance, A may be mapped to X and then B to C, there is no relation between mappings. This can either be a 13-letter table (where, then, X would map to A and C to B) or a full 26 (C may map to A, and X would become I).

Simple Ciphers, Randomize
S maps to E. I maps to M, M maps to Z and NOT I. P maps to Y. L to K, and E to G. Simple maps to Emzykg.

Simple Ciphers Demonstrated
Emzykg Amyugse Ogzhrevsxvgo

I made a note that M mapped to Z and not I. The process of enciphering this text could be made “easier” by making any given cipher pair a bidirectional pairing. I to M and M to I. But that also simplifies the algorithm and makes it simpler for an “attacker” to “crack” the “code”. (I put those words in quotes because, honestly, there’s not much code to crack in this instance)

Simple Ciphers

cyphers, Descriptions | Posted by attriel April 6th, 2008

A simple cipher substitutes one letter for another, one-to-one generally. Technically ‘simple ciphers’ covers three common setups, but as they are fundamentally the same, I’m including both.

The first is “ROT-13 encoding,” which despite it’s name isn’t really an encoding. ROT-13 substitutes each letter with the letter 13 away (half an alphabet), which eliminates the need to define a direction in the shift. A becomes M, M becomes A. D becomes P, P becomes D.

Second is a “Rotation Cipher,” more commonly known as a “Caesar Cipher,” which is actually a more general version of ROT-13. A Rotation Cipher would generally be named with a direction and a number. ROT Right 5, or ROT-L-9. ROT-13 is a special case because L and R would be identical (26 letters, 13 is halfway around, either direction). Rotation Ciphers are frequently put on “secret decoder rings.”

The third is the generic case of “substitution cipher.” In this instance, A may be mapped to X and then B to C, there is no relation between mappings. This can either be a 13-letter table (where, then, X would map to A and C to B) or a full 26 (C may map to A, and X would become I).

In terms of data security, none of these is any good. These are more useful for either pre-coding a message for actual encoding or encryption, or for passing insecure data. There are ways to complicate these techniques (which I will work up separately), which make them more secure.

The basic use for a Simple Cipher is to make data require some level of work to read (to slow someone down), and to make for ready manual processing. With the “decoder ring”, anyone can easily tick through an arbitrarily long message with a consistent time per letter, and a consistent process.

(This is a post I’m migrating from the first edition of this blog)