Bastian Braun

Caspar Gries
email: cgries@in-doc.de

Benedikt Petschkuhn
email: petschku@fim.uni-passau.de

Joachim Posegga

Ghostrail: Ad Hoc Control-Flow Integrity for Web Applications

Modern web applications frequently implement complex control flows, which require the users to perform actions in a given order. Users interact with a web application by sending HTTP requests with parameters and in response receive web pages with hyperlinks that indicate the expected next actions. If a web application takes for granted that the user sends only those expected requests and parameters, malicious users can exploit this assumption by crafting harming requests. We analyze recent attacks on web applications with respect to user-defined requests and identify their root cause in the missing enforcement of allowed next user requests. Based on this result, we provide our approach, named Ghostrail, a control-flow monitor that is applicable to legacy as well as newly developed web applications. It observes incoming requests and lets only those pass that were provided as next steps in the last web page. Ghostrail protects the web application against race condition exploits, the manipulation of HTTP parameters, unsolicited request sequences, and forceful browsing. We evaluate the approach and show that it neither needs a training phase nor a manual policy definition while it is suitable for a broad range of web technologies.

Introduction

Over the past two decades, the Web has evolved from a simple delivery mechanism for static content to an environment for powerful distributed applications. In spite of these advances, remote interactions between users and web applications are still handled using the stateless HTTP protocol, which has no protocollevel session concept. Handling session state is fully left to the web application developer or to high-level web application frameworks.

Web applications often include complex control flows that span a series of multiple distributed interactions. The application developer usually expects the user to follow the intended control flow, i.e., to first access the website on an entry page and then proceed by clicking on links and buttons and fill provided forms. However, if a web application does not carefully ensure that interactions adhere to the intended control flow, attackers can easily abuse the web application by using unexpected interactions. Our previous work showed that common web application frameworks provide hardly any protection means a developer could rely on [START_REF] Braun | A Survey on Control-Flow Integrity Means in Web Application Frameworks[END_REF], meaning that developers must ensure control-flow integrity manually.

Several known attacks have exploited missing protection in the past. The attacks' impact ranges from sending more free SMS text messages than actually allowed [START_REF] Paleari | On Race Vulnerabilities in Web Applications[END_REF], and unauthorized access to user accounts [START_REF] Grossman | Seven Business Logic Flaws That Put Your Website At Risk[END_REF][START_REF]Thieves Found Citigroup Site an Easy Entry[END_REF][START_REF] Tate | Apple's Worst Security Breach: 114,000 iPad Owners Exposed[END_REF], to shopping for expensive goods with arbitrarily low payments [START_REF] Wang | How to Shop for Free Online -Security Analysis of Cashier-as-a-Service Based Web Stores[END_REF]. This paper presents a novel approach for avoiding problems related to control-flow integrity in web applications. Based on the assumption that all client-side requests are potentially compromised, the approach replicates a user's mouse clicks and form input in a server-side sandbox. Requests triggered by the sandbox are trustworthy because they adhere to the assumed user interaction with the web application. We show that this approach provides ad hoc protection against attacks on the web application's control flow without the need for a learning phase or a manual policy definition. It functions as a reverse proxy and is thus independent of the server-side technology. No adaptations are required on the web application making the approach applicable to new and legacy applications. The induced load can be outsourced to scalable, e.g. cloud-based, platforms if necessary.

This paper is structured as follows. The next section provides an in-depth discussion of technical aspects of control-flow integrity in web applications and explains known attacks and vulnerabilities. Section 3 presents our novel approach for controlling flow integrity at the server-side, and Section 4 gives details about the implementation. We evaluate the approach in Section 5, discuss related work in Section 6, and finally conclude in Section 7.

Control-Flow Integrity

In this section, we investigate in more detail the problem of control-flow integrity of web applications, analyze several real-world attacks, and discuss their root causes.

Technical Background

In a typical web application, the user's web browser interacts with the remote application by sending HTTP requests. HTTP is a stateless protocol without session concept. This means that each request is independent of all others. The protocol does not inherently link one request to the next. Dynamic web applications, however, have workflows that are composed of multiple steps, which corresponds to multiple HTTP requests from the user to the web application. For each step, the client receives a web page with hyperlinks that offer possible next steps to a user. Upon clicking a link, the user's browser sends a particular HTTP request to the web application, which then performs actions in order to progress to the next step in the workflow. The actions are defined by the URI of the HTTP request, the request parameters, and the server-side session record.

The Attacks

Several kinds of attacks on web applications exploit the fact that attackers can craft arbitrary requests instead of clicking on provided hyperlinks. Real-world examples of control-flow integrity violations are race conditions, manipulated HTTP parameters, unsolicited request sequences, and forceful browsing.

Race Conditions

In order to exploit race conditions [START_REF]OWASP: Race Conditions[END_REF] in web applications, attackers can send several crafted requests almost in parallel. If the web application does not handle concurrent requests by proper synchronisation, the actual application semantics can be changed in this way. In one real-world example, a web application provided an interface to send a limited number of SMS text messages per day [START_REF] Paleari | On Race Vulnerabilities in Web Applications[END_REF]. The web application first checked the current amount of sent messages (time-of-check ), then delivered the message according to the received request, and finally updated the number of sent messages in the database (time-of-use). Attackers were able to send more messages than allowed by the web application by crafting a number of HTTP requests, each containing the receiver and text of the message to be sent. These requests were sent almost in parallel and the multi-threaded web application processed the incoming requests concurrently. This way, the attacker exploited the fact that the messages were sent before the respective database entry was updated, leading to the delivery of all requested messages. The developers' underlying assumption was that users finish one transmission process before sending the next message and do not request one operation of the workflow several times in parallel.

HTTP Parameter Manipulation HTTP requests can contain parameters in addition to the receiving host, path, and resource. As the parameters are sent by the client, the user can control the parameters' values and which parameters are sent to the web application. Wang et al. [START_REF] Wang | How to Shop for Free Online -Security Analysis of Cashier-as-a-Service Based Web Stores[END_REF] found a bunch of logic flaws in well-known merchant systems and Cashier-as-a-Service (CaaS) services. These flaws allowed them to buy any item for the price of the cheapest item in the store. In 2011, the Citigroup faced an attack on their customers' data [START_REF]Thieves Found Citigroup Site an Easy Entry[END_REF]. The attackers were able to access names, credit card numbers, e-mail addresses and transaction histories. All the attackers had to do was simply changing the HTTP parameters in the web browser. By automation, they obtained confidential data of more than 200,000 customers.

File Inclusion Attacks are a special kind of HTTP parameter manipulation. The successful attacker gains access to protected resources be it static documents or application functions. For instance, an application might offer the URL http://example.com/?view=welcome.html as a hyperlink. In this case, the view parameter holds the name of a file that is supposed to be included in the output. An attacker can change the parameter value to /etc/passwd. He succeeds if the application fails to detect the manipulation. A successful file inclusion attack allows to access all files that are readable to the web server process.

Unsolicited Request Sequences Attackers can not only modify the requests' parameters but also craft requests to any method of the web application. Besides manipulated HTTP parameters, web applications might face unexpected requests to any method. For instance, in another given scenario by Wang et al. [START_REF] Wang | How to Shop for Free Online -Security Analysis of Cashier-as-a-Service Based Web Stores[END_REF], a malicious shopper was able to add items to her cart between checkout and payment. She was only charged the value of her cart at checkout time. The recently added items were shipped but not invoiced.

Forceful Browsing A forceful browsing attacker exploits predictable naming schemes in combination with insufficient access control. For instance, left installation scripts for PHP-based web applications are popular targets for forceful browsing attacks. An administrator uploads such a script to the web server and calls it via her browser in order to install a web application. Attackers can call the installation script and reconfigure the application if the administrator forgets to delete it. In 2010, a group of attackers gained access to 114,000 user records of iPad owners by requesting a server-side script that was supposed to embed user details into a web page [START_REF] Tate | Apple's Worst Security Breach: 114,000 iPad Owners Exposed[END_REF]. The attackers could easily guess the naming scheme and access restricted application functions.

Root Causes

All described attacks share common root causes. Web application developers assume that users first request one of possibly several application entry points, e.g. the base directory at http://www.example.com. Upon the first request, the web application sends a given response containing a set of hyperlinks or a redirect instruction to the client. As users tend to click on hyperlinks in order to navigate through the application, developers might assume that only the given requests will be accessed next. However, the user is technically not bound to click on one of the provided hyperlinks but she can still send requests that are not provided within this response. Sent requests can differ from provided hyperlinks in terms of addressed methods and HTTP parameters. Vulnerable web applications fail to handle unintended user behavior in terms of sequences of requests.

More formally, web application developers implement implicit control-flow graphs. In each state, sending a request leads to a subsequent state in the graph. Executing a step corresponds to changing the server-side state. Control-flow weaknesses occur if an attacker is able to address at least one method, i.e. cause a state-changing action, that is not meant to be addressed in the respective session state. In the respective control-flow graph, this transition does not exist due to the developer's assumption that the request does not happen at that time. Vice versa, a web application implementing a control-flow graph with transitions for all requests in every state is not susceptible to control-flow weaknesses.

Forceful browsing attacks and some cases of HTTP parameter manipulation can be overcome with access control. The other attack vectors, however, include only requests that are in the scope of the user's rights. Access control mechanisms prevent users from accessing sensitive API methods at all time while control-flow integrity protection prohibits access to regular API methods at the wrong time.

Preserving Control-Flow Integrity Ad Hoc

In this section, we present Ghostrail, our approach to overcome the attacks described in Sec. 2. We give details on the implementation in Sec. 4.

High-Level Overview

The idea behind Ghostrail is the ad hoc enforcement of control-flow integrity based on the developer's assumptions phrased in Sec. 2.3: Users first request one entry point of the web application, e.g. www.example.com, and then click on links and buttons or fill in forms. We assume that the attacker is a web user that controls all client-side data and applications within his domain. However, he can not bypass reverse proxies. He can send messages to the server but does not control the server-side platform.

Ghostrail operates as a traffic monitor on the server side. It protects a web application against the attacks described in Sec. 2.2 by filtering out incoming requests that are not generated by user clicks and form entries. In order to determine whether a request arises from regular interaction between the user and the current web page, Ghostrail analyzes the last web page delivered by the web application. A request is accepted if the web page contained the respective link. Otherwise -the page did not contain the requested URL -the request is considered crafted and, thus, possibly malicious because it violates the assumption that the user only interacts with the web application using clicks and filling in forms. Ghostrail has a three-tier whitelisting approach to derive regular requests:

-First, Ghostrail queries an application-wide whitelist of always allowed requests. The list contains the application's entry points, e.g. the start page, and possibly all requests to public resources that do not change the application's state. -Second, Ghostrail parses the last web page delivered by the web application.

