Nicola Gobbo
email: gobbonic@dei.unipd.it

Alessio Merlo
email: alessio.merlo@uniecampus.it

Mauro Migliardi
email: mauro.migliardi@unipd.it

A Denial of Service attack to GSM networks via Attach Procedure

Keywords: Mobile Security, GSM, cellular networks security, DoS attack

Mobile Network Operators (MNOs) keep a strict control over users accessing the networks by means of the Subscribe Identity Module (SIM). This module grants the user to access the network, by performing the registration and authentication of the user's device. Without a valid SIM module and a successful authentication, mobile devices are not granted access and, hence, they are not allowed to inject any traffic in the mobile infrastructure. Nevertheless, in this paper we describe an attack to the security of a mobile network allowing an unauthenticated malicious mobile device to inject traffic in the mobile operator's infrastructure. We show that even with devices without any SIM module it is possible to inject high levels of signaling traffic in the mobile infrastructure, causing significant service degradation up to a full-fledged Denial of Service (DoS) attack.

Introduction

Mobile phones are one of the most pervasively deployed technology in the world and cellular networks have reached worldwide coverage. On one hand, the evolution from early analog networks to recent 4G LTE solutions has allowed operators to offer new services to their customers. On the other hand, the same evolution has pushed new needs into the customers; such needs have evolved from simple phone calls and SMS to internet connections and high speed access to streaming data.

The availability of smartphones with wide touch-screen displays as well as the always-on, high bandwidth IP connectivity have generated a growing set of services and applications ranging from e-mail to remote banking, from e-shopping to music streaming, from video on demand to social geo-localized networks. In turn, the ease of use and the availability of a rich a set of functionalities have instilled into users a growing familiarity and a sense of dependency. This dependency does not exist only for leisurable activities, but has a definite onset also in business and critical tasks. In particular, the last year has seen a significant penetration in govern agencies and public bodies. To this aim, we can cite the recent security certification of Android smartphones by the US Department of Defense [START_REF]Security Technical implementation Guide[END_REF] that allows the deployment of Dell hardware with Froyo (Android OS v2.2) in the Pentagon. A second example is the adoption of tablet PCs (Apple iPad) by the Chicago hospital and the Loyola University Medical Center in Maywood. Finally, several research projects are focusing on the deployment of health-care services onto the tablet PC platform with widely goals from simple access to medical records [START_REF] Doukas | Mobile healthcare information management utilizing cloud computing and android os[END_REF], to reminders for medication intake [START_REF] Wang | Wedjat: a mobile phone based medicine intake reminder and monitor[END_REF], to decision support systems [START_REF] Kuntagod | Mobile decision support system for outreach health worker[END_REF], to automatic recognition of pathological states [START_REF] Tacconi | Smartphone-based applications for investigating falls and mobility[END_REF], to systems for memory support [START_REF] Migliardi | Memory Support through Pervasive and Mobile Systems[END_REF]. For these reasons, mobile networks security analysis should emphasize availability along with confidentiality and integrity.

However, the introduction of new technologies cannot be decoupled from the support to legacy ones, since i) a high number of older terminals are still active, and ii) some manufactures keep producing 2G-only phones to satisfy low-end market. For these reasons, each new radio access technology has to be deployed alongside existing ones, leading to hybrid architectures where some network components are shared among different technological infrastructures. This condition is driving operators toward single Radio Access Network solutions, causing a cellular site to broadcast signals related to up to 3 different technologies in 5 different frequency bands. Such a composite network architecture co-exists with a design traditionally focused on making mobile networks smarter and smarter, while keeping devices crowding their cells as "dumb" as possible [START_REF] Guo | Smart-phone attacks and defenses[END_REF][START_REF] Traynor | On attack causality in internetconnected cellular networks[END_REF]. Today's smartphones are far more intelligent and powerful than their predecessors. However, networks still don't profit from their enhanced processing power; on the contrary they assume the lowest possible capability in order to maintain compatibility with older devices. This assumption results in higher signaling traffic levels between network nodes3 and more complex system management.

The complexity of the network structure may hide both unknown and known vulnerabilities. For an interesting survey on threats undermining the world of mobile telecommunication, the reader can refer to [START_REF] Castiglione | Do You Trust Your Phone?[END_REF]. For the case of known vulnerabilities, the true impact on the mobile phone network may have not been sufficiently assessed in a way that is similar to what happens in mobile OSes [START_REF] Armando | Would you mind forking this process? A Denial of Service attack on Android (and some countermeasures)[END_REF]. To this aim, in this paper we extend the work by Khan et al. [START_REF] Khan | Vulnerabilities of umts access domain security architecture[END_REF] focusing on the attach phase of GSM protocol and we show that it is possible to mount a complete attack even without hijacking or controlling a large number of user IDs recognized by the network. To achieve our goal, we study the amount of signalling traffic that a dedicated SIM-less device can inject into an operator's core network, by pushing air interface to its design limit. Such activity may obviously disable the signalling capabilities of the cells under attack, causing a local Denial of Service (DoS) similar to the one that can be achieved with a radio jammer; however, to reach a very critical level of disruption, the generated traffic may be targeted at the Home Location Register (HLR), i.e. the database containing information on mobile subscribers. Since this database is a critical component of the core network, an outage of its functionality may cause an interruption of other mobile services too, finally resulting in a mobile network DoS. In our study, we leverage the HLR performance measurement conducted by Traynor et al. [START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF], showing that it is possible to mount an attack without any SIM module.

The remainder of this paper is structured as follow: in Section 2 we provide a description of the architecture of GSM networks; in Section 3 we analyze the state of the art in the field and we discuss the results obtained in previous related works; in section 4 we describe how it is possible to launch a DoS attack with a number of SIMless devices; finally, in section 5, we provide some concluding remarks and we describe the future direction of our study.

GSM network description

Global System for Mobile Communications (GSM) standard (2G) was initially designed to carry efficiently circuit switched voice communications in full duplex, with a main advantage over previous analog generation: all the processing happens in the digital domain. The standard protocol set expanded over time with addictions that, from Mobile Network Operators (MNOs) point of view, require just a software upgrade on already deployed hardware; consumers, instead, need modern and more powerful devices to experiment newly offered services. The first addiction to GSM has been General Packet Radio Service (GPRS) that introduced data delivery alongside of voice communications, in both circuit switched and -the more efficient-packet switched mode. Apart from calls GPRS permits data connection throughputs roughly ranging in the 9-170kbps interval; augmenting this modest numbers has been the main target of the second GSM enhancement: Enhanced Data Rates for GSM Evolution (EDGE). EDGE is a backward-compatible extension to GSM/GPRS network that introduce new coding and transmission techniques thus allowing for data rates up to 470kbps.

A typical GSM Public Land Mobile Network (PLMN) consists at least of the infrastructures depicted in figure 1. It is mainly split up in three different portions: i) the Mobile Station (MS) or User Equipment (UE), ii) the GSM/EDGE Radio Access Network (GERAN), iii) the Core Network (CN) or Network Switching Subsystem (NSS) with fully separated packet and circuit switched domains.

The MS may be a mobile phone or a mobile broadband modem with appropriate protocol stack and capabilities as defined by specifications. Nonetheless whichever device is used to connect to the network, there will be a Subscribe Identity Module (SIM) in it. SIMs are smart cards usually referred to as the furthest extension of mobile operator's network; it securely stores user identity, represented by the International Mobile Subscriber Identity (IMSI), and its related secret key, as long as the algorithms needed during the Authentication and Key Agreement (AKA) phase.

MSs communicate over air interface with the Base Transceiver Station (BTS). This is the first element composing the Radio Access Network (RAN), in GSM it has minimum functionality in the sense that it just consists of a transceiver that controls the physical layer transmission. A typical GSM BTS serves three 120°sectors -also called cells-by means of one or more antennas per sector; antennas are powered by amplifiers that gets their pilot signals from one or more baseband modules which are finally connected to the transceiver. BTS are grouped together in tens or hundreds and connected with Base Station Controllers (BSCs), which are the devices accounting for radio resource management, MSs mobility management functions and encryption of user data prior to transmission over the air interface.

