Stefan Tillich
email: tillich@cs.bris.ac.uk

Mario Kirschbaum
email: mario.kirschbaum@iaik.tugraz.at

Alexander Szekely
email: alexander.szekely@iaik.tugraz.at

Implementation and Evaluation of an SCA-Resistant Embedded Processor

Keywords: Side-channel analysis, SCA countermeasures, embedded processors, iMDPL, DWDDL

Side-channel analysis (SCA) attacks are a threat for many embedded applications which have a need for security. With embedded processors being at the very heart of such applications, it is desirable to address SCA attacks with countermeasures which "naturally" fit deployment in those processors. This paper describes our work in implementing one such protection concept in an ASIC prototype and our results from a practical evaluation of its security. We are able to demonstrate that the basic principle of limiting the "leaking" portion of the processor works rather well to reduce the side-channel leakage. From this result we can draw valuable conclusions for future embedded processor design. In order to minimize the remaining leakage, the security concept calls for the application of a secure logic style. We used two concrete secure logic styles (iMDPL and DWDDL) in order to demonstrate this increase in security. Unfortunately, neither of these logic styles seems to do a particularly good job as we were still able to attribute SCA leakage to the secure-logic part of the processor. If a better suited logic style can be employed we believe that the overall leakage of the processor can be further reduced. Thus we deem the evaluated security concept as a viable method for protecting embedded processors.

Introduction

Two well-known methods for protecting cryptographic workloads on embedded processors against side-channel analysis (SCA) attacks are software countermeasures and cryptographic coprocessors with custom hardware protection. On the one hand, software countermeasures are the most flexible solution but might not address all attacks or bear a significant overhead in terms of running time or resources. On the other hand, coprocessors often only offer a limited range of functionality and inhibit even slight changes of parameters (e.g. new modes of operation). An alternative approach is the incorporation of SCA countermeasures into the processor itself in order to find a trade-off between the flexibility of software countermeasures and the protection of hardware countermeasures.

There have been several proposals for adapting processors directly in order to increase their SCA resistance. Randomized execution of programs is the basic concept in non-deterministic processors as proposed by May et al. [START_REF] May | Non-deterministic Processors[END_REF]. Regazzoni et al. [START_REF] Regazzoni | A Design Flow and Evaluation Framework for DPA-Resistant Instruction Set Extensions[END_REF] built an automated design flow for integrating custom functional units (FUs) implemented in a secure logic style into the processor. The MUTE-AES architecture proposed by Ambrose et al. [START_REF] Ambrose | MUTE-AES: A Multiprocessor Architecture to prevent Power Analysis based Side Channel Attack of the AES Algorithm[END_REF] uses a second processor to balance out the AES operations of the first with the calculation of the same operations on inverted data. The balancing of the second processor is activated and terminated automatically by detecting certain sequences of instructions and it can be used for other tasks when no cryptographic operations are performed on the first processor. Recently, additional works regarding SCA protection of processors have been published. Nakatsu et al. [START_REF] Nakatsu | Combination of SW Countermeasure and CPU Modification on FPGA against Power Analysis[END_REF] have investigated a processor modification in combination with software countermeasures for eliminating SCA vulnerabilities due to branches, addresses and intermediate values dependent on secret information. They propose to implement the ALU in a specific secure logic style (Random Switching Logic) and use masking of operands and results. Although the authors emphasize that their proposal can be applied to various operations and processor architectures, several issues regarding mask handling remain open. Barthe et al. [START_REF] Barthe | Investigation of a Masking Countermeasure against Side-Channel Attacks for RISC-based Processor Architectures[END_REF] proposed to duplicate the processor data path by adding an additional register file and pipeline registers. Data in the original data path is masked while the second data path carries the corresponding masks. Before entering the FUs, data is unmasked and the according result is freshly masked. Data in memory is protected with a "static" mask.

Protecting a processor from SCA with a combination of masking and the application of secure logic styles has first been proposed by Tillich et al. in [START_REF] Tillich | Power-Analysis Resistant AES Implementation with Instruction Set Extensions[END_REF]. The original proposal was targeted at securing a specific set of cryptographic instructions. Based on the original idea, a full security concept covering a wide range of instructions and addressing issues of hardware limitations and secure task switching was then presented in [START_REF] Tillich | SCA-Resistant Embedded Processors-The Next Generation[END_REF]. As this work was conducted in context of the so-called Power-Trust project, we will refer to this security concept as the Power-Trust security concept in the remainder of this paper. The work of [START_REF] Tillich | SCA-Resistant Embedded Processors-The Next Generation[END_REF] also produced an FPGA prototype to validate the functionality and a preliminary SCA evaluation to demonstrate the principal protection offered by the concept (although the use of FPGA-style secure logic had been omitted).

In the present paper we present an ASIC implementation of the Power-Trust security concept based on the SPARC V8 Leon3 embedded processor. Our prototype includes several optional features proposed in [START_REF] Tillich | SCA-Resistant Embedded Processors-The Next Generation[END_REF]. For the critical portion of the processor (the so-called secure zone) we have used two different secure logic styles. Additionally, we have included a CMOS variant of the secure zone for reference. The goal of our work was threefold:

-Demonstrate the functionality and practicality of the concept.

-Test the utility of the optional features and develop possible improvements both regarding usage in software and simplification in hardware. -Evaluate the SCA resistance of the prototype in order to estimate the potential protection offered by the Power-Trust security concept.

Although we have observed huge improvements in DPA attack resistance in our practical evaluation, the use of our chosen secure logic styles has turned out to be rather ineffective (leading only to little improvements in resistance at relatively high cost). Nevertheless, we deem our results as valuable insights into the issues of practical deployment of secure logic styles.

The rest of this paper is organized as follows. The Power-Trust security concept is described in Section 2. Our ASIC prototype implementation including a description of features of the secure zone as well as details of the implementation of the logic styles on ASIC is presented in Section 3. Section 4 discusses possible improvements of the whole security concept. A detailed security evaluation and the presentation of our SCA attack results is given in Section 5, followed by analyses of the results in Section 6. Conclusions are drawn in Section 7.

Description of the Power-Trust Security Concept

SCA attacks exploit the effect specific key-dependent data has on various observable physical characteristics of a device, e.g. timing or power consumption. We will denote such data as critical data in the following. The basic assumption for the Power-Trust security concept is that each handling of critical data is a potential target for an attacker. The general term handling hereby refers to both operations on the critical data as well as the movement of it through various data flow control elements (e.g. multiplexers) and storage units. For example, in a typical modern processor critical data are not only operated upon in a number of functional units but also have to pass through various pipeline stages, feedback paths, and storage elements like pipeline registers, register files, caches and memories. All these activities are reflected in the processor's power consumption and can be ultimately exploited in a power analysis attack.

The first step for counteracting SCA attacks is to minimize the effect of the critical data on the physical characteristics. Leakage in the timing of the processor can be addressed by eliminating key-dependent branches and avoiding other potentially variable-time operations like table lookups. The use of special cryptographic instructions (instruction set extensions) is very helpful in achieving this goal without sacrificing performance. Also, elimination of table lookups is expected to go a long way in reducing leakage in the power side channel, as memory operations are usually a significant contributor to the overall power consumption.

With the help of cryptographic instruction set extensions (ISEs) it is possible to confine actual operations on critical data exclusively to the FUs of the processor, which are usually the main part of its execute stage. Any other part of the processor then just moves around critical data without transforming it.

Based on this observation, the Power-Trust security concept applies a mask to all critical data which circulates outside of the FUs. The operands entering a FU have to be unmasked and the results leaving the FU have to be masked again. Therefore, arbitrary FUs can be supported easily. This is unlike most of the previous masking solutions, which require the development of special FUs to implement non-linear operations which transform masked values and mask.

Thus, direct leakage only emanates from the FUs which are required for implementing the cryptographic algorithm. Leakage from components which handle the masks (mask storage and mask generator) could also lead to higherorder weaknesses when combined with leakage from the masked values. In order to mitigate these vulnerabilities, all these components are implemented in a secure logic style. This portion of the processor is denoted as secure zone. From its functionality and interface, the secure zone is very similar to a conventional FU, which facilitates its implementation in secure logic and its integration into the processor. Conceptually, an attacker must overcome the protection of the secure logic style3 in order to break the security of the processor.

The secure zone can only store a fixed number of masks, which determines the maximum size of the intermediate state of a cryptographic algorithm at any point in time. However, by using pseudo-randomly generated masks it is possible to store masks intermittently outside of the secure zone in a secure redundant representation. This mechanism allows to virtually extend the number of available masks and also to share the secure zone between several processes in a secure fashion. Other issues addressed in [START_REF] Tillich | SCA-Resistant Embedded Processors-The Next Generation[END_REF] are the way that masks and masked values are associated in the processor and the options for dealing with exceptional cases during runtime, e.g. when the maximum number of possible masks is reached. Those issues afford various solutions and we describe our concrete design choices in Section 3.

