The Blowfish block cipher was designed by Bruce Schneier and first published in Fast Software Encryption '93. It encrypts a 64 bit block under the control of a key, which can range in size from 0 to 448 bits (in increments
of 8). Blowfish quickly became very popular, largely due to its excellent performance in software, and its patent-free status. Most other alternatives at the time, such as DES, TripleDES, IDEA, and FEAL,
suffered from either poor performance (DES, TripleDES), IP entanglements (IDEA, FEAL), or less than great security (DES, FEAL).
Blowfish, in a sense, was the origin of the AES process that ended with the Rijndael algorithm becoming the official replacement for DES in the U.S. government (for securing non-classified data). In the FSE paper, Schneier suggested that the world needed a highly secure, IP-free algorithm to be used for high security applications in the 21st century. Ironically, Schneier's own AES candidate, Twofish, was beaten in the AES competition.
As to how it works. Blowfish initializes 5 tables: S{1,2,3,4}, each of which contains 256 32-bit values, and also P, which contains 18 32-bit values, using a (rather inelegant) PRNG based off of the encryption routine.
The algorithm uses the big-endian convention, and splits it's 64 bit input into two 32-bit words, called L and R (the left and right halves). Arrays are accessed using 0-based indicies.
For i = 0 to 15:
L = L XOR P[i]
R = F(L) XOR R
Swap L and R
Swap L and R (Undo the last swap)
R = R XOR P[16]
L = L XOR P[17]
The F function used above is defined as:
F(L) = ((S1[L0] + S2[L1] mod 232) XOR S1[L2]) + S4[L3] mod 232
Where
L0,
L1,
L2, and
L3 are the four bytes of L (
L0 being the first, or most significant, byte and
L3 being the least significant). In an actual implementation you wouldn't do the swaps: instead the code will
unroll the loop at least once and maybe twice.
Even after 10 years, Blowfish is still considered quite secure. The only attack (that I know of) was published by Serge Vaudeney in his PhD thesis, which showed that certain keys were "weak" in the sense that they could be
distinguished from other keys. Given that even this attack only works if you reduce the number of rounds from 16 to 14, it is quite safe to say that there is no publicly known attacks on Blowfish which might concern potential or current users of the algorithm. Given this track record, and the general structure of the algorithm, it highly unlikely that any serious attacks will be developed anytime within the next 10 years (at least in this amateur cryptographer's opinion).
While secure and quite fast, Blowfish is not perfect. For one thing, the block size is only 64 bits long. These days, that raises a number of concerns, which is why almost all new ciphers use blocks at least 128 bits in length. Basically, the problem is that there are a number of quite general collision attacks possible on things using block ciphers (like CBC mode), and a 64 bit block means these attacks can work with 232 complexity (that's bad). In addition, changing the key that Blowfish uses to encrypt involves as much work as encrypting 521 blocks, which is quite substantial. Most block ciphers take about as much time to run the key schedule as it takes to encrypt a single block. The term for this property of Blowfish is low key agility.
While Blowfish is very fast in software, it requires the use of at least 4K of RAM, which is very expensive in hardware (compared to something like DES or even IDEA) or in memory constrained environments (like smartcards). More recent ciphers, like Rijndael and Serpent, are easier on hardware resources. Many other ciphers allow various speed/memory tradeoffs in software, and in a standard issue CPU, a few extra kilobytes of memory is not a problem. But with Blowfish, you have to have that 4K of memory, and that's bad. DES, for example, can be implemented using just a few hundred bits of memory (probably just registers).
Because it is simple and free (and probably, because of the widely available source code on the Internet), Blowfish is particularly commonly seen among basic shareware encryption programs (much more common than, for example, CAST-128, which is very similar to Blowfish in flavor).
You can find out more about Blowfish at http://www.counterpane.com, which is the web site of Schneier's company. A huge number of software libraries support Blowfish, so if you decide to use it, it will probably be easier to get one of those than deal with the reference implementation (which isn't so great) or coding it yourself (never a good idea for crypto neophytes; it's very easy to mess things up).
Props to jrn for helping me out with my terrible grammar in this writeup.