Each BSC has a couple of connections toward the core network: one linking the Serving GPRS Support Node (SGSN) carrying packet switched data, the other linking the Mobile Switching Center (MSC) and transporting circuit switched informations. This division is due to the fact that the data delivery capability of the GPRS has been a posthumous addendum to the NSS, so it has been designed for deployment in environments where GSM core networks have been already running. Both SGSN and MSC act as switching and end point for end-to-end connections in their own domains; they manage hand-overs between different BSCs as well as authentication checking and charging functions. The most valuable operation of these equipments, however, is the mobility management: they keep track of MS movements inside their service area and locate it whenever required. To carry out this operation an auxiliary database called Visitor Location Register (VLR) is used: it contains the user identity at the BSC-level along with an indication of its current location and a pointer to the main user record which is contained in another database called Home Location Register (HLR). The HLR maintains a record for each mobile phone subscriber with details like the telephone number, IMSI and a secret key (i.e. the same contained in the SIM), call blocking and forwarding and a pointer to the most updated VLR the user is known to be roaming on. HLR is a core component for the networks because it has to be queried for phone call and SMS delivery, billing procedures and authentication: this latter function is supported by the Authentication Center (AuC) which calculates challenges and responses that are sent to the MSC/SGSN for actual user validation.

Related works

Cellular networks seem unaffected by the same threats that, almost daily, came up in the newspapers regarding other types of widely spread systems like the Internet. Nonetheless, even if a large security outbreak has not already made its way through the news, mobile operators' network security has been studied in the literature for quite a long time. Initially, most of the attention of researchers was focused on confidentiality and integrity [START_REF] Castiglione | SECR3T: Secure End-to-End Communication over 3G Telecommunication Networks[END_REF], [START_REF] Castiglione | Engineering a secure mobile messaging framework[END_REF], [START_REF] De Santis | An Extensible Framework for Efficient Secure SMS[END_REF], [START_REF] Castiglione | SPEECH: Secure Personal End-to-End Communication with Handheld[END_REF] of data travelling over the wireless portion of the system; however, in more recent works, the problem of the actual availability of the services provided by the network, both in the wireless segment and in the core network segment, has gained popularity, becoming the focus of different studies.

The simplest way to prevent a mobile network from offering its services is using a radio jammer. Moving from physical towards upper layers increases both the complexity of the attack and the size of the involved network segment. In order to be able to prove higher layer attacks possible, however, researchers have had to wait for a device with extensible capabilities, a kind of device that made its first market appearance in 2000 but actually had a significant deployment only in 2007: the smartphone 4 . Until late 1990s mobile phones had only basic phone features so the user had complete control over what the terminals were doing. This fact, however, has been subverted by the first iPhone release in 2007 and, more specifically, by the introduction of Apple App Store. The iPhone, in fact, as all the smartphones marketed today, ran an operating system over which a series of applications are executed. The advent of this application-enabled phones and centralized software distribution systems attracted the attention both of attackers 5 and of security researchers. In particular, the research community has proved that the open feature set nature of the smartphone makes it the device capable of massive and distribute mobile network attacks [START_REF] Derr | Nightmares with mobile devices are just around the corner! In: Portable Information Devices[END_REF].

Past Internet security studies prove that in order to mount a DoS attack a botnet is the tool that provides the most suitable characteristics; however, mobile networks have constraints and peculiarities that should be taken into consideration both during the infection phase [START_REF] Fleizach | Can you infect me now?: malware propagation in mobile phone networks[END_REF] and in the setup of the command and control mechanism [START_REF] Mulliner | Rise of the iBots: Owning a telco network[END_REF] [START_REF] Castiglione | A botnet-based command and control approach relying on swarm intelligence[END_REF]. An attacker capable of controlling a botnet can use infected devices for multiple purposes: spam delivery, sending calls or SMS toward premium price services, spoofing user identity and remote wiretapping become all straightforward for an attacker [START_REF] Guo | Smart-phone attacks and defenses[END_REF][START_REF] Felt | A survey of mobile malware in the wild[END_REF]. A malicious entity may also try to kick mobile network elements out of service. As an example, Guo et al. [START_REF] Guo | Smart-phone attacks and defenses[END_REF] predicted that a few dozens of subverted smartphones, served by the same base station, can jeopardize its availability by making no-answer calls and thus saturating provisioned voice channels. If phones are not located in the same place, authors outlined that it is still possible to put call aggregation points to a halt by means of a distributed denial of service: the number of needed controlled devices is indeed higher than the one needed in the previous case, but, due to the fact that PSTN, cellular switches and call centers are designed for a limited Busy Hour Call Attempts, the attack is still feasible.

Later studies still focusing on DoS attacks show that it is possible to achieve the needed level of service degradation in a more efficient way: instead of consuming traffic (or user-plane) channels, an attacker may try to flood control channels which are usually separated from traffic ones and significantly more limited in terms of available bandwidth. One of the first work in this direction is from Traynor et al. [START_REF] Traynor | Mitigating attacks on open functionality in sms-capable cellular networks[END_REF]. In a strict sense, the attack described here doesn't use a botnet but, in a broader sense, every mobile phone is an accomplice because what it has to do is just receiving incoming requests. They show how the interconnection between the mobile network and the Internet via, for example, on-line SMS delivery capabilities, may be exploited by an attacker continuously sending text messages to an especially crafted hit-list of telephone numbers. Such a data flood, estimated in roughly 580kbps, is enough to keep a control channel shared by voice and SMS busy, thus unavailable to accept or delivery new voice calls. Another study from Traynor et al. [START_REF] Traynor | On attack causality in internetconnected cellular networks[END_REF] focuses on the GPRS network and characterizes two different types of DoS attacks targeting data connection setup and tear-down mechanisms. Tear-down mechanism affects only the data portion of the network trying to keep reserved all Temporary Flow Identifiers (TFIs) that distinguish different data flows. In the setup attack, instead, authors moves the focus from resource exhaustion to control channel depletion, analysing the Random Access Channel (RACH). They find out that, for the Manhattan borough, 3Mbps of malicious traffic cause a data and voice connection blocking probability of 65% and, along with that, they point out that, this time, attacking data realm affects voice realm too, because of the single shared control channel.

A significant advancement in the analysis of mobile network security has been achieved when researchers found a way to attack core network elements, proving that network-wide service deterioration possible. Khan et al. and Kambourakis et al. [START_REF] Khan | Vulnerabilities of umts access domain security architecture[END_REF][START_REF] Kambourakis | Signaling-oriented dos attacks in umts networks[END_REF] examine UMTS security architecture finding some protocols flaws that can be used to delete, modify or replay some unauthenticated or not integrity protected messages. This flaws may permit revealing user identities (IMSI), launching DoS attacks against both user phones and network nodes or impersonating the network acting as a man-in-the-middle. These studies, however, do not detail the amount of resources needed to mount a successful DoS attack. An attempt to evaluate the amount of resources needed can be found in the work by Traynor et al. [START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF]. The first step is a performance characterization of different HLR devices in different network deployments. The authors identify the transaction most suitable to mount an HLR DoS attack, searching for a compromise between resource consumption and execution time. By means of a simulation of the network behaviour they find that about 11750 infected devices submitting an "insert call forwarding" every 4.7 seconds are sufficient to reduce HLR throughput of legitimate traffic by more than 93%.

Concluding this summary of works related to DoS attacks in mobile cellular networks, it is interesting to notice the "big picture" that [START_REF] Guo | Smart-phone attacks and defenses[END_REF] and [START_REF] Traynor | On attack causality in internetconnected cellular networks[END_REF] try to draw. Currently studied mobile network DoS attacks roots their cause in the fact that this networks were designed to manage traffic with highly predictable properties but, once connected to the Internet, such constraints hold no more. The Internet was designed with architectural assumptions that are in complete opposition from the ones adopted for cellular networks; this creates a disparity in the effort spent to set up and tear down a connection, necessarily leading to a bottle neck. Moreover mobile terminals have been traditionally considered dumb because of their limited battery life and computational power: this second assumption, however, holds no more in the smartphone era and its underestimation both increases network design complexity and forces core elements to early commit far more resources than those needed by an unauthenticated device. In the following sections we show how it is possible to leverage these facts to greatly reduce the amount of resources needed to mount a successful DoS attack against cellular networks.

Squeezing radio access protocols

