Cryptography is crucial for effective security in trusted computing: introduction to symmetric algorithms
Systems designers must employ the correct cryptography algorithms in their proper modes to secure secret or sensitive data in military trusted computing.
By David Sheets
ASHBURN, Va. – There are three general categories of cryptographic algorithms that are common in trusted computing: secure hashing, symmetric cryptography, and asymmetric cryptography. This column focuses on symmetric cryptographic algorithms, which are designed to take a block of data and encrypt it so that it is mathematically infeasible to extract the original information from the cipher-text without the key, which is used to both encrypt and decrypt the data.
In this approach, the same key encrypts and decrypts data to ensure the secrecy of that key, which is critical for ensuring the secrecy of the protected data. Most symmetric algorithms work on fixed sizes of data called blocks. The plaintext input is divided into blocks and each block is encrypted on its own to create the entire cipher-text stream.
There are several types of attacks against symmetric algorithms. In some, the goal is to determine the key to enable the attacker either to decrypt the protected data or encrypt different data. This helps the attacker insert his own data without otherwise modifying the system. Other types of attacks on symmetric algorithms are just designed to obtain the unencrypted plaintext, which might be protected data or protected algorithms.
The most straightforward type of attack is a brute-force attack, which tries to defeat cryptography by decrypting data with all possible keys until it finds the right key. The difficulty in this type of attack results from the vast number of possible keys, which increases exponentially as the number of bits in the key are increased.
The birthday attack is a corollary to the brute-force attack. It attempts to try different likely inputs to find a collision between the result of encrypting the likely plaintext inputs and the known cipher-text. A birthday attack is most effective against symmetric algorithms with small block sizes and less variability in the input so that the search space is small. A birthday attack also requires a system that enables the attacker to enter his own input stream to be processed by the symmetric algorithm.
Most modern symmetric algorithms can resist known plaintext attacks, which attempt to determine the secret key based on the input text and the produced cipher-text. Once determined, the key can decrypt other messages that were not previously known.
While all the previous attacks discussed work on the mathematical algorithm itself, side-channel attacks target information leaked due to the implementation details of the algorithm. Normally, some side channel of information is analyzed over several cryptographic blocks to determine the secret key.
Examples of the type of information that can be analyzed are timing information; cache hits and misses; and power usage. To obtain the needed level of information requires access to the system, either virtually or physically, depending on the type of side-channel information and the level of fidelity required.
As computing power has increased, several generations of symmetric algorithms have been developed and put into use. One of the first standardized symmetric cryptographic algorithms was Data Encryption Standard (DES), developed in the late 1970s. It set the stage for symmetric algorithms operating over blocks of data.
Later symmetric algorithms included Blowfish and Twofish. Today, the most popular symmetric algorithm is Advanced Encryption Standard (AES). These algorithms operate on blocks, so they must run in a particular mode to be effective. The mode dictates how the keys are (or are not) changed in between each block.
DES/3DES symmetric algorithms
DES, one of the first publicly available block symmetric cryptographic algorithms, was developed by IBM Corp. with input from the U.S. National Security Agency (NSA) in the 1970s. It had a fixed block size of 64-bits, and an effective key length of 56-bits. After the security of DES began to wane, a new standard, called triple-DES (3DES), was formalized in FIPS 64-3. 3DES effectively runs DES three times in succession, with independent keys. While Triple-DES can still be used securely, AES is recommended for new applications.
The Blowfish algorithm was developed by Bruce Schneier to provide an efficient secure symmetric encryption algorithm unencumbered by patents. It operates on 64-bit blocks and supports effective key lengths of 32 to 448 bits. Because Blowfish suffers from slow initialization during key rolling, it is less efficient because many applications use frequent key rolling to combat side-channel attacks.
Twofish, designed as a follow-on to Blowfish, was entered in the National Institute of Standards and Technology (NIST) challenge to determine the AES standard algorithm, but was not selected. Twofish operates on 128-bit blocks and supports key sizes of 128, 192, or 256 bits. While neither Blowfish nor Twofish have any verified cryptographic vulnerabilities, they have received less attention than AES, so are not generally as trusted as AES.
The AES algorithm, formalized in the FIPS 197 Advanced Encryption standard, is the world's most widely used symmetric cryptographic algorithm. It resulted from a competition managed by NIST starting in 2001. A slightly modified subset of the Rijndael algorithm, AES operates on block of 128-bits and supports key lengths of 128, 192, and 256 bits. AES is widely accepted as the standard to use for most symmetric cryptography, and since its adoption, has received the most attention of any algorithm in research activity. Despite repeated attempts to defeat it, AES still remains effective when used properly.
Block symmetric algorithm modes of operation
Because all of the symmetric algorithms discussed above operate on blocks of data, there is a need to determine the relationship of the cryptographic operations performed on each subsequent block of data. The different methods of cryptographic operation of each algorithm are referred to as modes.
Many of these modes were described originally in relation to DES in the FIPS 81 publication "DES Modes of Operation." Additional modes were later added in NIST special publication 800-38A and NIST special publication 800-38E.
Electronic Cookbook Mode (ECB) is the most simplistic mode of operation and performs no operations on the key in between blocks. This can have disastrous effects on the confidentiality of the resultant cipher-text. As an example, see the original image of Tux [Image 1], and the same image after being encrypted using ECB mode [Image 2].
Because of the lack of key modification, blocks that are the same in the plaintext also come out the same in the cipher-text. That allows large patterns to emerge. Because of these issues, ECB should almost never be used in operational environments where confidentiality is desired.
Cipher block chaining (CBC)
Cipher block chaining (CBC) takes each plaintext block and performs the logical exclusive OR operation (XORs) with the previous cipher-text block. For the initial plaintext block, since there is no previous cipher-text, an initial value called initialization vector (IV) seeds the algorithm.
Although the IV does not need to remain secret or require protection like the secret key, in CBC mode, it is important to ensure that IVs are not reused with the same key. Reusing the same IV with the same keys can leak information about the contents of the first block.
Cipher Feedback Mode (CFB) encrypts the IV for the first block, and then XORs the resultant value with the plaintext, instead of encrypting the plaintext. Each cipher-text block then re-encrypts to provide the next value to XOR with each subsequent plaintext block. As with CBC, IV should not be reused with the same key because it can leak information.
Counter mode (CTR) uses the algorithm to encrypt an IV concatenated with a non-repeating pattern -- normally a simple incrementing counter. Then it XORs the plaintext with the resultant value to generate the cipher-text.
Using a counter maintains an easy way to view an overall pattern, and ensures that decrypting an individual block does not depend on decrypting previous blocks. This can enable decrypting several blocks in parallel. In CTR mode, the IV must not be reused to ensure continued confidentiality.
Galois Counter Mode (GCM) with authentication works with AES to provide confidentiality and integrity verification. It uses the same CTR mode of operation for encryption and decryption, yet adds an authentication tag by taking the cipher-text through a polynomial function, and then encrypting the result. This approach verifies the block's integrity by reversing the process. If the decrypted tag doesn't match, then the block verification fails and should be discarded.
While authentication in AES-GCM can verify the integrity of blocks, this process has different security implications from asymmetric cryptographic algorithms that use public-private key pairs. Since public-private keys pairs can separate out the signing key from the verification key, ensuring the confidentiality of the key becomes much more important for maintaining integrity with symmetric cryptography.
Symmetric cryptography in trusted computing
Symmetric cryptography can provide confidentiality for data-at-rest and data-in-transit. Systems designers choose different algorithms based on their performance requirements, their desired level of security, and necessary certifications.
Systems designers should choose the correct mode of each algorithm to maintain confidentiality across the life of the product. Mode selection can have profound effects on system performance to take advantage of potential parallelization across several data blocks.
Some modes can decrypt, but not encrypt, in parallel. This may fit well with a secure boot model that prepares an image once, and then processes it many times. It's not a good match, however, for a message streaming model that must encrypt messages dynamically.
For symmetric algorithms, the key to security is protecting the key itself. Keys used during system startup have physical and process controls that can protect the secrecy of symmetric keys. For dynamic systems, key agreement protocols using asymmetric cryptographic algorithms can generate secret keys dynamically during operation.
David Sheets is senior principal security architect at Curtiss-Wright Defense Solutions in Ashburn, Va.. Contact him by email at firstname.lastname@example.org.