A new medium-sized health care facility just opened and you are

Architectural Support for Fast Symmetric-Key Cryptography

Jerome Burke John McDonald Todd Austin

Advanced Computer Architecture Laboratory University of Michigan

fjaburke,johngm,[email protected]

Abstract

The emergence of the Internet as a trusted medium for commerce and communication has made cryptography an essential component of modern information systems. Cryp- tography provides the mechanisms necessary to implement accountability, accuracy, and confidentiality in communi- cation. As demands for secure communication bandwidth grow, efficient cryptographic processing will become in- creasingly vital to good system performance.

In this paper, we explore techniques to improve the per- formance of symmetric key cipher algorithms. Eight pop- ular strong encryption algorithms are examined in detail. Analysis reveals the algorithms are computationally com- plex and contain little parallelism. Overall throughput on a high-end microprocessor is quite poor, a 600 Mhz proces- sor is incapable of saturating a T3 communication line with 3DES (triple DES) encrypted data.

We introduce new instructions that improve the efficiency of the analyzed algorithms. Our approach adds instruction set support for fast substitutions, general permutations, ro- tates, and modular arithmetic. Performance analysis of the optimized ciphers shows an overall speedup of 59% over a baseline machine with rotate instructions and 74% speedup over a baseline without rotates. Even higher speedups are demonstrated with optimized substitutions (SBOXes) and additional functional unit resources. Our analyses of the original and optimized algorithms suggest future directions for the design of high-performance programmable crypto- graphic processors.

1 Introduction

In an increasingly connected world, cryptography has become an essential component of modern information sys- tems. Cryptography provides the mechanisms necessary to provide accountability, accuracy and confidentiality in in-

herently public communication mediums such as the Inter- net. Today, cryptographic processing is primarily reserved for electronic commerce transactions and secure e-mail, however, the adoption of virtual private networks (VPNs) [12] and secure IP (IPSEC) [3] will subject more of all com- munication to cryptographic processing. As secure commu- nication bandwidth demands continue to grow, so too will the importance of efficient cryptographic processing.

Cryptography is the art of using mathematics to encrypt and decrypt data. There are many cryptography algorithms (or ciphers) in use today, some good, and some not so good. The quality of a cipher is judged by its ability to prevent an unrelated party from determining the original content of an encrypted message. Figure 1 illustrates the two forms of cryptography most commonly used in information systems today. The simplest ciphers are known as symmetric-key ci- phers. Communicating parties share a common private key which is used to transform the message from plaintext to ci- phertext. The ciphertext is communicated to the other party, and then the process is reversed using the same private key.

The primary obstacle in making private key symmetric ciphers useful is distribution of private keys. To securely share a private key, communicating parties would first have to be holding a shared private key! Public key cryptog- raphy solves this conundrum by implementing encryption with two keys, a well-known public key and a private key. Only the receiver knows the private key value. The re- ceiver’s public key, on the other hand, is widely published by trusted sources. As shown in Figure 1, to encrypt a mes- sage using a public key cipher, it is first converted to cipher- text using the public key. The resulting ciphertext can only be decrypted using the receiver’s private key. Secure com- munication now proceeds without any insecure exchanges of private information. The process may also be reversed to produce what is known as a digital signature. Digital signa- tures authenticate the sender, i.e., verify the identity of the sender. Since only the person holding the private key knows its value, only that person can create a digital signature that others can decrypt with the public key (assuming the private key has not been compromised).

It would seem that the additional benefits of public key encryption would obviate the need for private key encryp- tion, however, the high cost of employing public key en- cryption requires that it be used sparingly. Strong public key ciphers are computationally very expensive, running

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed

ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to

sion and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1

Copyright © A.C.M. 2000 1-58113-317-0/00/0011…$5.00

for profit or commercial advantage and that copies bear this notice and the full cita- tion on the first page. Copyrights for components of this work owned by others than

republish, to post on servers, or to redistribute to lists, requires prior specific permis-

(212) 869-0481, or [email protected] ASPLOS 2000 Cambridge, MA Nov. 12-15 , 2000

178

plaintext ciphertext plaintextf()

private key

private key

