Amir Herzberg
email: herzbea@cs.biu.ac.il

Ronen Margulies

My Authentication Album: Adaptive Images-Based Login Mechanism

We present the design and user study of an adaptive authentication mechanism based on recognition of user-custom images. The mechanism relies on memorizing the custom images on each primary login, and adaptively increasing the authentication difficulty upon failures (suspected impersonation attempts). The constant memorization of the images allows fallback authentication by recognizing all/most of the user's custom images. Our mechanism can be used for multiple authentication scenarios; in particular, it can provide effective phishing protection for primary and/or fallback web login. The mechanism features quick authentication times and low guessing probabilities.

Introduction

In today's world, users have accounts to many websites, devices and systems which require them to remember a password in order to identify. As seen on [START_REF] Vu | Improving password security and memorability to protect personal and organizational information[END_REF] and other studies, most users can only remember a limited amount of passwords, especially if those passwords are strong and hard-to-guess. Therefore, many users often forget their passwords. To deal with passwords forgetfulness, two families of countermeasures were suggested:

-Automatic fallback authentication techniques, aiming to allow authentication even if the password is forgotten. -Memorable alternatives to textual passwords, aiming to prevent users from forgetting their passwords in the first place.

Each authentication technique, primary or fallback, should deal with the following security and usability parameters:

Susceptibility to guessing attacks which includes both the password space (which should be large enough to effectively prevent brute-force attacks), and the susceptibility for educated guesses which could significantly reduce the password space. Susceptibility to phishing primary/fallback authentication techniques should prevent users from submitting their identifying information to a spoofed site. Memorability of the identifying information provided by the user. Usability the authentication times and ease of use.

Fallback authentication techniques ought to be (almost) as secure as the primary authentication in their resistance to guessing and phishing attacks, or else attackers will focus on attacking the fallback authentication mechanism, instead of the primary. In addition, since the fallback authentication process is not used frequently, the memorability of the identifying information has an increased importance. Since easily-remembered information might be easily-guessed, it is a true challenge to preserve its memorability and prevent its predictability. On the other hand, the fallback authentication could be somewhat slower and less convenient in comparison to the primary login.

Like fallback authentication, alternatives for the primary login also need to be as secure as the login ceremony they intend to replace, and should not have worse authentication times.

Textual passwords encounter some additional problems: users often choose passwords that are easily guessed, keyloggers can transfer them to an attacker, and sometimes typing is inconvenient/infeasible.

The Fallback Authentication Challenge

Today's most common mechanisms for automatic fallback authentication/password recovery are email-based mechanisms and security questions (a.k.a. challenge questions). Email-based mechanisms require access to a pre-configured email address, in order for the site to send back the password or a link to a password reset page. Security questions are used as identifying information, provided by the user during registration and supposed to be known only to the user.

Email-based password recovery reduces the security to that of the email account, which is often unacceptable. Security questions suffer from a few problems. First, they are susceptible to phishing attacks if no effective security indicators are used to help the user identify she reached her target site. This is due to the fact that security questions, like login forms, stimulate an automatic response among users causing them to answer the questions mindlessly. Karlof et al. found 92.7% spoof rate in their user study of security questions [START_REF] Karlof | Conditioned-safe ceremonies and a user study of an application to web authentication[END_REF].

In addition, early and recent studies of leading websites have shown that users tend to forget ∼20% of their answers and they are easily-guessed due to inherently low entropy [START_REF] Zviran | User authentication by cognitive passwords: an empirical assessment[END_REF][START_REF] Rabkin | Personal knowledge questions for fallback authentication: security questions in the era of facebook[END_REF][START_REF] Schechter | It's no secret. measuring the security and reliability of authentication via 'secret' questions[END_REF]. If a few and/or trivial questions are used, it is easy to find the answers, especially in today's social-networked world, where attackers can harvest all kinds of 'secret' information about users. Using many and/or non-trivial questions makes it harder for users to remember their questions for a long period of time.

Finally, the security questions mechanism does not prevent attackers from accessing the fallback authentication page, where they can try guessing the user's answers, possibly by presenting the same questions to the user and using the answers.

Graphical Passwords

Graphical passwords, a general name for authentication methods where images are used for authentication, were originally proposed as an alternative to textual passwords to deal with the problems textual passwords encounter:

-Ease of use on devices where typing is inconvenient (e.g. mobile devices with a touch screen, ATMs). -Increased memorability -Images are better remembered than textual phrases [START_REF] Shepard | Recognition memory for words, sentences, and pictures[END_REF]. -It is hard to write down a graphical password, or tell it to someone orally.

-Resistance to keyloggers.

An example for a graphical password scheme is Dèjá Vu, which was suggested by Dhamija and Perrig [START_REF] Dhamija | Dèjá vu: a user study using images for authentication[END_REF]. Dèjá Vu uses randomly created abstract images, which are unlikely to be guessed. On the authentication screen Dèjá Vu displays a grid with n images, k of whom are the user's custom images, which the user should identify (by 'clicking') to login; see figure 1.

Graphical passwords seem like a very nice and appealing alternative to textual passwords, and indeed several additional graphical password schemes were proposed [START_REF] Suo | Graphical passwords: A survey[END_REF][START_REF]Passfaces: Graphical password technology[END_REF]. Yet, due to their rather long authentication times (∼30 seconds in [START_REF] Dhamija | Dèjá vu: a user study using images for authentication[END_REF]), graphical passwords were not widely deployed as a substitute for textual passwords. In fact, for that reason they are better suited for fallback authentication.

In particular, a fallback authentication technique which require users to recognize items (as text phrases or images) they like or dislike was suggested by Jakobsson et al. [START_REF] Jakobsson | Quantifying the security of preferencebased authentication[END_REF]. Jakobsson et al. argue that this method is preferably, since it has higher entropy, and since they believe that preferences don't change much over the years, hence are better remembered.

Yet, in today's social-networked world users often publish their preferences in many areas, so (part of) the fallback authentication information can be found. In addition, as discussed in section 3, this method is susceptible to educated guesses. Finally, in their evaluation Jakobsson et al. found that 16 items (8 likes and 8 dislikes) are needed for sufficient security. We believe that recognizing such a large set of images/items after a long period of time from the initial setup, may prove hard, especially without periodically refreshing the user's memory.

The poor authentication times for primary authentication and poor memorability for fallback authentication raises a dilemma for the usefulness of graphical passwords. We propose a "learn-by-use" login mechanism which provides memorization of custom-images on the primary login while preserving its quick authentication times, and requires the user to recognize all/most of her images when fallback authentication is requested.

Contributions

We have designed and implemented a learn-by-use authentication mechanism, which is comprised of the following elements:

Single stage authentication requires the user to recognize and click one/few of her custom images from a small set of images on each primary login. Multiple Stages Authentication requires the user to recognize all/most of her custom images in multiple stages. The multiple-stages authentication is used for fallback authentication or as a difficult authentication scheme when an impersonation attack was detected. The use of multiple stages allows gradually increasing the authentication difficulty by increasing the number of stages. Detecting impersonation attacks and handling them with different levels of certainty. Adaptivity using different authentication difficulties on different scenariosweak authentication when additional identifiers are provided (passwords, cookies) and increasing the difficulty when no identifiers are provided and upon impersonation attacks.

One contribution of our mechanism is the constant memorization of the identifying information (custom images) it provides to the users, which can be used when fallback authentication is needed. Another contribution is the adaptive nature of our mechanism, which detects impersonation attacks and increases the authentication difficulty gradually as the certainty that an attack is witnessed increases. We also present the new concept (to the best of our knowledge) of detecting that part of the authentication secret is exposed to an attacker and asking the user to replace it upon high attack-certainty.

Another contribution is the flexibility of our mechanism, which allows different levels of security and usability. We present two main authentication usages; one that is more stringent and provides two-factor authentication and phishing protection, hence more suitable to sensitive sites; and one that is more alleviate, hence more suitable for less-sensitive sites. In both usages, our mechanism increases the security level of current login ceremonies without increasing the authentication times, provides a secure fallback authentication ceremony and handles impersonation attacks.

Finally, we conducted a long-term user study, whose results confirmed our mechanism's long-term memorability, quick authentication times and effective phishing-resistance.

Paper Layout

The next section describes our mechanism. Section 3 provides a security analysis of our mechanism in comparison to related work. Section 4 discusses its different applications and section 5 describes our user study and its results.

Mechanism Description

Registration. During registration the user chooses (or assigned) a small number of custom images (k ) from a large collection of images.

