Standards Institute Studies Encoding Formula Options

August 1999
By Michelle L. Hankins

Process to develop new encryption standard involves governments, industry worldwide.

A U.S. organization that is heading efforts to develop a new standard for cryptography may opt for more than one algorithm to serve widely varying global requirements for secure communications in such applications as electronic mail or video. The advanced encryption standard, when it is chosen, will be the successor to a data encryption standard that was developed approximately 20 years ago. It was adopted by users internationally, and the new scrambling code promises to be equally well received.

Since the search for a new standard began in January 1997, the National Institute of Standards and Technology has been testing and analyzing candidate algorithms that have been submitted for consideration. These mathematical formulas are the fundamental drivers of computerized encryption systems.

Recognizing the need to keep up with technology that has diminished the effectiveness of the older data encryption method, the standards institute has established forward-thinking requirements that experts predict will protect the life span of the code. Because developers have created algorithms with longevity in mind, some knowledgeable observers estimate that the new standard will be used for more than 25 years.

The current data encryption standard (DES) was chosen in the 1970s through a U.S. government-sponsored program. The selection process was closed to the international community, and the algorithm was, for the most part, examined privately by the U.S. government. DES has a 56-bit key size with the possibility of 72,057,594,037,927,936 keys. The standard employs a 64-bit block size, coding data in these 64-bit installments.

The National Institute of Standards and Technology (NIST), Gaithersburg, Maryland, has recognized the need for a new algorithm for some time, says Miles Smid, who is acting chief of the computer security division and is leading the team working to institute the advanced encryption standard (AES), the DES replacement. The time has come to replace DES, Smid states, because the standard is limited by its key size.

Other organizations have also cited the need for an advanced standard. A Bedford, Massachusetts, company has made significant efforts to encourage the adoption of a new algorithm. In July 1998, RSA Laboratories offered a $10,000 prize to anyone who could penetrate DES. The company wanted to show that it is feasible to attack DES in spite of its 56-bit key size, says Burt Kaliski, chief scientist and director of the firm.

A team of cryptography experts claimed the prize by deciphering the DES key within three days. They employed a highly specialized key-search machine called Deep Crack that was custom-built to sift through potential keys. The machine used circuits to test keys and to stop whenever a possible key or match was found. Each chip within the machine was capable of testing 60 million keys per second.

While NIST has known for some time that a new standard is needed, RSA’s contest further demonstrated the point. “Cracking [DES] certainly helped to illustrate the importance of moving to AES,” Smid admits.

Since commencing the search for a replacement standard, NIST has held workshops and invited comments from the public, and 15 candidate algorithms have been involved in the first round of the selection process. A global pool of cryptographers and cryptanalysts is participating in the discussions and is analyzing the algorithms. NIST has invited people to find flaws in the algorithms, and Smid observes that university professors and companies are submitting papers about possible holes in the formulas. NIST itself is running statistical tests to look for any abnormalities in the candidate algorithms.

The intent is to select a standard that would be beneficial worldwide for both government and commercial users. Twelve nations are represented among the candidates, 10 of which are from non-U.S. companies, organizations or universities. “It is definitely an international undertaking. We decided from the beginning that it would be,” Smid explains.

The standard will be used for a wide variety of applications, mainly in network communications to prevent people from eavesdropping. In addition to being used in e-mail to secure data or for video being transferred between two parties, AES will also be used in electronic commerce and banking, which are two areas that will rely heavily on the new standard. NIST officials agree that the extent of potential applications for AES is yet to be envisioned.

Throughout the selection process, NIST will narrow the candidate field to allow the agency to challenge the remaining algorithms’ capabilities in greater detail. Ultimately, more than one algorithm could be chosen if it is deemed necessary to support the many different applications for which the standard will be used. The goal is to make AES a standard for federal information-processing, and as such, it will require approval by the secretary of commerce.

