Other Cryptosystems

Symmetric Key Algorithms and the Key Distribution Problem

Before the invention of public key systems, if two persons wished to communicate secretly, they had to agree on an algorithm and a secret between them. This meant that for every conceivable pair of communicating parties, there had to be a unique key/algorithm. These keys have to be decided upon securely. This is a non-trivial problem, as it requires an expensive means of key distribution. Banks and large corporations which depended on encryption for business transactions used to spend large amounts of money sending new keys out using couriers before the advent of the public key distribution solution. But before we discuss that, let's look at some of the symmetric key systems.

Data Encryption Standard (DES)

In the early 1970s there was no standard encryption protocols; the many different products were not inter-operable. The military used its own scheme and commercial business's used different products with no real idea of the security of the system. In fact, research into cryptography was not widespread. In an attempt to change this, the National Institute of Standards and Technology (NIST) started a program to protect computer and communications data. A public request for proposals was issued in 1973.

It was not until a second request for proposals (the first not getting good enough responses) that IBM submitted an algorithm they had been developing called Lucifer. After consulting with the National Security Agency (NSA), and after much discussion within the industry, DES was accepted as a standard for encrypting all unclassified government data. Later the American National Standards Institute (ANSI) approved DES as a private sector standard.

Not everyone was happy with DES. Many critics were not happy with the NSA's involvement. They believed that the complicated inner workings of the algorithm may have been to allow a trapdoor in the scheme. Also there was much complaining that the NSA had advised that the key length be reduced from 128-bits to 56-bits. Later the NSA themselves expressed dismay at the manner in which the standard had been published. They had thought that the algorithm would be implemented in hardware only, with the exact algorithm remaining secret. However, the specifications were available to the public, allowing cryptanalysts a head start in attacking the cryptosystem.

Detailed descriptions of DES can be found in Applied Cryptography and in the Handbook of Applied Cryptology. But basically the algorithm is to perform 16 rounds of substitution and permutation based on the key, on blocks of 64 bits. It uses only standard arithmetic and logical operations on numbers of 64 bits at most, so it was implementable easily on the hardware of the time.

The security of DES has been in doubt from the very beginning. As mentioned a lot of people critisized the involvement of the NSA in the project. In fact in 1990 Eli Biham and Adi Shamir showed that DES was indeed insecure through the use of a new form of cryptanalysis - Differential Cryptanalysis. This form of analysis looks at ciphertext pairs - that is pairs of ciphertexts whose plaintexts have particular differences. The technique relies on certain fixed differences between the plaintexts. The attacker does not even have to know the values of the plaintexts!. The more ciphertexts that the attacker gets access to, the more a key emerges.

Varients of DES have come about over the years. Triple DES involves 3 rounds of DES. DESX uses a technique of "whitening" the key before encrypting by XORing a 64-bit whitening key with the plaintext before and another 64-bit number derived from the entire key XORed to the ciphertext. These techinques and others, improve the security of DES against brute-force attacks, but since the original DES is not trustworthy anymore, it is questionable if we could build a secure system on top of it. A new encryption standard was needed and the NIST issued another call for proposals.

Advanced Encryption Standard (AES) - Rijndael

I have recently, for a project in my Computer and Network Security course written a servlet that demonstrates Rijndael (pronounced Rhine-Doll). It takes a key and a short message and returns the hex. Try it out

Public Key Systems

There are some other cryptosystems based on public key algorithms.

ElGamal

I mentioned above the servlet demonstrating Rijndael; well it also contains an example of ElGamal. Try it out.

ElGamal works slightly differently from RSA. It is based on a different one way function and encrypts plaintext to pairs of numbers.

I will expand on these explanations of AES, DES and ElGamal tommorow.

Ronan Killeen
Back to home.