f()

plaintext ciphertext plaintextf()

private key

public key

g()

Figure 1. Private Key and Public Key Cryptography.

usually 1000 times slower than comparable private key ci- phers [23]. Public key encryption requires exponentiation and modular multiplication of large multi-precision num- bers of 1024 bits in length or more. As a result, most secure information systems only use public key encryption at the start of a session to authenticate communicating parties and to effect a secure exchange of private keys. The remain- der of the session employs efficient private key algorithms, using the private keys exchanged during authentication.

An example of a system that uses this session manage- ment strategy is the Secure Sockets Layer (SSL) protocol [29]. SSL extends TCP/IP to support secure encrypted connections with authentication of senders and receivers. The protocol is used by web servers and browsers to es- tablish secure HTTP connections. Figure 2 illustrates the relative costs of private and public key cryptography for a web server. The numbers shown were gathered by Intel for a heavily loaded web server running on an iA32 platform [22]. The results show the total fraction of time spent in the public key cipher code, private key cipher code, and other parts of the web server and operating system. Re- sults are shown for increasing session length, where a ses- sion includes an initial public key authentication and private key exchange, and a transfer of a single message of the size listed.

Clearly, for very short sessions fast public key cipher processing is crucial for high transaction throughput. For sessions lengths on the order of a single web page object (approximately 21k bytes [2]), private key cipher process- ing dominates web server run time. For a 32k session length, private key processing overheads rise to 48% of overall run time. Since a session will likely see a user visit many web pages and web pages with many objects, private key cipher performance will quickly dominate the perfor- mance of SSL sessions. To further reduce the cost of public key authentication, SSL allows the use of a session cache, where authenticated private keys are held and can later be reused when users reconnect to view other web pages.

In this paper, we focus our attention on improving the performance of private key symmetric ciphers. We first examine the execution of eight widely known strong symmetric-key ciphers. We analyze their performance on detailed microarchitectural models, where we are able to

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

1k 2k 4k 8k 16k 32k

SSL Session Length (bytes)

R el

at iv

e C

o n

tr ib

u ti

o n

t o

R u

n T

im e

Public Other Private

average size of a single web object (21k)

Figure 2. SSL Characterization by Session Length.

clearly show their performance and the bottlenecks that slow their progress. Armed with these insights, we pro- pose architectural extensions that streamline cipher kernel processing. The new instructions speed modular arithmetic, substitutions, general bit permutations, and rotates. We re- code the cipher using these new instructions and then ex- amine their performance on microarchitectural models with varying levels of support for fast cryptography. Our ap- proach is a general one, the instructions are shown to be useful across a broad array of cipher algorithms.

2 Private Key Symmetric Ciphers

Figure 3 shows the kernel of the Twofish cipher, devel- oped by Counterpane Systems [26]. It is a candidate for the Advanced Encryption Standard (AES) [1], the US gov- ernment’s effort to develop a new strong encryption stan- dard. Twofish is a particularly good example to look at be- cause it captures many of the operations that ciphers em- ploy. The code shown in Figure 3 is the encryption kernel, run on one 128-bit block of data to encrypt it into a 128- bit ciphertext block using a 128-bit key value. The Twofish decryption kernel is nearly identical except the order of the operations is reversed and inverted (e.g., rotate left becomes rotate right).

The cipher algorithm first reads the input data, XOR’s it with the 128-bit intermediate vector (IV) and key, and then enters the encryption loop. The encryption loop executes 16 iterations (or rounds as they are called in cryptography literature) to produce 128 bits of ciphertext. The ciphertext is then once again XOR’ed with the key and stored to the intermediate vector and the output buffer.

Within the kernel loop, the cipher algorithm employs a series of reversible operations to implement a process called diffusion. Diffusion works to randomly impress upon each of the output bits some information from each of the input bits. The direction of the diffusion process is set by the

179

x[0] = input[0] ˆ key[0] ˆ IV[0]; x[1] = input[1] ˆ key[1] ˆ IV[1]; x[2] = input[2] ˆ key[2] ˆ IV[2]; x[3] = input[3] ˆ key[3] ˆ IV[3];

