Suliman A Alsuhibany
email: suliman.alsuhibany@ncl.ac.uk

Ahmad Alonaizi
email: a.alonaizi@ncl.ac.uk

Charles Morisset
email: charles.morisset@ncl.ac.uk

Chris Smith

Aad Van Moorsel
email: aad.vanmoorsel@ncl.ac.uk

Experimental Investigation in the Impact on Security of the Release Order of Defensive Algorithms

Keywords: Release Order of Defensive Algorithms, learning, Experimentation, Security and Protection

In the practical use of security mechanisms such as CAPTCHAs and spam filters, attackers and defenders exchange 'victories,' each celebrating (temporary) success in breaking and defending. While most of security mechanisms rely on a single algorithm as a defense mechanism, we propose an approach based on a set of algorithms as a defense mechanism. When studying sets of algorithms various issues arise about how to construct the algorithms and in which order or in which combination to release them. In this paper, we consider the question of whether the order in which a set of defensive algorithms is released has a significant impact on the time taken by attackers to break the combined set of algorithms. The rationale behind our approach is that attackers learn from their attempts, and that the release schedule of defensive mechanisms can be adjusted so as to impair that learning process. This paper introduces this problem. We show that our hypothesis holds for an experiment using several simplified but representative spam filter algorithms-that is, the order in which spam filters are released has a statistically significant impact on the time attackers take to break all algorithms.

Introduction

Many security solutions are based on algorithms that aim to protect system resources from misuse. These algorithms encode a set of rules that aim to characterize and recognize attempts of misuse, and prevent any adverse effect on system resources. Examples of such algorithms include spam-filters, CAPTCHAs and Anti-Phishing solutions. As attackers interact with the system, they receive feedback that augments their knowledge of the rules used by the system to characterize misuse. Accordingly, they are able to adapt their future interactions in accordance with this augmented knowledge, increasing their ability to break the defensive algorithms, until eventually reaching the point where the security mechanism is broken: the spam-filter rules are overridden, the CAPTCHAs are automatically deciphered, etc. Once a mechanism is broken, the security officer must deploy another one, which will eventually be in turn broken, leading the officer to deploy a new mechanism, and so on and so forth [START_REF] Alsuhibany | Optimising CAPTCHA Generation[END_REF]. Deploying a defensive mechanism has a cost, for example, the cost of deploying a SPAM filter within a particular organization has been calculated at about fifteen thousand euro for the first year [START_REF] Caliendo | The Cost Impact of Spam Filters: Measuring the Effect of Information System Technologies in Organizations[END_REF]. Furthermore, the security officer must usually work within a given budget constraint, and has therefore a limited number of defense mechanisms to deploy. This raises the question whether we can better plan the release of defensive algorithms, so as to extend the period for which the combined set of algorithms is effective? For instance, could it be useful to break up one defensive algorithm into multiple algorithms, and release them one by one? Or could it be useful to reorder the release of the various algorithms to maximize the overall time taken by the attacker to break all algorithms?

In this paper, we are interested to address the following research question: "Does the order in which different defensive mechanisms are released impact the time an attacker needs to break each one of them?" The main reasoning behind considering this question may be answered affirmatively is that the time it takes an attacker to break a defensive algorithms may depend on what the attacker has learned from earlier successful attacks on similar algorithms. If that is true, one may be able to defend better against attacks by impairing the process of learning of attackers. There may be many ways in which one can try to achieve this, but in this paper we consider the most direct implication of this reasoning, namely that the order in which defensive algorithms are released may impact the learning process.

We experimentally test the hypothesis that the release order matters. We conduct an experiment with simplified but representative spam filter algorithms, asking two groups of twenty subjects to break these algorithms. The algorithms are presented in a reversed order to the respective groups. By analyzing these groups, the order of release can have a statistically significance influence in the time required by an attacker to break a mechanism. In other words, there is potential to improve the security of a system by optimizing the order in which the defensive algorithms are released.

The work presented here contributes to the effort captured recently in the term 'science of security', to emphasize scientific and empirical studies for security mechanisms rather than designing a set of best practices. In this regard, an important contribution of this work is the method and protocol used to answer the research question.

In addition, the effect of presentation orders on the learning mechanism is not new. Previous researches in the field of education and psychology provide several insights into the effect of presentation orders [START_REF] Elio | The Effects of Information Order and Learning Mode on Schema Abstraction[END_REF][START_REF] Sandhofer | Order of Presentation Effects in Learning Color Categories[END_REF][START_REF] Medin | Presentation Order and Recognition of Categorically Related Examples[END_REF][START_REF] Mathy | A Rule-Based Presentation Order Facilitates Category Learning[END_REF]. However, to the best of our knowledge, we are the first to address this particular issue of the release order strategy. There exists a considerable amount of related work considering the attack and defense interaction as a game-theoretic problem, but these formulations do not fit exactly with our approach. We refer to Section 6 for a further discussion.

The rest of this paper is organized as follows. Section 2 describes the problem as precise as possible through a detailed system model. Section 3 describes the experimental study, and its results are presented in Section 4. The discussion is presented in Section 5. Section 6 discusses related work. Finally, we conclude with overall discussions and future work in Section 7.

Problem Definition

In order to precisely define the problem under consideration, we start by providing an abstract system model of the attack scenario, involving the attacker and the system as shown in Figure 1. It describes a general class of security solutions which include CAPTCHAs, certain spam filters, intrusion tolerance algorithms, etc. This class of mechanisms is characterized by an intelligent defensive algorithm being attacked and eventually broken, and then being replaced by a new intelligent defensive mechanism, etc. Furthermore, this model provides the basis of the experimental study that we present in Section 3. System Resources. In the system model, we assume a finite set of resources that can be used, e.g. communication or computation resources. The pool of security algorithms is contained by a security layer deployed to protect the system resources from misuse, e.g. excessively high consumption or consumption for unacceptable purposes. These algorithms classify requests to the system as acceptable or unacceptable based upon a set of rules. If a request is classified as acceptable then the request proceeds and the system resources are consumed. A request that is classified as unacceptable cannot proceed through the security layer, and feedback is provided to the user regarding the failed request.

Attacker. An attacker is an agent (human or computational) that attempts to misuse system resources. The attacker makes requests for the system resources, which pass through the security layer as described above. The attacker has some prior knowledge about the rules used to classify request, and attempts to design requests to be classified as acceptable. On each failed attempt, the attacker receives some feedback from the system. This feedback may be a simple Boolean response, or may include reasons for the failure. The attacker can add this feedback to his knowledge, and use this knowledge to inform his subsequent requests. By repeatedly performing this knowledge acquisition process 1 , the attacker can derive the rules that are used by algorithms to classify requests. This includes both the parameters used, and the values of these parameters. The attacker can then misuse system resources by sending requests that are structured in such a way that they fulfill the rules of the algorithm in the security layer. In that case, we consider the algorithm 'broken'.

Security Layer. To maintain the security of the system, the security layer must be updated. Within this update, the algorithm used by the security layer is replaced by another algorithm from the pool to encapsulate a different set of rules such that requests that are misusing system resources are no longer permitted to pass through the security layer. The attacker must repeat the process of knowledge acquisition in order to determine the new classification rules, such that he can continue sending requests to misuse system resources. This process of learning takes time and the overall aim of the algorithms is to maximize the time until all are broken.

Algorithms. The selection of algorithm when updating the security layer determines the subsequent security of the system. In particular, a set of algorithms D, D = {d 1 , d 2 , ..., d n }, n > 1, d n ∈ D, represents the security layer of the system. Each of these algorithms has a specific robustness level dr i ∈ DR. This robustness includes a number of rules dr i = {r 1 , r 2 , …, r n }, n ≥ 1 to protect the system. Based on the rules of an algorithm, a set of algorithm is classified into three types: overlapping rules, not overlapping rules or mixed. In the first type, some of the algorithms are subset from each other dr i ⊂ dr i+1 . The importance of this type can be in breaking up a secure algorithm into a set of algorithm, and more details about this would be given latter. In the not overlapping rules type, all the algorithms are independent dr i ≠ dr i+1 . The importance of this type can be in using variance algorithms. The third type is that using mixed overlapping rules and not overlapping rules algorithms dr i ⊂ dr i+1 and dr i+1 ≠ dr i+2 . The importance of this type can be, in addition to the importance of the first and second type, releasing an independent algorithm between dependent algorithms may impair the attacker's learning process.