It compiles a list of static references found in HTML and CSS documents. Those references denote hyperlinks, i.e., possible next user clicks, or embedded resources that are needed by the browser to render the web page, e.g. images. We give more details on static reference extraction in Sec. 3.2. -Third, Ghostrail renders web pages in server-side sandboxes to determine dynamically generated requests, e.g. using AJAX and JavaScript. Those requests can not be determined by the static parser in step 2. Ghostrail accepts requests from client side if the sandbox triggered the same request. We describe the sandbox-based request detection in Sec. 3.3. Ghostrail lets only requests found in any of these three lists pass. This way, it enforces the assumption that users do only interact with the web application using mouse clicks and form input. Due to the fact that the whitelists in step 2 and step 3 are compiled ad hoc, Ghostrail neither needs a pre-release learning phase to generate its control-flow policy nor a hand-crafted control-flow definition. However, as Ghostrail operates on automatically generated whitelists of references, every reference it fails to extract may degrade the usability of the web application. It is therefore crucial to extract as many references as possible. By extraction we mean the analysis, classification and storage of reference information that is embedded in content delivered by the web application. In the remainder of this section, we provide details on how Ghostrail extracts references statically and dynamically.

Extraction of Static References

In this section, we give details on how Ghostrail extracts static URLs from delivered web pages. Static references usually occur in HTML and CSS files. Other web resources like JavaScript and Flash, i.e., ActionScript, mainly utilize dynamic URL generation. They assemble the requests based on user input or client-side state. We explain dynamic URL tracking in the next section. Finally, media files like images are ignored because they do not contain links for subsequent requests.

HTML is a tag-based language, i.e., the elements of a web page are described as tags. There is a limited number of HTML tags that may contain URLs: <a>, <link>, <iframe>, <script>, <img>, <area>, <embed>, <form>, <base>, and <meta>. Ghostrail parses these tags and extracts URLs found. However, not all HTML content is trustworthy. Web applications often allow users to provide own content, e.g. in the form of comments that are embedded in the HTML output. An attacker could easily abuse such a feature by posting the URLs he wants to request next. It is therefore possible and necessary to configure Ghostrail so that it excludes user-provided content from reference extraction within HTML documents. The second type of static content that may contain references is CSS data. As this is limited to only one syntax element (url()), an adequate regular expression performs the reference extraction.

There can be different URLs that are semantically identical, e.g. http:// example.org/?par1=foo&par2=bar and http://example.org/?par2=bar&par1= foo. Ghostrail normalizes URLs in order to prevent misclassification.

During reference extraction, Ghostrail tags whitelisted URLs either as a transition or as an extension. Transitions make the browser replace the current web page while extensions only update a part of the page, e.g. in a iframe or by an AJAX request, or load an additional page in a new browser window (or tab) without modifying the parent window. A transition invalidates all previous whitelisted URLs whereas an extension adds new URLs to the whitelist.

Replication of Client-Side Execution

Beside the static references, dynamically generated requests play an important role within modern web applications. Applications that used to be installed and executed on a local machine, for instance office apps, move to the Web and become accessible via a web browser. The synchronization of client and server state as well as seamless interface updates require dynamic request generation and response processing, known as AJAX. The same is true for the search-asyou-type feature during user input. Such dynamically generated requests can not be determined using the static reference extraction described in Sec. 3.2 because the static analysis of JavaScript code is fault-prone and requires manual code annotations [START_REF] Guha | Using Static Analysis for Ajax Intrusion Detection[END_REF]. Ghostrail, however, aims to protect web applications without the need to change the application code. Instead, we equipped Ghostrail with a server-side replica of the user's browser to track the execution of JavaScript and derive the respective requests. Ghostrail maintains one replica for each user session. Each replica runs in a sandbox and virtually performs the same actions that happen in the user's browser. In order to monitor a user's actions, Ghostrail injects a few lines of JavaScript code into every delivered web page. This code monitors all user actions that can trigger JavaScript events. This is necessary because JavaScript has an eventdriven execution paradigm: Code is not executed linearly but triggered by user actions, timing, or state changes of the web page. While timing and state changes also happen in the server-side replica without further ado, user actions must be transmitted to keep track. Interesting user actions include mouse movements, mouse clicks, and keystrokes. The server-side replica virtually renders the same web page as the user, it executes the same JavaScript code, and it simulates the user's mouse movements, clicks, and form input, i.e., only expected -thus benign -user actions. The requests from the replica are the condensed set of expected user requests.

So, Ghostrail adds them to the user's whitelist. It is important to stress that Ghostrail only receives user actions from client side but not the respective state change in the user's browser. This is a crucial point because it limits a malicious user's scope: transmitting state changes allows an attacker to modify his browser such that it finally generates an attack request. For instance, a hash function may compute a URL parameter. The modified browser would always output /etc/passwd, independent of the input. Transmitting the output would allow the attacker to inject crafted requests into Ghostrail's whitelist. Limited to user actions, he can only spoof mouse clicks, movements and keystrokes on the web page. However, all these actions are within the scope of expected user interaction so there is no attack even if these actions are spoofed.

Fig. 1 shows the initial loading of a web page in the sandbox. The replica is initiated with the start of the user session (steps A/B). After the page has been fetched from the web application (steps D/E), it is send as a response to the client and the replica (step F). The replica does not interact directly with the web application to prevent double impact on the application state. Also, the duplication of the application's response (step F) ensures that both the client and the replica share the same content. After the page load, the user can interact with the web page. Fig. 2 shows an example how Ghostrail classifies dynamic references. The user clicks on an element (step A). The details are transmitted to Ghostrail and forwarded to the replica (step B) which simulates the same mouse click. The subsequent request to click.php (step C) is recorded by Ghostrail as legitimate because it is the result of intended user interaction. So, Ghostrail accepts and forwards the user request (step D).

Implementation

In this section, we describe the implementation of Ghostrail and the sandboxed replica. We implemented Ghostrail as a reverse proxy using Node.js (version 0.10.0) [9]. This reverse proxy manages all requests and responses and directs the replicas (see Sec. 3.3) as well as the static reference parser (see Sec. 3.2). This design allows to outsource CPU-or memory-intensive processes to other machines. The reverse proxy buffers incoming requests, queries the three-tiered list of regular requests (see Sec. 3.1) and finally accepts or rejects the request. It forwards the web application's responses to the static reference parser and the respective replica for further analysis. In the remainder of this section, we focus on the implementation of the replicas and the handling of client-side data.

The Sandboxed Replica

Ghostrail initiates a fresh replica for each user session -and destroys replicas when the session ends. We implemented the replicas using PhantomJS [START_REF] Hidayat | PhantomJS[END_REF], a fully-fledged, GUI-less, and WebKit-based browser. Due to the WebKit basis, the replicas support all major web technologies like JavaScript, AJAX, CSS, JSON and SVG. Replicas do not need to run on the same machine as Ghostrail. They can be distributed to cloud-based computing platforms to scale with varying load. The communication between the replicas and Ghostrail is based on HTTP and WebSockets.

Ghostrail injects a small piece of JavaScript code into every web page that is delivered to the user. This code establishes a WebSocket connection with Ghostrail to transmit user actions. Ghostrail records three kinds of user actions:

-Mouse clicks: Ghostrail records mouse clicks by injecting the onclick event handler for the whole web page. In order to simulate the click in the right page area, the (x, y) coordinates relative to the browser window are appended. Also, the dimensions of the browser window must be transmitted to configure the replica with the same size. -Mouse movements: Mouse movements can trigger onmouseover events on a web page. Hence, Ghostrail records mouse movements above a configurable threshold using the onmousemove event handler. The threshold is necessary to avoid an overload of Ghostrail.

-Key strokes: Requests can contain user-defined data from an HTML form.

Ghostrail must record every key stroke (using onkeypress and onkeyup event handlers) to simulate the user input. This is the only option to relate the resulting request to regular user behavior, i.e., entering data into form fields. While Ghostrail injects new event handlers into the web page, there could be other event handlers that fire first and bypass Ghostrail's events. For instance, an event handler that redirects the browser to another page is executed first such that Ghostrail loses track and forbids future regular requests. We overcome this issue the following way: There are two options for the order of cascading event handlers, namely event bubbling and event capturing [START_REF] Kantor | JavaScript Tutorial -Bubbling and capturing[END_REF]. Event bubbling triggers the innermost event of the DOM tree first, i.e., for nested elements where each has an onclick event handler, the event of the inner element fires first when the user clicks. Event capturing has the reverse execution order. Ghostrail enforces event capturing and assigns its event handlers to the outermost element of the DOM tree, i.e., document.

Handling Browser Cache and History

In order to improve performance, browsers cache web content locally. Upon the next page access, they first query their local cache and restore the page without the need to request it again from the website. This, however, poses a problem to Ghostrail if it can not observe the local page load and extract the references from the cached page. We implemented a twofold cache management in Ghostrail to overcome this issue: First, Ghostrail adds the Cache-Control: no-cache HTTP header [START_REF] Fielding | [END_REF] to each response to prevent caching on client side. More precisely, the browser may cache the respective content but must revalidate every usage with the server. However, we found that the Chrome and the Firefox browser still cache at least the last visited page and reuse it without revalidation. Second, the client-side code detects the click that loads the cached resource. Then, the replica performs the same click and loads the same content from the local cache provided by PhantomJS. Beside the local cache, browsers also maintain a local browsing history. This history allows users to navigate back and forth. PhantomJS supports the browsing history since version 1.8 such that the replica can emulate the navigation through the browsing history.

Evaluation

We evaluate the security gain by Ghostrail, investigate a possible impact of Ghostrail on the protected web application's availability, and give results of our performance measurements.

The Security Gain by Ghostrail

In order to evaluate the security gain by Ghostrail, we first describe how Ghostrail protects web applications against the attacks described in Sec. 2.2. Then, we explain our practical evaluation using the intentionally vulnerable web application Google Gruyere [START_REF] Gruyere | [END_REF].

An attacker who exploits race conditions in web applications must send the same request many times in parallel. If the request is compiled dynamically, he must prepare the respective input in his browser and send the form using a mouse click to make the request be also sent by the replica and thus be whitelisted. In any case, as soon as Ghostrail accepts the attacker's first request, it immediately discards the whitelist of requests and waits for the application response to refill the list of expected requests. So, Ghostrail rejects the second request unless it is extracted from the subsequent page.

HTTP parameter manipulation attacks rely on the user's ability to freely change the parameters of a given request, e.g. to change the given account ID or message ID. While an attacker can still craft arbitrary requests in his browser's address line, Ghostrail rejects all requests that do not match an extracted request from the current page.

Unsolicited request sequences occur if an attacker can assemble a request to call application functions when they are not supposed to be called. In the example given in Sec. 2.2, the attacker knows the request that adds items to his shopping cart. As Ghostrail discards previously allowed requests, the crafted request is not whitelisted after checkout and thus rejected.

A forceful browsing attacker also needs to craft a targeted request that is not part of the current web page. So, Ghostrail rejects forceful browsing attempts by design.

In order to evaluate Ghostrail's protection in practice, we set up Google Gruyere that is vulnerable to forceful browsing, file inclusion, and reflected crosssite scripting (XSS) attacks. With Ghostrail in place, none of the attacks on Gruyere worked. However, we want to emphasize that injection attacks like XSS and SQL injection are out of scope for Ghostrail. If the attacker enters the payload into a form field, Ghostrail regards the resulting request as benign. So, protected applications still need to sanitize user input from free text form fields.

