Since we are getting more advanced in the C language, I have been working on

a tutorial that covers a more advanced C program: Blowfish.

For those of you who don't know, Blowfish is a symmetric block cipher (an

encryption algorithm with one key) made by Bruce Schneier, a well-respected

cryptographer. It has a 64-bit block size, and a variable key length (up to

448 bits).

I'll go over how Blowfish works so you can get a better understanding of the

code. This is straight from Schneier's book:

" Blowfish is a 64-bit block cipher with a variable-length key. The algorithm

consists of two parts: key expansion and data encryption. Key expansion

converts a key of up to 448 bits into several subkey arrays totaling 4168

bytes.

Data encryption consts of a simple function iterated 16 times. Each round

consists of a key-dependent permutation, and a key- and data-dependent

substitution. All operations are additions and XORs on 32-bit words. The only

additional operations are four indexed array data lookups per round." (What

he means is data is taken from an array)

" Blowfish uses a large number of subkeys. These keys must be precomputed

before any data encryption or decryption."

(Begin my comments)

The array P consists of 18 32-bit subkeys.

Four arrays S consist of 256 entries. (it's a two-dimensional array).

To encrypt, we do the following, assuming that x is a 64-bit plaintext block:

First divide x into two 32-bit blocks, Xl and Xr. (Or X-left and X-right :)

for i = 0 to 15 (16 times):

Xl = Xl XOR P[i];

Xr = Function F(Xl) XOR Xr;

Swap Xl and Xr

After the loop is done, swap Xl and Xr again.

Xr = Xr XOR P[17];

Xl = Xl XOR P[18];

Concatenate Xl and Xr back together (Remember our left and right? :)

This is function F, which is a BIT confusing, because of inconsistancies in

Schneier's explanation and Schneier's code:

Divide Xl into 4 8-bit quarters: a, b, c, and d.

((S1[a] + S2[b] mod 2(exp)32) XOR S3[c]) + S4[d] mod 2(exp)32;

A bit confusing, no? However, unless mod does not mean modulus, here's what

Schneier's code says instead:

((S1[a] + S2[b]) XOR S3[c]) + S4[d]

No modulus at all in there. Maybe the book has an errata list I can check

somewhere, I'll look at it later.

Here is the challenge for you all right now: write a function or macro for

function F. Assume the 4 S arrays are global variables. It will be

interesting to see how you split the 32-bit block into four 8-bit blocks.

Lastly, this is how subkey generation works (from the book again). Things in

parenthesis are notes from me:

"

(1) Initialize first the P-array and then the four S-boxes (the 4 S arrays),

in order, with a fixed string. This string consts of the hexadecimal digits

of pi.

(2) XOR P1 with the first 32 bits of the key, XOR p2 with the second 32 bits

of the key, and so on for all bits of the key (up to P18). Repeatedly cycle

through the key bits until the entire P-array has been XORed with key bits

(This is how it takes a variable-length key)

(3) Encrypt the all-zero string (bad English! Guess he didn't have a

proofreader) with the Blowfish algorithm, using the subkeys described in

steps (1) and (2). (Right now, the S-arrays are some of the hexadecimal

digits of pi, so remember, function F will still work, even though they

haven't really been "initialized" yet)

(4) Replace P1 and P2 with the output of step (3).

(5) Encrypt the output of step (3) using the blowfish algorithm with the

modified subkeys

(6) Replace P3 and P4 with the output of step (5).

(7) Continue the process, replacing all elements of the P-array, and then all

four S-boxes in order, with the output of the continuously changing Blowfish

algorithm.

"

I will follow up this post with the tutorial soon, right now I am just

cleaning up Schneier's code (which has given me a new respect to writing

stuff cleanly). In the mean time, let me see the answers to that challenge :)

Morgon

--

grab my updated (12/21/02) public key from http://www.surgo.net/pubkey.asc

a tutorial that covers a more advanced C program: Blowfish.

For those of you who don't know, Blowfish is a symmetric block cipher (an

encryption algorithm with one key) made by Bruce Schneier, a well-respected

cryptographer. It has a 64-bit block size, and a variable key length (up to

448 bits).

I'll go over how Blowfish works so you can get a better understanding of the

code. This is straight from Schneier's book:

" Blowfish is a 64-bit block cipher with a variable-length key. The algorithm

consists of two parts: key expansion and data encryption. Key expansion

converts a key of up to 448 bits into several subkey arrays totaling 4168

bytes.

Data encryption consts of a simple function iterated 16 times. Each round

consists of a key-dependent permutation, and a key- and data-dependent

substitution. All operations are additions and XORs on 32-bit words. The only

additional operations are four indexed array data lookups per round." (What

he means is data is taken from an array)

" Blowfish uses a large number of subkeys. These keys must be precomputed

before any data encryption or decryption."

(Begin my comments)

The array P consists of 18 32-bit subkeys.

Four arrays S consist of 256 entries. (it's a two-dimensional array).

To encrypt, we do the following, assuming that x is a 64-bit plaintext block:

First divide x into two 32-bit blocks, Xl and Xr. (Or X-left and X-right :)

for i = 0 to 15 (16 times):

Xl = Xl XOR P[i];

Xr = Function F(Xl) XOR Xr;

Swap Xl and Xr

After the loop is done, swap Xl and Xr again.

Xr = Xr XOR P[17];

Xl = Xl XOR P[18];

Concatenate Xl and Xr back together (Remember our left and right? :)

This is function F, which is a BIT confusing, because of inconsistancies in

Schneier's explanation and Schneier's code:

Divide Xl into 4 8-bit quarters: a, b, c, and d.

((S1[a] + S2[b] mod 2(exp)32) XOR S3[c]) + S4[d] mod 2(exp)32;

A bit confusing, no? However, unless mod does not mean modulus, here's what

Schneier's code says instead:

((S1[a] + S2[b]) XOR S3[c]) + S4[d]

No modulus at all in there. Maybe the book has an errata list I can check

somewhere, I'll look at it later.

Here is the challenge for you all right now: write a function or macro for

function F. Assume the 4 S arrays are global variables. It will be

interesting to see how you split the 32-bit block into four 8-bit blocks.

Lastly, this is how subkey generation works (from the book again). Things in

parenthesis are notes from me:

"

(1) Initialize first the P-array and then the four S-boxes (the 4 S arrays),

in order, with a fixed string. This string consts of the hexadecimal digits

of pi.

(2) XOR P1 with the first 32 bits of the key, XOR p2 with the second 32 bits

of the key, and so on for all bits of the key (up to P18). Repeatedly cycle

through the key bits until the entire P-array has been XORed with key bits

(This is how it takes a variable-length key)

(3) Encrypt the all-zero string (bad English! Guess he didn't have a

proofreader) with the Blowfish algorithm, using the subkeys described in

steps (1) and (2). (Right now, the S-arrays are some of the hexadecimal

digits of pi, so remember, function F will still work, even though they

haven't really been "initialized" yet)

(4) Replace P1 and P2 with the output of step (3).

(5) Encrypt the output of step (3) using the blowfish algorithm with the

modified subkeys

(6) Replace P3 and P4 with the output of step (5).

(7) Continue the process, replacing all elements of the P-array, and then all

four S-boxes in order, with the output of the continuously changing Blowfish

algorithm.

"

I will follow up this post with the tutorial soon, right now I am just

cleaning up Schneier's code (which has given me a new respect to writing

stuff cleanly). In the mean time, let me see the answers to that challenge :)

Morgon

--

grab my updated (12/21/02) public key from http://www.surgo.net/pubkey.asc