Symmetric cryptographic algorithms

Symmetric cryptographic algorithms are based on the principle of performing encryption and decryption using the same secret key – hence the designation ‘symmetric’.

The DES algorithm

The best-known and most widely used type of symmetric cryptographic algorithm is the Data Encryption Algorithm (DEA). It was developed by IBM in collaboration with the NBS (US National Bureau of Standards) and published in 1977 as the US FIPS 46 standard. The standard that describes theDEAis generally referred to as the DES (Data Encryption Standard). Consequently, the Data Encryption Algorithm is often (but not entirely correctly) called the DES algorithm. Since this algorithm is of course fashioned according to Kerckhoff’s principle, it could be published without losing any of its security. However, even today not all of the development criteria have been made known, which repeatedly leads to assumptions regarding possible methods of attack and the possible presence of ‘trap doors’. However, up to now all attempts to break the algorithm on this basis have failed. Two important principles for a good encryption algorithm were incorporated into the design of the DES algorithm. These are the principles of confusion and diffusion, as first proposed by C. Shannon. The confusion principle states that the statistics of the ciphertext should affect the statistics of the plaintext in a manner that is so complex that an attacker can derive no advantage from them. The diffusion principle states that each bit of the plaintext and each bit of the key should affect as many bits of the ciphertext as possible.

DES, which is a symmetric block encryption algorithm, does not expand the ciphertext. This means that the plaintext and ciphertext blocks have the same size. The block size is 64 bits (8 bytes), which is also the length of the key, although only 56 of these bits are used as the actual key. The key contains eight parity bits, which reduces the available key space. The 64 bits of the key are numbered consecutively from left (msb) to right (lsb). Bits 8, 16, 24, . . . , 64 are the parity bits. The parity is always odd. Due to the parity bits, the key space is 256, which means that there are approximately 7.2×1016 possible keys. At first glance, a key space with 72,057,594,037,927,936 possible keys may appear very large, but the limited size of its key space is actually the main weakness of the DES algorithm.3 Given the steadily increasing processing capacity of modern computers, a key space of this size is already considered to be too small for a secure cryptographic algorithm. If a plaintext–ciphertext pair is available, it is easy to test all possible keys if the key space is too small. If a plaintext–ciphertext pair is obtained by tapping the communications between a terminal and a smart card, a brute-force attack can be mounted by encrypting the plaintext using all possible keys. The correct key can be determined by comparing all of the resulting ciphertexts with the previously obtained ciphertext. This procedure can very easily be executed using several parallel processors. Each of the processors tests only the relatively small portion of the key space assigned to it. A sample calculation can illustrate the amount of time needed for such a brute-force attack. The fastest currently available DES components require 64 ns for a complete block encryption.4 If 10,000 such computation modules are assembled in parallel, each one can independently test a small part of the key space. Assuming that on average only half of the key space must be searched to find the correct key, the processing time can be calculated as follows:

((256 × 64 ns) ÷ 10,000) × 0.5 ≈ 64 h

In 1993, Michael Wiener published plans for a million-dollar computer that could test all the DES keys of a given plaintext–ciphertext pair within seven hours [Wiener 93]. In 1998, a similar concept, called ‘DES Cracker’,was implemented by the Electronic Frontier Foundation (EFF) at a cost of approximately US $ 250,000. The DES Cracker can test approximately 88.8 billion keys per second, and in a public test it took 56 hours to determine an unknown key [EFF 98]. The biggest problem with the use of DES is that its key space has become too small over time. Consequently, the triple-DES algorithm is used almost exclusively for new applications.

A full description of the exact implementation of the DES algorithm is far beyond the scope of this book, and it is not necessary for understanding the subject. If you are interested in having more detailed information, consult FIPS Publication 46, Carl Meyer [Meyer 82] or Bruce Schneier [Schneier 96]. However, one significant detail must be mentioned. The DES was designed as an encryption algorithm that can easily be implemented in hardware. There are presently many smart card microcontrollers with a DES hardware module. However, if it is necessary to implement DES in a smart card in software, it will occupy around 1 kB of assembler code, even in a highly optimized version. The size of a DPA-resistant version is approximately 2 kB. Its computational speed is consequently rather low. Typical computation times for encryption and decryption using a smart card, with comparison values for using a PC and a hardware integrated circuit, are shown in Table 4.7. These numbers can vary depending on the actual implementation, and they take into account only the pure processing time for DES encryption or decryption of an 8-byte block, assuming that all registers are already loaded. As a general rule, it can be assumed that DES implemented in hardware is approximately 150 times faster than DES in software. Keys for theDESalgorithm can be generated using a random number generator that produces an 8-byte random number, which is then checked against the four weak and 12 semi-weak keys. If the computed value does not match any of these easily broken keys, the parity bits are computed and the result is a DES key.

IDEA algorithm

There are many other symmetric cryptographic algorithms besides DES. Here we consider only the International Data Encryption Algorithm (IDEA) as a representative example. It was developed by Xuejia Lai and James L. Massey, and it was published in 1990 as the ‘proposed encryption standard’ (PES). It was improved in 1991, and for a short while the improved version was known as the ‘improved proposed encryption standard’ (IPES), but nowadays it is commonly known as IDEA. The development criteria and internal construction of this algorithm have been fully published, so Kerckhoff’s principle is satisfied. However, IDEA is subject to patent restrictions, which was formerly also the case with the RSA algorithm. IDEA, like DES, is a block-oriented cryptographic algorithm, and it also uses 8-byte plaintext and ciphertext blocks. In contrast to the DES algorithm, the key length is 16 bytes (2 × 8 bytes). This provides a significantly larger key space, with a size of 2128 ≈ 3.4 × 1038. In regular decimal notation, the number of possible keys for the IDEA is exactly 340,282,366,920,938,463,463,374,607,431,768,211,456. Due to its structure, IDEA is compatible with DES except for its extended key length. It is also compatible with triple-DES systems, which use keys that are 2 × 56 bits long, which means that changing the algorithm used does not affect the lengths of the keys or the input and output data blocks. Of course, compatibility in this regard does not mean that DES-encrypted data can be decrypted using the IDEA. In general, IDEA is considered to be a very good cryptographic algorithm. It has also been widely distributed in the form of the public-domain program PGP (Pretty Good Privacy) from Philip Zimmermann, which is used for secure data transmission. There are only a few smart card implementations of IDEA. The amount of memory space needed for the program is around 1000 bytes. Typical computation times for encryption and decryption are somewhat less than for DES. However, in the development of IDEA, it was assumed that the computations would be executed by a 16-bit processor. Since most smart cards still have 8-bit processors, the speed advantage in comparison with DES is not as great as might be expected. Table 4.8 lists typical values for IDEA operations on an 8-byte block, assuming that previously computed keys are available.