The order in which algorithms are released may thus be important. The longer it takes for the attacker to acquire the necessary knowledge regarding classification, the longer the system is protected from misuse. For instance, in the pool of algorithms that can be selected, there may exist algorithms that have some overlapping or similar rules. The question for the defender then is in what order to release these algorithms so that the time until all algorithms are broken is maximized.

Experimental Study

In order to test the hypothesis that the time spent on breaking a set of defensive algorithms depends on the order in which these algorithms are released, we conducted a controlled laboratory experiment in which subjects were asked to break a set of three specifically created spam-filter algorithms. The main hypothesis under test is:

H 1 -The time it takes to break a series of algorithms is dependent on the order in which the algorithms are released

We like to point out that the objective of our experiment is not to say anything definitive about spam filter algorithms. We designed bespoke spam filters that would fit the purposes of our experiment, although we have ventured to create an intuitively appealing experiment that has various elements in common with traditional spam filters. Further, an automated program can be used to break the algorithms. However, a form of understanding of a human learning process can be seen clearly by sending e-mails to evade a spam filter, as automated approaches are abstractions of this human learning process that require encoding by human.

Experiment Setup

The experiment involves subjects to act as potential attackers carrying out attacks on a test system, within which a number of different security algorithms have been deployed.

Experiment Design. In order to evaluate the time needed to break the algorithms, we decided to use a between-subjects design. That is, we have two sets of subjects breaking a series of defensive algorithms where the order is different between the groups. This type of design ensures that the exact same algorithms are used in each experiment condition, and that there is no unnecessary confounding factor biasing the results (at the cost of recruiting relatively many participants). The main independent variable for this experiment is the algorithm order. The time consumed to break each algorithm and the numbers of trials are the dependent variables.

The participants are randomly assigned to one of the following two experimental groups:

 Group 1: The order of algorithms for this group was: A1, A2 then A3.  Group 2: The order of algorithms for this group was: A2, A1 then A3. Specifics about the algorithms will be given in the remainder of this section.

Attackers.

A nontrivial problem was to find potential attackers. The aim was attackers that could be considered to be non-specialists. Whilst specialist attackers or security experts could have been recruited, they would give us information mostly about where and how our particular algorithms needed to be improved and less about learning. Forty students were recruited for this experiment (34 male and 6 female, something we did not consider relevant for our experiment). The typical age range of subjects was 24-33 with 4 participants in the group 40+. The subjects of this experiment were 40 master and PhD students from the School of computing science and other schools in Newcastle University. 37 subjects have technical backgrounds (majoring in computer science and engineering), and the remaining 3 subjects nontechnical (in linguistics). It is important to note that because our aim was to recruit non-specialists attackers to observe the learning acquisition, the inconsistency-bias produced by attackers' background is reduced. In addition, as stated in [START_REF] Elio | The Effects of Information Order and Learning Mode on Schema Abstraction[END_REF][START_REF] Kahn | Guide to Curriculum Design: Enquiry-Based Learning[END_REF] the learning process is achieved regardless the backgrounds.

System. A challenge in designing the experiment is to design a system that can be breached by ordinary people in a matter of minutes. We found that spam filters could offer a very good model for our experimental requirements. Although as mentioned we do not claim or attempt to study and derive results for spam filters themselves, we do believe the simple spam filters we consider have enough similarities with reality to act as an example of the class of systems that we introduced in Section 2.

We developed a web-based system on which to perform the experiment. A Web application was developed, which enables each participant to perform a registration process (e.g. choosing a username, password and educational background), sign a consent form, and read a brief introductory page with necessary information (e.g. description of the experiment, experiment factors, the participant goal, applied method on how to defeat a content-based spam-filter). The participant can then begin the experimental process, interacting with the spam-filter algorithms. The main idea is that the participants try to send e-mails that pass through the spam filters-we describe this in more detail in Section 3.2. The system records all attempts and the time taken by each participant to break each algorithm in each session.

Algorithms. The rationale behind the defensive spam-filter algorithms we constructed is as follows. A simple algorithm A1 acts as base algorithm and a more complicated algorithm A2 extends the rules used by A1. In other words, the rules in A1 are a subset of A2, which we believe is the first case to consider when one wants to test the hypothesis. The third algorithm A3 does not share any rule neither with A1 nor with A2, and acts as a simple independent algorithm. Hence, we challenge our hypothesis H 1 by the two following questions: Q 1 -Do G1 and G2 break A1 and A2 within a similar amount of time? Q 2 -Do G1 and G2 break A3 within a similar amount of time? 2We will answer in Section 4 negatively to Q 1 and positively to Q 2 . We now describe the specific algorithms A1, A2 and A3, as well as pseudo code describing their operation. Modern density-based spam filter [START_REF] Yoshida | Density Based Spam Detector[END_REF] forms the base to implement the algorithms. Note that some of the symbol names being used in the pseudo code are given in Table 1. Algorithm 1 (A1). This algorithm is a simple implementation of the proposal of [START_REF] Yoshida | Density Based Spam Detector[END_REF] where only the first part of the message is checked for similar hashes. Further, the similarity threshold is 75. The pseudo code of this is shown in Figure 2.

Algorithm 2 (A2). This algorithm is similar to A1 except that before any calculation of the hash values, the message would go through word transformation that would delete all redundant letters, white spaces, unify letters case, and transform common number shortcuts to their equivalent letters (e.g. 4 would become for). Those transformations would create a harder algorithm since it would detect any attempt of the attacker to trick the spam filter by using those word transformations. Furthermore, the similarity threshold is 45. In other words, this algorithm has more rules to increase the robustness level. The pseudo code of this is shown in Figure 3. Algorithm A1 and A2 are the main two algorithms to test our hypothesis. We created a third algorithm A3 that both groups G1 and G2 are tasked to break after breaking A1 and A2. Any difference between the groups in the time to break A3 would be very interesting, because it would suggest that the order in which A1 and A2 were broken in the past determines the success of breaking a future algorithm. Algorithm 3 (A3). This algorithm is a simple implementation of the proposal of [START_REF] Yoshida | Density Based Spam Detector[END_REF]; however the last part of the message is checked for similar hashes, and the similarity threshold is 75. The pseudo code of this is shown in Figure 4.

It is worthwhile to note that the reason behind using a different threshold is that we empirically found that the similarity threshold can play an important role in terms of determining the difficulty of an algorithm. That is, in A1 and A3, the attacker needs to modify only 25% from the part that the algorithm is checking, while it is 55% in A2.

Briefly, the symbols in Table 1 are explained in the following. As in [START_REF] Yoshida | Density Based Spam Detector[END_REF], a hashbased vector representation was used. That is, for each e-mail, hash values of each length 9 substring are calculated 3 , and then the first N of them are used as vector representation of the e-mail. To check a single e-mail, in order to find similar previous email which share S% of the same hash values, the algorithm checks the database. As a result, an e-mail transferred more than D times is marked as spam. Materials: stimulus and rational. The stimulus material provided to participants consisted of some default e-mail text. The subjects were asked to send this text to the server, as if it was a typical e-mail. The e-mail text was chosen to be 512 characters in length. Although real-life spammers may send messages that are shorter than this, the length of messages provides the subjects with sufficient text to utilize a range of different strategies to breach the spam-filter.

The same e-mail text was assigned to all subjects, rather than allowing each subject to write his own e-mail. There were several reasons for this. First, self-written e-mails may be of different lengths, making the measurement and comparison of participant's learning a difficult task. Second, self-written e-mails might be chosen because they are easy to type (or, in perverse cases, particularly hard to type). This would again introduce biases that are difficult to control. Third, the use of the same e-mail template across all subjects means that each subject can be treated as an impostor for all the other subjects, putting testing on a firm foundation. Finally, using the same e-mail for everyone affected experimental control over unanticipated biases.

Experimental Procedure

In this section, the way we ran the experiment is explained, i.e., instructions to subjects, procedures and the data collected.

Instructions to subjects. Subjects were instructed to act as attackers whose target is to defeat the spam-filter algorithms by successfully passing the spam filter algorithms for 3 e-mails (where each e-mail is interpreted as a batch of 100). The subjects were instructed that to defeat an algorithm, they should introduce enough changes to the provided message template to trick the spam filter into thinking that the message being sent is genuine. The maximum number of changes they were allowed to introduce at each trial was 80. This makes it impossible for participants to write a completely different message. Moreover, the copy and paste functions were not activated to avoid sending completely different e-mail.