for (ii=15, jj=0; ii >= 0; ii–, jjˆ=2) { t0 = (sbox1[x[jj][0]] ˆ sbox2[x[jj][1]]

ˆ sbox3[x[jj][2]] ˆ sbox4[x[jj][3]]); t1 = (sbox1[x[jjˆ1][3]] ˆ sbox2[x[jjˆ1][0]]

ˆ sbox3[x[jjˆ1][1]] ˆ sbox4[x[jjˆ1][2]]);

x[jjˆ3] = x[jjˆ3] <<< 1; x[jjˆ2] = x[jjˆ2]ˆ(t0+t1+key[ii<<1]); x[jjˆ3] = x[jjˆ3]ˆ(t0+(t1<<1)+key[(ii<<1)+1]); x[jjˆ2] = x[jjˆ2] >>> 1;

}

output[0] = IV[0] = x[2] ˆ key[0]; output[1] = IV[0] = x[3] ˆ key[1]; output[2] = IV[0] = x[0] ˆ key[2]; output[3] = IV[0] = x[1] ˆ key[3];

Figure 3. The Twofish Cipher Kernel. All variables are 32-bit integers. Rotates are indicated by <<< and >>>.

private key. The more seemingly random and complete the diffusion process is, the more difficult it is to recreate the plaintext without the key value. With large keys and good diffusion, the ciphertext is extremely resistant to attackers. Quantitatively, a strong encryption algorithm is one where any change in the input results in a random perturbation of each output bit with probability 50%. Moreover, any change to the key value should have an equally dramatic effect on the ciphertext produced.

The process of diffusion has two important implications to the underlying machine architecture. First, diffusing in- put bits is computationally expensive on modern micropro- cessors. Most algorithms run their kernel loop at least 16 times on each block of data encrypted, successively mixing the data more and more on each round. The second implica- tion is that cipher kernels have little parallelism. Parallelism in the cipher (especially coarse-grained parallelism) would imply that some aspect of the computation does not affect later ciphertext results, which would in turn imply that the cipher algorithm was not a strong one! While we did find a small level of ILP in cipher kernels, the process of making the kernels run fast primarily entails improving their execu- tion efficiency on the underlying microarchitecture.

The intermediate vector IV ensures that the diffusion process propagates to all remaining ciphertext in the com- munication stream. The ciphertext value of encrypted block i is first XOR’ed with plaintext block i + 1 before it is en- crypted. The end results is that the cipher kernel execution is a very long recurrence with virtually no parallelism.

To ensure that the ciphertext can be decrypted back to the plaintext, the cipher kernel must employ a series of key- parameterized reversible operations. The Twofish algorithm demonstrates a number of these:

Rotates Rotates are easily reversible (simply rotate the same distance in the opposite direction). Rotates also have

good diffusion properties, impressing each bit onto another bit of the output.

Modular Addition Modular arithmetic, if based on a power-of-two base, is cheap, fast, and has relatively good diffusion properties. Moreover, it is easily inverted using modular subtraction or modular addition with the two’s-complement of the addend. XOR operations, which are modular additions in base 2, are easily reversible by XOR’ing the same value onto the resulting ciphertext.

Substitutions Table-based substitutions can be used to quickly implement any key-parameterized function. An SBOX is a table of values indexed with plaintext (usually a byte) that produces the result of the key-parameterized function. SBOX’s are easily reversible by inverting the ta- ble, i.e., indices become values and values become indices.

In addition, other algorithms often employ two other mech- anisms, modular multiplication and XBOXs.

Modular Multiplication Modular multiplication has been shown to have particularly good diffusion properties [18], and the operation can be easily reversed with modular multiplication of the modular inverse of the multiplicand. If the multiplicand is part of the key, all divides (which are typically much more expensive) can be confined to the ci- pher setup code. If the modulus of the operation is a power- of-two (as in RC6), it can be efficiently implemented using existing multiply instructions. A few algorithms (most no- tably IDEA) use a modulus of a 2N +1 prime number. This further improves diffusion properties of the operation at the expense of more computation. Techniques have been devel- oped to efficiently implement 2N +1 prime modulus opera- tions using only two additional (and parallel) adds plus one multiply [18].

