[Courses] [C] A tutorial on Blowfish

[Morgon Kanter]

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