Subjects were instructed that there are a number of candidate attacks that spammers can enact to fool spam filter algorithms. For example [START_REF] Garcia | Spam Filter Analysis[END_REF]: Random addition, Thesaurus substitution, Perceptive substitution and Aimed addition. In this way we aimed at creating a level playing field for all participants.

Subjects were told that if they needed a break; they were to do so after they had defeated all the algorithms. Subjects were able to gauge their progress by looking at a counter at the right of the screen which showed how many e-mails had been sent successfully so far and how many yet remained. Subjects were admonished to focus on the task and to avoid distractions, such as talking with the experimenter, while the task was in progress.

Procedures. The experiment was conducted in a controlled laboratory environment to avoid any distractions, and collect the desired data without any biases. As we mentioned, each group had an equal number of participants (i.e. 20 participants). Each participant was offered £5 for the participation. To motivate participants to do their best, like real attackers, an additional incentive to increase their motivation was offered. The participant who got the highest score in each group was awarded £40 while the second ranked subject was awarded £20. The highest score is based on the time and number of trials consumed to complete the task.

After every e-mail message send by the participant, the system gives information about the progress made: whether the spam attempt passes or fails, and once the algorithms is considered defeated, a notice that the deployed algorithm of the system has been changed. At the end of the experiment, each participant was informed about the achieved score, the time taken and the number of trials. Finally, the participant was asked to fill a short survey/questionnaire about his or her experience.

Collected Data. The time taken by each participant to defeat the algorithms in each session was recorded by the system. Further, the number of trials and the e-mails sent for each session were recorded as well (for later analysis). Additionally, the questionnaires were collected.

4

Results and Analysis: Does Order Matter?

In the experimental study, all the participants successfully completed their task. We first discuss in Section 4.1 the hypothesis with respect to the ordering of the algorithms A1 and A2. We then discuss in Section 4.2 the hypothesis regarding the insen-sitivity of the order of A1 and A2 with respect to the time used to defeat A3. Further, the impact of order on defeating all algorithms is presented in Section 4.3.

Testing Hypothesis if Order Matters

The average time needed to break each algorithm in the two groups is shown in Figure 5. From the totals (the rightmost bar), we see that Group 1 took longer than Group 2. This indicates there are implications to the ordering of the algorithm, but we will discuss this more precisely below. As expected, the 'tougher' algorithm A2 took more time to break than A1. In Group 2 it took on average 16.2 minutes and in Group 1, 14.1 minutes. The time needed to break A1 is far less in Group 2, possibly because learning of the techniques to break A2 first, which is effectively a superset of A1, is enough to break A1. The statistical significance of this will be discussed now. Table 2 compares the algorithms A1 and A2 in the two groups, with respect to time needed (middle column) as well as trials made (rightmost column). For both, we provide average (Avg.), standard decision (SD) and maximum (Max) and minimum (Min). With respect to average time, we find the following. Time needed for breaking A1 and A2 in Group 1 is 25.0 minutes, while it is 20.1 minutes in Group 2. A t-test yields a result of t=1.89, p<0.1, indicating that the difference between Group 1 and Group 2 is indeed statistically significant.

We can therefore answer negatively to Q 1 by observing that G2 break A1+A2 with significantly less time than G1. This result validates the hypothesis H 1 , since we exhibit a case where the order of release has an impact on the time required to break an algorithm.

With respect to the number of trials, we found a less significant difference. The average number of trials is 33.4 trials for Group 1 and 26.1 trials for Group 2. However, this difference is not statistically significant (t=1.55, p=0.139). The discrepancy between time and trials is interesting; we do not believe that this invalidates our claim Total that order matters but it shows that it is not always apparent (and, of course, as always, possibly not true). We discuss this a bit more at the end of this section. If we then look at A1 and A2 individually, we find that the difference in the total time/trials can be attributed particularly to the time/trials it takes to break A1. Comparing the time and trials to break A1 in the two groups in Table 3, a t-test yields a result of t=6.33, p<0.001, indicating that the time consumed to break A1 in Group 1 is significantly higher than that in Group 2. Also a statistically significant difference is found in the number of trials (t=6.62, p<0.005). Likewise, we compare A2 in the two groups in Table 4. A t-test yields a result of t=-1.32, p=0.196, indicating that the time consumed to break A2 in Group 2 is not significantly higher than that in Group 1. The difference found in number of trials was not found a statistically significant (t=-0.86, p=0.399). In other words, the difference for A2 is less significant than that for A1. This suggests that attackers learn more from A2 than from A1, in terms of how much it speeds them up in attacking the other algorithm.

It is worthwhile to note that previous research assumed, based on psychology studies, that interacting with a limited set of highly similar exemplars leads to more learning than when the instances are distributed and dissimilar [START_REF] Sandhofer | Order of Presentation Effects in Learning Color Categories[END_REF]. Our order matters results appeared to confirm this assumption. The average time of breaking A1 in Group 2 was 3.8 minutes, and the maximum time was 6.5 compared to 10.9 minutes and the maximum time was 24.8 minutes in Group 1. On the contrary, the average time of breaking A2 in Group 2 was 16.2 minutes instead of 14.1 minutes in Group 1.

The Influence of Order on Defeating Future Algorithms

The negative answer to Q 1 validates the hypothesis H 1 ; however we also need to verify that the difference between in G1 and G2 comes indeed from the release order, and not from the fact that G2 contains more naturally talented attackers. To research this question, we added the third algorithm A3 at the end of each experiment. This allows us to check if the order of the previous algorithms has any effect on the time needed to defeat the subsequent algorithm A3. We compare A3 in the two groups in Table 5. A t-test yields a result of t=0.14, p=0.891, indicating that there is no statistically significant difference between the times needed to break A3 in Group 1 and Group 2, respectively. Also, no statistically significant difference was found in the number of trials (t=1.12, p=0.273). Hence, we can positively answer to Q 2 , by observing that G1 and G2 take a similar amount of time to break the independent algorithm A3.

One needs to be careful to generalize this result: we do not claim here that any independent algorithm would require the same amount of time, regardless of the history of the attackers. It may be that if A3 was more closely related to A1 and A2, the results will be different. In addition, one would expect that aspects that influence the working of memory of the attacker may matter, such as the absolute time it takes to break algorithms. After all, it is not unlikely that attackers simply forget more of the knowledge gained from earlier attacks if the attack is longer in the past. So, we look at this experiment as an initial look at this issue.

The Influence of Order on Defeating All Algorithms

To complete our discussion, we revisit the influence of ordering for the time and effort it takes to break all three algorithms. We compare the effects of all algorithms in the two groups in Table 6. A t-test yields a result of t=1.76, p<0.1, indicating that the time needed to break the series of algorithms in Group 1 is significantly higher than in Group 2. The average number of trials is 42.3 trials in Group 1 compared to 32.1 trials in Group 2 and a t-test yields a result of t=1.78, p<0.1, indicating that the number of trials in Group 1 is statistically significantly higher than in Group 2. This is somewhat surprising, since the time to break A3 differs little between groups, and we showed in Section 4.1 that without algorithm A3 the difference in the total numbers of trials of the two groups is not statistically different. This may suggest that with respect to the number of trials needed the validity of our hypothesis is at the edge of statistical significance.

Discussion

Our experimental study provides statistically significant evidence that the release order for a set of algorithms can increase the time needed to break a system's security. In particular, as shown in Table 2, the time required by Group 1 to break the algorithms was significantly higher than Group 2. So, we established the main objective of this paper, namely that 'order matters'.

Since A1 is a simplified version of A2, our experiments also indicate that the success of attacks can be delayed by breaking up an algorithm in parts that are released in sequence. We have to be careful not to generalize that conclusion too quickly, but it is an interesting insight that would imply the intuitive reasoning that by breaking up an algorithm in subsets you 'teach' the attacker how to attack is less valid.

