click here for article

As wireless devices pervade deeper into our lives, it becomes increasingly important to maintain security. For example, the wired equivalent privacy protocol (WEP) used with 802.11b (the IEEE standard for wireless LANs) was recently shown to be easily broken. Such a security breach is a wake-up call to the wireless industry to implement effective secret communications. Cryptography is an ideal candidate.

Cryptography — past, present and future

Cryptography can be used in either software or hardware, but as bandwidth increases and the need for embedded encryption develops, hardware-based cryptography is preferred.

Cryptography, in Greek, literally means “hidden writing,” or the art of changing plain text (the message) into cipher text (an unreadable message). Cryptography has a long and ancient history, starting in ancient Roman times. One of the earliest ciphers used was the so-called Caesar code, which simply replaced a letter in the alphabet with another letter, shifting a set number of letters along the alphabet. For this code, an A becomes a D, a B becomes an E and so on. For shifted code, the alphabet reads as follows:

Plain text: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

shifted text: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

The basic crypto tools

While modern cryptography is a vast and complicated field, the basics of are easy to understand. Cryptography includes four commonly used tools: a cipher, a key exchange mechanism, a hashing core and a random-number generator.

• Cipher

  Ciphers are what most people think of when they hear the word cryptography. Given a known key, a cipher can either encrypt (turn plain text into cipher text) or decrypt (turn cipher text into plain text). The security of the system lies in the key being kept secret — only someone with the key can decode the message. Because the same key is used to encrypt and decrypt, this form of encryption is known as symmetric encryption.

  Ciphers come in two types: block and stream. Block ciphers operate on a block of plain text to produce a block of cipher text, whereas stream ciphers produce an output that is logically exclusive-ored with the plain text to produce cipher text. Most modern cryptography is based around block ciphers for two reasons: more analysis into the design of block ciphers has been carried out, and block ciphers can be modified for use as a stream cipher if needed.

• Key exchange mechanism

  To use the ciphers described above, the people sending the messages must agree on the key to be used with the cipher. However, if the people wishing to communicate have no secure lines to send the keys over, it is a seemingly impossible task to use cryptography securely. This was an insurmountable problem in cryptography for a long time. The problem was first overcome via the Diffie-Hellman algorithm, which allowed users to exchange keys over an insecure line using modular exponentiation¹. An example Diffie-Hellman key is shown in Table 1.

Users agree on a generator, g, and a modulus n (which can be made public).

An eavesdropper can intercept I_a and I_b, but to calculate the key K from these two numbers represents a substantial computational task.

The Diffie-Hellman algorithm was a major step forward for cryptography; it had not been possible to agree on a key over insecure lines without an eavesdropper being able to determine the key. However, this key exchange had to be performed for every two users on the net.

Stepping up the food chain

The next major step was the development of the RSA algorithm from RSA Security. For this algorithm, each user had a public and a private key. The public and private keys were mathematically related and a message enciphered using a public key could only be deciphered using the associated private key. The security of the system relied on the private key being kept secret so the public key could be freely distributed.

Public key cryptography is also known as asymmetric encryption because one key is used to encrypt the data and another is used to decrypt the data. Most real cryptography systems are hybrid systems, i.e. they use both symmetric and asymmetric encryption. Asymmetric encryption is used to exchange the key used for asymmetric encryption, and the bulk of the data is sent using symmetric encryption algorithms. This is because symmetric algorithms (such as defense encryption standards (DES)) are much faster than asymmetric algorithms (such as RSA).

Hashing — the digital fingerprint

A hash is a one-way function that can be used to create a digital “fingerprint” of data. This fingerprint is a number that is similar to a checksum for the data. If the file is modified in any way, then the hash value will also change.

Commonly used hash functions include SHA-1, which creates a 160-bit hash of a message of any size. These functions are used to create a checksum that can be recalculated later to ensure that the data have not been modified. If the file has been modified, then the calculated hash will be different. In cryptography, hash functions are used (as detailed below) for authentication.

Random number generator

