Shengqi Yang

Wayne Wolf

N Vijaykrishnan

D N Serpanos
email: serpanos@ee.upatras.gr

Yuan Xie

Power Attack Resistant Cryptosystem Design: A Dynamic Voltage and Frequency Switching Approach

A novel power attack resistant cryptosystem is presented in this paper. Security in digital computing and communication is becoming increasingly important. Design techniques that can protect cryptosystems from leaking information have been studied by several groups. Power attacks, which infer program behavior from observing power supply current into a processor core, are important forms of attacks. Various methods have been proposed to countermeasure the popular and efficient power attacks. However, these methods do not adequately protect against power attacks and may introduce new vulnerabilities. In this work, we addressed a novel approach against the power attacks, i.e., Dynamic Voltage and Frequency Switching (DVFS). Three designs, naive, improved and advanced implementations, have been studied to test the efficiency of DVFS against power attacks. A final advanced realization of our novel cryptosystem was given out, which achieved enough high power trace entropy and time trace entropy to block all kinds of power attacks, with 27% energy reduction and 16% time overhead for DES encryption and decryption algorithms.

I. INTRODUCTION

This paper describes a novel DVFS approach to improve the security of cryptographic algorithms. Our approach uses hardware techniques to obscure the cryptoprocessor's activities, making it more difficult to attack. Differential power analysis (DPA), which identifies cryptographic keys by monitoring processor power supply current, is a very real thread that has been used to break the security of smart cards [START_REF] Kocher | Differential Power Analysis[END_REF]. Our new method makes it substantially harder for an attacker to use DPA against a secure system.

Security is emerging as a discipline of utmost importance. This is especially true for embedded systems due to several unique security challenges [START_REF] Kocher | Security as A New Dimension in Embedded System Design[END_REF]. Cryptography is the best known answer to these challenges, as it provides a way to securely encode digital information [START_REF] Schneier | Applied Cryptography, Protocols, Algorithms, and Source Code in C[END_REF]. A cryptographic scheme is an encryption function C = f (K, P ) that maps an unprotected block of bytes P (plaintext) into a secure block of bytes C (cyphertext), and gives an easy way (a decryption function P = f -1 (K, C)) to recover the plaintext from the cyphertext if some additional information K (key) is available. Cryptographic algorithms can be implemented as hardware ASIC (Application Specific Integrated Circuits), software routines running on embedded cryptography processor (cryptoprocessor), or hybrid hardware-software modules. In this paper, we use a cryptoprocessor as a part of our novel cryptosystem, and try to realize a cost effective, flexible and power attack resistant platform for cryptographic algorithms software implementation.

Numerous attacks have been devised to break cryptoprocessor and can be classified into three categories, i.e., software attacks [START_REF] Ravi | Embedding Security in Wireless Embedded Systems[END_REF], microprobing/physical attacks [START_REF] Ömmerling | Design Princeples for Tamperresistant Smartcard Processors[END_REF], and side-channel attacks [START_REF] Samyde | Side-channel Cryptanalysis[END_REF]. Software attack uses the normal communication interface of the processor and exploits security vulnerability found in the protocols, cryptographic algorithms, or their implementation. Microprobing is an invasive technique that involves physical manipulation of the cryptoprocessor by depackaging, layout reconstruction, manual microprobing and memory/bus readout. Side-channel attacks include timing analysis [START_REF] Kocher | Timing Attacks on Implementations of Diffe-Hellman, RSA, DSS and Other Systems[END_REF], power analysis [START_REF] Kocher | Differential Power Analysis[END_REF], electromagnetic analysis [START_REF] Quisquater | ElectroMagnetic Analysis (EMA): Measures and Counter-measures for Smart Cards[END_REF] and fault induction [START_REF] Boneh | On the Importance of Eliminating Errors in Cryptographic Computations[END_REF]. Here, we are most interested in protection of cryptoprocessor against power attacks, which are considered as a fundamental class of attacks that are practically quite difficult to defend against.

Various countermeasures against power attacks have been proposed to remove the symptoms that make an cryptoprocessor vulnerable to monitoring and analysis of side-channel information. The proposed defenses, for example, reduction of signal sizes [START_REF] Kocher | Differential Power Analysis[END_REF], introduction of noise to signals [START_REF] Benini | Energy-Aware Design Techniques for Differenctial Power Analysis Protection[END_REF], self-timed circuit [START_REF] Moore | Improving Smart Card Security Using Self-timed Circuits[END_REF], [START_REF] Tiri | Securing encryption algorithms against DPA at the logic level: next generation smart card technology[END_REF], masking techniques [START_REF] Saputra | Maksing the Engergy Behavior of DES Encryption[END_REF], [START_REF] Benini | Energy-Efficient Data Scrambling on Memory-Processor Interface[END_REF], and duplication techniques [START_REF] Goubin | DES and Differential Power Analysisthe Duplication Method[END_REF], mainly try to make it more difficult to measure. These techniques either make the sample size for the analysis significantly large, or try to break the ability of the attacker to correlate information which is used for statistical analysis to work.

In this work, we propose a novel cryptosystem design using Dynamic Voltage and Frequency Switching (DVFS) against all kinds of power attacks. We show that naive random changes to the operating voltage and frequency are not sufficient to obscure the operation of the encryption system. We develop advanced circuit methods that substantially obscure encryption operations at minimum hardware cost in addition to much power savings without missing the timing deadline. The remainder of this paper is organized as follows. Section II presents some background material and motivates this work. Section III describes the novel cryptosystem design and experimental results. Section IV concludes this paper.

II. BACKGROUND AND MOTIVATION

This section describes previous work that motivates our study of DVFS. Specifically, we briefly introduce a typical cryptographic algorithm, DES algorithm, which will be used as a benchmark to test the efficiency of our novel cryptosystem. Then we discuss power attack techniques, which include Simple Power Attack (SPA) and Differential Power Attack (DPA). We also review the traditional idea of DVFS and show the potential of DVFS in the design of tamper resistant cryptosystem. Finally we point out the issues our novel approach needs to address and motivation of this work.

A. Data Encryption Standard

The DES [START_REF]Commerce/National Institute of Standards and Technology, Data Encryption Standard (DES)[END_REF] algorithm is the most widely used symmetric cryptographic algorithm. It uses 64 bits for the key, of which 56 bits are used for encryption and decryption while the other 8 bits are used for error detection in key generation, distribution and storage. The plaintext is permuted first before it goes to the encryption process. The core of the DES encryption process consists of 16 identical rounds, each of which has its own sub secret key, called K n(n = 1, 2, ...16). Each Kn is 48 bits produced from the original secret key using key permutation and shift operations. Each round consists of 8 S-box selection functions. Each of the unique selection functions, S1, S2,..., S8, takes a 6-bit block as input and yields a 4-bit block as output. For DES decryption algorithm, it is the reverse of encryption algorithm.

B. Power Attacks

B.1 Simple Power Attack

SPA is based on measuring and analyzing power traces during cryptographic computations. Basically by using inspection, the attacker analyzes the trace and identifies executed instructions (such as whether a branch at time t is taken or not taken or whether a multiplication or squaring operation is performed) and derives data bits of the involved operands (including secret keys). Due to its straightforward methodology, protecting against this type of simple attack can be achieved fairly easily by restructuring the code [START_REF] Coron | Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF], introducing noise into power measurement by adding dummy modules which are activating at random intervals [START_REF] Benini | Energy-Aware Design Techniques for Differenctial Power Analysis Protection[END_REF], etc. The key point of countermeasures is tuning the power traces to prevent information leakage.

B.2 Differential Power Attack

DPA is currently the most popular high order power analysis and is a very real threat which has been used to break the security of smart cards. This scheme utilizes power traces gathered from several runs and relies on the power consumption variation due to data dependency to break the key. It proceeds as follows. A DPA attack begins by running the encryption algorithm for N random values of plaintext inputs. For each of the N plaintext inputs, P i, a discrete power signal, Si[j], is collected using high speed analog to digital converters and the corresponding ciphertext, Ci, may also be collected. The power signal Si[j] is a sampled version of the power consumed during the execution of the algorithm that is being attacked. The index i corresponds to the Pi that produces the signal and the index j corresponds to the time of the sample. After the data collection, the attacker makes a hypothesis about the key. For example, if the target algorithm is DES algorithm, a typical prediction might be that the 6 key bits entering S-box4 are equal to '011010'. If correct, an assertion of this form allows the attacker to compute four bits entering the second round of the DES computation. If the assertion is incorrect, however, an effort to predict any of these bits will be wrong roughly half the time. For any of the four predicted bits, the Si[j] signals are split into two sets using a partitioning function, D(.):

S0 = {Si[j]|D(.) = 0} S1 = {Si[j]|D(.) = 1} (1)
The next step is to compute the average power signal for each set:

A0[j] = 1 |S0| S i [j]∈S 0 Si[j] A1[j] = 1 |S1| S i [j]∈S 1 Si[j] (2)
where S0 + S1 = N . By subtracting the two averages, a discrete time DPA bias signal, T [ j], is obtained:

T [j] = A0[j] -A1[j] (3)
If the original hypothesis is incorrect, the criteria, D(.) function, used to create the subsets will be approximately random. Any randomly chosen subset of a sufficiently large data set will have the same average as the main set. As a result, the difference ,T [j], will be effectively zero at all points, and the attacker repeats the process with a new guess. If the hypothesis is correct, however, choice of the subsets will be correlated to the actual computation. In particular, the second round bit will be '0' in all traces in one subset and '1' in the other. When this bit is actually being manipulated, its value will have a small effect on the power consumption, which will appear as a statistically significant deviation from zero in the T [ j]. This method allows the attacker to learn all 48 bits of the subkey for the 16th round. The remaining 8 bits can be found by brute force or by successively applying this approach backward to previous round.

From the above description, we can see that there is a very important assumption about DPA, i.e., the output of the S-Box must occur at a fixed time or the operational frequency of the cryptoprocessor must be constant. Thus, traces collected by an attacker can be correlated in time, so that the statistical analysis is

C. Dynamic Voltage and Frequency Switching