It is important to point out that the value in testing the two conditions (i.e. A1 is deployed before A2 and A2 is deployed before A1) in which the defenses are overlapping was necessary to build our hypothesis on solid grounds before we conduct further experiments. Even though several studies in the psychology and education filed indicated that the learning curves can be considerably increased by interacting with a limited set of highly similar exemplars [e.g. [START_REF] Elio | The Effects of Information Order and Learning Mode on Schema Abstraction[END_REF][START_REF] Sandhofer | Order of Presentation Effects in Learning Color Categories[END_REF], these studies were only focused on the effectiveness of the presentation order on the categorization models. For this reason, in our experiment, even the trivial assumption (i.e. A2 is deployed before A1) is tested to avoid surprises. Hence, the experimental results achieved from these conditions can lead to a further experiment in which the algorithms order is, for instance, subset, independent and superset or other orders, as will be highlighted in the following.

Furthermore, based on the qualitative data, we found that the participants performed the attacking process by strategies using skills gained. Among such wrongful direction is the believing that the algorithm is checking a different part of the e-mail. Interestingly, pervious research assumed, based on empirical results, that the attackers' skills would increase based on the knowledge acquired [START_REF] Mcqueen | Quantitative Cyber Risk Reduction Estimation Methodology for a Small SCADA Control System[END_REF]. Our qualitative data appeared to confirm this assumption.

The concatenation of A3 at the end of both Group 1 and Group 2 yielded an interesting and important result. It showed that despite the knowledge gain at any point of the release chain, injecting a non-subset algorithm would force the attacker back to the learning phase. Accordingly, we investigated in [START_REF] Alsuhibany | Modelling and Analysis of Release Order of Security Algorithms Using Stochastic Petri Nets[END_REF] such orders, for examples, A1, A3 and A2 or A2, A3 and A1 that lead to more interesting results. Further, we also note that we used the insight that breaking A3 takes an equal amount of time for both group as a confirmation that a Markov model is an appropriate formalism for the problem at hand, as we shown in [START_REF] Alsuhibany | Optimizing the Release Order of Defensive Mechanisms[END_REF].

As the results obtained in this paper are very encouraging, optimizing the release order of defensive algorithms is a problem worthwhile to study. The results in this paper are a first step, showing the validity of the problem and providing insights in where to invest future research.

Related Work

Attack Modeling. A quantitative analysis of attacker behavior based on empirical data collected from intrusion experiments was presented in [START_REF] Jonsson | A Quantitative Model of the Security Intrusion Process Based on Attacker Behavior[END_REF]. Beside this, Ortalo et al. described in [START_REF] Ortalo | Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security[END_REF] a technique where the states of the resulting Markov chain denote the enhanced privileges gained by an attacker as a result of series of atomic attacks on a system. Furthermore, generic models have been developed that focus on evaluating security [START_REF] Madan | Modeling and Quantification of Security Attributes of Software Systems[END_REF][START_REF] Almasizadeh | Intrusion Process Modeling for Security Quantification[END_REF]. In relation to the time taken for an attacker to compromise a system and misuse its resources, several studies proposed in [START_REF] Mcqueen | Time-to-Compromise Model for Cyber Risk Reduction Estimation[END_REF][START_REF] Mcqueen | Quantitative Cyber Risk Reduction Estimation Methodology for a Small SCADA Control System[END_REF][START_REF] Leversage | Comparing Electronic Battlefields: Using Mean Time-to-Compromise as a Comparative Security Metric[END_REF] a model for estimating the time to compromise a system component that is visible to an attacker. Additionally, McQueen et al. suggested in [START_REF] Mcqueen | Time-to-Compromise Model for Cyber Risk Reduction Estimation[END_REF][START_REF] Mcqueen | Quantitative Cyber Risk Reduction Estimation Methodology for a Small SCADA Control System[END_REF] that the attacker skill levels should be consideration when determining the mean time to compromise a system. With regard to adversarial machine learning, a recent study by Huang et al. explored in [19] that the limits of an adversary's knowledge about the machine learning algorithm and the input data.

Game theoretic Security Approaches. In traditional network security solutions, one of the first approaches for applying game theory to network security is discussed in [START_REF] Mcinerney | FRIARS: a Feedback Control System for Information Assurance Using a Markov Decision Process[END_REF]. Furthermore, Alpcan and Baser utilized in [START_REF] Alpcan | An Intrusion Detection Game with Limited Observations[END_REF] Min-max Q learning to aid in the gradual improvement of the defender's quality. This work can handle reactive defense actions, while in [START_REF] Shiva | Game Theory for Cyber Security[END_REF] proposes proactive defense measures. In addition, a study by Jiang et al. [START_REF] Jiang | A Stochastic Game Theoretic Approach to Attack Prediction and Optimal Active Defense Strategy Decision[END_REF] focused on active defense using an approach to attack prediction. Furthermore, a game theory approach has been adapted to attack modeling as a means for computing and therefore predicting the expected attacker strategy [START_REF] Sallhammar | Using Stochastic Game Theory to Compute the Expected Behavior of Attackers[END_REF]. Recently, a comprehensive survey has been conducted by Roy et al. [START_REF] Roy | A Survey of Game Theory as Applied To Network Security[END_REF] concluded that most of the current games theoretic are based on static game, games with perfect information or games with complete information. Indeed, although a number of current models involving dynamic games with incomplete and imperfect information exist, none of them considers learning and/or maximizing the duration of the game as the game's objective.

Effects of information order. The idea that the order in which information is received could affect both the learning process and the ultimate knowledge representation is of course commonly studied in the fields such as education or psychology. Most of this literature focused on the similarity-based order. The similarity-based order that maximizes the adjacency of the training examples has investigated by numerous studies [START_REF] Elio | The Effects of Information Order and Learning Mode on Schema Abstraction[END_REF][START_REF] Sandhofer | Order of Presentation Effects in Learning Color Categories[END_REF][START_REF] Medin | Presentation Order and Recognition of Categorically Related Examples[END_REF]]. An empirical non-linguistic experiment by Elio and Anderson evaluated in [START_REF] Elio | The Effects of Information Order and Learning Mode on Schema Abstraction[END_REF] the effects of information order and variance on schema abstraction. This research shown that the low-variance condition group performed better with regards to typicality ratings and accuracy than high-variance condition. Further, this study concluded that the manipulation of presentation orders is a potentially useful tool for studying the mechanisms of learning. Mathy and Feldman recently showed in [START_REF] Mathy | A Rule-Based Presentation Order Facilitates Category Learning[END_REF] that a rule-based presentation order (i.e. a small number of rulelearning assumptions) yields superior learning compared to the similarity-based order. Despite these studies provided some insights into presentation orders for investigating categorization processes concept, our study is clearly investigated the effects of presentation order on different concept type.

Conclusion and Future Work

This paper reports on experimental validation of the hypothesis that the order in which defensive algorithms are released impacts the success of the attacker. Our work is based on the observation that attackers increase knowledge by learning from their attempted attacks, and on the intuition that the learning experience of attackers can be influenced by the order in which defensive algorithms are released.

Through a between-subjects experiment with simplified but representative spam filter algorithms we were able to show that the order in which defensive algorithms are released indeed influences the time attacks take. This is a very encouraging result for this line of research, indicating that the problem merits study. The experiment also provides an indication that breaking up a defensive algorithm can be a beneficial tool in prolonging the overall attack time, but this issue need to be researched in much more detail before this conclusion can be drawn more widely. Furthermore, the experiment shows that the success in breaking future algorithms does not depend on how that total amount of knowledge was gained.

A number of potential issues for future research follow from our research. Some of the challenges are of technical nature, but the largest challenge may lie in gaining a deeper understanding of the way attackers collect knowledge (i.e., in the way they learn). That would allow us to better estimate the time it takes to break a defensive algorithm under various levels of knowledge gained, and would allow us to determine an optimal strategy without conducting the time-consuming experiments carried out in this paper. Similarly, it will be of interest to investigate deeper if breaking up defensive algorithms in 'subsets' indeed increases the speed at which attackers gain knowledge, as we found in the our experiments.

Fig. 1 .

 1 Fig. 1. System Model

Fig. 2 .

 2 Fig. 2. Pseudo code of A1

Fig. 3 .

 3 Fig. 3. Pseudo code of A2

Fig. 4 .

 4 Fig. 4. Pseudo code of A3

Fig. 5 .

 5 Fig. 5. The average time (in minutes) for 'attackers' in each group to break the algorithms

Table 1 .

 1 Symbols used in pseudo code and their values in the experiments

	Symbol	Meaning	Value
	D	Spam threshold	100
	N	Number of hash values for each email	100
	S 1	Similarity threshold "Algorithm 1&3"	75%
	S 2	Similarity threshold "Algorithm 2"	45%

Table 2 .

 2 Order matters of two algorithms A1 and A2

	Group	Avg.	Total time SD Max Min	Avg.	Total trials SD Max Min
	1	25.0 10.6 57.1 13.5	33.4	20.1 99.0 14.0
	2	20.1	4.3	26.0 10.8	26.1	8.3	40.0 11.0

Table 3 .

 3 Breaking A1 for each group

	Group	Avg.	Total time A1 SD Max Min	Avg.	Total trials A1 SD Max Min
	1	10.9	4.7	24.8	5.5	14.8	6.8	31	6
	2	3.8	1.3	6.5	0.86	4.3	1.87	8	2

Table 4 .

 4 Breaking A2 for each group

	Group	Avg.	Total time A2 SD Max Min	Avg.	Total trials A2 SD Max Min
	1	14.1	6.2	32.3	7.8	18.6	14.7	74	8
	2	16.2	3.4	21.3	8.9	21.7	7.2	34	9

Table 5 .

 5 Breaking A3 for each group

	Group	Avg.	Total time A3 SD Max Min Avg.	Total trials A3 SD Max Min
	1	6.70	4.93	17	0.97	8.8	10.3	49	2
	2	6.5	4.4	16.3 0.56 6.05	4.4	20	2

Table 6 .

 6 Breaking all algorithms for each group

	Group	Avg.	Total time SD Max Min	Avg.	Total trials SD Max Min
	1	31.7 10.8 59.4 17.4	42.3	23	112	16
	2	26.6 7.36 36.1 12.2	32.1	11	56	13

In the education context, e.g.[START_REF] Kahn | Guide to Curriculum Design: Enquiry-Based Learning[END_REF] stated that the learning is driven by a process of inquiry.

We have an additional reason to consider this particular question, namely whether we can justify the use of a Markov decision model with a state space that simply keeps track of which algorithms are broken. The question corresponds to demonstrating the memoryless property of the Markov model with that state space. The Markov decision model itself is outside the scope of this paper, we refer to our work in[START_REF] Alsuhibany | Optimizing the Release Order of Defensive Mechanisms[END_REF] for more details.

We use the standard hash function provided in Java library.


Chien-Ning Chen
email: chienning@ntu.edu.sg

Jheng-Hong Tu
email: jhtu@csie.ncu.edu.tw

Sung-Ming Yen

SPA on MIST Exponentiation Algorithm with Multiple Computational Sequences

Keywords: division chain, exponentiation, MIST algorithm, side-channel analysis, simple power analysis

The MIST algorithm is a randomized version of the division chain exponentiation algorithm and is a side-channel countermeasure. When analyzing the MIST algorithm by ordinary simple power analysis (with only one square-multiply sequence obtained), an attacker cannot retrieve the secret exponent due to the ambiguous relationship between the square-multiply sequence and the computation. We point out the MIST algorithm is still vulnerable to simple power analysis observing multiple power consumption traces and propose a practical method with detailed steps to deduce the secret exponent from multiple squaremultiply sequences. Further countermeasures such as exponent blinding are required to prevent the analysis proposed in this paper.

Introduction

Exponentiation evaluation is a fundamental computation in most public-key cryptography. Conventional exponentiation algorithms are vulnerable to simple power analysis (SPA) [START_REF] Paul | Differential power analysis[END_REF], differential power analysis (DPA) [START_REF] Paul | Differential power analysis[END_REF] and other sidechannel attacks, which break a cryptosystem by analyzing side-channel leakages from their implementation. SPA assumes that an attacker can distinguish power consumption patterns generated by different operations. When analyzing exponentiation computation, if a fast squaring algorithm is adopted, the attacker can distinguish the power consumption pattern of a squaring from that of a multiplication and then obtain a computational sequence composed of squarings and multiplications (abbreviated to "SM sequence"). Since a multiplication indicates a nonzero bit in the exponent, an attacker can deduce the secret exponent or partial information about the secret exponent from the SM sequence.

Many research results of countermeasures against side-channel attacks can be found in the literature. The square-and-multiply-always algorithm [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF] is a well-known method against SPA. It performs a dummy multiplication when the corresponding bit of the exponent is zero, i.e., there are always a squaring and a multiplication in each iteration. An attacker cannot retrieve any information about the secret exponent from a regular SM sequence.

The MIST algorithm [START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF] proposed by Walter is an efficient exponentiation algorithm and also a countermeasure against side-channel attacks. Conventional exponentiation algorithms have exponents in binary and scan one or more bits per iteration. In contrast, the MIST algorithm represents exponents in mixedradix. Mixed-radix representation means that the radix varies from position to position. An application of mixed-radix is the representation of dates and times, for example, 18429 seconds can be represented as (0100011111111101) 2 in binary or as (5 24 7 60 9 60 ), 5 hours 7 minutes 9 seconds in the mixed-radix clock system. The radixes in the MIST algorithm are randomly selected from small integers, and the radixes {2, 3, 5} are used in [START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF]. Side-channel attacks which average a number of power consumption traces (e.g., DPA) are infeasible because the computation varies among each exponentiation evaluation.

The MIST algorithm is also immune to ordinary SPA due to the ambiguous relationship between an observed SM sequence and the computation. For example, the pattern SM (a squaring followed by a multiplication) in a sequence corresponds to either 1 2 (digit 1 with radix 2) or 0 3 (digit 0 with radix 3). While analyzing an SM sequence of the MIST algorithm with the exponent smaller than 2 n , the average number of exponents which may possibly generate this sequence is about 2 3n/5 [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF], i.e., there are 2 3n/5 candidates of the exponent. A unique candidate might be deduced from multiple SM sequences, but it is infeasible to find the intersection of sets of 2 3n/5 candidates. Walter claimed analyzing multiple sequences is an open problem, and Okeya [START_REF] Okeya | A Multiple Power Analysis Attack against Side Channel Attack Countermeasure MIST[END_REF] also observed that a small portion of the exponent reveals when analyzing multiple sequences. Besides the analysis by Walter, Oswald pointed out the security margin provided in [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF] is wrong (might be lower) [START_REF] Oswald | A Survey on Passive Side-Channel Attacks and their Countermeasures for the NESSIE Public-Key Cryptosystems[END_REF]. Sim et al. [START_REF] Sim | New Power Analysis on the Ha-Moon Algorithm and the MIST Algorithm[END_REF] also analyzed the MIST algorithm with an additional assumption which is similar to the doubling attack [START_REF] Fouque | The Doubling Attack -Why Upwards Is Better than Downwards[END_REF].

This paper presents a multi-sequence SPA on the MIST algorithm. We assume that an attacker can collect multiple power consumption traces generated by the MIST algorithm with the same exponent and then obtain SM sequences by the same technique used in ordinary SPA. In contrast with finding the intersection of sets of candidates after analyzing all sequences individually, the proposed method simultaneously analyzes multiple sequences and finds candidates satisfying all sequences. The proposed analysis employs the residue class operations and is a practical method to deduce the exponent directly from multiple SM sequences. Our implementation results show that around 25 sequences are sufficient to deduce a 1024-bit exponent in less than two hours by using a modern desktop PC in 2012.

The remaining parts of this paper are organized as follows. We review the MIST algorithm as well as some operations of residue class in Sect. 2. Section 3 describes our analysis, a theoretical attack with one SM sequence, followed by the extended attack exploiting multiple sequences. Section 4 provides the implementation results and also some tricks to reduce the memory requirement. Finally, Sect. 5 concludes this paper.

Preliminary and Background

MIST Exponentiation Algorithm

In 1998, Walter proposed an algorithm -exponentiation using division chain [START_REF] Walter | Exponentiation using Division Chains[END_REF] which is a predecessor of the MIST exponentiation algorithm. In both algorithms, an exponentiation x e is decomposed into

x (e mod d) × x d e d
where d is a small positive integer. The two small exponentiations x (e mod d) and x d are computed by using a computational sequence {x, x 2 , • • • , x d } in which the exponents {1, 2, • • • , d} form an addition sequence containing (e mod d) and d, i.e., x (e mod d) can be obtained during the evaluation of x d without any cost. By repeating the above procedure, we have

x e = A i × x i qi = (A i × x i ri ) × x i di q i d i (1)
= A i+1 × x i+1 qi+1 = • • •
with the base number x i+1 = x i di initialized by x 1 = x; the accumulator A i+1 = A i × x i ri initialized by A 1 = 1; the quotient q i+1 = qi di initialized by q 1 = e; and the remainder r i = q i mod d i . The quotient q i is the remaining exponent in the i-th iteration of the computation, and we have q i = (r MSB ) dMSB • • • (r i ) di in mixed-radix representation. The divisors d i are small integers. The MIST algorithm in [START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF] selects d i from {2, 3, 5} randomly and is a randomized version of its predecessor (exponentiation using division chain).