Single Stage Weak Authentication. On the primary login, the system displays a small set of L images, one of whom is one of the user's k custom images which she has to click in order to login. After each successful login, a new set of L images is chosen randomly for the next login. Since the user's custom images are displayed and clicked on each login, the primary login ceremony constantly refreshes the user's memory of her custom images, so they are better remembered when fallback authentication is needed. The single stage authentication provides only weak authentication (1/L guessing probability) and in most applications will be used in conjunction with other identifiers (passwords, cookies, etc.). In addition, our mechanism increases its authentication difficulty adaptively upon suspected impersonation attacks, thus the weak authentication can rapidly become strong.

Multiple Stages Authentication. On the multiple stages authentication, which is used for fallback authentication or upon suspecting attacks, the user is displayed with a series of k stages. Each stage displays n images, only one of whom is a usercustom image, and the user has to correctly click all/most of her custom images. If the user has chosen a wrong images in any of the stages, the ceremony continues until her k -th click and only then announces an unsuccessful authentication attempt. See figure 2. It is important to note that in all stages of different authentication attempts, the same images are displayed on each stage, or else an attacker will be able to isolate the user's custom images from the non-custom images.

Detecting and Handling Impersonation Attacks. Since one of the user's custom images is displayed on the primary login page, an attacker can find that image by accessing the primary login page and providing an initial identifier. After each successful login, the custom image will differ the next time the user (or the attacker) reaches the login page. This way, the attacker could constantly monitor the login page and check if any new images are displayed, until he finds most/all of the user's custom images.

An impersonation attack includes both a monitoring attack, and guessing attempts of the user's password or custom images. The first stage is to detect such attacks, and there are several ways for doing so. The system can notice when a user reaches the login page and does not try to authenticate at all, or mistakenly trying to guess the user's correct image (out of L), especially if this happened several times within a pre-determined period of time. Guessing attacks are detected by failed authentication attempts, i.e. submitting a wrong password or clicking incorrect images on the fallback authentication page.

After the system detected a suspected attack it increases the authentication difficulty adaptively to prevent the attacker from gaining more of the user's custom images or apply guessing attacks. As the difficulty increases, the attacker is likely to make more mistaken clicks or disconnect without trying to authenticate, which increases the attack's certainty even more. First, the system can increase the number of images displayed on the login page (for example, double them) after reaching some certainty threshold. Second, the system can apply the multiple stages scheme for increased difficulty. Third, the amount of stages can also be increased to m>k stages, each containing a "none of my images are here" choice, and only k of the stages display a user-custom image. The authentication difficulty can be further increased by using hindering measures such as CAPTCHAs between the stages.

After a pre-configured level of certainty was reached, the system can ask the user to replace her initial identifier (discussed on next section), and by logging the images that the suspected attacker correctly clicked, can also ask the user to replace those images. The site can also deal with guessing attempts of the textual password; if the guessing attempts were close enough to the user's correct textual password (for example, a small edit distance value), the site can ask the user to replace her password.

On [START_REF] Margulies | Usable and phishing-resistant authentication mechanisms[END_REF] we provide an algorithm for detecting and handling impersonation attacks, with varying levels of certainty, by using all the above-mentioned measures.

Security Analysis

In this section we analyze the security strength of our method in comparison to Dèjá Vu [START_REF] Dhamija | Dèjá vu: a user study using images for authentication[END_REF] and preferences-based security questions [START_REF] Jakobsson | Quantifying the security of preferencebased authentication[END_REF] we discussed previously. The theoretical password space of our mechanism is n k and Dèjá Vu's is n k (390,625 and 12,650 respectively for reasonable values of n=25 and k=4). The theoretical password space of preferences-based security questions is 16 8 = 12, 870, similar to Dèjá Vu's.

As seen on Davis et al.'s user study [START_REF] Davis | On user choice in graphical password schemes[END_REF], user chosen images/items can be highly predictable, especially among certain populations (based on gender, geographic location, age, etc.). It was evidenced in [START_REF] Davis | On user choice in graphical password schemes[END_REF] and in [START_REF] Dhamija | Dèjá vu: a user study using images for authentication[END_REF] that more appealing images and popular items (objects, places, food, etc.) have higher probabilities to be selected by users. In addition, correlations between images/items also exist. Therefore, basic prior knowledge of the users' background and preferences (taken for example from social networks) as well as knowledge of the selection probabilities and correlations (among the general population or different populations) can significantly increase the guessing probabilities in all three methods.

With preferences-based security questions, a unique correlation also exist: category-based correlation. Since users are requested to select their items from different categories, a person who likes sports, for example, might choose most of his 'likes' from the sports category. The mere fact that a person likes one of the categories in general could be quite easily drawn from social networks. If users are allowed to choose only few likes/dislikes from each category, then they won't choose their most liked and most disliked items, resulting in weaker memorability.

To avoid different probabilities and correlation as much as possible, the images used by a site implementing images-based authentication should:

-Be as general as possible (e.g., abstract images) and/or taken from the same category/topic. The site's topic can be a good idea for the images portfolio. -Be unfamiliar. For example, a traveling agency should use general images of landscapes and urban views, instead of popular sites.

-Have the same level of appeal.

Obviously, preferences-based security questions cannot follow those guidelines. Therefore, it is likely that our method and Dèjá Vu have lower guessing probabilities than preferences-based security questions, and the actual password space should be close to the theoretical password space (though correlations and different probabilities are still possible with abstract images or images from the same topic). Another advantage over preferences-based security questions is the ability of the site to continuously learn guessing probabilities and correlations, and to remove images with high/low probabilities and avoid displaying correlating images together in the setup phase of a specific user. Therefore, since Dèjá Vu has a similar theoretical password space as preferences-based security questions, but reduced guessing probabilities (with a good choice of the images portfolio), its security is stronger. In addition, since the guessing probabilities of our method and Dèjá Vu's are similar, our larger theoretical password space gets the lead.

Another advantage of our method in comparison to Dèjá Vu and preferencesbased security questions is the ability to increase the authentication difficulty to the m-stages scheme. Suppose the attacker knows c of the user's custom images; with the k -stages scheme his guessing probability is ( 1n ) k-c . With the m-stages scheme, he has to guess the correct k-c stages where the other custom images are displayed, and then guess the correct images on those stages. This reduces the guessing probability to 1 ( m-c k-c )

• ( 1 n ) k-c .

Applications

Authentication to Highly-Sensitive Sites

On [START_REF] Herzberg | Forcing johnny to login safely[END_REF] we describe an extensive long-term user study we conducted, which examined login mechanisms that force and train users to login safely and resist phishing attacks. We tested two forcing functions mechanisms:

A login bookmark which forces users to reach the site's login page via the bookmark by not allowing them to login when reaching it otherwise. The login page looks for a secret token contained in the bookmark link and presents an error message if a familiar token is not provided. This mechanism also provides two-factor authentication as both the secret token and the password are necessary for authentication. An interactive user-custom image which forces the user to look for and click her custom image on the login page, by hiding the password text field until the custom image is clicked.

The study's results showed that a combined method, which uses a login bookmark with an interactive custom image, displays several images in the login page, and training the user not to follow links by intentionally providing 'non-working' links, received outstanding prevention and detection rates, and resisted 93% of the attacks. We exploited the idea of the login bookmark and interactive custom images, and used them in conjunction with our learn-by-use authentication mechanism. The only difference of the primary login in comparison to the combined method in [START_REF] Herzberg | Forcing johnny to login safely[END_REF] is that the user now has k custom images instead of just one, and one of them is displayed on the login page along with L-1 other images (e.g. L=4). In addition to the site identification that the image click provides to the user, it also provides her with the necessary memorization of the custom images.

Users can choose to go to the fallback authentication page when they have forgotten their passwords or when using a mobile application/browser on a mobile device, where it might be easier to click images than typing the password.

Access to a user's fallback authentication page requires the secret token, just like the primary login. This prevents anyone who doesn't have the secret token from accessing the fallback authentication page, and from performing guessing attacks or spoofing the fallback authentication page.

Entrance to the fallback authentication page can be done via the primary login page; After the bookmark click, the site initially identifies the user by her secret token and sends back the login page with the user's custom image. After the user clicks her custom image, the site reveals, in addition to the password text field, a button which leads the user to the fallback authentication page. This promises that the user effectively identifies the site before trying to authenticate. It is important to note that the login bookmark itself isn't necessary to achieve two-factor and two-sided authentication, only the secret token is. An alternative can be a cookie containing the secret token, which should be previously installed via a secondary channel on each computer the user uses (for example with a registration email). Yet, we recommend using the login bookmark for several security and usability advantages discussed on [START_REF] Herzberg | Forcing johnny to login safely[END_REF].