NIST’s AES requires a symmetrical encryption algorithm. This type of cryptography allows faster encryption than can be achieved with other methods, an important characteristic because both the government and commercial sectors typically generate large amounts of data. AES will be used in conjunction with public/private key cryptography to pass the key between users. NIST has called for a minimum 128-bit key size for AES with 192- and 256-bit key sizes to be available as well. A block cipher encrypts blocks of a specified number of bits at one time.

In determining AES, the organization is looking at three key points—security, efficiency and flexibility. Emphasizing security as a top priority, NIST is evaluating the significance of all theoretical or proposed attacks on each algorithm. The organization also is looking at the efficiency of each algorithm to judge how fast the formulas work and how much memory they will require. To test this, NIST is running the algorithms on various platforms. The algorithms’ flexibility, such as their ability to be used for a variety of applications, is also a factor, Smid says.

Some nations have already adopted new standards to replace DES. For example, Canada has instituted the use of a new algorithm to encrypt data, known as CAST-128. A newer version of the algorithm, CAST-256, has been among the candidates for the NIST AES effort. Originally developed in 1988, the latest version of the CAST algorithm is used for such applications as a bulk encryption of all files on a hard drive and for transferring secure Internet protocol packets and video.

Senior Cryptographer Carlisle Adams, Entrust Technologies, Plano, Texas, developed the original CAST design along with his thesis supervisor, Dr. Stafford Tavares, during his graduate studies. Adams agrees that flexibility is important when choosing the algorithm. Since AES will be implemented in many different parts of the world for various applications, the algorithm must be able to run efficiently on a number of different platforms. He adds that various levels of security can result in differences in encryption speed.

Adams predicts that AES could potentially be effective for 50 years or more. With its suggested key and block sizes, he believes it is unlikely that technology will be able to uncover the key from among the possibilities. He notes that participation from the cryptography community in the AES process has been small but vigorous. “AES has done a lot to reinvigorate this entire field,” Adams says. Particularly, he notes that the emphasis placed on searching for possible attacks to the proposed algorithms may uncover a whole new class of attacks.

RSA Laboratories, the company that challenged DES, has also participated in the selection of a new algorithm. RSA’s team of cryptographers and Ron Rivest, a company founder, developed its RC6 specifically for the NIST project. RC6 is a block cipher that uses data-dependent rotations. This method of encryption rotates part of the data in a circular fashion to shift the information. The amount of data shifted depends on other parts of the data. In rounds likened to the rounds used in DES, half of the data is updated by the other half and then the two are swapped.

Kaliski says that RC6 is intended to be a general-purpose algorithm. It can be used to request authentication, to encrypt cable television or to transfer data on the Internet.

Another company that submitted an algorithm during the first round of competition is IBM. Called MARS, for multiplication addition rotation substitution, this algorithm is one of 12 that were developed by an IBM team and is the company’s AES entry. MARS has a 128-bit block size and a variable key size of 128 to 1,248 bits. It is a type-3 Feistel network consisting of many rounds in which one data word and several key words are used to modify all other data words. It has a mixing function that performs data scrambling in front and back of a core. This heterogeneous structure gives it two layers of security.

According to Nev Zunic, program manager, IBM Cryptography Center of Competence, Poughkeepsie, New York, MARS developers added security by reducing performance speed by 40 percent. The speed dropped from 104 megabits per second on an Intel platform 200-megahertz processor to 65 megabits per second on the same processor when using MARS. Despite this performance drop, Zunic maintains that the algorithm has still tested high compared to other entries. It runs four times faster than the DES algorithm, according to Zunic.

NIST has received positive feedback about the selection process to develop the new standard. Kaliski described the effort as a “fruitful collaboration across the world.” Once AES is finally approved, Smid suggests that there will be a transition period. He estimates that vendors will likely start building AES-compliant products by August 2000, with the standard attaining full approval sometime the following year. Zunic suggests that there will be a coexistence of DES and AES until AES gains the confidence of users around the globe. For those that do not make the final cut for AES, Adams believes they will be used internally by the nations or companies that developed them.