DVFS was proposed as an effective approach to reduce energy and realized in two levels, low-level hardware support [START_REF] Nowka | A 32-bit PowerPC System-on-a-Chip with Support for Dynamic Voltage Scaling and Dynaic Frequency Scaling[END_REF], [START_REF] Zhai | Theoretical and Practical Limits of Dynamic Voltage Scaling[END_REF] and high-level software support(operating system, compiler, etc) [START_REF] Choi | Off-Chip Latency-Driven Dynamic Voltage and Frequency Scaling for an MPEG Decoding[END_REF], [START_REF] Ghiasi | Using IPC Variation in Workload with Externally Specified Rates to Reduce Power Consumption[END_REF]. In most current low-power DVFS processor designs [START_REF]Transmeta crusoe[END_REF]- [START_REF]Ibm powerpc[END_REF], the voltage range is limited from full supply voltage V dd to approximately half V dd at most, for example, the voltage ranges and frequency ranges are 1.0V-1.8V and 153M-333MHz for IBM PowerPC 405LP processor, 0.8v-1.3v and 300M-1GHz for Transmeta Crusoe TM5800 processor, and 0.95V-1.55V and 333M-733MHz for Intel Xscale 80200 processor. Theoretical study [START_REF] Zhai | Theoretical and Practical Limits of Dynamic Voltage Scaling[END_REF] showed that extending the voltage range below 1/2V dd will improve the energy efficiency for most processor designs, while extending this range to subthreshold operation is beneficial only for very specific applications.

D. Motivation

Based on the above analysis, we propose a new defense against the power attacks (SPA and DPA), which is effective, simple to implement and, unlike previous defenses, does not require algorithmic alterations. The defense is based on the implicit assumption of power attacks that the operational frequency of the cryptoprocessor is constant and thus, traces collected by an attacker can be correlated in time, so that the statistical analysis is feasible. The way to realize it is dynamic voltage and frequency switching during the execution of a cryptographic algorithm. Its methodology and implementation will be explained in the next section.

III. CRYPTOSYSTEM DESIGN

Our novel power attack resistant cryptosystem is composed of processor core, DVFS Feedback Loop (DVFSFL), and DVFS Scheduler (DVFSS), as shown in Figure 1. The DVFSFL [START_REF] Nowka | A 32-bit PowerPC System-on-a-Chip with Support for Dynamic Voltage Scaling and Dynaic Frequency Scaling[END_REF], [START_REF] Zhai | Theoretical and Practical Limits of Dynamic Voltage Scaling[END_REF] takes the value of desired Voltage/Frequency (V/F) as an object, which is stored in a internal register by the DVFSS. DVFSFL physically implements the desired supply voltage and operating frequency by using ring oscillator, phase locked loop, etc, and finally outputs the supply voltage to the cryptoprocessor core. The DVFSS unit randomly generates a voltage or frequency (V/F) value under certain limits and stores it in the register. This unit requires some timing information about the application program from the Operating System (OS), for example, the desired running time. In this work, we focus our attention on the design of DVFSS unit which effectively makes our cryptosystem unbreakable by power attacks.

A. DVFS Efficiency Metrics

In order to quantitatively measure the efficiency of our DVFS technique against power attacks, we define three metrics: Signal Trace Entropy (STE), Energy Overhead (EO) and Time Overhead (TO). STE measures the uncertainty of the signal trace monitored by the attacker over time. To calculate STE, we bin the signal values in a signal trace into N equally spaced containers, and count the number of signal values in each container, ni. Then STE can be expressed as Equation [START_REF] Ravi | Embedding Security in Wireless Embedded Systems[END_REF]. Specifically in this work, we use Power Trace Entropy (PTE) and Time Trace Entropy (TTE) to represent the uncertainty of the power traces and the clock period traces, respectively. The power trace measures the power consumption for each clock cycle during the algorithm execution; while time trace gives the clock period for each clock cycle. For EO and TO, they measure the energy overhead and time overhead caused by using DVFS. We define V dd normal and F normal as the normal supply voltage and the normal operating frequency for the cryptoprocessor without DVFS. In general, they are the highest supply voltage and frequency. When the supply voltage is switched to a lower value v dd scale , the operating frequency f scale is scaled according to Equation [START_REF] Ömmerling | Design Princeples for Tamperresistant Smartcard Processors[END_REF], where V th represents threshold voltage. Finally, EO and TO can be expressed as Equation ( 6) and Equation [START_REF] Kocher | Timing Attacks on Implementations of Diffe-Hellman, RSA, DSS and Other Systems[END_REF], respectively, where T NCC is the total number of clock cycles, and Ci is the capacitive load for ith clock cycle.

ST E = - N i=1 ni N j=1 ni log2 ni N j=1 ni (4) f scale = (v dd scale -V th ) 1.3 v dd scale × F normal (5) EO = T NCC i=1 1 2 Ci(v 2 dd scale -V 2 dd normal ) (6)
T O = T NCC i=1 ( 1 f scale - 1 F normal ) (7)

B. Experimental Setup

For the following designs and experiments, we make some reasonable assumptions. (1) In order to test the efficiency of the DVFSS unit, the underlying hardware of the DVFSFL unit is assumed to be realized already and implements DVFS from full range 1.8V/450MHz to 0.9V/250M. Furthermore, we abstract its function as a software program to communicate with the cryptoprocessor and the DVFSS unit. (2) The power overhead for the cryptoprocessor switching from high voltage/high frequency mode to low voltage/low frequency mode and vice versa is negligible. This assumption is tested to be reasonable in [START_REF] Nowka | A 32-bit PowerPC System-on-a-Chip with Support for Dynamic Voltage Scaling and Dynaic Frequency Scaling[END_REF], [START_REF] Zhai | Theoretical and Practical Limits of Dynamic Voltage Scaling[END_REF]. For the power consumption by DVFSS unit and DVFSFL unit, it is not counted when we measure the power traces and it is much less than that consumed by the cryptoprocessor. (3) For the cryptoprocessor, the supply voltage and operating frequency can be changed instantly during any clock cycle. It is an ideal condition. When an application runs for thousands of clock cycles, however, this ideal assumption tends to be true from a statistical viewpoint as voltag/freqquency switching may just take a few clock cycles.

For this work, we implement the DES encryption and decryption algorithms in software as benchmarks, and capture their energy consumption at each clock cycle when running on the processor core by using a customized version of the publicly available Sim-plePower [START_REF] Vijaykrishnan | Energy-Driven Integrated Hardware-Software Optimizations Using SimplePower[END_REF]. The cryptoprocessor is based on the architecture of a five-stage pipelined datapath which consists of the instruction fetch stage IF, the instruction decode stage ID, the execution stage EXE, the memory access stage MEM, and the write back stage WB. The simulator uses validated transition-sensitive and cycle-accurate energy models for both the datapath and memory systems. The flexibility of working with the simulator provides us the ability to monitor the energy consumed in every cycle along with details of actual instructions executed.

C. Cryptosystem Design

For power analysis, the attackers uncover the secret key bits by observing some significant characteristics in the original power traces and the differential power traces after running the algorithm many times. If the measured power signal is random and cannot be repeated by running the algorithm any times using same plaintext and same key, the underlying secret key cannot be broken. Based on this analysis, an efficient power attack resistant method is to realize a random number generating algorithm in the pivotal design of the cryptosystem, i.e. DVFSS unit, which can randomly generate a voltage/frequency value and store it in the designated register. After the random operating voltages are applied to the cryptoprocessor, the output signal will achieve the desired property. In the following, we will implement this DVFSS unit step by step.

C.1 First DVFSS: Naive Design

For each clock cycle of the cryptoprocessor, a naive and extreme design of the DVFSS unit generates a random voltage value (frequency is determined by Equation ( 5)) and informs the DVFSFL unit to physically implement this voltage and feed it to the processor core. Here, we neglect the time consumed to generate the random number in the DVFSS and the time consumed to implement it in the DVFSFL. This means the DVFSS unit can generate as many random numbers as we want during a clock cycle and the DVFSFL unit can provide the cryptoprocessor with as many new voltage values as it needs in every clock cycle. With this assumption, we can analyze the effectiveness of DVFS against power attacks under the extreme condition. The algorithm of this naive implementation is shown in Figure 2. The procedure takes V dd normal , F nomral , Signal Done and RW Enable as inputs; the first two signals come from the OS and give initial values for the DVFSS; the third signal is from the processor core which indicates whether the encryption/decryption finishes; and the fourth signal is sent out from DVFSFL to reveal the status of the internal register which stores the desired voltage/frequency value. By using the initial voltage/frequency value, the DVFSS generates random voltage/frequency number every clock cycle and outputs it to the DVFSFL register. DES encryption algorithm is tested in the cryptosystem and the power signal is measured by using customized SimplePower tool. In order to make the statistical results confident, the DES encryption algorithm is run for 1000 times on the naive implementation. The power traces without DVFS and with DVFS each clock cycle are shown in Figure 3. We list the EO, TO, PTE and TTE in Table I. For Figure 3(b), it is a typical case. However, its profile is similar as other power trace profiles with DVFS per clock cycle.

Figure 3(a) shows the power behavior of the DES encryption algorithm when running on the cryptoprocessor without DVFS technique. It clearly reveals the 16 DES rounds of operation. Figure 3(b) illustrates the power profile with DVFS per clock cycle, for DES algorithm running on the naive implementation. Although there is a little improvement on the information leakage, Figure 3(b) still makes the 16 DES rounds obvious. This phenomenon can be explained by the following fact. The total 16 DES rounds need about 211000 clock cycles when completely running on the processor core, and each round consumes about 10 5 clock cycles. For each round, a high power peak value lasts for about 2.5 × 10 4 clock cycles, while a low power peak value lasts for another 2.5 × 10 4 clock cycles. Although the voltage/frequency is randomly changed every clock cycle, which makes the power value for each clock cycle to be a random number, the power peak values still will appear when the power trace is plotted over such a big sample size as 2.5×10 4 clock cycles. This fact makes the naive implementation unable to mask the power consumption and prevent the information leakage. From Table I we can see, with an increase in the entropies of power trace and time trace, there is a big reduction on the total energy consumption and a big increase in the total time consumed by the DES algorithm, compared with that without DVFS.

C.2 Second DVFSS: Improved Design

We now propose an improved design. The algorithm is shown in Figure 4. The input and output signals of this implementation are same as that of the naive one. For the naive DVFSS, the voltage/frequency is changed every clock cycle and the time consumption for the random number generating algorithm is neglected. In this improved implementation, once the voltage/frequency is changed, the DVFSS unit will wait for a random time period before generating another random voltage/frequency value. As a result, there are two time periods introduced by this implementation, one is the time consumed by the random number generating algorithm, the other is the time consumed for waiting (Here, we still neglect the time consumed for voltage/frequency physical implementation in DVFSFL uint, and we treat it as a fixed time). The first time period is a constant (first order approximation), while the second time period is a random time period. As a final effect, the voltage/frequency is changed randomly in terms of value and generating time. In order to test the efficiency of this implementation, power and clock period are measured and calculated per clock cycle. Figure 5 illustrates the power traces and clock period traces for this improved implementation under two typical cases. The first case, as shown in Figures 5 (a1) and (a2), has long random waiting time between two random voltage/frequency generations. From the beginning to the end of the program running on the processor, The DVFSS only generates 10 random voltage/frequency numbers. The second case, as shown in Figures 5 (b1) and (b2), however, has a very short waiting time and generates 211 random voltage/frequency values. It is obvious that the first case cannot mask the information leakage and clearly reveals the 16 DES rounds. While the second case shows a very random power trace, and the DES rounds are efficiently masked.