When a mobile phone is switched on, GSM and UMTS protocols define what operations should be performed in order to attach to the network. Despite differences between the two technologies that derive from the fact that they use different radio interfaces -GSM uses TDMA while UMTS uses WCDMA-a high level description of these procedures can be described as follows: i) cell discovery, ii) best server synchronization, iii) attachment request, iv) authentication and key agreement (AKA) and v) temporary identity creation. The peculiarity of this procedure is that it cannot leverage previously accrued knowledge as it must accommodate for new devices of which there is no previous information. Moreover the design described in the introduction, i.e. the model of a smart-network and of dumb terminals, requires the whole procedure to be computationally light for the terminals and to delegate to the network most of the operations and resources. Thus, the terminals do not have to commit significant resources but the network does. These two facts are the basis of the vulnerability to DoS that is present in the attach procedure; in fact, during the AKA step, an unauthenticated device may force the core network to carry on computations that are more resource consuming than the request itself. As described by Khan et al. work [START_REF] Khan | Vulnerabilities of umts access domain security architecture[END_REF], the way an attack could be mounted is straightforward: in a preliminary phase an attacker builds a database of valid IMSIs, then, he floods the network with attach requests each one carrying a different IMSI chosen from said database. The cellular network forwards the requests to HLR/AuC where each IMSI is validated and, being authentic, triggers the calculation of authentication information that are sent to SGSN that, in turn, must submit the challenge back to the mobile station and verify the reply correctness. As the attacker is not in possess of the SIM corresponding to the IMSI used, he doesn't know the correct answer; however, has not need for it, in fact his goal is to exhaust HLR/AuC computing resources thus he is already hitting the target with all the valid attach requests he is injecting. Although authors describe this attack with UMTS architecture in mind, it is important to notice that it can be performed, with minimal changes, both to old GSM [19] and new LTE [1] networks.

Khan work, however, does not provide a value for the HLR/AuC performance, thus it does not provide the number of terminals needed by an attacker in order to considerably degrade HLR services, using the attack described above. A partial analysis of this problem comes from Traynor et al. article [START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF]. In this work they outline an attack targeting HLR, but they adopt a different approach that leverages a botnet of authenticated devices, repeatedly injecting resourcedemanding transactions available only to already attached terminals. In order to find the transaction that best suits their needs, the authors measure the average throughput -in transactions per second (TPS)-of an HLR setup, with respect to different transaction types. Their results are presented in figure 2. They choose the insert call forwarding procedure as the attack vector because it offers the best trade-off between computational load and execution speed. As the next step, authors simulate the effect of injecting attack traffic on an HLR already serving a typical mix of transactions: doing so they found that injecting 2500TPS the HLR capability to handle legitimate requests -under low-traffic assumptions-is reduced by 93%.

From figure 2 it is possible to determine that the get access data procedure is roughly 5 times faster than the insert call forwarding one, so, in order to achieve the same level of service degradation, we assume that the attack traffic must be multiplied by 5. This puts our target to 12500TPS, however, for the attacker this is a worst case scenario: in fact Traynor's tests focus only on the HLR, disregarding the computations at the AuC that is needed to calculate authentication information.

Regular mobile phones are a limiting factor

To launch the attack Traynor needs a smartphone botnet for two reasons: first, clients must be authenticated before submitting an insert call forwarding request; second, this very kind of procedure is a standard one, so it is possible for an application to ask the underlying operating system to begin its execution. In our scenario, instead, regular phones are a limiting factor. First, from a smartphone's OS there's no way to distinguish among the steps of the GSM authentication procedure once it has been started: OSes control the modem component via a Radio Interface Layer6 which converts high level actions such "call number" or "send SMS" into AT commands that the modem logic can understand [START_REF]AT command set for User Equipment (UE)[END_REF]. Both high level actions and AT commands, however, are too abstract for our needs because the only way to force the attach procedure would be switching the radio off and on again. This operation is completely contained inside the GSM protocol stack and operatively hidden inside the baseband module itself, thus the module informs the OS only after the completion or failure of the entire procedure. More in details, in a mobile phone the access to the network can take only one of these three roads: 1) if the device has a valid SIM module, then the attach procedure completes unless there is a failure on the network side; 2) if the device has an invalid SIM module, then it initiate the attach procedure, but the network rejects it without needing a significant amount of resources; 3) if the device has no SIM module at all, then it does not even initiate the attach procedure. The only way to use a standard phone for performing multiple attach procedures is to equip it with a programmable SIM card and instruct the card to return a different IMSI as well as a random challenge response at each invocation. However, in this case too the solution is definitely sub-optimal because of the phone itself. Built-in mobile protocol stack is implemented strictly following 3GPP specifications which, in turn, are full of transmission wait times, exponential backoffs, maximum re-transmission trials and other artifices [START_REF]Physical layer procedures (FDD)[END_REF] designed with the precise purpose to induce a fair use of the network resources. As a proof of this fact Traynor highlights that, during his network behaviour measurements, he was forced to insert a 2s delay between each request: its removal, otherwise, caused extended execution times. The very goal of a DoS attack, on the contrary, is to unfairly squander the network resources in order to prevent legitimate devices to access the service; furthermore we want to reach the limits of the air interface in order to cut down the number of attacking point. For these reasons we claim that the tool best suited to an attacker needs is a dedicated device capable of accessing the network without needing a valid SIM, and without the timing guards and the strict adherence to the protocol that are normally introduced in components aimed at the consumer market.

Analysing the Air Interface

We now analyze the peculiarities of GSM air interface protocol to evaluate its limits in terms of number of attach requests sent to the base station per second. In this process we suppose to be the only device communicating with the target cell; this hypothesis is unrealistic, but is a direct consequence of the unfairness of the attacking device: while legitimate mobile phones would backoff when facing a traffic problem, our device actively works toward the consumption of all the cell's resources. Thus, most of the time a mobile phone tries to get access, it won't be served because of the high number of requests injected by the attacking device, moreover, as soon as a legitimate request completes, the high number of requests injected by the attacking device generates a high probability that the just freed resources will be grabbed by the attacker and made unavailable to legitimate, well behaved devices.

GSM protocol. GSM attach procedure involves only three channels as depicted in figure 3: RACH, AGCH and SDCCH. Channels are logical entities used to carry specific traffic types; they are laid over GSM's frequency and time division multiple access (FDMA / TDMA) texture. For each carrier frequency, the fundamental building block is the TDMA frame that, in turn, is divided into 8 time slots, each during 577µs. Channel are broadcast over the air interface time-multiplexed into the multiframe structure: we focus on control-type multiframes which are dedicated to signalling and are made up of 51 frames, thus are repeating with periodicity 235.38ms. The standard dictates the available configurations for control-type multiframes: they differ for the number of available SDCCHs and, even if combined, it is possible to have at most 12 SDCCHs. [19] In order to evaluate the design limits of the GSM protocol, we need to analyse each channel and to find out which one introduces the maximum bottleneck. The RACH -the Random Access Channel-is the uplink channel used to carry mobile phone's access requests; in normal conditions, it is governed by the slotted ALOHA protocol, so, in order to maximize its performances, protocol developer designed RACH messages to fill just a single timeslot. We specified "normal conditions" because, in our scenario, we don't care about contention that may be caused by other devices, thus, differently from the normal scenario, we do not apply any backoff and we aim directly at the full channel consumption. In such a scenario, a 12 SDCCHs configuration provides 27 RACH access slots each multiframe and this means a capacity of: This result is not fully consistent with the 80TPS calculated by [START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF] for the slotted ALOHA instance: authors assume a multiframe entirely dedicated to RACH slots, but this is not the case when 12 SDCCHs are deployed [19, page 99].

ρ RACH = 27
The Access Grant (AGCH) downlink channel is used to answer incoming random access request; it carries the information needed by the mobile phone to access the dedicated channel used for further communications. Messages over AGCH fills 4 consecutive time slots due to channel coding and interleaving; this scheme allows the BSS to answer up to 3 RACH requests every multiframe7 :

ρ AGCH = 3 235.38ms
≈ 12.7 requests per second (2) which represent a tighter limit than RACH.