ASIC Prototype Implementation

Our prototype is based on the SPARC V8 Leon3 processor [START_REF] Research | GRLIB IP Library User's Manual[END_REF], which is a popular platform for academic research due to its high quality and tool support as well as its openness. It is a 32-bit embedded architecture with a large number of configuration options. Our most important enhancements are described in the following.

Features of the Secure Zone

When masked operands enter the secure zone, the processor needs a mechanism to identify the corresponding mask. Various options are possible but in our implementation we chose to introduce a custom addressing mechanism which is under explicit software control. Our reason for this choice was the huge degree of flexibility offered by this solution. Each mask and each masked value is associated with a custom 10-bit address, so that the mask and masked value with the same address belong together. As this address acts much like a register address, it is denoted as masked register address. Depending on the storage location of mask or masked value, the adjoint masked register address is handled differently.

Figure 1 depicts the different possible data representations of masked data and masks in various storage locations as well as the mechanisms used to keep the masked register address alongside them. Unmasked data only occurs in the secure zone's FUs (circled 1) and masks reside exclusively in the secure zone's mask storage unit (circled 2), where both are protected by the secure logic style (indicated by the gray shading). Masked data can circulate through the other pipeline stages, the register file, and memory (circled 3). Additionally, masks can be held in their secure redundant form in memory (circled 4). Masks and masked data must always be attached to their masked register address, so that the secure zone can associate masked data with its corresponding mask. Masked data in the pipeline stages and register file (diamond 1) are principally attached to a logical register address. A custom hardware table called Masked Register Table (MRT) then maps this logical register address to a masked register address. The masks in the mask storage (diamond 2) are held automatically alongside their masked register address. On the other hand, masked data and masks in memory (diamond 3) must have their masked register address stored explicitly with them by the software.

The advantage of this masked register addressing scheme is that it can be used to emulate several different forms of software usage of the secure zone. For example, the software can choose to never write masks or masked values out to memory. In this case, the MRT can be initialized with a fixed mapping and the logical register address of a masked value effectively determines the corresponding mask.

The instruction result coming from the secure zone must be protected by a fresh 32-bit mask. When the processor handles a sequence of such protected instructions, a fresh mask is needed in every clock cycle. Furthermore, masks must be uniformly distributed and unpredictable by an attacker. For dealing with more masks than the mask storage of the secure zone can handle internally, it is also necessary to have a secure representation of masks which allows their subsequent reconstruction.

In order to balance all these (partly conflicting) requirements with an efficient design we have implemented our mask generator as a 127-bit maximum-length LFSR. We used the pentanomial x 127 + x 87 + x 59 + x 37 + 1 as the reduction polynomial because it facilitates parallelization in both forward and reverse direction. In normal operation, the LFSR advances 32 steps per cycle in order to produce a fresh 32-bit mask.

The mask generator also keeps track of the number of steps (denoted as mask index ) it has taken from a specific initial state. In conjunction with a particular LFSR state, the mask index is a secure alternative representation of a mask. Software can read and write the LFSR state and can run the LFSR in forward or reverse direction towards a specific mask index in order to restore a mask. In a finished device, the LFSR should be seeded from a random number generator (RNG) to make the produced masks unpredictable and to prevent reset attacks. For our prototype, we did not integrate an RNG.

The secure zone can hold up to eight masks in its mask storage component. Metadata about stored mask like masked register address and mask index can be read by software. Exceptional conditions in the secure zone cause traps. Such exceptional conditions are a full mask storage, encounter of a masked operand whose mask is missing from the mask storage, and an overflow of the mask index counter in the mask generator. It is up to the software to either avoid those exceptional conditions altogether or to address them at runtime with specific trap handlers. Protected instructions of the secure zone encompass specific support for AES and ECC over GF(2 m ) as well as a range of logic operations for bit-sliced implementations.

Implementation Details

We have used the UMC 0.18 µm standard-cell library FSA0A C from Faraday [START_REF]Faraday FSA0A C 0.18 µm ASIC Standard Cell Library[END_REF] for implementation. Our original plan was to employ memory macros from this library to implement memory components like the caches. However, despite our best efforts we were unable to integrate those memory macros into our design flow within a reasonable time frame. Therefore, we used the synthesizer to infer those memory structures with flip-flops. As such inferred structures are significantly larger compared to macros, we had to reduce the size of instruction and data cache to the minimum of 1 KB each.

We have integrated secure zone blocks in three different logic styles in our prototype. We chose logic styles which are based on standard cell libraries and thus can be relatively easily implemented in a more or less automatic way but which still promised to deliver an increase in protection over CMOS. To this end we chose iMDPL [START_REF] Popp | Evaluation of the Masked Logic Style MDPL on a Prototype Chip[END_REF] and DWDDL [START_REF] Yu | Secure FPGA circuits using controlled placement and routing[END_REF]. The third secure zone was implemented in CMOS to serve as a point of reference. Software can select a specific secure zone by writing to a custom configuration register. The inputs (including the clock signal) of the other two secure zones are held at zero in order to minimize their impact on the power profile.

The improved masked dual-rail precharge logic (iMDPL) style combines the dual-rail precharge (DRP) technique, a masking technique, and it takes precautions to prevent the effect of early propagation ( [START_REF] Suzuki | Security Evaluation of DPA Countermeasures Using Dual-Rail Pre-charge Logic Style[END_REF]). The DRP technique avoids the occurrence of glitches ( [START_REF] Popp | Masked Dual-Rail Pre-Charge Logic: DPA-Resistance without Routing Constraints[END_REF]) which may significantly reduce the side-channel resistance of implementations ( [START_REF] Mangard | Side-Channel Leakage of Masked CMOS Gates[END_REF] and [START_REF] Mangard | Successfully Attacking Masked AES Hardware Implementations[END_REF]). This is achieved by introducing an evaluation and a precharge phase in each clock cycle. In the precharge phase, both wire rails of each signal are precharged. In the evaluation phase the wires switch to their corresponding values. The masking technique bypasses the need for special routing techniques of the circuitry. In [START_REF] Popp | Evaluation of the Masked Logic Style MDPL on a Prototype Chip[END_REF] it has been shown that early propagation may cause a significant side-channel leakage in a masked DRP logic style. Thus, each iMDPL gate contains an evaluation-precharge detection unit (EPDU) which tries to prevent the premature evaluation/precharge of the gates.

A basic iMDPL AND gate is built with two three-input majority (MAJ) gates. MAJ gates are part of standard cell libraries, so there is no need to design and verify special security cells in the library. The iMDPL style can thus be implemented by a more or less straight forward search and replace processing step after design synthesis. Each iMDPL gate processes the masked values a m , b m (ā m , bm ) and the mask value m ( m). IMDPL is based on boolean masking, i.e. a m = a ⊕ m, and the mask value m is derived from a 64-bit maximum-length LFSR counter [START_REF] Alfke | Xilinx Application note on Shift Registers and LFSR counters[END_REF] in each clock cycle.

The area of a pure iMDPL implementation is usually increased by a factor of approximately 20. In our case, the area of the iMDPL secure zone is 406 kGE, compared to 19 kGE of the secure zone implemented in unprotected CMOS logic, which corresponds to a factor of 21. The whole Leon3 processor without any secure zones has 582 kGE 4 . This results in a total area overhead of approximately 64% compared to a pure CMOS implementation of the SPARCV8 embedded processor.

We implemented iMDPL with knowledge that the security of the logic style might suffer from unbalanced wires ( [START_REF] Schaumont | Masking and Dual-Rail Logic Dont Add Up[END_REF], [START_REF] Tiri | Changing the Odds against Masked Logic[END_REF]). Recent research has shown that the mask value in an iMDPL circuit can most probably be discovered and that also other wires within the circuitry might be affected by imbalances. Nevertheless, investigations of an ASIC implemented in iMDPL have shown that the logic style is able to increase the SCA resistance ( [START_REF] Kirschbaum | Evaluation of a DPA-Resistant Prototype Chip[END_REF]).

Double Wave Dynamic Differential Logic (DWDDL) [START_REF] Yu | Secure FPGA circuits using controlled placement and routing[END_REF] is an enhancement of WDDL [START_REF] Tiri | A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation[END_REF] with the goal of solving its inherent balancing issues. Whereas WDDL requires techniques of balanced routing of its differential signals, DWDDL duplicates the layout of a normally routed WDDL circuit and inverts both the block's input as well as the inputs and outputs of all logic cells 5 . Thus, for each differential signal, a bit flip at one of the wires in the first WDDL block is counterbalanced by a bit flip on the other wire of this differential signal in the second WDDL block.

The area of the DWDDL secure zone is 260 kGE, which represents a factor of 14 compared to the secure zone implemented in unprotected CMOS logic. With respect to the whole Leon3 processor, the total area overhead is approximately 40%, which represents a relatively moderate increase in area in return for a significantly increased SCA resistance.

