Advanced cryptographic program increases security and flexibility.
The U.S. government is poised to adopt a new encryption standard that will replace existing ciphers used in secure, nonsecret communications. The algorithm is compatible across a variety of software and hardware applications and in limited-memory environments such as smart cards.
Advances in computer technology have made older cryptographic systems vulnerable to cracking. Ciphers with relatively short key lengths can now be compromised through brute-force computing. Researchers are preparing modern algorithms with greater key lengths and increased security to thwart such attacks.
The U.S. National Institute of Standards and Technology (NIST) selected the new standard after a four-year international search. Beginning in January 1997, NIST initiated a process to find candidates for a new advanced encryption standard (AES) to replace the U.S. government’s aging data encryption standard (DES) for secure messaging. A more robust version, known as Triple DES, will continue to be used for secret communications.
NIST sent out selection criteria to a number of private sector groups for comment. Based on the feedback, a uniform set of requirements evolved. Participants were then invited to submit their encryption schemes for testing and review. NIST announced an initial field of 15 candidates in August 1998 and, over a one-year trial period, reduced this group to five candidates. A winner was selected in October 2000. Called Rijndael (pronounced rhine dahl), the algorithm is named after its creators, Belgium cryptographers Dr. Vincent Rijmen, a researcher in the electrical engineering department of the Katholieke Universiteit of Leuven, and Dr. Joan Daemen of Proton World International, Brussels.
According to James Foti, a mathematician in NIST’s computer security division, the institute examined all of the competing algorithms’ operational specifications to make a decision. Categories such as security, performance and performance in a memory-restricted environment were investigated. NIST then summarized the results and compared the contestants. One deciding factor was which cipher performed best across multiple categories. It was a difficult decision to make because all of the algorithms were good, but Rijndael performed best overall. “It wasn’t lacking in any particular category, and it excelled in the others,” Foti explains.
The algorithm was selected because of its combination of security, performance, efficiency, ease of implementation and flexibility, officials say. NIST specifically chose Rijndael because of its consistent high performance in both hardware and software across a wide range of computing environments regardless of its use in feedback and nonfeedback modes. Other considerations included key setup time and the cipher’s very low memory requirements, which make it suitable for smart cards and other restricted-memory environments.
Rijndael also proved to be the easiest to defend against power and timing attacks without significantly affecting the algorithm’s performance. Designed with some flexibility in block and key sizes, the algorithm could accommodate alterations in the number of rounds. A round is a series of steps consisting of transformation and substitution that are repeated to encode a message. In each round, different parts of the cipher’s key are added to the encryption process. However, changing the number of rounds will require more study and is not currently under consideration, NIST officials say.
Unlike the aging 56-bit DES standard, the new cipher has three key sizes: 128, 192 and 256 bits. In the late 1990s, specialized DES cracker machines were built that could retrieve a key within a few hours by exhausting all of the algorithm’s key combinations. Rijndael defeats these brute-force attempts because the AES specifications are for a minimum key length of 128 bits. NIST officials claim that if a computer could recover the key to a 56-bit algorithm in one second, it would take that machine approximately 149 trillion years to crack a 128-bit AES key.
Rijndael can be applied across a variety of communications standards, such as asynchronous transfer mode, high-definition television, broadband integrated services digital networks, voice and satellite. The cipher is written in American National Standards Institute (ANSI) C and can also operate in Java. The only factor relevant to its use in these applications is the choice of microprocessor on which the cipher is implemented, the designers say. The algorithm uses a limited set of instructions and has sufficient parallelism for application in modern multiarithmetic-logic-unit processors. Rijndael can be installed in dedicated hardware for applications requiring data rates of more than one gigabit per second.
The cipher is compatible with a wide range of processors such as 8-bit processors commonly employed in smart cards and the 32-bit processors in desktop computers. While the algorithm is designed for use in dedicated hardware, compromises exist between a microprocessor’s available physical area and speed. Because the software in general purpose processors is already very fast, the need for hardware implementation will probably be limited to extremely high-speed chips with no area restrictions and compact co-processors used in smart cards to accelerate cipher execution.
Rijndael has been tested in two microprocessors commonly installed in smart cards: the Intel 8051 and Motorola 68HC08. According to Rijmen and Daemen, in these implementations, the round keys are computed between the cipher’s rounds, allowing the key schedule to be repeated every cipher execution. This means that no extra time is required for key setup, key change and algorithm setup, the designers say. However, they caution that this has been implemented only in the cipher’s encryption operation, and efforts by other laboratories indicate that the cipher operates 30 percent slower when decrypting a message.
One of Rijndael’s advantages is that it can be set to run at speeds that are unusually fast for a block cipher on a Pentium-class processor. However, the designers note that there is a trade-off between table size and performance. When used in smart cards, the algorithm requires only a small amount of code, memory and cycles to function.
The algorithm’s round transformation is parallel by design, allowing it to be employed in future processors and dedicated hardware. Because the cipher does not use arithmetic operations, it has no bias toward either desktop or high-end computers. Rijndael is fully self-supporting—it does not borrow cryptographic components from other ciphers. The algorithm also does not base any part of its security on obscure and little known interactions between mathematical operations. Rijmen and Daemen claim the tight cipher design does not leave room for a back door into the program.
Variable block lengths within the algorithm also allow for flexibility across a variety of platforms. Block lengths of 192 and 256 bits allow the construction of a collision-resistant iterated hash function using Rijndael as the compression function. A hash function preserves message integrity by compressing the data to a fixed length. The designers note that the 128-bit block length is no longer considered sufficient for this purpose. The design allows the specification of variants with block and key lengths ranging from 128 to 256 bits in steps of 32 bits. Though the number of rounds is fixed in the algorithm’s specification, it can be modified as a parameter in case of security problems.
Rijndael is currently limited in its decryption ability under some conditions. The cipher is less suited for decryption in smart cards because it takes more code and cycles. Yet even under these circumstances, decryption is still very fast compared with other algorithms, the designers maintain. Other issues include the need for different code and tables for decryption in software. When the algorithm is installed in hardware, the decryption function can only partially employ the circuitry used for encryption.
Rijndael is still in the comment period and will not officially become the AES standard until late spring, Foti says. The delay is due to a temporary hold on Federal Register announcements put in place by the Bush administration until it can put its personnel in place, he explains.
NIST is also making the reference code available to vendors to use when building Rijndael into their products. The code can be accessed from the NIST World Wide Web site. Products featuring the cipher must meet Federal Information Processing Standard 140-1 cryptography requirements before they can be sold to the government. “If you want to sell to the government, you will want to meet certain requirements,” Foti says. Federal agencies that need encryption products can visit the NIST Web site for a list of vendors and their cryptographic applications to determine which products meet their needs.
When Rijndael becomes the AES standard, NIST will have a laboratory in place to allow vendors to test their software. Only if it meets NIST specifications will software become available to federal agencies. “If they’re looking at the reference code, that doesn’t mean that it’s validated by us,” Foti says. The laboratory will be the vehicle for NIST to act as an independent third party between the vendors and the government to determine the quality of the software.
Vendors Adopt New Cipher
Even before Rijndael officially becomes the U.S. government’s advanced encryption standard, some companies are already begging to incorporate it into their products. Zaxus Limited is using the cipher in its Datacryptor 2000 line of encryption devices. The Sunrise, Florida-based firm manufactures hardware serving as point-to-point links in leased-line links, asynchronous transfer mode, X.25, Internet protocol and frame relay networks.
Rijndael is also being implemented in products like Entrust Technologies Incorporated’s Entrust Cryptographic Kernel, a software-based cryptographic module. According to company spokesperson Elizabeth MacLellan, inserting the cipher into the program’s next release also allows the Kanata, Ontario-based firm to maintain its federal information processing standard 140-1 level-2 certification with the U.S. government.