The main part of the attach procedure is delivered via Standalone Dedicated Control Channel (SDCCH) that is an bidirectional channel assigned to a mobile terminal and is reserved to it until a special channel release message is issued by the BSC. As we stated above, in our scenario we assume the presence of 12 SDCCHs; determining their occupation time, however, is quite tricky. Traynor et al. [START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF] measured an average time of 3s to perform a complete attach where 0.5s are needed by the core network to contact HLR/AuC, calculate the authentication information and receive data back. We prove that the remaining 2.5s are spent to send messages back and forth between the mobile phone and the BTS. A multiframe can carry just one message for each SDCCH in each direction, but, when the BTS requires information to the mobile phone, the latter one can answer in the same multiframe: in fact the GSM protocol states a displacement between downlink and uplink multiframes that allows the MS to compute its reply. Given these two rules and assuming two multiframes needed for the RACH-AGCH exchange, we may conclude that completing the attach procedure requires 11 multiframes, that is 11 × 235.38ms = 2.6s that is almost exactly the time obtained in Traynor's measurements. Thus we say that, during message exchange between the MS and the BTS, the only wait time is related to the HLR/AuC interrogation; this, in turn, allows us to estimate SDCCH utilization time during our attack. Message exchange will be modified just from authentication response message on, in the way depicted in figure 4. After receiving the authentication request the device answers back with a LAPD m DISC message that request BTS to terminate the multiple frame operation, releasing its Layer 2 connection [START_REF]-Mobile Station -Base Stations System (MS -BSS) interface Data Link (DL) layer specification[END_REF]. We use this procedure instead of replying with a wrong SRES for two reasons: first, it speeds up the SDCCH release cutting the number of needed messages from 10 to 7; second, the authentication request message, containing the challenge, already carries the proof that the HLR/AuC has been consulted. Using the same rule, we now require 6 multiframes, 4 of which are carried over SDCCH, leading to a channel holding time of 4 × 235.38ms + 0.5s = 1.44s, thus a 12 SDCCHs capacity of:

ρ SDCCHs = 12 1.44s ≈ 8.3 requests per second (3)
Comparing each channel capacity and choosing the lower one, we argue that GSM attacking capabilities are limited by the SDCCH channel at a rate of 8TPS. This result tell us that a GSM-only attack can be mounted with 1563 SIMless devices spread over the same number of cells. Furthermore, we have proved that using SIMless devices is not only possible but, compared with the number of devices required for a botnet based attack, allows reducing the amount of resources of an order of magnitude. Finally, it is important to notice that the devices enrolled in a botnet are still positioned by their rightful owners, independently from the attacker will. Thus, it is possible that an unusual clustering of users (e.g. an event in a theatre or a concert) could produce a concentration of devices that saturates the cell signalling bandwidth and prevents some of the botnets node to fulfil their full attacking potential. On the contrary, the device we envision is not owned by an unknowing user, it can be precisely placed by the attacker and even remotely triggered to start the attack. All of these factors represents a significant increase in the dangerousness of the described attack when compared with the ones described in previous works.

Conclusions and future works

Cellular networks are one of the infrastructure designated as critical both in the American and the European vision of the homeland security. This has lead to a large number of studies that have analysed the architecture of the networks to identify and possibly mend vulnerabilities that could be exploited to mount attacks.

Each infrastructure has been deeply analysed and many possible sweet spots for an attack have been neutralized; however, two new factors aggravate the com-plexity in the infrastructure defence. The first of these factors is the appearance of programmable mobile phones; the second aggravating factor is, as it has been already pinpointed in previous works [5] [6] the interplay between different well known components: in this case coexisting different generations of networks. In past works several ways to mount DoS attack leveraging the programmability of modern smartphones have been described, however, these works described methodologies that needed hijacking more than 10.000 smartphones with valid SIM modules in order to mount a successful attack.

In this paper we have described a different approach, we have evaluated the possibility to bypass the strict timings enforced by the cellular network protocols by means of a dedicated radio device. This allowed us to prove that it is possible to inject into the cellular networks signalling traffic without having the control of valid SIM modules. The amount of resources that we can force the infrastructure to squander through the network of a single generation (e.g. 2G, the GSM network) is sufficient to produce a significant degradation of the service although the number of needed devices is still very high. Nonetheless, this result is very significant: first, the usage of a SIMless device allows gathering the resources needed to mount the attack without interfering with users and running the risk of being discovered; second, the usage of devices that are not in possession of unknowing users allows optimal distribution of attacking devices and removes the risk that the attack fails because of an incorrect placement of the botnet nodes. The possibility to hit a single infrastructure component through different generations of network, thus leveraging the interplay between network generations in the cellular infrastructure, would allow reducing the number of attacking devices need. In fact, combining the signalling bandwidth of GSM with the one made available by the 3G (UMTS) let each attacking device to inject more traffic into the network. The combination of this with what we presented in this paper, though, is part of a broader study [START_REF] Gobbo | Attacking the attach procedure in cellular networks[END_REF] which has been submitted to the Journal of Ambient Intelligence and Humanized Computing.

Fig. 1 :

 1 Fig. 1: Representation of the main components of a standard GPRS network.

Fig. 2 :

 2 Fig.2: HLR throughput for each transaction type with 500k subscribers[START_REF] Traynor | On cellular botnets: measuring the impact of malicious devices on a cellular network core[END_REF].

Fig. 3 :

 3 Fig. 3: Messages exchanged between MS and BTS during the GSM attach procedure [19]. The lighting on the left mark the message replaced during the attack.

Fig. 4 :

 4 Fig.4: Messages exchanged between MS and BTS during the attack: our device solicits an early disconnection right after receiving the AUTH REQ from the network.

http://connectedplanetonline.com/mss/4g-world/the-lte-signalingchallenge-0919/ (accessed in May 2013).

en.wikipedia.org/wiki/Smartphone (accessed in May 2013).

http://arstechnica.com/security/2013/04/family-of-badnews-malware-ingoogle-play-downloaded-up-to-9-million-times/ (accessed on May 2013).

RIL specifications are available for Windows Mobile ® http://msdn.microsoft.com/ en-us/library/aa920475.aspx (accessed on May 2013) and Android http://www. kandroid.org/online-pdk/guide/telephony.html (accessed on May 2013).

The BSS may use the extended version of the immediate assignment command that allow channel assignment to two mobile phones simultaneously, thus doubling AGCH capacity: we will see, however, that also in the more stringent case the AGCH is not the attack bottleneck.


Abdel Alim Kamal
email: akamala@ci.menofia.edu.eg

Roger Zahno
email: rzahno@ciise.concordia.ca

Amr M Youssef
email: youssef@ciise.concordia.ca

A Comparison Between Two off-the-shelf Algebraic Tools for Extraction of Cryptographic Keys from Corrupted Memory Images

Cold boot attack is a class of side channel attacks which exploits the data remanence property of random access memory (RAM) to retrieve its contents which remain readable shortly after its power has been removed. Specialized algorithms have been previously proposed to recover cryptographic keys of several ciphers from decayed memory images. However, these techniques were cipher-dependent and certainly uneasy to develop and fine tune. On the other hand, for symmetric ciphers, the relations that have to be satisfied between the subround key bits in the key schedule always correspond to a set of nonlinear Boolean equations. In this paper, we investigate the use of an off-the-shelf SAT solver (CryptoMiniSat), and an open source Gröbner basis tool (PolyBoRi) to solve the resulting system of equations. We also provide the pros and cons of both approaches and present some simulation results for the extraction of AES and Serpent keys from decayed memory images using these tools.

Introduction

Cryptanalytic attacks can be classified into pure mathematical attacks and side channel attacks. Pure mathematical attacks, are traditional cryptanalytic techniques that rely only on known or chosen input-output pairs of the cryptographic function, and exploit the inner structure of the cipher to reveal secret key information. On the other hand, in side channel attacks, it is assumed that the attacker has some physical access to the cryptographic device through one or more side channel. Well-known side channels, which can leak critical information about the encryption state, include timing information [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF] and power consumption [START_REF] Kocher | Differential Power Analysis[END_REF].

In addition to these commonly exploited side channels, the remanence effect of random access memory (RAM) is a highly critical side channel that has been recently exploited by cold boot attacks [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF] [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] to retrieve secret keys from RAM. Although dynamic RAMs (DRAMs) become less reliable when its contents are not refreshed, they are not immediately erased. In fact, contrary to popular belief, DRAMs may retain their contents for seconds to minutes after power is lost and even if they are removed from the computer motherboard. A cold boot attack is launched by removing the memory module, after cooling it, from the target system and immediately plugging it in another system under the adversarys control. This system is then booted to access the memory. Another possible approach to execute the attack is to cold boot the target machine by cycling its power off and then on without letting it shut down properly. Upon reboot, a lightweight operating system is instantly booted where the contents of targeted memory are dumped to a file.

