Blowfish is a symmetric block cipher that can be effectively used for encryption and safeguarding of data. It takes a variable-length key, from 32 bits to 448 bits, making it ideal for securing data. Blowfish was designed in 1993 by Bruce Schneier as a fast, free alternative to existing encryption algorithms. Blowfish is unpatented and license-free, and is available free for all uses. Blowfish Algorithm is a Feistel Network, iterating a simple encryption function 16 times. The block size is 64 bits, and the key can be any length up to 448 bits. Although there is a complex initialization phase required before any encryption can take place, the actual encryption of data is very efficient on large microprocessors. Blowfish is a variable-length key block cipher. It is suitable for applications where the key does not change often, like a communications link or an automatic file encryptor. It is
significantly faster than most encryption algorithms when implemented on 32-bit microprocessors with large data caches.
- Manipulates data in large blocks
- Has a 64-bit block size.
- Has a scalable key, from 32 bits to at least 256 bits
- Uses simple operations that are efficient on microprocessors.
e.g., exclusive-or, addition, table lookup, modular- multiplication.
It does not use variable-length shifts or bit-wise permutations, or conditional jumps. It employs precomputable sub keys on large-memory systems, these sub keys can be precomputed for faster operation. Not precomputing the sub keys will result in slower operation, but it should still be possible to encrypt data without any precomputations. It consists of a variable number of iterations. For applications with a small key size, the trade-off between the complexity of a brute-force attack and a differential attack make a large number of iterations superfluous. Hence, it should be possible to reduce the number of iterations with no loss of security (beyond that of the reduced key size). Uses sub keys that are a one-way hash of the key. This allows the use of long passphrases for the key without compromising security. Has no linear structures that reduce the complexity of exhaustive search. It uses a design that is simple to understand. This facilitates analysis and increase the confidence in the algorithm. In practice, this means that the algorithm will be a Feistel iterated block cipher.
DESCRIPTION OF THE ALGORITHM:
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 sub key 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.
Blowfish uses a large number of sub keys. These keys must be precomputed before any data encryption or decryption.
The P-array consists of 18 32-bit sub keys:
P1, P2,…, P18.
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.
Blowfish has 16 rounds. The input is a 64-bit data element, x.
Divide x into two 32-bit halves: xL, xR.
Then, for i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR. After the sixteenth round, swap xL and xR again to undo the last swap.
Then, xR = xR XOR P17 and xL = xL XOR P18.
Finally, recombine xL and xR to get the ciphertext.
Decryption is exactly the same as encryption, except that P1, P2,…, P18 are used in the reverse order.
Implementations of Blowfish that require the fastest speeds should unroll the loop and ensure that all sub keys are stored in cache.
A 64-bit block size yields a 32-bit word size, and maintains block-size compatibility with existing algorithms. Blowfish is easy to scale up to a 128-bit block, and down to smaller block sizes. The fundamental operations were chosen with speed in mind. XOR, ADD, and MOV from a cache are efficient on both Intel and Motorola architectures. The Feistel Network that makes up the body of Blowfish is designed to be as simple as possible, while still retaining the desirable cryptographic properties of the structure. In algorithm design, there are two basic ways to ensure that the key is long enough to ensure a particular security level. One is to carefully design the algorithm so that the entire entropy of the key is preserved, so there is no better way to cryptanalyze the algorithm other than brute force. The other is to design the algorithm with so many key bits that attacks that reduce the effective key length by several bits are irrelevant. Since Blowfish is designed for large microprocessors with large amounts of memory, the latter has been chosen. But it works equally well on Handheld systems with a decent microprocessor. The sub key generation process is designed to preserve the entire entropy of the key and to distribute that entropy uniformly throughout the sub keys. It is also designed to distribute the set of allowed sub keys randomly throughout the domain of possible sub keys. The digits of pi were chosen as the initial sub key table for two reasons: because it is a random sequence not related to the algorithm, and because it could either be stored as part of the algorithm or derived when needed. But if the initial string is non-random in any way (for example, ASCII text with the high bit of every byte a 0), this non randomness will propagate throughout the algorithm. In the sub key generation process, the sub keys change slightly with every pair of sub keys generated. This is primarily to protect against any attacked of the sub key generation process that exploit the fixed and known sub keys. It also reduces storage requirements. The 448 limit on the key size ensures that the every bit of every sub key depends on every bit of the key. The key bits are repeatedly XORed with the digits of pi in the initial P-array to prevent the following potential attack: Assume that the key bits are not repeated, but instead padded with zeros to extend it to the length of the P-array. An attacker might find two keys that differ only in the 64-bit value XORed with P1 and P2 that, using the initial known sub keys, produce the same encrypted value. If so, he can find two keys that produce all the same sub keys. This is a highly tempting attack for a malicious key generator. To prevent this same type of attack, the initial plaintext value in the sub key generation process is fixed. The sub key-generation algorithm does not assume that the key bits are random. Even highly correlated key bits, such as an alphanumeric ASCII string with the bit of every byte set to 0, will produce random sub keys. However, to produce sub keys with the same entropy, a longer alphanumeric key is required. The time-consuming sub key-generation process adds considerable complexity for a brute-force attack. The sub keys are too long to be stored on a massive tape, so they would have to be generated by a brute-force cracking machine as required. A total of 522 iterations of the encryption algorithm are required to test a single key, effectively adding 29 steps to any brute-force attack. The most efficient way to break Blowfish is through exhaustive search of the key space.