DWDDL has originally been proposed exclusively for use in FPGAs, as they allow to invert the functionality of logic cells simply by changing the contents of their lookup tables (LUTs). In case of ASIC implementations a swapping of cell functionality (i.e. substituting an AND cell with an OR cell) would result in significant changes in the circuitry due to differences in the structure of the cells. This would implicate differences between the two WDDL circuits and would hence introduce imbalances in the power consumption of the two circuits. We have developed a simple way to overcome this issues and to adopt DWDDL for ASIC implementations. Our approach is based on the observation that threeinput MAJ gates can be seen as configurable two-input AND/OR gates (inputs a and b), where the value of the third MAJ input c determines the functionality, see Figure 2.

We started with the design synthesis utilizing conventional AND and OR gates. Afterwards we implemented WDDL based on MAJ gates by means of a search and replace processing step in which the standard AND and OR cells are replaced by corresponding WDDL cells (based on MAJ cells) and the whole netlist is transformed to a dual-rail circuitry. The third input of each MAJ gate a b c q a b c q 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 MAJ as AND MAJ as OR MAJ q a b c is hooked up to a global configuration signal. This WDDL netlist is then placed and routed. The resulting layout is duplicated and the second instance of the WDDL block is hooked up to the inverted inputs and the inverted configuration signal. This way we achieved two identically placed and routed WDDL circuits with a globally configurable cell functionality. We are aware that such a separation of the two WDDL circuits on the chip opens the door for localized EM measurements and thus represents a potential vulnerability.

A critical point for the SCA resistance of the DWDDL implementation is the timing of the two WDDL circuits. The propagation of the evaluation and precharge waves through the circuits has to start as exact as possible in both circuits, deviations would result in early propagation which would significantly affect the SCA resistance. Thus, we implemented the transformation cells CMOStoWDDL in a way that the clock signal acts as a trigger for the precharge/evaluation phases. Internally, the WDDL circuits are operated with a doubled clock speed due to the master-slave flip-flop structure implemented [START_REF] Tiri | A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation[END_REF]. So we have two clock domains in the whole design: (1) the standard clock signal for all CMOS circuits and the iMDPL secure zone, which also serves as a precharge/evaluation signal and (2) a double-speed clock signal for the two WDDL circuits. We also had to take precautions when implementing the transformation cells for leaving the dual-rail circuit. Similar to inputs in the CMOStoWDDL cells, in case of WDDLtoCMOS the sensitive outputs of both WDDL circuits have to be synchronized to prevent a data leakage. Thus, we added a register stage to the output transformation which is synchronized by the clock signal.

Known weakness in DWDDL: Before the implementation of DWDDL we performed a theoretical investigation. Unfortunately, at this point we made a mistake and evaluated an incorrectly designed DWDDL cell: we correctly inverted the input signals of the complementary WDDL cell but we missed to exchange the logic gates AND and OR of the complementary WDDL cell. Our mistake disguised the occurrence of early propagation in DWDDL and resulted in an incorrect behavior of the complementary WDDL circuit. We recognized the mistake only shortly before the tape-out date, where we still had the time to correctly exchange the logic gates but we did not have enough time to switch to another logic style or to implement and improved version of DWDDL.

Possible Improvements

Experience with software development using the various features of the prototype has led to a number of possible improvements. Most of the features are intended to support manual software development for the enhanced processor. However, we expect that software generation should ultimately be pushed off to the toolchain in order to minimize the risk of programming errors. In such a case, many of the extra features of the secure zone could be simplified or eliminated in order to reduce its size and cost.

The biggest issue is the use of masked register addresses to associate masked data and masks. This leads to a high degree of flexibility for software which allows to move masked data freely between memory and any register. However, as allocation of masked data is expected to be ultimately handled by the toolchain, this flexibility does not seem to be required. Masked register addresses require elaborate address lookup logic and the inclusion of the MRT. By using the already present logical register address as mechanism to associate masked data and masks, the address lookup logic can be greatly simplified and the MRT can be eliminated altogether. This implies that masked data must be loaded back into the same logical register from which it has originally been stored to memory. However, we do not expect this to be a problem for the software.

The hardware traps are mainly intended for a very flexible but also rather slow mode of execution. This mode is intended for software developers who have little knowledge about the characteristics of the secure zone but still want to write code manually. By removing this mode of execution, the hardware trap mechanism can be simplified or even eliminated altogether.

Mask indices are maintained by the mask generator (i.e. its current "step" count) and the mask storage (i.e. the "step" count of each mask) with the sole purpose of having a secure redundant representation of masks. If the mask storage of the secure zone is deemed large enough to support all required cryptographic algorithms, these mask indexing mechanisms could be removed in order to reduce hardware overhead.

A more minor issue are the management instructions to read out metadata from the mask storage. In our prototype, it is not possible to get the metadata corresponding to a particular mask directly, which makes it necessary to read out all metadata and look for the desired entry. This problem could be easily remedied by a slight modification of the functionality of the management instructions.

Security Evaluation

We have compared various implementations of a single round of AES by means of classical correlation-based DPA attacks using Hamming weight (HW) and Hamming distance (HD) as power models. A standard software AES using only native SPARC V8 instructions and incorporating an S-box lookup table serves as our baseline version (SW-AES). Then we have the use of basic AES ISEs, which eliminate the need for table lookups (AESREF). Furthermore, we implemented AES on each of the three secure zones (SZ CMOS, SZ IMPDL, SZ DWDDL). We defined a DPA attack as successful if at least 9 of the 16 key bytes could have been revealed. We assumed that the remaining 7 key bytes can be revealed by a brute force attack within reasonable time. Our approach is based on common bruteforce attacks on the 7-byte key of DES ( [START_REF] Kumar | How to Break DES for 8,980[END_REF] and [START_REF] Kumar | Breaking Ciphers with COPACOBANA -A Cost-Optimized Parallel Code Breaker[END_REF]). Hence, for our estimations of the number of required power traces we used the ninth-highest correlation value of all correctly revealed key bytes.

In case of SW-AES we performed 10 000 measurements. According to our attack success metrics and according to the rule-of-thumb formula from [START_REF] Mangard | Power Analysis Attacks -Revealing the Secrets of Smart Cards[END_REF] (Chapter 6.4.1) the number of required power traces to distinguish the correct key hypothesis from the incorrect ones is 263 (key byte 9 has the ninth-highest correlation value of 0.315). The SW-AES implemented in unprotected CMOS is highly vulnerable as expected. Due to the involvement of the MixColumns operation in the SW implementation, attacks using the HD power model would have resulted in rather expensive attacks based on 4 key bytes at once, and hence, these attacks have been omitted. Our results show that the AESREF implementation offers a very slightly increased protection compared to SW-AES. The number of required traces of the ninth-highest correlation value (0.0319) in case of HW is 27 200. The attacks using a HD power model resulted in significantly higher correlation values around 0.2, which corresponds to 700 required power traces.

We received very interesting results from the SZ CMOS: it turned out that the secure zone implementation already has a significant effect on the SCA resistance, even without implementing the secure zone itself in a special logic style. According to our attack success metrics the number of required power traces in case of SZ CMOS is around 130 000. The results of the attacks on the SZ IMDPL show a further increase in SCA resistance: around 260 000 power traces are required to distinguish the ninth-highest correlation value. In case of SZ DWDDL it turned out that the lower 16 bits of the four 32-bit words processed can not be clearly distinguished in a HW attack. As only eight key bytes could be revealed, we used the eighth-highest correlation value of 0.0064 in this case, which corresponds to 675 000 required power traces. By means of an HD attack on SZ DWDDL, all 16 key bytes could have been revealed: the highest correlation value corresponds to a number of required power traces of approximately 5 200 000.

The results lead to the following conclusions: it shows that the confinement of leaking operations to a small part of the implemented processor significantly enhances the SCA resistance, even though the confined part is not implemented in a secure logic style. The results also show that the implemented logic styles still have an information leakage, therefore we can not conclusively show that the overall security will increase further with a reliably secure logic style. Nevertheless, the assumption that the elimination of the leakage in the confined part of the processor would also have a positive effect on the overall security still seems plausible.

Analysis of the Results

The results of the DPA attacks using Hamming weight power model are summarized in Table 1, the results using Hamming distance power model are summarized in Table 2.

The AES ISEs in the FU of the AESREF implementation are identical to the ISEs in the FU of the SZ CMOS, i.e. the only difference between these two implementations is the masking of the result values leaving the SZ CMOS. Hence, we assume that the significant HD leakage of AESREF is related to storing the unmasked results in the register file of the processor. In other words, the HD leakage of the SZ CMOS is prevented due to the masking of the output operands.

The results of the SZ IMDPL support the assumptions that routing imbalances within the circuitry limit the effectiveness of the logic style to a certain degree. Imbalances between complementary wires in a DRP circuit obviously cause signal-dependent differences in terms of power consumption as well as in terms of signal timings. In a conventional digital design which contains considerably large combinational structures such imbalances may influence the overall power consumption to a certain degree, which results in a data leakage.