Experimental results in [START_REF] Skorobogatov | Low temperature data remanence in static RAM[END_REF] show how data are retained for a relatively long time in computer memories after a system power off. However, the first work explicitly exploiting those observations to recover cryptographic keys from the memory was reported by Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF] where they presented proof of concept experiments which showed that it is practically feasible to perform cold boot attacks exploiting the remanence effect of RAMs to recover secret keys of DES, AES and RSA. After the publication of Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF], several other authors (e.g., [START_REF] Tsow | An Improved Recovery Algorithm for Decayed AES Key Schedule Images[END_REF], [START_REF] Albrecht | Cold Boot Key Recovery by Solving Polynomial Systems with Noise[END_REF] [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF]) further improved upon this proof of concept and presented algorithms that solved cases with higher decay factors. However, almost all these previously proposed techniques were cipher-dependent and certainly uneasy to develop and fine tune. On the other hand, for symmetric ciphers, the relations that have to be satisfied between the subround key bits in the key schedule always correspond to a set of nonlinear Boolean equations. In this paper, we investigate the use of an off-the-shelf SAT solver (CryptoMiniSat [START_REF]CryptoMiniSat[END_REF]), and an open source Gröbner basis tool (PolyBoRi [START_REF] Brickenstein | PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials[END_REF]) to solve the resulting system of equations. We also discuss the pros and cons of both tools and present some experimental results for the extraction of AES and Serpent keys from decayed memory images.

The remainder of the paper is organized as follows. In section 2 we briefly review some related works. SAT solvers and Gröbner basis tools, and their applications in cryptography, are discussed in section 3. Relevant details of the the structure of the AES and Serpent key schedules are discussed in section 4. Our experimental results are presented and discussed in section 5. Finally, our conclusion is given in section 6.

Related work

Cryptographic key recovery from memory or memory dumps, for malicious or forensic purposes, has attracted great attention of security professionals and cryptographic researchers. In [START_REF] Shamir | Playing Hide and Seek With Stored Keys[END_REF], Shamir and van Someren considered the problem of locating cryptographic keys hidden in large amount of data, such as the complete file system of a computer system. In addition to efficient algebraic attacks locating secret RSA keys in long bit strings, they also presented more general statistical attacks which can be used to find arbitrary cryptographic keys embedded in large files. This statistical approach relies on the simple fact that good cryptographic keys pose high entropy. Areas with unusually high entropy can be located by searching for unique byte patterns in sliding windows and then selecting those windows with the highest numbers of unique bytes as a potential places for the key. Moe et al. [START_REF] Maartmann-Moe | The persistence of memory: Forensic identification and extraction of cryptographic keys[END_REF] developed a proof of concept tool, Interrogate, which implements several search methods for a set of key schedules. To verify the effectiveness of the developed tool, they investigated key recovery for systems running in different states (live, screen-saver, dismounted, hibernation, terminated, logged out, reboot, and boot states). Another proof of concept tool, Disk Decryptor, which can extract Pretty Good Privacy (PGP) and Whole Disk Encryption (WDE) keys from dumps of volatile memories was presented in [START_REF] Kaplan | RAM is Key, Extracting Disk Encryption Keys From Volatile Memory[END_REF].

All the above techniques and tools took another dimension after the publication of the cold boot attack by Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF]. While the remanence effect of RAM has already been known since decades [START_REF] Skorobogatov | Low temperature data remanence in static RAM[END_REF], it attracted greater attention in cryptography only after Halderman et al. work in 2008, which explicitly exploited those observations to recover cryptographic keys from the memory. They developed tools which capture everything present in RAM before power was cut off and developed proof of concept tools which can analyze these memory copies to extract secret DES, AES and RSA keys.

In particular, Heninger et al. showed that an RSA private key with small public exponent can be efficiently recovered given a 27% fraction of its bits at random. They have also developed a recovery algorithm for the 128-bit version of AES (AES-128) that recovers keys from 30% decayed AES-128 Key Schedule images in less than 20 minutes for half of the simulated cases. Tsow [START_REF] Tsow | An Improved Recovery Algorithm for Decayed AES Key Schedule Images[END_REF] further improved upon the proof of concept in Halderman et al. and presented a heuristic algorithm that solved all cases at 50% decay in under half a second. At 60% decay, Tsow recovered the worst case in 35.5 seconds while solving the average case in 0.174 seconds. At the extended decay rate of 70%, recovery time averages grew to over 6 minutes with the median time at about five seconds.

In [START_REF] Albrecht | Cold Boot Key Recovery by Solving Polynomial Systems with Noise[END_REF], Albrecht et al. proposed methods for key recovery of ciphers (AES, Serpent and Twofish) used in Full Disk Encryption (FDE) products where they applied a method for solving a set of non-linear algebraic equations with noise based on mixed integer programming. To improve the running time of their algorithms, they only considered a reduced number of rounds. Applying their algorithms, they obtained satisfactory success rates for key recovery using the Serpent key schedule up to 30% decay and for the AES up to 40% decay. The use of SAT solvers and Gröbner basis in cryptanalysis has recently attracted the attention of cryptanalysts. Courtois et al. [START_REF] Courtois | Algebraic and Slide Attacks on KeeLoq[END_REF] demonstrated a weakness in KeeLog by presenting an attack which requires about 2 32 known plaintexts. For 30% of all keys, the full key can be recovered against a complexity of 2 28 KeeLoq encryptions. In [START_REF] Courtois | Algebraic Cryptanalysis of the Data Encryption Standard[END_REF], 6 rounds of DES are attacked with only a single known plaintext/ciphertext pair using a SAT solver. Erickson et al. [START_REF] Erickson | Algebraic Cryptanalysis of SMS4: Gröbner Basis Attack and SAT Attack Compared[END_REF] used the SAT solver and Gröbner basis [START_REF] Buchberger | Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory[END_REF] attacks against SMS4 on equation system over GF [START_REF] Kocher | Differential Power Analysis[END_REF] and GF (2 8 ). In [START_REF] Buchmann | Block Ciphers Sensitive to Gröbner Basis Attacks[END_REF], a practical Gröbner basis [START_REF] Buchberger | Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory[END_REF] attack using Magma was applied against the ciphers Flurry and Curry, recovering the full cipher key by requiring only a minimal number of plaintext/ciphertext pairs. SAT solvers and Gröbner basis have also been applied to the cryptanalysis of stream ciphers. Eibach et al. [START_REF] Eibach | Attacking Bivium using SAT solvers[END_REF] presented experimental results on attacking a reduced version of Trivium (Bivium) using exhaustive search, a SAT solver, a binary decision diagram (BDD) based attack, a graph theoretic approach, and Gröbner basis. Their result implies that the usage of the SAT solver is faster than the other attacks. The full key of Hitag2 stream cipher is recovered in a few hours using MiniSat 2.0 [START_REF] Courtois | Practical Algebraic Attacks on the Hitag2 Stream Cipher[END_REF]. In [START_REF] Courtois | Algebraic Attacks on the Crypto-1 Stream Cipher in MiFare Classic and Oyster Cards[END_REF], the full 48-bit key of the MiFareCrypto 1 algorithm was recovered in 200 seconds on a PC, given 1 known initial vector (IV) from one single encryption. In [START_REF] Velichkov | Algebraic cryptanalysis of a small-scale version of stream cipher Lex[END_REF], Velichkov et al. applied the Gröbner basis on a reduced 16 bit version of the stream cipher Lex.

Mironov and Zhang [START_REF] Mironov | Applications of SAT Solvers to Cryptanalysis of Hash Functions[END_REF] described some initial results on using SAT solvers to automate certain components in cryptanalysis of hash functions of the MD and SHA families. De et al. [START_REF] De | Inversion Attacks on Secure Hash Functions Using satSolvers[END_REF] presented heuristics for solving inversion problems for functions that satisfy certain statistical properties similar to that of random functions. They demonstrate that this technique can be used to solve the hard case of inverting a popular secure hash function and were able to invert MD4 up to 2 rounds and 7 steps in less than 8 hours. In [START_REF] Sugita | Algebraic Cryptanalysis of 58-Round SHA-1[END_REF], Sugita et al. used the Gröbner basis to improve the attack on the 58-round SHA-1 hash function to 2 31 computations instead of 2 34 in Wang's method [START_REF] Wang | Finding Collisions in the Full SHA-1[END_REF].