General Permutations General permutations map N bits onto N bits with an arbitrary exchange of individual bit values. While trivial to implement in hardware with a wire network (called an XBOX), these permutations are quite expensive to implement in software. Consequently, newer ciphers strictly avoid permutations. We still consider them, however, as they are used in DES [11], the US en- cryption standard put into practice in the early 1970’s and still in wide use today.

3 Experimental Framework

3.1 Cipher Benchmarks We analyzed the eight private key symmetric ciphers

listed in Table 1. The table lists for each algorithm the key size used for the experiments, the block size encrypted by each application of the cipher kernel, the number of rounds (iterations) executed within the cipher kernel, the author of the algorithm, and popular applications that use the cipher. Each of the algorithms use at least 128 bits of key data, and each is generally considered a strong algo- rithm, having undergone review and aggressive cryptanal- ysis. Four of the ciphers, i.e., 3DES [11], Blowfish [8],

180

Cipher Key Blk Rnds/ Author Example Size Size Blk Application

3DES 186 64 48 CryptSoft SSL, SSH Blowfish 128 64 16 CryptSoft Norton Utilities IDEA 128 64 8 Ascom PGP, SSH Mars 128 128 16 IBM AES Candidate RC4 128 8 1 CryptSoft SSL RC6 128 128 18 RSA Security AES Candidate Rijndael 128 128 10 Rijmen AES Candidate Twofish 128 128 16 Counterpane AES Candidate

Table 1. Private Key Symmetric Ciphers Analyzed.

IDEA [18], and RC4 [25], are algorithms used in popular software packages. 3DES runs the US DES standard en- cryption algorithm [11] serially three times with three 56-bit keys. This is the mode of operation specified in the Secure Sockets Layer (SSL) protocol specification [29]. The re- maining algorithms, i.e., Mars [6], RC6 [24], Rijndael [10], and Twofish [26], are second round candidates for the Ad- vanced Encryption Standard (AES) [1]. The National Insti- tute of Standards and Technologies (NIST) is coordinating the multi-year AES competition that will ultimately lead to the selection of a new US encryption standard (to replace DES). However, many of the AES algorithms will likely emerge as high-quality encryption algorithms that will see use in popular applications and protocols.

Our baseline implementation of each algorithm is quite efficient. We obtained optimized implementations of each of the AES finalists from the inventors of the algorithms. 3DES, Blowfish, and RC4 were all developed by Eric Young of CryptSoft [9]. CryptSoft’s code is quite efficient, as a result, it has found its way into many popular soft- ware systems including SSH, OpenSSL, FreeBSD, and the Mozilla web browser. The optimized IDEA implementation was provided by Ascom, inventors of the algorithm.

Operation of the algorithms can be tailored significantly, e.g., number of rounds, block size, key size. We config- ured each algorithm as suggested by the inventors to main- tain good strength and performance. 3DES was configured as per the SSL specification [29]. All ciphers were run in chaining-block-cipher (CBC) mode. In this mode, the value of cipher text block i is XOR’ed with plaintext block i+1 before it is encrypted. Nearly all applications use CBC mode as it produces ciphertext that is more resistant to at- tacks.

All baseline codes were compiled with the Compaq Al- pha CC compiler (version 5.9) with full optimization and EV6 architecture optimizations (e.g., byte and word loads). All hand coded versions of the algorithms were based on assembly outputs from the Compaq CC compiler with the same optimizations. All analyzed codes (baseline and opti- mized) were validated by running the optimized encryption kernel with the original decryption kernel (and vice versa).

3.2 Performance Analysis Tools

Performance analysis was performed with the Sim- pleScalar Tool Set version 3.0 for the Alpha architecture [5].

The SimpleScalar tool set includes detailed microarchitec- ture simulators that can be tailored to reveal the bottlenecks within a program. We used the SimpleView visualization framework to optimize the performance of the cipher ker- nels. The SimpleView viewer displays graphically the stalls experienced by instruction as they pass though the modeled pipeline, making it fairly straightforward to identify the bot- tlenecks that slowed cipher kernels.