Unfortunately, at this stage there are several questions unanswered which are marked for future work. During our evaluations it turned out that we are not able to fully resolve the open questions solely by means of measurements. It further turned out that we cannot perform logic simulations of the whole Leon3 processor within a reasonable time. Hence, we plan to perform simpler simulations of individual submodules in order to be able to investigate the processes within the Leon3 processor and the secure zones in more detail.

The proposal of Barthe et al. [START_REF] Barthe | Investigation of a Masking Countermeasure against Side-Channel Attacks for RISC-based Processor Architectures[END_REF] is similar to the Power-Trust security concept: it tries to confine the leaking operations to a specific portion of the processor. However, protection of memory appears relatively weak as a constant mask added to all words is in principle not expected to deliver good protection against DPA attacks. The authors have performed practical evaluation of an FPGA implementation of an enhanced MicroBlaze clone. They used EM measurements at a number of points of the device. However, analysis of the acquired traces seems to have been done with classical difference-of-means DPA, which makes it hard to accurately estimate the minimal required number of traces for a successful attack from the resulting difference-of-means trace. Barthe et al. concluded that their proposal significantly reduces leakage from most parts of the pipeline but that leakage from the unprotected combinational logic in the FUs remains.

Conclusions

In this paper we presented an ASIC implementation of the Power-Trust security concept. Our prototype is based on the SPARC V8 Leon3 processor and has been produced in a 0.18 µm process technology from UMC. We demonstrated the functionality and practicality of the security concept and we evaluated the SCA resistance of the ASIC prototype.

The results have shown that the use of basic AES ISEs, which eliminate the need for table lookups, already has a positive effect on the SCA resistance of an implementation. A further improvement of the SCA resistance has been achieved by the secure zone concept where critical operations are confined to a small part of the processor and all data outside of the secure zone is strictly masked. Even if the secure zone itself is not implemented in a secure logic style (as it is proposed by the Power-Trust security concept), the SCA resistance is significantly increased. A further increment in security is provided if the secure zone is implemented in a special logic style. Unfortunately, neither iMDPL nor DWDDL provide a very high level of SCA resistance, but our results indicate that the efficiency of the Power-Trust security concept could be further increased when implementing the secure zone in a well-performing logic style. Furthermore, restricting the implementation of a special logic style only to a small part of a processor tremendously reduces the overhead in terms of area and power which is associated with most of such logic styles.

Fig. 1 :

 1 Fig. 1: Data representation and addressing in enhanced processor.

Fig. 2 :

 2 Fig. 2: Using a MAJ gate as configurable AND/OR gate. The gate functionality can be controlled by input c of the MAJ gate.

Table 1 :

 1 Correlation analysis results for the measurement series (Hamming weight model); correlation values marked with an asterisk indicate unsuccessful attacks; correlation values in bold represent the ninth-highest value (if at least nine key bytes could have been discovered).

	Target SW-AES AESREF SZ CMOS SZ IMPDL SZ DWDDL
	Byte 1 0.227	0.0164*	0.0111	0.0066	0.0028*
	Byte 2 0.298	0.162	<0.003*	0.0177	0.0025*
	Byte 3 0.574	0.0244	0.0264	0.0103	0.0121
	Byte 4 0.135	0.177	0.0177	0.0289	0.0243
	Byte 5 0.230	0.0334	0.0146	0.0067	0.0024*
	Byte 6 0.697	0.0162*	0.0074	0.0195	0.0018*
	Byte 7 0.672	0.0878	0.0261	0.0080	0.0064
	Byte 8 0.178	0.0294	0.0213	0.0289	0.0120
	Byte 9 0.315	0.0222	0.0085	0.0059	0.0026*
	Byte 10 0.564	0.0355	0.0067	0.0166	0.0018*
	Byte 0.511	0.0240	0.0228	0.0078	0.0091
	Byte 12 0.556	0.1296	0.0192	0.0268	0.0114
	Byte 13 0.409	0.145	0.0050	0.0062	0.0028*
	Byte 14 0.294	0.0201	0.0045*	0.0181	0.0019*
	Byte 15 0.452	0.168	0.0237	0.0084	0.0155
	Byte 16 0.113	0.0319	0.0240	0.0279	0.0098
	Target	AESREF SZ CMOS SZ IMPDL SZ DWDDL
	Byte 1 → 5	0.184	<0.003*	<0.002*	0.0019
	Byte 3 → 7	0.211	<0.003*	<0.002*	0.0019
	Byte 5 → 9	0.184	<0.003*	<0.002*	0.0020
	Byte 6 → 10 0.200	<0.003*	<0.002*	0.0023
	Byte 7 → 11 0.212	<0.003*	<0.002*	0.0021
	Byte 8 → 12 0.221	<0.003*	<0.002*	0.0023
	Byte 9 → 13 0.184	<0.003*	<0.002*	0.0017
	Byte 10 → 14 0.201	<0.003*	<0.002*	0.0019
	Byte 11 → 15 0.214	0.0314	<0.002*	0.0021
	Byte 12 → 16 0.221	<0.003*	<0.002*	0.0021
	Byte 14 → 2 0.201	<0.003*	<0.002*	0.0017
	Byte 16 → 4 0.222	0.0239	<0.002*	0.0021

Table 2 :

 2 Correlation analysis results for the measurement series (Hamming distance model); correlation values marked with an asterisk indicate unsuccessful attacks.

Either by attacking the unmasked critical data in the secure zone or with a higherorder attack on the masked values and their masks in the secure zone.

The area of

kGE of the Leon3 processor includes everything except the three secure zones. Note the fact that we implemented the chip using inferred memory structures instead of smaller memory macros. Subtracting the inferred memories (488 kGE) and some conventional AES ISEs (6 kGE), the size of the bare processor is about 88 kGE.[START_REF] Kirschbaum | Evaluation of a DPA-Resistant Prototype Chip[END_REF] In practice, this means that AND gates become OR gates and vice versa.

Acknowledgements. The research described in this paper has been supported by the Austrian Science Fund (FWF) under grant number P22241-N23 ("Investigation of Implementation Attacks"), by EPSRC grant EP/H001689/1, and, in part by the European Commission through the ICT Programme under contract ICT-2007-216676 ECRYPT II. The information in this document reflects only the author's views, is provided as is, and no guarantee or warranty is given that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.


Erich Wenger
email: erich.wenger@iaik.tugraz.at

Mario Werner
email: m.werner@student.tugraz.at

Evaluating 16-bit Processors for Elliptic Curve Cryptography

Keywords: Elliptic Curve Cryptography, ECC, Prime Field, MSP430, PIC24, dsPIC, Assembler Optimization

In a world in which every processing cycle is proportional to used energy and the amount of available energy is limited, it is especially important to optimize source code in order to achieve the best possible runtime. In this paper, we present a side-channel secure C framework performing elliptic curve cryptography and improve its runtime on three 16-bit microprocessors: the MSP430, the PIC24, and the dsPIC. To the best of our knowledge we are the first to present results for the PIC24 and the dsPIC. By evaluating different multi-precision and fieldmultiplication methods, and hand-crafting the performance critical code in Assembler, we improve the runtime of a point multiplication by a factor of up to 5.41 and the secp160r1 field-multiplication by 6.36, and the corresponding multi-precision multiplication by 7.91 (compared to a speed-optimized C-implementation). Additionally, we present and compare results for four different standardized elliptic curves making our data applicable for real-world applications. Most spectacular are the performance results on the dsPIC processor, being able to calculate a point multiplication within 1.7 -4.9 MCycles.

Introduction

Public-key cryptography is an active research area with a lot of applications. The applications range from desktop computing, over (wireless) smart cards down to low-energy sensor networks. On desktop computers one can use special instructions or graphic processors in order to implement asymmetric cryptography. Even nowadays mobile phones are equipped with powerful 32-bit processors making the job of implementing public-key cryptography easier. However, there are a lot of circumstances which call for cheap, energy saving, and fast solutions.

