Security Applications Abhyudaya Chodisetti Paul Wang Lee Garrett Smith 1. Introduction Cryptography applications generally involve a large amount of processing. Thus, there is the possibility that these applications would present a good target for CMP’s. In this survey, we examined the characteristics of major cryptography applications to determine whether this is the case. The major components of cryptography include encryption, MAC’s, digital signatures, and authentication. Encryption hides the content of a message from eavesdroppers, providing privacy. MAC’s provide a way to detect tampering, thereby providing message integrity. Digital signatures enable a party to verify the origin of a message. Authentication provides a way to identify another party. Most extended applications such as electronic cash, electronic voting, secure auctions, etc. use these or some extension of these major components. These components, in turn, are built using a few basic functions, such as block ciphers, secure hash functions, and public key encryption. For example, digital signatures use secure hash functions and public key encryption, and MAC’s are created using secure hash functions. Block cipher or public key encryption is used directly for encryption. Therefore, examining these three key functions will enable us to gain an understanding of the properties and requirements of most cryptography applications. (There is another class of encryption methods, stream ciphers, but it was omitted from our study as they seem to be less interesting. Stream ciphers generally involve generation of pseudorandom numbers from a seed and XORing to the message to be encrypted.) 2. Block Ciphers Block ciphers work on a block of plain text (typically 64-256 bits) as a whole and produce a cipher text block of equal length. We examined two block ciphers in particular, DES and AES. DES DES(Data Encryption Standard) is a block cipher that has been in use since the 1970’s. DES operates on blocks of 64 bits each and uses a key size of 56 bits. It is composed of 16 rounds, each one performing the same operations, but using different inputs. The inputs to a given round are the two 32 bit outputs from the previous round (L[i] and R[i]) and 48 bits of data derived from the key (K[i]). Half of the input data at each round is first permuted/expanded and XORed with a round key, and then divided into 8 6-bit chunks. A ‘substitution box’ (S-box) is used to convert this 6 bit value to a 4 bit value, which is then concatenated with all the other outputs of the S-boxes. This value is then XORed with the other half of the input data, producing the inputs to the next round. S-boxes can beimplemented efficiently in hardware using four 6-input single-output gates. In software, they are implemented as lookup tables. Global Structure of DES Structure of one DES round Because of the design of the round structure, the computation of a DES encryption / decryption is highly serialized. The S-box lookups are independent, but since they are implemented as small lookup tables, they are all memory accesses. Another property of DES is its bit permutations, which are hard to implement in software. DES’s 56 bit key is too short to be safe from brute force attacks given today’s computers, so a variant, Triple DES is used, encrypting each block 3 times with different keys. This further increases the amount of computation per block.AES AES is the new federal standard that replaces DES. Its original name is Rijndael. It can operate on blocks of 128, 192 and 256 bits and can use keys of 128, 192 and 256 bits. It also uses the round structure, but the content of each round is different from DES. In each round 4 operations are performed: 1. Byte Substitution: A byte substitution is performed, based on the results of a table lookup. The table is generated from a Galois Field, and provides the non-linearity in the system. 2. Shift Rows: Each row is shifted by different byte amounts. 3. Mix Column: Mix the bytes within a column in a linear way, using table lookups and arithmetic. 4. Key Addition: XOR in new key material. AES is easier to implement in software, due to its avoidance of bit permutations. An important issue in using block ciphers is the mode of their operation when encrypting messages of general length. Two representative modes are ECB(electronic code book) mode and CBC(cipher block chaining) mode. The important difference between these two modes is the way they encrypt successive blocks. In ECB, every block of the message is encrypted independently of the previous block. In CBC mode, each block’s encryption depends on the encryption of the previous block. ECB mode exposes information about the original message, and is thus insecure. Hence, CBC mode is more commonly used, but this introduces serial dependency limiting the available parallelism that can be exploited. Properties of DES/AES Both DES and AES rely heavily on table lookups, with AES relying even more heavily. Because of this there are two different data access patterns to look at: The table access patterns and the data access patterns. The tables are relatively small (2K for DES 1K for AES). These are accessed randomly, based on the input data, but are small enough to fit fully in L1 cache, and in hardware implementations can be implemented directly with gates. The key (56bits for DES, 128-256 bits for AES) is small enough to fit in registers. The input data can be of arbitrary size, depending on the application that is using cryptography. But it is operated on serially and in very small chunks at a time (64 bits for DES, 128-265 bits for AES), which fit in the register file. These algorithms operate in a streaming manner over the input data, with very predictable memory access patterns, thus prefetching would be very effective. Encryption in general is O(N) with N being the amount of data to be encrypted. Software Implementations We investigated the NIST’s published reference implementation of AES and the implementation of DES that came with OpenSSL 0.9.7b. To determine the ratio of ALU operation to memory references we profiled test programs to locate the inner loop for both AES and DES, and then compiled the relevant function to assembly and analyzed the output by hand. The target architecture for all tests was SPARC v8.For DES, the encryption of a block of data takes 192 memory