Blowfish

From Computing and Software Wiki

Current revision as of 21:29, 12 April 2008

In cryptography, Blowfish is symmetric block cipher, designed in 1993 by Bruce Schneier. It is a fast and compact, that is, it provides a good encryption rate in software. There still exists no effective cryptanalysis of the algorithm and is therefore considered an extremely strong algorithm.

Blowfish was designed as an algorithm that could be used in everyday life by everybody, intended as a replacement of the Data Encryption Standard (DES). At that time most of the encryption algorithms in use were proprietary or kept secret by the governments, Blowfish broke away from that standard and Schneier placed it in the public domain to be used by anyone free of cost.

Blowfish Algorithm

Blowfish encrypts data in 64-bits blocks and has a variable key length between 32 and 448 bits. Also as Blowfish is a symmetric encryption algorithm, it uses the same secret key to encrypt and decrypt messages. A graphical representation of the blowfish algorithm can be seen in Figure 1.

In this figure we can see, a 64-bit plaintext message is first divided into 32 bits. The "left" 32 bits are XORed with the first element of a P-array to create a value P', run through a transformation function called F, then XORed with the "right" 32 bits of the message to produce a new value F'. F' then replaces the "left" half of the message and P' replaces the "right" half, and the process is repeated 15 more times with successive members of the P-array. The resulting P' and F' are then XORed with the last two entries in the P-array (entries 17 and 18), and recombined to produce the 64-bit ciphertext.

Figure 2
Graphical representation of F. [1 ]

Figure 2 shows a graphical representation of F, The function divides a 32-bit input into four bytes and uses those as indices into an S-array. The lookup results are then added and XORed together to produce the output. As previously mentioned blowfish is a symmetric algorithm and therefore employs the same technique to decrypt a message. The only difference being the output is in plain-text. The P-array and S-array values used by Blowfish are precomputed based on the user's key. In effect, the user's key is transformed into the P-array and S-array; the key itself may be discarded after the transformation. The P-array and S-array need not be recomputed (as long as the key doesn't change), but must remain secret. [1]

Cryptanalysis of Blowfish

There currently exists no effective cryptanalysis of blowfish highlighting the strength of the algorithm.

In 1996, Serge Vaudenay found a known-plaintext attack requiring 28r + 1 known plaintexts to break, where r is the number of rounds. Moreover, he also found a class of weak keys that can be detected and broken by the same attack with only 24r + 1 known plaintexts. This attack cannot be used against the regular Blowfish; it assumes knowledge of the key-dependent S-boxes. Vincent Rijmen, in his Ph.D. thesis, introduced a second-order differential attack that can break four rounds and no more. There remains no known way to break the full 16 rounds, apart from a brute-force search. [1]

Blowfish in Practise

Blowfish is one of the fastest block ciphers in widespread use, except while changing keys. Each new key requires pre-processing equivalent to encrypting about 4 kilobytes of text, which is very slow compared to other block ciphers. This prevents its use in certain applications, but is not a problem in others. In one application, it is actually a benefit: the password-hashing method used in OpenBSD uses an algorithm derived from Blowfish that makes use of the slow key schedule; the idea is that the extra computational effort required gives protection against dictionary attacks. See key strengthening.

In some implementations, Blowfish has a relatively large memory footprint of just over 4 kilobytes of RAM. This is not a problem even for older smaller desktop and laptop computers, but it does prevent use in the smallest embedded systems such as early smartcards.

Schneier designed Blowfish to be specifically used in performance constrained environments such as embedded systems. It has been extensively analyzed and deemed reasonably secure by the cryptographic community. Schneier now advises against the use of Blowfish and recommends using Twofish instead.Blowfish(cipher) [3]

See Also

• Peer To Peer Network Security
• Digital Signatures
• Public Key Encryption Algorithms
• Conventional Encryption Algorithms
  
• Digital Identity
  

References

1. Bill Gatliff: Encrypting Data With the Blowfish Algorithm Embedded.com June 15, 2003.
2. William Farmer: Cryptography, SE4C03 Course Website March 19, 2008.
3. Blowfish(cipher), Wikipedia March 3, 2008.
4. Bruce Schneier: The Blowfish Encryption Algorithm, schneier.com April 12, 2008.

External links

• Official Blowfish website
• List of products using Blowfish
• SCAN's entry for Blowfish
• Blowfish PHP and JavaScript implementation with online demo
• Blowfish JavaScript implementation and Page Encryption
• Blowfish PHP implementation
• Blowfish Java implementation (LGPL)

Signature

--Sheikha 17:27, 12 April 2008 (EDT)