Nevertheless, Ghostrail limits possible user input via drop-down menus or radio buttons to the given options.

As Ghostrail plays the role of a traffic monitor, it must be the server-side endpoint of SSL connections with the client side. Given that it runs in the same domain as the protected web application, we do not consider this point a serious issue. If needed, the communication between Ghostrail and the web application, as well as between Ghostrail and the replicas, can be encrypted again.

The Impact of Ghostrail on the Availability of the Protected Web Application

We evaluated whether Ghostrail has a negative impact on the web application's availability. A negative side effect can occur if Ghostrail fails to extract a regular reference that is accessed by the user in the next step. In that case, Ghostrail mistakenly classifies the user request as unexpected (false negative). The evaluation is threefold: First, we set up a demo web application that implements a broad range of modern web technologies, i.e., redirects, CSS, jQuery as a representative JavaScript library, dynamic page updates via AJAX, and the navigation to dynamically generated URLs. This approach is meant to find out whether there are general compatibility issues of Ghostrail with any web technology. We used Selenium [START_REF] Seleniumhq | Browser Automation[END_REF] to direct an instance of Firefox and Chromium respectively. Each browser performed virtually 1,000 user actions, resulting in 20,648 requests overall (each user action can trigger several requests). Afterwards, we analyzed Ghostrail's log files and did not find any blocked request. Please note that every blocked request would be a false negative because the virtual users only clicked on links on filled forms -what we defined as compliant behavior. Second, we set up Ghostrail as a reverse proxy for the Alexa Top 20 websites. We used Selenium again to make Firefox perform 200 user actions on each website. Overall, we recorded 18,319 requests with a false rejection rate of 17.57%. Our analysis showed that blocked requests contained customized elements. Some websites perform a kind of client fingerprinting, i.e., they read browser and system features that differ for Firefox and the replica and add such information to the requests. The replica proved able to simulate the more common User-Agent: string for client classification. Another source for blocked requests are client-side timestamps and random numbers generated by JavaScript and appended to requests. In these cases, the outcome of code execution differs for the browser and the replica. While we had to consider each web application as a black box, the application provider can configure Ghostrail more appropriately to avoid most of the false rejections, e.g. by adding a rule that ignores differing parameters if they match the expected pattern and if their processing may not cause harm. We avoid transmitting the random numbers and timestamps from client side to the replica for synchronization because this would allow a malicious user to inject arbitrary HTTP parameters.

Third, we accessed three websites manually to learn the perceivable impact of Ghostrail. This is important because the raw number of blocked requests does not make a point concerning the impact on the web application's availability.

-Google search: The search function was usable without interference. Only the auto completion did not work due to differing request parameters. -Amazon: We were able to search items, add them to our cart and checkout.

However, we did not see product recommendations. The almost complete functionality of Amazon is particularly interesting because we experienced the highest number of falsely rejected requests (≈ 60%). This result calls the significance of the raw number of false rejections into question. -Wikipedia: We did not experience any issues on the availability.

We found that Ghostrail is able to allow workflows which span several domains. For instance, Ghostrail may protect an online shopping web application. When the user is redirected to a third-party cashier like PayPal, Ghostrail can not track the payment process (however, the cashier may run another instance of Ghostrail). Hence, the first request that leads the user back to the shopping application must be whitelisted as an application entry point. Instead of redirecting, a web application may include third-party content in its own pages. Then, the replica fetches the same content but does not provide cookies or authenticating HTTP parameters to avoid requests on behalf of the user.

Performance

Finally, we evaluated the performance impact of Ghostrail. We measured the HTTP round trip time between sending a request and receiving the response. We used the testbed with our demo application described above in order to avoid independent factors on the performance. The size of the served web pages ranges from 225KB to 450KB, and the round-trip overhead was between 250ms and 360ms. For applications with real-time requirements, e.g. online games, Ghostrail may only be an intermediate solution. For other applications, it is possible to scale the number of Ghostrail and replica instances with the load.

Related Work

The Open Web Application Security Project (OWASP) coined the term Failure to Restrict URL Access [START_REF]OWASP: Failure to Restrict URL Access[END_REF] to describe a similar vulnerability as our controlflow weakness. However, it is more focused on access control flaws. Workflows and control-flow integrity play a tangential role in the description.

With existing approaches, every change on the web application either needs a manual change on the policy definition [START_REF] Jayaraman | Enforcing Request Integrity in Web Applications[END_REF][START_REF] Braun | Control-Flow Integrity in Web Applications[END_REF] or a new pre-release learning phase to derive the policy automatically [START_REF] Balzarotti | Multi-Module Vulnerability Analysis of Web-based Applications[END_REF][START_REF] Cova | Swaddler: An Approach for the Anomaly-based Detection of State Violations in Web Applications[END_REF][START_REF] Felmetsger | Toward Automated Detection of Logic Vulnerabilities in Web Applications[END_REF][START_REF] Li | BLOCK: A Black-box Approach for Detection of State Violation Attacks Towards Web Applications[END_REF]. Their policies can never be sound because training phases always miss unusual scenarios and manual policy definition requires expert knowledge and is prone to human faults. Also, all such approaches must be fuzzy by design because they neglect the actual request context, e.g. HTTP parameters like an ID that change case-by-case but must not be changed by the user. Ghostrail is able to enforce exact parameter matching without a need for policy updates.

Depending on the business logic of the web application, changes on the clientside JavaScript code can cause damage to the application provider. Existing approaches statically analyze JavaScript to determine the expected sequence of requests [START_REF] Guha | Using Static Analysis for Ajax Intrusion Detection[END_REF] or check the web application for exploitable HTTP parameter pollution vulnerabilities [START_REF] Balduzzi | Automated Discovery of Parameter Pollution Vulnerabilities in Web Applications[END_REF]. Two approaches replicate client-side computation on server side to detect deviations: NoTamper [START_REF] Bisht | No-Tamper: Automatic Blackbox Detection of Parameter Tampering Opportunities in Web Applications[END_REF] focuses on input validation of HTML forms, while Ripley [START_REF] Vikram | Ripley: Automatically Securing Web 2.0 Applications Through Replicated Execution[END_REF] follows a similar approach to ours. It replicates client-side JavaScript events in a server-side replica. However, Ripley is only applicable during development but not for legacy applications. Also, it relies on a distributing compiler thus excludes non-fitting technologies. Technically, Ripley ignores mouse movements on client side and can not track respective events. As it uses event bubbling, it misses client-side events that redirect the browser. Ripley can not handle JavaScript code from different domains like common JavaScript libraries, mash-ups, and the postMessage API for communication between iframes. In that sense, Ghostrail is the consequent next step after Ripley because it covers modern application scenarios and all relevant user actions, thus makes less assumptions. Ripley and Ghostrail still share the same issues with randomness and timestamps.

An attacker exploiting a race condition vulnerability [START_REF]OWASP: Race Conditions[END_REF] can execute one function more often than intended by the application developer. Paleari et al. [START_REF] Paleari | On Race Vulnerabilities in Web Applications[END_REF] describe an approach to detect race condition vulnerabilities in web applications.

Conclusion

We explained the complex problem of control-flow vulnerabilities and showed its high practical relevance by real-world examples, i.e., existing vulnerabilities and attacks. We identified the root causes in the attacker's possibility to craft arbitrary requests at any time together with the developer's assumption that users only follow provided links. Ghostrail overcomes this problem by the ad hoc generation of next step policies. It is the first approach that neither needs a repeated training phase nor a manual policy definition and covers the whole bandwidth of related vulnerabilities, including race conditions, HTTP parameter manipulation, unsolicited request sequences, and forceful browsing. Ghostrail is compatible with all modern web technologies including mash-up's and JavaScript libraries while it is applicable to all new and legacy web applications without any changes on the application code. For high-traffic applications, the induced load can be moved to any appropriate platform. In sum, we provided a thorough approach that provides guarantees to the developer concerning the sequences of incoming requests including the values of parameters. As a side effect, Ghostrail mitigates Cross-Site Request Forgery (CSRF) and injection (XSS, SQLi) attacks in most cases.

Fig. 1 .

 1 Fig. 1. Initial loading of a web page in the sandbox.

Fig. 2 .

 2 Fig. 2. Dynamic reference extraction by replicating an user's action.


Miaomiao Tian
email: miaotian@mail.ustc.edu.cn.

Liusheng Huang

Efficient identity-based signature from lattices

Keywords: identity-based signature, lattice, performance

Identity-based signature is an important technique for light-weight authentication. Recently, many efforts have been made to construct identity-based signatures over lattice assumptions since they would remain secure in future quantum age. In this paper we present a new identity-based signature scheme from lattice problems. This scheme is more efficient than other lattice-based identity-based signature schemes in terms of both computation and communication complexities. We prove its security in the random oracle model under short integer solution assumption that is as hard as approximating several worst-case lattice problems.

Introduction

As the rapid development of networks, authentication between users is becoming increasingly important. In many scenarios, improving the performance of authentication is crucial. For example, in wireless sensor network and mobile social network, the battery life of devices is so short that complex authentication protocols are intolerable. Since digital signature is a main building block of authentication, reducing its complexity is an apparent approach towards meeting this demand. One way of reducing the complexity of signatures is to use identity-based signatures instead of regular signatures (which rely on certificates).

Identity-based signature (IBS) is a basic component of identity-based cryptography that was first introduced by Shamir [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF] in 1984. As an alternative of traditional certificate-based cryptography, identity-based cryptography possesses an arresting advantage, i.e., it eliminates the onerous certificate management procedure in traditional certificate-based cryptography. To achieve the merit, each user in identity-based cryptosystem sets his identity (e.g. his e-mail address) as his public key (while in traditional certificate-based cryptosystem, users' public keys are random strings). The secret key of any user is generated by a trusted Private Key Generator (PKG) from PKG's secret key and the user's identity. Thanks to this advantage, IBSs are more preferable than regular signatures in many real-world applications. After Shamir's seminal work, several IBSs emerged (e.g. [START_REF] Fiat | How to prove yourself: practical solutions to identification and signature problems[END_REF]), however fully practical implementations are recently proposed due to the work of [START_REF] Boneh | Identity-based encryption from the weil pairing[END_REF]. In [START_REF] Boneh | Identity-based encryption from the weil pairing[END_REF], Boneh and Franklin designed an efficient identity-based encryption scheme by utilizing bilinear pairings. Since then, many excellent proposals for IBS appeared based on pairings [START_REF] Hess | Efficient identity based signature schemes based on pairings[END_REF][START_REF] Choon | An identity-based signature from gap diffie-hellman groups[END_REF][START_REF] Barreto | Efficient and provably-secure identity-based signatures and signcryption from bilinear maps[END_REF][START_REF] Paterson | Efficient identity-based signatures secure in the standard model[END_REF]. These IBS proposals are very efficient for practical applications, whereas they all substantially rely on the discrete logarithm problem that is facile for quantum computers [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. In view of the recent progresses of quantum computer, looking for quantum-immune IBSs is no longer alarmist. To achieve this, new mathematical tool on which cryptographic schemes are built should be developed. Lattice seems to be our best option because cryptographic schemes based on lattices are supported by worst-case hardness assumption and conjectured to withstand quantum attacks. Moreover, lattice-based cryptographic schemes are also easy to implement since typical computations involved in them are only integer matrix-vector multiplication and modular addition. (See [START_REF] Regev | Lattice-based cryptography[END_REF] for an overview on lattice-based cryptography.)

In 2010, Rückert [START_REF] Rückert | Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[END_REF] successfully constructed the first two (hierarchical) IBSs over lattice assumptions. One is secure in the random oracle model and the other is secure in the standard model. Later on, some other lattice-based IBSs also appeared, e.g., [START_REF] Tian | Efficient hierarchical identity-based signatures from lattices[END_REF][START_REF] Liu | Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model[END_REF]). All of the IBS constructions followed the signature framework of Gentry, Peikert and Vaikuntanathan [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. According to the framework, the signing key S of a user is a trapdoor of the function like f A (x) = Ax mod q, where A is a user-related matrix. Typically S is a short basis of the lattice defined by A. Armed with the signing key S, the user can run a preimage sampling algorithm for the function f A to obtain a signature sig. For those lattice IBS schemes, the generation of users' signing keys requires lattice basis delegation technique [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF][START_REF] Agrawal | Lattice basis delegation in fixed dimension and shorterciphertext hierarchical ibe[END_REF][START_REF] Agrawal | Efficient lattice (h)ibe in the standard model[END_REF]. Since the signing key size and the signature length will increase dramatically after lattice basis delegation, those IBSs would be inefficient in practice. In addition, the short basis (signing key) extraction algorithms involved in them are also very expensive, thus PKG will be overburdened.

Our Contributions. In this paper, we construct a new IBS scheme over lattice assumptions, which does not follow the signature framework of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. Actually, our IBS scheme adopts the rejection sampling technique of [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] and can be viewed as an identity-based version of Lyubashevsky's signature scheme [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. Compared with other lattice-based IBS schemes, our scheme is much more efficient in terms of both communication and computation overhead. We prove the IBS scheme is secure against adaptive chosen message and identity attacks in the random oracle model under conventional short integer solution (SIS) assumption which, in turn, leads our IBS scheme to be secure under the worst-case hardness of approximating several classic lattice problems, by the results of [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF].

Paper Organization. The remainder of this paper is organized as follows. Section 2 and Section 3 respectively give some preliminaries and an efficient signing key extraction algorithm to be used in this work. Section 4 provides our lattice-based IBS scheme. Section 5 concludes the whole paper.

Preliminaries

Notation

Throughout this paper, the security parameter is a positive integer n. For a positive integer k, [k] denotes the set {1, • • • , k}. Vectors are assumed to be in column form and are written as bold low-case letters, e.g., v. The ith component of v is represented by v i , and the ℓ p norm of v is denoted by ||v|| p (we will avoid writing p if p = 2). Matrices are represented by bold upper-case letters, e.g., A. Let the ith column of A be a i and define ||A|| p = max i (||a i || p ). For a full rank square matrix A, its Gram-Schmidt orthogonalization is denoted as A.

We say a function f (n) is negligible if it is smaller than all polynomial fractions for sufficiently large n, and we use negl(n) to denote a negligible function of n. We say an event occurs with overwhelming probability if its probability is 1 -negl(n).

The statistical distance between two distributions X and Y over some finite set F is defined as max e⊆F |X(e) -Y (e)|. We say that two distributions are statistically close if their statistical distance is negligible.

Lattices

An m-dimensional lattice Λ is a full-rank discrete subgroup of R m . In this paper, we focus on integer lattices, i.e., those lattices whose points have coordinates in Z m . Among these lattices are the "q-ary" lattices. Definition 1. For prime q, u ∈ Z n q and A ∈ Z n×m q , define the "q-ary" lattices as follows:

Λ ⊥ (A) = {e ∈ Z m : Ae = 0 (mod q)}, Λ u (A) = {e ∈ Z m : Ae = u (mod q)}.

Gaussians on Lattices

The Gaussian function is a useful tool in lattice-based cryptography.

Definition 2. For any s > 0 and c ∈ R m , define the Gaussian function as:

g s,c (x) = exp(-π||x -c|| 2 /s 2 ).
Let g s,c (Λ) be a sum of g s,c over the lattice Λ. The discrete Gaussian distribution over Λ with center c and parameter s is defined as

G Λ,s,c = g s,c (x)/g s,c (Λ).
For notational convenience, in the rest of the paper, g s,0 and G Λ,s,0 will be abbreviated as g s and G Λ,s , respectively.

The following facts about discrete Gaussian distribution are very useful in this work. They are from [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF] and [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], respectively. Lemma 1. Let q prime and integer m ≥ 2n log q and let Gaussian parameter s ≥ ω( √ log m). For any u ∈ Z n q , we have: 1. For all but a q -n fraction of

A ∈ Z n×m q , Pr[ x ← G Λ u (A),s : ||x|| > s √ m ] ≤ negl(n). 2. For all but a 2q -n fraction of A ∈ Z n×m q
, if e ← G Z m ,s , then the distribution of the syndrome t = Ae (mod q) is statistically close to uniform over Z n q .

Hardness Assumption

The security of our signature scheme rests on the hardness of SIS problem [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF].

Definition 3. Given an integer q > 0, a matrix A ∈ Z n×m q and a real γ, the SIS problem is finding a vector v ∈ Z m \{0} such that Av = 0 (mod q) and ||v|| ≤ γ.

For the hardness of SIS problem, Micciancio and Regev [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF] have showed that, for any polynomial-bounded m, γ and for any prime q ≥ γ • ω( √ n log n), solving SIS on the average is as hard as approximating some intractable lattice problems such as the shortest lattice vector problem in the worst case.

Short Bases of Lattices

Short basis of a lattice is an important concept in many lattice-based cryptographic schemes. Here, we recall two useful theorems on short lattice bases. The first theorem is adapted from Lemma 3.5 of [START_REF] Alwen | Generating shorter bases for hard random lattices[END_REF] that shows a recent result on how to generate a short basis of an approximate uniform lattice. The second theorem comes from [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] that is about how to use a short lattice basis to solve a kind of SIS problems.

Theorem 1. Let q ≥ 3 be odd and m > 5n log q. There is a probabilistic polynomial-time (PPT) algorithm TrapGen(q, n) that outputs a matrix A ∈ Z n×m q and a basis B ∈ Z m×m of Λ ⊥ (A) such that A is statistical close to uniform, and ||B|| ≤ O(n log q) and || B|| ≤ O( √ n log q) with overwhelming probability. Theorem 2. Let m ≥ n be an integer and q be prime. Let Λ ⊥ (A) be a lattice defined by matrix A ∈ Z n×m q and B be a basis of

Λ ⊥ (A). If s ≥ ∥ B∥ • ω( √ log n)
, then for any u ∈ Z n q , there is a PPT algorithm SamplePre(A, B, s, u) that outputs a vector v ∈ Λ u (A) from a distribution that is statistically close to G Λ u (A),s .

Discrete Normal Distribution

This work will also make use of the discrete normal distribution. Definition 4. For any σ > 0 and c ∈ Z m , define the continuous normal distribution as:

ρ m σ,c (x) = (2πσ 2 ) -m 2 exp(- ||x -c|| 2 2σ 2 ).
Let ρ m σ,c (Z m ) be a sum of ρ m σ,c over Z m . The discrete normal distribution over Z m centered at c ∈ Z with parameter σ is defined as

D m σ,c (x) = ρ m σ,c (x)/ρ m σ,c (Z m ).
In the rest of the paper, we will abbreviate ρ m σ,0 and D m σ,0 as ρ m σ and D m σ . The following lemma shows two basic properties of such distributions [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF][START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF]. Lemma 2. For any σ > 0 and positive integer m, we have:

1. Pr[x ← D 1 σ : |x| > 12σ] < 2 -100 . 2. Pr[x ← D m σ : ||x|| > 2σ √ m ] < 2 -m .
Lyubashevsky [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] also shows the following interesting fact on the distribution.

Lemma 3. For any v ∈ Z m and positive real

α, if σ = ω(||v|| √ log m), we have P r[x ← D m σ : D m σ (x)/D m σ,v (x) = O(1)] = 1 -2 ω(log m) ,
and more specifically, if σ = α||v||, then

P r[x ← D m σ : D m σ (x)/D m σ,v (x) < e 12/α+1/(2α 2 ) ] > 1 -2 -100 .

Rejection Sampling Technique

The core idea of rejection sampling technique for a signature scheme is to make the distribution of the outputted signatures is independent of signing key. To achieve this goal, rejection sampling technique works as follows. When signing a message, a signer with signing key s first chooses a random y from some distribution and computes the candidate signature sig that is in the form of y adding to (or multiplying by) some function of s. Let the target distribution of the outputted signatures be f which is independent of s, and let the distribution of all candidate signatures be g which may be related to s. If f (x) ≤ M g(x) for all x and some real M > 0, then the candidate signature sig can be output with probability f (sig)/(M g(sig)). By [START_REF] Neumann | Various techniques used in connection with random digits[END_REF], we know if the signer follows the above process, then the distribution of the outputted signatures is f and the expected number of times this process will output a signature is M .

As an example of how to use the rejection sampling technique, consider the signature scheme of Lyubashevsky [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]. Its target distribution is D m σ . To sign a message µ, first select a random y from D m σ and compute z = y + Sc, where S is a signing key and c is a hash value on the inputs of y and µ. The candidate signature is (c, z). Notice that the z's distribution is D m σ,Sc and, by Lemma 3, D m σ (y)/D m σ,Sc (y) ≈ e. Therefore, according to the rejection sampling technique, we know there exists a small M (≈ e) such that if we output the candidate signature (c, z) with possibility min(1,

D m σ (z) M D m σ,Sc (z) ) then z's distribution is D m σ (in this case, by Lemma 2, we have ||z|| ≤ 2σ
√ m with a high probability) and the expected number of running the signing process is no more than M .

Matrix Sampling Algorithm

In our construction, we need an efficient algorithm to extract each user's signing key that is a short matrix S satisfying AS = U (mod q) for some user-defined matrix U. We address this problem by introducing the algorithm SampleMat that is an extension of the preimage sampling algorithm SamplePre of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF].

The algorithm SampleMat(A, B, s, U) works as follows.

1. Input A ∈ Z n×m q and U ∈ Z n×k q , a basis B of Λ ⊥ (A) and parameter s ≥ ∥ B∥ • ω( √ log n). 2. For each i ∈ [k], run algorithm SamplePre(A, B, s, u i )→ s i ∈ Z m . 3. Output S = [s 1 , • • • , s k ] ∈ Z m×k .
By Theorem 2, we know, for any u ∈ Z n q , the algorithm SamplePre(A, B, s, u) will sample a vector v ∈ Λ u (A) from a distribution that is statistically close to G Λ u (A),s . Therefore, we can easily check that the output S of the above algorithm SampleMat(A, B, s, U) satisfies AS = U (mod q) and its distribution is statistically close to

G Λ u 1 (A),s ו • •×G Λ u k (A),s (thus ||S|| ≤ s
√ m with overwhelming probability by Lemma 1). As a result, we have the following lemma. Lemma 4. Let m ≥ n and k ≥ 2 be positive integers, and let q be prime. Let Λ ⊥ (A) be a lattice defined by matrix A ∈ Z n×m q and B be a basis of

Λ ⊥ (A). If parameter s ≥ ∥ B∥ • ω( √ log n), then for any U ∈ Z n×k q
, there is a PPT algorithm SampleMat(A, B, s, U) that outputs a matrix S ∈ Z m×k from a distribution that is statistically close to G Λ U (A),s such that AS = U (mod q) and ||S|| ≤ s √ m with overwhelming probability, where

G Λ U (A),s = G Λ u 1 (A),s × • • • × G Λ u k (A),s .

An efficient IBS scheme from lattices

We here give the description of our efficient IBS scheme based on lattice assumptions.

Construction

Our IBS construction involves a few parameters defined below:

prime q ≥ 3, real M , m > 5n log q, k, λ are all positive integers.

-bound L = O( √ n log q), Gaussian parameter s = L • ω( √ log n), σ = 12sλm.
The IBS scheme works as follows.

Setup(n). Given a security parameter n, do the following: 1. Run TrapGen(q, n) to output an approximate uniform matrix A ∈ Z n×m q along with a basis B ∈ Z m×m q of Λ ⊥ (A) such that || B|| ≤ L.

Select two hash functions

H : {0, 1} * → {v : v ∈ {-1, 0, 1} k , ||v|| 1 ≤ λ} and

Correctness

Theorem 3. The identity-based signature scheme above satisfies correctness.

Proof. According to the construction of the IBS scheme, we know that

Az -H 1 (ID)h = Az -AS ID h = A(z -S ID h) = Ay Therefore, we have H(Az -H 1 (ID)h, µ) = H(Ay, µ) = h.
By simply combining the rejection sampling technique described in Section 2.7 with Lemma 3, we know the distribution of z is very close to D m σ . Therefore, by Lemma 2, we have ||z|| ≤ 2σ √ m with probability at least 1-2 -m .

Efficiency

The most efficient (presently known) lattice-based IBS schemes are those ones that are secure in the random oracle model, e.g., the IBS schemes1 proposed respectively by Rückert [START_REF] Rückert | Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[END_REF] and Tian et al. [START_REF] Tian | Efficient hierarchical identity-based signatures from lattices[END_REF]. We now compare the performance of our IBS scheme to that of the two schemes. Table 1 lists the comparison on the communication overhead of the three schemes for the same security parameter n, where the constant c is the bit length of all identities in Rückert's scheme with random oracle, s = s √ (c + 1)mω( √ log n) and ŝ = s • mω(log 3/2 n) are extended Gaussian parameters, and other parameters are the same as those in Section 4.1. Since m ≫ k and n ≫ λ(log k + 1) for reasonable security (e.g., 512 bits or more), one can easily check that the signing key size and the signature length of our scheme are both much smaller than those of Rückert's scheme as well as those of Tian et al.'s scheme. In terms of computation complexity, we can see that the signing and verification algorithms of our scheme are very simple because they only take matrix-vector multiplication, integer addition and hash operations, whereas signing a message in the schemes of Rückert and Tian et al. both need to run the more complicated algorithm SamplePre. Moreover, the signing key extraction algorithm in our scheme is the algorithm SampleMat, which is much faster than the algorithm RandBasis used in the extraction algorithms of Rückert and Tian et al.'s schemes.

Therefore, we can conclude that our IBS scheme is more efficient than other lattice-based ones in terms of both communication and computation overhead.

Security

Theorem 4. The proposed identity-based signature scheme is existential unforgeable against adaptive chosen message and identity attacks in the random oracle model, assuming the hardness of SIS problem.

The proof of Theorem 4 will appear in the full version of this paper.

Conclusion

In this paper, we presented the first lattice-based IBS scheme that dose not employ the signature framework of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]. We proved its security in the random oracle model under the SIS assumption. Our IBS scheme is more efficient than others based on lattices. We believe the ideas and techniques used in this work will also be helpful for designing other lattice-based signatures.

H 1 :. 3 . 2 .

 132 {0, 1} * → Z n×k q Output the public parameters params = {A, H, H 1 } and PKG's secret key SK = B. Extract(params, SK, ID). Given the public parameters params, PKG's secret key SK = B and an identity ID ∈ {0, 1} * , run algorithm SampleMat(A, B, s, H 1 (ID)) to obtain a signing key sk ID = S ID ∈ Z m×k for the user with identity ID. The correctness of S ID can be verified by checking if AS ID = H 1 (ID) and ||S ID || ≤ s √ m. Sign(params, µ, sk ID ). Given the public parameters params, a message µ ∈ {0, 1} * and a signing key sk ID = S ID , do the following: 1. Select a random y ← D m σ . Compute h = H(Ay, µ) and z = S ID h + y. 3. Output sig = (h, z) with probability min(1, D m σ (z) M D m σ,S ID h (z) ). If nothing is outputted, repeat the algorithm Sign(params, µ, sk ID ). Verify(params, sig, µ, ID). Given the public parameters params, a signature sig = (h, z), a message µ and an identity ID, output 1 if and only if h = H(Az -H 1 (ID)h, µ) and ||z|| ≤ 2σ √ m.

Table 1 .

 1 Comparison of several lattice-based IBS schemes

	Scheme Rückert [17] with RO Tian et al. [20] This work	(	Signing key size m(c + 1) ) 2 log(s √ (c + 1)m) m(c + 1) log(s Signature size √ (c + 1)m) + n m 2 log(ŝ √ m) m log(ŝ √ m) + n mk log(s √ m) m log(12σ) + λ(log k + 1)

Notice that these IBS schemes are both generalized ones, i.e., they may have more than two hierarchies. For comparability, we here set their hierarchy depth

as 2 (including the PKG).

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (No. 61202407), the Basic Perspective Project of SGCC (No. XXN51201304253), and the Natural Science Foundation of Jiangsu Province of China (No. BK2011357).


Yair Diaz-Tellez
email: y.diaz-tellez@qmul.ac.uk

Eliane L Bodanese
email: eliane.bodanese@qmul.ac.uk

Theo Dimitrakos
email: theo.dimitrakos@bt.com

Michael Turner
email: michael.turner@bt.com

CONTEXT-AWARE MULTIFACTOR AUTHENTICATION BASED ON DYNAMIC PIN

Keywords: authentication, dual ciphers, context-aware, dynamic PIN 1

An innovative context-aware multi-factor authentication scheme based on a dynamic PIN is presented. The scheme is based on graphical passwords where a challenge is dynamically produced based on contextual factors and client device constraints while balancing security assurance and usability. The approach utilizes a new methodology where the cryptographic transformation used to produce the Dynamic PIN changes dynamically based on the user input, history of authentications, and available authentication factors at the client device.

Introduction

User authentication is a means of identifying a user and verifying his identity. Different authentication methods exist, e.g. token-based, biometric-based, and knowledge-based. Each method has its own properties, (dis)advantages, and applications. Text passwords are a widely used method because of convenience and usability; however, they are vulnerable to key logging, shoulder-surfing, dictionary, and social engineering attacks. Graphical passwords are an alternative as they can mitigate the abovementioned attacks. One approach to increase assurance is multi-factor authentication. However, not all transactions require the same assurance level. An adequate level depends on criticality, sensitivity, context, and the risk involved. Additionally, there are trade-offs among variables such as assurance, performance, and usability.

This work proposes an innovative context-aware multi-factor authentication scheme based on a Dynamic PIN. The scheme produces a graphical challenge based on context, client device constraints, and risk associated, while balancing assurance and usability. Also, a methodology is proposed where the crypto-function used to produce the Dynamic PIN changes dynamically. A PIN is generated without any predictable backward and forward correlation making practically infeasible for an attacker to predict the next PIN. The approach leverages on the fact that users commonly use various types of client devices that incorporate authentication factors (e.g. SIM cards, biometric readers, etc.), sensors, and APIs, which can be integrated in the authentication process to modulate security assurance, and to optimize it using context.

Section 2 presents related work. The scheme consists of two functional phases: registration and setup: the user creates an account and registers different information (section 3); and challenge and dynamic PIN: a challenge and Dynamic PIN are generated (section 4). Section 5 presents the conclusions and future work.

Related Work

The proposed scheme considers how the properties of graphical passwords [START_REF] Xiaoyuan | Graphical passwords: a survey[END_REF] can be adjusted at runtime balancing assurance vs. usability. In [START_REF] Catuogno | A Graphical PIN Authentication Mechanism with Applications to Smart Cards and Low-Cost Devices[END_REF], a PIN-based mechanism is presented that uses a secret sequence of objects to analyze security vs. usability. This work does not consider the use of contextual information to influence the generation of the challenge. Several frameworks have been proposed that make use of context [START_REF] Bardram | Context-Aware User Authentication -Supporting Proximity-Based Login in Pervasive Computing[END_REF][START_REF] Corner | Protecting applications with transient authentication[END_REF]. [START_REF] Jakobsson | Implicit authentication for mobile devices[END_REF] introduces the notion of implicit authentication that consists in authenticating users based on behavioral patterns. [START_REF] Hayashi | CASA: context-aware scalable authentication[END_REF] presents a framework that combines passive factors (e.g. location) and active factors (e.g. tokens) in a probabilistic model for selecting an authentication scheme that satisfies security requirements; however, it does not consider client device constraints.

Security tokens, implementable on hardware[7] and software [START_REF] Aloul | Two factor authentication using mobile phones[END_REF], typically generate a one-time-password (OTP) [START_REF] Lamport | Password authentication with insecure communication[END_REF] in response to the user typing a PIN. Several tokenbased systems feature a fixed function that outputs the OTP [START_REF] Dodson | Secure, Consumer-Friendly Web Authentication and Payments with a Phone[END_REF][START_REF] Gianluigi | A mobile based approach to strong authentication on Web[END_REF][START_REF] Wen-Bin | Design of a time and location based One-Time Password authentication scheme[END_REF][START_REF] Soare | Internet Banking Two-Factor Authentication using Smartphones[END_REF][START_REF] Eldefrawy | Mobile one-time passwords: two-factor authentication using mobile phones[END_REF]. The proposed system is effectively a software-based security token that produces an OTP, i.e. the Dynamic PIN; and additionally, the crypto-function used changes itself dynamically improving the pseudo-randomness of the scheme.

Registration and Setup