We designed and implemented WAPP (Web Application Phishing Protection), a server side solution which implements the above mentioned mechanisms for primary login, as well as our fallback authentication mechanism (see http://submit2.cs.biu.ac.il/WAPP/ for a live demo).

Authentication to Less-Sensitive Sites

The mechanism we described can be altered for less-sensitive sites which do not aim to provide effective phishing protection or two-factor authentication. Many of today's sites that require authentication (e.g. gmail, facebook) provide the user with an option to create an authentication cookie containing a secret token when the user provides her password for the first time on a certain browser (usually with a "keep me signed in" check box). On the next logins from the same browser, those sites don't require a password at all if the cookie is installed. Our mechanism can also be used on such sites:

-When an authentication cookie is already installed, the site can display one of the user's custom images, together with several non-custom images (e.g., L=9) which provides the necessary memorization and further security (since a password is not required). The mechanism can be set to allow no mistakes and double the amount of images immediately after a single mistaken click (and increasing the difficulty rapidly on further mistakes). If a password is also required, the mechanism also provides phishing protection. -When an authentication cookie is not installed, no other initial identifier (such as the username) should be used instead. If the username is used to initially recognize the user and display her image, then the site is susceptible to MITM attacks: the attacker can spoof the initial page where the user provides her username, forward the username to the original site, get the image and display it to the user, and finally get the password from the user. This even provides a false-sense-of-security to the users.

Therefore, the site should first ask for the password and only then display the images. This does not provide phishing protection, but it provides the necessary memorization and further weak (and increasing) security. -If the user has forgotten her password or uses a mobile device, the site can allow her to authenticate using the k -stages authentication by providing her username only.

5 User Study

Study's Framework System

For our long-term phishing study in [START_REF] Herzberg | Forcing johnny to login safely[END_REF], we used an online exercise submission system called 'submit' (submit.cs.biu.ac.il), which is used by most courses at the computer science department of Bar-Ilan University. With the submit system, students submit their exercises and receive emails announcing new grades. Due to its wide usage, most users logged-in to the system dozens to hundreds of times throughout the study. We have used the system for three semesters, among a population of ∼400 students. In addition to its primary usage as an exercise submission system, we simulated several phishing attacks and collected the results.

We extended the phishing study to test our fallback authentication mechanism in the fourth semester. Users were asked to choose 3 or 4 new custom images (in addition to their existing custom image). One of their custom images was randomly selected and displayed on the login page on each login (along with three other non-custom images). Users were tested with the k -stages authentication scheme twice -immediately after they have chosen their additional custom images and once again 2-3 months later, while using the system regularly (and clicking one of their images on each login). In both tests, users had only one authentication attempt, and they were not forced to succeed in order to proceed with their exercise submission.

We logged the success rates and authentication times, and also examined if there was a decrease in the detection rates of spoofed login pages in comparison to the previous semesters (where users had only one custom image), especially for spoofed login pages displaying only fake images.

Results

The memorability of the custom images and the authentication times are of course affected by the amount of entrances to the system between the setup and authentication attempt. The more times a user enters the system, the better she remembers her images and authenticates faster. Table 1 summarizes our results and compares them to Dhamija and Perrig's study [START_REF] Dhamija | Dèjá vu: a user study using images for authentication[END_REF], where all users authenticated once after one week from the setup phase. The table displays the results of users from the top 25% of entrances (21+), top 50% of entrances (8+) and a base line of minimum entrances we chose (5+). The results show reasonable authentication times, similar to Dèjá Vu. The success rates of users who entered the system eight times or more are quite good, especially if the system allows a single mistake. For users who entered the system more than 20 times, the results are very good even when no mistake is allowed. The results are expected to improve even more if several attempts are allowed and if users will have to succeed to use the system. Yet, it can be assumed that users remembered their custom image that preceded the experiment, so the results can be somewhat reduced. For a better picture, a longer-term experiment, which compares our method with other techniques, is still needed. Surprisingly, we found better success rates for users with five custom images than users with four, suggesting that using five images and allowing a single mistake is the best option. Even with four images (out of five) needed for authentication, the password space of our method is larger than the password space of Dèjá Vu with five images1 .

Finally, there was no degradation in the detection rates of spoofed pages for users with eight or more entrances, and no increased false negative rates (falsely reporting a non-spoofed page).

Conclusions and Future Work

We have described an images-based authentication mechanism which reminds the user of her custom images on each primary login, so they will be highly memorable when a fallback authentication is needed. Our fallback authentication mechanism was shown to be quick and memorable after sufficient training on our user study. Our mechanism also increases its difficulty adaptively upon detecting impersonation attacks. The mechanism is well suited for different web authentication scenarios, providing different levels of security and quick authentication times. Our fallback authentication scheme provides a large password space and high resistance to guessing attacks, and for sensitive sites it also provides effective phishing protection.

Another important authentication scenario that our mechanism suits for, is the authentication to mobile devices. Since authentication to mobile devices should be quick (as it is done very frequently) and the mere possession of the device can be assumed to provide some identification, than the authentication can start with our single-stage authentication and rapidly increase its difficulty upon each mistaken click. It can also be combined with other identifying measures.

Fig. 1 .

 1 Fig. 1. Dèjá Vu's abstract images selection.

Fig. 2 .

 2 Fig. 2. The multiple (k ) stages authentication scheme. The user must click all/most of her custom images.

Table 1 .

 1 Memorability and authentication times of our method in comparison to Dèjá Vu. We expect that allowing several login attempts will improve our method's results.

			images	weeks	no	up to	auth.	auth.
	method entrances	used	from mistakes	one	attempts time
				setup		mistake		(seconds)
	Ours	5+	photos+abstract 8-12 65.3%±11.2 87.7%±7.7	1	38
	Ours	8+	photos+abstract 8-12 67.5%±12.2 90%±7.8	1	38
	Ours	21+	photos+abstract 8-12 84.2%±13.8 94.7%±8.4	1	31
	Dèjá Vu	0	photos	1	95%±8	100%	no limit	27
	Dèjá Vu	0	abstract	1	90%±11	100%	no limit	32

25 4 / 5 4 =78,125 and

5 =53,130 respectively

Acknowledgments

This research was supported by grant 1354/11 from the Israeli Science Foundation (ISF).


Joan Boyar

René Peralta
email: rene.peralta@nist.gov

A Small Depth-16 Circuit for the AES S-Box

.

Introduction

Constructing optimal combinational circuits is an intractable problem under almost any meaningful metric (gate count, depth, energy consumption, etc.). In practice, no known techniques can reliably find optimal circuits for functions with as few as eight Boolean inputs and one Boolean output (there are 2 256 such functions). Thus, heuristic or specialized techniques are necessary in practice. The depth of a circuit is the number of gates on a longest path. Reducing depth generally leads to faster circuits. Reducing the number of gates is important for reducing area and power consumption. The aim is to reduce both simultaneously, but there is often a trade-off between these two goals.

Many different logically complete bases are possible for circuits. Since the operations in the basis (XOR, AND) are equivalent to addition and multiplication modulo 2 (i.e., in GF (2)), much work on circuits for cryptographic functions uses this basis. For logical completeness, the negation operation (or the constant 1) is needed as well. In GF (2), negation corresponds to x + 1. For technical reasons, and for an accurate gate-count, we use XNOR gates (XN OR(x, y) = x + y + 1 in GF (2)) instead of negation. This platform-independent basis leads to easy comparison with previous implementations. Note that changing AND gates to NANDs is not difficult.

The Advanced Encryption Standard (AES) is a widely used symmetric key encryption system that was adopted as a standard by the U.S. government in 2002. The nonlinear part of AES is the SubBytes step, which is often referred to as the S-Box. The original specification of AES [START_REF]NIST: Advanced Encryption Standard (AES) (FIPS PUB 197[END_REF] defined the S-Box as the multiplicative inverse in the field GF (2 8 ), followed by an affine transformation.

However, the S-Box can also be implemented using table look-up. This requires a ROM with 2048 bits. However, ROMs are not efficient in terms of size/power consumption. Satoh et al. [START_REF] Satoh | A compact Rijndael hardware architecture with S-Box optimization[END_REF], using a tower-of-fields approach to compute the S-Box, designed a combinational circuit that can be implemented with an area under 1/4 of previous ROM-based designs. Other work, for example [START_REF] Canright | A very compact Rijndael S-box[END_REF][START_REF] Morioka | An optimized S-Box circuit architecture for low power AES design[END_REF][START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF], has improved on this size.

Recently, Nogami et al. [START_REF] Nogami | Mixed bases for efficient inversion in F(((2 2 ) 2 ) 2 ) and conversion matrices of subbytes of AES[END_REF] presented a technique for reducing circuit depth in the forward direction of the AES S-Box. Their technique was primarily to choose mixed bases for the tower-of-fields architecture in such a way that the 8×8 matrices doing the linear transformations at the top and bottom had at most 4 ones in every row. In this way they were able to compute these transformations in depth 2 each, for a total of depth 4. Their technique cannot be simultaneously applied to the AES circuit in the reverse direction, as the inverse matrices do not have at most 4 ones in every row.

We present more general techniques that are less dependent on the actual representation of the fields. These techniques allow us to produce circuits which are both smaller and shorter than those in [START_REF] Nogami | Mixed bases for efficient inversion in F(((2 2 ) 2 ) 2 ) and conversion matrices of subbytes of AES[END_REF]. Although the size of our construction is larger than our size-optimized circuit [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF] (which had only 115 gates but had depth 28) it is comparable to previous efforts to make a small circuit (the constructions in [START_REF] Canright | A very compact Rijndael S-box[END_REF] and [START_REF] Morioka | An optimized S-Box circuit architecture for low power AES design[END_REF] have depths 25 and 27, respectively). The work of Nogami et al. improved on the forward direction of the S-Box to depth 22 at the cost of increasing the number of gates to 148. Our new circuits have depth 16 in both directions, size 128 in the forward direction, and size 127 in the reverse direction. The part that is shared between the forward and reverse directions is of size 63.

A general overview of the technique is described in Section 2, and the technique used for the nonlinear component, inversion in GF (2 4 ), is described in Section 3. A greedy heuristic for linear components is described in Section 4. Further techniques for depth and size reduction are described in Section 5. The AES S-Box circuits are presented in Section 6 and conclusions in Section 7.

Combinational Circuit Optimization

Under the basis (XOR,XNOR,AND), classic results by Shannon [START_REF] Shannon | The synthesis of two-terminal switching circuits[END_REF] and Lupanov [START_REF] Lupanov | A method of circuit synthesis[END_REF] show that almost all predicates on n bits have circuit complexity about

2 n
n . The multiplicative complexity of a function is the number of AND gates necessary and sufficient to compute the function. Analogous to the Shannon-Lupanov bound, it was shown in [START_REF] Boyar | On the multiplicative complexity of Boolean functions over the basis (∧, ⊕, 1)[END_REF] that almost all Boolean predicates on n bits have multiplicative complexity about 2 n 2 . Strictly speaking, these theorems say nothing about the class of functions with polynomial circuit complexity. However, it is reasonable to expect that, in practice, the multiplicative complexity of functions is significantly smaller than their Boolean complexity. This is one of the principles that guide our design strategy.

Circuits with few AND gates will naturally have large sections which are purely linear. The authors [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF] and Courtois et al. [START_REF] Courtois | Solving circuit optimisation problems in cryptography and cryptanalysis[END_REF] have used this insight to construct circuits much smaller than previously known for a variety of applications. The heuristic is a two-step process which first reduces multiplicative complexity and then optimizes linear components.

The work presented in this paper is based on the idea that a short circuit may be obtained by starting from a small (i.e. optimized for size) circuit and performing three types of optimizations with automatic heuristics:

use techniques from automatic theorem proving to re-synthesize non-linear components into lower-depth constructions; -apply a greedy heuristic to re-synthesize linear components into lower-depth constructions; -perform depth-shortening and size-reducing local replacement.

These techniques are explained below. They will often increase the size of the circuit, but we start with our small circuit from [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF], and the techniques are designed to minimize the size increase.

The Tower Field Construction: A Nonlinear Component

There are many representations of GF (2 8 ). We construct

-GF (2 2
) by adjoining a root W of x 2 + x + 1 over GF (2); -GF (2 4 ) by adjoining a root Z of

x 2 + x + W 2 over GF (2 2 ). -GF (2 8
) by adjoining a root Y of x 2 + x + W Z over GF (2 4 ).

Thus, there is a tower of fields, each one contained in the previous, and one can do multiplication and inverse operations in the larger fields efficiently by implementing the relevant operations in the smaller fields efficiently, as in [START_REF] Itoh | A fast algorithm for computing multiplicative inverses in GF (2 m ) using normal bases[END_REF].

As does Canright in [START_REF] Canright | A very compact Rijndael S-box[END_REF], we represent GF (2 2 ) using the basis (W, W 2 ), GF (2 4 ) using the basis (Z 2 , Z 8 ), and GF (2 8 ) using the basis (Y, Y 16 ).

Let A = a 0 Y + a 1 Y 16 be an arbitrary element in GF (2 8 ). Following [START_REF] Itoh | A fast algorithm for computing multiplicative inverses in GF (2 m ) using normal bases[END_REF], the inverse of A can be computed as follows:

A -1 = (AA 16 ) -1 A 16 = ((a 0 Y + a 1 Y 16 )(a 1 Y + a 0 Y 16 )) -1 (a 1 Y + a 0 Y 16 ) = ((a 2 0 + a 2 1 )Y 17 + a 0 a 1 (Y 2 + Y 32 )) -1 (a 1 Y + a 0 Y 16 ) = ((a 0 + a 1 ) 2 Y 17 + a 0 a 1 (Y + Y 16 ) 2 ) -1 (a 1 Y + a 0 Y 16 ) = ((a 0 + a 1 ) 2 W Z + a 0 a 1 ) -1 (a 1 Y + a 0 Y 16 ).
Thus, computation of the inverse in GF (2 8 ) can be done using operations in GF (2 4 ) as follows:

T 1 = (a 0 + a 1 ); T 2 = (W Z)T 2 1 ; T 3 = a 0 a 1 ; T 4 = T 2 + T 3 ; T 5 = T -1 4 ; T 6 = T 5 a 1 ; T 7 = T 5 a 0 ;
The result is

A -1 = T 6 Y + T 7 Y 16 .
The GF (2 4 ) operations involved are addition, multiplication, square and scale by WZ, and inverse. Of these, only multiplication and inverse turn out to be non-linear. We derive a standard GF (2 4 ) multiplication circuit by reduction to GF (2 2 ) operations. The standard inversion circuit, however, has more gates and depth than necessary. Hence we derive a better circuit here.

Let 8 where the y i 's satisfy the following polynomials over GF (2) (see [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF]):

∆ = (x 0 W + x 1 W 2 )Z 2 + (x 2 W + x 3 W 2 )Z 8 be an arbitrary element in GF (2 4 ). It is not hard to verify that its inverse is ∆ -1 = (y 0 W + y 1 W 2 )Z 2 + (y 2 W + y 3 W 2 )Z
-y 0 = x 1 x 2 x 3 + x 0 x 2 + x 1 x 2 + x 2 + x 3 -y 1 = x 0 x 2 x 3 + x 0 x 2 + x 1 x 2 + x 1 x 3 + x 3 -y 2 = x 0 x 1 x 3 + x 0 x 2 + x 0 x 3 + x 0 + x 1 -y 4 = x 0 x 1 x 2 + x 0 x 2 + x 0 x 3 + x 1 x 3 + x 1
The heuristic we used in [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF] to compute the y i 's was inspired by methods from automatic theorem proving. Consider an arbitrary predicate f on n inputs. We refer to the last column of the truth table for f as the signal of f . The columns in the truth table corresponding to each of the inputs to f are known signals. A search for a circuit for f starts with this set S of known signals. If u, v are known signals for functions g, h respectively, then the bit-wise XOR (AND) of u and v is the signal for the predicate g⊕h (g∧h). We can grow the set S by adding the XOR of randomly chosen signals. We call this step an XOR round. The analogous step where the AND of signals is added to S is called an AND round. Each round is parametrized by the number of new signals added and the maximum number of AND gates allowed. In either an XOR round or an AND round, two signals are not combined if doing so creates a circuit with more AND gates than is allowed. The heuristic alternates between XOR and AND rounds until the target signal is found or the set S becomes too large. In the latter case, since this is a randomized procedure, we start again.

In [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF] we used this heuristic to find a circuit with only 5 AND gates and 11 XOR gates, but depth 9. In terms of size, this was a significant improvement over previous constructions (e.g. [START_REF] Paar | Some remarks on efficient inversion in finite fields[END_REF][START_REF] Canright | A very compact Rijndael S-box[END_REF]). All these constructions, however, were mostly concerned with size. To minimize depth without incurring a large increase in size, we use the search techniques described above, but add code to discard search paths that either violate given depth constraints or size constraints. With this modification, we found a circuit with depth 4 and size 17. The straight-line program for the circuit is in Figure 1 (arithmetic is over GF (2)).

A Greedy Heuristic for Linear Components

After this small circuit for inversion in GF (2 4 ) was found, it was set into the original circuit for AES (we started with the circuit in [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF]), and maximal linear components, connected components of the circuit not containing any AND gates, were found. The largest linear components in our circuit are the top linear and bottom linear components. These components contain more than the

t1 = x2 + x3 t2 = x2 × x0 t3 = x1 + t2 t4 = x0 + x1 t5 = x3 + t2 t6 = t5 × t4 t7 = t3 × t1 t8 = x0 × x3 t9 = t4 × t8 t10 = t4 + t9 t11 = x1 × x2 t12 = t1 × t11 t13 = t1 + t12 y0 = t2 + t13 y1 = x3 + t7 y2 = t2 + t10 y3 = x1 + t6 Fig. 1. Inversion in GF (2 4 ). Input is (x0, x1, x2, x3
) and output is (y0, y1, y2, y3).

U T =             0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0             Fig. 2.
The transpose U T of the top linear transformation U .

linear operations defined explicitly in the definition of the AES S-Box and the matrices to do the basis changes. This is because they include some of the finite field inversion operations. The top linear component is defined by the matrix U , a 22 × 8 matrix (Figure 2), meaning that 22 linear combinations of the 8 inputs are calculated. One can compute all 22 of the required outputs with only 23 XOR gates, and 23 are necessary [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF][START_REF] Fuhs | Synthesizing shortest linear straight-line programs over GF(2) using SAT[END_REF][START_REF] Fuhs | Optimizing the AES S-Box using SAT[END_REF]. But these results do not attempt to minimize depth (the depth is 7). Since there are only 8 columns in this matrix, each of the 22 outputs could clearly be calculated independently using depth at most 3, simply by using a balanced binary tree with the inputs as leaves. The challenge is to achieve the low depth without increasing the number of XOR gates drastically. The algorithm below does this. (Note that although the linear transformation at the top of Nogami et al.'s circuit only has depth 2, they have XOR gates at depth 3, so their top linear component also has depth at least 3.)

The bottom linear component is defined by the matrix B, an 8 × 18 matrix (Figure 3). The row with the largest Hamming weight (number of ones = number of variables added together) has 12 ones, so depth at most 4 is possible for this component.

The smallest circuits for these two matrices, U and B, use the concept of cancellation of variables. Note that in [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF], the variable y 11 is computed as y 20 ⊕y 9 . Since y 20 = x 0 ⊕ x 1 ⊕ x 3 ⊕ x 4 ⊕ x 5 ⊕ x 6 and y 9 = x 0 ⊕ x 3 , the result is y 11 = x 1 ⊕ x 4 ⊕ x 5 ⊕ x 6 ; the x 0 and x 3 are cancelled.

When attempting to find small, low-depth circuits for a linear component, one expects that cancellation of variables will be of limited help, since it would often require that something with a large Hamming weight has already been

B =            
0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 computed, before adding one to the depth at the gate where the cancellation occurs. Thus, it seems reasonable to start with a technique which does not allow cancellation, and then try to add cancellation afterwards where it helps.

           
We modify Paar's technique [START_REF] Paar | Optimized arithmetic for Reed-Solomon encoders[END_REF], a greedy approach which produces cancellation-free programs. Paar's technique keeps a list of variables computed, which is initially only the inputs. Then it repeatedly determines which two variables, XORed together, occur in most outputs. One such pair is selected and XORed together. This result is added as a new variable which appears in all outputs where both variables previously appeared. This is repeated until everything has been computed. Paar's technique is implemented by starting with the initial matrix and adding columns corresponding to the new variables which are added. When a new column is added, this corresponds to adding two existing variables, u and v. In all rows in the matrix which currently have a one in both of the columns corresponding to u and v, those two ones are changed to zeros, and a one is placed in the corresponding row of the new column. All other values in the new column are set to zero.

The Low Depth Greedy algorithm maintains the greedy approach of Paar's technique, but only allows this greediness as long as it does not increase the circuit's depth unnecessarily. Assume that k is the depth we are aiming for, i.e. k = ⌈log 2 (w)⌉, where w is the largest Hamming weight of any row. This new algorithm has k phases, starting with 0. At the beginning of a new phase, we check if any row has Hamming weight two. Since there must be an additional gate to produce that output, we produce it at the beginning of the phase so that it affects all counting in the current phase. During phase i ≥ 0, no row in the current matrix has Hamming weight more than 2 k-i and only inputs or gates already produced at depth i or less are considered as possible inputs to gates in phase i. Thus, the depth of gates in phase i is at most i + 1. When choosing two possible inputs for gates, one chooses a pair which occurs most frequently in the current rows, with the restriction, of course, that both inputs are at level i or less. Pseudo-code for this algorithm is given in Figure 4. This algorithm produces a minimum depth (optimal depth) circuit.

ℓ = 1 to m do if M [ℓ, j1] = M [ℓ, j2] = 1 then M [ℓ, j1] := 0; M [ℓ, j2] := 0; M [ℓ, s] := 1 else M [ℓ, s] := 0 s := s + 1
Fig. 4. Algorithm for creating a minimum depth circuit for linear components depth-k circuit for computing the linear component defined by the matrix. The running time is O(mt 3 ), where t is the final number of columns and is at most mn + nm.

Proof. If one considers the inputs as being produced at depth zero, in phase i of the algorithm, only variables which have been produced at depth at most i are considered as possible inputs to XOR gates, so the XOR gates produced have depth at most i + 1. This is maintained inductively by only considering columns between 1 and ip, and ip is reset at the end of each phase to the last column produced in that phase. Since the algorithm maintains that at the beginning of phase i, no more than 2 k-i of the current variables have to be XORed to produce any output, the algorithm terminates in phase k -1, giving maximum depth k. Note that it will always be possible to proceed from phase i to phase i + 1, since combining the at most 2 k-i ones any row by pairs will reduce the number of ones to at most half as many, at most 2 k-i-1 .

For each XOR gate added, the algorithm checks every pair of columns between 1 and ip < s, where s is the new column being added. For each of these pairs of columns, one checks for each row if both entries corresponding to these columns are one and then does some updating. The number of rows is m, so the total running time is O(mt 3 ). Since there are at most n ones in every row, each row will be computed using at most n -1 XORs, and all m rows will be computed with at most m(n -1) XORs. There are n columns initially, so in all t ≤ mn + nm.

⊓ ⊔

Another possibility for an algorithm to produce optimal depth circuits for linear components would have been to finish with all pairs of inputs before continuing to pairs involving gates at depth one, and then to finish with all pairs at depth one (or involving the possibly one remaining input which has not been paired), etc. However, the method chosen here allows more flexibility in choosing gates, thus allowing more possibilities to create gates which can be used more than once.

Local Optimizations

After applying the techniques discussed in the previous sections, highly localized optimizations may be possible.

We are able to further decrease the number of gates in the top linear component since not all the XOR gates at level three (an output of the top linear component) would necessarily increase the total depth if they were at level four or more (for the AES S-Box, k and k + 1 more generally). Or, on the other hand, one might be able to reduce the depth even more by calculating some outputs of the top linear component at lower depth than the depth indicated by the matrix row with largest Hamming weight, if these "outputs" are on a longest path.

It is easy to determine which outputs of the top linear component could be allowed to be at a larger depth or should be at a lower depth if possible, using a program which calculates the depth and height of every gate. If all of the outputs of the top linear component which have depth and height values adding up to exactly the total depth of the circuit are such that they could have been calculated at lower depth than their current depth, then one can probably reduce the depth of the circuit. On the other hand, when these values add up to less than the total depth of the circuit, there is some slack at that gate. For XOR gates at depth 3 (in an AES S-Box circuit) which have slack, one can check if they are the sum of any two of the other outputs of the top-linear part. If they are, these other outputs were computed at depth 3, so adding them together only gives depth 4, which is acceptable when the output was originally created at a gate with slack. Note that cancellation of variables should be allowed here.

The Low Depth Greedy algorithm can be modified to take advantage of slackness. In this case, an extra array Factor is initialized for each input to the linear transformation. Rows with no slack are given the value 1, and rows that could be at j levels further down than the minimum are given the value 2 j in Factor. Then, when checking if one should proceed to the next phase, rather than check if all rows have Hamming weight at most 2 k-i for phase i, one checks if its Hamming weight divided by its value in Factor is at most 2 k-i . This allows the possibility of choosing inputs required for these outputs at a larger depth. These modifications of the Low Depth Greedy algorithm were not actually necessary to produce the circuits found.

Finally, there are straight-forward techniques for reducing depth in linear components via local replacement. Consider any gate in such a component. The output produced there is the XOR of several values (either inputs or outputs from other gates). These values can be XORed in any order to get this result. For example, suppose g = g 1 ⊕g 2 , g 1 = g 3 ⊕g 4 , and g 1 is at depth d. If the depths of g 2 and g 3 are at most d -2, then g is at depth d + 1 and g 4 is at depth at d -1. Now calculating h 1 = g 2 ⊕ g 3 and h 2 = h 1 ⊕ g 4 results in h 2 computing the same result as g, but at depth one lower, d. If the result computed at g 1 was not used anywhere else in the circuit, then this does not increase the total number of gates. However, if g 1 is used elsewhere, it would still need to be computed, and the number of gates would increase by one.

The circuits were generated automatically using randomization for tie-resolution. Different runs of our code yield depth 16 consistently. However, size can vary by a few gates. As long as the topology derived from the tower-offields method is maintained, we conjecture that it is unlikely that the size of the circuits can be significantly reduced without increasing the depth. We also conjecture that it is unlikely that the depth can be reduced without significantly increasing size. Of course, if the logical base is expanded, we may be able to do better. For example, if NAND gates are used in the circuit for inversion in GF (2 4 ), it is not hard to reduce the number of gates by two without increasing the depth (see appendix). Since there are only 256 possible inputs, we verified the circuits fully against the specifications in [START_REF]NIST: Advanced Encryption Standard (AES) (FIPS PUB 197[END_REF].

Conclusion

The techniques used in [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF][START_REF] Courtois | Solving circuit optimisation problems in cryptography and cryptanalysis[END_REF] to obtain smaller AND/XOR circuits were modified and extended here to consider the depth of the circuits produced. The resulting techniques were successfully applied to the AES S-Box, significantly improving, both in size and depth, over another recent attempt at a low depth S-Box [START_REF] Nogami | Mixed bases for efficient inversion in F(((2 2 ) 2 ) 2 ) and conversion matrices of subbytes of AES[END_REF].

The techniques presented in this paper appear, not surprisingly, to lead to a trade-off between size and depth. The modification of our search technique [START_REF] Boyar | A new combinational logic minimization technique with applications to cryptology[END_REF] to find circuits with few AND gates, which rejected candidates with too large depth, decreased the depth of the GF (2 4 ) inversion from 9 to 4 while only increasing the number of gates from 16 to 17, changing 5 AND gates and 11 XOR gates to 7 AND gates and 10 XOR gates. Thus, most of the trade-off was due to the techniques for handling large linear components, especially the Low -Depth Greedy algorithm. To illustrate this trade-off, we list the depths and sizes of some of the circuits for the AES S-Box which were obtained in the course of this research:

-

Fig. 3 .

 3 Fig. 3. The bottom linear transformation B.

Theorem 1 .

 1 When given an m × n 0-1 matrix, M , with maximum Hamming weight at most 2 k in any row, Algorithm Low Depth Greedy, produces a correct, Low Depth Greedy(M, m, n, k): { M is an m × n 0-1 matrix with Hamming weight at most 2 k in any row} s := n + 1 { index of the next column } for i := 0 to k -1 do ip := s -1 { keep track of which gates had depth at most i } while there is some row in M with Hamming weight > 2 k-i-1 do { Phase i } if some row ℓ in M with weight 2 had weight 2 at the beginning of the phase then let j1 and j2 be the columns in row ℓ with ones else find two columns 1 ≤ j1, j2 ≤ ip which maximize |{ℓ | M [ℓ, j1] = M [ℓ, j2] = 1}| add an XOR gate with inputs from the variables for columns j1, j2 the output variable produced will correspond to column s for

  depth 28; size 115: original circuit depth 23; size 116 -depth 22; size 117 -depth 21; size 118 -depth 20; size 122 -depth 16; size 128: final result

⋆ Partially supported by the Danish Council for Independent Research, Natural Sciences.

The Circuits

The depth-16 circuits are shown in Figures 5,[START_REF] Fuhs | Optimizing the AES S-Box using SAT[END_REF][START_REF] Fuhs | Synthesizing shortest linear straight-line programs over GF(2) using SAT[END_REF][START_REF] Itoh | A fast algorithm for computing multiplicative inverses in GF (2 m ) using normal bases[END_REF][START_REF] Lupanov | A method of circuit synthesis[END_REF]. Note that the addition and multiplication operations are modulo 2, so they are XOR and AND operations. The # operation is an XNOR (adding modulo 2 and then complementing the result) and is only used for the outputs. We used Algorithm Low Depth Greedy for the four linear transformations (here, we do not include the binary matrices corresponding to the transformations in the reverse direction of the AES S-Box). The circuits are divided into three components: top linear transformations (Figures 5 and6), shared non-linear component (Figure 7), and bottom linear transformations (Figures 8 and9).

Fig. 6. Top linear transform in reverse direction.


Baozeng Ding

Fufeng Yao

Yanjun Wu
email: yanjun.wu@gmail.comyeping@iscas.ac.cn

Yeping He

Improving Flask Implementation Using Hardware Assisted In-VM Isolation

Keywords: Flask Architecture, Virtualization, Security, In-VM Isolation, Extended Page Tables

The Flask architecture, which mainly contains object manager (OM) and security server (SS), is widely used to support flexible security policies in operating system. In nature, OM and SS should be isolated from each other to separate decision from enforcement. However, current implementation of Flask, such as SELinux and SEBSD, puts both OM and SS in the same address space. If one component is subverted, the whole system will be exposed to the attacker. In this paper, we present hardware assisted in-VM isolation to improve the security of the Flask implementation. The key of our approach is the separation of SS from other parts of guest OS by constructing hardware assisted page tables at the hypervisor level. In this way SS can execute in a strongly isolated address space with respect to its associated guest OS, and therefore can provide a trustworthy and centralized repository for policy and decision-making. Our experiment shows that our method introduces moderate performance overhead.

Introduction

Since operating system kernels occupy a privileged position in the software stack of computer systems, exploiting kernel-level vulnerability gives attackers completely control of systems. So protecting the integrity of operating system is very important. The Flask architecture [START_REF] Spencer | The Flask security architecture: system support for diverse security policies[END_REF], which mainly contains object manager (OM) and security sever (SS), is widely used to support flexible security policies in operating system.

Various security modules such as SELinux [START_REF] Loscocco | Integrating flexible support for security policies into the linux operating system[END_REF], SEBSD [START_REF] Vance | Security Enhanced BSD[END_REF], have been implemented using the Flask architecture. Since such modules play an important role in the system security, it is important to protect them from being attacked. In nature, OM and SS should be isolated from each other to separate decision from enforcement. However, current implementation of Flask, places both OM and SS in the same address space. If one component is subverted, the security module will be broken and the system will be exposed to the attacker.

As far as we know, there is no effective ways to protect the Flask implementation. Kernel-level integrity protection of Flask is not enough, as these protection mechanisms reside in the same privilege level as the operating system kernel. They could be potentially bypassed or subverted. Virtualization gives us a chance to improve the security of Flask implementation. As the virtual machine monitor (VMM), also known as the hypervisor, exists on the lower level than the kernel, it could be used to detect and prevent the attacks against the Flask. Livewire [START_REF] Garfinkel | A virtual machine introspection based architecture for intrusion detection[END_REF], VMwatcher [START_REF] Jiang | Stealthy malware detection through vmm-based "out-ofthe-box" semantic view reconstruction[END_REF], Lares [START_REF] Payne | Lares: An architecture for secure active monitoring using virtualization[END_REF], Patagonix [START_REF] Litty | Hypervisor support for identifying covertly executing binaries[END_REF] raised to protect the guest kernel integrity utilizing virtualization. These approaches leverage a separate trusted VM to monitor the untrusted VM. Although these out-of-VM approaches have good security effect, they are suitable only for monitoring the events that occur infrequently during system running because switching between VMs causes large overhead. So it's not appropriate for protecting Flask architecture which is used to actively monitor those events occurring frequently.

SIM [START_REF] Sharif | Secure in-VM monitoring using hardware virtualization[END_REF] is an In-VM monitoring framework that puts security tools in the same VM. It utilizes shadow page tables (SPT) mechanism [START_REF] Barham | Xen and the art of virtualization[END_REF] to create a separate virtual address space called SIM address space in the guest VM. It's a one-side view address space and exists in parallel to the system address spaces used by guest kernel. That means the code in the kernel address space cannot visit SIM address space directly but the code in the SIM address space can visit the kernel code. Security monitor is placed in the SIM address space so that it can be isolated from the untrusted kernel, and therefore is protected. It also leverages a feature of Intel VT to reduce the overhead when switching between the system address space and the SIM address space. This way gives SIM the performance benefits and the same security level as out-of-VM method. However, the SPT mechanism that SIM uses will result in expensive VM exits and context switches when synchronizing the shadow page tables with guest page tables [START_REF] Wang | Selective hardware/software memory virtualization[END_REF]. Moreover, the source code structure of the shadow page tables is quite complex and not easy to maintain [START_REF] Wang | Selective hardware/software memory virtualization[END_REF].

In this paper, we utilize Intel Extended Page Table (EPT) technology [21] to design a hardware assisted in-VM framework to isolate SS from the kernel. Isolated SS provides a trustworthy and centralized repository for policy and decision-making. EPT is an Intel hardware virtualization technology that is used to support the virtualization of physical memory. It controls the translation from guest physical addresses to the host physical address. The extended page table is shared by all the process in the guest VM and we call it system EPT which constructs system address space. In order to construct an isolated address space for SS, we create an independent EPT called SS EPT. This EPT maps all the physical addresses that belong to the guest VM, which constructs security server address space. Then we modify the origin system EPT to eliminate the mapping for SS code and data. In this way, the code in the kernel cannot access SS code and data directly. It has to enter security server address space by switching from system EPT to SS EPT to call SS function. We use UnixBench [11] to evaluate our prototype. The result shows the overhead is moderate. As AMD Nested Page Tables (NPT) [START_REF]Advanced Micro Devices[END_REF] technology is similar to EPT, our work can be extended to the system with an AMD CPU. To the best of our knowledge, our work is a first step towards constructing in-VM isolation using hardware assisted page tables to improve Flask implementation.

Background

2.1

The Flask Architecture Overview

Flask [START_REF] Spencer | The Flask security architecture: system support for diverse security policies[END_REF] is an operating system security architecture that aims at supporting diverse security policies, as shown in Figure 1. OM is used to enforce security policy decisions returned by SS. Access Vector Cache module (AVC), is used to store the access decisions provided by SS for future use so that it can reduce the performance overhead. When the system executes an operation, opening a file for example, OM will enforce security policy decision for this operation. OM queries AVC for the access decision. If AVC has stored such rules, it passes the result directly to OM. If no valid entries exist, AVC will send the query to SS. SS will look up the policy database, find the access decision and return it to AVC. AVC saves this decision, and then returns the result to OM.

EPT Overview

Without virtualization, memory management unit (MMU) is used to translate virtual addresses (VA) to physical addresses (PA) using page tables. But in a virtualized environment, the hypervisor takes full control of the host memory which is shared among virtual machines. So the guest VM can't see PA and guest page tables can't be used directly. In order to abstract the physical memory, the hypervisor presents guest physical addresses (GPA) to VM and maintains the mapping from GPA to host physical addresses (HPA). This gives the VM an illusion that it owns the actual physical memory.

EPT mechanism [21] is an Intel hardware virtualization technology that can be used to support the virtualization of physical memory. It is used to map GPA to HPA. Figure 2 shows the address translating process using EPT technology. First, the guest page tables pointed by CR3 register are used to translate VA to GPA. Then the EPT pointed by EPT base pointer is used to translate GPA to HPA. EPT has a structure of four level page tables. The top level is page map level 4

Assumption and Threat Model

Our framework is based on the following security assumptions. First, we assume that the operating system runs on a virtualization environment. Second, we assume that the underlying hypervisor is trusted. Recent hypervisor rootkits [START_REF]The Blue Pill Project[END_REF][START_REF] King | SubVirt: implementing malware with virtual machines[END_REF] make the hypervisor insecure. There are already some research such as HyperGuard [START_REF] Wojtczuk | Xen 0wning trilogy[END_REF], HyperCheck [START_REF] Wang | HyperCheck: A hardware-assisted integrity monitor[END_REF], HyperSentry [START_REF] Azab | HyperSentry: enabling stealthy in-context measurement of hypervisor integrity[END_REF] and HyperSafe [START_REF] Wang | HyperSafe, a lightweight approach to provide lifetime hypervisor control-flow integrity[END_REF] which aim at protecting the integrity of the hypervisor. In our prototype, we assume that the attacker cannot control the hypervisor to do malicious things. Especially the attacker cannot manipulate the EPT maintained by the hypervisor. Third, we assume OM hooks can be protected so that they cannot be removed or changed maliciously to bypass the security checks enforced by SS. Protecting these hooks are out of the scope for our work. It can be done using other research work like HookSafe [START_REF] Wang | Countering kernel rootkits with lightweight hook protection[END_REF]. In this way, we can guarantee the security operation cannot be bypassed. Finally, the boot of guest VM is trusted and the guest is clean before we enable our setting.

Our threat model allows an attacker to gain access to the kernel address space and to carry out the following type of attack:

SS code attack:

The attacker can modify SS code or inject malicious code to make SS not functional.

SS data attack:

The attacker may carry out control flow attack targeting SS stack or heap data. For example, stack buffer overflow or heap overflow attack. Also, non-control data attack is possible. It is pointers out that non-control data, like global variable, can be exploited to launch attack [START_REF] Shuo | Non-control-data attacks are realistic threats[END_REF]. For example, a Boolean variable in SS that used to determine whether authentication is passed or not can be flipped to circumvent the authentication. Moreover, the attacker may take control of AVC entries and security policy data which may cause the Flask architecture not work as expected.

Overview of Our Approach

In order to make SS trustworthy to provide a centralized repository for policy and decision making, we isolate SS from kernel, including OM and other parts of the kernel, using hardware assisted in-VM isolation technique, as shown in Figure 3. We introduce a security server address space that is independent from and invisible to the system address space used by the operating system. We place SS together with AVC in it, as AVC is subverted, it makes no sense to isolate and protect SS. For clarity, when we refer to SS in the following section, it includes SS and AVC together. We create security server address space by constructing an independent EPT, called SS EPT, at the hypervisor level. This EPT is a synchronized copy of system EPT and is only used by SS for address translation. At the same time we remove the mapping to SS in the original system EPT. In this way, the code in the system address space cannot view and access SS code and data directly.

The entry and exit gates are used to switch address spaces by loading different EPTs. When the kernel calls SS function, it uses the entry gates to enter security server address space by switching from system EPT to SS EPT. When the call is finished, it uses the exit gates to return to system address space by switching from SS EPT to system EPT. The entry and exit gates also switch the stacks as SS need have its own to prevent attacks against stack data. The entry gates perform the transfer out of system stack into security server stack. The exit gates perform the switch from security server stack to system stack. The entry and exit gates are the only regions mapped into both address spaces so that a transfer between system address space and security server address space can only happen through code contained in these regions. They are write-protected so that their contents cannot be modified by any code in the kernel.

Implementation

In our prototype, we use Xen as the hypervisor and SELinux in the HVM DomU with 2.6.32 Linux kernel as the implementation of the flask architecture. First, we construct an independent address space for SS by creating a separate EPT. Then we create entry and exit gates to achieve the switching between two EPTs. At last, we load a kernel module to take all the settings into effect.

Isolated Address Space Construction

Generally, SELinux which includes OM and SS is compiled into the kernel. SS code and kernel code may be sharing one physical page. SS data is similar. In order to isolate SS from other parts of the kernel, we need modify the Linux kernel linker script file to guarantee SS code and data are page aligned. So they are not mixed with code and data from the kernel. Take x86 architecture for example, when the kernel is compiled, a link script file called "vmlinux.lds" is generated according to the source file "vmlinux.lds.S". It's used to control the kernel linking. Here we modify its source file so that the changes will take effect every time vmlinux.lds is generated. In vmlinux.lds.S, we make SS code and data page align and add four indicators to record the start and end address of SS code and data. After the kernel building is completed, we can lookup System.map table to find the values of indicators to see whether the change is applied successfully. After that, in order to construct an EPT that is only used by SS to execute address translation, we add a hypercall named "ept_create". It is invoked only once. After guest VM is booted up, we load a kernel module to notify the hypervisor to invoke this function. It completes the following two tasks.

First, this hypercall creates a new EPT. For clarity, we would refer the EPT used for guest VM as system EPT, and refer the EPT we create for SS as SS EPT. This hypercall uses the system EPT as a template. Since EPT has a structure of four level page tables, we need allocate the physical pages for them and set their entries. First of all, the hypercall allocates a physical page as the new top level page table for SS EPT. Then it checks the top level page table entries of system EPT. For each valid entry that points to a second level page table of system EPT, the top level page table of SS EPT will be set the corresponding entry to point to a new page allocated as a second level page table of SS EPT. As for the access permission of the entry, the hypercall will copy it from the top level page table entry of system EPT. We do the similar operations for the second and the third page table of SS EPT. The last level page table is dealt with differently. As for the page table entries, we assign them exactly the same value as those in system EPT. When all is done, we get an independent EPT which has its own top level, second level, third level and last level page tables. But it maps the same physical memory as system EPT.

Second, the hypercall changes access permissions in system EPT. In order to isolate SS from the guest OS, SS code and data can only be seen and used in the security server address space. So the hypercall removes the mapping for them from system EPT. The hypercall "ept_create" takes four parameters when it's called. Two of them represent start and end of guest frame number of SS code section. The other two are for SS data section. For each guest frame number of code section, we find the entry of page table in system EPT and make it invalid. For SS data section, we do the same setting.

Entry Gate and Exit Gate Implementation

We use entry and exit gates to switch the address spaces. First, in order to implement the switching between system EPT and SS EPT, we need to define another hypercall named "ept_switch". The main task of entry and exit gates is issuing this hypercall to switch EPTs. This hypercall is designed to take an integer as parameter to indicate switching direction. If we want to enter SS to execute code, the physical address of the top level page table of SS EPT will be written to a control field in virtual machine control structure. If we want to exit SS and return to the kernel, the physical address of the top level page table of system EPT will be written to that field. Both the above physical addresses are stored in a structure of the hypervisor, so they cannot be obtained and operated by attackers.

In order to prevent the execution from diverting to somewhere else due to interrupt, we disable interrupts at the beginning of entry gates and enable interrupts at the end of exit gates. Moreover, we also need switch the stacks in the entry and exit gates. In other words, the security server address space has its own stack. The entry gates perform the transfer out of the stack in the system address space into the stack in the security server address space. The exit gates do the opposite thing. In this way, SS stack is not viewed and accessed by the kernel code, and therefore our framework can defend attacks against stack data.

There is still one detail we need to deal with. After SELinux completes the initialization, the entry and exit gates should begin to work. But we don't have the SS EPT created at the moment, so the entry and exit gates actually do nothing before the "ept_create" hypercall is issued. We define a global integer variable H in the kernel to illustrate this condition. Before SS EPT is constructed, we assign zero to H. The entry and exit gates will read this value and do nothing. After creating SS EPT, we assign one to H. The code in both gates will perceive the change and begin to work.

Loading a Module to Enforce the Settings

The last step is to load a kernel module to take the entire configuration into effect. The module does the following two things.

First it will issue the "ept_create" hypercall to notify the hypervisor to create SS EPT. The four parameters of this function can be obtained through simple calculation. In section 5.1, we define four indicators, which are saved in the System.map file. They record the start and end address of SS code and data. The addresses are all virtual addresses. But the kernel lies in the direct mapping area, so we can get physical address by subtracting a fixed offset from virtual address. Then we can get guest frame numbers that the hypercall needs by shifting right the physical address a page size. When this hypercall is called successfully, SS EPT is created. Second, the module will set the global variable H, which is described in 5.2, to be one. The entry and exit gates check this variable and start to work.

Since the global variable H is in the system address space, attackers may change its value to be zero at run time. However, if it is set to be zero, the entry gates and exit gates will do nothing, and the guest VM can only use system EPT. In this way OM cannot find SS when it calls SS functions, as the system EPT has no mapping to them. So it returns a segmentation fault and terminates current process.

Evaluation

We have implemented our prototype on a DELL desktop with Intel Core i5-650 processor, which supports Intel VT technology. We used Xen 4.0.1 as the hypervisor.

The host OS is 32-bit Ubuntu 10.04. So is the guest VM. It's booted up as HVM Do-mU with one VCPU and 512M RAM. We evaluate our work from the aspects of performance and security.

Performance Overhead

As many security hooks exist in the kernel and they are frequently called, we should pay attention to the performance overhead. In our experiments, we used UnixBench [11] to evaluate the system performance. UnixBench provides a basic reference of the performance of a Unix-like system. We tested the performance of the guest VM in two scenarios: one was with SELinux enabled natively and the other one was our prototype that used hardware assisted in-VM isolation. First we ran UnixBench in DomU with SELinux enabled natively. It means SS and OM are not isolated from each other and both of them are in the kernel address space. We used the results as the base of our test. Then we ran UnixBench again using our prototype. SS is isolated from OM and it is in its own address space. As is shown in Figure 4, we divided the latter results by the formal ones and expressed the final results as percentages. Each result is the average of 5 trials. Most of them demonstrate that the overhead of our prototype is small except for the shell script test. This test made a process start eight concurrent copies of a shell script which did operations to a data file. SELinux would check process creation, shell script running and file access for each copy, so the performance went down due to frequent switching of EPTs. Besides, as we put AVC in the security server address space to improve security, every time OM queries AVC for the access rules, it would switch to the security server space. This is a large part of performance overhead. We can improve the performance by moving AVC out of the security server address space but we need extra effort to protect it from being attacked.

Security Analysis

One important design consideration is to stop attacks against SS code and data. It is easy to protect SS code. For example, we can use write-protected technology or attestation technology to protect SS code. However, it is nontrivial to protect SS data. It includes dynamic data that may cause control flow attack. For instance, the heap overflow can be used to modify function pointers and stack buffer overflow can be used to change return addresses. Our approach can prevent such attack, as SS has its own address space, including its own heap and stack. Attackers may also launch noncontrol-data attack [START_REF] Shuo | Non-control-data attacks are realistic threats[END_REF] to bypass the authentication. Since we isolate SS strongly from other parts of the kernel, the attacker who even obtains the kernel privilege cannot see SS non-control data. So our approach can prevent such attack too. As we put AVC and security policy data in the security server address space, it is also very difficult for the attacker to change them maliciously.

Since SS can load policy files into memory at runtime, attackers may breach the security of SS by loading an invalid policy. To prevent this we can maintain a white list which stores valid hash values of policy files. When SS loads a policy file, we can check whether the hash value of this file is in the list. If it is, the file is allowed to be loaded into the memory. Otherwise, SS refuses to load the policy.

Related Work

Our work is related to projects that use secure monitors to protect the integrity of OS kernels. Livewire [START_REF] Garfinkel | A virtual machine introspection based architecture for intrusion detection[END_REF] is a VMM-based prototype that aims at protecting the guest VM kernel code and critical data structures from being modified. VMwatcher [START_REF] Jiang | Stealthy malware detection through vmm-based "out-ofthe-box" semantic view reconstruction[END_REF] is a VMM-based malware detection approach, which moves the anti-malware facilities out of the monitored VM in order to achieve stronger tamper-resistance. Lares [START_REF] Payne | Lares: An architecture for secure active monitoring using virtualization[END_REF] is an architecture that places hooks inside the guest VM that can invoke a security application residing in a separated VM. Patagonix [START_REF] Litty | Hypervisor support for identifying covertly executing binaries[END_REF] is a hypervisor-based prototype that detects and identifies covertly executing binaries without making assumptions about the OS kernel. All these approaches are out-of-VM monitors which are inappropriate for Flask as it is a fine-grained secure architecture that the hooks are called frequently during system execution. They would incur heavy overhead due to frequent switching between the guest VMs and the hypervisor.

SIM [START_REF] Sharif | Secure in-VM monitoring using hardware virtualization[END_REF] is an in-VM monitor which places the security tools in the same VM and uses the hardware virtualization technology to avoid the hypervisor involvement when switching address spaces. It is more efficient than the out-of-VM approaches, and also guarantees the security. However, the shadow paging mechanism it uses is quite complex and not easy to maintain. So we design a hardware assisted in-VM isolated framework that takes advantage of Intel EPT technology to improve the Flask implementation.

Conclusions and Future Work

In this work, we improve the Flask implementation using hardware assisted in-VM isolation. We introduce a separated EPT in the hypervisor to construct an address space for SS so that we can isolate SS from other parts of the kernel. Since all the improving is done at the hypervisor level, the attacker cannot subvert them at the guest VM level. Our approach only works with a Type I VMM, which is implemented directly on the physical hardware, since we need the lower level VMM to protect guest VMs running on it. Our work is a first step towards creating in-VM isolation using hardware assisted page tables to improve Flask implementation. It can be applied to other security tools, such as integrity measurement agent, instruction detection tools and so on. Our future work is to protect OM, especially the hooks used by OM to call AVC and SS functions. If they are bypassed, SS will have no effect at all. Only using writeprotect method to protect them is not enough and we will utilize the research results of HookSafe [START_REF] Wang | Countering kernel rootkits with lightweight hook protection[END_REF] to protect the hooks from being hijacked.

Fig. 4 .

 4 Fig. 4. Performance Overhead

  table, the second level is page directory pointer table, the third is page directory table and the last is page table.

	CR3		EPT Base Pointer
			Guest
	Virtual		Physical
	Address	Guest Page Tables	Address	Extended Page Tables	Host Physical Address
		Fig. 2. Address translation using EPT

Acknowledgments

. Our work is supported by the National Natural Science Foundation of China under Grant No. 90818012, National Science and Technology Major Project No.2010ZX01036-001-002, 2010ZX01037-001-002, and the Knowledge Innovation Key Directional Program of Chinese Academy of Sciences under Grant No.KGCX2-YW-174, No.KGCX2-YW-125.