INPUT:

x and e OUTPUT: 2 provides the detailed computation of the MIST algorithm for various divisor-remainder pairs (abbreviated to "DR pair"). In the column of register sequence, X and A are the two variables used in the algorithm in Fig. 1, and T is the temporary variable. The computation XX→T denotes that the result of the multiplication (squaring) X × X is stored in T. The addition sequence and the square-multiply pattern (abbreviated to "SM pattern") generated by the computation are also provided. Since the MIST algorithm selects the divisors d i randomly, it is naturally immune to power analysis which averages over a number of power consumption traces, e.g., differential power analysis. Simple power analysis is the other category of power analysis which assumes the power consumption trace of multiplications is distinguishable from that of squarings. However, an attacker cannot uniquely determine the secret exponent by analyzing one SM sequence of the MIST algorithm due to the ambiguous relationship between an observed SM pattern and the exact computation. As shown in Fig. 2, each of the patterns SM, SMM, SMMM corresponds to two or three DR pairs, and the pattern SSMM corresponds to either the DR pair [START_REF] Okeya | A Multiple Power Analysis Attack against Side Channel Attack Countermeasure MIST[END_REF][START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF] or a squaring (S) followed by the pattern SMM. In [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF], Walter pointed out that on average 2 3n/5 candidates will remain for an n-bit exponent after analyzing one SM sequence.

x e 01 A = 1, X = x, Q = e 02 while (Q > 0) 03 Randomly choose d from {2, 3, 5} 04 r = Q mod d 05 Compute A = A × X r and X = X d together † 06 Q = Q/d 07 return A † Referring to

Operations of Residue Class

The proposed analysis represents the candidates of the exponent as a collection of residue classes, which is much more efficient than enumerating and storing all candidates. In this paper, a residue class M, N denotes a set consisting of nonnegative integers congruent to the nonnegative integer N modulo the positive integer M (0 ≤ N < M ), i.e., M, N = {kM + N |k ∈ Z, k ≥ 0}. The following operations are used in the proposed analysis.

The first operation is split which splits a residue class M, N into ε subsets by expanding the modulus M to εM . Since kM +N = k ε εM +(k mod ε)M +N , M, N can be split into the collection of distinct subsets

M, N = ε-1 δ=0 εM, δM + N ,
and split ( M, N , ε, δ) = εM, δM + N is defined as the δ-th subset of M, N .

The second operation is integer division, i.e., dividing all numbers in a residue class M, N by a given divisor d and obtaining the integer quotients. Suppose εM = lcm(M, d), the least common multiple of M and d.

Since kM +N d = (k ε+δ)M +N d = k ( εM d ) + δM +N d
where k = k ε and δ = k mod ε, we have

M, N ÷ d = kM + N d k = 1, 2, • • • = ε-1 i=0 εM d , iM + N d .
For example, 10, 7 represents integers {7, 17, 27, • • • }. When dividing by 6, 10, 7 will be split to a collection 30, 7 ∪ 30, 17 ∪ 30, 27 , and then we have 10, 7

÷ 6 = 5, 1 ∪ 5, 2 ∪ 5, 4 which represents integers {1, 2, 4, 6, 7, 9, • • •}.
The last two operations are to find union and intersection3 of two residue classes. Before finding union or intersection, the moduli of the two sets should be expanded to their least common multiple by using the first operation. For example, 2, 1 = 6, 1 ∪ 6, 3 ∪ 6, 5 and 3, 2 = 6, 2 ∪ 6, 5 , and we have 2, 1 ∪ 3, 2 = 6, 1 ∪ 6, 2 ∪ 6, 3 ∪ 6, 5 as well as 2, 1 ∩ 3, 2 = 6, 5 .

Analysis to MIST by Using Residue Class

The MIST algorithm with a given exponent can generate various SM sequences due to its randomness. These SM sequences are the potential SM sequences associated with the given exponent, and one of them will be generated during each computation. On the other hand, an SM sequence generated by the MIST algorithm is associated with more than one exponents due to the ambiguous relationship between the SM pattern and the computation. The MIST algorithm with these exponents may possibly generate this SM sequence. When an SM sequence is observed by SPA, all these exponents associated with this observed SM sequence are candidates of the secret exponent, and we say these candidates satisfy this SM sequence. The proposed analysis will find the candidates simultaneously satisfying multiple SM sequences.

The observed SM sequences should be decomposed into small blocks before the analysis. Each block contains one SM pattern listed in Fig. 2 and corresponds to one iteration of the MIST algorithm. However, the pattern SSMM can be interpreted as either an atomic pattern or two patterns S-SMM. It should be identified as a special block prior to other SM patterns. The proposed analysis deals with one block per iteration from the first to the last block of each SM sequence. Since there will be some special blocks SSMM, the block number in the proposed analysis is different from the iteration number in the MIST algorithm.

In the first step, the proposed analysis will find candidates of the exponent simultaneously satisfying the first block of every observed SM sequence. 4 These candidates can be divided into one or more residue classes, and each residue class is a candidate set. After analyzing the first i blocks of the observed SM sequences and obtaining the candidate sets satisfying the first i blocks, we inspect the subsets of each candidate set and then obtain the candidate sets satisfying the first (i + 1) blocks. After analyzing from the first to the last block of the observed SM sequences, we obtain the candidates of the exponent satisfying whole blocks of the observed SM sequences.

The candidates of the exponent in the proposed analysis are organized into one or more candidate sets (represented by using residue class) instead of enumerating all of them. A candidate set will contain more than one candidates when its modulus M is smaller than the upper limit of the exponent of the cryptosystem. The number of candidate sets does not indicate how much exhaustive search required, for example, we can use only one residue class 1, 0 to represent all exponents smaller than the upper limit.

The details of the analysis is provided in the following subsections. The theoretical analysis with one SM sequence is introduced in Sect. 3.1, and the practical analysis of exploiting multiple SM sequences is presented in Sect. 3.2.

Single-sequence Analysis to MIST

Referring to the equation ( 1), the computation of the MIST algorithm is controlled by the DR pairs (d i , r i ). The potential DR pairs associated with the block of SM patterns S, SM, SMM, SMMM are listed in Fig. 2, and the DR pairs associated with the special block SSMM are (5, 4), (6, 2), [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF][START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF], and (10, 0). 5 The variable for the potential DR pair as well as some other variables is defined below.

Definition 1. Let DR i (γ) = (d i (γ) , r i (γ)
) be the γ-th potential DR pair associated with the i-th block of the SM sequence. α) , N i (α) be the α-th candidate set of the exponent satisfying the first (i -1) blocks of the SM sequence. 4 A candidate of the exponent satisfying the first i blocks of an observed SM sequence means there is at least one potential SM sequence associated with this candidate, of which the first i blocks are identical to the first i blocks of the observed SM sequence. 5 The DR pair [START_REF] Okeya | A Multiple Power Analysis Attack against Side Channel Attack Countermeasure MIST[END_REF][START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF] is associated with the atomic pattern SSMM. In contrast, when a block SSMM is composed of two patterns S-SMM, the remaining exponent will satisfy qi mod 2 = 0 as well as one of the three equations q i 2 mod 3 = 1, q i 2 mod 3 = 2, and q i 2 mod 5 = 0. The DR pairs associated with S-SMM are (6, 2), [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF][START_REF] Walter | MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis[END_REF], and (10, 0).