To quantify the statistical properties of these two cases, the algorithm implementation is modified. The total number of random voltage/frequency values is fixed to 10 (for 1st case) or 211 (for 2nd case), while the voltage/frequency values and the time when the voltage/frequency values are generated are randomly determined. The experiments are repeated to 1000 times to make the statistics confident. Finally, the EO, TO, PTE, and TTE are listed in Table II. It shows that the second case with short waiting time improves the PTE, TTE and EO compared with the first case with 1.06% more time consumption. Although the first case will appear with small probability when the cryptography algorithm runs on our cryptosystem, this case should be avoided. To implement the advanced DVFSS unit, there are two problems we need to solve. The first is long random waiting time which should be avoided. The second is tradeoff between energy reduction and timing overhead which is a big problem for real time cryptographic applications with restricted deadline time.

C.3 Third DVFSS: Advanced Design

The algorithm of the advanced design of DVFSS unit is shown in Figure 6. Two new signals, T B and ET CC, are input to the DVFSS unit from the OS. Signals T B and ET CC are estimations of the timing budget and the total clock cycles for the application program when running on the processor core. Both of them can be generated by the OS after the application program is compiled.

For the advanced DVFSS unit, it first generates a random v dd scale /f scale and stores it in the register for the processor core using it to run the program. After that, it initializes and determines the High limit W T , which represents the high limit of the waiting time. This limit prevents the DVFSS unit from a long random waiting time. For convenience, this waiting time limit can be calculated by the OS and input to the DVFSS unit. Here we assign it a constant number.

During the program running in the processor core, the DVFSS unit iteratively generates random voltage/frequency values. In each iteration, it firstly waits a random time limited by High limit W T , then calculates some timing information, determines the lowest value (LV ) for the next voltage/frequency generation, and produces a random voltage/frequency which is not lower than the LV . As a final step, it outputs the voltage/frequency value to the register. Variables timing and timing space count the total elapsed time and the time elapsed for one iteration, respectively. They are used to calculate the LV .

For our cryptosystem, the first goal is preventing the information leakage instead of saving power which is a by-product of DVFS. However, DVFS does bring much timing overhead that is not desired. In order to reduce it, the DVFSS unit first calculate the lower bound, i.e. LV , and then generates the suitable voltage/frequency. Equation 8shows how to calculate the lower bound for the scaled frequency. And the corresponding scaled supply voltage can be calculated by Equation [START_REF] Ömmerling | Design Princeples for Tamperresistant Smartcard Processors[END_REF].

LV = (ET CC -i timing space/f scale (i -1)) (T B -(timing + ∆)) (8)
where f scale (i -1) represents the scaled frequency randomly generated in the (i -1)th iteration. The summation is done over the number of iterations and calculates the total time elapsed. ∆ is an estimation of the time spent for steps from 16 to 21. The numerator gives the total clock cycles needed to finish the remainder workload, while the denominator gives the total time left for the application program to meet its deadline according to the time budget. Finally, this equation gives the lowest frequency for the processor to finish the application. The DVFSS unit uses this number as a lower bound and generates a random frequency number which is higher than the bound. Figure 7 compares two differential power traces generated by using two different keys and the same plaintext before using DVFS (Figure 7 (a)) and after using advanced DVFSS (Figure 7 (b)). And it illustrates the difference between two differential power traces generated by using two different plaintexts and the same key before using DVFS (Figure 7 (c)) and after using our advanced DVFSS (Figure 7 (d)). For Figures 7 (a) and (b), the secret keys vary in the first bit; while for Figures 7 (c) and (d) the Plaintexts vary in the tenth bit. These bit variations are randomly selected, and same profiles can be observed for other choices. Figures 7 (a) and (c) demonstrate that without DVFS significant information is leaked by using different key bits or different plaintext bits to run the algorithms and doing time correlation. When the advanced DVFSS is used, this information leakage is prevented as shown in Figures 7 (b) and(d).

Two factors contribute to this good property of our cryptosystem. (1) When the encryption/decryption program runs in our cryptosystem for the first time, operation A is executed at time t; while it is executed at time (t+∆t) when the program runs again. ∆t represents a time shift with positive or negative value. With high probability, it is not equal to zero. As a result, at a fixed time point for many power traces which are achieved by using different plaintexts or keys, different operations are carried out in the processor core. This makes time correlation, which is a very important step in power attacks, impossible. (2) Even if the same operation is executed at time t, the supply voltages for different runs may be different with much probability. This makes the power values at time t for different traces unequal and results in a random number for DPA bias signals. All the two aspects efficiently prevent the advanced cryptosystem from the power attacks, such as SPA and DPA.

To test and quantify the efficiency of our advanced cryptosystem against power attacks, DES encryption and decryption algorithms were run in this cryptosystem for one thousand times. Table III shows the energy overhead, time overhead, power trace entropy, time trace entropy and Long Time Waiting Effect (LTWE) for DES encryption and decryption algorithms. From the table, we can see the PTE and the TTE are greatly increased and much higher than that of the improved implementation. As a result, the LTWE does not exist for DES encryption and decryption algorithms. Furthermore, the TO is much less than that of the previous two implementations with a sacrifice of energy reduction. As an advanced implementation, it overcomes all the shortcomings of the naive and the improved implementations. By adjusting the lowest value for v dd scale /f scale in the algorithm to be a higher value, we can further reduce the time overhead. Experiments show that the TO range for encryption and decryption is about 17% to 5%.

Finally, we compare the performance of our DVFS cryptosystem and the cryptosystem without DVFS by using DES algorithm as a IV. CONCLUSIONS In this paper, we presented a design of novel power attack resistant cryptosystem, which uses dynamic voltage and frequency switching to make the power traces show random property and prevent the power attackers from doing time correlation between different power traces. Experiments were carried out through three levels, naive, improve, and advanced implementations, to test the efficiency and performance of this dynamic voltage and frequency switching approach. For the naive and the improved implementations, they did enhance the resistance of the cryptosystem to the power attacks, but with inborn shortcomings which make this cryptosystem still attackable. Advanced cryptosystem realization overcame all the shortcomings and exhibited excellent efficiency to block the SPA and DPA attacks. DES encryption and decryption algorithms were tested on this advanced cryptosystem. Results show that both the power trace entropy and time trace entropy are high enough to prevent information leakage. While the energy consumption is averagely reduced by 27%, the execution times for both algorithms are delayed for 16%. This advanced DVFSS implementation provides an efficient method to countermeasure the popular power analysis attacks, and is difficult to be broken because of its random property.

Fig. 1 .

 1 Fig. 1. DVFS cryptosystem.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Naive implementation of DVFSS unit.

Fig. 4 .

 4 Fig. 4. Improved implementation of DVFSS unit.

Fig. 5 .

 5 Fig. 5. Comparison between long random waiting time (for (a1) and (a2)) and short random waiting time (for (b1) and (b2))in terms of power traces and clock period traces. For all the four figures, the X axis represents clock cycle number.

Fig. 6 .

 6 Fig. 6. advanced implementation of DVFSS unit.

Fig. 7 .

 7 Fig.7. Difference between power traces generated using two different keys (vary in the first bit of the key) before using DVFS (a) and after using advanced DVFSS (b); Difference between power traces generated using two different plaintext (vary in the 10th bit of the plaintext) before using DVFS (c) and after using advanced DVFSS (d).

TABLE II PERFORMANCE

 II COMPARISON FOR IMPROVED DVFSS IMPLEMENTATIONS.

	DES Encryption	EO	TO	PTE	TTE
	long waiting time	-34.18%	25.15%	5.20	3.17
	short waiting time	-35.23%	26.21%	5.33	5.97

  generate random vdd_scale/fscale by using Vdd_normal, Fnormal 3: assign vdd_scale/fscale to register in DVFSFL 4: initialize timing, timing_space to zero timing_space += timing_space 15: use timing, timing_space, TB, ETCC to determine the lowest value of vdd_scale/fscale, 16: generate random vdd_scale/fscale > the lowest value 17: if RW_Enable==1 18: assign vdd_scale/fscale to register in DVFSFL

	Input	: Vdd_normal, Fnormal, TB, ETCC,
		Signal_Done, RW_Enable
	Output	: vdd_scale/fscale
	Algorithm :
	1: time_1= clock()
	2: 5: determine High_limit_WT
	6: While Signal_Done != 1 Do
	7: time_3=clock()
	8: generate a random number NCC < High_limit_WT
	9: for i=1:1:NCC
	10: NOP
	11: end for
	12: time_2= clock();
	13: timing= (time_2-time_1)/clocks_per_second_DVFSS
	14: 19: end if
	20: time_4=clock()
	21: timing_space=(time_4-time_3)
	22:End While

TABLE III ACHIEVED

 III PERFORMANCE FOR DES ENCRYPTION AND DECRYPTION BY USING ADVANCED DVFSS. and summarize it in TableIV. As we can see, our novel cryptosystem obtains 27% energy reduction, 7.5% increase in power trace entroy, and ∞% increase in time trace entroy, with a timing overhead of 16%, compared with the cryptosystem without DVFS.

	DES	EO	TO	PTE	TTE LTWE
	Encryption	-27.32%	16.15%	5.42	6.02	No
	Decryption	-26.89%	16.01%	5.44	6.05	No

benchmark

TABLE IV PERFORMANCE

 IV GAIN OF DVFS CRYPTOSYSTEM OVER NORMAL CRYPTOSYSTEM WITHOUT DVFS.

		Energy	Time	PTE	TTE
	DVFS Cryptosystem	-27%	+16% +7.5%	+∞%

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)


Zoya Dyka

Peter Langendoerfer
email: langendoerfer@ihp-microelectronics.com

Area Efficient Hardware Implementation of Elliptic Curve Cryptography by Iteratively Applying Karatsuba's Method

Keywords: Extended Galois fields, polynomial multiplication, Elliptic Curve Cryptography, Karatsuba's formula

