Raoul Strackx
email: raoul.strackx@cs.kuleuven.be

Yves Younan
email: yves.younan@cs.kuleuven.be

Pieter Philippaerts
email: pieter.philippaerts@cs.kuleuven.be

Frank Piessens
email: frank.piessens@cs.kuleuven.be

Efficient and Effective Buffer Overflow Protection on ARM Processors

Keywords: Control flow attacks, Stack-based buffer overflow, Software security, mobile platform

Although many countermeasures have been developed for desktop and server environments, buffer overflows still pose a big threat. The same approach can be used to target mobile devices. Unfortunately, they place more severe limitations on countermeasures. Not only are the performance requirements at least as important, memory and power consumption need to be considered as well. Moreover, processors used in mobile devices generally are equipped with a different instruction set. Therefore countermeasures may not be ported easily. Multistack is an effective countermeasure against stack-based buffer overflows. It protects applications by using multiple stacks to separate possible attack targets from possible sources. However, its performance overhead will no longer be negligible on the ARMv7 platform (widely used on mobile devices) and it wastes too much memory, making it too costly for mobile applications. We propose 3 methods to reduce memory overhead up to 28% with only a 3.91% performance overhead.

Introduction

Buffer overflow vulnerabilities pose a significant threat to applications written in unsafe languages and to the devices they run on. Most of the existing buffer overflow attacks write past the boundary of a buffer located on the stack and modify an interesting memory location. Function return addresses are a frequently chosen target of attack. By overwriting them with the location of code inserted as data into memory, the program can be forced to execute instructions with the privilege level of the attacked program [START_REF]Aleph1: Smashing the stack for fun and profit[END_REF][START_REF] Erlingsson | Handbook of information and communication security[END_REF].

Many countermeasures that protect desktop and server environments have been developed. Some try to solve the problem entirely by inserting bound checks or modifying the language itself [START_REF] Kendall | Bcc: Runtime checking for C programs[END_REF][START_REF] Larus | Righting software[END_REF][START_REF] Necula | CCured: Type-safe retrofitting of legacy software[END_REF]. Others rely on randomness and secrets to detect or prevent modifications of data in memory. The latter have less performance overhead [START_REF] Cowan | Stackguard: automatic adaptive detection and prevention of buffer-overflow attacks[END_REF][START_REF] Etoh | Protecting from stack-smashing attacks[END_REF][START_REF] Team | Documentation for the PaX project[END_REF][START_REF] Bhatkar | Address obfuscation: An efficient approach to combat a broad range of memory error exploits[END_REF]. Even though many more approaches exist, attackers still find ways to attack systems successfully, for example by breaking some of the assumptions made in the countermeasures in place, such as the fact that a canary remains secret [START_REF] Strackx | Breaking the memory secrecy assumption[END_REF].

Buffers can be allocated on the stack, the heap or in the data/bss section in C. For arrays 1 that are declared in a function body, space is reserved on the stack. Buffers that are allocated dynamically (using the malloc function, or some other variant), are put on the heap, while arrays that are global or static are allocated in the data/bss section. The array is manipulated by means of a pointer to the first byte. Bytes within the buffer can be addressed by adding the desired index to this base pointer. Most C-compilers generate code that does not check the bounds of an array and allow programs to copy data beyond their end. This behavior can be used to overwrite data in adjacent memory space. The unprotected application can be successfully attacked if these memory locations contain data that influence control flow and is used after the buffer overflow.

On the stack this is usually the case: it stores the addresses to resume execution at, after a function call has completed its execution. This address is called the return address. Manipulating it gives the attacker the possibility to execute arbitrary code.

Listing 1.1 shows a straightforward string copy function. Improper use of this function can lead to a buffer overflow, because there is no validation that the destination buffer can actually hold the input string. An attacker can thus exploit the buffer overflow vulnerability to overwrite memory that is stored adjacent to the destination buffer.

Multistack

Approach

Multistack [START_REF] Younan | Extended protection against stack smashing attacks without performance loss[END_REF] is a separation-based countermeasure designed to protect applications against stack-based buffer overflows. For each data type that may be stored on the stack, an analysis is made to determine the feasibility that 1) it can be used as a source of attack and 2) it will ever be a target of an attack. Using this information, types with a comparable source/target trade-off are placed in the same category.

For example, an array of characters is a common source of attack, but is rarely a target itself. Pointers on the other hand, are much more likely to be a target. In case an attacker is able to overwrite a pointer and specify the value written to memory by dereferencing that modified pointer, he/she can write an arbitrary value to a chosen memory location [START_REF] Bulba | Kil3r: Bypassing stackguard and stackshield[END_REF]. It is clear that these types should be separated from one another and they are placed in different categories.

This however, may not always be possible. Consider a structure containing an array of characters as well as pointers. This type may be used as an attack source, but may also be a target of attack. This type does not fit in either one of the two previous categories and a new one is created.

Multistack operates by placing the categories of variables on different stacks (see Figure 1). Guard pages2 prevent buffer overflows on one stack from reaching another.

Note that the guard pages will not prevent arrays in structures to overwrite the accompanied pointers. However, in most applications the usage of such structures is modest and the chance of finding a buffer overflow vulnerability in code operating on them, is limited. Applications that do not fulfill this assumption may apply additional countermeasures, possibly only in functions that use such types as local variables.

By placing the separate stacks sequentially in memory, their exact location can be calculated at compile-time. Consider a variable x that should be placed on stack s with offset d from the stack pointer. When all stacks are assigned a maximum length of 8 MiB3 , the updated offset will be

f p -d -s • 8M iB
where fp, the frame pointer, points to the start of the stack frame. This has another advantage; it allows address space layout randomization (ASLR) (see section 7) to relocate the base of the stack each time the application is run. Obviously, the relative distance between the stacks must be specified at compile-time.

To address a variable on the stack, unprotected applications also have to perform this addition, though with a different operand. Since the x86 instruction set provides load and store instructions that are able to store an immediate constant of 32-bits, no extra instructions need to be issued to access the variable.

Multistack can be configured to use any number of stacks. However, when their number increases, the drawbacks of the countermeasure do as well (see section 3.2). Some methods that will be described in section 4 limit the maximum number of categories to four.

Discussion

Performance penalty With the exception of code to allocate the different stacks and the creation of guard pages, no extra instructions are required. Performance evaluation [START_REF] Younan | Extended protection against stack smashing attacks without performance loss[END_REF] shows an overhead between 0% and 3%, on the x86 platform.

This efficiency is reached because this platform is able to use a 32-bit offset in a load and store instruction. On processors equipped with the ARM instruction set, multiple instructions would be required, leading to a degradation of performance (see section 4.1).

Memory consumption By only modifying the offset used to address a stackbased variable, performance loss remains negligible, but it also leads to wasted memory. The corresponding locations of a variable x on the other stacks, remain unused until the function returns. At any time in the execution of an application with s stacks and m the combined size of all variables on the stack, (s -1)m MiB of virtual memory is wasted.

The situation even deteriorates in case multi-threaded applications are considered. In that case, each thread would waste that amount of memory. In section 5 a more detailed analysis is given.

Conclusion

The multistack countermeasure has a very limited performance penalty while providing effective protection against stack-based buffer overflows on the x86 platform. Its memory consumption and increased performance overhead on ARM processors, however make it too costly for mobile devices.

Original approach

The most obvious implementation of Multistack on mobile devices is using a similar implementation as on the x86 platform. As described in section 3, a single frame pointer is used to address stack-based variables. This poses an issue since the ARMv7 instruction set does not support adding an arbitrary 32-bit integer using a single instruction. A simple solution is to use multiple additions (i.e. add instructions), however a performance penalty is expected.

The obvious drawback of this technique is its memory consumption. However, the evaluation in section 5 will reveal that this memory overhead in some cases is negligible.

Dedicated registers

Most applications never allocate space on the stack dynamically. Therefore the size of the stack frame is fixed for each function and the stack pointer can be used to address variables located on the stack. Applications that do not follow this assumption, can be modified by the compiler to not allocate space on the stack at runtime but on the heap instead.

ARM processors are equipped with a large number of registers to store intermediate results. To reduce memory consumption, three stack pointers can be stored in specially reserved registers and used to track the top of each stack.

This can be implemented in a compiler in a straightforward way. The main function is modified to allocate the different stacks and initialize the stack pointers. To each function's prologue and epilogue, instructions are added to allocate and free the required space on the related stacks by updating the corresponding registers. The addressing of stack-based variables is modified to use the appropriate stack pointer.

By reserving save-by-callee registers to hold the stack pointers, protected code is able to call unprotected libraries. However, the registers may not always contain the correct value when callbacks are used to return to protected code. Only in that case, recompilation of the library is required.

Indirection using a fixed address

The previous technique reserves three registers. This may lead to an increased register pressure and consequently a degradation of performance. Alternatively, the location of the stack pointers can be stored at a fixed location. Since all instructions in the ARMv7 instruction set have a fixed length of 32 bits, it is impossible to load an arbitrary 32-bit address in a register by specifying it as the payload of a single instruction. However, the mov instruction is able to do just that when certain requirements on the value are met. To be able to use this instruction, the stack pointers are stored on a reserved page at 0xbe000000 -0xbe000008.

Before executing any other code, the stacks are created and the page at 0xbe000000 is allocated. To allocate/deallocate memory on stack 2 to 4 or address a stack-based variable, the location of stack pointer 2 is loaded in a register first. The subsequent load or store instruction adds the required offset to access the relevant stack pointer. Note that by storing the stack pointers at a well chosen location, no register has to be reserved and only one extra instruction needs to be executed before each memory access related to stack 2 to 4.

Packed stack pointers

The previous technique assumes the increased register pressure to be the main contributor to the performance overhead of the countermeasure. In order to reduce it, stack pointers are loaded from and stored in memory when appropriate. This assumption however, may not hold for all applications. The presented "improvements" may in some cases even lead to a further deterioration of the countermeasure's performance.

Technological developments during the last decades resulted in a huge increase of processor and memory speed. However, making inexpensive, large memory that can be accessed rapidly, proved to be challenging. Multiple levels of caches were introduced to increase the overall performance of the system but accessing registers remains faster than loading a value from cache.

To load instructions from memory quickly, processors are equipped with pipelines to decode instructions. This technique works well when branches are reduced to a minimum. Considering both optimizations, it is obvious that it may be more efficient to execute more instructions when this avoids memory accesses.

The approach presented in this section uses another observation. The dedicated register approach uses one register for each stack pointer. While theoretically the stack is able to grow arbitrarily large, in practice only in extremely rare cases more than 8 MiB is required.

By aligning the added stacks at 8 MiB, the 11 most significant bits of their stack pointers will remain fixed for the entire execution of the program. As a result, by allocating the stacks at a location specified at compile time, only the 23 least significant bits need to be stored. This number can be reduced to 21 when it is assumed that each variable on the stack is 4-byte aligned. Using this approach [START_REF] Ergin | Register packing: Exploiting narrow-width operands for reducing register file pressure[END_REF], three stack pointers can be stored in only two registers. The stack pointer of the least frequently accessed stack will be split over the two registers.

Note that even more stack pointers can be stored using less registers by limiting the size of the stacks. Another option is to increase the alignment of both the stacks and the stored variables to facilitate larger stacks. However, in case a stack frame's length is not a multiple of the alignment, memory will be wasted.

As before, the main function is modified to allocate memory for the different stacks, to set the guard pages and initialize the stack pointers. Allocating space on a stack can be done without completely restoring the stack pointers. However, care must be taken when the stack pointer that is split over two registers needs to be updated. A carry bit may need to be added or subtracted from the most significant part of the pointer when the least significant part wraps around zero. By carefully choosing bit shift operations, this can be done without using any extra registers or branches.

Since this approach requires that two registers are reserved, the same incompatibility with callback functions as described in section 4.2 exists and a full recompilation of the application may be required.

Evaluation

During development, we focused mainly on smart phones and PDA's. The telecom and consumer suite of the MiBench benchmark [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] provides representative applications for these devices. They are used to evaluate memory and performance overhead. The typeset application is omitted because its in-line assembly uses the reserved registers. Applications that would only use stack 1 (CRC32 and adpcm) do not benefit from the countermeasure and are not considered.

Security evaluation

Two of the presented approaches store the stack pointers in registers. This has the advantage that an attacker is not able to modify this control data, before a successful code execution attack. In case the stack pointers are stored in memory (section 4.3), they are an interesting target of attack. Additional countermeasures need to be installed. However, a simple solution is to modify the location of stack 1 so it contains the memory locations where the pointers are stored.

With the exception of the packed stack pointers approach (section 4.4), the presented techniques have an additional advantage: they allow the locations of the stacks to be randomized, also relative to each other.

In all other aspects, our proposed approaches are as secure as the original Multistack countermeasure [START_REF] Younan | Extended protection against stack smashing attacks without performance loss[END_REF].

Memory consumption

The question how much physical memory can be gained by applying one of the proposed techniques for a specific application, is difficult to answer because many factors must be considered. The core of the problem is that when a virtual page remains unused, there is no need to store the corresponding physical page.

To determine the likelihood of this situation, we ran the telecom and consumer suite of MiBench, protected with the original Multistack implementation. Memory usage of each application was tracked, as well as the number of physical memory pages that were referenced.

These measurements relied on two assumptions. First, we assumed that in any function, the stack variables on stack 1 were placed closest to the base of the stack. Variables on stack 2 came next and so on. Note that the C standard does not specify the exact order of these variables in memory. Second, each stack, including stack 1, started at the beginning of an empty page. This is a worst case scenario. Applications with maximum stack sizes smaller than a single page, will not waste physical memory. In practice, memory may be wasted much sooner.

Table 1 displays the result of the test. Using these figures, the number of pages that will be gained by the proposed approaches, can be calculated easily. The measurements show improvements between 0% and 28% for the test applications, assuming a page size of 4,096 bytes. This large difference in potential gain depends on several factors, being discussed next.

Number, size and type of stack variables As explained in section 3.1, the original Multistack implementation, will result in holes of unused virtual memory. Depending on the number, size and type of stack variables, this in turn leads to internally fragmented, unused and/or completely used pages. Figure 2 displays these possibilities for the lame and qsort applications.

In case pages remain unused, no physical memory is wasted. This situation occurs when a stack is rarely used or when large arrays are allocated. When space is allocated to hold an array larger than two pages, at least one page remains unreferenced on the other stacks. The qsort application allocates 1.2 • 10 6 MiB to hold the values to be sorted and thus is a good example of this situation.

Compacting the stacks will have a positive influence in case many pages are internally fragmented. Consider stack 1 of the lame application. It uses 7 pages (28,672 bytes) to store only 1,444 bytes, or 35.3% of the memory it allocated. Figure 2 also displays the percentage of actually used physical memory to the amount that was allocated.

Number of function calls

The number of function calls also plays an important role. Obviously, in case the number of calls is small, the combined stack size may not be larger than a single page. As a result, even though the original implementation does leave unused memory locations on the stacks, no pages can be saved by compacting the stacks. A number of examples of this situation can be found in the MiBench benchmark, including jpeg, tiff2bw, gsm, FFT, . . . The number of function calls made throughout the execution of the application and the way these calls are made, can play a role in memory usage. When functions call each other to a great depth, the size of the stack could grow large. As a result, multiple pages could be used to store only a few bytes.

Also, if a lot of consecutive calls are made, memory usage could degrade. The diversity of the different calls will decrease the chances that pages on other stacks remain unused. Page size Consider the example that a variable is stored on a certain stack. When this variable is larger than two pages, the corresponding location at the other stacks may remain unused and no physical pages need to be stored. The chances that this situation occurs increases inversibly with the size of the pages.

Small pages have a second advantage; on average only half of the pages before and after such a hole are used. In case the pages are smaller, less physical memory is wasted.

Our memory usage measurement on the MiBench benchmark assumes that the stack pointer points to the beginning of a blank page when the Multistack countermeasure is installed. In practice this may not be the case. In the worst case, it points to the end. As a result, only a few bytes can be stored on the first page of stack 2 to 4. However, the original implementation of Multistack could be adjusted easily. By allocating more space on stack 1, memory consumption on the other stacks may decrease with one page.

Programming style It is clear that the way a program is written will have a huge impact on the structure of the stack. A programmer could opt solving a problem iteratively instead of using recursive calls. This would prevent the size of the stacks from growing rapidly and wasting memory.

Also by allocating large variables on the heap, more pages could be reused on the stack with less fragmentation. This could be implemented in a compiler as a heuristic.

Performance evaluation

To evaluate the performance of the different Multistack implementations, we ran the telecom and consumer suite of the MiBench benchmark [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] on a Sharp PC-z1 running Ubuntu Linux 9.04 (kernel 2.6.28). This netbook is equipped with an ARM Cortex-A8 CPU running at 800 MHz and 512 MiB RAM. The countermeasures were implemented in the gcc-4.3.3 revision 143643 compiler. The benchmark was compiled with -O0 -fomit-frame-pointer flags. To receive accurate results, each application was provided the large input set and run 500 times. Table 2 displays the results.

Explaining and predicting performance overhead is complex since there are many factors to consider. Two of the most relevant factors are discussed next.

Increased number of instructions There are two obvious places where instructions may be added. First, all techniques, with the exception of the original Multistack, require the prologues and epilogues to be modified to allocate memory on the stack. Obviously, this will have a negative impact on performance in case an application makes many function calls, for example, if recursion is used.

Second, additional instructions may be required to access a variable on a stack. Applications such as fft and ifft read and write to stack 2 very often. Hence, the time to access this stack will have a huge impact on their performance.

In case of the original Multistack implementation, the immediate offset in the load/store instruction can not be used to load/store a value on stack 2, 3 or 4 since this offset is too large. Therefore an extra addition is required, leading to a performance loss of 15.1% for fft and even 19.08% for ifft. In case dedicated registers are used to store the different stack pointers, the stack-based variables can be accessed in only one instruction. This leads to a much lower performance loss; 6.99% for ftt and 9.03% for ifft.

In case the stack pointers are packed, the accessed variable's location will have an influence as well. Acesses to stack 2 or 4 only require a few instructions. Variables on stack 3 are much harder to access since their stack pointer is scattered over 2 registers. As a result, accessing stack 3 is slower than stack 2 or 4. With the exception of the dedicated registers approach, the same applies for the other implementations; variables on stack 1 can be addressed by simply specifying an offset to register sp. For other stacks, more instructions are needed.

When main memory needs to be accessed, the order wherin the instructions are scheduled and the memory's access time will also play an import role.

Register pressure The dedicated register approach does not require additional instructions to access a stack-based variable. Therefore, it was able to execute the fft and ifft applications much faster. However, by reserving three registers, register pressure may increase, leading to a performance deterioration. To discover the impact on the selected applications, each was run unprotected with 3 reserved registers but no significant impact on performance was found.

Summary Many factors influence the performance of the different presented techniques. On average (see table 2), all the presented techniques perform better than the original Multistack implementation. By storing the stack pointers at a fixed location, performance overhead is reduced from 4.91% (original Multistack) to 4.57%. Packing the stack pointers in two registers further reduces the performance overhead to 4.39%. The dedicated register approach is on average even 1% faster (3.91%). In case for each application the best performing countermeasure is chosen while requiring that no physical memory is wasted, the average performance overhead is reduced to 3.30%.

Discussion and ongoing work

Besides the possible implementations presented in section 4, another one was developed, but omitted due to page limits. As the technique described in sec- tion 4.3, the stack pointers are stored in main memory but a reserved register stores their location. This eliminates the instruction to load the location in a register. However, its performance proved slightly worse in practice. We assume that the processor on our test was not able to schedule the instructions as well as the fixed address approach. More detailed information can be found in [START_REF] Strackx | Protecting mobile devices against stack-based buffer overflows. Master'[END_REF]. Using static analysis, many of the presented approaches can still be improved. At compile time it could be determined that some of the stacks will never be used by the application (see section 5.2). This knowledge could be applied to reserve less registers for the dedicated register approach. Combining this knowledge with a more guided estimation of the maximum size of each stack, the packed stack pointers technique could be modified to reduce the number of registers reserved and/or store less bits of each stack pointer.

Also a heuristic could be used in case registers are reserved to reduce the register pressure; functions may use these registers to store intermediate values, as long as their contents is restored before they are used by the function itself or one that it calls (in)directly.

The main goal was to eliminate the memory usage of the original Multistack implementation. Not only do all proposed implementations satisfy this goal, section 5.3 showed that on average they also reduce performance overhead. The dedicated registers approach not only outperforms all other implementations, but it can also be adapted easily for multithreaded applications, a situation not supported by the original approach.

Related work

Many countermeasures to protect applications against (stack-based) buffer overflow attacks have been developed during the last decades. In this section we briefly highlight the differences between our and existing approaches to the problem. A more elaborate overview can be found in [START_REF] Erlingsson | Handbook of information and communication security[END_REF][START_REF] Younan | Code injection in c and c++ : A survey of vulnerabilities and countermeasures[END_REF][START_REF] Younan | Efficient countermeasures for software vulnerabilities due to memory management errors[END_REF].

One obvious way to defend applications against buffer overflow attacks is to add bound checks [START_REF] Kendall | Bcc: Runtime checking for C programs[END_REF], however when implemented for C, their performance overhead is significantly larger than other countermeasures.

Another approach uses a type system and runtime checks to create safe languages where the existence of buffer overflow vulnerabilities are prevented. There are safe languages, referred to as safe dialects, that remain as close to C or C++ as possible. However, their performance overhead is also significant [START_REF] Larus | Righting software[END_REF][START_REF] Necula | CCured: Type-safe retrofitting of legacy software[END_REF].

The most often applied countermeasure in practice uses random data to detect buffer overflows or try to prevent their successful execution. StackGuard [START_REF] Cowan | Stackguard: automatic adaptive detection and prevention of buffer-overflow attacks[END_REF][START_REF] Etoh | Protecting from stack-smashing attacks[END_REF] is an example of such a probabilistic countermeasure. It places a random value, called canary, in front of each return address on the stack. An attacker that overflows a stack-based buffer up to a return address, will modify the canary. The canary check at each function's epilogue will notice this modification and prevent the exploit before the return address is used.

However, by overwriting a pointer, an attacker is able to write to an arbitrary memory location, when the application dereferences the pointer for such an instruction. In case he/she is also able to control the written value, the execution path can be redirected to injected code, for example, by overwriting a return address [START_REF] Bulba | Kil3r: Bypassing stackguard and stackshield[END_REF]. Since the canary is not modified, StackGuard is not able to detect the attack. ProPolice [START_REF] Etoh | Protecting from stack-smashing attacks[END_REF] entangles the canary and the return address by taking the xor function from a random value and the return address. This allows the detection of any change to the return address.

Address space layout randomization (ASLR) [START_REF] Team | Documentation for the PaX project[END_REF][START_REF] Bhatkar | Address obfuscation: An efficient approach to combat a broad range of memory error exploits[END_REF] randomizes the location of program data and code. As a result, redirecting execution to shellcode is hard.

While these last approaches are efficient, they rely on keeping memory locations secret. However, programs could also contain "buffer overreads" [START_REF] Strackx | Breaking the memory secrecy assumption[END_REF] or other vulnerabilities like format string vulnerabilities [START_REF] Shankar | Detecting format string vulnerabilities with type qaualifiers[END_REF], which allow attackers to print out memory locations. Such memory leaking vulnerabilities could allow attackers to bypass this type of countermeasure.

Other countermeasures take advantage of hardware to protect against buffer overflows. Francillon et. al. [START_REF] Francillon | Defending Embedded Systems Against Control Flow Attacks 23[END_REF] implement a similar approach as Multistack, but only two stacks are supported and the presence of specialized hardware is required. The techniques presented in this paper take advantage of a Memory Management Unit (MMU) to create guard pages, hardware that can also be used to facilitate additional countermeasures (e.g. non-executable memory [23,[START_REF] Team | Documentation for the PaX project[END_REF]) and already present in many modern processors.

Conclusion

The Multistack countermeasure effectively protects against stack-based buffer overflows, defeating many state-of-the-art attacks. Unfortunately, its straightforward port to the ARMv7 instruction set, does not reach the same efficiency as on the x86 platform and it suffers from high memory overhead.

In this paper we presented three approaches that reduce memory overhead up to 28%. In addition, each approach also reduces performance overhead. The best performing has an overhead of only 3.91% and supports multi-threaded applications, a situation not supported by the original Multistack implementation.

  v o i d copy ( c h a r * s r c , c h a r * d s t ) { i n t i = 0 ; c h a r c u r r = s r c [ 0 ] ; w h i l e ( c u r r ) { d s t [ i ] = c u r r ; i ++; c u r r = s r c [ i ] ; } } Listing 1.1. A C function that is vulnerable to a buffer overflow.

Fig. 1 .

 1 Fig. 1. Multistack stack layout for 4 stacks

Fig. 2 .

 2 Fig. 2. Depending on the number, size and other factors, physical pages may remain unused (white boxes), internally fragmented (gray boxes) or completely used (black boxes). Compacting the stack minimizes the number of internally fragmented pages.

Table 1 .

 1 From the MiBench benchmark the telecom and consumer suites were selected. The different applications from these suites were run protected with the original Multistack implementation. This table displays the maximum number of memory locations used on the different stacks. The size in bytes is displayed together with the used physical pages. The last column displays how much memory is saved by compacting the stacks.

		stack 1		stack 2		stack 3		stack 4		Total		Potential gain
	application set bytes pages	bytes pages	bytes pages bytes pages	bytes pages bytes pages	%
	qsort	small 796	2	0	0 7,680,000	0	0	0 7,680,796 1,878 8,192	2 0.11%
	qsort	large 948	3 1,200,000 293	0	0	0	0 1,200,948 296 8,192	2 0.68%
	FFT	both 360	1	48	1	0	0	0	0	408	2	0	0	0%
	IFFT	both 360	1	48	1	0	0	0	0	408	2	0	0	0%
	gsm (enc.) both 544	1	957	1	0	0	0	0	1,501	2	0	0	0%
	gsm (dec.) both 540	1	932	1	0	0	0	0	1,472	2	0	0	0%
	jpeg (enc.) both 436	1	2,960	1	132	1	257	1	3,785	4	0	0	0%
	jpeg (dec.) both 480	1	1,484	1	132	1	257	1	2,353	4	0	0	0%
	lame	both 1,444	7	56,044	15	4	1 16,389	6	73,881	29 32,768	8 27.59%
	mad	small 1,216	3	7,192	1	632	1 27,674	8	36,714	15 16,384	4 26.67%
	mad	large 1,216	2	368	1	404	1 27,674	8	29,662	12 8,192	2 16.67%
	tiff2bw	both 472	1	100	1	0	0 1,104	1	1,676	3	0	0	0%
	tiff2rgba both 464	1	102	1	0	0 1,024	1	1,590	3	0	0	0%
	tiffdither both 1,044	1	92	1	0	0 1,104	1	2,240	3	0	0	0%
	tiffmedian both 532	1	228	1	0	0	80	1	840	3	0	0	0%

Table 2 .

 2 Running the telecom and consumer suite of the MiBench benchmark shows that the dedicated register approach, on average, outperforms the other approaches. ± 0.01 1.21 ± 0.01 19.08% 1.11 ± 0.01 9.03% 1.13 ± 0.01 10.95% 1.13 ± 0.01 10.65% gsm (enc.) 6.32 ± 0.02 6.33 ± 0.02 0.08% 6.32 ± 0.02 0.05% 6.32 ± 0.03 0.05% 6.33 ± 0.03 0.08% gsm (dec.) 2.68 ± 0.02 2.68 ± 0.02 0.14% 2.68 ± 0.02 0.15% 2.68 ± 0.02 0.10% 2.68 ± 0.02 0.14% jpeg (enc.) 0.34 ± 0.01 0.41 ± 0.01 19.31% 0.43 ± 0.01 25.53% 0.43 ± 0.01 26.19% 0.44 ± 0.01 27.

		unprot.	original		dedicated regs.		packed sp		fixed address
	application	sec	sec	%	sec	%	sec	%	sec	%
	FFT	1.25 ± 0.01 1.43 ± 0.01 15.10% 1.33 ± 0.01 6.99% 1.36 ± 0.01 8.93% 1.36 ± 0.01 8.88%
	IFFT	1.02 12%
	jpeg (dec.) 0.09 ± 0.01 0.09 ± 0.01 0.00% 0.09 ± 0.01 -0.34% 0.09 ± 0.01 0.67% 0.09 ± 0.01 0.22%
	lame	26.42 ± 0.06 26.56 ± 0.08 0.53% 26.40 ± 0.07 -0.05% 26.64 ± 0.05 0.86% 26.53 ± 0.05 0.43%
	mad	1.44 ± 0.01 1.48 ± 0.01 2.78% 1.50 ± 0.01 4.51%	-	-% 1.57 ± 0.01 8.95%
	tiff2bw	0.94 ± 0.01 0.94 ± 0.01 -0.46% 0.94 ± 0.01 -0.11% 0.94 ± 0.01 -0.54% 0.94 ± 0.01 -0.27%
	tiff2rgba	2.57 ± 0.02 2.56 ± 0.02 -0.13% 2.57 ± 0.02 -0.06% 2.57 ± 0.02 -0.03% 2.57 ± 0.02 0.03%
	tiffdither	3.38 ± 0.02 3.46 ± 0.02 2.35% 3.41 ± 0.02 1.03% 3.42 ± 0.02 1.22% 3.46 ± 0.02 2.47%
	tiffmedian 2.64 ± 0.02 2.64 ± 0.02 0.18% 2.64 ± 0.02 0.18% 2.63 ± 0.02 -0.14% 2.63 ± 0.02 -0.28%
	average			4.91%	3.91%	4.39%	4.57%

A memory page without any permission. Any attempt to read, write or execute from this page will result in a segmentation fault.

1 MiB = 1 mebibytes = 2 20 bytes (standardized by IEC 60027-2)

Acknowledgments. We thank Thomas Walter and Sven Lachmund for the discussions on this topic, and the feedback on an earlier draft of the paper. This research is partially funded by NTT Docomo Eurolabs, by the Interuniversity Attraction Poles Programme Belgian State, Belgian Science Policy, and by the Research Fund K.U.Leuven.


Benoît Chevallier-Mames

Jean-Sébastien Coron
email: jean-sebastien.coron@uni.lu

Noel Mccullagh
email: noel.mccullagh@computing.dcu.ie

David Naccache
email: david.naccache@ens.fr

Michael Scott

Secure Delegation of Elliptic-Curve Pairing

Keywords: Elliptic-curve pairing, secure delegation protocol, Boneh-Franklin IBE

In this paper we describe a simple protocol for secure delegation of the elliptic-curve pairing. A computationally limited device (typically a smart-card) will delegate the computation of the pairing e(A, B) to a more powerful device (for example a PC), in such a way that 1) the powerful device learns nothing about the points A and B, and 2) the limited device is able to detect when the powerful device is cheating.

Introduction

Since the discovery of the first practical identity-based cryptosystem based on the elliptic-curve pairing [START_REF] Boneh | Identity based encryption from the Weil pairing[END_REF], pairing-based cryptography has become a very active research area. Many pairing-based protocols have been proposed with novel and attractive properties, for example for key-exchange [START_REF] Joux | A one round protocol for tripartite Diffie-Hellman[END_REF] and digital signatures [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF].

The increasing popularity of pairing-based cryptosystems and their foreseeable deployment in computationally constrained devices such as smart-cards and dongles spurred recent research in the implementation of pairing (e.g. [START_REF] Scott | Compressed Pairings[END_REF]). Unfortunately, although pairing is a cubic-time operation, pairing implementation attempts in limited devices such as smart-cards reveal that the embedded code may be slow, resourceconsuming and tricky to program.

Given that several PC-based pairing libraries exist, it seems natural to find-out whether a smart-card could interact with such packages to privately compute the elliptic-curve pairing. Note that beyond preserving operands from preying eyes, the card must also ascertain that bogus libraries don't mislead it into generating wrong results.

In this paper, we propose a simple protocol for secure delegation of elliptic-curve pairing. A computationally limited device (for example a smart-card) will delegate the computation of the elliptic-curve pairing e(A, B) to a more powerful device (for example a PC), in such a way that 1) the powerful device learns nothing about the points A and B, and 2) the limited device is able to detect when the powerful device is cheating. The limited device will restrict itself to simple curve or field operations. We also describe some efficient variants of our protocol if one of the points A and B or both are already publicly known, or when the point A can be considered as constant, as it is the case for the Boneh-Franklin identity-based encryption scheme [START_REF] Boneh | Identity based encryption from the Weil pairing[END_REF].

Preliminaries

Bilinear Map

Our protocol for secure pairing delegation is actually more general than just ellipticcurve pairing : as most pairing-based cryptosystems, it works for any bilinear map. Therefore, we briefly review the basic facts about bilinear maps. We follow the notations in [START_REF] Boneh | Short signatures from the Weil pairing[END_REF]. We refer the reader to [START_REF] Menezes | Elliptic Curve Public Key Cryptosystems[END_REF] for an extensive background on ellipticcurve pairing.

1. G 1 and G 2 are two (additive) cyclic groups of prime order p;

2. G 1 is a generator of G 1 and G 2 is a generator of G 2 ; 3. ψ is a computable isomorphism from G 1 to G 2 with ψ(G 1 ) = G 2 ;
4. e is a computable bilinear map e :

G 1 × G 2 → G T ;
5. G T is a multiplicative cyclic group of order p.

A bilinear map is a map e : G 1 × G 2 → G T with the following properties :

1. Bilinear: for all U ∈ G 1 , V ∈ G 2 and a, b ∈ Z Z, e(a • U, b • V ) = e(U, V ) a•b 2. Non-degenerate: e(G 1 , G 2 ) = 1
Note that the previous conditions imply that e(G 1 , G 2 ) is a generator of G T .

Computational Indistinguishability

We recall the notion of computational indistinguishability [START_REF] Goldwasser | Probabilistic Encryption[END_REF], which will be used in the definition of secure pairing delegation. Two distribution ensemble X = {X n } n∈N and Y = {Y n } n∈N are said to be computationally indistinguishable and denoted X c ≡ Y if for every (probabilistic) polynomial-time algorithm A, and every c > 0, there exists an integer N such that for all n > N

|Pr[A(X n ) = 1] -Pr[A(Y n ) = 1]| < 1 n c
3 Secure Pairing Delegation

In this section, we formalize the security notions for secure pairing delegation. Our setting is the following : a computationally limited device, called the card and denoted C, will delegate the computation of the pairing e(A, B) to a more powerful device, called the terminal and denoted T . Both devices C and T are actually probabilistic polynomial-time Turing machines. We denote by View T (A, B) the terminal's view when interacting with C with points A, B. The terminal's view includes the randomness used by the terminal, and the data received from the card. The security notions could be formalized in the general framework of secure multiparty computation (for standard definitions, see for example [START_REF] Canetti | Security and Composition of Multiparty Cryptographic Protocols[END_REF]). However, we observe that our setting is much simpler than for general secure multiparty computation : the terminal has no secret and outputs nothing; moreover only the terminal can be malicious. Therefore, we adapt the general notions for secure multiparty computation to our restricted setting. We obtain that a protocol for pairing delegation is secure if it satisfies the three following security notions :

Completeness : after completion of the protocol with an honest terminal, the card obtains e(A, B), except with negligible probability.

Secrecy : a (possibly cheating) terminal should not learn any information about the points A and B. More formally, for any malicious terminal T , there exists a simulator S such that for any A, B, the output of S is computationally indistinguishable from the terminal's view :

S c ≡ View T (A, B)
Note that the simulator S is not given A, B as input.

Correctness : The card should be able to detect a cheating terminal, except with negligible probability. More formally, for any cheating terminal T and for any A, B, the card outputs either ⊥ or e(A, B), except with negligible probability.

In order to delegate the pairing computation, one could think of the following protocol. On input A, B, the card could generate random x, y and ask the terminal to compute the pairing :

α = e(x • A, y • B)
The card would then recover e(A, B) by simply computing :

e(A, B) = α (x•y) -1
However, it is easy to see that this is not a secure pairing delegation protocol. Namely, although the terminal learns nothing about A, B, the card cannot detect a cheating terminal. Namely, if the terminal outputs α r for some r instead of α, the card will obtain e(A, B) r instead of e(A, B), and will not be able to detect the cheating terminal. In the following, we describe a secure pairing delegation protocol, such that if the terminal is cheating, then the card outputs either the correct e(A, B) or nothing with overwhelming probability.

Description

The card and the terminal are given as input a description of the groups G 1 , G 2 and G T , and a description of the bilinear map e :

G 1 × G 2 → G T .
The card and the terminal receive the generators G 1 and G 2 ; we also assume that the card receives e(G 1 , G 2 ). The card is given as input the points A and B and must eventually output e(A, B). Recall that G 1 , G 2 and G T are additive groups of order p.

1. The card generates a random g 1 ∈ Z Z p and a random g 2 ∈ Z Z p , and queries the three following pairings to the terminal :

α 1 = e(A + g 1 .G 1 , G 2 ), α 2 = e(G 1 , B + g 2 .G 2 ) α 3 = e(A + g 1 .G 1 , B + g 2 .G 2 ) 2. The card checks that α 1 , α 2 , α 3 ∈ G T , by checking that (α i ) p = 1 for i = 1, 2, 3.
Otherwise, the card outputs ⊥ and halts. 3. The card computes a purported value for e(A, B):

e AB = α -g 2 1 • α -g 1 2 • α 3 • e(G 1 , G 2 ) g 1 g 2 (1)
4. The card generates four random values a 1 , r 1 , a 2 , r 2 ∈ Z Z p and queries the pairing :

α 4 = e(a 1 .A + r 1 .G 1 , a 2 .B + r 2 .G 2 )
5. The card computes :

α ′ 4 = (e AB ) a 1 a 2 • (α 1 ) a 1 r 2 • (α 2 ) a 2 r 1 • e(G 1 , G 2 ) r 1 r 2 -a 1 g 1 r 2 -a 2 g 2 r 1 (2)
and checks that α ′ 4 = α 4 . In this case, the card outputs e AB ; otherwise it outputs ⊥.

Security Proof

The following theorem shows that our protocol is secure : Theorem 1. The previous protocol is a secure pairing delegation protocol.

Proof. The completeness property is easily established. We obtain from the bilinear property :

e(A + g 1 .G 1 , B + g 2 .G 2 ) = e(A, B) • e(A, G 2 ) g 2 • e(G 1 , B) g 1 • e(G 1 , G 2 ) g 1 g 2
Then, for an honest terminal, we have :

α 1 = e(A + g 1 .G 1 , G 2 ) = e(A, G 2 ) • e(G 1 , G 2 ) g 1 (3)
α 2 = e(G 1 , B + g 2 .G 2 ) = e(G 1 , B) • e(G 1 , G 2 ) g 2 (4
)

α 3 = e(A + g 1 .G 1 , B + g 2 .G 2 ) (5)
Combining the four previous equations, we obtain :

α 3 = e(A, B) • (α 1 ) g 2 • (α 2 ) g 1 • e(G 1 , G 2 ) -g 1 g 2
which, using (1), shows that the card computes the correct e AB = e(A, B). Moreover, using :

α 4 = e(a 1 .A + r 1 .G 1 , a 2 .B + r 2 .G 2 ) = e(A, B) a 1 a 2 • e(A, G 2 ) a 1 r 2 • e(G 1 , B) r 1 a 2 • e(G 1 , G 2 ) r 1 r 2
we obtain from equations ( 3) and (4) :

α 4 = (e AB ) a 1 a 2 • (α 1 ) a 1 r 2 • (α 2 ) r 1 a 2 e(G 1 , G 2 ) r 1 r 2 -a 1 g 1 r 2 -a 2 g 2 r 1
which, using (2), gives α 4 = α ′ 4 and shows that the card eventually outputs the correct e AB = e(A, B).

The secrecy property follows from the fact that the terminal receives only random, independently distributed points in the groups G 1 and G 2 . Therefore, the simulator S simply consists in running the terminal T with randomly generated points. The simulator's output and the terminal's view when interacting with C are then identically distributed.

The correctness property is established as follows : we show that if the value e AB computed by the card at step 3 is not equal to e(A, B), then the element α ′ 4 computed by the card at step 5 has a nearly uniform distribution in G T , independent from the terminal's view. Then, the probability that α 4 = α ′ 4 at step 5 will be roughly 1/p. Therefore, the card will output ⊥, except with negligible probability.

We let U = a

1 .A + r 1 .G 1 and V = a 2 .B + r 2 .G 2 . Moreover, we let a, b, u, v ∈ Z Z p be such that A = a.G 1 , B = b.G 2 , U = u.G 1 , V = v.G 2 , which gives : u = a 1 • a + r 1 (6) v = a 2 • b + r 2 (7)
The card checks that α 1 , α 2 , α 3 ∈ G T . Therefore, we must have e AB ∈ G T , and since e(G 1 , G 2 ) is a generator of G T , we can let β 1 , β 2 , β 3 ∈ Z Z p be such that :

α 1 = e(A, G 2 ) • e(G 1 , G 2 ) g 1 +β 1 ( 8
)
α 2 = e(G 1 , B) • e(G 1 , G 2 ) g 2 +β 2 (9) e AB = e(A, B) • e(G 1 , G 2 ) β 3 (10)
Therefore, the value e AB is correct iff β 3 = 0.

From the previous observation, we also have α ′ 4 ∈ G T . Therefore, we can assume that α 4 ∈ G T , since otherwise α ′ 4 = α 4 and the card outputs ⊥. Then we can let β 4 , β ′ 4 ∈ Z Z p be such that :

α 4 = e(U, V ) • e(G 1 , G 2 ) β 4 (11) α ′ 4 = e(U, V ) • e(G 1 , G 2 ) β ′ 4 (12)
Therefore, the card outputs e AB iff β 4 = β ′ 4 . In the following, we assume that u = 0 and v = 0. Since (u, v) is uniformly distributed in Z Z p , this happens with probability (1 -1/p) 2 ≥ 1 -2/p.

We show that if β 3 = 0, then β ′ 4 has a nearly uniform distribution in Z Z p , independent from the terminal's view, and therefore β 4 = β ′ 4 happens with negligible probability.

From equations ( 2), ( 8), (9), (10) and (12), we obtain :

β ′ 4 = a 1 a 2 β 3 + a 1 r 2 β 1 + a 2 r 1 β 2 (13)
The terminal's view includes the points A+g 1 .G 1 , B +g 2 .G 2 , U and V and the group elements α 1 , α 2 , α 3 and α 4 . Therefore, the terminal's view is entirely determined by (β 1 , β 2 , β 3 , β 4 , u, v, r), where r is the randomness used by the terminal. Moreover, given (β 1 , β 2 , β 3 , β 4 , u, v, r), the element (a 1 , a 2 ) is uniformly distributed over Z Z 2 p . From equations ( 6), ( 7) and (13), we obtain :

β ′ 4 = a 1 a 2 (β 3 -bβ 1 -aβ 2 ) + a 1 (vβ 1 ) + a 2 (uβ 2 )
Lemma 1. Let p be a prime integer and let a, b, c, d ∈ Z Z such that (a, b, c) = (0, 0, 0). Then the number of solutions (x, y) ∈ Z Z 2 p to the polynomial equation a

• xy + b • x + c • y + d = 0 mod p is at most 2p -1.
Proof. The proof is straightforward and is therefore omitted. Since u, v = 0, then β 3 = 0 implies (β 3 -bβ 1 -aβ 2 , vβ 1 , uβ 2 ) = (0, 0, 0). Then using the previous lemma, for any γ ∈ Z Z p , the probability over (a 1 , a

2 ) ∈ Z Z 2 p that β ′ 4 = γ is such that : Pr[β ′ 4 = γ] ≤ 2p -1 p 2 ≤ 2 p
Therefore, if β 3 = 0, the probability that β ′ 4 = β 4 is at most 2/p. Since we have that u = 0 or v = 0 with probability at most 2/p, we conclude that if e AB = e(A, B), then the card outputs ⊥, except with probability at most 4/p.

⊓ ⊔

Note that the security of the protocol is not based on any computational assumption; namely the protocol achieves unconditional security.

Efficiency

Our protocol requires a total of 4 scalar multiplications in G 1 and G 2 , and a total of 10 exponentiations in G T . Our protocol is actually a one-round protocol since the four pairing queries can be performed in the same round.

Efficient Variants with Public A or B

In this section, we describe more efficient variants of our protocol, when one of the points A and B or both are already publicly known.

For example, when decrypting with Boneh and Franklin's identity-based encryption scheme [START_REF] Boneh | Identity based encryption from the Weil pairing[END_REF], the point A is the user's private key, and the point B is some part of the ciphertext. Therefore, the point B is already publicly known and does not need to be protected. Similarly, when encrypting with Boneh and Franklin's scheme, the point A is the recipient's identity, and the point B is the trusted party's public-key. Therefore, both points A and B are already publicly known and don't need to be protected.

When the point B is publicly known, the definition of the secrecy property is modified by simply giving B to the simulator. When both points A and B are publicly known, the secrecy property is not necessary anymore.

Secure Pairing Delegation with Public B

The protocol is the same as the protocol described in the previous section, except that we can take g 2 = 0 since the point B does not need to be protected.

1. The card generates a random g 1 ∈ Z Z p and queries the three following pairings to the terminal :

α 1 = e(A + g 1 .G 1 , G 2 ), α 2 = e(G 1 , B), α 3 = e(A + g 1 .G 1 , B)
2. The card checks that α 1 , α 2 , α 3 ∈ G T , by checking that (α i ) p = 1 for i = 1, 2, 3.

Otherwise, the card outputs ⊥ and halts. 3. The card computes a purported value for e(A, B):

e AB = (α 2 ) -g 1 • α 3 (14)
4. The card generates four random values a 1 , r 1 , a 2 , r 2 ∈ Z Z p and queries the pairing :

α 4 = e(a 1 .A + r 1 .G 1 , a 2 .B + r 2 .G 2 )
5. The card computes :

α ′ 4 = (e AB ) a 1 a 2 • (α 1 ) a 1 r 2 • (α 2 ) a 2 r 1 • e(G 1 , G 2 ) r 1 r 2 -a 1 g 1 r 2 (15)
and checks that α ′ 4 = α 4 . In this case, the card outputs e AB ; otherwise it outputs ⊥.

The protocol is more efficient than the protocol of Section 4 since only 3 scalar multiplications in G 1 and G 2 , and 8 exponentiations in G T are required.

Theorem 2. The previous protocol with public B is a secure pairing delegation protocol.

Proof. The proof is similar to the proof of theorem 1 and is therefore omitted.

Secure Pairing Delegation with Public A and B

The protocol is similar to the previous protocol except that we can also take g 1 = 0 since A does not need to be protected.

1. The card queries the three following pairings to the terminal :

α 1 = e(A, G 2 ), α 2 = e(G 1 , B), α 3 = e(A, B) 2. The card checks that α 1 , α 2 , α 3 ∈ G T , by checking that (α i ) p = 1 for i = 1, 2, 3.
Otherwise, the card outputs ⊥ and halts. 3. The card computes a purported value for e(A, B): e AB = α 3 4. The card generates four random values a 1 , r 1 , a 2 , r 2 ∈ Z Z p and queries the pairing :

α 4 = e(a 1 .A + r 1 .G 1 , a 2 .B + r 2 .G 2 )
5. The card computes :

α ′ 4 = (e AB ) a 1 a 2 • (α 1 ) a 1 r 2 • (α 2 ) a 2 r 1 • e(G 1 , G 2 ) r 1 r 2
and checks that α ′ 4 = α 4 . In this case, the card outputs e AB ; otherwise it outputs ⊥.

The protocol is more efficient than the protocol of Section 4 since only 2 scalar multiplications in G 1 and G 2 , and 7 exponentiations in G T are required.

Theorem 3. The previous protocol with public A and B is a secure pairing delegation protocol.

Proof. The proof is similar to the proof of theorem 1 and is therefore omitted.

Efficient Variant for Constant Point

In this section, we provide two efficient variants of the previous protocol, when the point A can be considered as constant. In the first protocol, both points A and B are public, whereas in the second protocol, A is private whereas B is public.

Those two variants are particularly useful for Boneh and Franklin's identitybased encryption scheme [START_REF] Boneh | Identity based encryption from the Weil pairing[END_REF]. Namely, when encrypting with Boneh and Franklin's IBE, the point B is the trusted server public-key, and the point A is the receiver's identity-based public-key. Therefore, B can be considered as constant, and both A and B are public. This corresponds to the first protocol (with constant B instead of constant A, but the protocol modification is straightforward).

Moreover, when decrypting with Boneh and Franklin's IBE, the point A is the user's private key, and the point B is some part of the ciphertext. Therefore, A can be considered as constant and private, whereas B can be considered as public. This corresponds to the second protocol.

Efficient Variant for constant A and public A, B

As in the previous protocol, the card and the terminal are given as input a description of the groups G 1 , G 2 and G T , and a description of the bilinear map e : G 1 × G 2 → G T . Moreover, the card receives e(A, Q) for some random Q ∈ G 2 . The point Q and e(A, Q) are kept private by the card. The card is given as input the point B and must eventually output e(A, B).

1. The card generates a random r ∈ Z Z p and queries the following pairings to the terminal :

α 1 = e(A, B), α 2 = e(A, r • B + Q) 2. The card checks that (α 1 ) r • e(A, Q) = α 2 (16)
and that (α 1 ) p = 1. In this case, it outputs α 1 , otherwise it outputs ⊥.

The protocol is more efficient than the protocol of section 5.2 since it requires only one scalar multiplication and 2 exponentiations in G T .

Theorem 4. The previous protocol with constant public A and public B is a secure pairing delegation protocol.

Proof. The completeness property is straightforward to establish. The protocol's correctness is showed as follows :

Let b be such

B = b • G 2 . Let q be such that Q = q • G 2 . Let u = r • b + q mod p which gives r•B +Q = u•G 2 .
We have that the terminal's view is entirely determined by (b, u) and by the randomness used by T . Since r and q are randomly generated in Z p , we obtain that the distribution of r is independent from the terminal's view. Let β 1 , β 2 be such that :

α 1 = e(A, B) • e(A, G 2 ) β 1 α 2 = e(A, r • B + Q) • e(A, G 2 ) β 2
We have that β 1 , β 2 are a function of the terminal's view, and that α 1 = e(A, B) if β 1 = 0. Moreover, we obtain from (16) that the card outputs α 1 iff :

r • β 1 = β 2 mod p (17)
Assume now that β 1 = 0. Then since β 1 and β 2 are a function of the terminal's view, and the distribution of r is independent from the terminal's view, equality (17) holds with probability at most 1/p. Therefore, for any cheating terminal, the card outputs either ⊥ or the correct e(A, B), except with probability at most 1/p. ⊓ ⊔

Efficient variant for constant private A and for public B

As in the previous protocol, the card and the terminal are given as input a description of the groups G 1 , G 2 and G T , and a description of the bilinear map e :

G 1 × G 2 → G T .
Moreover, the card receives e(A, Q) for some random Q ∈ G 2 . The points A, Q and the value e(A, Q) are kept private by the card. The card is given as input the point B and must eventually output e(A, B).

1. The card generates random x, y, z ∈ Z p and queries the following pairings to the terminal :

α 1 = e(x • A, B), α 2 = e(y • A, z • (B + Q))
2. The card computes :

e AB = (α 1 ) x -1 , α 3 = (α 2 ) (yz) -1 3. The card checks that e AB • e(A, Q) = α 3 (18)
and that (e AB ) p = 1. In this case, it outputs e AB ; otherwise it outputs ⊥.

The protocol is more efficient than the protocol of section 5.1 as it requires only 3 scalar multiplications and 3 exponentiations in G T .

Theorem 5. The previous protocol with constant private A and public B is a secure pairing delegation protocol.

Proof. The protocol's completeness is easily established. The protocol's secrecy follows from the fact that the terminal receives only randomly distributed points. The protocol's correctness is established as follows :

Let b be such

B = b • G 2 . Let q be such that Q = q • G 2 . Let u = z • (b + q) mod p which gives z • (B + Q) = u • G 2 .
The terminal's view is then entirely determined by (b, u, x • A, y • A) and by the randomness used by T . Since z and q are randomly generated in Z p , we obtain that the distribution of z is independent from the terminal's view.

Let β 1 , β 2 be such that :

α 1 = e(x • A, B) 1+β 1 α 2 = e(y • A, z • (B + Q)) 1+β 2
We have that β 1 and β 2 are a function of the terminal's view. Moreover, we obtain : Then since b, β 1 , β 2 are a function of the terminal's view, and the distribution of q is uniform in Z p , independent of the terminal's view, we obtain that if β 1 = 0, the equality (19) holds with probability at most 1/p. Therefore, for any cheating terminal, the card outputs either ⊥ or the correct e(A, B), except with probability 1/p. ⊓ ⊔

Conclusion

In this paper we have described a simple protocol for secure delegation of ellipticcurve pairing. Our protocol allows a computationally limited device (for example a smart-card) to delegate the computation of the pairing e(A, B) to a more powerful device (for example a PC), in such a way that 1) the powerful device learns nothing about the points A and B, and 2) the limited device is able to detect when the powerful device is cheating. We have also described more efficient variants of our protocol when one of the points or both are already publicly known, and when one of the points can be considered as constant.

We observe that our protocols achieve unconditional security. An interesting research direction would be to further optimize the protocols by trading-off unconditional security against computational security. A second interesting question consists in bounding the number of protocol rounds (passes) necessary to delegate pairing in diverse contexts.

e 1 α 3 =

 13 AB = e(A, B) 1+β e(A, B + Q) 1+β 2Therefore, e AB = e(A, B) iff β 1 = 0. Moreover, we obtain from (18) that the card outputs e AB if :e(A, B + Q) β 1 = e(A, B) β 2 which gives : b • β 1 = (b + q) • β 2 mod p (19)


Christophe Giraud
email: c.giraud@oberthur.com

Erik W Knudsen

Michael Tunstall
email: tunstall@cs.bris.ac.uk

Improved Fault Analysis of Signature Schemes

Keywords: Fault analysis, Signature schemes, Smart card

, Giraud and Knudsen presented the first fault analysis of DSA, ECDSA, XTR-DSA, Schnorr and ElGamal signatures schemes that considered faults affecting one byte. They showed that 2304 faulty signatures would be expected to reduce the number of possible keys to 2 40 , allowing a 160-bit private key to be recovered. In this paper we show that Giraud and Knudsen's fault attack is much more efficient than originally claimed. We prove that 34.3% less faulty signatures are required to recover a private key using the same fault model. We also show that their original way of expressing the fault model under a system of equations can be improved. A more precise expression allows us to obtain another improvement of up to 47.1%, depending on the values of the key byte affected.

Introduction

Since their introduction in 1996 by Boneh, DeMillo and Lipton [START_REF] Bellcore | New Threat Model Breaks Crypto Codes[END_REF], fault attacks have been widely studied from both practical and theoretical points of view. This type of attack poses a serious threat that needs to be considered when implementing cryptographic algorithms on embedded devices [START_REF] Bar-El | The Sorcerer's Apprentice Guide to Fault Attacks[END_REF]. Once a suitable mechanism for injecting a fault is found, fault attacks would allow an attacker to break any cryptographic implementation faster than any other kind of attacks.

The following examples speak for themselves: a DES secret key can be revealed by using two faulty ciphertexts [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystem[END_REF][START_REF] Giraud | A Survey on Fault Attacks[END_REF], an 128-bit AES secret key can be recovered by using one faulty ciphertext [START_REF] Saha | A Diagonal Fault Attack on the Advanced Encryption Standard[END_REF] and CRT RSA private parameters can be obtained by using one faulty signature [START_REF] Lenstra | Memo on RSA Signature Generation in the Presence of Faults[END_REF][START_REF] Joye | Chinese Remaindering Based Cryptosystems in the Presence of Faults[END_REF]. In the particular case of DSA [START_REF]Digital Signature Standard[END_REF], ECDSA [START_REF]Digital Signature Standard[END_REF], XTR-DSA [START_REF] Lenstra | An Overview of the XTR Public Key System[END_REF], Schnorr [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF] and ElGamal [START_REF]A Public-Key Cryptosystems and a Signature Scheme based on Discret Logarithms[END_REF] signature schemes, fault attacks are not as efficient. Indeed, if an attacker is able to induce an error on a single bit, the most efficient attacks on such schemes can recover the corresponding private keys by using one faulty signature per bit of the private key [START_REF] Bao | Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault[END_REF][START_REF] Dottax | Fault Attacks on NESSIE Signature and Identification Schemes[END_REF]. However, injecting a fault that would only affect one bit would be very difficult to put into practice. Giraud and Knudsen extended previous attacks to use a more realistic model where faults where considered that would affect one byte [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. By using this fault model, they claimed that one would be able to recover a 160-bit private key by using 2304 faulty signatures and then conducting an exhaustive search amongst 2 40 possible keys.

In this paper, we analyse the attack proposed by Giraud and Knudsen [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] in more detail, and we show that their attack is much more efficient than originally claimed. Our improved analysis is two-fold. Firstly, under the same assumptions used in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF], we prove that the average number of trials required to conduct an exhaustive search is 2 30 and not 2 39 as implicitly indicated in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. Consequently, under the same attack model used in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] we show that an attacker needs 34.3% less faulty signatures to recover a 160-bit private key. Secondly, we improve the detail of the system of equations representing the fault model. This more precise definition allows us to significantly improve the results given in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF], especially if the key is composed of bytes close to 0 or 255. In such a case, the improvement can be up to 47.1%.

The rest of this paper is organised as follows. In Section 2, we recall the previous fault attacks which have been published on signature schemes. In Section 3, we compute the average number of guesses to conduct an exhaustive search if performing a fault attack by using the fault model presented in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. In Section 4, we present a more accurate system of equations representing the fault model used in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. This allows us to improve the original result and to show that the efficiency of this attack is dependant on the key value. Finally, Section 5 investigates if there is an optimal method to perform the exhaustive search.

Previous Work

The first fault attack on signature schemes was proposed in [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults[END_REF] on the RSA using the Chinese Remainder Theorem (CRT). It was shown that a CRT RSA private key could be derived if one fault was injected during the generation of a signature. This attack requires an attacker to obtain two signatures for the same message , where one signature is correct and the other one is faulty. By computing the gcd of the modulus and the difference between the correct and the faulty signature, the attacker would obtain one private factor of the modulus. This attack was extended in [START_REF] Lenstra | Memo on RSA Signature Generation in the Presence of Faults[END_REF][START_REF] Joye | Chinese Remaindering Based Cryptosystems in the Presence of Faults[END_REF] by using only one signature generation.

A fault attack on RSA, where the CRT is not used, is defined in [START_REF] Bao | Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault[END_REF]. Again the attack compares the result of generating signatures from the same message with, and without faults. While a signature is being generated an attacker generates a fault causing one bit of the private exponent to be changed, resulting in a faulty signature ′ . Assuming that the -th bit of is complemented, then, as described in [START_REF] Bao | Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault[END_REF], we have:

′ ≡ ′ -≡ { 2 (mod ) if the -th bit of = 0, 1 2 (mod ) if the -th bit of = 1. ( 1
)
where is the correct signature. In [START_REF] Bao | Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault[END_REF] it was also shown that this attack can be applied to other signature schemes, such as ElGamal, Schnorr and DSA.

In [START_REF] Joye | RSA-type Signatures in the Presence of Transient Faults[END_REF] it was shown that this attack can be improved by raising the formula to the power of the public exponent , giving:

′ ≡ { ( ) 2 (mod ) if the -th bit of = 0, 1 ( ) 2
(mod ) if the -th bit of = 1.

(

) 2
In this case it is not necessary to know the correct signature .

An attacker can compute ′ mod for all the possible one-bit fault errors in . This requires a total of log 2 trials to completely derive if an attacker is able to dictate which bit of is complemented.

This was extended by Giraud and Knudsen in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] to consider faults that affect one byte of an exponent. Let us now describe this extension where, to avoid any ambiguity, the fault needs to be treated as an integer difference between a correct exponent byte and a corrupted exponent byte. As above, we define the private key as and ′ as the corresponding corrupt private key. We define and ′ as the th byte of and ′ respectively, a fault on the th byte will therefore produce:

{ ′ = , ∀ ∕ = ′ = + , if = (3)
with , ′ ∈ {0, . . . , 255} and ∈ {-255, . . . , 255} where = 0 corresponds to no error. For each fault on one byte of , the attacker will deduce the position of the corrupted byte since it is the only value for which satisfies ∕ = ′ . He will then compute the corresponding value of by subtracting ′ with . By definition, the possible values for are: ∈ {-, . . . , 255 -} .

If two faults are observed, and ˆ , the possible values of can be restricted to values where:

< ˆ : ˆ -= 256 -, (5)
which means that:

-≤ ≤ -+ ( -1) . (6)
In [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] it is shown that the number of faulty signatures required to observe two faults with a significant enough difference to reduce to a certain number of hypotheses can be defined. The average number of faults required to reduce the possible values to values, for ∈ {1, . . . , 8}, are shown in Table 1.

In the next section, we present another way of analysing the efficiency of the attack described in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. Indeed, whatever the number of candidates left, the most important information is the average number of guesses the attacker needs to do to recover the value of the secret key.

A More Practical Analysis

The analysis in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] defines the average number of faulty signatures that are required to reduce the number of possible values for to a given number of hypotheses. It is then suggested that the private key can be found using an exhaustive search. However, the expected number of guesses an attacker would have to conduct is not defined in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. This information is of uttermost importance when analysing the efficiency of the attack. For example, it is shown in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] that a 2 160 key space is reduced to at most 2 40 by using 2304 faulty signatures. Therefore, one could assume that expected number of guesses in the exhaustive search is 2 39 , but this is not the case as it will be seen in this section. In the following, we derive the expected number of guesses for a given number of induced faults under the same assumptions defined in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF].

Notation

After inducing faults for ∈ {1, ⋅ ⋅ ⋅ , }, we define the Min statistic by:

min = Min( 1 , . . . , ) , (7)
and the Max statistic by: max = Max( 1 , . . . , ) .

Expected Search Time

By denoting by the number of possible values for the variable we disturb (in our case = 256 since we disturb one byte), we summarise the attack described in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] as follows:

"Induce faults on a variable ∈ {0, ⋅ ⋅ ⋅ , -1} which results in observed values min and max with difference = max -min. Then guess between the -remaining candidates at random." Theorem 1 gives the probability of guessing the correct key in the th guess using this algorithm: Theorem 1. Let a variable ∈ {0, ⋅ ⋅ ⋅ , -1} with value be given. The probability of the number of guesses being equal to using the ACISP Algorithm with faulty signatures uniformly distributed is given by:

Pr( = | = ) = Pr(max = -+ 1| = ) = ( -+1
) -

( - ) (9)
Using Theorem 1, we can compute the expected waiting time as:

Corollary 1.
The expected size of an exhaustive search by using the algorithm described in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] is:

∑ =1 ( ) .
The proofs of Theorem 1 and Corollary 1 are given in Appendix A5 . By using Corollary 1 with = 256, we can compute the expected number of faulty signatures to reduce the number of guesses to , for ∈ {2, . . . , 8}, as shown in Table 2. ) 20 ≈ 2 30 and not 2 39 as implicitly indicated in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF].

Moreover, under the same attack model as in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] (i.e. an attacker being able to inject faults on one byte and being able to perform 2 39 signatures during the exhaustive search to find the correct key), we compute by using Corollary 1 that only 1513.3 faulty signatures are required 6 to recover a 160-bit private key. It is therefore an improvement of 34.3% compared to what was announced in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF].

The analysis presented in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] and in this section are based on Relations (4) and [START_REF] Dottax | Fault Attacks on NESSIE Signature and Identification Schemes[END_REF]. However, we show in the next section that these Relations can be refined, leading to an improvement of the corresponding analyses.

Improving the Analysis

In this section we will discuss some improvements to the analysis given in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. This is based on a more precise definition of the fault model and subsequent interpretation.

Reducing the number of possible values for the error

In this section, we present two remarks that allow us to improve the number of faulty signatures required.

Firstly, as described above, we have:

+ = ′ (10)
with , ′ ∈ {0, . . . , 255} and ∈ {-255, . . . , 255}. In [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF], Relation (10) leads them to the following relation:

-≤ ≤ 255 - (11)
However, we can reduce this interval of possible values for by taking into account that ∈ {0, . . . , 255}. This leads us to the following relation:

Max(0, -) ≤ ≤ Min(255, 255 -) , (12)
One may note that this restriction only significantly improves the analysis when the key byte value is close to 0 or to 255. Another way to slightly improve the analysis of [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] is to notice that they take into account the case = 0 when computing their probabilities. As this case corresponds to not inflicting any error, the resulting signature will be correct and can then be excluded. We can, therefore, define the error as:

∈ {-, . . . , 255 -} ∖ {0} , (13)
which further allows us to reduce the number of faulty signatures required.

In the next section, we redo the analysis done in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] and in Section (3) by using Relations ( 12) and ( 13) instead of Relations ( 6) and ( 4) respectively. 6 To obtain

( ∑ 256 =1 ( 256
) ) 20 ≈ 2 39 , we need to use = 75.66 faulty signatures per byte.

The Expected Number of Faults Required

To compute the statistically expected number of faults that will need to be observed we can model the system using a series of geometric distributions (see Appendix B). In this section we assume that an attacker wants to reduce the number of possible hypotheses for a given byte to less than . That is, the results of this analysis can be directly compared to those presented in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF].

The simplest case will be where the key byte is equal to zero or 255. Assuming that the effect of a fault is uniformly distributed, the probability of a given event allowing this is /255. So, we can say that attacker would expect to reduce the hypotheses to less than after 255/ observed faults. This is no longer the case if we consider other key values as observations can occur that are improved upon with subsequent observations. An attacker will be interested in observing a fault such that ∈ {-, . . . , -+ } or ∈ {255 --, . . . , 255 -}, for some key byte . This is because these values can be combined to make a list of less than, or equal to, hypotheses. For any event an attacker would expect to observe a value form these groups with a probability of 2 255 , and therefore would expect this to occur after 255 2 observed faults. For each of the 2 possible faults there will be a certain number of faults that will be of interest to an attacker. For each of the possible faults the number of faults that improve the amount of information can be noted. The probability of observing a further fault of interest can be computed and another expectation derived from this. This can be continued for each possible combination of observations for a given and the average expected number of observations can be computed.

For key values close to zero or 255 the initial two groups {-, . . . , -+ } or {255 --, . . . , 255 -} will be modified since an attacker will know the value when no fault is applied, i.e. = 0. This means that the average expectation across all the possible key values will lead to the expected number of faults.

If, for example, we consider the case where = 2. For simplicity, we will also assume that the key byte value is ∈ {2, . . . , 253}, i.e. the value of the key byte will not interfere with the analysis. Using the above method the expected number of observations 1 is computed as

( 1 ) = 255 4 + 1 4 ⋅ 255 2 + 1 4
( 255 3 + 2 3 ⋅ 255 2 ) + 1 4 ⋅ 255 2 + 1 4
( 255 3 + 2 3 ⋅ 255 2 ) = 212.5 ,
where is a function that returns the statistical expectation.

If the key byte value is ∈ {1, 254}, then the known value for no fault being injected will be part of the process. Using the above method the expected number of observations 2 is computed as

( 2 ) = 255 3 + 1 3 ⋅ 255 2 + 1 3 ⋅ 255 2 = 170 .
If the key byte value is ∈ {0, 255}, then we only need one observation of interest to reduce the number of possible values to the required amount. Using the above method the expected number of observations 3 is computed as

( 3 ) = 255 2 = 127.5 .
The expectation for a uniformly distributed key ∈ {0, . . . , 255} is a weighted mean of the above expectations. The expected number of faults required therefore becomes

( ) = 252 ( 1 ) + 2 ( 2 ) + 2 ( 3 ) 256 = 211.5 .
The results of computing the above for ∈ {1, . . . , 8} is shown in Table 3 (all rounded to one decimal place). One can note that the improvement in Table 3 is minimal compared to Table 1 (1.3% on average). The improvements discussed in Section 4.1 only have a significant impact when a the value of a key byte is close to 0 or to 255. Figure 1 shows the key value dependency of this improvement when using 114 faulty signatures. In such a case, the improvement is of 39.2% if the key byte is equal to 0 or 255. Moreover, the smallest the number of faulty signatures we use, the biggest the improvement is. For instance, we obtain an improvement of 49.3% when using 10 faulty signatures if the key byte is equal to 0 or 255.

The Expected Size of an Exhaustive Search

The analysis described in the previous section is limited in the same way as the analysis described in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]. The number of faults required is that needed to reduce the number of faults to less than a given value. In this section we define the expected number of faults required to produce an exhaustive search of a given size. We first define the probability that a set of observations will span different values, for ∈ {1, . . . , -1} (in our case = 256). Trivially, we can say that

Pr( = 1) = -1 ( -1) (14)
since the probability of all observations having the same value is 1 ( -1) for each possible value of . For = 2,

Pr( = 2) = 2 ( , 2) ( -2) ( -1) (15)
where we define ( , ) as a function that returns the Stirling numbers of the second kind. That is, the number of ways of partitioning elements into nonempty sets. Given that our sets are unique this needs to be multiplied by 2. Furthermore, there are ( -2) possible sets where = 2. Computing the expectation becomes more complex for > 2 since the sets representing the minimum and maximum possible values need to be non-empty, but the values in between can be empty. In order to compute the number of possible combinations that will span different values we consider that the values fall into two sets. The first set represents the minimum and maximum values (there will be a minimum of two observations in this set). The second set represents the values in between the minimum and maximum observation and can contain empty sets.

We consider faults that span different values, where > 2 and > 2. These faults will be distributed between the two sets defined above. The set representing the minimum and maximum values contains observations, where is ∈ {2, . . . , }, then the number of combinations that are possible for a given will be 2 ( , 2), as described above. The remaining observations will be in the other set where the number of combinations will be ( -2) -. We can note that this number of combinations will only take into account one particular set of observations from faults. This means that there will be ( ) possible ways of choosing observations. This leads to

Pr( = | > 2) = ( -) ∑ =2 2 ( , 2) ( -2) -( ) ( -1) , ( 16
)
where we note that there are ( -) possible combinations where = . The list of key hypotheses that can be excluded will also depend on the value of the byte affected by the fault being injected. The probability of a set of observations having a particular difference between the maximum and minimum observation for a specific key value is

Pr( = | = ) = Pr( = ) 256 , ( 17
)
where we assume that the is ∈ {0, . . . , 255}, i.e. 256 possible values. However, the expectation cannot be computed directly from this probability. This is because the signature where no fault is injected is known, i.e. an observation where the fault induced is equal to zero. For a minimum observation 1 and a maximum observation 2 , spanning values, we can define:

Min( 1 , 0) Max(0, 2 )
For a given 1 and 2 the number of values that are actually spanned will be equal to Max(0, 2 ) -Min( 1 , 0), and the number of remaining hypotheses is equal to -1-Max(0, 2 )+Min( 1 , 0). Therefore, the probability given above for Pr( = | = ) needs to be divided by -to produce the probability for specific values of 1 and 2 .

The expected number of remaining hypotheses ( ) can be computed as

( ) = -1 ∑ =0 -1 ∑ =1 ∑ ∈ + -1 ∈ ( -Max(0, + -1)+Min( , 0)) Pr( = | = ) - ,
where we use the notation defined above (cf. ( 14), ( 15), ( 16) and ( 17)). In addition we denote as the minimum observation in a set of observations that span values. The values that and + -1 can take are in , where is the set {-, . . . , --} ∖ {0}.

If we assume the actual key value is uniformly distributed between the remaining hypotheses ℎ then the expected number of tests required to find a key byte is computed as (ℎ + 1)/2. For a fault in one by these values are shown in Table 4, rounded to one decimal place. In order to allow the results of the improvement to be directly compared to the results described in Section 3, we used the formula for ( ) to compute the expected number of faulty signatures required to reduce the number of guesses between 2 and 8, cf. Table 5. By observing Table 5, one can see that the improvement is minimal compared to Table 2 (2.1% on average). It only has a significant impact when the value of a key byte is close to 0 or 255. Figure 2 shows this improvement when using 73 faulty signatures. In such a case, the improvement is of 37.6% if the key byte is equal to 0 or 255. Moreover, the smallest the number of faulty signatures we use, the biggest the improvement is. For instance, we obtain an improvement of 48.1% when using 10 faulty signatures. The analysis conducted in this section shows that using the same attack model used in [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] 7 and considering a random 160-bit key (resp. a 160-bit key that consists of bytes equal to 0 or 255), we would need 1488 8 (resp. 800 9 ) faulty ciphertexts to recover the entire key. In the latter case, we have an improvement of 47.1% comparing to the result presented in Section 3.

The Exhaustive Search

In [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF], no detail is given on how to obtain the correct value of the key amongst the possible values that are defined by the analysis. If, for example, there are 4 20 (2 40 ) possible values for a private key, we can say that one would expect to conduct 2 39 trials, on average, to identify the correct value amongst the 4 20 possible values. In this section we demonstrate that there is no best method of searching through the hypotheses that are produced by the analyses described in this paper.

We define a series of faults for ∈ {1, . . . , }, which we assume are drawn from a distribution that is uniform over the integers in { , . . . , 255 -} ∖ {0}, where is an unknown integer ∈ {0, . . . , 255}. In order to rank a given value of , we divide the interval into intervals. For simplicity, we assume that the intervals are evenly spaced. Let denote the number of the observed which fall within the -th interval, so we have

1 + ⋅ ⋅ ⋅ + = . ( 18
)
7 That is, by using byte-fault model and a expected number guesses of 2 39 . 8 To obtain ( ) 20 ≈ 2 39 with = 256, we need to use = 74.4 faulty signatures per key byte. 9 To obtain ( ) 20 ≈ 2 39 with = 256, ∈ {0, 255} and by dividing Pr( = ) by 2 instead of 256 to obtain Pr( = | = ), we need to use = 40 faulty signatures per key byte.

Given that the faults induced are uniformly distributed, then

( 1 ) = ⋅ ⋅ ⋅ = ( ) = , (19)
where is a function that returns the statistical expectation. This can be used to conduct a frequency test. That is, we compute a statistic , where

= ∑ =1 ( ( ) -( )) 2 ( ) , (20)
and is a function that returns the number of observed faults in a particular interval. Then ∼ 2 ( -1) and can be used to test the null hypothesis that is a given value for each possible value ∈ {0, . . . , 255}. For a given the P-value can be computed which is a value between 0 and 1, where the larger the value the more evidence is provided against a hypothesis for (typically values above 0.95 or 0.99 are used as a boundary, above which it can be stated that there is no evidence to support a given null hypothesis).

A set of 32 simulated observations were generated where was, arbitrarily, set to 140. The above statistical test was then conducted for ∈ {3, 5, 15}, i.e. small divisors of 255. In Figure 3 we show the resulting P-values for all the possible hypotheses for . The dashed lines represent the boundaries that can be deduced by observing the maximum and minimum possible values (see Equation ( 12)). One could assume that the P-value between the two lines could be used to determine which values of are most likely and use this to optimise the exhaustive search required once the possible values for a private key have been reduced to a certain amount. However, this is not the case.

The test described above where the number of faults was set to values ∈ {1, . . . , 64}, where 10 000 tests were conducted for each value. In each case the distribution of the number of tests required in an exhaustive search was identical to that produced by simply starting with the least (or most) significant hypothesis and incrementing (or decrementing) the hypothesis for each test. This is because the number of observed faults is not enough to give a good indication of the distribution to which they belong. If enough faults were observed to give a strong indication of the correct value of , it would be expected that the minimum and maximum observation would also identify without requiring any further computation.

Conclusion

In this paper, we show that the fault attack described by Giraud and Knudsen at ACISP 2004 is much more efficient than originally claimed. We proved that, using the same attack model, we need 34.3% less faulty signatures to recover a 160-bit private key. Furthermore, by improving the fault model expression, we show that for some key values we obtain another improvement of up to 47.1%. Finally, we show that there is no optimal way of performing the exhaustive search in order to reduce the computation complexity of this step.

In summary, Giraud and Knudsen claim that they need 2304 faulty signatures to recover a 160-bit private key, but in this paper we prove that one would only need between 800 and 1488 faulty signatures to recover such a key, using the same model and expected size of the required exhaustive search. The following hold:

i. For -( -1) ≤ ≤ :

( = | = ) = ( + - ) + ( -1 + - ) ( = | = ) = ( + 1 - ) + ( -)
ii. For ≥ 2 and -( -1) ≤ ≤ -:

( = , = + | = ) = ( = -( -1) + | = ) -( = -+ | = )
iii. For ≥ 2:

( - = ) = ( -)( ( = + 1) -( = )) ( ≤ - ) = 1 -( -+ 1) ( ) + ( -) ( -1)
The latter result is the same as the result from [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF]:

( ≤ ) = ( ≤ - ) = 1 -( -+ 1) ( ) + ( -) ( -1)
Proof (Theorem 2.i). ) but the derivation here is much simpler than the one in the aforementioned article. □

Fig. 1 .Fig. 1 .

 11 Fig. 1.a. Global view Fig. 1.b. Zoom on Fig. 1.a

Fig. 2 .Fig. 2 .

 22 Fig. 2.a. Global view Fig. 2.b. Zoom on Fig. 2.a

Fig. 3 .

 3 Fig. 3. Returned P-values plotted for all possible values for one byte for = 3, 5, 15 (top left, top right and bottom middle respectively). The dashed lines represent the boundaries identified by the minimum and maximum observed fault.

1 ≤ 1 , 1 -

 111 ⋅ ⋅ ⋅ , ≤ + -1) -( ≤ 1, ⋅ ⋅ ⋅ , ≤ + -1) -( + 1 ≤ 1, ⋅ ⋅ ⋅ , ≤ + ) = ( + 1) -( ) -( ( ) -( -( ) -( -)( ( ) -( -1)) = 1 -( -+ 1) ( ) + ( -) (-1)If we substitute = 256 and = -= 256 -we get the result from [9

Table 1 .

 1 Expected number of faulty signatures required to reduce the number of possible values for one key byte[START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF].

	Maximum 4 number of candidates Expected number of faulty
	left for	signatures required
	1	384.0
	2	213.3
	3	149.3
	4	115.2
	5	93.9
	6	79.2
	7	68.6
	8	60.4

Table 2 .

 2 Expected number of faulty signatures required to reduce the expected number of guesses to , for ∈ {2, . . . , 8}.

	Expected number of guesses for	Number of faulty signatures performed
	2	176.5
	3	102.8
	4	72.7
	5	56.2
	6	45.7
	7	38.5
	8	33.2

We can, therefore, demonstrate using Corollary 1 that using 2304 faulty signatures to attack a 160-bit key (i.e. 115.2 faulty signatures per key byte) implies that the expected number of guesses required to conduct an exhaustive search is ( ∑ 256 =1 ( 256 ) 115.2

Table 3 .

 3 Expected number of guesses for one key byte depending on the number of faulty signatures.

	Maximum number of hypotheses for	Expected number of faulty signatures
	1	381.5
	2	211.5
	3	147.8
	4	113.8
	5	92.5
	6	77.9
	7	67.3
	8	59.2

Table 4 .

 4 Expected number of hypotheses and guesses required to determine a given key byte.

		(# of Remaining Hypotheses) (# of Tests)
	1	170.3	85.7
	2	127.7	64.3
	3	102.1	51.6
	4	85.1	43.0
	5	72.9	37.0
	6	63.7	32.4
	7	56.7	28.8
	8	51.0	26.0
	9	46.4	23.7
	10	42.5	21.8

Table 5 .

 5 Expected number of faulty signatures required to reduce the expected number of guesses to , for ∈ {1, . . . , 8}.

	Expected number of guesses for	Number of faulty signatures required
	2	174.8
	3	101.4
	4	71.4
	5	55.0
	6	44.5
	7	37.4
	8	32.1

In[START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF], it is written "Average number of candidates left" but their formula gives the average number of faulty signatures required to reduced the number of candidates to at most . Therefore we need to replace "Average" by "Maximum".

In Appendix A.1, we present a simpler proof of [9, Theorem 1] than the one in the aforementioned article.

Acknowledgments

The authors would like to thank Frédéric Amiel for initiating this work and Emmanuel Prouff for his helpful comments on the preliminary version of this paper. The work described in this paper has been supported in part by the European Commission IST Programme under Contract IST-2002-507932 ECRYPT and EPSRC grant EP/F039638/1.

A Proof of Theorem 1 and Corollary 1

A.1 Distributions Theorem 2. Let a random variable be given, which is uniformly discrete on the interval 1 to :

A.2 Generic Formula for Making the Correct Guess Lemma 1. With the notation:

The probability of guessing the correct key in the th guess can be expressed as

Now we can write:

and we know from Theorem 2.ii that

Insertion concludes the proof. □

A.3 Proofs of Theorem 1 and Corollary 1

Proof (Theorem 1). Having observed = and = + , [START_REF] Giraud | Fault Attacks on Signature Schemes[END_REF] is content with noting that the number of remaining candidates equals -and therefore

The claim follows by insertion in the formula of Lemma 1. □ Proof (Corollary 1). The expected is given by the formula

which reduces to the claimed formula. □

B The Geometric Distribution

A geometric distribution is produced when we consider a system

That is, a geometric distribution is produced when there will be -1 failures before a successful event (that occurs with probability ) and the system stops. We note that a geometric series, for -1 < < 1 gives

and the first differential is

If has a geometric distribution and 0 < < 1, then the expectation of X is given by

using the above formula for ′ ( ) with = and = .