P Gaudry

E Thomé

The mpF q library and implementing curve-based key exchanges

We present a library for finite field arithmetic. The originality of this library lies in the fact that specialized code is automatically produced for the selected finite fields. The opportunity of compile-time optimizations yields substantial performance improvements compared to libraries which initialize the finite field at runtime. This library is used to present benchmarks on some curve-based public key cryptosystems.

Introduction

Cryptosystems based on the discrete logarithm problem in (Jacobians of) curves are competitive in many contexts. The main advantage compared to systems based on the factorization problem or on the discrete logarithm problem in finite fields is that the best known algorithm for attacking has exponential time instead of subexponential. In practice it means that for obtaining a given security, the sizes of the parameters are smaller.

The speed of an implementation of a curve-based cryptosystem is mostly given by the speed of the underlying finite field arithmetic. Once the particularities of the finite field implementation are known, one can search in the literature the most suitable choice for the coordinate systems and for the addition chain. This also depends on the amount of memory available, and if resistance to side-channel attacks is required.

In this paper we describe a new (still in development) finite field library called mpF q that we have used to write curve-based cryptosystems. The main objective of this library is speed. Portability, readability, ease of maintenance, ease of use are also wanted, but we accept no feature in the design of the library that would prevent us to apply certain optimizations.

Setting as a goal the implementation of fast curve-based cryptosystems forces a particularity of the underlying finite field operations: The finite field is known at compile-time. This enables a considerable amount of optimizations. The design of the mpF q library is suited to this problem: provide optimized code that takes advantage of all the information that is known at compile-time.

In Section 2 we give an overview of the existing software, and list the requirements for the mpF q library. In Section 3 we explain with more detail the design of mpF q and why certain choices were made. In Section 4 we give some timings. Finally in Section 5 we describe a few BATs that have been implemented with the help of mpF q . We conclude with some plans for the future.

2 Why yet another finite field library?

Existing finite field libraries

Obviously, there are several already existing software libraries that can be used to perform computations in finite fields. We briefly review here some of them.

The NTL library [START_REF] Shoup | NTL: A library for doing number theory[END_REF] by V. Shoup provides arithmetic modulo finite fields, and also goes well beyond that. NTL is written in a small subset of C++, and based on selectable multiprecision arithmetic packages (including the Gnu MP library [START_REF] Granlund | GMP, the GNU multiple precision arithmetic library[END_REF]). NTL has good performance in general and very good performance for small prime fields, using IEEE floating point arithmetic for the reduction step.

The ZEN library [START_REF] Chabaud | user manual[END_REF] by F. Chabaud and R. Lercier is a C library for finite field arithmetic. ZEN handles arbitrary finite field (extension of extensions for instance). Although ZEN is written in ANSI C, it should really be regarded as an object-oriented implementation in the same spirit as X11: Almost every user-land identifier from the high-level interface is a macro that calls a function obtained by dereferencing a pointer in the last passed argument (the field). The high-level interface is well-documented. However, for best performance, if the finite field one is working in is known in advance when writing the code, it is possible to call directly the lower-level functions, thereby saving an indirect function call. ZEN has several lower-level layers, including specialized arithmetic for one-word-long modulus. This only goes to a limited extent, however, since the lower-level interface of ZEN is not documented.

The Miracl library by M. Scott [START_REF] Scott | MIRACL: Multiprecision integer and rational arithmetic c/c++ library[END_REF] provides an optimized feature set for cryptographical operations. It relies on a finite field layer whose performance appears to be good. Miracl goes well beyond finite field operations, since algorithms such as elliptic curve point counting or algorithms for computing pairings are included.

We also mention the Givaro library by J.-G. Dumas et al. [START_REF] Dumas | Givaro, une bibliothèque C++ pour le calcul formel[END_REF]. It is written in C++ templates, and claims to perform well for one-word-long modulus.

Besides the libraries cited above, which strive for providing arithmetic for all finite fields, there are also software libraries which focus on particular finite fields. The NuMongo library by R. Avanzi [START_REF] Avanzi | Aspects of hyperelliptic curves over large prime fields in software implementations[END_REF] handles specially selected prime fields, with the modulus having a special form. As far as we know, it contains only 32-bit code and is not publicly available.

The opportunity of compile-time optimizations

As mentioned in the introduction, the primary goal that started the development of mpF q was the implementation of fast curve-based cryptosystems. For such an application, the finite field is known in advance. Since speed is desired, one wants to take advantage of this knowledge when building the library. While the performance improvement might seem limited if one has in mind fields modulo 1024-bit primes, this kind of optimization makes a vast difference for small fields.

The contexts with an opportunity for compile-time optimization also includes longrunning computations on one or several selected finite fields. In particular, cryptanalysis attempts such as the breaking of the Certicom ECC Challenges [START_REF]The Certicom ECC challenges[END_REF][START_REF] Harley | The ECDL project[END_REF] fall in this category. In the precise example of [START_REF] Harley | The ECDL project[END_REF], specially crafted code was written in order to have fast finite field operations. Other settings in which specific code was written include [START_REF] Fouquet | Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy[END_REF][START_REF] Bernstein | Curve25519: new diffie-hellman speed records[END_REF].

Several kinds of optimizations are made possible by the knowledge of the finite field at compile time. These include the following list of methods. All these optimizations can easily be performed at compile time, but it is not so easy to do the same at runtime, and in many cases it is impossible.

• Code inlining. At runtime, this is not clear which code to inline, because it might depend on the field.

• Branch elimination. If the values determining the control flow are constant at compile time, then the branches can be avoided. This reduces the cost of loops and conditionals.

• Loop unrolling. Nowadays compilers do it automatically, but the unrolling is more efficient if the length of the loop is a constant.

• Choice of the best algorithm for a given task. This can be done also at runtime (ZEN does so), but is more comfortable at compile time (and comes with zero runtime overhead).

Of the finite field libraries mentioned above, only those focusing on a handful of specialized finite fields (like NuMongo) have the opportunity to take full advantage of the optimizations above. By design, none of the other libraries which provide arithmetic for general finite fields are in position to exploit these optimizations.

It is always conceivable to overload some particular library with a new class for the particular field we are interested in, but no simple mechanism is provided to help the developer in this task.

Wanted features of mpF q

From our experience emerges a need for a software library for finite fields which differs from the existing material. Briefly put, the two main differences are:

• mpF q has to handle very efficiently finite fields that are known at compile time.

• mpF q 's specialized code for the selected finite fields should be written automatically, rather than crafted by hand.

mpF q sets some goals. The utmost concern is speed, obviously. mpF q is not contented with merely working code, since this is not good enough for our claimed purposes. While the automatic process of generating specialized code should take sensible choices, we require that these choices may be overridden easily, or that radically different implementation choices may be taken by the user in a way that is reasonably compatible with the rest of the library. Indeed, there is quite often no single answer to the question "which is the fastest implementation of F q ?" for a given value of q. Depending on the intended application, the different finite field operations are not necessarily used equally frequently; in situations where optimizing an operation penalizes another one at the same time, the relevant optimization choices therefore depend on the application.

Since the underlying finite field might be in several cases a parameter of an algorithm, mpF q has to provide a consistent application programming interface (API) in order to allow code reuse.

In the last few years, the processors that are available in average workstations have become multi-core. This means that for most applications, having a multi-threaded implementation is a good way to gain efficiency. For this reason, we require that the mpF q code be reentrant, so that they are usable within a multi-threaded application.

The dependencies of mpF q are free software, mpF q itself being free software licensed under the terms of the Gnu Lesser General Public License (LGPL)1 .

3 The design of mpF q

Choice of the programming languages

The programming languages used by mpF q are perl, C, and assembly. The automatic generation of specialized code for a selectable finite field is done by perl. From the description of the finite field, the perl code creates a C source file and header, which provides the required set of functionalities.

The choice of perl calls for some comments. The C++ language offers several methods which could provide the needed genericity. An object-oriented approach with a virtual base class would fail on the speed requirement. The unavoidable indirect function call for virtual methods would be a major performance hit, in particular for the sizes we are focusing on (for small sizes, an inlined implementation of the operation would be most suitable). Furthermore, the variety of fields on which different specialized code is needed would require different classes to be generated by other means anyway.