Securing communication channels is especially needed in wireless environments. But applying cipher mechanisms in software is limited by the calculation and energy resources of the mobile devices. If hardware is applied to realize cryptographic operations cost becomes an issue. In this paper we describe an approach which tackles all these three points. We implemented a hardware accelerator for polynomial multiplication in extended Galois fields (GF) applying Karatsuba's method iteratively. With this approach the area consumption is reduced to 2.1 mm 2 in comparison to. 6.2 mm 2 for the standard application of Karatsuba's method i.e. for recursive application. Our approach also reduces the energy consumption to 60 per cent of the original approach. The price we have to pay for these achievement is the increased execution time. In our implementation a polynomial multiplication takes 3 clock cycles whereas the recurisve Karatsuba approach needs only one clock cycle. But considering area, energy and calculation speed we are convinced that the benefits of our approach outweigh its drawback.

Introduction

Motivation Mobile devices are penetrating our every day life. More and more sensitive information is exchanged between mobile nodes and between mobile and fixed communication endpoints. This data exchange is normally protected by cipher mechanisms. But due to the scarce resources of mobile nodes, exhaustive use of cryptographic means is infeasible. This holds especially true for public key cryptography, which is normally used to establish a secure channel between the communicating parties as well as for providing digital signatures. Hardware accelerators for public key cryptography operations are ideal means to reduce the calculation time as well as the energy consumption. But, a straight forward realization of cryptographic operations results in a relatively large area consumption, which makes the application of hardware accelerators economically infeasible. Thus, our design constraints were:

• Calculation time,

• Energy consumption, and

• Area consumption.
We decided to use Elliptic Curve Cryptography (ECC) since it guarantees the same security level as RSA does but with significant shorter keys. In addition to this the ECC operations are faster than those of RSA [START_REF] Brown | PGP in Constrained Wireless Devices[END_REF]. We selected B-233 over Galois field GF (2 233 ) which is recommended by NIST [START_REF]Digital Signature Standard[END_REF] and well suited to be implemented in hardware.

Despite ECC is less computational intensive than RSA it still requires a significant effort in terms of energy and time. In this paper we concentrate on the area efficient realization of basic mathematical operations, which are used in ECC.

ECC Background

In order to calculate the product of two 233 bit long operands, denoted 'kP'. Here P is a point on an elliptic curve (EC) and k is a large number. The 'kP' multiplication is based on point doubling and point addition. All these EC point operations are based on addition, subtraction, squaring, multiplication and division in a chosen GF. The basic operations in GF (2 233 ) are addition, squaring, multiplication and division of polynomials. Addition of polynomials is equivalent to a bit-wise XOR operation. Squaring and multiplication require two steps: squaring/multiplication itself and reduction of the result. Reduction is done using so-called irreducible polynomials and it is a fast operation in GF(2 n ). The irreducible polynomial for B-233 is the trinomial:

1 ) ( 74 233 ⊕ ⊕ = x x x f 1 .
Division of polynomials usually is done in two steps: first identifying the inverse of the divisor using the irreducible polynomial, and second multiplying the inverse with the dividend. Multiplication and division of polynomials require the major part of the calculation time.

In this paper we are concentrating on polynomial multiplication, since our long term goal is to implement a Montgomery multiplier for the 'kP' operation. The Montgomery method requires only one polynomial division for 'kP', so that the major effort comes from the multiplication.

Contribution and structure of this paper

In this paper we show that an iterative application of the Karatsuba method provides very good results with respect to the following three parameters: calculation time, area consumption and energy consumption. With our iterative hardware solution, the chip area needed to calculate the product of two 233 bit long operands, is 2.1 mm 2 whereas the standard application of Karatsuba's method needs 6.2 mm 2 . Our approach also reduces the energy consumption to 60 per cent of the original approach. The price we have to pay for these achievements is the increased execution time. In our implementation a polynomial multiplication takes 3 clock cycles whereas the original one needs only one clock cycle.

The rest of this paper is structured as follows. Section 2 contains a short description of implemented methods. We propose to use the Karatsuba's formula for polynomial multiplication iteratively. The detailed description of our approach is given in Section 3. Section 4 discusses the hardware realization of our approach and provides measurement results. We conclude the paper with a short discussion of our results and an outlook on further research steps.

State of the art

In this section we describe methods for polynomial multiplication in polynomial basis. We implemented these methods and different combinations of them to realize our own approach and to benchmark our solution.

Polynomial multiplication

The product of two polynomials

i i n i x a x A ⊕ - = = 1 0 ) ( and i i n i x b x B ⊕ - = = 1 0 ) ( is the polynomial: , ) ( ) ( ) ( 2 2 0 i i n i x c x B x A x C ⊕ - = = ⋅ = where l k i l k i b a c ⋅ = ⊕ = + , i.e.: 1 1 2 2 1 2 2 1 3 2 1 0 1 2 0 1 1 1 0 0 1 1 0 0 0 - - - - - - - - - - - - ⋅ = ⋅ ⊕ ⋅ = ⋅ ⊕ ⊕ ⋅ ⊕ ⋅ = ⋅ ⊕ ⋅ = ⋅ = n n n n n n n n n n n n b a c b a b a c b a b a b a c b a b a c b a c ( 1 )
The straight forward implementation of formula (1) requires n 2 partial multiplication and (n-1) 2 XOR operations of partial products in order to calculate c i . All operands in formula ( 1) are only one-bit long. In case of using EC B-233 both polynomials A(x) and B(x) are 233-bit long. It means that in total 233 2 one-bit partial multiplications and 232 2 XOR operations are required.

Karatsuba based methods

Original

Karatsuba's method For polynomial multiplication with original Karatsuba method [START_REF] Karatsuba | Multiplication of multidigit numbers by automata[END_REF] both operands have to be fragmentized into two equal parts. If the length n of operands is odd, they have to be padded with leading '0'. So, operands can be written as 2 :

0 2 1 0 1 1 2 2 2 1 0 1 1 2 2 1 ... ... ... ... ) ( a x a a a a x a a a a a a a x A n n n n n n n n ⊕ ⋅ = = ⊕ ⋅ = = - - - - (2)
2 We denote as ai the i th bit and as a i the i th segment of operand A(x).

The polynomial B(x) is represented in the same way. The Karatsuba's formula for the product

C(x)=A(x)ÂB(x) is [ ] n n x b a x b b a a b a b a b a x C ⋅ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕ ⊕ ⊕ = 1 1 2 1 0 1 0 1 1 0 0 0 0 ) )( ( ) ( (3)
In order to calculate the partial products partial multiplications, where s is the number of segments. This method can be used to speed up software as well as hardware implementations. Usually in software implementations the Karatsuba's approach is applied until both operands have a size of one word.

In Bailey and Paar [START_REF] Bailey | Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography[END_REF] a new scheme how to apply Karatsuba's idea was proposed. In this scheme the operands are divided into three parts. Throughout the rest of this paper we denote this method as Bailey's method. It requires 6 partial multiplications of n/3-bit long operands. This method can be combined with the original Karatsuba formula for operands, whose length is divisible by six.

Iterative Application of the Karatsuba Approach

The major point in our approach is to apply the original version Karatsuba's method iteratively. We denote this as Iterative-Karatsuba method. The major benefits of this approach are:

-a smaller area consumption of the hardware accelerators due to the fact that partial multiplications can be performed serially -a reduced number of XOR operations compared with the recursive variant of Karatsuba's method.

We explain our idea of the iterative application of Karatsuba's formula using an example in which the operands are split up into four segments. First of all, we use the original Karatsuba formula to obtain the expression for a product, in which only 1-segment long operands for partial multiplication are used.

So, at the beginning we have two operands, each of them 4n-bit long. We fragment each operand into two 2n-bit long parts:

0 1 2 2 3 0 1 2 3 0 1 2 2 3 0 1 2 3 ) ( ) ( b b x b b b b b b x B a a x a a a a a a x A n n ⊕ ⋅ = = ⊕ ⋅ = = (4)
The result of applying Karatsuba's formula is:

[ ] n n x b b a a x b b a a b b a a b b a a b b a a x C 4 2 3 2 3 2 02 13 02 13 2 3 2 3 0 1 0 1 0 1 0 1 ) ( ⋅ ⋅ ⊕ ⊕ ⋅ ⋅ ⊕ ⋅ ⊕ ⋅ ⊕ ⊕ ⋅ = (5)
where

2 3 0 1 2 3 0 1 2 0 3 1 02 13 02 13 ) ( ) ( ) ( ) ( a a a a a x a a x a a a x a a a x a a a n n n n ⊕ = ⊕ ⋅ ⊕ ⊕ ⋅ = = ⊕ ⊕ ⋅ ⊕ = ⊕ ⋅ = (6)
and

2 3 0 1 02 13 b b b b b b ⊕ = (7)
Every 2-segments element is:

j n i j i a x a a a ⊕ ⋅ =
. So, for each partial multiplication from ( 6) and ( 7) we use the Karatsuba's formula again. The final result is given in formula (8).

⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⊕ ⋅ ⊕ ⊕ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕ ⋅ = (8)
Each of the operands is 1-segment long, so that the resulting partial product is (2n-1)-bit long. We denote the bits from n-1 to 0 of the product

i i b a ⋅ as ] 0 [ i i b a
and the bits from 2n-

1 to n as ] 1 [ i i b a : ] 0 [ ] 1 [ i i n i i i i b a x b a b a ⊕ ⋅ = ⋅ (9)
Using the notation introduced in (9) we can represent formula (8) as given in table 1.

Table1. Representation of formula (8)

partial products segments of result

a 0 ƒb 0 [0] ⊕ ⊕ ⊕ ⊕ a 0 ƒb 0 [1] ⊕ ⊕ ⊕ ⊕ a 1 ƒb 1 [0] ⊕ ⊕ ⊕ ⊕ a 1 ƒb 1 [1] ⊕ ⊕ ⊕ ⊕ a 2 ƒb 2 [0] ⊕ ⊕ ⊕ ⊕ a 2 ƒb 2 [1] ⊕ ⊕ ⊕ ⊕ a 3 ƒb 3 [0] ⊕ ⊕ ⊕ ⊕ a 3 ƒb 3 [1] ⊕ ⊕ ⊕ ⊕ (a 0 ⊕ a 1 )ƒ( b 0 ⊕ b 1 ) [0] ⊕ ⊕ (a 0 ⊕ a 1 )ƒ( b 0 ⊕ b 1 ) [1] ⊕ ⊕ (a 0 ⊕ a 2 )ƒ( b 0 ⊕ b 2 ) [0] ⊕ ⊕ (a 0 ⊕ a 2 )ƒ( b 0 ⊕ b 2 ) [1] ⊕ ⊕ (a 1 ⊕ a 3 )ƒ( b 1 ⊕ b 3 ) [0] ⊕ ⊕ (a 1 ⊕ a 3 )ƒ( b 1 ⊕ b 3 ) [1] ⊕ ⊕ (a 2 ⊕ a 3 )ƒ( b 2 ⊕ b 3 ) [0] ⊕ ⊕ (a 2 ⊕ a 3 )ƒ( b 2 ⊕ b 3 ) [1] ⊕ ⊕ (a 0 ⊕ a 1 ⊕ a 2 ⊕ a 3 )ƒ( b 0 ⊕ b 1 ⊕ b 2 ⊕ b 3 ) [0] ⊕ (a 0 ⊕ a 1 ⊕ a 2 ⊕ a 3 )ƒ( b 0 ⊕ b 1 ⊕ b 2 ⊕ b 3 ) [1] ⊕ = ) (x C 0 1 2 3 4 5 6 7 c c c c c c c c
All columns in table 1 which are nested under the topic 'segments of result' in represent a certain segment c i . For each partial product two lines are given in Table 1, one line representing the lower (a x b x [0]), and a second one representing the upper part (a x b x [START_REF] Brown | PGP in Constrained Wireless Devices[END_REF]) of the product as specified above. The segment c i can be calculated by XORing all lines in the table 1, which contain the symbol ' '⊕ in the column of c i . For example c 5 can be calculated as follows:

c 5 =a 1 b 1 [1]⊕ a 2 b 2 [0]⊕ a 2 b 2 [1]⊕ a 3 b 3 [0]⊕ a 3 b 3 [1]⊕ ((a 1 ⊕ a 3 )(b 1 ⊕ b 3 )[1])⊕ ((a 2 ⊕ a 3 )(b 2 ⊕ b 3 )[0]) (10)
Each segment c i can be calculated iteratively i.e. step by step as we calculate the partial products starting with 0 0 b a down to ( ) ( )

3 2 1 0 3 2 1 0 b b b b a a a a ⊕ ⊕ ⊕ ⋅ ⊕ ⊕ ⊕
. We then start to calculate the segments of products using the already received results. For example:

Step 1

Step

2 … ] 1 [ ] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 0 [ 0 0 4 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 0 0 0 b a c b a b a c b a b a c b a b a c b a c = ⊕ = ⊕ = ⊕ = = ] 1 [ ] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 0 [ 1 1 5 1 1 1 1 4 4 1 1 1 1 3 3 1 1 1 1 2 2 1 1 1 1 b a c b a b a c c b a b a c c b a b a c c b a c c = ⊕ ⊕ = ⊕ ⊕ = ⊕ ⊕ = ⊕ =

And so on to

Step 9

This iterative calculation of the C(x) reduces the area of our hardware multiplier. We need only one partial multiplier for 1-segment long operands. After each new clock this multiplier delivers the next partial product. In that way the segments of product C(x) are collected. For the above given example this means after 9 clock cycles all segments contain the correct product of the polynomial multiplication.

Additionally we exploit another 'iterative possibility': we do not need to calculate all segments of C(x) separately. We can use c 0 to determine c 1 after the first clock, c 1 for c 2 after second clock, and so on (see table 2). This iterative calculation reduces the number of XOR operations to 29 compared to 42 XOR operations if the calculation of every c i is done separately.

In a similar way we applied our iterative approach to Bailey's method, which we call Iterative-Bailey throughout the rest of this paper.

Table 2. Exact operation sequence of our hardware implementation of formula (8)

clock obtained partial product sequence of operations 1

pr = a 0 ⋅ b 0 c 0 = pr[0] c 1 = pr [1] 2 pr = a 1 ⋅ b 1 c 1 = c 1 ⊕ c 0 ⊕ pr[0] c 2 = pr[1] 3 pr = a 2 ⋅ b 2 c 2 = c 2 ⊕ c 1 ⊕ pr[0] c 3 = pr[1] 4 pr = a 3 ⋅ b 3 c 3 = c 3 ⊕ c 2 ⊕ pr[0] ⊕ pr[1] c 7 =pr[1] 5 pr = (a 0 ⊕ a 1 ) ⋅ (b 0 ⊕ b 1 ) c 6 = c 3 ⊕ c 2 c 5 = c 3 ⊕ c 1 c 4 = c 3 ⊕ c 0 ⊕ pr[1] c 3 = c 3 ⊕ c 7 ⊕ pr[0] c 2 = c 2 ⊕ pr[1] c 1 = c 1 ⊕ pr[0] 6 pr = (a 0 ⊕ a 2 ) ⋅ (b 0 ⊕ b 2 ) c 3 = c 3 ⊕ pr[0] ⊕ pr[1] c 2 = c 2 ⊕ pr[0] c 4 = c 4 ⊕ pr[1] 7 pr = (a 1 ⊕ a 3 ) ⋅ (b 1 ⊕ b 3 ) c 4 = c 4 ⊕ pr[0] ⊕ pr[1] c 3 = c 3 ⊕ pr[0] c 5 = c 5 ⊕ pr[1] 8 pr = (a 2 ⊕ a 3 ) ⋅ (b 2 ⊕ b 3 ) c 3 = c 3 ⊕ pr[0] c 5 = c 5 ⊕ pr[0] c 4 = c 4 ⊕ pr[1] c 6 = c 6 ⊕ pr[1] 9 pr = (a 0 ⊕ a 1 ⊕ a 2 ⊕ a 3 ) ⋅ Â (b 0 ⊕ b 1 ⊕ b 2 ⊕ b 3 ) c 3 = c 3 ⊕ pr[0] c 4 = c 4 ⊕ pr[1]

Hardware implementation

In this section we will present the design and the key parameters of our hardware realization of the Iterative Karatsuba approach.

The design of the Iterative Karatsuba accelerator consists of three major parts (see Fig. 1):

• Selection block feeds certain parts of both operands into the Partial Multiplier, for each new clock signal.

• Partial Multiplier block calculates the partial product of the operands delivered by the selection block and provides the results to the product accumulation block.

• Product Accumulation block computes the final product from the partial products it receives from the partial multiplier. The theoretical basis and exact operation sequence is discussed in detail in Section 3.

Figure 1: Block diagram of our Iterative-Karatsuba multiplier

The performance, chip area and energy consumption of a polynomial multiplier are dominated by the partial multiplier which is used. The larger the input signals of the partial multiplier may be, the faster the partial multiplier is. But this also results in a relatively large area consumption. So, the design decision to make seems to be straight forward: calculation time versus chip area. This is true as long as only the partial multiplier is considered. But for the polynomial multiplier also the area of the selection and the product accumulation block have to be taken into account.

The chip area needed for the accumulation block depends on the area of the partial multiplier in an inverse proportional manner, i.e. the smaller the partial multiplier the larger the accumulation block. This results from the fact that in case of small partial multipliers more intermediary results have to be stored for the final calculation of the polynomial product.

For example the size of the accumulation block is 0,649 mm 2 if the partial multiplier accepts 128 bit long operands, and 1,466 mm 2 if the maximum length of the operands is 32 bits.

In order to determine the most appropriate design for a polynomial multiplier we realized several partial multipliers. We realized 3 one-clock partial multipliers for our iterative Karatsuba as well as for our iterative Bailey approach. These partial multipliers accept operands with a maximal length of 128, 64 and 32 bits respectively. They were synthesized with a library of our in-house 0.25 m CMOS-Technology [START_REF]Technology[END_REF]. Table 3 shows the area, the time and energy consumption for each of these six partial multipliers. These values stem from the Design analyzer tool from Synopsys [START_REF]Products & Solutions[END_REF]. In order to benchmark our approach we realized polynomial multipliers using the following approaches:

• Iterative Karatsuba

• Iterative Bailey

• Original Karatsuba (recursive)

• Original Bailey (recursive)

For the first two approaches, i.e. for our own iterative approaches, we realized three polynomial multipliers using different partial multipliers (see table 3) in order to see how the partial multiplier influences the overall parameters. We named these multipliers so that the name indicates the applied method. For example, the name iterative_Karatsuba_8segments means: Iterative-Karatsuba fragmentizing incoming operands into 8 segments.

In the two recursive multipliers the original Karatsuba and the Bailey formula are applied down to one-bit operands. Both multipliers deliver the polynomial product after one clock cycle. They differ in the length of the input operands. The Karatsuba multiplier expects always two 256 bit long input values whereas the Bailey multiplier expects two 243bit long input values.

Since we are going to use these multipliers for EC B-233 the two input values will be only 233-bit long. Therefore the operands were padded with leading 0's if it was necessary. The result of the multiplication is always 465-bit long.

We synthesized all polynomial multipliers using a library of our in-house 0.25 m CMOS-Technology [START_REF]Technology[END_REF]. We obtained the data represented in these tables with different kinds of reports from the Synopsys "Design Analyzer" [START_REF]Products & Solutions[END_REF]. The parameters of the implemented polynomial multipliers are given in Table 4. Our results clearly indicate that an iterative application of the original Karatsuba and Bailey approach significantly reduces the chip area. If the number of iterations is kept small, our approach also helps to reduce the energy consumption. In those designs the decision is less area and less energy versus slower execution time. Increasing the number of iterations helps to reduce the chip area needed, but it also leads to an increased power consumption and an increased calculation time. So, these implementations are beneficial only if cost is the dominating parameter.

Conclusions and Outlook

In this paper we discussed the iterative application of Karatsuba's method for polynomial multiplications as a means to reduce the chip area and energy needed to run elliptic curve cryptography on mobile devices. In order to evaluate our approach we analyzed different methods for polynomial multiplication in GF(2 n ), and implemented different polynomial multiplication algorithms. For our own approach we realized several partial multipliers. Weused them to implement a set of iterative polynomial multipliers with the goal to identify the one which is best suited for application in mobile devices. Our results clearly indicate that our iterative approach leads to significantly better results with respect to area and energy consumption than the original straight forward application.

Our next step is the finalization of our Montgomery 'kP' multiplier. In this multiplier we will use the Fermat theorem, since it allows to determine the inverse for the division multiplication and squaring. The Fermat theorem is slower than the Extended Euklidian Algorithm or the method proposed by Shantz [START_REF] Weimerskirch | Elliptic Curve Cryptography on a Palm OS Device[END_REF], but it requires less area. Since the Montgomery method requires only a single division, we think that the smaller area outweighs the slower performance.

1

  Note: In GF(2 n ) addition and subtraction are XOR operations. Due to this and for simpler understanding of formulas we change the usual representation of polynomials ¦ of this paper we denote XOR operation as '⊕'. The symbol '+' means always an ordinary addition.

Table 3 . Parameters of synthesized partial multipliers

 3

	Name of partial	Length	Area, mm 2 time, ns Energy/clock,
	multiplier (PM)	of input			pW¡ s
		values,
		bits
	k128_k64_k32_k16_sh8	128	1.620410 12.53	1394.4000
	k64_k32_k16_sh8	64	0.514759	8.99	404.3913
	k32_k16_sh8	32	0.159006	5.62	108.2011
	p81_p27_sh9	81	0.896391	7.98	692.0033
	p39_sh13	39	0.264672	5.97	179.4565
	p27_sh9	27	0.133616	4.80	88.4779

Table 4 . Parameters of synthesized polynomial multipliers

 4

	Name of multiplier	Area,	Number	Period,	Power,	Energy,
			of	T, ns	P, mW	E=T¡ N¡ P,
		S, mm 2	clocks,			pW¡ s
			N
	iterative_Karatsuba_	2.18	3	15	98.89	4450.1
	2segments
	(PM -k128_k64_
	k32_k16_sh8)
	iterative_Karatsuba_	1.52	9	10	105.48	9493.2
	4segments (PM -
	_k64_k32_k16_sh8)
	iterative_Karatsuba_	1.67 27	9	107.63 26154.1
	8segments
	(PM -_k32_k16_sh8)
	iterative_Bailey_	2.12	6	10	148.16	8889.6
	3segments
	(PM -p81_p27_sh9)
	iterative_Bailey_	1.60 18	9	110.46 17894.5
	6segments
	(PM -p39_sh13)
	iterative_Bailey_	1.71	36	9	103.35 33485.4
	9segments
	(PM -p27_sh9)
	recurcive_Karatsuba_	6.28	1	19.35 326.15	6311.0
	for_1clock
	recurcive_Bailey_	7.02	1	16.94 441.75	7483.3
	for_1clock

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

This work was partially funded by the German Ministry of Education and Research under grant 01AK060B.


Magdy Hala A Farouk

Saeb Arab

AN IMPROVED FPGA IMPLEMENTATION OF THE MODIFIED HYBRID HIDING ENCRYPTION ALGORITHM (MHHEA) FOR DATA COMMUNICATION SECURITY

Keywords: FPGA, micro-architecture, data communication security, encryption, steganography, cryptography, algorithm

The hybrid hiding encryption algorithm, as its name implies, embraces concepts from both steganography and cryptography. In this exertion, an improved microarchitecture Field Programmable Gate Array (FPGA) implementation of this algorithm is presented. This design overcomes the observed limitations of a previouslydesigned micro-architecture. These observed limitations are: no exploitation of the possibility of parallel bit replacement, and the fact that the input plaintext was encrypted serially, which caused a dependency between the throughput and the nature of the used secret key. This dependency can be viewed by some as vulnerability in the security of the implemented micro-architecture. The proposed modified micro-architecture is constructed using five basic modules. These modules are; the message cache, the message alignment module, the key cache, the comparator, and at last the encryption module. In this work, we provide comprehensive simulation and implementation results. These are: the timing diagrams, the post-implementation timing and routing reports, and finally the floor plan. Moreover, a detailed comparison with other FPGA implementations is made available and discussed.

I. INTRODUCTION

In this work, we present an FPGA-based microarchitecture implementation of a modified version of the encryption algorithm entitled "Hybrid Hiding Encryption Algorithm (HHEA)" [SHAAR03]. In the basic version of this algorithm, no conventional substitution and translation operations on the plaintext characters are used. It rather uses simple plaintext hiding in a random bit string called the hiding vector. The name "Hybrid" is used to show that this encryption algorithm has built-in features that are inherited from data hiding techniques or "Steganography". As a matter of fact, one can use the micro-architecture for both steganography and cryptography depending on the user approach and the proper selection of the key. The basic version of this algorithm was previously implemented, as shown in reference [START_REF] Saeb | An FPGA Implementation of the Hybrid Hiding Encryption Algorithm (MHHEA) for Data Communication Security[END_REF]. However, this approach did not exploit the possibility of parallel bit replacement. Furthermore, the input plaintext was encrypted serially, which caused some dependency between the throughput and the nature of the key. This dependency can be viewed by some as vulnerability in the security of the implemented micro-architecture. Based on these observations and to eliminate certain types of cipher attacks, we decided to present a modified algorithm and its accompanying micro-architecture that overcomes such limitations. The modified design eliminates the dependency between the micro-architecture throughput and the key. It also provides a significant performance improvement by fully exploiting the inherited parallelism originated by the algorithm. Moreover, the modified version escapes the chosen-plaintext attacks. In the next few sections we discuss the modified algorithm, the building blocks of the proposed improved microarchitecture along with details of its operation, the simulation and implementation results. The details of the carried out simulations, timing, routing reports and the floor plan are completely provided in the given appendix. Moreover, we present a comparison with other implementations of a selected group of encryption algorithms [START_REF] Saeb | A Microarchitecture Implementation of YAEA Encryption Algorithm Utilizing VHDL and FPGA Technology[END_REF], [START_REF] Saeb | A Microarchitecture Implementation of YAEA Encryption Algorithm Utilizing VHDL and FPGA Technology[END_REF].

II. THE ALGORITHM

In the following few lines, we provide a summary of the MHHEA algorithm [SHAAR03]. The aim of the algorithm is hiding a number of bits from plain text message (M) into an N-bit long random vector (V). The locations of the hidden bits are determined by the key (K).

Algorithm MMHHEA [Given a plain text message M , key matrix K Lx2 , scrambled key matrix KN Lx2 where i =0,…., L; L 15

k ij 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 j =1,2
The aim of the algorithm is hiding a number of bits from plain text message (M) into a random vector (V) of bits. The locations of the hidden bits are determined by the key K Lx2 ] Input: M, K Lx2 , Output: encrypted file Algorithm Body: i: =0, m:=0 M[0]: =first digit in M file while (M[m] EOF) [EOF: End Of File] i: = i mod L Generate 16-bit randomly and set them in V Vector if (K i,1 K i,2 ) then z: =Ki,1 Ki,1: =Ki,2 K i,2 : =z // Scramble the hiding location using the high order bits of the hiding vector KNi,1:=V[Ki,2+8 down to Ki,1+8] XOR Ki,1 KNi,2:= KNi,1+(Ki,2-Ki,1) mod 8 if (KN i,1 KN i,2 ) then z: =KN i,1 KNi,1: =KNi,2 KNi,2: =z // Scramble the message bits using the original key q:=0 for j= KN i,1 to KN i,2 q:=q mod 3

if (M[m] EOF) then do V [j]=M[m] XOR K i,1 [q]
m: =m+1; next m in M file q:=q+1 end do next j Save V in output file i: =i+1 end while; End algorithm.

In this algorithm, we have scrambled the location and the message to overcome constant chosen-plaintext attack.

III. THE MICRO-ARCHITECTURE

In this section we describe the micro-architecture with its operation details using a finite state machine approach (FSM). The FSM, shown in Figure 1, illustrates the conceptual required hardware modules and the elements of the design of the control unit. The machine operation takes place through six basic states. These are summarized as follows. The initial state "Init" holds back the execution of the successive states until the "Go" signal is triggered and furthermore resets all hardware modules. In the following state "LMsg", the 32-bit input plaintext is buffered for the other modules to operate on. The key is buffered into sixteen four-bit pairs of registers in the "LKey" state. The key is saved in pairs of integers. One part of the key is XOR-ed with a part of the random vector V as described in the algorithm. After the scrambling of the key, the new key points to the locations of the substitution procedure as depicted in Figure 2. In a previous work [START_REF] Saeb | An FPGA Implementation of the Hybrid Hiding Encryption Algorithm (MHHEA) for Data Communication Security[END_REF], this procedure was performed serially where in each cycle one bit is replaced until the entire range from the left to right key is covered. However, we aim at designing a modified architecture that replaces the whole number of bits determined by the key in parallel rather in serial to improve the overall performance. The location of the replaced bits is determined randomly based on the generated sub-key. In this respect, two design alternatives are possible. In the first one, a variable connection between the register containing the random hiding vector and the register with the scrambled plaintext is required. Nevertheless, this approach is rather difficult. Therefore, in this modified design, the connection is fixed but the plaintext is rotated to be aligned with the bits that are to be replaced in the hiding vector. An example of the rotation scheme is illustrated in Figure 3. This leads to a considerable saving in time as well as the implementation area. The limited FPGA implementation area places a barrier on the size of the input plaintext required to be rotated. This fact has led to the splitting of the 32-bit input into two 16-bit parts. Each part is taken into a buffer inside the "Message Alignment" Module at a time during the "LMsgCache" state. The plaintext is subsequently aligned in the "Circ" state. Afterwards, the encryption or replacement procedure is performed in "Encrypt" state. These two states are interleaved in a chain of cycles until the whole 16-bit plaintext is encrypted. Consequently, the encryption process takes two clock cycles per one key pair regardless of the number of bits replaced. The micro-architecture is subdivided into six modules as shown in Figure 4. In the following subsections every module is described in details.

Message Cache

In this module 32-bit of the user plaintext is saved into two 16-bit registers. This is due to the fact that the "Message Alignment" module can operate on 16-bit data only. The reason for this constraint is described in the previous section.

Message Alignment

The "Message Alignment" module buffers the 16-bit plaintext for rotation. In order to accelerate the rotation process, multiplexers are used for n-bit rotations. Hence, the circulate operation takes only one clock cycle. In this module, the plaintext can be rotated left or right. The motivation behind this rotation procedure is explained in Figure 3. The module rotates left depending on the smaller scrambled key value and rotates right based on the larger key plus one.

Key Cache

The "Key Cache" module buffers the whole 16 three-bit key pairs. The key cache is organized as 32 three-bit registers. Each two registers share the same address to create key pairs.

Comparator

The comparator delivers the scrambled key with the smaller value to the "Message Alignment" module. This value is needed for the left rotation.

Encryption Module

The encryption module has a simple architecture of mere multiplexers that choose between the bits in the hiding vector and the ones in the scrambled plaintext stream. The selects of the multiplexers are controlled by the scrambled key pair. As a result the replacement procedure can be performed. The output cipher text is 16-bit large and is generated every two cycles. To simplify the handshaking protocol between this module and any other communication module, a ready signal is generated on every stable output.

Random Number Generator

The output cipher text should be scrambled as much as possible; therefore the scrambled plaintext bits are hidden inside a random string that is called hiding vector. The "Random Number Generator" module generates this hiding vector. This module is designed using Linear Feedback Shift Register (LFSR) with primitive feedback polynomial to ensure a maximal-length sequence of random numbers.

IV. SIMULATION

The simulation of the designed micro-architecture is performed on the Logic Simulator of the Xilinx Foundation F2.1i. The first operation performed by the MHHEA processor is loading the 32-bit plaintext during the "LMSG" state. Figure 5 depicts this operation. In this case, the input plaintext is "ABCD1234" and the "LMSG" state is active. The "LKey" state, shown in Figure 6, is the successive state to the "LMSG" state. Key pairs are loaded in parallel since they are pointed to by the same address.

In the following state in Figure 7, namely the "LMSGCACHE" state, the least significant 16 bits are placed in the buffer inside the "Message Alignment" module.

32-bit Plaintext

"LMSG" State An example for the rotation and encryption is shown in Figure 8. The part of the key with the smaller value is, in this case, equal to zero. The other part is equal to "3". The smaller part is XOR-ed with the zero to the third location in the upper byte of the random vector V, resulting in the value "2". Adding this value to the difference between the two initial key parts, results in the second key part value, namely "5". Therefore, rotating the message twice to the left, renders the message value equal to "2341" after being "48D0". The message bits that should be encrypted are positioned from the second to the fifth location. Thus, the message is aligned with the replacement locations. Note that the location zero refers to the least significant bit. The message bits in this range of locations are equal to the hexadecimal value zero. The lower byte of the hiding vector is equal to "06". Note that in Figure 8, the lower byte of the hiding vector or the random vector is referred to as "Coverr7". The bits from the second to the fifth location in the random vector are to be replaced by the message bits in the corresponding locations to produce the cipher text equal to "CA02". The message is then rotated M times to the right, where M is equal to the larger key value plus one as mentioned before. In this case, M is equal to six. Hence, the message value "2341" is rotated to the right six times to become "048D". In this way, the least significant bits of the message buffer are always the bits yet to be encrypted.

V. IMPLEMENTATION RESULTS

We have used Spartan II FPGA family to implement our design. A comparison between our micro-architecture and other encryption micro-architectures is performed through The term CLB is the abbreviation for "Configurable Logic Block". In appendix B we provide a summary of the timing reports. These reports were taken for a 32-bit block plaintext and a cipher text of 16 bits. The details of these reports are as shown in Appendix A. Moreover, the floor plan of the design is also provided.

VI. SUMMARY AND CONCLUSION

Steganography and cryptography are the essential elements of today's data communication security.

Cryptography is used to scramble the data, whereas steganography is used to hide the data. The MHHEA algorithm bridges the gap between these two elements of data security. In this work, we have introduced a microarchitecture that is based on this algorithm for packet-level encryption. The special features of this micro-architecture can be summarized as follows:

A construction that effortlessly allows the user's data block to be varied. Subsequently, the register size holding this block can be optimized depending on the implementation technology and the communication channel data rate.

A design that allows the size of the hiding vector registers to be varied. Accordingly, a variable level of data security can be obtained. Increasing the register size leads to a higher security level. Moreover, it extends the key space with added security. The higher order byte is employed to scramble the hiding locations. Moreover, the message is scrambled using one of the key integers. This approach eliminates chosen-plain text attacks using a constant value.

A parallel bit replacement approach that improves the overall throughput, and overcomes the security limitations encountered by a dependency between the throughput and the nature of the key. The micro-architecture throughput is of the order of 106 Mbps which is quite satisfactory for most of today's high speed networks. With a slight modification of the selected key, one can use the micro-architecture for sequentialtype steganography. Moreover, if the random vector is loaded with multimedia cover data, one can immediately realize that the microarchitecture is used for hiding as well as scrambling data. This micro-architecture allows the user to choose between steganography and encryption by selecting the appropriate input without any changes to the hardware. Consequently, we have bridged the gap between cryptography and steganography.

This micro-architecture can also be combined with the Steganographic Shuffler (STS), shown in [START_REF] Saeb | Design and Implementation of a Secret Key Steganographic Micro-Architecture Employing FPGA[END_REF], for shuffled-type steganography.

As shown in Table 1 and Figure 9, the microarchitecture provides a clear advantage when compared with other implementations. It holds the highest functional density, if we exclude the YAEA algorithm. Without a doubt, different algorithms have different degrees of security. However, we have demonstrated that with proper adaptation of the algorithm to hardware implementations, one can arrive at higher degrees of functional density and overall better performance. The complementary nature between Cryptography and Steganography is illustrated in this work with a modified micro-architecture that can be used for both techniques. Based on the given comparison, we have demonstrated that the proposed micro-architecture shows clear performance dominance, if we exclude the variations in security levels, in data security applications of today's high speed networks.

Figure 2 :

 2 Figure 2: The substitution procedure.

Figure 3 :

 3 Figure 3: Message alignment using circulate left and circulate right.

Figure 5 :Figure 6 :

 56 Figure 5: Simulation of 32-bit plaintext loading.

Figure 7 :

 7 Figure 7: Simulation of 16-bit message buffer loading.

Figure 8 :

 8 Figure 8: Simulation of encryption process.

Figure 9

 9 in Appendix A. This comparison demonstrates the dominance of the discussed algorithm and our proposed micro-architecture. This is based on the data throughput and the consumed area. The functional density is computed by the following equation: the Key KN i,2 =KN i,1 +(K i,2 -K i,1 )=2+(3-0)=5 "Encr" State M Value after Right Rotation Cipher Text V[15:6] || (ML[5:2] xor K i,1 ) || V[1:0] Ready Signal Key Part with the Smaller Value K i,1 =0 "Circ" State Scrambled Part of the Key KN i,1 =K i,1 xor V[K i,2 +8:K i,1 +8] =000 b xor 010 b = 2 d

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgement

The authors would like to thank the reviewers for their numerous and helpful comments. The close scrutiny and constructive observations have greatly improved the final version of this paper.

APPENDIX A

The following table [START_REF] Saeb | A Microarchitecture Implementation of YAEA Encryption Algorithm Utilizing VHDL and FPGA Technology[END_REF], [START_REF] Saeb | A Microarchitecture Implementation of YAEA Encryption Algorithm Utilizing VHDL and FPGA Technology[END_REF], [START_REF] Trimberger | A 12 Gbps DES Encryptor/Decryptor Core in FPGA[END_REF], [START_REF] Goodman | An Energy -Efficient Reconfigurable Public-Key Cryptography Processor Architecture[END_REF], [START_REF] Dandalis | A Comparative Study of Performance of AES Final Candidates Using FPGAs[END_REF], [START_REF] Patterson | A Dynamic FPGA Implementation of the Serpent Block Cipher[END_REF] and accompanying chart provide a comparison of some of the algorithms' FPGA implementations. We propose a figure-of-merit that is equal to the throughput divided by the area consumed in realizing this architecture. A chart is given below that demonstrates this figure-of-merit for some of the cited algorithms.

Implementation reports

In this appendix, we provide the details of the implementation reports as they were made available by the Xilinx CAD software.

Design Information

Target


R Pradeep

S Vinay

Dr Sanjay Burman

V Kamakoti

FPGA based Agile Algorithm-On-Demand co-processor

With growing computational needs of many real-world applications, frequently changing specifications of standards, and the high design and NRE costs of ASICs, an algorithm-agile FPGA based co-processor has become a viable alternative. In this article, we report about the general design of an algorith-agile co-processor and the proof-ofconcept implementation.

Introduction

Co-processors were initially designed to reduce the computational overload on the host processors, thus scaling-up the latter's performance [START_REF] Paar | An Algoritm Agile Co-Processor based on FPGA[END_REF] [START_REF] Dandalis | An Adaptive Cryptographic Engine for IPSec architecture[END_REF]. Typically, co-processors, such as graphics co-processors, are application-specific.The computations they perform are predetermined.

In this paper,we provide a single chip solution for an agile co-processor that can execute any one of a set of functions on-demand by the host computer. The idea here is to give this co-processor additional agility by making it capable of executing many such computationally intensive functions.

Architecture

Co-processor architecture

This section gives an overview of the proposed architecture of the FPGA based Agile Algorithm-On-Demand coprocessor. Our proposed architecture consists of three major blocks: A block diagram of the proposed architecture is shown in Figure 1. The entire system sits on a PCI card which can be fitted to a standard desktop computer / work-station / server. The system can be operated by issuing instructions to the microcontroller through the PCI.

Memory

The compressed configuration bit-streams of the functions that are to be implemented on the FPGA are downloaded on to the ROM from the host PC. In addition, the ROM, contains records that holds the start address of each function's compressed configuration bit-stream on the ROM, its size and the input/output size of the functions. The compressed configuration bit-streams are loaded from one end of the ROM while the record table is populated from the other end of the ROM. The memory has an interface only with the microcontroller. The microcontroller utilises the records in the ROM to access the compressed bit-streams.

Microcontroller

The microcontroller is interfaced with the host PC(through the PCI), the ROM, the local RAM, the configuration module, the data input module and the output collection module. The microcontroller is responsible for accessing the compressed configuration bitstreams from the ROM and passing them to the configuration module. The microcontroller also takes inputs for the functions from the host through the PCI and stores them in the local RAM. It then passes these inputs to the data input module. Similarly the microcontroller collects the outputs from the functions through the data collection module and stores them in the local RAM before passing them back to the host PC. The configuration module decompresses the compressed bit-stream window by window and passes the configuration bit-stream to the FPGA to configure it. The data transfer to and from the FPGA takes place through the data input/output modules. Each data transfer is a multiple of the width of the interface bus as specified by the function record present in the ROM.

Partially reconfigurable FPGA chip

Parital reconfiguration of an FPGA is a method by which only a portion of the logic space on the FPGA is reconfigured. The configuration of the remaining portion of the FPGA is untouched and hence, the functions present in the untouched logic space may be accessed for execution. This parital reconfiguration of the FPGA facilitates the swap-in and swap-out of functions, from the FPGA, on-demand.

On-demand Algorithm

On-demand algorithms deals with the execution of a particular algorithm, from a bank of algorithms. When the host requests the execution of a particular algorithm, on some specified inputs, to the co-processor, the micro-controller is responsible for configuring the FPGA with that relevant configuration bit-stream if the function is not already present on the FPGA.

When the FPGA is programmed with the configuration bit stream of a particular algorithm, if occupies a certain number of Frames 1 . Thus, an algorithm's logic may occupy either a set of contiguous frames or a set of non-contiguous frames on the FPGA , as predetermined by the area constraints on the FPGA during the programming of the same. When a new algorithm is to be executed, the configuration bit stream of this algorithm may give rise to logic which may fit in the set of free frames, specified by the Free Frame List. The micro-controller's mini OS maintains a Frames in the FPGA which are currently not used to realize any logic and are thus potentially programmable without any intervention to the functions currently being executed, called the Free Frame List. However, if the Free Frame list is insufficient for the logic that the new algorithm's function is to realize, or is empty, some functions from the FPGA have to be erased so as to accommodate the logic necessary for the functions of the new algorithm whose execution has been requested by the host PC. The frames that are to be replaced is decided by the Frame Replacement Policy , which makes those frames that belong to the frequently least used Algorithm potential candidates for replacement. This set of frames may be decided by a look up in the Frame Replacement Table which gives an indication of the list of frames occupied by each algorithm present on the FPGA along with a time stamp specifying the last moment at which it was accessed. That algorithm which has the oldest time stamp provides extra frames for potential reconfiguration.

Proposed Proof-of-concept Implementation

The proof-of-concept implementation of the FPGA based Agile Algorithm-On-Demand co-processor is done using an Altera STRATIX PCI Development board [START_REF]PCI Development Kit[END_REF] and a Xilinx Virtex-II FPGA which has partial reconfigurability [START_REF]Two Flows for Parital Reconfiguration: Module Based or Difference Based[END_REF].

Conclusion

This paper presents an algorithm agile co-processor. One of the interseting open problems is to explore advanced techniques for compression that can exploit the symmetry in the CLB architectures of FPGAs and also the partial reconfigurability of FPGAs.

  partially reconfigurable FPGA device.

Figure 1 .

 1 Figure 1. A block diagram of the coprocessor

1

  Frames are a prespecified number of Logic Blocks and the relevant Switch Blocks of and FPGA

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Wayne Wolf

Multimedia Applications of Multiprocessor Systems-on-Chips

This paper surveys the characteristics of multimedia systems. Multimedia applications today are dominated by compression and decompression, but multimedia devices must also implement many other functions such as security and file management. We introduce some basic concepts of multimedia algorithms and the larger set of functions that multimedia systems-on-chips must implement.

Introduction

Multimedia systems constitue a huge application space for systems-on-chips. Multimedia underlies many common devices for entertainment and and business applications. Because these markets are so large, they require system-onchip implementations to be successful.

Multimedia algorithms are surprisingly complex. A great deal of effort has gone into algorithms that efficiently compress data, provide high image/sound quality, etc. Multimedia standards deploy combinations of many types of algorithms to obtain high-quality results.

Multimedia systems are also complex beyond the needs of the algorithms themselves. A multimedia device must perform many other functions-communications, file management, security, etc.-in order to perform all its duties. These added duties must also be supported by systems-onchips for multimedia.

In the next section, we will briefly survey the types of applications that may see implementation in multiprocessor systems-on-chips. We will then look at video and audio compression, the dominant multimedia applications today. We will briefly consider content analysis, an emerging application. We will then look at digital rights management and other functions that must be performed by multimedia systems.

Multimedia Applications for Systems-on-Chips

Systems-on-chips designed specifically for multimedia are targeted at consumer applications, where cost and power are critical. Most of today's consumer multimedia applications are based on compression. Even within that relatively constrained algorithmic domain, consumer multimedia devices cover a broad range of cost/performance/power points:

• multimedia-enabled cell phones;

• digital audio players;

• digital set-top boxes;

• digital video recorders;

• digital video cameras.

Digital video recorders are an example of a multimedia analysis system-they may, for example, skip commercials or skip to the next scene based upon an analysis of the content. We should expect to see a wider range of analysis-oriented products as more computational power becomes available and consumers feel the need to use tools to manage their content.

Video compression algorithms symmetric and asymmetric applications. A symmetric compression system is designed to require roughly equal computational power from both the sender and receiver. Videoconferencing is a classic example of this scenario, in which each terminal must both transmit and receive. Asymmetric systems put more effort into encoding to simplify the decoder. Broadcast systems, in which a complex transmitter supplies content to many simpler receivers, is an example of an asymmetric system.

Video compression is lossy encoding---information is removed and the reconstructed signal is not identical to the original signal. The structure of a video encoder is shown in Figure 1. Modern video compression systems rely on three major techniques [START_REF] Barry | Digital Video: An Introduction to MPEG-2[END_REF]:

• The discrete cosine transform (DCT) is used to select details to remove.

• Lossless encoding, particularly Huffman-style encoding, is used to remove entropy from the final data stream sent to the decoder.

• Motion estimation and compensation are used to determine the representation between frames

The first two are also used in image compression, while the third is unique to video.

The discrete cosine transform helps the encoder identify information in the frame to be thrown away. It is a frequency transform with the advantage that a 2-D DCT can be computed from two 1-D DCTs. The DCT itself does not fundamentally reduce the amount of information, but it does separate that information into spatial frequencies. The higher spatial frequencies represent finer detail that is eliminated first.

Motion estimation and compensation allow one frame to be described relative to another. Motion estimation compares part of one frame to a reference frame and determines what motion would cause the selected part to appear in the reference frame. Motion compensation at the receiver then applies that motion vector to reconstruct the frame. The receiver must hold the reference frame in its memory but motion estimation/compensation greatly reduce the number of bits required to represent the video sequence.

Wavelets are a frequency representation that has come into common use in the past several years. Wavelets represent the frequency content hierarchically and do not suffer from the edge artifacts common to DCT-based encoding. Wavelets been incorporated into JPEG2000 for image encoding.

One problem with the multiplicity of standards is transcoding. Since different devices may use different compression standards, content must be recoded to be used on a different device. Because encoding is lossy, each generation of transcoding reduces image quality.

Audio Compression

The GSM cellular telephony standard uses an audio compression method called Regular Pulse Excitation-Long Term Predictor (RPE-LTP). This method uses a fairly simple model of the voice to encode speech. Speech is often divided into two types of sounds: voiced, which is periodic; and unvoiced, which has broader frequency content. These two types of sound can be generated filtering a combination of glottal resonance and noise. The RPE-LTP encoder generates filter coefficients that can be used at the receiver to generate the required sound from the combination of these two sources.

The well-known audio standard MP3 is shorthand for MPEG-1 Layer 3; the MPEG-1 standard [START_REF]Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1[END_REF] included three layers of audio compression, of which Layer 3 is the most sophisticated. MPEG audio compression methods are best thought of in terms of hearing rather than sound generation as with RPE-LTP.

The structure of an MPEG-1 audio encoder is shown in Figure 2. MP3 uses a combination of subband coding and a psychoacoustic model to compress the audio stream. The psychoacoustic model, because it is relies on the characteristics of the human auditory system, it is not limited to speech. A key psychoacoustic mechanism exploited by compression is masking-when one tone is heard, followed by another tone at a nearby frequency, the second tone cannot be heard for some interval. Human experimentation has determined what time and frequency combinations will be masked. The encoder can eliminate masked tones to reduce the amount of information that is sent to the decoder.

Other standards for audio compression include Dolby Digital (TM), dtx, (TM), and Ogg Vorbis.

Content Analysis

Content analysis tools use characteristics of the multimedia material to classify the material either as a whole or into its constituent components. As consumers' collections of multimedia content grow, content analysis is becoming increasingly popular as a way to help manage that content.

Audio content analysis has been used to categorize and search for music. Algorithms have had some success in categorizing music into categories and identifying salient features of the music. That information can then be used to recommend similar pieces of music. This type of analysis is generally conducted off-line on a server.

Simple forms of video content analysis has been implemented in consumer devices. The Replay (TM) digital video recorder, for example, automatically identifies com-FIGURE 2. The structure of an MPEG-1 audio encoder. mercials and skips them. Replay uses black frames between programs and commercials to identify television. Early VCR add-ons identified commercials using the color burst, under the assumption that many movies on broadcast TV were black-and-white while the commercials were in color. A number of research groups have developed algorithms that can parse various types of television content into segments. Such algorithms would allow a viewer to skip an interview segment, for example, and move into the next part of the program.

Digital Rights Management

Digital rights management (DRM) encompasses all the operations necessary to enforce copyright and license agreements. Digital rights management uses encryption as a tool but it affects the system architecture from user interface to file management.

The DRM system enforces a set of rights that are defined relative to users and to content. Rights may take a number of forms:

• The ability to play certain titles.

• The number of times that a title may be played.

• The right to play a title on more than one device.

• The time period during which the title may be played.

The DRM system may require access to the Internet to be effective. In other cases, DRM may hold rights markers that can be updated over the Internet but do not require a connection for verification.

The playback device must be able not only to perform the authorization transaction but also to play back the content in such a way that the authorizations are not easily subverted. For example, a playback device may be architected to provide only analog output at the pins to prevent direct copying of unencoded digital content.

Support

Today's multimedia devices must support a wide variety of functions beyond the multimedia algorithms themselves:

• Multimedia cell phones must clearly provide cell phone functionality.

• Many devices must provide Internet access.

• Set-top boxes must provide program guides, pay-perview authorization, etc.

• Devices with local storage, such as personal audio players or digital video recorders, must provide file systems.

The applications of Internet access vary across devices. Some use the Internet for limited purposes, such as content access or DRM. These devices can make use of the small IP stacks that have been developed over the past several years. Other devices are intended to operate as network devices and to support a variety of transactions across the network. Network-oriented consumer devices often use Java in the upper layers to ease development and allow code to be transported across the network.

Devices with local libraries must have their own file systems. Portable MP3 players and digital video recorders are examples of devices with internal file systems. MP3enabled CD players are a particularly interesting case since the files are created outside the player. A CD/MP3 player must be able to handle a wide variety of directory structures, file names, etc. A device that creates its own files has somewhat more control over the characteristics of those files. But these file systems must still incorporate the major characteristics of modern file systems: large file sizes, nonsequential allocation of blocks, etc.

Unlike magnetic disk drives, who bundle their control with the drive, DVD recorders and players must control their drives using complex digital filters. The control requires real-time processing at high rates and the control laws are generally adapted to the particular mechanism being used.

Conclusions

Multimedia applications, such as audio and video compression, are sophisticated collections multiple algorithms. Furthermore, these applications are part of larger systems that must incorporate many features of general-purpose computing systems but at low cost and low power. We should expect both the real-time and background computations required of multimedia systems to become even more complex over the next decade.

FIGURE 1 .

 1 FIGURE 1. Structure of a video encoder.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE