Blowfish

Blowfish is a symmetric block cipher that uses a variable-length key up to 448 bits in length. It was designed in 1993 by Bruce Schneier as a drop-in replacement for DES and IDEA. It is fast and well tested. It is also unpatented and license-free and available to anyone by visiting Schneier’s web site at http://www.counterpane.com/blowfish.html.

The next section turns to asymmetric cryptographic systems and how they operate. Recall that asymmetric schemes use two keys (public and private), as opposed to symmetric schemes, which use one secret key.

Asymmetric (Public-Key) Cryptography

The basics of public key cryptography were discussed previously. Every user has a public key that is given out freely and a private key that they hold secretly. To send a private message to someone else, you encrypt it with the recipient’s public key. The recipient then decrypts it with their private key. The technique is simple and elegant. However, getting two keys that work together and that maintain high levels of security is a little more complex.

The many uses of public key cryptography were also discussed, including the capability to exchange private messages with anyone without first exchanging a private key, the capability to digitally sign a document, and the capability to engage in all sorts of electronic commerce in a safe and secure way.

Other public key schemes are available, but the RSA scheme has gained worldwide support. Therefore, only RSA is discussed from here on. It is basically a block cipher that converts plaintext to ciphertext like the secret key schemes mentioned earlier, except that two keys exist. Creating two keys that work in concert is the all-important feature of RSA.

The gist of this scheme is that it is possible to generate a pair of keys in which someone can encrypt a message with one key in the pair and someone else can decrypt the message with the other key in the pair. At the same time, it is not possible for someone to determine the private key by knowing the public key, nor is it possible for someone to decrypt a message with the same key that was used to encrypt the message. Only the other key in the pair can decrypt a message.

Here is how the key pairs are generated, according to RSA Data Security:

“Take two large primes, p and q, and find their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed-1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n,d). The factors p and q may be kept with the private key, or destroyed.”

Once the key pairs are generated, encryption and decryption can take place. To send a secret message to someone, you obtain their public key to encrypt the message and the recipient decrypts the message with their private key. But what method is used for the encryption?

The RSA public key cryptosystem is based on a trap-door, one-way function. Recall that a one-way function is easy to perform in one direction (encrypt) but difficult to perform in the other direction (decrypt). For example, encryption might take a few seconds while decryption could take years with the most powerful computers. A trap-door one-way function is a one-way function in which decryption is very difficult unless you have a certain piece of information (i.e., the trap door or key). In RSA, the public key is used to encrypt using a one-way function and the private key is used to decrypt.

Even though RSA’s system is secure, it makes mention in its own documentation that one-way functions are believed to be secure (one-way), but there is no proof for it so far and the possibility exists that someone could compute the functions without a key. This sets the stage for a discussion of cryptanalysis as outlined in the next section.

Attacks and Cryptanalysis

Cryptanalysis is the “art” of trying to discover the original message by analyzing the ciphertext. In some cases, cryptanalysis may involve repeated attempts to find some discernible patterns in the ciphertext, or it may involve running the same algorithm over and over again using different keys until the matching text is found.

The algorithms for most cryptosystems are well-known, so we start this discussion with the assumption that the cryptanalyst has the algorithm in hand at the start of the attack. Additional security can be obtained by hiding the algorithm as well, but with public systems this is not an option. Users of private systems like the CIA choose to hide their algorithms.

In most cryptosystems, the algorithm is distributed to all users and the strength of the system is in the key and how well the algorithm uses it to encrypt information. In addition, the length of the encryption key determines how well the resulting ciphertext is encrypted and will hold up against brute force attacks. A brute force attack, as mentioned earlier, is one in which every possible key is tried in an attempt to decrypt the ciphertext.

Many cryptographers believe that brute force attacks are basically unfeasible when long keys are used, even as computer power increases. Brute forcing ciphertext that has been encrypted with a large key (over 100 bits) could take millions or billions of years even with powerful networked computer systems. In addition, adding a single bit to the key doubles the cost of performing such a brute-force cryptanalysis.

The possibility exists, however, that a weakness in the system excludes some keys, which reduces the number of keys that need to be tested. For example, a cryptanalyst might discover that an algorithm thought to produce random numbers actually has some repeating pattern. This “weakness” in the system may provide an avenue for exploitation.

Still, what are the chances that the cryptanalyst will know that one of the millions of keys tested is the key that decrypts the message. What if the original plaintext is itself a ciphertext? The cryptanalyst may not find anything recognizable even if the correct key is found. In addition, is the cryptanalyst sitting at a computer and watching the results of each key that is tested?

We can assume that a brute force attack is impossible given that long keys are used. Some people have gone to great lengths to describe models in which all the energy of the sun over a period of millions of years is necessary to power all the computers necessary to find a key.