The template mechanism from C++ provides essentially what is needed. Indeed, this allows a static overriding of functions, leaving the possibility of inlining. We believe however that the kind of syntactic manipulation that is offered by C++ templates can also be obtained by other means. At the expense of losing the type checking of code specializations, we have opted for doing the code generation using perl, which is best suited for text manipulation.

The dilemma of assembly

In many cases, writing critical routines in assembly is required for gaining speed. This is due to strict limitations of the C language concerning arithmetic. For instance, after adding two machine-words, if there is an overflow (a carry), the C language ignores it, whereas on many platforms this information is still available at the assembly level. Also the popular x86 architecture gives access to the full double-word result of a multiplication, whereas only the low significant word is reachable from C. A third example is assembly instructions specific to some platform, like for instance the SSE-2 instructions set [1]. Such instructions and the corresponding data types are not accessible with standard C.

There are several approaches to writing assembly. It is possible to write a standalone function, that respects the application binary interface (ABI) of the C compiler/system we use. This is very convenient but it means that a possibly costly function call has to be payed each and every time one needs it. The other approach is not standard, but available in many compilers, including the Gnu C compiler (GCC). It consists in inline assembly language insertion using the asm() keyword. The programmer must tell the compiler which registers are used for input, ouput and temporary usage during the assembly stage. This has the advantage of avoiding the function call. Another option is language extensions which are specific to some compilers. Several compilers (including GCC as well as compilers from Intel, Microsoft) provide the emmintrin.h include file, with for instance the _mm_slli_epi64 macro which corresponds to the psrlq assembly instruction (which right-shifts a 128-bit SSE-2 register).

Deciding between standalone functions and inline assembly language is a matter of length of the assembly code, but not only. One could think that writing a C function as a list of small blocks of asm() interleaved with pure C code is a good idea, but sometimes it appears that it is better to write the whole function in assembly to help the compiler in register allocation and handling the data flow. Unfortunately, right now, we have not yet been able to find a strict rule for when an approach should be chosen or another, and trying several implementations is the only resort.

The API and function naming

The API of mpF q is as follows: Let TAG be a mnemonic that corresponds to a finite field or a family of finite fields. In fact, TAG will also be different if the internal representation of elements of the same finite field are different. For instance, 2_27 can be the mnemonic for the finite field with 2 27 elements in classical (polynomial basis) representation; or p_mgy_3 can be the mnemonic for the family of prime finite fields where the modulus fits in 3 machine-words and the elements are in Montgomery representation. Then the C types and the C functions corresponding to this mnemonic start with mpfq_TAG. For instance, an element of F 2 27 will have a type mpfq_2_27_elt, and the multiplication function between two such elements will be called mpfq_2_27_mul.

Macros and inline functions

All these types and functions are stored in two files: mpfq_TAG.c and mpfq_TAG.h. The speed requirement means that all the functions that take less than (say) a few hundred cycles must be inlined. Instead of using the C preprocessor for defining macros, mpF q is developed using static inline C functions that are included in the .h file. The inlining effect is the same, but compared to a macro, this has the advantage to allow the compiler to perform a type checking and to facilitate the debugging (when switching off the inlining optimisation options of the compiler). For instance, in F 2 89 the add function will be as follows: [1]; } This example calls for additional remarks:

static inline mpfq_2_89_add(mpfq_2_89_field_ptr K, mpfq_2_89_dst_elt r, mpfq_2_89_src_elt s1, mpfq_2_89_src_elt s2) { r[0] = s1[0]^s2[0]; r[1] = s1[1]^s2
• The first argument of most mpF q functions is a pointer to the finite field in which the operation takes place. For most implementations, it is not used, but in some case it is convenient. For instance if the implementation of the multiplication covers all prime fields of a given size, then the modulus should be accessible to the function, and is then obtained from the first argument.

• The type for an element is split into two subtypes marked src and dst. This follows GMP practice to distinguish between const and variable arguments. Adding the keyword const to a variable sometimes helps the compiler to choose the right optimization.

Code generation

It should be now evident that there will be a lot of redundancy between different .c and .h files of mpF q . To avoid the problems with maintaining a code with a lot of code duplication, we have chosen to have most of the C and assembly sources of mpF q generated automatically by perl scripts. The power of perl with manipulating files, strings, regular expressions makes it a very nice alternative to any macro-based preprocessing (like CPP or M4) or to a template-based C++ approach.

We give an example of the power of this approach: when writing the code for the trace of an element in a specific finite field of characteristic 2 in polynomial basis representation, one wants to precompute the powers of the defining element x that have trace 1, in order to create the mask. If you do not allow a powerful enough language for the preprocessing, this precomputation will have to be stored and shipped with the library sources, whereas a perl script has no problem to do this precomputation on the fly, just before creating the appropriate C function. It is even possible, if some precomputations would be tedious in perl, to hand off some of the work to an external program in C (mpF q uses such a convenience).

We have implemented a main module that helps in the organization of the code generation. Several perl scripts in mpF q generate code, but they are not handling the global organization themselves. Instead, the API for mpF q for all finite fields is concentrated in a single file api.pl that lists the functions that should be present, together with their prototypes. The generation of the .c and .h files for a given mnemonic TAG is done by the main module, which iterates over the functions in the API. It delegates the generation of these functions to the specialized scripts, fetching perl subroutines named code_for_<function_to_generate>. At the end the main module reconstructs both files from all the codes, and creates the appropriate prototypes. This approach allows to enforce conformance to the API.

Benchmarks

Development status of mpF q

The API and the main perl module of mpF q are more or less fixed. mpF q will probably gain more functionalities gradually, and most importantly we need to improve speed at every possible level. Until now we have focused on 64-bit architectures based on the AMD64 instruction set. This covers essentially all the processors currently sold for personal computers and workstations (Athlon64, Opteron, Core2, recent Xeon). We believe that in a near future, 32-bit architectures will be found only in embedded systems. Our code works on 32-bit architectures but the assembly support is inexistent or very poorly written. Furthermore, on many 32-bit architectures, the floating-point unit is more powerful than the integer unit, so that this would probably give the best performance, and we didn't implement this.

Apart from the target architecture, we have been concentrating in optimizing the finite fields that are needed for our BATs. In particular, for a prime field modulus which is not sparse, the Montgomery representation should probably be used, but this is not yet properly set in mpF q , so that the benchmarks are somewhat deceiving2 .

While mpF q has good performance for some operations, some other are in dire need for improvement (finite field inversion notably).

Benchmarking methodology

We start with a word of warning: measuring the cost of a small operation is essentially impossible on modern computers. Assume that an operation takes 20 cycles; assume also that this operation is implemented in an inlined function (in C or assembly, this does not really matter for this discussion). The cost of setting up the data and preparing the registers at the beginning might take a few cycles (say 4 cycles), and this task is done by the compiler. However, those 4 cycles might become much less if the context of the function call is favorable (that's one of the advantages of inlining). Therefore, some discrepancy is inherently attached to the measurement.

There are basically two ways of timing an operation: either ask the operating system (with the getrusage() function) or use the tick counter of the processor (the rdtsc assembly instruction on x86). The first approach is fine only for very long tasks, since the precision is of the order of the millisecond. The second approach is suitable only for rather short tasks, since any interruption or context switch of the system will perturbate the measure. Also, there is some kind of "Observer effect" for very small operations: a call to rdtsc is not serializing, which means that there is no guarantee that the instructions are executed in the order they are written. This is of course not good for our purpose. There is a variant of rdtsc that is serializing (or one can add some serializing operation before and calibrate it), but then we really perturbate the operation we are measuring, since there is a high risk of flushing the pipeline.

In our context, we have mostly used the getrusage approach for our measures. Since the operations we want to measure are small, we repeat them a large number of times and divide the running time accordingly. On a few tests we have made, the results are not too far from the other approach based on rdtsc, and consistent with the running times of the BATs we have built upon the measured operations. But an operation like an addition in F 2 113 can definitely not be measured in an optimized implementation, since its cost is essentially just the cost of fetching the appropriate data: if it is already in registers, then the operation will be less than 2 cycles or even zero (if the xor's can be inserted between higher latency instructions), but if this operation must be done at a time where all the registers are already occupied, moving data between the stack and the registers can cost a non-negligible time.

Cost of basic operations for prime fields

For prime fields, we have written mpF q implementations for each machine word size of the modulus (up to nine words) and for the two finite fields that we use in our cryptographic applications. The algorithms we have implemented are by no means original (classical representation and we have used a basic binary extended GCD for the inversion). The costs of basic operations for these fields are given in Table 1 and Table 2. We also give similar benchmarks in NTL and ZEN for comparison. NTL and ZEN do not take advantage of the pseudo-Mersenne form of the modulus. However, in ZEN one can activate a Montgomery representation that speeds-up computations, so we give both timings.

We can see that mpF q is faster than NTL for all sizes. ZEN with Montgomery representation is comparable or slower than NTL except for 1 word primes, where it is sometimes faster than mpF q . As one can expect, the difference is more visible for small sizes, and on Opteron, since our assembly code is best suited to this processor. The gain obtained by writing a reduction procedure that is specific to a pseudo-Mersenne modulus is visible on the last two columns.

We conclude with a comment on the usual practice in curve-based cryptography: quite often, to compare the costs of different coordinate systems or addition chains, only the multiplications and squarings are counted, and the additions are said to be negligible. This is clearly not the case, for instance for the field F 2 255 -19 on the Opteron where the mul/add ratio is less than 6. The same kind of ratio is observed with the ZEN and NTL libraries, and is even amplified by the fact that an addition or subtraction is much slower than with mpF q .

Cost of basic operations for binary fields

The binary fields up to F 2 255 are implemented in mpF q , using a polynomial basis representation. We have chosen defining polynomials with lowest possible Hamming weight. Figure 1 shows the performance of the multiplication, squaring and inversion using mpF q compared to the NTL and ZEN libraries for these fields. The figure also indicates the timings for the "unreduced" multiplication and squaring operations. The graphs on the left side correspond to timings on an AMD Opteron CPU at 2.40 GHz, while the graphs on the right side correspond to timings on an Intel Core2 CPU at 2.66 GHz.

The algorithms implemented for the different operations are the classical ones described for instance in [8, chap. 11]. So far, the multiplication is done using the schoolbook algorithm, but Karatsuba and Toom-Cook variants have to be measured in comparison. It appears that for all sizes, the best performance for the multiplication is attained by using the SSE-2 instruction set [1]. Using these instructions, it is effectively possible to work in parallel with two 64-bit machine words at a time. The performance gain is most remarkable on the Intel Core2 CPU.

The comparison with the NTL library shows that mpF q is faster than NTL except in a few situations. The ZEN library is somewhat slower than NTL in particular for the inversion (we did not investigate where this problem could come from). In our ZEN test program, we have activated the precomputations that could yield speedups, but we have not tried to split the extension in a double extension; in the documentation of ZENfact (a submodule of ZEN), there are examples of such constructions that provide a speedup, but this is not really automatic. We have also skipped the optimization that builds a logarithm table, since this is valid only for tiny fields.

The inversion in mpF q has not been looked at seriously, it merely has the merit of giving correct results. Concerning the multiplication, the relative under-performance of the SSE-2 implementation on the AMD Opteron CPU is probably explained by the different implementation of the SSE-2 pipeline on this particular CPU compared to the Intel Core2. On both CPUs, the large steps around 2 250 call for further optimization, and will be investigated. For this purpose, an automatic tuning program is being prepared. We mention that NTL has a conspicuous problem for finite fields smaller than F 2 64 . This should probably not be worried about and should be considered as an easy tuning issue.

Writing BATs with mpF q

We have used mpF q to write efficient software implementation of the Diffie-Hellman key exchange protocol based on curves. We started with the curve25519 parameters given by Bernstein [START_REF] Bernstein | Curve25519: new diffie-hellman speed records[END_REF]: this is an elliptic curve in Montgomery form defined over F 2 255 -19 , such that both the curve and the twist are secure. We obtain the following timings on our two test machines. We have designed a cryptosystem of genus 2 of the same level of security that we called surf127eps. It is based on a genus 2 curve defined over F 2 127 -735 that has complex multiplication by K = Q i 5 + √ 53 . The Jacobian of this curve has an order which is 16 times a prime and is suitable for using the Kummer surface formulae of [START_REF] Gaudry | Fast genus 2 arithmetic based on Theta functions[END_REF] that we have implemented. We obtain the following timings on our two test machines. We can see that for prime fields, the Opteron behaves better than the Core2. This might be surprising since this Opteron is a 3-year old computer, whereas the Core2 is a brand new architecture; however our skills to optimize assembly code for the Core2 is clearly not the same as for Opteron.

The other observation is that a genus 2 cryptosystem can beat an elliptic one with our implementation, depending on the processor. However, if a general, efficient genus 2 point counting implementation were available, one could construct a Kummer surface with small coefficients, thus saving a lot of operations (as shown by Bernstein [START_REF] Bernstein | Elliptic vs. hyperelliptic, part 1[END_REF]). We expect that the situation would be constantly in favour of genus 2.

In order to test our library and to measure the difference between prime fields and characteristic 2 curve based cryptosystems, we have also implemented the scalar multiplication on elliptic curves in characteristic 2, based on the formulae by Stam [START_REF] Stam | On Montgomery-like representations for elliptic curves over GF (2 k )[END_REF], over the finite field F 2 251 and a genus 2 scalar multiplication based on the Kummer surface, over the finite field F 2 113 . This time there is no problem for the point counting in genus 2, thanks to p-adic methods (we have used Magma for these point counting computations).

The results are the following. It should be noted that the performance suffers from the lack of fine-tuning of the multiplication algorithm (in particular, we acknowledge that the multiplication in F 2 251 is still sub-optimal). curve2_251

Comparison with other scalar multiplication implementations

The usual problem when comparing timings is that the computers are quickly evolving, so that comparison is difficult. This is particularly true in the present case, where we are concentrating only on 64-bit architectures, whereas almost all implementations reported in the literature rely on 32-bit architecture. This is strange, since the Opteron has been sold for 4 years, now, and the gain of using 64-bit is clear. Additionally, usually the reported implementations are there to illustrate some improvement in the group law formulae, so that no two papers are really comparable if one is mostly interested in the underlying finite field implementation. Therefore we give the raw data, without trying to scale it to our experiment platform or to the coordinate system we choose.

For each reference, we mention the result that corresponds more or less to the security level we have chosen.

In [START_REF] Avanzi | Rethinking low genus hyperelliptic jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formulae[END_REF], an implementation of curve arithmetic in characteristic 2 has been written, based on a carefully written set of finite field routines. There timings are given on a 32-bit Power G4 at 1.5 GHz. In genus 1 over F 2 251 , a scalar multiplication takes 3758 microseconds. In genus 2 over F 2 109 , a scalar multiplication takes 1673 microseconds.

In [START_REF] Bernstein | Curve25519: new diffie-hellman speed records[END_REF] where curve25519 is described, Bernstein reports an implementation between 620000 and 950000 cycles depending on the processor. All the processors that are considered are 32-bit, and therefore floating point arithmetic used. In [START_REF] Bernstein | Elliptic vs. hyperelliptic, part 1[END_REF], he gives a genus 2 implementation (very similar to surf127eps) that takes 580000 cycles on a Pentium M.

In [START_REF] Wollinger | Cantor versus Harley: Optimization and analysis of explicit formulae for hyperelliptic curve cryptosystems[END_REF], an implementation in characteristic 2 gives the following timings on a Pentium 4 at 1.8 GHz: in genus 1 over F 2 191 , a scalar multiplication takes 2780 microseconds and in genus 2 over F 2 95 , it takes 3410 microseconds.

In [START_REF] Avanzi | Aspects of hyperelliptic curves over large prime fields in software implementations[END_REF], Avanzi has used his NuMongo library to implement scalar multiplication for curves over prime fields. The timings are for an Athlon 1 GHz: in genus 1 over a 256-bit prime field, it takes 3048 microseconds and in genus 2 over a 128-bit prime field, it takes 3575 microseconds.

Future plans

The future directions of mpF q are numerous, given the amount of algorithms that would be worth giving a try. For prime fields, we need to adapt our implementation of Montgomery's REDC algorithm [START_REF] Montgomery | Modular multiplication without trial division[END_REF] to the mpF q library. We also plan to improve the inversion both on prime and binary fields.

Given the growing interest in pairing-based cryptography, we will probably provide implementations of extension field arithmetic (with specialized code for the most frequently used extension degrees).

It is planned to extend mpF q to handle polynomials and matrices over finite fields and generate optimized source code files for this purpose. This might lead us to consider the case of large polynomials, and include FFT algorithms which are suited to the base fields used.

As for the BATs, we still have room for improvements in the choice of the addition chain. Right now, we have used the most basic binary ladder. We plan to try some of the heuristic algorithms available in the literature for finding better addition chains, for instance the so-called PRAC algorithm by Montgomery [START_REF] Montgomery | Evaluating recurrences of form x m+n = f (x m , x n , xmn) via Lucas chains[END_REF].

Figure 1 :

 1 Figure 1: Time (in microseconds) for Multiplication, Squaring, Inversion in F 2 n (Left column is on AMD Opteron 2.40 GHz, right column is on Intel Core 2 2.66 GHz)

Table 1 :

 1 Time (in nanoseconds, with 2 significant digits) for basic operations in F p on an AMD Opteron 250 processor at 2.40 GHz.

		add	1 word 2 words 3 words 4 words 2 127 -735 2 255 -19 2 4 5 7 4 8
	mpF q :	sub sqr	2 67	3 108	5 170	5 230	4 14	9 30
		mul	66	109	180	240	16	45
		inv	420	2600	4600	7500	2600	7400
			1 word 2 words 3 words 4 words
		add	40	42	36	47
	NTL:	sub sqr	38 120	40 150	28 230	44 290
		mul	120	150	230	290
		inv	1600	4400	6600	9200
			1 word	2 words	3 words	4 words
		add	8/11	44/44		44/44	48/49
	ZEN/ZENmgy:	sub sqr	7/8 62/90	64/71 270/170	66/70 420/270	73/75 520/320
		mul	68/95	300/180	450/270	600/340
		inv 1700/2100 3300/4300 4800/5900 6500/7500

Table 2 :

 2 Time (in nanoseconds, with 2 significant digits) for basic operations in F p on an Intel Core2 6700 processor at 2.66 GHz.

		add	1 word 2 words 3 words 4 words 2 127 -735 2 255 -19 1 2 4 8 3 8
	mpF q :	sub sqr	1 73	4 110	5 180	7 240	3 17	9 40
		mul	74	120	190	260	19	53
		inv	300	2000	3600	5800	2000	5800
			1 word 2 words 3 words 4 words
		add	38	45	53	67
	NTL:	sub sqr	38 110	45 130	52 210	64 270
		mul	110	140	210	270
		inv	1200	3400	5800	8000
			1 word	2 words	3 words	4 words
		add	6/6	41/41		46/46	57/57
	ZEN/ZENmgy:	sub sqr	4/4 52/52	54/60 280/120	60/62 400/170	73/78 550/250
		mul	52/60	280/120	400/180	590/260
		inv 1000/1000 2500/3000 3800/4300 5000/5900

By the time of the Speed conference, we plan to distribute a first beta release of mpF q .

Montgomery representation arithmetic will probably be in place by the time of the Speed conference.

Acknowledgments

Although we are only two authors, we rely heavily on GMP, not only as a dependency library, but also as a source of inspiration for the design of mpF q . We have also taken ideas from ZEN, NTL and from software written by R. Harley for the ECDL challenges. We wish to thank Paul Zimmermann and Richard Brent who shared several ideas with us on the topic of muliplication in binary fields.

The genus 2 curve that we use for the BAT called Surf127-735 has been generated by the CM method using tools written by T. Houtmann.


Dieudonne Mulamba
email: mulamba@cs.colostate.edu

Indrajit Ray
email: indrajit@cs.colostate.edu

Resilient Reference Monitor for Distributed Access Control via Moving Target Defense

Effective access control is dependent not only on the existence of strong policies but also on ensuring that the access control enforcement subsystem is adequately protected. Protecting this subsystem has not been adequately addressed in the literature. In general, it is assumed to be implemented as a reference monitor in a trusted computing base (TCB) that is tamper-proof. However, in distributed access control, ensuring TCB security kernel to be tamper proof is not always feasible. It needs to be implemented in software and on platforms that can potentially have vulnerabilities. We posit that allowing a very limited opportunity to the attacker to enumerate exploitable vulnerabilities in the access control subsystem can considerably facilitate its protection. Towards this end we propose a moving target defense framework for access control in a distributed environment. In this framework, access control is provided by cooperation of several distributed modules that materialize randomly, announce their services, enforce access control and then disappear to be replaced by another module randomly. As a result, the attacker does not know which process can be targeted to compromise the access control system.

Introduction

Many emerging distributed applications rely on on-demad network-enabled access to a shared pool of computing resources. Examples of such applications are IoT applications, sensor networks or enterprise level distributed workflow systems. This distributed computing model brings with it some unique challenges to access control that require re-visiting the traditional TCB approach [START_REF] Anderson | Computer Security Technology Planning Study[END_REF]. In traditional systems, access control is implemented by the cooperation of four functional modules that are part of the trusted computing base:

1. Policy Administration Point (PAP): The PAP is a repository for the authorization policies that are expressed in terms of the actions that subjects (human users, devices, processes, organizations etc.) can take on various objects in the system. The authorization policies are essentially an instantiation of the access control model tailored towards the organization. It is the main component for the authorization portion of access control 2. Policy Information Point (PIP): The PIP is the component that gathers together all the attribute information that are needed to evaluate an authorization policy.

Policy Decision Point (PDP):

The PDP gets relevant information from the PIP and consults the PAP to arrive at a decision whether to grant or deny an access request. 4. Policy Enforcement Point (PEP): The PEP receives access requests from subjects in the external world, hands them to the PDP for evaluation, and after receiving the grant or deny response from the PDP, ensures the appropriate action is taken.

One of the requirements of a TCB is that it implements the concept of reference monitor [START_REF] Anderson | Computer Security Technology Planning Study[END_REF]; that is, the TCB mediates all access to objects by subjects, is tamper-proof and cannot be bypassed, and is small enough to be thoroughly tested and analyzed. In the newer distributing computing environments however, making the TCB small and tamper-proof is very difficult. This is because access control in such environment needs to be achieved via the cooperation of both local as well as remote access control engines. To remain within the confines of the TCB paradigm, not only all of these separate components need to be made tamperproof, but also all communications and coordinations among the components. As a result, the trusted computing base needs to be enlarged in scope and functionality, which violates the principles of reference monitor. Moreover, the sheer size of these distributed systems, the degree of heterogeneity among the different devices (potentially virtual machines), and the dynamicity of the whole system, compound the problem many fold. It appears, therefore, that it is next to impossible to rely on a single TCB to provide access control in these environments. The access control subsystem should try to satisfy as many properties of a TCB as possible but should also incorporate certain self-defending strategies to make it secure.

In this work, we treat access control in such a distributed environment as a service that needs to be proactively protected. From a functional perspective, this service is achieved by the four functional units -PAP, PIP, PDP and PEP. We assume that like any other service the access control service can be attacked by an attacker and hence needs to be protected. An attacker intent on damaging the access control service will launch reconnaissance efforts seeking exploitable vulnerabilities for this subsystem. We propose being proactive and allow only limited opportunity to the attacker to enumerate exploitable vulnerabilities, thus reducing the attack surface of the access control subsystem. Towards this end, we propose employing a Moving Target Defense (MTD) paradigm for the access control subsystem. The four functional modules are effectuated by randomly materializing processes that announce their services, enforce access control and then disappear to be replaced by another module randomly. As a result, the attacker does not know which processes can be targeted to compromise the system. Moreover, the window of opportunity for targeting processes is varied to further reduce opportunities of attack. We describe an implementation of this system to handle RBAC policies using COTS components.

The rest of the paper is organized as follows: Section 2 reviews previous works on access controls, leader election protocols, moving target as well as on service discovery protocols. In section 3 we first present the reference architecture for access control in distributed environments. We then give an overview of our moving target defense approach for protecting the access control subsystem. Section 4 presents the moving target defense architecture. We present our implementation in section 5 as well as an analysis of the security of the proposed approach. Finally, we conclude this paper in section 6 and give some directions for future works.

2 Background and Related Works

Protection of Access Control Subsystems

One of the most important aspect of security is ensuring that users access only resources to which they are authorized. Research on designing and deploying access control in computers and networks can be traced back several decades [START_REF] Sandhu | Access control: principle and practice[END_REF]. Early standards of access control included discretionary and mandatory access control [17] [42] [34] [START_REF] Ferraiolo | Role-based access control (rbac): Features and motivations[END_REF]. However, Role based Access Control (RBAC) represented a major leap forward in term of flexibility. RBAC is built on the principle that users do not have discretionary access to enterprise objects. In a RBAC model, roles are created and users belong administratively to these roles, while permissions are administratively assigned to the roles. This arrangement provides more flexibility and simplicity to the management of authorization [START_REF] Ferraiolo | Role-based access control (rbac): Features and motivations[END_REF]. RBAC has been traditionally implemented for centralized systems. In recent years, several works have been done to provide the capabilities of this access control model to distributed systems and the cloud. For instance, in [START_REF] Huh | Next-generation access control for distributed control systems[END_REF] authors present an access control tailored for distributed control systems. [START_REF] Ruj | Decentralized access control with anonymous authentication of data stored in clouds[END_REF] explains how one can provide access control to anonymous users while verifying their authorization in a decentralized manner.

In several works, including recently in [START_REF] Ferreira | How to securely break into rbac: the btg-rbac model[END_REF], researchers have worried that a malicious program may tamper with the operation of an access control system. The notion of a trusted computing base implementing the reference monitor concept was proposed by Anderson [START_REF] Anderson | Computer Security Technology Planning Study[END_REF], in order to address this problem. Security kernels such as Scomp [START_REF] Fraim | scomp: A solution to the multilevel security problem[END_REF] and GEMSOS [START_REF] Schell | Designing the GEMSOS Security Kernel for Security and Performance[END_REF], included a reference validation mechanism to satisfy the reference monitor concept of the TCB. Other operating systems such as Trusted Solaris [START_REF]ORACLE: Trusted Solaris Operating System[END_REF], the Linux Security Modules (LSM) framework [START_REF] Wright | Linux Security Modules: General Security Support for the Linux Kernel[END_REF], TrustedBSD [START_REF]The TrustedBSD Project: Trustedbsd[END_REF], Mac OS X, and the Xen hypervisor provide various degree of support for reference validation so as to enable some shade of reference monitor. However, the major problem with these systems is that the tamperproof property that needs to be ensured for provably implementing a reference monitor, is hard to achieve. Tamperproofing requires the TCB to have a very small footprint. It can be shown that a general algorithm to prove that an arbitrary program behaves correctly reduces to solving the Halting problem. While current algorithms can prove correctness properties of specific programs, the variety of reference validation code and the complexity of correctness properties preclude verification for all but the smallest, most specialized systems. Unfortunately, for most of these systems, the TCB is too large to determine whether tampering is prevented. Moreover, for practicality and functionality, many systems allow user-level processes to modify the kernel. However, none of these user-level processes are immune to tampering, thus becoming one of the weakest links. In this work, we are interested in the protection of the access control subsystem where ensuring the tamperproof property of a reference monitor is challenging.

Moving Target Defense

Several works have been done on Moving Target Defense (MTD). In order to improve the understanding of MTD, [START_REF] Zhuang | Towards a theory of moving target defense[END_REF] presents key concepts and their basic properties. Other works on MTD are mainly focused on network-based MTD [START_REF] Al-Shaer | Toward network configuration randomization for moving target defense[END_REF][START_REF] Antonatos | Defending against hitlist worms using network address space randomization[END_REF][START_REF] Compton | Improving the quality of service and security of military networks with a network tasking order process[END_REF]. In addition, in [12], the effectiveness of MTD using low-level techniques to defend a computing system has been studied. Those low-level techniques include Address Space Randomization, Instruction Set Randomization, and Data Randomization. In [START_REF] Han | Characterizing the power of moving target defense via cyber epidemic dynamics[END_REF] two measures are designed that allow a defender to quantify its gain in security while deploying a MTD system. In order to chose a particular MTD technique, one needs to know its effectiveness. For that purpose, [START_REF] Xu | Comparing different moving target defense techniques[END_REF] proposes a comparison of different MTD techniques based on their effectiveness. However, none of these techniques are applicable for the problem we are addressing.

Leader Election

In a distributed system, leader election is a fundamental problem that requires that a unique leader be elected from among a set of given nodes. The goal of a leader election algorithm is to elect a good processor as a leader in a setting where there are n processors among which a certain number m < n are bad, while ensuring that no bad processor get elected as a leader [START_REF] King | Scalable leader election[END_REF].

A distributed computing system often requires that active nodes continue performing their task after a failure has occurred. This reorganization or reconfiguration necessitate that a coordinator be elected in the first place [START_REF] Garcia-Molina | Elections in a distributed computing system[END_REF]. This is the reason of the wide interest the leader election problem [START_REF] Le Lann | Distributed systems-towards a formal approach[END_REF] has received. Several works have been done on Leader Election [START_REF] Abu-Amara | Election in asynchronous complete networks with intermittent link failures[END_REF][START_REF] Brunekreef | Design and analysis of dynamic leader election protocols in broadcast networks[END_REF][START_REF] Garcia-Molina | Elections in a distributed computing system[END_REF][START_REF] Sayeed | Optimal asynchronous agreement and leader election algorithm for complete networks with byzantine faulty links[END_REF][START_REF] Singh | Leader election in the presence of link failures[END_REF].

Consensus algorithms

One approach for building fault-tolerant applications is the Lamport's approach. The core of this approach involves two primitives: consensus and atomic broadcast [START_REF] Lamport | The part-time parliament[END_REF]. Leader election protocols are generally used to solve the consensus problem.

Bully algorithm [START_REF] Arghavani | Improved bully election algorithm in distributed systems[END_REF] and Ring algorithm [START_REF] Soundarabai | Message efficient ring leader election in distributed systems[END_REF] are among the most used algorithms for solving the consensus problem. A hugely popular algorithm is the Paxos algorithm proposed by Lamport [START_REF] Lamport | Paxos made simple[END_REF]. Another popular algorithm, considered even superior to Paxos due to its simplicity, is the Raft consensus algorithm [START_REF] Howard | Raft refloated: do we have consensus?[END_REF]. Raft provides the capabilities for Leader election and log replication.

ZooKeeper [START_REF] Hunt | Zookeeper: Wait-free coordination for internetscale systems[END_REF], an open-source replicated service for coordinating web applications, and Chubby [START_REF] Burrows | The chubby lock service for loosely-coupled distributed systems[END_REF] are some practical systems exploiting these algorithms. Recently, GIRAFFE [START_REF] Shi | Giraffe: A scalable distributed coordination service for large-scale systems[END_REF] has been proposed to provide a coordination service in scalable distributed system. Another practical system is the Apache Kafka [START_REF] Wang | Building a replicated logging system with apache kafka[END_REF] which allows the building of a replicated logging system. However, these algorithms and protocols do not take into account Byzantine failures. In addition, their approach for electing a new leader does not prevent a malicious host from being elected as a leader

Byzantine Fault Tolerance

A computer system can be affected by a type of failure that can cause it to behave in an arbitrary way. After being affected, the computer system can be led either to process requests incorrectly, to corrupt their local state, and/or to produce incorrect or inconsistent outputs. This type of failure is called Byzantine failures. The problem for coping with this type of failure is known as the Byzantine Generals Problem [START_REF] Lamport | The byzantine generals problem[END_REF]. The goal of Byzantine fault tolerance is to allow computer system to be immune against Byzantine failures. I Several works have been proposed to reach a consensus in the face of Byzantine failures. Building on Paxos, the authors in [START_REF] Castro | Practical byzantine fault tolerance[END_REF] have proposed an improvement that allows Paxos to support Byzantine fault tolerance with a modest latency. Castro and Liskovs proposed the Practical Byzantine Fault-tolerance protocol [START_REF] Castro | Practical byzantine fault tolerance and proactive recovery[END_REF] that reduces the number of messages exchanged to only four messages. [START_REF] Martin | Fast byzantine consensus[END_REF] looked at improving the number of communications in the Byzantine Paxos protocols. In [START_REF] Copeland | Tangaroa: a byzantine fault tolerant raft 12[END_REF], authors took the task of improving Raft to support Byzantine fault-tolerance. They reach their goal by combining the ideas from the original Raft algorithm and from Practical Byzantine Fault-tolerance protocol [START_REF] Castro | Practical byzantine fault tolerance[END_REF].

Service Location Protocol

A zero configuration approach is a self-management networking approach that allows network devices to be automatically configured, discover services automatically, and to access service without the involvement of a network specialist [Intelligent Self-Management Home Multimedia Service System]. Three major self-management technologies have been proposed. The Internet Engineering Task Force (IETF) promoted SLP [START_REF] Guttman | Service location protocol: Automatic discovery of ip network services[END_REF][START_REF] Perkins | Dhcp options for service location protocol[END_REF] as an intranet standard for automatic network resource discovery. Intel and Microsoft, on their part, proposed the Universal Plug and Play (UPnP) [START_REF] Presser | Upnp device architecture 1.1[END_REF] as a standard for automatic communication between network devices using XML messages. Apple Inc. proposed a protocol called Bonjour [START_REF] Inc | Bonjour[END_REF] as its zero configuration networking standard. Recently, z2z [START_REF] Lee | z2z: Discovering zeroconf services beyond local link[END_REF] has been proposed for the discovery of network services beyond the local network.

In this work, our contribution includes the development of a system that leverages these existing concepts into a single framework so as to address the problem of protecting a reference monitor.

Architecture Overview

We assume that the access control model is Role-Based Access Control. We start with a high level operational architecture of access control (AC) in the distributed setup. The resources we are concerned about are the shared resources. The AC architecture is composed of four functional entities. Each entity has specific functions and participates in the communication as a client, as a server or both.

Access Control Architecture Components

The four entities are: Using these entities, the distributed access enforcement proceeds as follows. When a client needs to access a protected resource, it sends a request to the Authorization Control Service (ACS). The ACS verifies the policy governing the access to the needed resources, and replies with a decision to grant or deny access to the requested resource. If the decision was to grant access, the request is forwarded to the Resource Access Service along with a limited life-time token given to the client allowing it to access that particular resource. The occurrence of an election triggers the Authorization Control Service to be Switched to a different location. In this case, the ACS will register its new location with the Discovery Service. In addition, the client will need to consult the Discovery Service in order to find the new location of the ACS.

Threat Model

In our architecture, we consider access control (AC) as a service and we assume that the Access Control Service can be attacked and compromised. To mitigate the vulnerability of the open network in which an attacker passively listens to various communications, we make all access related communications go over secure channels. This makes the communication secure, but does not protect the endpoints, particularly the Resource Access Server and the Authorization Control Server where the AC engine components reside. We assume that an attacker can masquerade as one of these servers. Alternately, some numbers of these servers can themselves be compromised by malware and behave in a Byzantine manner. An attacker masquerading as a valid server or corrupting a server are treated similarly.

To protect these two entities, we propose the Moving Target Defense strategy. Our motivation for this approach follows from the observation that an attacker needs a reconnaissance window to explore the vulnerabilities in a system before attacking it. The moving target defense strategy reduces this window of opportunity. It requires both the Resource Access Server and the Authorization Control Server to be replicated. At each instance there is only one Resource Access Server and one Authorization Control Server that is responsible to handle access requests. These are called respectively, RAS leader and ACS leader servers. In addition, both leader servers are periodically replaced by a pair of leader servers randomly chosen by following a Byzantine consensus process executed by the existing candidate RAS and ACS servers. The replacement is achieved through a migration process that relies on a secure service discovery process.

Using moving target defense in this manner to protect the Access Control Engine raises several challenges. Those challenges are as follows.

1. How does one avoid migrating a leader server to a malicious server during the migration process? 2. Which access control component is going to be migrated? And, 3. After the migration process, how does one discover which server is currently providing the services?

In the following sections we are going to address these challenges. We present an architecture that provides access control services. In order to protect the access control service against certain attacks, we have proposed to implement a Moving Target Defense strategy on the access control service architecture. In this section, we present the different components that constitute our Moving Target Defense architecture.

The Client

It is an endpoint entity whose main objective is to access protected resources. It is responsible to initiate or terminate a session with the Resource Access Service. It resides on the individual devices running the applications that require access to shared resources.

The Authorization Control Service

In this section we present the different components that allow the Authorization Control Service to provide access control service, to be elected as a leader, and to announce its services once elected as a leader.

Access Control Engine

The access control engine is based on RBAC model (other models are also possible) and is designed to prevent unauthorized access to protected resources. It comprises the Policy Enforcement Point (PEP), the Policy Decision Point (PDP), the Policy Administration Point (PAP), and the Policy Information Point (PIP).

Fault Detector Module (FD)

The Fault Detector Module is designed to detect the byzantine faults occurring in the server providing the Access Control service. The failure and the compromise of the current leader server are reasons to trigger the Moving Target Defense. The Fault Detector is able to detect any kind of byzantine faults that are local to the leader server. The unavailability of the leader server is detected by the Fault Detector of any other server that probes the aliveness of the leader server. The occurrence of either failure, compromise, or unavailability is used to trigger the election of a new leader server that will be responsible to provide access control services.

Election Module (EM) The Election Module is responsible for processing the election of a new leader server. Several causes can trigger this election. Since the leader server is assuming this function for a limited time, called here a term, the expiration of this term is a cause that triggers the election of a new leader server. We add randomness to the duration of this term in order to prevent an attacker from correctly guessing the occurrence of the next leader election. At the expiration of his term, the current leader server proceeds to the election of a new leader. In other circumstances, the first server noticing the failure of the current leader server, is responsible to proceed to a new election.

Leader Election Protocol In our system, after having opted to replicate the Authorization Control Service among several servers, a single server is responsible to provide this service at any given time. We call this server the leader. At any instance, this leader may be the subject of attacks or of failures. Thus to realize the moving target defense, the leader is required to be periodically changed. This change can occur at the expiration of the current leader's lifetime or when the current leader fails. Moreover, the next server is not pre-determined but is elected by existing servers, each of which is a candidate. All this is done in an environment where we assume that some servers may be malicious attackers. Thus, we need a leader election algorithm that can ensure that a malicious server cannot be elected as leader. Once a server is elected, it sets a random lifetime for itself.

For the sake of maintaining our distributed system in a good functioning state, it becomes crucial to prevent faulty nodes from becoming leader. We adapt the algorithm from [START_REF] King | Scalable Leader Election[END_REF] in order to realize a leader election. The election process proceeds in the form of a distributed protocol as follows.

The election algorithm proceeds in rounds and in each round there is a node that is coordinating the consensus, called the coordinator. For each round r there is a coordinator c known a priori by each participating node by computing c ≡ (r mod n) + 1 with n being the total number of nodes. At each node, there are several local variables that are maintained, among which there is the estimate value which is an input value selected by the node, its current election round, its current coordinator c p , and a timestamp ts p . The consensus algorithm runs by exchanging messages between nodes participating in the distributed system. These messages include the types ESTIMATE, SELECT, CON-FIRM, READY/NREADY, and SUSPECT. The algorithm runs in a sequence of five tasks that are concurrently executed.

The consensus algorithm, (see Algorithm 1), works as follows. The algorithm starts with each node p picking its estimate of the input value, and sending an ESTIMATE message to all nodes. The coordinator, after receiving nk ESTIMATE messages that it was waiting for, selects a value es based on all the estimate values received. It then sends a SELECT message carrying the es value to all nodes. Each node p, upon receiving SELECT message from the coordinator, sends a CONFIRM message carrying the es value to all other nodes. The es value should be the same for a given round r. After receiving a CONFIRM message from (n + k)/2 + 1 distinct nodes, each node p updates its local variables. It then sends a READY message or a NREADY message depending on whether it had received the same es value or not from (n + k)/2 + 1 CONFIRM messages. It should be noted that if the CONFIRM messages received by a node p did not contain the same es value, p will assume that the coordinator had deviated from the algorithm. The node p will therefore add the coordinator to its list of Suspect, and will send a SUSPECT message containing the id of the suspected coordinator to all. After a node p received the same es value as content of READY message from (n + k)/2 + 1 distinct nodes, it will decide on that value. A node q is confirmed to be malicious by a node p and added to Out put(D) p if and only if node q have been reported malicious by at least k + 1 nodes. Out put(D) p is the final list of malicious nodes. Any round in which the coordinator has not been reported with malicious nodes will end with a consensus on the input value and the coordinator being confirmed as the new leader. Otherwise, a new round will start with a new coordinator.

Migration Module (MM) The Migration Module is responsible for executing the migration protocol. The Migration Module receives a notification from the Election Module that a new leader has been elected. This notification contains the identity of the new leader server. Upon receiving the notification from the Election Module, this module executes the migration protocol, which transfers the Access Control service to the new elected leader server.

23:

if [p = c p ] then

24:

[Wait until received (nk) distinct estimate q messages from q nodes] 25:

Estimates p ← estimate q 26: ts = largest ts q : estimate q ∈ Estimates p

27:

if [ts = 0 and (at least (k + 1) distinct estimate q ∈ Estimates p have common value e)] then

28:

es ← e 29:

32:

{Coordinator creates select msg} 33: select p = ((SELECT, p, r p , e s ) p )

34:

Send select p to all 35: end if

36:

{Task 1, Phase 3 : receiving confirm msg} 37:

[Wait until received [(n + k)/2] + 1 distinct con f irm q messages or c p ∈ Out put p ] 38: con f irm p = ((SELECT, p, r p , e s ) p ) 39: if [[(n + k)/2] + 1 distinct con f irm q ∈ Con f

68:

Send suspect p to all 69: end while 70: {Task 5:} 71: for r in S do 72:

When p receives Suspect q from q 73: if r in Suspected q then 74:

Suspecting p [r] ← Suspecting p [r] ∪ (q)
75: else 76:

Suspecting p [r] ← Suspecting p [r] -(q) 77: end if 78: if |Suspecting p [r]| k + 1 then

79:

Out put p = Out put p ∪ (r)

80:

else 81:

Out put p = Out put p -(r)

82:

end if

83: end for

Service Migration Protocol In our architecture, replacing the current leader server by a new one necessitates the migration of the Authorization Control Service provided by the current leader server to the new one. For this purpose, we need to put in place a service migration protocol that can handle this task.

Process migration is the movement of a running process from one host to another. A process migration protocol can have several components like the transfer policy, the selection policy, and the location policy. Since we are interested with the migration of an access control service, we define these policies in terms of the requirements of the access control service.

1. The Transfer Policy: This policy determines when a host needs to send a process to another host. In our case, it determines when the current leader server needs to send the access control services to a newly elected leader server. In our architecture, this decision is triggered by the successful completion of the leader election protocol. 2. The Location Policy: This policy determines the destination host to which to transfer the process to be migrated. In our architecture, this information is provided by the leader election protocol that communicates the identity of the new elected leader server to all the hosts. This new Authorization Control Service is the destination host for the migration protocol. 3. The Selection Policy: Determines which resource to transfer. It is question here to determine which component of the access control service needs to be migrated.

We have designed the Authorization Control Server to be fully replicated. We assume the existence of a replicated protocol. Therefore, the discussion about the replication protocol is beyond the scope of this paper. Being fully replicated, each Authorization Control Service has the same PDP, PAP, and PEP. There is no need to migrate those entities. However, only the current leader server has the information about the granted access requests in addition to having the most up to date policy database. Granted access requests information is stored in the session history of the current Authorization Control Service. Therefore, the session history and the policy database need to be migrated to the new Authorization Control Service to allow users with granted access a continuous use of the allowed resources.

The Discovery Service

Implementing a Moving Target Defense for an Access Control service requires switching frequently but randomly the server that is responsible for offering the Access Control service. Once the Authorization Control service has been switched to a newly elected leader server, users need a way to rediscover the new server offering the service. In this section, we adapt the Service Location Protocol or SLP in order to enable users to discover the new location of the services they need.

SLP Module

The SLP Module is responsible for running the service discovery protocol. This service is provided to clients that need to consult the SLP Module in order to discover the new Authorization Control Service location.

SLP overview Service Location Protocol (SLP) is a protocol designed by the Internet

Engineering Task Force to eliminate the need of a manual configuration from users of communication networks in order to discover services, applications, and devices available in those networks. Since users, mainly mobile users, increasingly experience changing environments and the fact that the Internet has became more service oriented, service location is becoming more helpful in today's complex networks [START_REF] Veizades | Service location protocol[END_REF][START_REF] Guttman | Service location protocol: Automatic discovery of ip network services[END_REF].

SLP Architecture

The SLP framework includes three main components called "Agents" to process SLP information. These agents are: User Agents (UA), Service Agents (SA), and Directory Agents (DA).

-User Agents (UA): They are responsible for requesting services on behalf of the users or applications. -Service Agents (SA): They are entities that advertise the location and description of services on behalf of services. To advertise services, the SAs embed the service information into an URL. These information include the IP address, the port number, the service type and the path. Each service type is characterized by specific attributes along with their default values. All of these are specified by the Service Templates. -Directory Agents (DA): They are central repositories that aggregate SLP information. Since service information are embedded in a URL, these URL are stored by the DA which provides them to any UA that have issued a request which matched some attributes in the URL. At the beginning of the protocol, any service provider needs to advertise its services. For that purpose, its SA registers the service with the DA. This step is known as the Service Registration. The DA acknowledges the registration by issuing a service ACK message to the SA. A user that needs to use the given service needs to have his UA issuing a query with the appropriate attributes to the DA. This is known as the Service Request step. The DA may reply back to the UA with the address and characteristics of the desired service (Service Replay). This is the general approach of the SLP protocol as illustrated on fig 2.

There is a major issue with the general approach of the SLP protocol as explained above. No one from both the UA and the SA knows the address of the DA. Before registering a service with the DA, the SA needs to discover the existence of the DA. The same thing applies to the UA. Three different methods are used to discover the location of the DA: static, active, and passive. When using the static discovery method, both the UA and the SA learn the address of the DA from a DHCP server. In case of an active discovery, SLP agents contact the DA by sending service requests to the SLP multicast address on which the DA is configured to listen to for incoming communications. Upon receiving a service request, DA responds directly to the requesting agent via the agent's unicast address. The passive discovery method involves DAs periodically advertising their existence through the SLP multicast address. The other SLP agents discover the DAs location after listening the multicast advertisements. They can then contact the DAs directly through their unicast addresses for other operations [START_REF] Perkins | Service location protocol[END_REF]. Besides the basic SLP architecture involving SAs, DAs, and UA, it is possible to set a SLP architecture without DAs. In this case, UAs and SAs need to communicate directly to each other. In order to discover available services, UAs repeatedly send out their service requests to the SLP multicast address. On the other hand, SAs are listening for incoming requests on the SLP multicast address. Upon receiving a request corresponding to a service they are advertising, SAs reply through unicast address to UAs.

The Resource Access Service

It is a server that manages the various protected resources. It acts as both client and server when receiving or replying to access requests from clients. The decision to grant the access to those resources is received from the Authorization Control Service.

Implementation

In this section, we introduce the proof-of-concept implementation of our proposed architecture. We have designed a test case to exemplify the functioning of the protocol.

Clients and Resource Access Service

We assume that we have a set of users represented by client applications. Those users are grouped into a set of roles (Undergraduate, Graduate, and Faculty). We also have a set of resources, in this case files stored on a file server. This file server constitutes our Resource Access Service. We have also defined a set of actions to be performed on those files by users. We have chosen basic Linux actions: Read, Write, and Execute. The different permissions given to users over those files are represented on figure 3.

Authorization Control Server

Using socket programming, we have implemented five Authorization Control Services named ACS1, ACS2, ACS3, ACS4, and ACS5. Those have been implemented as Java Access Control We start our process with the Authorization service being provided by, let us say, the Authorization Control Server ACS1. We consider that user Tom submits a request to read a file named certificate.txt. This request is intercepted by ACS1 which run the Access Control Module. The Access Control Module has been implemented using the Balana [START_REF]Balana[END_REF] open source implementation of XACML. Tom's query will be a tuple user-id, action, resource-name where in this particular case user-id is Tom, action is read, and resource-name is the file certificate.txt requested by Tom.

Policy Enforcement Point

Tom's query is intercepted by the Policy Enforcement Point (PEP). In fact, the PEP intercepts all queries sent to the Resource Access Service [START_REF] Rissanen | extensible access control markup language (xacml) version 3[END_REF]. We have developed a wrapper that converts the original query into a XACML request. The request is then sent to the PDP for verification. Figure 5 illustrates the form of the XACML request.

Policy Decision Point

The Policy Decision Point (PDP) receives Tom's request coming from the PEP. It needs to analyse if Tom fulfills the required conditions to read the file certificate.txt. The PDP will consult the Policy file to determine what actions Tom is allowed to perform on the file certificate.txt. Balana [START_REF]Balana[END_REF] provides us with an API call that allows us to create a PDP.

Policy Administration Point

To write policies, we have made use of the Simple Policy Editor. This policy editor is part of WSO2 Identity Server [START_REF]Wso2 identity server[END_REF]. Simple Policy Editor allows anyone to create XACML 3.0 policies without an extensive knowledge of XACML language. However, an understanding of access control rules is required. Figure 6 is a sample of our policy file. In addition to the Policy file, the PDP also consults the user-role assignment table. After determining Tom's role, which is undergraduate, and consulting the Policy file, the PDP reaches the conclusion to authorize Tom to read the desired file. The PDP passes that decision back to the PEP. That response is represented as a XACML file. A sample of the response XACML file is exhibited on figure 7.

The PEP then replies to Tom with a response granting him access to the file. Tom can now access the file server. Leader Election Our objective is to protect the Access Control Module by regularly switching the Authorization Control Service providing the Access Control service at any given time. For the sake of demonstrating, we have chosen to switch the Authorization Control Service after every 10 minutes plus a random number of seconds. The random time is added to cancel the predictability of the time when the election takes place. An attacker knowing when the new leader is elected can schedule his attack accordingly.

An election is called after the end of term of the current Leader. In this instance, that term is set to ten minutes and some random seconds. The current leader being ACS1, it is the one responsible to call for an election. Using Java, the Leader Election is implemented according to the adaptation of the protocol presented in section 4.2. At the end of the protocol a new leader is elected. This leader is different from ACS1, for instance ACS3 has been selected a the new leader. This is the server that is going to be responsible of providing the Authorization Control Service until next election. We made all Authorization Control Services probe the leader after every ninety seconds by sending a IsAlive message to it. This is done in order to detect the failure of the current leader.

Tom want to request another file stored on the file server, but the Authorization Control Service has been moved from ACS1 to ACS3. Any attacker who was in the middle of preparing an attack against ACS1 will be attacking the wrong Authorization Control Service, which is the intended goal of our architecture. However, Tom will also be sending his authorization request to the wrong server.

Migration We have implemented the Migration Module as a mechanism to simply transfer the session history file and the policy file from the previous leader ACS1 to the elected leader ACS3. As stated in section 4.2, the other access control modules are the same across all Authorization Control Services. The reason for transferring ACS1 Policy file to ACS3 is that while ACS1 was providing the Authorization service, policies, resources and users may have been updated. To avoid disruption in the access control service, ACS3 needs to have the most recent policy file.

Other alternatives to this migration can be envisioned. One option is to store the policies in a Policy Database, and replicate the database across all the Authorization Control Services accordingly. Another option would be to migrate the database from the current leader to the new leader at the end of an election. An additional option would be to use a single Policy database that would be shared by all the Authorization Control Services. This last option can create a potential issue by making that single policy database a single point of failure attractive for would be attacker.

Discovery Service

We need to let Tom know that the Authorization Control Server ACS3 has been elected as the new leader, and therefore he should send his request to ACS3. The Discovery Service allows us to achieve that goal through the adaptation of SLP protocol.

We have implemented the Discovery Service using a tool called OpenSLP [START_REF]OpenSLP: Service location protocol[END_REF] which is an open source implementation of the Service Location Protocol. OpenSLP can be used either in a three components mode or in a two components mode. In the first mode, we can have a User Agent (UA), a Service Agent (SA) and Directory Agent (DA). The User Agent is the Agent requesting services. The Service Agent is the Agent providing the services, while the Directory Agent is the repository of services. In a two component mode, we can have only the User Agent and the Service Agent. In this case, the Service Agent plays also the role of a Directory Agent (DA). For the sake of this demonstration, we have implemented the later option. We have installed OpenSLP and made sure that sl pd, which is the OpenSLP daemon, is running.

Service Agent

Since our setting do not use a Directory Agent, the new leader will have to register its services with sl pd upon being elected. The old Authorization Control Service, previously registered, is unregistered to avoid confusing users. The new leader registers its access control service by issuing a query in the form of a ServiceURL. The ServiceURL has the following form: service:ServiceName://IPAddress:PortNo, where ServiceName is the Authorization Service, IPAddress is the IP address of the new leader, and PortNo is the port where the Authorization Service is running.

User Agent

In our setting, the User Agent is Tom who needs to find the location of the new leader which is providing the access control service. In order to discover the Authorization Service, Tom's client sends a multicast packet with a ServiceURL. The Service Agent, which is the new leader, will verifies if Tom's query matches the registered service. In case of a match, the Service Agent replies to Tom with the ServiceURL informing him how to access the access control service.

Conclusion and Future Work

We have sketched a Moving Target Defense architecture aiming at defending an Access Control Reference Monitor. The design allows a master Resource Access Server and a master Authorization Control Server to be periodically and randomly switched to other ones. This mechanism allows the disruption of any ongoing attack on the Access Control Reference Monitor. This work opens a new direction in research on Moving Target Defense of an Access Control Reference Monitor. This architecture can benefit from some improvements. For instance, we do not believe that the election algorithm is an optimal one in term of computation and the number of messages exchanged during the election process.

Fig. 1 .

 1 Fig. 1. Moving Target Defense Architecture

Algorithm 1 7 :

 17 Leader Election 1: /* Each node p executes the following */ 2: /* Initialization */ 3: e p = V P {Chosen value} 4: r p = 0 {Initial round} 5: ts p = 0 {Initial timestamps} 6: Estimates p = / 0 {list of estimate msg} Con f irms p = / 0 {list of comfirm msg} 8: Suspected p = / 0 {list of suspected nodes} 9: Out put p = / 0 {blacklisted nodes} 10: for r in listnode do 11: Suspecting p [r] = / 0 12

Fig. 2 .

 2 Fig. 2. Service Discovery flow

Fig. 3 .

 3 Fig. 3. Roles-Permissions assignment

Fig. 4 .

 4 Fig. 4. XACML architecture

Fig. 5 .

 5 Fig. 5. User Request sample

Fig. 6 .

 6 Fig. 6. Policy file sample

Fig. 7 .

 7 Fig. 7. Response sample

  1. A users client: It is an endpoint entity whose main objective is to access protected resources. It is responsible to initiate or terminate a session with the Resource Access Server. It resides on the individual devices running the applications that require access to shared resources. 2. Resource Access Service(RAS) : It is an entity that manages the various distributed resources and controls the access to it. It acts as both client and server when receiving or replying to access requests from the client. The decision to grant or deny the access to protected resources is received from the Authorization Control Server. The Resource Access Server is responsible for reinforcing that decision. 3. Authorization Control Service (ACS) : It is an endpoint entity that governs the access to each protected resource. It hosts the Access Control engine. The access control engine is based on RBAC model (other models are also possible) and is designed to prevent unauthorized access to protected resources. The policies defining the access to protected resources are also managed by the Authorization Control Service. This service receives any client request and replies with the decision to grant or deny the access to the needed resources. 4. Discovery Service : Since the protection of the Authorization Control Service requires this later to be moved to a different location in a non predictable manner, the clients need to be able to discover the new location of the Authorization Control Service. The Discovery Service provides such capability.

  irms p have common value e] then [p received select p msg from c = (r p mod n) + 1 and p has not sent con f irm q msg] then

	40:	ts p ← r p
	41:	e p ← e
	42:	Con f irm p ← (CONFIRM, q, r p , e) q
	43:	ready p = (READY, p, r p , e) p )
	44:	Send ready p to all
	45: 46:	else nready p = (NREADY, p, r p , e) p
	47:	Send nready p to all
	48: 49: end while end if 50: {Task 2: }
	51: while true do 52:
	53:	Selects p ← ((SELECT, c, r, e,ts) c )
	54:	con f irm p = (CONFIRM, p, r, e) p
	55:	send con f irm p to all
	56: 57: end while end if 58: {Task 3:}
	59: while true do 60: [Wait until received [(n + k)/2] + 1 distinct ready q
		messages from q nodes with common r,e]
	61:	decide(e)
	62: end while 63: {Task 4:}
	64: while true do 65: {Send list of suspected nodes}
	66:	Suspected p ← D 1
	67:	suspect p = (SUSPECT, p, Suspected p ) p

if

Acknowledgement

This work was partially supported by funding from CableLabs, the US National Science Foundation under grant number 1650573, and the US Department of Energy under contract DE-NE0008571. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of CableLabs, the National Science Foundation, or the Department of Energy.