Registering authentication factors. The scheme uses authentication factors that may be available on the client device, e.g. SIM number, or fingerprint. For each factor, the server creates a record and associates a secret seed generated randomly, � 𝑎𝑎𝑓𝑓 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑖𝑖 , 𝑎𝑎𝑓𝑓 𝑣𝑣𝑛𝑛𝑎𝑎𝑎𝑎𝑛𝑛 𝑖𝑖 , 𝑎𝑎𝑓𝑓 𝑠𝑠𝑛𝑛𝑛𝑛𝑠𝑠 𝑖𝑖 � with 𝑎𝑎𝑓𝑓 𝑖𝑖 an authentication factor. For example, (IMSI, 464989052765867, 4596). A vector of secret seeds is pushes into the device. An authentication token is computed by 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃2(𝑐𝑐𝑁𝑁𝑁𝑁𝑐𝑐𝑎𝑎𝐴𝐴� ( 𝑎𝑎𝑓𝑓 𝑣𝑣𝑛𝑛𝑎𝑎𝑎𝑎𝑛𝑛 𝑖𝑖 + 𝑎𝑎𝑓𝑓 𝑠𝑠𝑛𝑛𝑛𝑛𝑠𝑠 𝑖𝑖 )�). PBKDF2, a Key Derivation Function, is used to derive a key strong against brute force attacks. A token vector is defined as 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑐𝑐𝐴𝐴𝑁𝑁𝑁𝑁 = 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 1 , 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 2 , … 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑛𝑛 , where 𝑚𝑚 is the number of authentication factors registered for a device. The client must recreate the same token calculated at the server side. Notice that the value 𝑎𝑎𝑓𝑓 𝑣𝑣𝑛𝑛𝑎𝑎𝑎𝑎𝑛𝑛 𝑖𝑖 is obtained at runtime.

Registering the image-based password(s).

The user is presented with a selection of image categories, ℂ = {𝐶𝐶 1 , 𝐶𝐶 2 , 𝐶𝐶 3 , . . . } . Each category consists of image objects grouped by common characteristics easy to understand, e.g. icons. Let category C= (𝑁𝑁 1 , 𝑁𝑁 2 , 𝑁𝑁 3 , . . 𝑁𝑁 𝑛𝑛 ) ∈ ℂ be a set of 𝑁𝑁 objects. A seed is randomly generated for each object 𝑁𝑁 𝑖𝑖 . Let 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠𝑠𝑠𝑁𝑁𝑁𝑁𝑐𝑐𝐴𝐴𝑁𝑁𝑁𝑁 = (𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 1 , 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 2 , 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 3 , . . 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑛𝑛 ) be the vector of seeds with (𝑁𝑁 𝑖𝑖 , 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 ) ∈ (𝐶𝐶 × 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠𝑠𝑠𝑁𝑁𝑁𝑁𝑐𝑐𝐴𝐴𝑁𝑁𝑁𝑁). Each 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 is of 2 bytes length and represented as 4 hexadecimal digits (0-F). The user selects a subset of objects as his secret password: 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁 ⊂ 𝐶𝐶 . For |𝑁𝑁| ≫ |𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁| a brute force attack can become increasingly difficult as the number of combinations and permutations increases.

Registering device parameters. This includes form factor parameters about the device(s): type of device, display size, authentication interfaces -e.g. biometrics. These are used to specify at runtime an adequate customization of the image challenge.

4

Challenge and Dynamic PIN Generation Overview. Steps: (i) the server generates a random pin string (RPS) and the graphical challenge. The RPS is used as part of the dynamic pin generation algorithm. The challenge is constructed by combining a subset of secret and non-secret images based on device constraints, context, and level of assurance required. Due to lack of space, it is assumed the communication channel between client and server is secured. A key exchange protocol, e.g. Diffie Hellman, can be easily incorporated in the scheme. [START_REF] Catuogno | A Graphical PIN Authentication Mechanism with Applications to Smart Cards and Low-Cost Devices[END_REF] the user is asked to recognize the subset of secret images; (3) a crypto-function is computed dynamically based on different variable elements of information including user input, authentication factors, and history of authentication attempts; (4) the crypto-function is then used to generate the dynamic pin; (5) the client device sends the dynamic pin to the server for validation.

4.1

Generation of the RPS and the context-based image challenge.

In this section, first the random pin string (RPS) and the image challenge are introduced. Then, a rules-based mechanism used to parameterize and generate the challenge based on runtime context information, device constraints, and risk is presented.

Random pin string (RPS).

The RPS is a synchronization value used during the computation of the dynamic pin. The RPS is a pseudo-randomly generated string of 160 bytes in length: 𝑅𝑅𝑃𝑃𝑠𝑠 = 𝑅𝑅𝑃𝑃𝑃𝑃 1 𝑅𝑅𝑃𝑃𝑃𝑃 2 𝑅𝑅𝑃𝑃𝑃𝑃 3 … 𝑅𝑅𝑃𝑃𝑃𝑃 159 , 𝑤𝑤ℎ𝑁𝑁𝑁𝑁𝑁𝑁 𝑅𝑅𝑃𝑃𝑃𝑃 𝑖𝑖 𝑖𝑖𝑠𝑠 𝑎𝑎 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁.

Image challenge. The image challenge is the set 𝐶𝐶ℎ𝑎𝑎𝑎𝑎𝑎𝑎𝑁𝑁𝑁𝑁𝑎𝑎𝑁𝑁𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠 = (𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠 ∪ 𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠), 𝑤𝑤𝑖𝑖𝐴𝐴ℎ 𝑐𝑐𝑎𝑎𝑁𝑁𝑠𝑠𝑖𝑖𝑁𝑁𝑎𝑎𝑎𝑎𝑖𝑖𝐴𝐴𝑏𝑏 |𝑠𝑠 + 𝑝𝑝|

where: (i) 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠 ⊂ 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁, 𝑤𝑤𝑖𝑖𝐴𝐴ℎ 𝑐𝑐𝑎𝑎𝑁𝑁𝑠𝑠𝑖𝑖𝑁𝑁𝑎𝑎𝑎𝑎𝑖𝑖𝐴𝐴𝑏𝑏 |𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠| = 𝑠𝑠 , a subset of images selected from the 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁 ⊂ 𝐶𝐶 that contains the image password objects selected by the user at registration; and (ii) 𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠 = 𝐶𝐶 ∖ 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁, 𝑤𝑤𝑖𝑖𝐴𝐴ℎ 𝑐𝑐𝑎𝑎𝑁𝑁𝑠𝑠𝑖𝑖𝑁𝑁𝑎𝑎𝑎𝑎𝑖𝑖𝐴𝐴𝑏𝑏 |𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑎𝑎𝑚𝑚𝑎𝑎𝑁𝑁𝑠𝑠| = 𝑝𝑝, , where the relative complement of 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁 in 𝐶𝐶 is the set of elements in 𝐶𝐶 , but not in 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁: 𝐶𝐶 ∖ 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁 = {𝑁𝑁 ∈ 𝐶𝐶 ┤|𝑁𝑁 ∉ 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑠𝑠𝑁𝑁𝑠𝑠𝐴𝐴𝑁𝑁𝑁𝑁𝑐𝑐𝑁𝑁}. The security strength of the challenge depends on the values of p and q, and on the mode in which the user is asked to recognize the secret images. In the combination mode images are recognized in any order: 𝑁𝑁!/(𝑁𝑁 -𝑠𝑠)! (𝑠𝑠)!. In permutation mode images are recognized according to the sequence registered: 𝑁𝑁!/((𝑁𝑁 -𝑠𝑠)!). In both cases, 𝑁𝑁 = 𝑠𝑠 + 𝑝𝑝. Fig. 2(b) illustrates, in logarithmic scale, the speed at which the number of possible combinations (and therefore the security strength) for a challenge with 𝑠𝑠 = 5 increases for different values of p (1 < 𝑝𝑝 < 35) for the permutation and combination modes. As illustrated, permutation mode provides higher security over combination mode. However, such increase in security is inversely proportional to usability since it is easier for the user to recognize the 5 secret images without having to recall the exact sequence. Table 1 compares the modes for different p and q.

Security strength of the challenge and usability.

Table 1. Comparison combination vs. permutation for different 𝑝𝑝 and 𝑠𝑠

Rules-based challenge generation, usability vs security assurance.

A challenge is generated at runtime taking into account: client device constraints, contextual factors and risk associated, the level of authentication assurance required, and usability.

Client device constraints.

A client device constraint is defined as a tuple (𝑠𝑠𝑁𝑁𝑑𝑑𝑖𝑖𝑐𝑐𝑁𝑁_𝑖𝑖𝑠𝑠, 𝑝𝑝𝑎𝑎𝑁𝑁𝑎𝑎𝑚𝑚𝑁𝑁𝐴𝐴𝑁𝑁𝑁𝑁, 𝑝𝑝) where p (see Table 1) is an estimate of the size of the challenge. For instance, a laptop has a larger screen than a smartphone and can display a challenge with a larger number of image objects 𝑁𝑁 = 𝑠𝑠 + 𝑝𝑝, 1. (𝑠𝑠𝑚𝑚𝑎𝑎𝑁𝑁𝐴𝐴𝑝𝑝ℎ𝑁𝑁𝑁𝑁𝑁𝑁 𝑛𝑛𝑎𝑎𝑎𝑎 , 𝑠𝑠𝑐𝑐𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑠𝑠𝑖𝑖𝑠𝑠𝑛𝑛 = 5 inch, 20)

Contextual rules. This refers to contextual factors that carry a level of risk. A contextual rule is defined as a tuple �𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑁𝑁𝑐𝑐𝐴𝐴 𝑝𝑝𝑛𝑛𝑝𝑝𝑛𝑛𝑛𝑛𝑛𝑛𝑝𝑝𝑛𝑛𝑝𝑝 1 , … , 𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑁𝑁𝑐𝑐𝐴𝐴 𝑝𝑝𝑛𝑛𝑝𝑝𝑛𝑛𝑛𝑛𝑛𝑛𝑝𝑝𝑛𝑛𝑝𝑝 𝑥𝑥 , 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 � where 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 is a value between 0 and 1. For example, consider an employee authenticating to a corporate server and the following contextual rules:

2. (𝑎𝑎𝑁𝑁𝑐𝑐𝑎𝑎𝐴𝐴𝑖𝑖𝑁𝑁𝑁𝑁 = 𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻, 𝐴𝐴𝑖𝑖𝑚𝑚𝑁𝑁 = 𝐴𝐴𝑁𝑁𝐴𝐴, 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 𝐻𝐻𝐻𝐻𝑃𝑃𝑎𝑎𝑀𝑀𝐻𝐻 = 0.5)

In the proposed system, the level of risk defines the strength of the challengechallenge rules; and the number of authentication factors required -authentication factor rules.

Challenge rules.

A challenge rule is defined as a tuple (𝑠𝑠, 𝑝𝑝, 𝑐𝑐ℎ𝑎𝑎𝑎𝑎𝑎𝑎𝑁𝑁𝑁𝑁𝑎𝑎𝑁𝑁 𝑛𝑛𝑚𝑚𝑠𝑠𝑛𝑛 , 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 ). where 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 is a value between 0 and 1 For example consider the following rules for 𝑝𝑝 = 20 (see Table 1 Notice that rules 4 and 5 are given the same 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 . This is because the number of possible combinations and permutations for these two rules are of similar order of magnitude, 230230 and 255024(see Table 1).

Authentication factor rules. An authentication factor rule is defined as a tuple �𝑁𝑁𝐴𝐴𝑚𝑚𝑏𝑏𝑁𝑁𝑁𝑁 𝑛𝑛𝑎𝑎𝑝𝑝ℎ𝑛𝑛𝑛𝑛𝑝𝑝𝑖𝑖𝑎𝑎𝑛𝑛𝑝𝑝𝑖𝑖𝑚𝑚𝑛𝑛 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 , 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 � and indicates the number of authentication factors required given some risk level. For instance:

6. �𝑎𝑎𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝐴𝐴𝑖𝑖𝑐𝑐𝑎𝑎𝐴𝐴𝑖𝑖𝑁𝑁𝑁𝑁 𝑓𝑓𝑛𝑛𝑎𝑎𝑝𝑝𝑚𝑚𝑝𝑝𝑠𝑠 = 1, 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 𝐿𝐿𝐻𝐻𝐿𝐿 = 0.2� 7. �𝑎𝑎𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝐴𝐴𝑖𝑖𝑐𝑐𝑎𝑎𝐴𝐴𝑖𝑖𝑁𝑁𝑁𝑁 𝑓𝑓𝑛𝑛𝑎𝑎𝑝𝑝𝑚𝑚𝑝𝑝𝑠𝑠 = 2, 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 𝐻𝐻𝐻𝐻𝑃𝑃𝑎𝑎𝑀𝑀𝐻𝐻 = 0.5�

Example. Assume rules (1) and (2) are applicable. In such case, then rules (4) and (5) would hold true, i.e. p=20 and 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 ≥ 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 . And between (4) and ( 5), (4) would be the optimal choice since it mitigates the present level of risk and provides the best option in terms of usability, i.e. unordered recognition mode. Rule (4) enforces p=20 and q=6 to generate the challenge. Similarly, rule (7) would hold true, i.e. 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 ≥ 𝑁𝑁𝑖𝑖𝑠𝑠𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 , and enforces the use of at least two authentication factors, i.e. the challenge itself, and an additional factor, e.g. IMSI.

4.2

User response to the challenge.

The user responds to the challenge by selecting the secret images. The algorithm then retrieves the secret images' seeds and performs an XOR operation over them whose result is a pin of 4 hexadecimal digits (ℎ𝑁𝑁𝑐𝑐 𝑖𝑖 ) in length: 𝑀𝑀𝑠𝑠𝑁𝑁𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 = 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 1 ′ ⊕ 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 2 ′ ⊕ 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 3 ′ ⊕ … ⊕ 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 |𝑠𝑠𝑛𝑛𝑎𝑎𝑝𝑝𝑛𝑛𝑝𝑝𝑠𝑠𝑛𝑛𝑛𝑛𝑠𝑠𝑛𝑛𝑠𝑠| = ℎ𝑁𝑁𝑐𝑐 1 ℎ𝑁𝑁𝑐𝑐 2 ℎ𝑁𝑁𝑐𝑐 3 ℎ𝑁𝑁𝑐𝑐 4 , where each element 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 ′ corresponds to an element 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 ∈ 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠𝑠𝑠𝑁𝑁𝑁𝑁𝑐𝑐𝐴𝐴𝑁𝑁𝑁𝑁 (i.e. 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 ′ 𝑓𝑓 → 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑖𝑖 ). The value 𝑀𝑀𝑠𝑠𝑁𝑁𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 along with the value 𝑅𝑅𝑃𝑃𝑠𝑠 are taken as input parameters to the cryptographic transformation that calculates the dynamic pin.

4.3

Computation of the cryptographic transformation function.

A Substitution Box (S-Box) is a component used in cryptosystems to perform substitutions in a way that relations between output and input bits are highly non-linear. This protects against cryptanalysis. An S-Box designed to be resistant to linear and differential cryptanalysis is the Rijndael S-Box [START_REF] Daemen | AES Proposal: Rijndael[END_REF]. The design was made balancing security and computational efficiency. The security strength of crypto-algorithms based on S-Boxes can be improved by changing the S-Box dynamically (e.g. Blowfish). This makes more difficult to carry out an attacks without knowing what S-Box to associate to a given output. To increase the pseudo-randomness of the dynamic PIN, it is proposed to use an S-Box that can be obtained dynamically, complies with strong security design criteria and crypto-properties, and that can be generated using a deterministic technique based on parameters known to both client and server. Barkan et al. [START_REF] Barkan | In How Many Ways Can You Write Rijndael?[END_REF] show that by replacing the irreducible polynomial and the affine transformation in the Rijndael S-Box it is possible to produce dual ciphers with the same cryptographic properties of the original S-Box. This result is used here to propose an indexing technique that allows selecting different dual ciphers, i.e. S-Boxes. In the next subsections the mathematical definitions that support the formulation of the indexing technique are presented along with the proposed indexing function(s).

Rijndael S-box [START_REF] Daemen | AES Proposal: Rijndael[END_REF]. The Rijndael S-box is an algebraic operation that takes in an element of the Galois Field 𝐺𝐺𝑃𝑃(2 8 ) and outputs another element of 𝐺𝐺𝑃𝑃(2 8 ) , where 𝐺𝐺𝑃𝑃(2 8 ) is viewed as the finite field

𝐺𝐺𝐺𝐺(2)[𝑋𝑋] (𝑋𝑋 8 +𝑋𝑋 4 +𝑋𝑋 3 +𝑋𝑋+1)
of polynomials over the finite field 𝐺𝐺𝑃𝑃(2) reduced modulo by the polynomial 𝑋𝑋 8 +𝑋𝑋 4 + 𝑋𝑋 3 + 𝑋𝑋 + 1. The operation has 2 steps: (i) find the multiplicative inverse of the input over 𝐺𝐺𝑃𝑃 (2 8 ) (0 is sent to 0); and (ii) apply the affine transformation 𝐴𝐴𝑐𝑐 + 𝑏𝑏 where 𝑐𝑐 is the result of the first step, (in Rijndael) 𝐴𝐴 is a specific 8 × 8 matrix with entries in 𝐺𝐺𝑃𝑃(2) and 𝑏𝑏 is a specific vector with 8 entries in 𝐺𝐺𝑃𝑃(2), both specifically chosen to make it resistant to linear and differential cryptanalysis. Elements in 𝐺𝐺𝑃𝑃(2 8 ) are represented as bytes and transformations can be pre-computed and represented as a lookup matrix.

Dual Ciphers [START_REF] Barkan | In How Many Ways Can You Write Rijndael?[END_REF]. Two ciphers 𝐻𝐻 and 𝐻𝐻′ are called Dual Ciphers if they are isomorphic, that is to say there exists three invertible transformations 𝑓𝑓, 𝑎𝑎, ℎ such that 𝐻𝐻 𝐾𝐾 (𝑃𝑃) = 𝑓𝑓(𝐻𝐻 ′ 𝑠𝑠(𝐾𝐾) �ℎ(𝑃𝑃)�) ∀𝑃𝑃, 𝑃𝑃, where P is the plain text and K is the key. Different cipher can be created from an original cipher while keeping the original's algebraic properties because of the isomorphism. [START_REF] Barkan | In How Many Ways Can You Write Rijndael?[END_REF]. If the constants of the Rijndael Sbox (denote the Rijndael S-box 𝐻𝐻) are replaced such that: (i) it is replaced 𝐴𝐴 with 𝐴𝐴 2 where 𝐴𝐴 2 is not simply the square of the matrix, it is equal to 𝑄𝑄𝐴𝐴𝑄𝑄 -1 where Q is an 8 × 8 matrix chosen such that 𝑄𝑄𝑐𝑐 = 𝑐𝑐 2 for all 𝑐𝑐. As a side result this also means that 𝑄𝑄𝐴𝐴𝑄𝑄 -1 𝑐𝑐 = (𝐴𝐴𝑐𝑐) 2 ; and (ii) 𝑏𝑏 is replaced with 𝑏𝑏 2 . Hence it can be shown that these transformations result in a dual cipher (let it be denoted 𝐻𝐻 2 ). It can be seen that 𝐴𝐴 2 𝑐𝑐 + 𝑏𝑏 2 = 𝑄𝑄𝐴𝐴𝑄𝑄 -1 𝑐𝑐 + 𝑄𝑄𝑏𝑏 = 𝑄𝑄(𝐴𝐴(𝑄𝑄 -1 𝑐𝑐) + 𝑏𝑏) . Hence making these transformations (and creating the square dual cipher) is equivalent to applying a pre and post matrix multiplication on the original Rijndael S-box. This same transformation can be applied to 𝐻𝐻 2 to obtain 𝐻𝐻 4 and similarly for 𝐻𝐻 8 , 𝐻𝐻 16 , 𝐻𝐻 32 , 𝐻𝐻 64 and 𝐻𝐻 128 (𝐻𝐻 256 = 𝐻𝐻). [START_REF] Barkan | In How Many Ways Can You Write Rijndael?[END_REF]. Recall that the first operation of the Rijndael S-box is to find the multiplicative inverse of the input over 𝐺𝐺𝑃𝑃 (2 8 ). There are a total of 30 irreducible polynomials of degree 8, of which the Rijndael selected 𝑋𝑋 8 +𝑋𝑋 4 + 𝑋𝑋 3 + 𝑋𝑋 + 1 . As different fields 𝐺𝐺𝑃𝑃 [START_REF] Catuogno | A Graphical PIN Authentication Mechanism with Applications to Smart Cards and Low-Cost Devices[END_REF][𝑋𝑋]/𝑓𝑓(𝑋𝑋) for different irreducible polynomials 𝑓𝑓(𝑋𝑋) of the same degree are isomorphic, there exist a linear transformation which can be represented as a binary matrix 𝑅𝑅 such that 𝑅𝑅 takes an element of the Rijndael case and outputs an element of the new case with the changed polynomial. The matrix 𝑅𝑅 is of the form 𝑅𝑅 = (1, 𝑎𝑎 , 𝑎𝑎 2 , 𝑎𝑎 3 , 𝑎𝑎 4 , 𝑎𝑎 5 , 𝑎𝑎 6 , 𝑎𝑎 7 ) where 𝑎𝑎 𝑖𝑖 ′𝑠𝑠 are computed modulo the new irreducible polynomial. Hence 𝑅𝑅 can be used in the same way as 𝑄𝑄 was used in the previous: applying a pre and post matrix multiplication on the original Rijndael S-box 𝑅𝑅(𝑠𝑠(𝑅𝑅 -1 𝑐𝑐)). As there are 30 irreducible polynomials, each of which has the 8 squared ciphers this totals 8 × 30 = 240 different dual ciphers. In the book of Rijndaels [START_REF] Barkan | The book of Rijndaels[END_REF] the 240 dual ciphers of Rijndael are presented including the matrices 𝑅𝑅𝑠𝑠 and the 𝑅𝑅 -1 𝑠𝑠. Here they are used in the following way on the original Rijndael S-box to create a new S-box: 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋) = 𝑅𝑅 × 𝑠𝑠𝑅𝑅𝑖𝑖𝑅𝑅𝑁𝑁𝑠𝑠𝑎𝑎𝑁𝑁𝑎𝑎(𝑅𝑅 -1 × 𝑋𝑋), with 𝑠𝑠𝑅𝑅𝑖𝑖𝑅𝑅𝑁𝑁𝑠𝑠𝑎𝑎𝑁𝑁𝑎𝑎 the original Rijndael S-Box matrix.

Square Dual Cipher of the Rijndael S-box

Modifying the polynomial of the Rijndael S-box

Indexing the dual ciphers of the Rijndael S-box. In the proposed scheme, an indexing technique is used for the 240 distinct dual ciphers of Rijndael (in [START_REF] Raddum | More Dual Rijndaels[END_REF] the number of possible dual ciphers has been extended to 9120). An indexing function is defined, i. In permutation mode each 𝑠𝑠𝑁𝑁𝑁𝑁𝑠𝑠 𝑘𝑘 is multiplied by the index 𝑁𝑁 forcing the result to depend on order. Both variants of 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑛𝑛𝑛𝑛𝑛𝑛 output an integer between 0 and 239 that is used to select (𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑐𝑐𝑐𝑐𝑛𝑛 , 𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑐𝑐𝑐𝑐𝑛𝑛 -1

) ∈ 𝑃𝑃𝐴𝐴𝑎𝑎𝑎𝑎𝐶𝐶𝑖𝑖𝑝𝑝ℎ𝑁𝑁𝑁𝑁𝐻𝐻𝑎𝑎𝐴𝐴𝑁𝑁𝑖𝑖𝑐𝑐𝑁𝑁𝑠𝑠, and to determine the new S-Box transformation: 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋) = 𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑐𝑐𝑐𝑐𝑛𝑛 × 𝑠𝑠𝑅𝑅𝑖𝑖𝑅𝑅𝑁𝑁𝑠𝑠𝑎𝑎𝑁𝑁𝑎𝑎(𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑐𝑐𝑐𝑐𝑛𝑛 -1 × 𝑋𝑋). 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋) takes as input a byte and outputs another byte.