Especially applications utilizing small, embedded processors are interesting for elliptic curve cryptography (ECC). An ECC implementation for such a microprocessor must be resource-conscious, aware of practically dangerous power, timing, and fault attacks and still deliver a runtime, which is fast enough for realworld applications. Additionally, many applications require the use of standard-ized elliptic curves [START_REF]AMERICAN NATIONAL[END_REF][START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF][START_REF]3: Digital Signature Standard (DSS)[END_REF] that exceed a defined security threshold. Previous work [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF][START_REF] Scott | Optimizing Multiprecision Multiplication for Public Key Cryptography[END_REF][START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks[END_REF][START_REF] Yan | Efficient Implementation of Elliptic Curve Cryptography on DSP for Underwater Sensor Networks[END_REF] did only consider a part of those requirements.

This paper focuses on a fast and secure implementation of ECC on three embedded 16-bit processors. By optimizing performance critical field operations in Assembler, we drive the PIC24 [START_REF]PIC24FJ128GA010 Family Data Sheet[END_REF], dsPIC [START_REF]A/6015 Data Sheet[END_REF], and MSP430 [START_REF]MSP430C11x1 -Mixed Signal Microcontroller[END_REF] to their limits. To the best of our knowledge we are the first to report runtime results on the PIC24 and dsPIC. Furthermore we present runtime results on the MSP430 using standardized NIST curves [START_REF]3: Digital Signature Standard (DSS)[END_REF]. Especially by taking advantage of the 16bit multiply-accumulate unit of the dsPIC, we were able to improve its runtime for a point multiplication by a factor of up to 5.41, a field multiplication by 6.36, and a big-integer multiplication by 7.91 (compared to a speed-optimized C-implementation). Thus we reduced a 160-bit multi-precision multiplication to 180 cycles, with 100 cycles being the theoretical minimum.

Our framework is written and verified in C, uses a side-channel aware Montgomery Ladder including y-recovery (formulae by Hutter et al. [START_REF] Hutter | Memory-Constrained Implementations of Elliptic Curve Cryptography in Co-Z Coordinate Representation[END_REF]), and verifies the resulting point in order to check for fault attacks (see Ebeid et al. [START_REF] Ebeid | Securing the Elliptic Curve Montgomery Ladder Against Fault Attacks[END_REF]). Additionally a projective point randomization [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF] was used in order to strengthen the side-channel resistance of the Montgomery ladder. Having fixed our high-level algorithms, we investigate different big-integer multiplication methods (operandscanning, product-scanning, and hybrid) and field-multiplication methods (Barrett, Montgomery, and fast-NIST-reduction) on the three processors. Our results can be the foundation for choosing suitable embedded processors (e.g. smart cards or sensor networks), for the investigation of important ECC-related features for future microprocessors, and for follow-up research on custom ECChardware designs.

The remainder of the paper is structured as followed. Section 2 discusses relevant related work. Section 3 gives an introduction to elliptic curve cryptography and the used algorithms. Whereas Section 4 gives a short introduction into the MSP430 processor, Section 5 discusses the performance optimizations made for the Microchip processors. Section 6 gives a comparison of all results and Section 7 concludes the work.

Related Work

In the last years, a lot of research has been done on implementing elliptic curve cryptography on embedded devices. Most notable is the work by Gura et al. [START_REF] Gura | Comparing Elliptic Curve Cryptography and RSA on 8-Bit CPUs[END_REF], who compared elliptic curve cryptography and RSA for the 8-bit ATmega128 processor [START_REF]8-bit AVR Microcontroller with 128K Bytes In-System Programmable Flash[END_REF]. For achieving high performance, they introduced the hybrid multiplication method. The results by Gura et al. for the ATmega128 processor have been later improved by Uhsadel et al. [START_REF] Uhsadel | Enabling Full-Size Public-Key Algorithms on 8-bit Sensor Nodes[END_REF], Scott et al. [START_REF] Scott | Optimizing Multiprecision Multiplication for Public Key Cryptography[END_REF], and Liu et al. [START_REF] Liu | Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers[END_REF]. Further results for ATmega128 processors have been shown by Szczechowiak et al. [START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks[END_REF]. Using the preceding work of Scott and Szczechowiak [START_REF] Scott | Optimizing Multiprecision Multiplication for Public Key Cryptography[END_REF], Szczechowiak et al. [START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks[END_REF] presented a comparison of ECC and pairings for the ATmega128 and MSP430 processors. Those processors are specially interesting, because they are used for the Wireless Sensor Network nodes MICA2 [8] and Tmote Sky [START_REF] Moteiv | The Moteiv Wireless Sensor Networks Website[END_REF]. They compared the performance of the sensor nodes for the NIST K-163 Koblitz curve over GF (2 163 ) and a custom curve with p = 2 160 -2 112 + 2 64 + 1 over GF (p). Their results are based on MIRACL [START_REF] Software | Multiprecision Integer and Rational Arithmetic C/C++ Library[END_REF], a Multiprecision Integer and Rational Arithmetic C/C++ Library.

Similar work with focus on sensor nodes has been published by Liu et al. [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF]. They used the by SECG standardized secp160r1 prime field [START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF]. Note that for security reasons this curve has been removed from the latest version of the standard [START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF].

In 2009, Yan et al. [START_REF] Yan | Efficient Implementation of Elliptic Curve Cryptography on DSP for Underwater Sensor Networks[END_REF] used the 32-bit DSP processor TMS320C6416 from Texas Instruments to implement the secp160r1 and secp224r1 elliptic curves. This very powerful processor fits only partly within the scope of this paper, but uses 16-bit multipliers internally. It operates at 1 GHz, has 64 32-bit registers and 1,024 KB L2 cache.

In contrast to the MSP430 and TMS320C6416 processors, we use the ECCprocessors by Kern et al. [START_REF] Kern | Low-Resource ECDSA Implementation for Passive RFID Tags[END_REF], Hutter et al. [START_REF] Hutter | An ECDSA Processor for RFID Authentication[END_REF], and Wenger et al. [START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF] as references. Those papers present specially optimized semi-custom ASIC designs that use 16-bit multipliers. This makes them perfectly suitable for a comparison with the performance of the dsPIC processor.

The design by Kern et al. [START_REF] Kern | Low-Resource ECDSA Implementation for Passive RFID Tags[END_REF] generates an ECDSA signature within 511 kCycles for the elliptic curve secp160r1. Specially notable is their fast reduction technique taking advantage of two carry registers.

Hutter et al. [START_REF] Hutter | An ECDSA Processor for RFID Authentication[END_REF] are using an 8-bit RISC microcontroller supporting 32 instructions, which is used for higher-level control-flow operations. In order to process ECC efficiently, they use eight microcode ROM tables. Those tables control a 16-bit multiply-accumulate unit and a dual-port 16-bit RAM. For NIST P-192 prime field, without reduction a multiplication only needs 168 clock cycles. This is very close to the optimum of N 2 = 12 2 = 144 clock cycles. The design performs ECDSA and has a chip area of only 19,115 gate equivalents.

The focus of the work of Wenger et al. [START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF] was to reduce the area footprint (11,686 gate equivalents) of their processor. They use a custom 16-bit RISC processor, featuring 46 instructions and 12 registers. The most notable feature of their Arithmetic Logic Unit (ALU) is a 16-bit multiply-accumulate unit. In order to reduce the disadvantage from their single-port RAM, they parallelized and combined the arithmetic and memory access instructions. Hence the run time of the same 192-bit multi-precision multiplication needs 252 clock cycles, which is 33 % longer than the design of [START_REF] Hutter | An ECDSA Processor for RFID Authentication[END_REF].

Elliptic-Curve Cryptography

Elliptic-Curve Cryptography (ECC) is defined over the Weierstrass equation

E : y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 (1)
with a i=1,2,3,4,6 , x, y ∈ K. K defines the finite field. If a combination of x and y fulfills Equation (1), it is noted a point P = (x, y) on the elliptic curve. Using formulas for the addition and doubling of points, a point multiplication Q = kP can be derived. Finding k, if Q and P are given, is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Throughout this paper, K is a prime field F p . n = log 2 (p) bits or N = n/W words are needed to represent an element of F p . W is the word size of the processor used. The binary representation of a field element a can be stored in an array A = (A[N -1], . . . , A [START_REF]8-bit AVR Microcontroller with 128K Bytes In-System Programmable Flash[END_REF], A [START_REF]AMERICAN NATIONAL[END_REF], A[0]) of N W -sized words. The least significant bit of a is stored in the rightmost bit of A[0].

Algorithms Used

Every point operation uses the underlying field operations, discussed in the following subsection. Speeding up those point operations has been a major goal of a lot of researchers [START_REF] Bernstein | Explicit-formulas database[END_REF][START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Unfortunately most of those formulas are vulnerable to power, timing and fault-analysis attacks [START_REF] Fan | State-of-the-Art of Secure ECC Implementations: A Survey on known Side-Channel Attacks and Countermeasures[END_REF][START_REF] Walter | Simple Power Analysis of Unified Code for ECC Double and Add[END_REF]. So it is important to use a method that is less vulnerable to such attacks. Such a method is the Montgomery Ladder. This method performs a point addition and doubling for every key bit during a point multiplication. We applied the formula by Hutter et al. [START_REF] Hutter | Memory-Constrained Implementations of Elliptic Curve Cryptography in Co-Z Coordinate Representation[END_REF] which only requires 7 n-bit registers. Their formula needs 12 multiplications, 4 squarings and 17 additions per key bit and uses a Montgomery Ladder with common-Z coordinates. By randomly initializing this Z-coordinate [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF], an additional, computationally cheap resistance against side-channel attacks can be added. In order to make fault attacks more difficult, the y-coordinate is recovered within the projective coordinates and a point verification [START_REF] Ebeid | Securing the Elliptic Curve Montgomery Ladder Against Fault Attacks[END_REF] is performed.

Having fixed the high-level point-multiplication formula, one can concentrate on the fast and efficient implementation of field operations.

Modular Multiplication

The most time-critical field operation is the field multiplication [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] and the most time-critical part of the field multiplication is the multi-precision multiplication. Although there exist different multi-precision multiplication methods, for every multiplication, N 2 partial products are needed in order to get a 2N -word result. Such methods are the operand-scanning, the product-scanning [START_REF] Comba | Exponentiation cryptosystems on the IBM PC[END_REF], and the by Gura et al. [START_REF] Gura | Comparing Elliptic Curve Cryptography and RSA on 8-Bit CPUs[END_REF] introduced hybrid method.

The operand-scanning method is shown on the left of Figure 1. During operand scanning one row is calculated by multiplying one word of the first operand with all words of the second operand. The resulting partial products are immediately added to C[k]. Thus this method needs 2N 2 + N read operations and N 2 + N write operations. Those are 3N 2 + 2N memory operations in total.

By rearranging the fixed number of partial products, the product-scanning method (see right part Figure 1) can be derived. Here the intermediate results are sorted column-wise. By using an accumulator [START_REF] Comba | Exponentiation cryptosystems on the IBM PC[END_REF][START_REF] Großschädl | Instruction Set Extensions for Fast Arithmetic in Finite Fields GF(p) and GF(2 m )[END_REF], the intermediate results can be summed up very efficiently. For this method N 2 read operations are needed to access A[i] and B[j] and only 2N write operations are needed to store C[k]. So 2N 2 + 2N memory operations are needed in total. In order to implement the operand and product-scanning multiplication methods, very few registers are needed. Gura et al. [START_REF] Gura | Comparing Elliptic Curve Cryptography and RSA on 8-Bit CPUs[END_REF] takes advantage of the large register-set of embedded processors and combines the operand and productscanning approaches. In an inner loop, d 2 intermediate products are processed row-wise (operand scanning) and in an outer loop, the intermediate sums are added column-wise (product scanning). The larger the parameter d is chosen, the more intermediate products are processed row-wise (d 2 ) and the more registers are needed (3d + log 2 (N/d)/W ) to implement this method efficiently. The advantage of the hybrid-multiplication method is that it can reduce the number of memory operations to 2 N 2 /d + 2N .

a 0 * b 3 a 1 * b 3 a 2 * b 3 a 3 * b 3 a 2 * b 1 a 3 * b 1 a 0 * b 2 a 1 * b 2 a 2 * b 2 a 3 * b 2 a 3 * b 1 a 3 * b 2 a 2 * b 3 a 3 * b 3 a 0 * b 0 a 1 * b 0 a 2 * b 0 a 3 * b 0 a 0 * b 1 a 1 * b 1 a 3 * b 0 a 2 * b 1 a 1 * b 2 a 0 * b 3 a 1 * b 3 a 2 * b 2 a 0 * b 0 a 1 * b 0 a 0 * b 1 a 0 * b 2 a 1 * b 1 a 2 * b 0

Field Multiplication

The used multi-precision multiplication method has a significant influence on the runtime of a point and field multiplication. A field multiplication adds a reduction to the multi-precision multiplication. There are three very popular ways to perform this reduction: Barrett reduction, Montgomery reduction, and fast reduction (NIST reduction). We implemented all three methods and the results convinced us to do no further investigation into the Barrett reduction.

The fast reduction method is based on the special design of the primes used within the standards (e.g. NIST P-192; p 192 = 2 192 -2 64 -1). This special Mersenne-like prime allows a reduction by only using addition and shift operations. In practice this method is very fast, because additions are much faster than multiplications. However there are Mersenne-like primes with a lot of (e.g. NIST P-256; p 256 = 2 256 -2 128 -2 96 + 2 32 -1) or odd (e.g. secp160r1;

p 160 = 2 160 -2 31 -1) exponents, which have a significant influence on the runtime.

A method which is not dependent on the kind of the used prime is the Montgomery multiplication [START_REF] Montgomery | Modular Multiplication without Trial Division[END_REF]. This method need some special set-up and back transformation of the field elements, but when there are a lot of operations involved, this method definitively pays off. First a R = 2 W N is selected at design-time, making sure that R > p and gcd(R, p) = 1. The field elements are transformed by ã ≡ aR (mod p), and

(2) b ≡ bR (mod p),

and further ã and b are used instead of a and b. A multiplication is performed as follows:

c ≡ M ont(ã, b) ≡ ãb R -1 ≡ (aR)(bR)R -1 ≡ abR ≡ cR (mod p). (4)
Utilizing the Montgomery multiplication, the transformation of the field elements can be carried out easily:

M ont(a, R 2 ) ≡ aR 2 R -1 ≡ aR ≡ ã (mod p), (5)
M ont(c, 1) ≡ (cR)R -1 ≡ c (mod p). (6)
In practice the multi-precision multiplication and Montgomery reduction are interleaved. For the important implementation specific aspects of the Montgomery multiplication we refer to Koç et al. [START_REF] Koç | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF]. Every one of the previously discussed multiplication and reduction methods has advantages and disadvantages on certain microprocessors and the used prime. Those are discussed in the following sections.

Texas Instruments MSP430

The 16-bit MSP430 processor [START_REF]MSP430C11x1 -Mixed Signal Microcontroller[END_REF] by Texas Instruments is a very popular RISC processor. Especially its vast field of application makes it interesting (e.g. Tmote Sky [START_REF] Moteiv | The Moteiv Wireless Sensor Networks Website[END_REF]). The processor has 16 fully-addressable, single-cycle CPU registers that can be used with 27 instructions (24 additional instructions are emulated). Four of those registers are special purpose registers (program counter, stack pointer, status register, and constant generator), so not all registers can be used for an Assembler-optimized elliptic-curve implementation. A very important module for the multi-precision multiplication algorithm is the multiplier. The MSP430 does not have a multiplication instruction. Depending on the series, it only offers a 16-bit or 32-bit memory-mapped hardware multiplier. In order to perform a 16-bit multiplication, four memory accesses are necessary (write the two operand words and read the two resulting words).

For the MSP430, we implemented the three major multi-precision multiplication operations, discussed in Section 3.2 in Assembler. The advantage of the operand-scanning method is that in average only three memory accesses are necessary for a single integer multiplication. Remember that one operand stays constant during the calculation of a row. The product-scanning multiplication method takes advantage of the MAC instruction. This instruction uses the result register as accumulator and provides a carry bit. So for every partial product, the two operands have to be written and only the carry flag has to be processed. For the hybrid multiplication results in Section 6, we used an implementation with d = 2.

In order to summarize our results for the MSP430, the biggest disadvantage in terms of ECC is that its hardware multiplier is memory mapped. Having a processor with a multiplication instruction improves ECC significantly. Such processors are the PIC24 and dsPIC.

Microchip PIC24 and dsPIC

The PIC24 and dsPIC microcontroller families by Microchip [START_REF]PIC24FJ128GA010 Family Data Sheet[END_REF][START_REF]A/6015 Data Sheet[END_REF] are 16-bit RISC processors that are using a modified Harvard architecture. They are widely used for motor control, signal processing, and intelligent sensor applications. These controllers use 24-bit instruction words with a variable length opcode field. Almost all instructions can be executed in a single cycle. Only commands which change the program flow, table operations and the double word move instruction take two or more cycles. Similar to the MSP430, the used PIC processors have 16 [START_REF] Hutter | Memory-Constrained Implementations of Elliptic Curve Cryptography in Co-Z Coordinate Representation[END_REF]-bit registers labeled as W0 to W15. W14 and W15 are used as frame and stack pointer.

The dsPIC processors facilitate different features that make them perfectly suited for public-key operations. First of all, the processor comes with a Digital Signal Processing (DSP) engine. This engine provides two 40-bit accumulators and a corresponding Arithmetic Logic Unit (ALU). This ALU is equipped with a multiply and accumulate (MAC) instruction. Additionally a second Address Generation Unit (AGU) is integrated. The primary address generation unit is called X, the secondary is called Y. Some of the DSP instructions can utilize these two AGUs and therefore fetch two operands at the same time while processing the data in the registers. However, not the whole address space is available to both AGUs. The X unit can read and write to all addresses while the Y unit can only read from a certain device specific region. Nevertheless it is possible to improve the performance considerable by taking the hassle of placing the data at the correct position in memory.

In order to minimize the overhead of loop constructs, special loop instructions named REPEAT and DO are provided. While DO needs two cycles to set up the loop and can execute several instructions multiple times, REPEAT needs one cycle and operates on a single command only. Another feature is the possibility to post increment or decrement pointers when indirect memory addressing is used. With this capability, the pointer arithmetic can be sped up significantly.

When performance is not the first priority using PIC24 processors is an option. Beside the missing DSP engine and the lack of the DO instruction the cores of the PIC24 and the dsPIC processors are the same. Due to this compatibility we can give detailed results on the impact of the DSP engine concerning performance.

In order to find the fastest implementation for this processor architecture we start by presenting a generic product scanning algorithm which takes advantage of the DSP instructions. As the code of the inner loop is the most important code segment concerning speed, the following subsection focuses on this part. In the next step additional ideas to further optimize the multi-precision multiplication for speed are explained.

Generic Product Scanning on the dsPIC

The inner loop of the product scanning algorithm consists of one 16-bit multiplication and one addition (32-bit plus overflow handling). Additionally two load operations are required to fetch the values of A[i] and B[j] from memory. Furthermore the increment or decrement of i and j has to be handled as well. Usually this operations would involve two registers for the operand values, two registers for the multiplication product and three registers for the result of the addition.

As we have the DSP extension we take advantage of one of the 40-bit accumulators. The multiply-accumulate (MAC) instruction is used to multiply two 16-bit operands and to add the result to the accumulator. This means that we can handle the multiplication and the addition with the necessary precision in one clock cycle. Now that we know how the data can be processed efficiently we still need to find a performant way to fetch the operand values. This can be implemented with the MAC instruction as well. As this DSP command possesses the capability to pre-fetch values by utilizing the two AGUs, it is possible to load both operands during one clock cycle.

By the use of pointers to address the current operands, the update of i and j can be implemented through applying post increments and/or decrements to those pointers. Due to the fact that this pointer arithmetic is also supported by this DSP operation the complete inner loop can be reduced to a single MAC instruction plus REPEAT command.

The result of this optimization can be seen in Figure 2 in Lines 14 to 16. At first the number of iterations for the REPEAT is calculated by subtracting the current loop count in DCOUNT (addressed via pointer in W0) from the total loop count (stored in W3). Afterwards the loop is set up using REPEAT followed by the MAC instruction which should be repeated. This MAC invocation reads as follows: Multiply the operands stored in a temp and b temp and add them to As the MAC instruction always operates with the values which are already stored in a temp and b temp, it is mandatory to initialize them before this inner loop is executed. These fetches are done by using the MOVSAC operation in Line 12.

By looking at the pre-fetch behavior it can be seen that the last MAC operation loads operands which are not needed for the algorithm. By unrolling this last MAC invocation from the REPEAT it is possible to use the last pre-fetch to initialize a temp and b temp with the needed data for the next iteration. By doing this, the MOVSAC operation in the outer loop can be omitted.

Unrolled Product Scanning on the dsPIC

By unrolling the code for a fixed n-bit integer multiplication, advantage of the constant input size can be taken to improve the pointer arithmetic. The temporary pointers can be omitted when an appropriate sequence for the partial products is chosen as the post-in/decrement functionality of the MAC instruction is sufficient to update the pointers. The resulting zig-zag like pattern is nicely visualized in Figure 3. A part of the resulting source code is shown in Figure 4. Observe that the multiplicands for the multiplication are loaded in the preceding operations W 5 ← [W 9] and W 6 ← [W 11]. In the once more preceding operation, the pointer registers are updated using the post in/decrement feature:

[W 9]-= 2, [W 11]+ = 2.
At this point, we have to note that there is a prerequisite which has to be fulfilled. The pre-fetch mechanism requires that the operands are in different address spaces (X and Y). We ensure this by copying the input integers into temporary variables at the beginning of the multiplication. Although these copy operations are quite cheap (15 cycles for one 160-bit integer) it is possible to omit them by placing the operands in the correct memory region before the function call. As the generic implementation uses the pre-fetch technique too, the same constraint applies.

Montgomery Multiplication on the dsPIC

Like proposed by Koç et al. [START_REF] Koç | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF], various implementations of the Montgomery multiplication are possible which mainly differ in the underlying multiplication method (operand scanning, product scanning, . . . ) and the degree of integration of the reduction step. As product scanning provides the best results on the dsPIC architecture we have chosen the Finely Integrated Product Scanning (FIPS)

1 MAC W5 * W6, A, [W9]-=2, W5, [W11]+=2, W6 2 MAC W5 * W6, A, [W9], W5, [W11]+=2, W6 3 MAC W5 * W6, A, [W9]+=2, W5, [W11]-=2, W6 4 MOV [W7],[W2++] 5 SFTAC A, #16 6 7 MAC W5 * W6, A, [W9]+=2, W5, [W11]-=2, W6 8 MAC W5 * W6, A, [W9]+=2, W5, [W11]-=2, W6 9 MAC W5 * W6, A, [W9]+=2, W5, [W11], W6 10 MAC W5 * W6, A, [W9]-=2, W5, [W11]+=2, W6 11 MOV [W7],[W2++] 12 SFTAC A, # 16
Fig. 4. Unrolled calculation of the result word two and three.

method for our implementation. The interleaving of multiplication and reduction makes it necessary to implement the whole Montgomery multiplication using Assembler. Otherwise no decent performance can be gained following the FIPS approach. Through the high similarity of the product-scanning and the FIPS method most of the optimizations presented in the last sections can be applied as well, resulting in a fast implementation of the field multiplication.

Comparison Results

For the results shown in this section, we avoided to select the parameters for ECC ourselves. Instead we chose curves that have been standardized [START_REF]AMERICAN NATIONAL[END_REF][START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF][START_REF]3: Digital Signature Standard (DSS)[END_REF]. NIST [START_REF]SP800-57 Part 1: DRAFT Recommendation for Key Management: Part 1: General[END_REF] gave recommendations about the security margin for future applications. They recommend to use elliptic curves that exceed 160 bits. Also SECG removed the 160-bit curve in their latest release of the SEC standard [START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF]. Nevertheless, we present results for the secp160r1 curve for comparison with related work. Additionally, the relative performance results shown in Subsection 6.1 are also applicable for larger elliptic curves. Those elliptic curves are discussed in Subsection 6.2.

For the generation of the results, for the MSP430 we used the IAR Embedded Workbench 5.30 [START_REF]IAR Embedded Workbench[END_REF] with the maximum optimizer settings available '-Ohs'. All results have been generated for the MSP430F1611 device which comes with an embedded 16-bit multiplier.

For the PIC24 and dsPIC results, we used the simulator of the MPLAB IDE v8.63 [START_REF]MPLAB Integrated Development Environment[END_REF], the MPLAB C30 v3.25 compiler with settings '-o3', '-funroll-loops', and the PIC24FJ96GA006 and dsPIC30F6015 devices.

For the following comparisons it should be noted that we neglect parameters such as chip area, power consumption and cost factors, because they significantly differ from processor to processor. However energy is defined as product of power and time. So by minimizing the runtime, we also optimize the energy consumption.

Relative Performance

In Table 1, we compare the run times for big-integer multiplication, field multiplication and point multiplication using the secp160r1 curve [START_REF]Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters[END_REF]. For all presented platforms, we started with a reference implementation in C. In C, the operand-scanning multiplication outperforms the product-scanning multiplication by 12.6 % (MSP430) and 16.4 % (PIC24). Consequently, the point multiplication is 8.2 % and 13.5 % faster. By manually writing the multi-precision multiplication in Assembler, the run time was reduced by a factor of 1.53 to 2.42. Implementing the hybrid multiplication method with d = 2 on the MSP430 improved the runtime by just 4.8 %. By only using 3.1 kbytes of program memory and 274 bytes of stack, this implementation is very resource friendly. Unrolling the product-scanning multiplication method improved the multi-precision multiplication by another 15.1 %, but came at the cost of additional 1.5 kbytes (47 %) more program code. Up to this point, the results on the PIC24 processor are identical to the results of the dsPIC processor. In the following steps, we utilize the special features of the dsPIC to further improve the performance. By making use of the DO and REPEAT commands, the run-time of a single multi-precision multiplication was reduced by 29 % to 33 %. A more significant performance improvement was achieved by utilizing the DSP part of the dsPIC processor. A speedup of 2.72 has been achieved for the product-scanning multiplication method. Using the same methodology, the operand-scanning multiplication method improved by only 1.14. So only when we take advantage of the DSP-unit, the productscanning method is (2.04 times) faster. A further experiment showed that by unrolling the Assembler code and performing the product-scanning in a zig-zaglike fashion, the run time could be further reduced by 32.6 %. At this point it should be noted that although the performance of the multi-precision multiplication has been improved by a factor of 7.91 (unrolled DSP vs. best C version), the performance of the field multiplication improved by 4.30 and the point mul-tiplication improved by 3.92. A reason for that is the slow reduction modulo p 160 = 2 160 -2 31 -1. The term 2 31 results into a relatively slow shift operation. So we investigated the Montgomery multiplication technique. Utilizing the FIPS multiplication method from Koç et al. [START_REF] Koç | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF], the field multiplication was improved by 14.0 %. Unrolling the Assembler code resulted in the fastest field multiplication, just needing 376 cycles. This is 32.5 % faster than the fastest combination of unrolled product-scanning and fast reduction.

By investigating the related results for the MSP430, it becomes obvious that in comparison to Liu et al. [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF], our point multiplication method is 25 % faster even though they used a memory-hungry sliding-window point multiplication method.

The hybrid multi-precision multiplication method by Scott and Szczechowiak et al. [START_REF] Scott | Optimizing Multiprecision Multiplication for Public Key Cryptography[END_REF][START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks[END_REF] is 6 % faster than our multiplication method, because they unrolled their hybrid multiplication. However compared to our unrolled product-scanning method they are 11 % slower. The differences within the field and point multiplication come from a different elliptic curve and sliding-window point multiplication formula used. Because the sliding window technique needs additional memory, they need 2.9 kbytes of data memory and 31.3 kbytes of program memory, which is more than 10 times the resources we need.

The results on the dsPIC processor made us confident enough to compare them with the powerful TMS320C6416 processor (Yan et al. [START_REF] Yan | Efficient Implementation of Elliptic Curve Cryptography on DSP for Underwater Sensor Networks[END_REF]) as well as the custom designed ASIC by Kern et al. [START_REF] Kern | Low-Resource ECDSA Implementation for Passive RFID Tags[END_REF]. The implementation by Yan et al. [START_REF] Yan | Efficient Implementation of Elliptic Curve Cryptography on DSP for Underwater Sensor Networks[END_REF] using the mighty TMS320C6416 processor1 and the custom designed ASIC ought to be faster. But the difference is only a factor of 1.53 -2.42.

With this comparison we showed that the field multiplication utilizing a memory-mapped multiplication unit is more than 2 times slower. Also the advantages of having DO/REPEAT and DSP instructions have been discussed. Utilizing the full potential of the Montgomery multiplication method, the point multiplication has been improved by a factor of 5.41 versus the fastest C-only implementation.

Scaling of Performance

The last subsection limited the comparison to the secp160r1 curve. This subsection extends our focuses to the NIST [START_REF]3: Digital Signature Standard (DSS)[END_REF] standardized elliptic curves P-192, P-224, and P-256.

The most remarkable feature within Table 2 is the influence of the chosen field prime into the run time of the point multiplication. On the dsPIC processor, the performance of the FIPS Montgomery field-multiplication is better for the secp160r1 and NIST P-256 fields, but the fast reduction technique utilizing Mersenne-like primes are faster for the NIST P-192 and P-224 prime fields.

The Assembler optimizations on the MSP430 resulted in a speedup of 1.93 to 2.34. The larger the used prime field, the larger is the achieved speedup. Also on the PIC24 architecture, speedups between 1.23 and 1.42 have been achieved. Utilizing the dsPIC, the biggest speedup factors, ranging from 3.89 up to 4.79, have been achieved.

Our results improved the work of Liu et al. [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF] on the MSP430 processor. Again we compared our results with the powerful TMS320C6416 processor as well as some custom designed ASICs. The TMS320C6416 performs the point multiplication only 1.7 -2.1 times faster, which is quite small compared to the processing power of the TMS320C6416. Also the ASIC designs ought to be faster. Although those design focused on area-optimizations the authors [START_REF] Hutter | An ECDSA Processor for RFID Authentication[END_REF][START_REF] Kern | Low-Resource ECDSA Implementation for Passive RFID Tags[END_REF][START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF] achieved good run time results. Consequently the performance differs by a factor of 1.58 -3.31.

Conclusion

In this paper we presented, evaluated, and optimized an elliptic curve point multiplication for three different processors using four different elliptic curves. Starting with a C reference implementation (which includes several countermeasures against possible attacks), we were able to improve the runtime by simply rewriting the performance critical field operations in Assembler. Therefore we evaluated the most commonly used big-integer and field multiplication methods. We achieved a speedup for a single point multiplication of 1.93 -2.34 on the MSP430, 1.23 -1.42 on the PIC24 and 3.89 -5.41 on the dsPIC. Especially impressing is the possible speedup of 7.91 for a single 160-bit multiplication on the dsPIC which is 10.5 times faster than fastest corresponding operation on the MSP430.

By the best of our knowledge, we are the first to present results for ECC on the PIC24 and dsPIC and those results are especially interesting for future applications in which embedded processors are required.

Fig. 1 .

 1 Fig. 1. Partial products during multi-precision multiplication. (left: Operand Scanning, right: Product Scanning)

  accumulator A (A ← A + W 5 * W 6). At the same time fetch the next a temp via AGU X by dereferencing aP tr temp (W 5 ← [W 8]). Simultaneously, the next b temp is fetched via AGU Y by dereferencing bP tr temp (W 6 ← [W 10]). The pointers are updated by incrementing aP tr temp ([W 8]+ = 2) and decrementing bP tr temp ([W 10]-= 2) by two.

1 ;

 1 W0 = pointer to the DCOUNT register ; W7 = pointer to the ACCAL register 2 ; W2 = result pointer ; W8 = temporary pointer (aPtr temp) 3 ; W3 = integer length in words (length) ; W9 = operand pointer (aPtr) 4 ; W4 = temp register (tmp) ; W10 = temporary pointer (bPtr temp) 5 ; W5 = value of operand a (a temp) ; W11 = operand pointer (bPtr) 6 ; W6 = value of operand b (b

Fig. 2 .

 2 Fig. 2. One of the two loops in the generic product scanning implementation.

Fig. 3 .

 3 Fig.3. Note the zig-zag product scanning multiplication method, which is specially suited for the dsPIC. (e.g. four word multi-precision multiplication)

Table 1 .

 1 Comparison of the multi-precision multiplication, the field multiplication and the ECC point multiplication for secp160r1.

	Implementation	Multi-Prec. Mult. Fp 160 Mult.	Point Mult.
	MSP430 C	op. sc.	4,103	6,069	16,985,654
	MSP430 C	pr. sc.	4,699	6,665	18,512,606
	MSP430 a ASM	op. sc.	2,583	4,127	11,380,361
	MSP430 a ASM	pr. sc.	1,945	3,489	9,745,805
	MSP430 a ASM	hybrid	1,851	3,395	9,504,977
	MSP430 a ASM + unrolled pr. sc.	1,570	3,112	8,779,931
	PIC24	C	op. sc.	1,423	2,393	6,703,476
	PIC24	C	pr. sc.	1,702	2,675	7,753,292
	PIC24 b ASM	op. sc.	929	1,909	5,463,648
	PIC24 b ASM	pr. sc.	1,031	2,011	5,739,732
	dsPIC c ASM + DO/REP. op. sc.	622	998	2,840,921
	dsPIC c ASM + DO/REP. pr. sc.	727	1,104	3,127,253
	dsPIC c ASM + DSP	op. sc.	546	923	2,648,377
	dsPIC c ASM + DSP	pr. sc.	267	644	1,932,431
	dsPIC c ASM + unrolled pr. sc.	180	557	1,709,537
	dsPIC c ASM + DSP	Montgomery	-	554	1,696,433
	dsPIC c ASM + unrolled Montgomery	-	376	1,239,281
	MSP430 Liu et al. [20]				12,645,040
	MSP430 d Scott et al. [29, 31]		1,746	2,736	5,760,000
	TMS320 Yan et al. [36]		150	290	810,000
	ASIC	Kern et al. [18]	pr. sc.		167	511,864

a Multi-precision addition and subtraction were manually unrolled in Assembler. b Only multi-precision multiplication was manually written in Assembler. c Multi-precision addition, subtraction, and shift operation were manually written in Assembler. d Did not use secp160r1.

Table 2 .

 2 Point multiplication for different field parameters in kCycles.

		Implementation		secp160r1	P-192	P-224	P-256
	MSP430	C	op. sc.	16,986	23,405	35,531	47,455
	MSP430	ASM	hybrid	9,505	11,949	18,464	23,973
	PIC24	C	op. sc.	6,703	8,985	13,781	18,992
	PIC24	ASM	op. sc.	5,464	6,754	10,138	13,379
	dsPIC	ASM + DSP	pr. sc.	1,932	2,178	2,880	5,079
	dsPIC	ASM + DSP	Mont.	1,696	2,528	3,582	4,879
	MSP430	Liu et al. [20]		12,645
	C6416	Yan et al. [36]		810		1,690
	ASIC	Kern et al. [18]	pr. sc.	512
	ASIC	Wenger et al. [35]	pr. sc.		1,377
	ASIC	Hutter et al. [15]	pr. sc.		783

64 32-bit registers. Eight independent functional units. 1 GHz.

Acknowledgements

This work has been supported by the Austrian Government through the research program FIT-IT Trust in IT Systems under the project number 825743 (project PIT). Finally we would like to thank Manfred Großmann for some fruitful discussions.