Definition 2. Let e i (α) = M i (
If the exponent belongs to a candidate set e i (α) , the remaining exponent q i in the i-th iteration will belong to e i (α) ÷ (d

1 (γ1) • • • d i-1 (γi-1)
) for all enumerations of products (d

1 (γ1) • • • d i-1 (γi-1) ). These potential values e i (α) ÷(d 1 (γ1) • • • d i-1 (γi-1)
) can be divided into several residue classes, and each one is a candidate set of the remaining exponent.

Definition 3. Let q i (α-β) = m i (α-β)
, n i (α-β) be the β-th candidate set of the remaining exponent in the i-th iteration, associated with e i (α) .

The superscript, (γ), (α), (α-β), in variables indicates a specified DR pair or candidate set. We also use ( * ) to indicate an arbitrary one among these DR pairs or candidate sets. For example, q i ( * - * ) is an arbitrary candidate set of q i , and q i (α- * ) is an arbitrary one associated with e i (α) . The following is an example of the proposed analysis. Suppose the first few operations of an SM sequence are SSMSMMS. The initial candidate set of the exponent and that of the remaining exponent associated are e 1

(1) = 1, 0 and q 1 (1-1) = 1, 0 .

The DR pair associated with the first block S is (d 1 (1) , r 1 (1) ) = (2, 0), and we have the expansion factor ε 1,1 = 2 when finding q 1

(1-1) ÷ d 1 (1) . Since only split(q 1 (1-1) , 2, 0) d 1 (1) , r 1 (1) = 2, 0 is nonempty, the candidate sets of the exponent and the associated remaining exponent satisfying the first block are e 2 (1) = split(e 1 (1) , 2, 0) = 2, 0 , q 2 (1-1) = split(q 1 (1-1) , 2, 0) ÷ d 1 (1) = 1, 0 .

When analyzing the second block SM, the potential DR pairs are (d 2 (1) , r 2 (1) ) = (2, 1) and (d 2 (2) , r 2 (2) ) = (3, 0). We have ε 2,1 = 6, and e 2 (1) will be split into six subsets. Four of these subsets will satisfy the first two blocks, and they are e 3 (1) = split(e 2 (1) , 6, 0) = 12, 0 , q 3 (1-1) = split(q 2 (1-1) , 6, 0) ÷ 3 = 2, 0 ; e 3 (2) = split(e 2 (1) , 6, 1) = 12, 2 , q 3 (2-1) = split(q 2 (1-1) , 6, 1) ÷ 2 = 3, 0 ; e 3 (3) = split(e 2 (1) , 6, 3) = 12, 6 , q 3 (3-1) = split(q 2 (1-1) , 6, 3)

÷ 2 = 3, 1 q 3 (3-2) = split(q 2 (1-1) , 6, 3) ÷ 3 = 2, 1 ;
e 3 (4) = split(e 2 (1) , 6, 5) = 12, 10 , q 3 (4-1) = split(q 2 (1-1) , 6, 5) ÷ 2 = 3, 2 .

When analyzing the third block SMM, the potential DR pairs are (3, 1), (3, 2), and (5, 0). The sets e 3 (1) , e 3 (2) , e 3 (3) , e 3 (4) will be split into ε 3,1 = 15, ε 3,2 = 5, ε 3,3 = 15, ε 3,4 = 5 subsets, and 11, 1, 15, 5 subsets will satisfy the first three blocks, respectively. We only demonstrate how to inspect the subset split(e 3 (2) , 5, 0) of e 3 (2) and the fourth subset split(e 3 (3) , 15, 3) of e 3 (3) . Since split(q 3 (2-1) , 5, 0) = 15, 0 ⊂ 5, 0 , we have e 4 (12) = split(e 3 (2) , 5, 0) = 60, 2 , q 4 (12-1) = split(q 3 (2-1) , 5, 0) ÷ 5 = 3, 0 .

Since split(q 3 (3-1) , 15, 3) = 45, 10 ⊂ 3, 1 , 45, 10 ⊂ 5, 0 , and split(q 3 (3-2) , 15, 3) = 30, 7 ⊂ 3, 1 , we have e 4

(16) = split(e 3 (3) , 15, 3) = 180, 42 ,    q 4 (16-1) = 45, 10 ÷ 3 = 15, 3 q 4 (16-2) = 45, 10 ÷ 5 = 9, 2 q 4 (16-3) = 30, 7 ÷ 3 = 10, 2

. Fig. 3. Candidate sets satisfying the SM sequence SSMSMMS Figure 3 sketches the relationship between the candidate sets in the above example, which forms a tree. Each child node is a subset of its parent node and will satisfy one more block of the SM sequence than its parent node. The proposed analysis is a breadth-first search, starting from the root e 1 (1) . Suppose we have obtained all e i ( * ) as well as all q i (α- * ) associated with each e i (α) . We can find all e i+1 ( * ) as well as all q i+1 ( * - * ) by the following steps.

Step 1 Select one e i ( * )

Step 2 Suppose e i (α) is selected. Find the smallest positive integer ε i,α satisfying

d i (γ) | ε i,α m i (α-β)
for all γ and β (i.e., for all DR i ( * ) and q i (α- * ) . Split e i (α) and all q i (α- * ) by the factor ε i,α .

Step 3 Select one subset of e i (α) , i.e., select an integer δ ∈ [0, ε i,α -1] and then

compute split(e i (α) , ε i,α , δ) = ε i,α M i (α) , δM i (α) + N i (α) .
Step 4 Inspect whether the selected split(e i (α) , ε i,α , δ) satisfies the first i blocks of the SM sequence (i.e., whether it is a valid e i+1 ( * ) ). * ) , and β,γ split(

If β,γ split(q i (α-β) , ε i,α , δ) d i (γ) , r i (γ) = ∅, then split(e i (α) , ε i,α , δ) is one e i+1 (
q i (α-β) , ε i,α , δ) d i (γ) , r i (γ) ÷ d i (γ) represents all q i+1
( * - * ) associated with split(e i (α) , ε i,α , δ). Otherwise, discard split(e i (α) , ε i,α , δ).

Step 5 Select another subset of e i (α) and go back to step 4 until all subsets are processed.

Step 6 Select another e i ( * ) and go back to step 2 until all e i ( * ) are processed.

Each e i ( * ) is split into several subsets in step 2, and whether each subset is a valid e i+1 ( * ) is inspected in step 4. Since the remaining exponent should satisfy * ) if and only if we can find at least one q i (α-β) (i.e., ∃β) satisfying split(q i (α-β) , ε i,α , δ)

q i mod d i = r i , a subset split(e i (α) , ε i,α , δ) is one e i+1 (
⊂ γ d i (γ) , r i (γ) . When s subset split(q i (α-β) , ε i,α , δ) ⊂ d i (γ) , r i (γ) , split(q i (α-β) , ε i,α , δ) ÷ d i (γ)
is one q i+1 ( * - * ) associated with split(e i (α) , ε i,α , δ). The candidate sets e end+1 ( * ) satisfying the whole SM sequence can be obtained by repeating the above steps. In the last few iterations of the analysis, the modulus M i ( * ) of each e i ( * ) will be greater than the upper limit of the exponent, and each e i ( * ) can be simplified by e i (α) = N i (α) because (δM i (α) + N i (α) ) with δ ≥ 1 is not a valid exponent. The associated q i ( * - * ) can be also simplified by q i (α-β) = n i (α-β) . In the last iteration, the DR pair (d end ( * ) , r end ( * ) ) should further satisfy r end ( * ) = 0 because of q end = d end q end+1 + r end = 0 and q end+1 = 0. After analyzing the whole SM sequence, we have the candidates α N end+1 (α) of the exponent.

The proposed analysis assumes the attacker can distinguish squaring and multiplication in a power consumption trace. However, some operations might not be identified exactly. Ambiguous SM patterns will be isolated and processed by the method similar to that analyzing the special pattern SSMM. For example, when an SM sequence is SSMS?MS, the fourth to sixth operations S?M will be isolated, and they are either SMM or SSM. The potential DR pairs are (3, 1), (3, 2), (5, 0) for the first case and (4, 2), (6, 0) for the second case. Some exponentiation algorithms employ uniform computation for both squarings and multiplications to prevent SPA, e.g., the side-channel atomicity [START_REF] Chevallier-Mames | Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity[END_REF]. However, the divisions q i = qi-1 di-1 in the MIST algorithm still reveal information. If the divisions are evaluated during the computation and the power consumption trace of divisions can be recognized, the SM patterns S, SM, and SMM can be determined by the number of squarings/multiplications between two divisions. In addition, some special chosen messages will cause revelation of computational sequence [START_REF] Courrège | Simple Power Analysis on Exponentiation Revisited[END_REF], e.g., -1 ≡ n -1 (mod n) and faulty elliptic curve points of small orders [START_REF] Yen | Modified Doubling Attack by Exploiting Chosen Ciphertext of Small Order[END_REF]. If the exponent is an odd integer and the input message (base number) is -1, referring to Fig. 2, there are only two types of computation, 1 × 1 = 1 and 1 × (-1) = (-1). The computations XA→A and TA→A can be identified because A is always equal to -1. The analysis based on the observation of divisions or the special chosen message is similar to the proposed analysis.

The proposed analysis is an implementation of the exhaustive search in [6, Section 8]. In the next subsection, we will introduce how to exploit multiple SM sequences simultaneously.

Multi-sequence Analysis to MIST

The straightforward method to exploit multiple SM sequences is to find the candidates satisfying each SM sequence individually and then find the intersection of these candidates. In contrast, the proposed method directly finds the candidates satisfying all observed SM sequences. Since multiple SM sequences are handled simultaneously, the additional subscript j is employed to indicate variables associated with the j-th SM sequence. Some variables are redefined below, and the steps 2 and 4 of the analysis in Sec. 3.1 are also modified. Definition 4. When analyzing the i-th block of the j-th SM sequence, let DR j,i (γ) = (d j,i (γ) , r j,i (γ) ) be the γ-th potential DR pair; q j,i be the remaining exponent; q j,i (α-β) = m j,i (α-β) , n j,i (α-β) be the β-th candidate set of q j,i associated with e i (α) .

Step 2 Suppose e i (α) is selected. Find the smallest positive integer ε i,α satisfying * ) and q * ,i (α- * ) and for all SM sequences (i.e. ∀j, γ, β). Split e i (α) and all q * ,i (α- * ) by the factor ε i,α .

d j,i (γ) |ε i,α m j,i (α-β) for all DR * ,i (
Step 4 Inspect whether the selected split(e i (α) , ε i,α , δ) satisfies the first i blocks of all SM sequences (i.e., whether it is one e i+1 ( * ) ).

If β,γ split(q j,i

(α-β) , ε i,α , δ) d j,i (γ) , r j,i (γ)
= ∅ for all j (i.e., for all SM sequences), then split(e i (α) , ε i,α , δ) is one e i+1 ( * ) , and

β,γ split(q j,i (α-β) , ε i,α , δ) d j,i (γ) , r j,i (γ)
÷ d j,i (γ) represents all q j,i+1

( * - * ) associated with split(e i (α) , ε i,α , δ) for the j-th SM sequence. Otherwise, discard split(e i (α) , ε i,α , δ).

Since each e i ( * ) should satisfy all SM sequences, in the modified step 2, all candidate sets are split with the same factor ε i,α instead of various factors for each SM sequence. In the modified step 4, split(e i (α) , ε i,α , δ) is one e i+1 ( * ) if the candidate set of remaining exponent q j,i+1

(α- * ) exists for every SM sequence. According to [START_REF] Walter | Some Security Aspects of the MIST Randomized Exponentiation Algorithm[END_REF]Theorem 9], the expected number of exponents satisfying a given SM sequence is about 2 3n/5 for an n-bit exponent, i.e., an arbitrary exponent will satisfy a given SM sequence with the probability 2 -0.4n . Three to five SM sequences might be sufficient to obtain a unique candidate of the exponent. In the next section, we will provide some implementation results and discuss the feasibility.

Results and Discussions

The proposed analysis is implemented in C++ and executes on PC with 3.1GHz CPU and 8GB RAM. It uses the list container of Standard Template Library to store candidate sets. Each candidate set of exponent e i (α) is associated with one or more candidate sets of remaining exponent q j,i (α- * ) for every SM sequence j. For a candidate set, the modulus M in the residue class M, N is represented as the form 2 a 3 b 5 c , and the remainder N is represented by 240-base number system. Figure 4 sketches the data structure in our implementation. * ) . The execution time (single thread execution) and peak memory usage are also provided. Figure 6 provides results with various numbers of SM sequences. We collect ten SM sequences associated with a 256-bit exponent and then perform analysis with 6/8/10 SM sequences.

q 1,i (1--1) q 1,i (1--2) … q 2,i (1--1) … … e i (2) q 1,i (2--1) … … … … … …
The number of candidate sets during the analysis is determined by two factors, the ratio E i of expansion in step 2 and the ratio F i of filtering in step 4. The product E i × F i is the ratio between the number of e i ( * ) and e i+1 ( * ) . However, the implementation results show that the number of candidate sets in each iteration is irregular and depends on combination of observed SM sequences. There is no obvious trend of the number, except after nearly the 160th iteration, it decreases continually because expansion is not required when the modulus M i ( * )

in each e i ( * ) is greater than the upper limit of the exponent. Exploiting more SM sequences will remove more subsets in step 4, i.e., F i gets smaller, but also generate more subsets in step 2, i.e., E i gets larger. For example, between the 130th and 140th iteration of Fig. 6, there are more candidate sets in the analysis with 10 SM sequences than with 6 or 8 SM sequences.

The execution time depends on the total number of candidate sets during the analysis, and the peak memory usage depends on the maximum number of candidate sets in an iteration. When the exponent is 1024-bit or longer, the analysis program might spend too much memory and also extreme long time. In order to reduce the number of candidate sets, we can employ supplement SM sequences to inspect candidate sets. Unlike ordinary SM sequences, supplement SM sequences do not allow to split candidate sets of the exponent, i.e., they only reduce the filter factor F i but not increase the expansion factor E i . Suppose the i-th iteration of the analysis with the ordinary SM sequences has finished. For each e i (α) , we initialize q sup,1 (α-1) = e i (α) and find all q sup,2 (α- * ) , . . . , q sup,i

(α- * )
relating to a supplement SM sequence until splitting is required (i.e., ε i +1,α = 1 in step 2) to find q sup,i +1 (α- * ) . A candidate set e i (α) is valid if there is at least one q sup,i (α- * ) , i.e., e i (α) satisfies the first (i -1) blocks of the supplement SM sequence. After inspecting all candidate sets e i ( * ) by a supplement SM sequence, we can filter them again by another supplement SM sequence. Since q sup,i ( * - * ) are not stored after analyzing a supplement SM sequence, exploiting supplement SM sequences only slightly increases the memory requirement.

According to our implementation results, five ordinary SM sequences and twenty supplement SM sequences are enough to deduce a 1024-bit exponent. We start to exploit supplement SM sequences when the number of candidate sets is more than 10, 000 and until it is less than 5, 000. These supplement SM sequences are circularly reused during the analysis. In the ten implementation results, the average execution time is 3,353 seconds (between 1,386 seconds and 5,719 seconds), and the average peak memory usage is 415 MB (between 214 MB and 872 MB). Exploiting more supplement SM sequences definitely reduces the number of candidate sets, but it might increase the execution time.

The proposed analysis is a breadth-first search (referring to Fig. 3). The breadth-first search requires a queue to store all nodes of a level, and the peak memory usage is determined by the maximum number of nodes of a level. The memory usage can be reduced by converting the proposed analysis to a depthfirst search. When traversing to a child node, we only need to store its parent node and the index of the child node, i.e., storing e i (α) and δ when traversing to split(e i (α) , ε i,α , δ). The maximum number of nodes stored is equal to the maximum number of blocks of SM sequences, and the execution time is roughly the same as the original method.

Conclusions

When designing an exponentiation algorithm with immunity to SPA, removing the explicit relationship between the computational sequence and the secret exponent is a widely used method. However, an attacker can still obtain partial information about the secret exponent from a computational sequence. He might be able to integrate information collected from several computations if the algorithm is nondeterministic, i.e., randomized.

This paper proposes the first practical multi-sequence SPA against the MIST algorithm. Further countermeasures such as exponent blinding are required to prevent the attacker from collecting multiple SM sequences corresponding to the same exponent. The proposed method is an example that a randomized algorithm with immunity to single-sequence SPA might be vulnerable to multisequence SPA due to its randomness. Randomized exponentiation algorithms is not an elixir of preventing side-channel attacks.

Fig. 2

 2 for the detailed computational sequence

Fig. 1 .Figure 1

 11 Fig. 1. The MIST exponentiation algorithm

Figure 5

 5 provides three results of finding 256-bit exponent by analyzing five SM sequences. Each time, we randomly generate a 256-bit exponent, and then the MIST algorithm executes five times to collect five SM sequences associated with this exponent. The figure illustrates the number of the candidate sets e i

Fig. 4 .Fig. 5 .

 45 Fig. 4. Data structure for storing candidate sets

The intersection operation is similar to solving the simultaneous congruences in the Chinese remainder theorem. However, in the proposed analysis, the moduli may not be relatively prime.

Some part of this research was done while Chien-Ning Chen was a postdoctoral research fellow at the National Central University. The research of Jheng-Hong Tu and Sung-Ming Yen on this work were supported by the National Science Council of the Republic of China under contract NSC 101-2221-E-008-111-MY2.