Gröbner Basis and PolyBoRi

A Gröbner basis is a set of multivariate polynomials that have desirable algorithmic properties. In what follows, we briefly review some basic definitions and algebraic preliminaries related to Gröbner basis as presented in [START_REF] Segers | Algebraic Attacks from a Groebner Basis Perspective[END_REF].

Let K be any field (in here we are interested in the case where K = F 2 .) We write K[x 1 , ..., x n ] for the ring of polynomials in n for the variables x i having its coefficients in the field K.

Definition 1. A subset I ⊂ K[x 1 , ..., x n ] is an ideal if it satisfies: 1. 0 ∈ I. 2. if f ,g ∈ I, then f + g ∈ I. 3. if f ∈ I and h ∈ K[x 1 , ..., x n ], then hf ∈ I. Definition 2. Let f 1 , ..., f m be polynomials in K[x 1 , ..., x n ]. Define the ideal ⟨f 1 , ..., f m ⟩ = { ∑ m i=1 h i f i : h 1 , ..., h m ∈ K[x 1 , ..., x n ] }.
If there exists a finite set of polynomials in K[x 1 , ..., x n ] that generate the given ideal, we call this set a basis.

Definition 3. A monomial ordering on

K[x 1 , ..., x n ] is any relation > on Z n ≥0 ,

or equivalently, any relation on the set of monomials

x α , α ∈ Z n ≥0 , satisfying: 1. > is a total ordering on Z n ≥0 . 2. if α > β and α, β, γ ∈ Z n ≥0 , then α + γ > β + γ. 3. > is a well ordering on Z n ≥0 .
That is every nonempty subset of Z n ≥0 has a smallest element with respect to >.

An example of monomial ordering for our application is lexicographic order which is defined as follows: Definition 4. (Lexicographic Order (lex)). Let α = (α 1 , ..., α n ), and β = (β 1 , ..., β n ) ∈ Z n ≥0 . We say α > lex β if, in the vector difference α -β ∈ Z n , the left-most nonzero entry is positive. We will write x α > lex x β if α > lex β. Definition 5. Let f = Σ α a α x α be a non-zero polynomial in P and let > be a monomial order. The multidegree of f is multideg

(f ) = max > (α ∈ Z n 0 : a α ̸ = 0). Definition 6. (leading term of a polynomial). Let f (x) = ∑ m i=1 c α x α : c α ∈ K is non-zero
and > is the order relation defined for the monomials of the polynomial f (x). The greatest monomial in f (x), regarding to the order relation >, is called the leading monomial for the polynomial f (x) and is represented by LM (f ) = x multideg(f ) . Also the set M (f ) consists of all monomials of f (x) and T (f ) denote the set of all terms of f (x). The coefficient of the leading monomial is represented by LC(f ) = a multideg(f ) ∈ K and called the leading coefficient. The term containing both the leading coefficient and leading monomial is called the leading term, represented by

LT (f ) = LC(f ) • LM (f ).
The idea of Gröbner basis was first proposed by Buchberger [START_REF] Buchberger | Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory[END_REF] to study the membership of a polynomial in the ideal of the polynomial ring. Definition 7. (Gröbner basis) Let an ideal I be generated by G = g 1 , ..., g m , where g i , 1 ≤ i ≤ m is a polynomial. G is called the Gröbner basis for the ideal I, if:

⟨LT (I)⟩ = ⟨LT (g 1 ), ..., LT (g m )⟩,
where ⟨LT (I)⟩ denotes the ideal generated by the leading terms of the members in I.

One can view Gröbner basis as a multivariate, non-linear generalization of the Euclidean algorithm for computation of univariate greatest common divisors, Gaussian elimination for linear systems, and integer programming problems. In this work, we use Gröbner basis as an algebraic tool that allows us to solve non-linear Boolean equations by using the PolyBoRi framework.

The following example explains the main involved steps and commands for the PolyBoRi framework in Sage [START_REF]Boolean Polynomials[END_REF] to solve a given system of nonlinear Boolean equations.

Example 8. Consider the following system of non-linear Boolean equations

x 1 x 2 ⊕ x 3 x 4 = 1, x 1 x 3 x 5 ⊕ x 4 x 5 = 0, x 1 x 2 x 5 ⊕ x 3 x 5 = 0, x 2 x 3 ⊕ x 3 x 4 x 5 = 1, (1)
Figure 1 shows the steps to be executed in PolyBoRi to solve the Gröbner basis. As shown in the figure, the function ideal() in step 2 takes the corresponding homogeneous system of equations as a calling parameter.

The resulting Gröbner basis is given by [

x 1 + x 4 + 1, x 2 + 1, x 3 + 1, x 2 4 + x 4 , x 5 ]
. In this notation, x i appearing in a separate term by itself implies that the system of equations under consideration can be solved by setting x i = 0. Similarly, x i + 1 implies that x i = 1. Also, the notation x i + x 2 i implies that x i can be assigned a 0 or a 1. Thus the above basis corresponds to the following two independent solutions:

{x 1 = 1, x 2 = 1, x 3 = 1, x 4 = 0, x 5 = 0} and {x 1 = 0, x 2 = 1, x 3 = 1, x 4 = 1, x 5 = 0}.

The SAT problem and CryptoMiniSat

The Boolean satisfiability (SAT) problem [START_REF] Cook | The complexity of theorem-proving procedures[END_REF] is defined as follows: Given a Boolean formula, check whether an assignment of Boolean values to the propositional variables in the formula exists such that the formula evaluates to true. If such an assignment exists, the formula is said to be satisfiable; otherwise, it is unsatisfiable. For a formula with m variables, there are 2 m possible truth assignments. The conjunctive normal form (CNF) is frequently used for representing Boolean c Lines starting with 'c' are comments c c c

Step 1 defines the Polynomial Ring; where GF(2) defines the Galois field (GF) of 2 elements as the base ring, 5 is the number of variables and order = 'lex' sets the order to lexical order c c

Step 2 defines the Ideal taking a set of homogeneous equations as calling parameter c c

Step 3 combines the ideal I with the field ideal; limiting the solution range to formulas. In CNF, the variables of the formula appear in literals (e.g., x) or their negation (e.g., x). Literals are grouped into clauses, which represent a disjunction (logical OR) of the literals they contain. A single literal can appear in any number of clauses. The conjunction (logical AND) of all clauses represents a formula. For example, the CNF formula (x 1 ) ∧ (x 2 ∨ x 3 ) ∧ (x 1 ∨ x 3 ) contains three clauses: x 1 , x 2 ∨ x 3 and x 1 ∨ x 3 . Two literals in these clauses are positive (x 1 , x 3 ) and two are negative (x 2 , x 3 ). For a variable assignment to satisfy a CNF formula, it must satisfy each of its clauses. For example, if x 1 is true and x 2 is false, then all three clauses are satisfied, regardless of the value of x 3 .

While the SAT problem has been shown to be NP-complete [START_REF] Cook | The complexity of theorem-proving procedures[END_REF], efficient heuristics exist that can solve many real-life SAT formulations. Furthermore, the wide range of target applications of SAT have motivated advances in SAT solving techniques that have been incorporated into freely-available SAT solvers such as the CryptoMiniSat.

When preparing the input to the SAT solver, the terms of quadratic and higher degree are handled by noting that (for example) the logical expression

(x 1 ∨ T )(x 2 ∨ T )(x 3 ∨ T )(x 4 ∨ T )(T ∨ x 1 ∨ x 2 ∨ x 3 ∨ x 4 ) (2)
is tautologically equivalent to T ⇔ (x 1 ∧ x 2 ∧ x 3 ∧ x 4 ), or the GF (2) equation T = x 1 x 2 x 3 x 4 . Similar expressions exist for higher order terms. Thus, the system of equations obtained in this step can be linearized by introducing new variables as illustrated by the following example.

Example 9. Suppose we would like to find the Boolean variable assignment that satisfies the following formula

x 0 ⊕ x 1 x 2 ⊕ x 0 x 1 x 2 = 0.
Then, using the approach illustrated in (2), we introduce two linearization variables, T 0 = x 1 x 2 and T 1 = x 0 x 1 x 2 . Thus we have

