Source Code & Canadian Export Laws
It is quite obvious that certain applications of transferring data require a secure method of doing so. There are many different encryption algorithms available to help keep the transfer of data secure. However, many of these algorithms are unavailable to the public. Bruce Schneier is one of the world's leading cryptologists. He is the president of Counterpane Systems, a consulting firm specializing in cryptography and computer security. Aside from his duties of presiding over Counterpane Systems, he has contributed many written documents on the subject of cryptography, including the book Applied Cryptography, (John Wiley & Sons, 1994 & 1996), which has been described as an influential literary work in the field of cryptography. As if this wasn't enough, he also developed a variable length key, 64-bit block cipher (a.k.a. the blowfish algorithm). It was his intent from the outset of creating this new encryption algorithm to provide the world with a new encryption standard. While there are many secure algorithms that have already been created, many of them are protected by patents (Khufu [11,12], REDOC II [2,23,30], and IDEA [7,8,9] or being kept secret by governments (Skipjack and Capstone protected by the U.S. government). Other algorithms are available, only in part (RC2, RC4, and GOST). The blowfish algorithm was first introduce in 1993, and has not been cracked yet. It is also noteworthy to point out that this algorithm can be optimized in hardware applications, although it, like most other ciphers, is often used in software applications.
Schneier admits that the blowfish algorithm does not meet a set of parameters that he feels is necessary for a new encryption algorithm; however, it has been impenetrable thus far. Nevertheless, he acknowledges that there is still room for improvement. While it may not be suitable for all applications, this algorithm may be used in instances where the key does not change often. Also, it should be noted that blowfish is significantly faster than DES.
Specifically for hardware applications (i.e. VHDL), three separate components must be integrated: the master component, the encryption component, and a counter. The master component basically controls the process from the time that the data is received until the time it is ready to be sent as an encrypted data stream. Note that the encryption and counter components are called by the master component, thus making simulation easier since all of the signals are included in that document.
The blowfish component basically starts and ends the encryption process. Upon sending a signal that identifies that it is ready to read in data, the blowfish component receives data from the interface being implemented to transmit data. Once all of the data has been read in, it is time to encrypt the data. In VHDL, a signal is asserted low once this happens.
The encryption component is responsible for actually encrypting the data. Once it has read in the data, it separates the 64-bit cipher into two halves. After this has been accomplished, a sixteen iteration 'for' loop must be created. At this point, for use with VHDL, another component must be included. As stated earlier, this component is simply a counter to count the iterations. For the blowfish algorithm, it counts up for encryption and down for decryption. Once the sixteen iterations of the loop have been completed, the algorithm is able to calculate the final outputs of the two halves and recombine them into an outgoing 64-bit cipher.
There are two parts to this algorithm; a part that handles the expansion of the key and a part that handles the encryption of the data.
The first step in the algorithm is to break the original key into a set of subkeys. Specifically, a key of no more than 448 bits is separated into 4168 bytes. There is a P-array and four 32-bit S-boxes. The P-array contains 18 32-bit subkeys, while each S-box contains 256 entries.
The following steps are used to calculate the subkeys:
The Blowfish Algorithm
Note: the 64-bit input is denoted with an x, while the P-array is denoted with a Pi (where i is the iteration).
The Function F
Implementing the blowfish algorithm in a design course seemed like a viable option for encryption, considering that it was intended to be fast, compact, simple, and variably secure. Nevertheless, it should be pointed out that this algorithm is better-suited to software than hardware. Specifically, the VHDL implementation of the algorithm requires many states. In the state machine that the eSAFE group implemented, the master component has 10 states, while the encryption component has 18 states. An example of the size constraints in hardware can be seen by noting that for a 20000 gate chip (Altera 10K20), an optimized VHDL implementation of the blowfish algorithm (using Altera's recommended state machine) requires 634 of 1152 cells (or 55%) of the chip. This may not be of much concern if a larger chip is available or a simple method of transmitting data is used.
Canadian Export Laws on cryptographic export are more rigid than those of the United States of America. While some of the examples displayed on Canadian Export Laws on cryptographic export suggest that source code of the blowfish algorithm (publicaly available from the U.S.A) may be freely distributed, to ensure that no laws are broken, it will not be made available here. Nevertheless, if you are interested in viewing some source code, see resources available on the internet at blowfish algorithm or see the book Applied Cryptography. Primarily, this code is written in C and there doesn't seem to be any VHDL code available for the blowfish algorithm; nevertheless, I hope that this application note gives some insight as to an approach to implementing the blowfish algorithm in hardware, under the right circumstances.
Schneier has encouraged the cryptanalysis of his blowfish algorithm and while it has been broken, in part, it has not been broken significantly. Through cryptanalysis, it has been noted that weak keys can be detected. This attack does not work after 16 rounds of blowfish, however. Thus, it seems that blowfish is a reasonable encryption algorithm, especially for an unpatented one.
The following links are quite useful (the second contains source code for the algorithm in C):
The book Applied Cryptography is also a great reference, especially since it was written by the author of the blowfish algorithm.
If you have any questions or comments that you would like clarified, please send mail to the address below. I will then be able to answer your questions and update the app note. Also, I will update the app note as the algorithm is implemented into our design.
This note maintained by: Kevin Hackett <khackett@telusplanet.net>
Last updated: Thursday November 26, 1998