Random numbers are used in cryptography for the keys used to encrypt data. If it is possible to guess the random numbers being used, then it is possible to guess at the keys being used for encryption. Creating truly random numbers is an incredibly difficult task. Due to the difficult nature of generating random numbers, a pseudo-random number generator (PRNG) is used. The PRNG generates a series of numbers that should be indistinguishable from a sequence of random numbers.

Several techniques are used to generate random numbers. They range from the simple linear feedback shift registers (LFSR), which are a series of flip-flops and XOR gates, to the complex Blum-Blum-Shub PRNG, which uses prime numbers and modular arithmetic. Most PRNGs use an initial seed, which should come from a physical source, such as hard-drive latency or PLL jitter.

Example cryptographic transaction

When a message is sent, there are two objectives. First, it is important to ensure the message can only be read by the intended recipient. It is also important to ensure that the message has not been altered in any way.

For example, user A can send a message to user B by encrypting the message using user B's public key. Only user B can decrypt this message even if other users receive it. However, user A also wants to ensure that the message is not modified en-route. Authentication allows user B to be certain that user A sent the message and that is has not been modified. To authenticate the message, user A must hash his plain text message and then encrypt this hash using his private key. This seemingly illogical step allows user B to verify that user A did send the message. If user B can decrypt the hash using user A's public key, then it was encrypted using user A's private key, which only he has.

User A then sends his privately encrypted hash and publicly encrypted message to user B. On receipt, user B can then decrypt the message using his private key and regenerate the message hash. They can also decrypt the encrypted hash using user A's public key, then compare the two hash values. This authenticates that user B sent the message and confirms the integrity of the message.

Cryptography and wireless

For wire-based networks, physical security was often adequate. A wire running from points A to B would be good enough to defeat eavesdroppers, and cryptography would be added if it was felt that anybody else had access to that wire. However, for wireless applications where data are beamed, it is difficult to ensure that only the intended recipient receives the data. For many cases, it does not matter — if you are just playing a wireless game between two telephones, who cares if other people can intercept the data? However, if you are beaming sensitive documents or carrying out personal conversations, the situation is different — especially with the merging of 3G and e-commerce. Nobody would walk down the street handing out their credit card details to complete strangers. But, without cryptography, that is essentially what would happen within e-commerce and wireless networks. Thankfully, the situation is not that bad — many different cryptographic protocols are used in conjunction with wireless networks to preserve users' privacy.

User 1	User 2
Generate random # A	Generate random # B
Calculate Ia = g ^ A mod n	Calculate Ib = g ^ B mod n
Transmit Ia	Transmit Ib
Calculate Ka = Ib ^ A mod n	Calculate Ka = Ib ^ A mod n
(K = Ka = Kb = g ^ (A*B) mod n)
Table 1. How the Diffie-Hellman key works.

WEP security analysis

A paper was recently published detailing an attack against the Wired Equivalent Privacy protocol². The protocol is part of the official 802.11b standard and is used to ensure that data can be sent securely at any speed. This protocol used the proprietary RC4 cipher developed by Ron Rivest (the R in RSA) in 1987. RC4 is a widely used stream cipher that consists of two parts: a key scheduling algorithm and a pseudo-random number generator. Due to its simplicity and perceived security, RC4 has become a popular cipher.

The paper by Flurhrer, Mantin and Shamir details two weaknesses in RC4: A series of weak keys in which a small part of the key affects a large number of bits in the output, and a flaw in the key-scheduling algorithm. For 802.11b, the key used was fixed, and there was an attack allowing a determined user to get access to the data using nothing more than a desktop computer with an 802.11 card. The attack exploited the fact that a fixed, secret key was used. The time to bypass the encryption grows linearly, rather than exponentially, with key size.

While this attack is not the end for RC4-based protocols, it does raise awareness of security issues and the shortcomings of WEP. For some users, enough security to stop casual eavesdroppers is sufficient. However, for secure traffic, another cipher will have to be used.

This has led to this question: If RC4 can be easily broken, which ciphers currently cannot and will not be breakable for the foreseeable future? One answer comes from the National Institute of Standards and Technology (NIST), the federal standards body that was responsible for the Data Encryption Standard (DES), the most widely used cipher in the world.