x 0 ⊕ T 0 ⊕ T 1 = 0, (T 0 ∨ x 1 ) ∧ (T 0 ∨ x 2 ) ∧ (T 0 ∨ x 1 ∨ x 2 ) = 1, (T 1 ∨ x 0 ) ∧ (T 1 ∨ x 1 ) ∧ (T 1 ∨ x 2 )∧ (T 1 ∨ x 0 ∨ x 1 ∨ x 2 ) = 1.
(3) Since the CryptoMiniSAT expects only positive clauses and the CNF form does not have any constants, we need to overcome the problem that the first line in (3) corresponds to a negative, i.e., false, clause. Adding the clause consisting of a dummy variable, d, or equivalently (d∧d • • •∧d) would require the variable d to be true in any satisfying solution, since all clauses must be true in any satisfying solution. In other words, the variable d will serve the place of the constant 1. Therefore, the above formula can be expressed as

d = 1, x 0 ⊕ T 0 ⊕ T 1 ⊕ d = 1, (T 0 ∨ x 1 ) ∧ (T 0 ∨ x 2 ) ∧ (T 0 ∨ x 1 ∨ x 2 ) = 1, (T 1 ∨ x 0 ) ∧ (T 1 ∨ x 1 ) ∧ (T 1 ∨ x 2 )∧ (T 1 ∨ x 0 ∨ x 1 ∨ x 2 ) = 1.
Applying the same logic to the system of equations in (1), we obtain

d = 1, T 1 ⊕ T 2 = 1, (T 1 ∨ x 1 ) ∧ (T 1 ∨ x 2 ) ∧ (T 1 ∨ x 1 ∨ x 2 ) = 1, (T 2 ∨ x 3 ) ∧ (T 2 ∨ x 4 ) ∧ (T 2 ∨ x 3 ∨ x 4 ) = 1, T 3 ⊕ T 4 ⊕ d = 1, (T 3 ∨ x 1 ) ∧ (T 3 ∨ x 3 ) ∧ (T 3 ∨ x 5 )∧ (T 3 ∨ x 1 ∨ x 3 ∨ x 5 ) = 1, (T 4 ∨ x 4 ) ∧ (T 4 ∨ x 5 ) ∧ (T 4 ∨ x 4 ∨ x 5 ) = 1, T 5 ⊕ T 6 ⊕ d = 1, (T 5 ∨ x 1 ) ∧ (T 5 ∨ x 2 ) ∧ (T 5 ∨ x 5 )∧ (T 3 ∨ x 1 ∨ x 2 ∨ x 5 ) = 1, (T 6 ∨ x 3 ) ∧ (T 6 ∨ x 5 ) ∧ (T 6 ∨ x 3 ∨ x 5 ) = 1, T 7 ⊕ T 8 = 1, (T 7 ∨ x 2 ) ∧ (T 7 ∨ x 3 ) ∧ (T 7 ∨ x 2 ∨ x 3 ) = 1, (T 8 ∨ x 3 ) ∧ (T 8 ∨ x 4 ) ∧ (T 8 ∨ x 5 )∧ (T 8 ∨ x 3 ∨ x 4 ∨ x 5 ) = 1,
Figure 2 shows the CryptoMiniSat input file corresponding to the above system of equations. As shown in the figure, a negative number implies that the variables assumes a value = 0 and a positive number implies a value = 1. Lines starting with 'x' denote an XOR equation and each lines is terminated with '0'.

From the above examples, its is clear that, compared to PolyBoRi, preparing the input for the CryptoMiniSat requires relatively longer pre-processing steps. Also, unlike the Gröbner basis approach which returns the general form of the solution, CryptoMiniSat returns one valid solution. To find the other solutions, the already found solutions have to be negated and added to the SAT solver input file. In the example above, the first solution returned by the CryptoMiniSat ({1, -2, 3, 4, 5, -6, -7, 8, -9, -10, -11, -12, 13, -14}) is negated ({-1, 2, -3, -4, -5, 6, 7, -8, 9, 10, 11, 12, -13, 14}) and added to the SAT solver input file as a new entry. When running the SAT solver again, this added entry forces the SAT solver to eliminate this as a possible solution and search for a new one that solves the SAT problem. When doing so, the SAT solver returns the second possible solution ({1, 2, 3, 4, -5, -6, 7, -8, -9, -10, -11, -12, 13, -14}).

Structure of the AES-128 and Serpent Key Schedules

In this section, we briefly review the relevant details of the AES-128 and Serpent key schedules.

Key Schedule of AES-128

In the following we describe the AES-128 key scheduler [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], [START_REF]Federal Information Processing Standards Publication[END_REF]. AES-128 works with a user key (Master Key) of 128 bits (16 bytes) represented by a 4x4 array K 0 i,j , the AES state matrix; with 0 ≤ i, j ≤ 3 where i and j denote the row and column indices, respectively. K r+1 i,j denotes the bijective mapping of the user key to the 10 sub-round keys, where 0 ≤ r ≤ 9 denotes the number of the rounds. The r th key schedule round is defined by the following transformations: c Lines starting with 'c' are comments c The first line in the SAT file is in the form: 'p cnf # variables # clause' c Each line ends with '0' and lines starting with 'x' denote XOR equations c c True variables are denoted by positive numbers and False variables are denoted by negating the number; example: x 1 2; (x ͞ 2 -3) c d 1, x 1 2, x 2 3, … , T 6 12, T 7 13, T 8 14 p cnf 14 32 1 0 x 7 8 0 -7 2 0 -7 3 0 7 -2 -3 0 -8 4 0 -8 5 0 8 -4 -5 0 x 9 10 1 0 -9 2 0 -9 4 0 -9 6 0 9 -2 -4 -6 0 -10 5 0 -10 6 0 10 -5 -6 0 x 11 12 1 0 -11 2 0 -11 3 0 -11 6 0 11 -2 -3 -6 0 -12 4 0 -12 6 0 12 -4 -6 0 x 13 14 0 -13 3 0 -13 4 0 13 -3 -4 0 -14 4 0 -14 5 0 -14 6 0 14 -4 -5 -6 0 Fig. 2. CryptoMiniSat input file corresponding to the system of equations in (1)

K r+1 0,0 ← S(K r 1,3 ) ⊕ K r 0,0 ⊕ Rcon(r + 1) K r+1 i,0 ← S(K r (i+1)mod4,3 ) ⊕ K r i,0 , 1 ≤ i ≤ 3 K r+1 i,j ← K r+1 i,j-1 ⊕ K r i,j , 0 ≤ i ≤ 3, 1 ≤ j ≤ 3 (4)
where Rcon(•) denotes a round-dependent constant and S(•) represents the S-box operations based on the 8 × 8 Rijndael S-box [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF]. Figure 3 shows the transformations given by equation 4.

Key Schedule of Serpent

Serpent [START_REF] Anderson | Serpent: A Proposal for the Advanced Encryption Standard[END_REF] is a 32 round block cipher based on a substitution permutation network (SPN) structure with an Initial Permutation (IP) and a Final Permutation (FP). It has 32 rounds, each consists of a key mixing operation, a pass through S-boxes, and (in all but the last round) a linear transformation. In the last round, this linear transformation is replaced by an additional key mixing operation. The cipher accepts a variable user key length that is always padded up to 256 bits by appending one bit-value '1' to the end of the most significant bit followed by bit-values '0'. To obtain the 33 128-bit subkeys K 0 , ..., K 32 , the user key is divided into eight 32-bit words w -8 , w -7 , ..., w -1 , from which the 132 intermediate keys or pre-keys (w 0 ...w 131 ) are derived as follows: where ϕ is a constant formed by the fractional part of the golden ratio ( √ 5 + 1)/2 or 0x9e3779b9 in hexadecimal.

w i := (w i-8 ⊕ w i-5 ⊕ w i-3 ⊕ w i-1 ⊕ ϕ ⊕ i) <<< 11 (5)
The round keys k i are evaluated from the pre-keys by first calling one of the eight 4×4 S-boxes in bit slice mode. In bit slice mode, each input of the S-box comes from a different 32-bit word and each output goes to a different 32-bit word. The 4x32 bits per round are all handled by the same S-box. A group of four input or four output words defines a unit that is handled together. The transformation from pre-keys w i into words k j of round keys is performed as follows:

{k 0 ; k 1 ; k 2 ; k 3 } = S 3 (
where S i denotes the i th s-box of Serpent. The round keys K i are then formed by regrouping the 32-bit values k j as 128-bit sub-keys K i (for i ∈ 0,.., r) as follows:

K i := {k 4i ; k 4i+1 ; k 4i+2 ; k 4i+3 } (7)
Finally, we apply IP to the round keys K i in order to place the key bits in the correct column, i.e., Ki = IP(K i ). Figure 4 depicts the described key scheduler of Serpent.

By exploiting the asymmetric decay of the memory images and the redundancy of key material inherent in the key schedule of both algorithms above, rectifying the faults in the corrupted memory images of the the key schedule is formulated as a Boolean satisfiability problem which can be solved efficiently for relatively large decay factors.

wi := (w i-8 ⊕ w i-5 ⊕ w i-3 ⊕ w i-1 ⊕ Φ ⊕ i) <<<11
...

Experimental Results

Because of the nature of the cold boot attack, it is realistic to assume that only a corrupted image of the contents of memory is available to the attacker, i.e., a fraction of the memory bits will be flipped. Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF] observed that, within a specific memory region, the decay is overwhelmingly asymmetric, i.e., either 0 → 1 or 1 → 0. When trying to retrieve cryptographic keys, the decay direction for a region can be determined by comparing the number of 0s and 1s since in an uncorrupted key, the expected number of 0s and 1s should approximately be equal. Similar to the previous work in [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF] [6] [START_REF] Kamal | Applications of SAT Solvers to AES Key Recovery from Decayed Key Schedule Images[END_REF], throughout our experimental results, we assume an asymmetric decay model where bits overwhelmingly decay to their ground state rather than their charged state. Using this model, only the bits that remain in their charged state are useful to the cryptanalyst since one cannot be sure about the original values of the 0 bits, i.e., whether they were originally 0's or decayed 1's. Let β denote the fraction of decayed bits. If the percentage of 0's and 1's in the original key schedule bits is p z and 1 -p z , respectively, then the fraction, f , of key bits that can be assumed to be known by examining the decayed memory of the key schedule is given by f

= 1 -(p z + β × (1 -p z )) = (1 -p z ) × (1 -β).
Since in an uncorrupted key schedule key, we expect the number of 0's and 1's to be approximately equal, i.e., p z ≈ 1/2, then we have f ≈ (1 -β)/2.

In our experiments, the input files for the CryptoMiniSAT contained 5,144 and 18,500 clauses for AES and Serpent, respectively. For PolyBoRi, 1,280 equations with 1,728 variables were defined for AES and 8,448 equations with 8,704 variables were defined for Serpent.

Tables 1, 2, 3 [START_REF] Kamal | Applications of SAT Solvers to AES Key Recovery from Decayed Key Schedule Images[END_REF] and 4 show statistics for the run time required to recover the key of AES and Serpent from the corresponding corrupted memory images for different decay factors. These runtime statistics were obtained using PolyBoRi and CryptoMiniSat running on a Dell Precision 370 workstation with a 3.0 GHz Intel Pentium 4 CPU and 1 GB of RAM. Examining the results in the tables reveal the following observations:

-While the resource requirements of both tools (time for CryptoMiniSat, and time and memory for PloyBoRi) seem to grow exponentially with the decay factor, for practical values of the decay factor, both tools require reasonably short time to recover the secret keys from corrupted memory images. -The simple and high redundancy in the AES key schedule allows for faster recovery of the key from corrupted memory images. This makes AES more prone to these attacks as compared to other AES finalist such as Serpent. In fact, our initial experiments with Twofish [START_REF]Twofish[END_REF] indicate that its relatively more complex key schedule limits the practical applications of these tools to very small values of the decay factor. -CryptoMiniSat seems to be more suitable for applications in this type of attacks. In particular, every time we tried to push the decay factor higher than the values reported in Table 1, the PolyBoRi tool always crashed after few minutes due to the excessive memory consumption. This behavior also persisted on a 64 bit Linux operating systems with a freshly compiled PolyBoRi/sage system and 8 GB RAM. The question remains if solutions for a higher decay factor can be achieved in a reasonable time if this memory limitations is fixed in the tool. 0.6 0.7 0.9 1.7 2.9 5.6 21 St.Dev 0.1 0.1 0.1 0.3 0.5 1.2 13 Med.

0.5 0.7 0.9 1.7 2.9 5.3 15

Conclusion

In this work, we investigated the suitability of two off-the-shelf Algebraic tools for extraction of cryptographic keys from corrupted memory images. Based on our experimental results, it is clear that while the CryptoMiniSat requires a slightly longer preprocessing step to prepare its input file, this step is done only once and the tool runs much faster than the Gröbner basis PolyBoRi tool. Furthermore, CryptoMiniSat does not require a large amount of memory during run time.

However, if several solutions were possible for the SAT problem in question, only one result is returned by the solver and the additional solutions have to be explicitly searched again by rerunning the tool after appending some extra constraints to exclude already found solutions. On the other hand, Gröbner basis returns a general form representing all possible solutions. However, PolyBoRi requires large memory and usually crashes when the memory requirements is exceeded which limits its applications for solving large problems. It should also be noted that, given the high redundancy of the key schedules of the considered ciphers, the advantage of being able to return all possible solutions does not seem to be very significant since in all the instances we considered, only one possible solution exists.

F 2 cFig. 1 .

 21 Fig. 1. Working with PolyBoRi to solve the systems of equations in (1)

Fig. 3 .

 3 Fig. 3. AES Key Scheduler

Fig. 4 .

 4 Fig. 4. Serpent Key Scheduler

  w 0 ; w 1 ; w 2 ; w 3 ) {k 4 ; k 5 ; k 6 ; k 7 } = S 2 (w 4 ; w 5 ; w 6 ; w 7 ) {k 8 ; k 9 ; k 10 ; k 11 } = S 1 (w 8 ; w 9 ; w 10 ; w 11 ) {k 12 ; k 13 ; k 14 ; k 15 } = S 0 (w 12 ; w 13 ; w 14 ; w 15 ) {k 16 ; k 17 ; k 18 ; k 19 } = S 7 (w 16 ; w 17 ; w 18 ; w 19 ) {k 124 ; k 125 ; k 126 ; k 127 } = S 4 (w 124 ; w 125 ; w 126 ; w 127 ) {k 128 ; k 129 ; k 130 ; k 131 } = S 3 (w 128 ; w 129 ; w 130 ; w 131 )

	. . .	. . .	. . .

Table 1 .

 1 Run-time statistics using Gröbner basis for AES.

	Decay 10% 20% 30% 40% 50% 60% 70%
	Min	0.4 0.6 0.8 1.3 2.2 3.5	7
	Max	0.7 0.9 1.1 2.1 3.6 7.6 45
	Avg.

Table 2 .

 2 Run-time statistics using Gröbner basis for Serpent.

	Decay 10% 20% 30% 40% 50% 60% 70%
	Min	8	9 17 56 114 417	-
	Max	9 34 50 2075 2812 578	-
	Avg.	8 15 36 328 399 507	-
	St.Dev 0.3	7 11 656 764 47	-
	Med.	8 12 40 107 131 504	-

Table 3 .

 3 Run-time statistics using SAT-solver for AES.

	Decay 30% 40% 50% 60%	70%
	Min	0.046 0.046 0.062 0.062 0.078
	Max	0.593 0.140 0.187 0.593 207.171
	Avg. 0.064 0.066 0.074 0.102 1.233
	St.Dev 0.009 0.007 0.008 0.028 4.899
	Med. 0.062 0.062 0.078 0.093 0.359

Table 4 .

 4 Run-time statistics using SAT-solver for Serpent.

	Decay 10% 20% 30% 40% 50% 60% 70%
	Min	0.4 0.4 0.5 0.5 0.7 0.9	4
	Max	0.7 0.8 1.2 1.6 8.0 69 35282
	Avg.	0.6 0.6 0.7 0.9 1.9	8 1278
	St.Dev 0.05 0.07 0.10 0.22 1.30 11 4402
	Med. 0.15 0.17 0.20 0.35 1.18	9 27706

S(.)

Rcon( 1RotWord S(.) Rcon( 2RotWord S(.) Rcon [START_REF] Shamir | Playing Hide and Seek With Stored Keys[END_REF] RotWord Rcon( 1)