We analyzed program performance on the detailed tim- ing simulator (sim-outorder). The timing simulator ex- ecutes user-level instructions, performing a detailed tim- ing simulation of an aggressive 4-way dynamically sched- uled microprocessor with two levels of instruction and data cache memory. Simulation is execution-driven, including execution down any speculative path until the detection of a fault, TLB miss, or branch misprediction. Our baseline simulation configuration models a future generation out- of-order processor microarchitecture. The processor has a large window of execution; it can fetch and issue up to 4 in- structions per cycle. It has a 256 entry re-order buffer with a 64 entry load/store buffer. Loads can only execute when all prior store addresses are known. There is an 8 cycle mini- mum branch misprediction penalty. The baseline processor has 4 integer ALU units, 2-load/store units, 2-FP adders, 1-integer MULT/DIV, and 1-FP MULT/DIV. The latencies are: ALU 1 cycle, MULT 7 cycles, Integer DIV 12 cycles, FP Adder 2 cycles, FP Mult 4 cycles, and FP DIV 12 cy- cles. All functional units, except the divide units, are fully pipelined allowing a new instruction to initiate execution each cycle.

The processor we simulated has 32k 2-way set- associative instruction and data caches. Both caches have block sizes of 32 bytes. The data cache is write-back, write- allocate, and is non-blocking with 2 ports. The data cache is pipelined to allow up to 2 new requests each cycle. There is a unified second-level 512k 4-way set-associative cache with 32 byte blocks, with a 12 cycle hit latency. If there is a second-level cache miss it takes a total of 120 cycles to make the round trip access to main memory. We model the bus latency to main memory with a 10 cycle bus occupancy per request. Address translation is implemented a 32 en- try 8-way associative instruction TLB and a 32 entry 8-way associative data TLB, each with a 30 cycle miss penalty.

4 Cipher Kernel Analysis 4.1 Cipher Throughput

Figure 4 shows the encryption performance of each al- gorithm.1 The performance of each algorithm is expressed as a rate, bytes encrypted per 1000 cycles. We selected this metric because it has a useful real interpretation: on a 1 GHz processor, the same value is the rate in megabytes/sec that the microarchitecture would be able to encrypt data. For each algorithm, we show the performance in instruc- tions per byte encrypted (the 1 CPI machine), performance

1Because of the symmetry between the encryption and decryption algo- rithms, performance was comparable for these codes for all experiments. For the sake of brevity we only present encryption performance numbers.

181

296.48 192.69

0

10

20

30

40

50

60

70

80

90

100

Blow fis

h

3D ES

ID EA

M ar

s RC4

RC6

Rijn da

el

Twof ish

E n

cr yp

ti o

n R

at e

(b yt

es /1

00 0

cy cl

es )

CPI=1 (Insts) Alpha 21264 4W DF

Figure 4. Cipher Encryption Performance.

on a real 600Mhz Alpha 21264 workstation, performance on the modeled baseline microarchitecture (4W), and the upper bound dataflow performance of the algorithm (DF). Dataflow performance was measured on the performance simulator using perfect branch prediction, infinite window size, unlimited fetch bandwidth, perfect memory address disambiguation (e.g., loads never wait for unrelated stores even if their addresses have not yet been computed), and un- limited functional unit resources. The dataflow experiments represent the maximum performance that could be attained on any machine short of speeding up individual operation or employing value speculation [19].

We felt it was important to validate the performance of the baseline SimpleScalar model so we ran the identi- cal code on a 600 Mhz Alpha 21264 workstation (running Tru64 Unix) with a 1GB main memory. We loosely based our simulator baseline on the Alpha 21264 microprocessor, setting the resource configuration and their latencies to val- ues published by Compaq [17]. The correlation in absolute performance was quite close, all except Mars and Twofish were within 10% of the actual machine tests. Mars was 11% faster, Twofish was 15% faster. It’s difficult to assess why these discrepancies exists as many of the details of the Al- pha 21264 microarchitecture have not been disclosed. We feel they are likely due to the 21264’s clustered microar- chitecture, which was not modeled by SimpleScalar. The clustered microarchitecture has slightly higher forwarding latency for some instructions; this would account for the slightly better performance of the algorithms when running on the simulator. However, performance trends were indeed captured, thus we are fairly confident that our performance models are representative of real hardware.