DES vs. AES

Currently, the federal standard for encryption is DES. IBM originally designed DES in 1974. It was based on a cipher called LUCIFER, which was written by Horst Feistel, who designed the general cipher models around which DES is based. DES was designed to be implemented in hardware and does not have the strength needed by modern cryptography. Triple DES (TDES) was introduced to solve the problem of the small key size, but the implementation was still mainly suitable for hardware.

It is now 27 years later, and NIST has identified the requirement for a new cryptography algorithm to replace DES. Requests for algorithms were tendered and five algorithms made it to the last round. Of the finalists, a cipher developed by a European team called Rijndael was selected to become the new federal standard, known as the Advanced Encryption Standard (AES). Several of the requirements that this standard had to fulfill were:

• It has be suitable for implementation in software or hardware.

• It has to have provision for use with larger key sizes.

• It has be suitable for high bandwidth networks.

In keeping with most modern algorithms, the algorithm picked for AES is a block cipher. The cipher operates 128-bit blocks of data, encrypting or decrypting with either 128, 192 or 256-bit keys. Key size is a good way to estimate the security of a system — each bit doubles the amount of work needed to brute-guess each of the keys. If a computer could perform a billion decrypts a second, it would take 10⁶⁵ years (or 10,000,000,000,000,000,000,0000,000,000,000,000,000,000,000,000,000,000,000,000,000 years) to exhaustively test each 256-bit key and every possibility.

So, why will DES (the current standard) be replaced by AES? The answer is not a simple one. There is a need for a faster algorithm with a larger key size, as DES can no longer be considered completely secure. In 1999, a $250,000 machine made by the EFF managed to break DES encryption in less than four days. However, that machine would still take roughly 10³¹ years to exhaustively test each TDES key. To put those numbers into context, the age of the universe is estimated to be 10¹⁰ years, so that is a billion, billion, billion, billion, billion, billion, billion times longer than the ages of the universe. DES and hence, TDES have been heavily analyzed, and in more than 25 years, no flaws have been found in the design. This means the algorithm is well-respected and trusted. DES' only weakness comes from its small key size, not from any flaws in the algorithm.

If it isn't broken, why fix it?

The main reason to change to AES is the need for a faster, more secure algorithm that is equally suited to software and hardware implementation. As broadband networks take off, it can be estimated that a high-end hardware AES solution should be able to encrypt 25 Gb/s of data. Conversely, a small, low-power hardware AES solution should be able to encrypt data at 290 Mb/s. The cryptographic community has extensively examined the AES algorithm, and no flaws have been discovered in the algorithm. However, the algorithm has only been analyzed for more than a year and has not received the large amount of cryptographic analysis and trust that DES has.

AES has yet to be fully ratified by NIST, but this should happen in the next few months. The draft specification documents are available, and it is unlikely that there will be any major modification to the algorithm. The only obvious change in the future might introduce the use of keys of different length.

A final word

The cryptography for wireless networks should be adequate to prevent casual eavesdroppers from overhearing conversations and determined hackers from getting your bank details. The cryptography solution must be transparent to the end user. Users will not be satisfied by a cryptography solution that results in a dramatic drop in performance. AES is coming and should be fully ratified by NIST in the near future. As the “wireless revolution” continues, the demand for cryptography will continue to rise.

References

1. B. Schneier, “Applied Cryptography,” John Wiley and Sons., 1996.

2. S. Fluhrer, I Mantin and A. Shamir, “Weakness in the Key scheduling Algorithm of RC4.”

Further Reading:
Steven Levy, Crypto,
Bruce Schneier, Secrets and Lies, John Wiley and Sons

About the author

Paul Lesso is a senior consulting engineer for Tality. He holds a PhD in physics from St. Andrews, Scotland University. His main areas of interest are cryptography, computer arithmetic and DSP. In 1999, Lesso was a joint winner of the National Physical Laboratory (NPL) international award for world-class metrology. He can be contacted at: plesso@tality.com.