What is Block Cipher?

  A block cipher transforms a fixed-length block of plaintext data into a block of ciphertext data of the same length. This transformation takes place under the action of a user-provided secret key. Decryption is performed by applying the reverse transformation to the ciphertext block using the same secret key. The fixed length is called the block size, and for many block ciphers, the block size is 64 bits. Since different plaintext blocks are mapped to different ciphertext blocks (to allow unique decryption), a block cipher effectively provides a permutation of the set of all possible messages. The permutation effected during any particular encryption is of course secret, since it is a function of the secret key. More information about block ciphers and the various available algorithms can be found in almost any book on contemporary cryptography and in RSA Laboratories.

DES.
DES was developed as a standard for communications and data protection by an IBM research team, in response to a public request for proposals by the NBS - the National Bureau of Standards (which is now known as NIST).

DES is a very interesting algorithm in many respects. Perhaps one of the most interesting aspects is the manner in which it has remained a secure algorithm over the past 20 years while public study of encryption has made phenomenal advances. To this day, the most practical attack against DES is a brute-force attack - one where the attacker tries each of the possible 2^56 keys on a plaintext and matches the result against the known corresponding ciphertext. (This isn't really true. Differential cryptanalysis will find a key faster, but you need 2^47 chosen plaintext to mount this attack. That is truly a proverbial buttload.) The biggest problem with DES is the fact that it uses only a 56-bit key, which is quickly becoming trivial to break as computing power continues to increase by a factor of 10 every 5 years.

Differential cryptanalysis is a technique for breaking an encryption algorithm by using pairs of cipertext with particular differences and studying how these differences evolve through the encryption. It was first published in 1990 by Eli Biham and Adi Shamir, yet the structure of DES's S-boxes are specifically built to resist this attack. Both the IBM research team which developed DES and the NSA, which worked with the IBM team through the development, were therefore (as they later admitted) aware of this technique in the early 1970's!

DES is a block algorithm using 64-bit blocks and a 56-bit key. The algorithm is symmetric, meaning the same algorithm and key are used for encryption and decryption. It consists of an initial and final permutation, and 16 rounds.

The key is usually stored as a 64-bit number, where every eighth bit is a parity bit. The parity bits are pitched during the algorithm, and the 56-bit key is used to create 16 different 48-bit subkeys - one for each round. The 64-bit block being enciphered is broken into two halves. The right half goes through one DES round, and the result becomes the new left half. The old left half becomes the new right half, and will go through one round in the next round. This goes on for 16 rounds, but after the last round the left and right halves are not swapped, so that the result of the 16th round becomes the final right half, and the result of the 15th round (which became the left half of the 16th round) is the final left half.

A variant of DES, Triple-DES or 3DES is based on using DES three times (normally in an encrypt-decrypt-encrypt sequence with three different, unrelated keys). Many people consider Triple-DES to be much safer than plain DES.

Implementations of DES can be found e.g. in the libdes, alodes, SSLeay, Crypto++, descore, chalmers-des, and destoo libraries.

Blowfish.
Blowfish is a variable-length key, 64-bit block cipher. The algorithm consists of two parts: a key-expansion part and a data encryption part. Key expansion converts a key of at most 448 bits into several subkey arrays totaling 4168 bytes.

Data encryption occurs via a 16-round Feistel network. Each round consists of a key-dependent permutation, and a key- and data-dependent substitution. All operations are XORs and additions on 32-bit words. The only additional operations are four indexed array data lookups per round.

Subkeys:
Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption can be done.
  1. The P-array consists of 18 32-bit subkeys: P1, P2,..., P18.
  2. There are four 32-bit S-boxes with 256 entries each:
    S1,0, S1,1,..., S1,255;
    S2,0, S2,1,..,, S2,255;
    S3,0, S3,1,..., S3,255;
    S4,0, S4,1,..,, S4,255.

The exact method used to calculate these subkeys will be described later.

Encryption:
Blowfish is a Feistel network consisting of 16 rounds. The input is a 64-bit data element, x.

  1. Divide x into two 32-bit halves: xL, xR
  2. For i = 1 to 16:
  3. xL = xL XOR Pi
  4. xR = F(xL) XOR xR
  5. Swap xL and xR
  6. Swap xL and xR (Undo the last swap.)
  7. xR = xR XOR P17
  8. xL = xL XOR P18
  9. Recombine xL and xR
  10. Function F:
  11. Divide xL into four eight-bit quarters: a, b, c, and d
  12. F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232

Decryption is exactly the same as encryption, except that P1, P2,..., P18 are used in the reverse order.

Generating the Subkeys:
The subkeys are calculated using the Blowfish algorithm. The exact method is as follows:

  1. Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of pi (less the initial 3). For example:

    P1 = 0x243f6a88
    P2 = 0x85a308d3
    P3 = 0x13198a2e
    P4 = 0x03707344

  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 (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

  3. Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2).
  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 entries of the P-array, and then all four S-boxes in order, with the output of the continuously-changing Blowfish algorithm.

In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys rather than execute this derivation process multiple times.