As shown in Figure 4, the baseline 4-wide superscalar processor model performance (4W) varied dramatically. The worst performance was given by 3DES. 3DES is com- putationally very complex, and it contains operations (e.g., general permutation) that do not map well to a general-

purpose microprocessor. It’s interesting to note that a 1 GHz processor running the 3DES kernel (a common en- cryption mode for secure web transports) would produce a maximum throughput of 7.32 MBytes/s, not even enough throughput to saturate a trailing edge 100 Mbs Ethernet link, and barely enough to saturate a low-cost T3 communication line. IDEA also turned in a poor performance, the primary bottleneck in this cipher is numerous 7-cycle multiplies.

The AES standard candidates have much better perfor- mance with Rijndael leading the pack at 48.51 bytes/1000 cycles. The best performance overall was delivered by RC4 at 88.16 bytes/1000 cycles, more than 10 times the perfor- mance of 3DES. RC4 benefits from significantly more par- allelism than the other algorithms. The algorithm is essen- tially a key-based random number generator that XOR’s a random sequence onto the input stream. The iterations of the random number generator are (mostly) independent, al- lowing its execution to fully saturate a wide machine, re- sulting in very high-bandwidth encryption.

The last experiment (DF) shows the scalability of cipher kernel performance. In these experiments, the original code is executed on a dataflow machine. This machine has infi- nite fetch, decode, execute, and retirement bandwidth. In addition, it is never slowed by branch misprediction, cache misses or ambiguous store address dependencies. This con- figuration gives the absolute top performance that the code could achieve (short of reducing instruction latencies or ap- plying value speculation to break data dependencies). We found these results quite surprising, Blowfish, IDEA, and RC6 are running within 10% of dataflow machine perfor- mance. There is slightly more headroom for 3DES, Mars and Twofish, with potential speedups of 12%, 13%, and 32%, respectively. RC4 and Rijndael are the outliers, these codes have ample parallelism and could be sped up signifi- cantly.

4.2 Bottleneck Analysis Figure 5 analyzes the bottlenecks in the cipher algo-

rithms. Results are only shown for the algorithms that were not running at dataflow performance in Figure 4. For each cipher, the impact of various stall conditions is shown. Performance for each bar is shown relative to the perfor- mance of the dataflow machine running the cipher kernel. In each experiment, a single bottleneck (e.g., branch mis- predictions) is re-inserted into the processor model, and the resulting performance impact indicates the extent to which that bottleneck is fully exposed in execution (independent of all other bottlenecks). Note that if a bottleneck affects the dataflow machine, it may not help the performance of the baseline machine if it is removed. All of the exposed bottlenecks may have to be removed before performance improvements are seen in the baseline machine. The most important aspect of these analyses is that bottlenecks that do not affect the dataflow machine will not (and cannot) affect the performance of the baseline machine.

Six bottlenecks are analyzed. The Alias bar shows the impact of stalling loads in the pipeline until all earlier store addresses have been resolved (i.e., no address aliases).

182

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

3DES Mars RC4 Rijndael Twofish

P er

fo rm

an ce

N o

rm al

iz ed

t o

D at

af lo

w S

p ee

d

Alias Branch Issue Mem Res Window All

Figure 5. Analysis of Bottlenecks in Cipher Kernels.

Branch shows the effects of mispredictions, Issue shows the impact of reducing issue width. Mem shows the impact of introducing a realistic memory system, and Res gives the impact of limited functional unit resources. Window shows the impact of a limited-size instruction window, and All shows performance of the machine with all bottlenecks en- abled.

It’s interesting to note that branch mispredictions and data memory performance do not impair the performance of any ciphe

Collepals.com Plagiarism Free Papers

Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.

Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS

Why Hire Collepals.com writers to do your paper?

Quality- We are experienced and have access to ample research materials.

We write plagiarism Free Content

Confidential- We never share or sell your personal information to third parties.

Support-Chat with us today! We are always waiting to answer all your questions.