4.4

Generation of Dynamic PIN (𝑫𝑫𝑫𝑫𝑫𝑫𝑫𝑫𝑫𝑫𝑫𝑫).

The dynamic pin, 𝑃𝑃𝑏𝑏𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁, is generated by performing iterative substitutions through the transformation function, 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋), using the values 𝑀𝑀𝑠𝑠𝑁𝑁𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 and 𝑅𝑅𝑃𝑃𝑠𝑠.

Recall that 𝑀𝑀𝑠𝑠𝑁𝑁𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 = ℎ𝑁𝑁𝑐𝑐 1 ℎ𝑁𝑁𝑐𝑐 2 ℎ𝑁𝑁𝑐𝑐 3 ℎ𝑁𝑁𝑐𝑐 4 , where0 ≪ ℎ𝑁𝑁𝑐𝑐 𝑖𝑖 ≪ 𝑃𝑃, is 2 bytes long, that is, each hexadecimal digit ℎ𝑁𝑁𝑐𝑐 𝑖𝑖 is a nibble (half byte), and that 𝑅𝑅𝑃𝑃𝑠𝑠 = 𝑅𝑅𝑃𝑃𝑃𝑃 1 𝑅𝑅𝑃𝑃𝑃𝑃 2 𝑅𝑅𝑃𝑃𝑃𝑃 3 … 𝑅𝑅𝑃𝑃𝑃𝑃 159 , is 160 bytes long. Each byte 𝑅𝑅𝑃𝑃𝑃𝑃 𝑖𝑖 is composed by a more significant and a less significant part, 𝑁𝑁𝑖𝑖𝑏𝑏𝑏𝑏𝑎𝑎𝑁𝑁 𝑅𝑅𝑃𝑃𝑃𝑃 𝑖𝑖 𝐻𝐻 𝑎𝑎𝑁𝑁𝑠𝑠 𝑁𝑁𝑖𝑖𝑏𝑏𝑏𝑏𝑎𝑎𝑁𝑁 𝑅𝑅𝑃𝑃𝑃𝑃 𝑖𝑖 𝐿𝐿 . The dynamic pin is defined 𝑃𝑃𝑏𝑏𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 = 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 1 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 2 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 3 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 4 .

Each 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 𝑖𝑖 digit is computed as the result of a chain of 7 substitutions between 𝑀𝑀𝑠𝑠𝑁𝑁𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 (2 bytes long) and 2 bytes of 𝑅𝑅𝑃𝑃𝑠𝑠 , and 7 iterations through the s-box 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋).

Conclusions and Future Work

This paper presented a context-based multi-factor authentication system based on a dynamic PIN. A novel crypto-function has been proposed that changes dynamically based on the user input, history of authentications, and authentication factors at the client device. The dynamic aspect of the crypto-function increases the pseudorandomness of the scheme and provides strong protection against cryptanalysis. The scheme generates a challenge based on context, takes into account risk and tunes assurance vs. usability criteria. In addition to the standard client-server workflow scenario, the proposed scheme has been implemented as a software security token that displays the Dynamic PIN and the user types it on a web interface. The synchronization between client and server via the web interface uses QR-Codes and the client device's camera. The prototype is being validated.

Fig. 1 (

 1 a) shows an example of a challenge represented as a grid of icons where 𝑠𝑠 = 5, 𝑝𝑝 = 20, and 𝑁𝑁 = 25 (the greyed images represent the secret).

Fig. 1 .

 1 Fig. 1. (a) Example of an image challenge, (b) Combination vs. Permutation Functions

): 3 .

 3 [START_REF] Jakobsson | Implicit authentication for mobile devices[END_REF] 20, 𝑚𝑚𝑁𝑁𝑠𝑠𝑁𝑁 = 𝐴𝐴𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠, 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 0.3) 4. (6, 20, 𝑚𝑚𝑁𝑁𝑠𝑠𝑁𝑁 = 𝐴𝐴𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠, 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 0.5) 5. (4, 20, 𝑚𝑚𝑁𝑁𝑠𝑠𝑁𝑁 = 𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠, 𝑎𝑎𝑠𝑠𝑠𝑠𝐴𝐴𝑁𝑁𝑎𝑎𝑁𝑁𝑐𝑐𝑁𝑁 𝑎𝑎𝑛𝑛𝑣𝑣𝑛𝑛𝑎𝑎 = 0.5)

))

  e. 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑛𝑛𝑛𝑛𝑛𝑛 , to determine what dual cipher, out of the 240, to use to generate a new S-Box, i.e. 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 (𝑋𝑋) . 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑛𝑛𝑛𝑛𝑛𝑛 takes as input authentication tokens 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑖𝑖 , the seeds associated to 𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠 and 𝑁𝑁𝑁𝑁𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐𝑁𝑁𝑁𝑁𝐴𝐴𝑎𝑎𝑚𝑚𝑎𝑎𝑎𝑎𝑁𝑁𝑠𝑠, and the index value of the last successful authentication. The proposed indexing function has two variants dependent recognition mode: permutation or combination.Let 𝑃𝑃𝐴𝐴𝑎𝑎𝑎𝑎𝐶𝐶𝑖𝑖𝑝𝑝ℎ𝑁𝑁𝑁𝑁𝐻𝐻𝑎𝑎𝐴𝐴𝑁𝑁𝑖𝑖𝑐𝑐𝑁𝑁𝑠𝑠 = �(𝑅𝑅 1 , 𝑅𝑅 1 -1 ), (𝑅𝑅 2 , 𝑅𝑅 2 -1 ), … , (𝑅𝑅 240 , 𝑅𝑅 240 -1 )� be the vector of Dual Ciphers' matrices (𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 , 𝑅𝑅 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 -1 ) where 0 ≤ 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 < 240. The two indexing function are defined as follows: (combination mode) 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑛𝑛𝑛𝑛𝑛𝑛 = (𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑎𝑎𝑎𝑎𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛𝑝𝑝 + 𝑚𝑚𝑁𝑁𝑠𝑠 240 ; and (permutation mode) 𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑛𝑛𝑛𝑛𝑛𝑛 = (𝑖𝑖𝑁𝑁𝑠𝑠𝑁𝑁𝑐𝑐 𝑎𝑎𝑎𝑎𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛𝑝𝑝 + ∑ 𝐴𝐴𝐴𝐴𝐴𝐴ℎ𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑖𝑖 𝑎𝑎 𝑖𝑖=1 𝑚𝑚𝑁𝑁𝑠𝑠 240, with 𝐴𝐴 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑓𝑓𝑐𝑐𝑓𝑓𝑓𝑓𝑐𝑐𝑐𝑐𝑓𝑓 < 𝐴𝐴 𝑖𝑖𝑛𝑛𝑠𝑠𝑛𝑛𝑖𝑖 𝑐𝑐𝑐𝑐𝑛𝑛 , 𝑤𝑤𝑖𝑖𝐴𝐴ℎ 𝐴𝐴𝑖𝑖𝑚𝑚𝑁𝑁 𝐴𝐴.

Fig. 2 Fig. 2 .

 22 Fig. 2. Chain of substitutions and S-Box iterations to generate 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 1 of 𝑃𝑃𝑏𝑏𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁The same process is repeated for the other digits, 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 2 , 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 3 , 𝑎𝑎𝑁𝑁𝑠𝑠 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 4 , but using a different starting byte of 𝑅𝑅𝑃𝑃𝑠𝑠 for each digit. To achieve this, the RPS is split into 4 quarters (each one 40 bytes long), and the previous digit ( 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 𝑖𝑖-1 ) of 𝑃𝑃𝑏𝑏𝑁𝑁𝑃𝑃𝑎𝑎𝑁𝑁 viewed as an integer, 0 to 255, and reduced modulo 40, is used to determine a starting byte in 𝑅𝑅𝑃𝑃𝑠𝑠 . The starting byte in 𝑅𝑅𝑃𝑃𝑠𝑠 for 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 𝑖𝑖 is calculated as follows: 𝑍𝑍 = (40 * 𝑅𝑅) + 𝐴𝐴, where 𝐴𝐴 = |(𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 𝑖𝑖-1 ) 10 | 40 . Z is the starting byte in the RPS used to calculate 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 2 (𝑅𝑅 = 1), 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 3 (𝑅𝑅 = 2), 𝑎𝑎𝑁𝑁𝑠𝑠 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 4 (𝑅𝑅 = 3) . Thus the starting byte in the RPS is randomized within each quarter block of the RPS. Once all the digits are computed, the dynamic pin is sent to the server for validation. The server executes the same algorithm and verifies the dynamic pin sent by the user.

𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �ℎ𝑁𝑁𝑐𝑐 1 ,

 1 𝑅𝑅𝑃𝑃𝑃𝑃 0 𝐻𝐻 � = 𝑠𝑠 1 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 1 𝐻𝐻 , 𝑅𝑅𝑃𝑃𝑃𝑃 0 𝐿𝐿 � = 𝑠𝑠 2 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 2 𝐿𝐿 , ℎ𝑁𝑁𝑐𝑐 2 � = 𝑠𝑠 3 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 3 𝐻𝐻 , ℎ𝑁𝑁𝑐𝑐 3 � = 𝑠𝑠 4 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 4 𝐿𝐿 , 𝑅𝑅𝑃𝑃𝑃𝑃 1 𝐻𝐻 � = 𝑠𝑠 5 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 5 𝐻𝐻 , 𝑅𝑅𝑃𝑃𝑃𝑃 1 𝐿𝐿 � = 𝑠𝑠 6 𝑠𝑠 𝑛𝑛𝑛𝑛𝑛𝑛 �𝑠𝑠 6 𝐿𝐿 , ℎ𝑁𝑁𝑐𝑐 4 � = 𝑠𝑠 7 = 𝑏𝑏𝑏𝑏𝐴𝐴𝑁𝑁 1

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011