Wouter Lueks
email: lueks@cs.ru.nl

Gergely Alpár
email: gergely@cs.ru.nl

Jaap-Henk Hoepman

Pim Vullers

Fast Revocation of Attribute-Based Credentials for Both Users and Verifiers

Attribute-based credentials allow a user to prove properties about herself anonymously. Revoking such credentials, which requires singling them out, is hard because it is at odds with anonymity. All revocation schemes proposed to date either sacrifice anonymity altogether, require the parties to be online, or put high load on the user or the verifier. As a result, these schemes are either too complicated for low-powered devices like smart cards or they do not scale. We propose a new revocation scheme that has a very low computational cost for users and verifiers, and does not require users to process updates. We trade only a limited, but well-defined, amount of anonymity to make the first practical revocation scheme that is efficient at large scales and fast enough for smart cards.

Introduction

More and more governments are issuing electronic identity (eID) cards to their citizens [START_REF] Lehmann | Survey and Analysis of Existing eID and Credential Systems[END_REF][START_REF] Naumann | Privacy features of European eID card specifications[END_REF][START_REF]OECD: National Strategies and Policies for Digital Identity Management in OECD Countries[END_REF]. These eID cards can be used both offline and online for secure authentication with the government and sometimes with other parties, like shops. Attributebased credentials (ABCs) [START_REF] Camenisch | D2.1 Architecture for Attribute-based Credential Technologies[END_REF] are an emerging technology for implementing eID cards because of their flexibility and strong privacy guarantees, and because they can be fully implemented on smart cards [START_REF] Vullers | Efficient Selective Disclosure on Smart Cards Using Idemix[END_REF]. Every credential contains attributes that the user can either reveal or keep hidden. Such attributes describe properties of a person, like her name and age. ABCs enable a range of scenarios from fully-identifying to fullyanonymous. 1 When using a credential fully anonymously (i.e., without revealing any identifying attributes), proper ABC technologies guarantee that the credential is unlinkable: it is not possible to connect multiple uses of the same credential.

When ABCs are applied, the carriers on which the credentials are stored (for example, smart cards) can be lost or stolen. In such cases, it is important that users can revoke An extendend version of this paper is available in the Cryptology ePrint Archive [START_REF] Lueks | Fast revocation of attribute-based credentials for both users and verifiers[END_REF]. The work described in this paper has been supported under the ICT theme of the Cooperation Programme of the 7th Framework Programme of the European Commission, GA number 318424 (FutureID) and the research program Sentinels (www.sentinels.nl) as project 'Mobile IDM' (10522) and 'Revocable Privacy' (10532). Sentinels is being financed by Technology Foundation STW, the Netherlands Organization for Scientific Research (NWO), and the Dutch Ministry of Economic Affairs. This research is conducted within the Privacy and Identity Lab (PI.lab) and funded by SIDN.nl (http://www.sidn.nl).

these credentials to ensure that they can no longer be (ab)used. This is also necessary when the owner of the credential herself abuses it. Revocation may, in fact, happen often. As an example, the nationwide Belgian eID system's revocation list contains more than 375 000 credentials [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF] for just over 10 million citizens. A practical revocation scheme must therefore efficiently deal with such large revocation lists.

Unfortunately, the unlinkability of ABCs precludes the use of standard, identitybased revocation. There exist many privacy-friendly revocation schemes, with different trade-offs in terms of efficiency (both for users and verifiers), connectivity requirements, and anonymity. It turns out to be hard to satisfy all of these simultaneously. In particular, all revocation schemes proposed so far suffer from at least one of the following two problems: (1) they rely on computationally powerful users, making the scheme unsuitable for smart cards, the obvious carrier for a national eID; or [START_REF] Bernstein | High-speed high-security signatures[END_REF] they place a high load on verifiers, resulting in long transaction times.

The IRMA Project. This research is part of the ongoing research project "I Reveal My Attributes" (IRMA). 2 The goal of this project is to demonstrate the practicality of attribute-based credentials. We implemented the entire user-side of the credentials on a smart card [START_REF] Vullers | Efficient Selective Disclosure on Smart Cards Using Idemix[END_REF]. In this paper we focus on this setting.

Our contribution. Our contribution is a new revocation scheme that has very low computational cost for users and verifiers alike; it is efficient even in the smart card setting, and can therefore be used in practice. We introduce the main idea in Section 2, introduce ABCs in Section 3, and describe the full scheme in Section 4. In our scheme, verifiers need only constant time on average to check revocation status, making it as fast as traditional non-anonymous revocation schemes. Furthermore, the users' computational overhead is small (and updates to reflect revocations are not necessary). Our scheme is based on epochs that divide time in short (configurable) intervals. Our scheme is unlinkable, except if the user uses her credential more than once per epoch at the same verifier. Our revocation scheme works with most credential schemes. As an example, we instantiate it for Idemix [START_REF]Specification of the Identity Mixer cryptographic library[END_REF] in Section 5. We give pointers for implementing our scheme in practice, and give experimental results as evidence of feasibility of our scheme in Section 6. Finally, we review related work in Section 7 and conclude our paper in Section 8.

The Idea

Our scheme enables efficient and privacy-friendly revocation of credentials. As it resembles verifier-local revocation (VLR) schemes [START_REF] Ateniese | Quasi-Efficient Revocation in Group Signatures[END_REF][START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF][START_REF] Brickell | The DAA scheme in context[END_REF], we describe those first.

Verifier-local revocation

The setting is a cyclic group G with prime order q. Every credential encodes a random revocation value r ∈ Z q . If a credential has to be revoked, its revocation value r is added to the global revocation list RL. When the user shows the credential to a verifier, the verifier needs to check whether the user's revocation value r appears on the revocation list RL. To facilitate this check without revealing r itself, the user chooses a random revocation generator h ∈ R G, calculates the revocation token R = h r , and sends

(h, R) (1)
to the verifier during showing. The user also proves that the revocation value r embedded into R corresponds to credential she is showing. This proof depends on the type of credential-see Section 5 for an example. Each verifier holds a copy of the revocation list RL = {r 1 , . . . , r k }. To check whether the credential is still valid, the verifier checks whether h rj = R for each r j ∈ RL and rejects the credential if one of these equalities holds. This form of verifier-local revocation has some problems in practice:

1. Because the user chooses the revocation generator h at random, the work for the verifier increases linearly with the number of items on the revocation list. This quickly causes performance problems. 2. The scheme is not forward-secure. Once the verifier obtains a revocation value r i , the verifier can link all past and future interactions involving this value, if it stores the tuples (h, R) from (1). Some solutions have been proposed to solve this problem-see Section 7-but they are not efficient enough for our purposes.

Our scheme addresses these two disadvantages.

Our scheme

We propose to split time into epochs and to use one generator per epoch and per verifier. This limits the user to one showing per verifier per epoch if she wants to remain unlinkable (which is not a problem when epochs are small) but makes revocation checking very fast for the verifier. The user uses the per-epoch per-verifier generator g ε,V to create the values in [START_REF] Ateniese | Quasi-Efficient Revocation in Group Signatures[END_REF]. In particular, she sends R = g r ε,V to the verifier. To check whether the credential is revoked the verifier does not need to know the raw revocation values. Instead, a semi-trusted party, the revocation authority (RA), can store these, and provide the verifier with a revocation list:

RL ε,V = {g r1 ε,V , . . . , g r k ε,V }.
The credential is revoked if R ∈ RL ε,V . This operation takes only O(1) time on average using associative arrays. The average time complexity thus decreases from linear to constant in the length of the revocation list RL ε,V . While some computation load shifts to the RA, the RA does no more work creating the list than a verifier in the VLR scheme does for every verification. Also, the verifier can no longer link transactions in different epochs since it does not have the bare revocation values.

Epochs and generators. The length of an epoch must be sufficiently short so that a user normally never shows her credential twice within the same epoch to the same verifier.

If the generator is reused, the corresponding activities of the user become linkable. The generators form an attack vector for a malicious adversary to link users' activities. It is not sufficient for the user to keep track of the generators she used before.

A malicious verifier could take one fixed generator g ε,V , and then create a new one by picking a random exponent x ∈ R Z q and sending g x ε,V to the user. All revocation tokens are then easily reduced to the same base g ε,V , without the user ever seeing a similar generator.

To prevent this attack, users should calculate the generators themselves. The easiest method-and the one we propose here-is to use a hash function and let the generator g ε,V for a verifier V and epoch ε equal H(ε V ), where H is a hash function from the strings to the group G and the epoch ε is derived from the current time.

A primer on ABCs

Attribute-based credentials are a cryptographic alternative to traditional credentials like driver's licenses and passports. ABCs contain a set of attributes, typically encoded as numbers, that a user can selectively reveal to the verifier. Even when attributes are hidden, the verifier can still assess the validity of the credential.

A typical attribute-based credential scheme comprises the following three parties.

Issuer The issuer issues credentials to users. It ensures that the correct data are stored in the credential. A typical credential scheme has multiple issuers. User The user holds a set of credentials, obtained from one or more issuers. She can disclose a (user defined) selection of attributes from any number of her credentials to a verifier to obtain a service. Verifier The verifier, sometimes called relying party or service provider, checks that the credential is valid, the revealed attributes are as required, and the credential is not revoked. Based on the outcome, it may provide a service to the user.

When the credential scheme supports revocation, another party is present.

Revocation Authority

The revocation authority is responsible for revoking credentials. It determines when to revoke, and stores all information necessary to do so. If necessary, it sends revocation information to users and verifiers.

Our scheme is independent of the choice of credential scheme, but we impose three restrictions on it:

3. The showing protocol must be extendible to provide the verifier with the revocation token R = g r ε,V and a proof that R and C(r) contain the same revocation value r. Fortunately, most credential schemes already rely on zero-knowledge proofs, and these can readily be extended to include the required proof of equality.

Furthermore, we assume that the credential scheme authenticates the verifiers. (This is without loss of generality. It is easy to add such a layer if it is missing.)

The full scheme

We now describe the full scheme. It expands on the intuition described in Section 2 by explicitly stating how the revocation authority (RA) operates and how it deals with verifiers. Section 6 shows how to implement this scheme.

The revocation authority runs the SetupRA algorithm once.

SetupRA(1 ) This algorithm takes as input a security parameter 1 . It chooses a cyclic group G of prime order q with generator g such that the DDH problem is hard in G and q has bits. Furthermore, it picks a hash function H : {0, 1} * → G that maps strings onto this group. It outputs (G, g, q, H). These parameters are public and known to all other parties. The RA keeps track of the current epoch ε, which it initializes to 0, and the initially empty master revocation list MRL containing revoked credentials identified by their revocation values.

Users and verifiers run the algorithms SetupU and SetupV respectively. SetupV() The verifier calls GetRevocationList to get an initial revocation list from the revocation authority-see below. It also keeps track of the current epoch ε.

SetupU()

At the beginning of a new epoch, all parties increase the current epoch ε by 1. In particular, we assume that all users know the current epoch. 4 At the start of a new epoch, users additionally clear the list T C of verifiers that have seen credential C in this epoch. Every verifier V runs the GetRevocationList protocol with the revocation authority to get its revocation list for the current epoch.

Sorting the revocation lists RL ε,V ensures that unlinkability is preserved for all previous activities, even for revoked users (if |MRL| > 1). 6To revoke a credential, the Revoke protocol is run with the revocation authority.

Revoke(r)

When the revocation authority is asked to revoke a credential with revocation value r, it adds r to the master revocation list MRL.

In a deployed system, it is the RA's responsibility to decide whether to grant the revocation request. In Section 6.1 we discuss how a credential can be revoked in practice.

When showing a credential, the user and the verifier follow the ShowCredential protocol. Using this protocol, the user first authenticates the verifier. Then, she gives a revocation token to the verifier and proves that she has a corresponding credential. The verifier checks the validity of the credential and whether it has been revoked.

ShowCredential(C, V )

This protocol is run between a user holding credential C and a verifier V. It proceeds as follows.

1. The verifier authenticates itself to the user. The user aborts if the authentication is unsuccessful or if V ∈ T C . 2. The user calculates the verifier (and epoch) specific generator g ε,V = H(ε V ), and adds V to the list of seen verifiers T C . 3. The user sends its revocation token R = g r ε,V to the verifier. Here, r is the revocation value encoded into the user's credential C(r). 4. The user and the verifier run the normal showing protocol for the user's credential C(r), but in addition the user proves that its revocation token R is wellformed, i.e., that the exponent r is the same as the revocation value encoded in the credential. Section 5 shows an example of such a proof for Idemix. 5. The verifier checks the validity of the credential and whether R is well-formed.

Finally, it confirms that R is not on its revocation list RL ε,V for the current epoch. It aborts if any of these checks fail.

The list T C and the epoch ε uniquely determine the generators that the user has used for credential C in this epoch. The checks above ensure that the user never reuses a generator. Also, the user always calculates the generators herself. This prevents the verifier from cheating with the generators. Checking that R ∈ RL ε,V can be done in constant time (on average) if the verifier processes the revocation list RL ε,V into an associative array. Some tricks help keep the size of the revocation lists manageable-see Section 6.5.

Sketch of the security of the scheme

A good revocation scheme needs to satisfy two properties: (1) non-revoked credentials are still unlinkable, and (2) a revoked credential is no longer usable. Our scheme satisfies these two properties in a reasonable security model.

To model unlinkability, the adversary can interact with credentials in the system as often as it wants, in any epoch and as any verifier. It can also revoke credentials. In the challenge phase, it picks a verifier, an epoch and two credentials i 0 and i 1 that were not revoked in any earlier epoch nor shown to it in the chosen epoch (since our scheme does not guarantee unlinkability when a credential is shown twice in one epoch to to the same verifier). It is shown one of these credentials; it must determine which one. In the full version of this paper, we show that, assuming the random oracle model and the hardness of the Diffie-Hellman problem, it is not possible to make this distinction [START_REF] Lueks | Fast revocation of attribute-based credentials for both users and verifiers[END_REF]. Because credentials can be revoked in epochs past the challenge epoch, this implies forward security.

It is also not possible for an adversary to avoid revocation. The proof in step 4 of ShowCredential binds the revocation token to the revocation value in the credential. Since credentials cannot be forged (by assumption on the credential scheme), the adversary cannot change its revocation value, and hence cannot avoid revocation. A full security model and proof is in the full version of this paper [START_REF] Lueks | Fast revocation of attribute-based credentials for both users and verifiers[END_REF].

Showing Protocol for Idemix

In this section, we give a brief overview of the Idemix [START_REF]Specification of the Identity Mixer cryptographic library[END_REF] attribute-based credential system and how our revocation scheme can be incorporated into it to enable revocation without losing anonymity. We focus on the way our revocation scheme can be incorporated and omit some of the cryptographic details.

In Idemix, a credential is a Camenisch-Lysyanskaya [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF] signature (A, e, v) on the block of messages consisting of the user's private key sk U and the attributes a 1 , . . . , a L . We can easily incorporate an extra attribute containing the revocation value r into the signature:

A ≡ Z S v • R sk U K • R r R • L i=1 R ai i 1/e (mod n),
where the credential issuer's public key consists of the integers Z, S, R K , R R , R 1 , . . . , R L , n. Both sk U and r should be chosen from a large set. The construction of the signature guarantees that the user cannot change any of the values in the exponents. In the issuing protocol, the revocation value r and the private key sk U should be hidden. Given a block of messages sk U , r and a 1 , . . . , a L the validity of the signature can be verified by checking that

Z ? ≡ A e • S v • R sk U K • R r R • L i=1 R ai i (mod n).
When the signature is part of a credential scheme, some of these values can never be shown to the verifier as they would make the credential linkable. Instead, during verification the user uses the following two functions to show a credential anonymously. First, the user randomizes the signature to ensure unlinkability. Second, the user selectively discloses only those attributes appropriate for the application (the private key and the revocation value are never revealed).

A user randomizes the value A of a signature (A, e, v) as follows. If (A, e, v) is a valid signature on sk U , r and a 1 , . . . , a L , then ( Â, e, v) is also a valid signature where  := A • S -(mod n), v := v + e for any randomly chosen (in some large interval). This does not yet provide unlinkability by itself-e remains unchanged-but the selective disclosure proof described below also hides the value e.

The selective disclosure protocol is a (non-interactive) zero-knowledge proof constructed by the user. Such a proof reveals a subset of the attributes determined by the index set D and proves that a (randomised) signature contains these attribute values. To make revocation possible, we also include a predicate that demonstrates that (a) the revocation token R was honestly computed using the generator g ε,V and (b) the revocation value r corresponds to this credential. The proof is as follows: 7 P K (e, v, sk U , r, (a i ) i / ∈D ) :

Z i∈D R -ai i ≡ Âe S v R sk U K R r R i / ∈D R ai i (mod n) ∧ R = g r ε,V in G .
In the congruence above, all the exponents on the left-hand side are known to the verifier (selectively disclosed attributes (a i ) i∈D ), while the exponents on the right-hand side remain hidden and the user only proves knowledge of them. The above proof realizes the user's side of steps 4 and 5 in the ShowCredential algorithm-see Section 4.

Implementation

We now address some implementation challenges when using our revocation scheme.

Obtaining revocation information

To revoke a credential, one needs to know its revocation value. However, this value also introduces a privacy risk: the party that stores it could revoke the credential and hence detect its use. Many revocation schemes suffer from this problem, see Section 7. We discuss three options for storing and using revocation values. In all cases, the user herself generates the revocation value. The issuer will include this revocation value in the credential without ever learning its value. 8 Option 1: only the user knows the revocation value. The privacy of the credential owner is best protected when only she knows the revocation value. When she loses her credential, she reveals the revocation value to the RA, who then uses this to revoke the credential. To get even better privacy, she can calculate the future revocation tokens herself. This is computationally intensive, but lowers the trust in the RA significantly.

When a smart card acts on behalf of the user, there is another difficulty to overcome: how does the user access the revocation values when the card is lost or stolen? We 7 We use a simplified version of the Camenisch-Stadler notation [START_REF] Camenisch | Efficient Group Signature Schemes for Large Groups[END_REF] for zero-knowledge proofs of knowledge. Only the prover knows the values in front of ':', other values are also known by the verifier. We also omited the range proofs; see the Idemix specification [START_REF]Specification of the Identity Mixer cryptographic library[END_REF] for details. 8 The method for encoding these attributes is similar to the 'blind' encoding of the user's private key in a credential. Idemix and U-Prove support this.

propose to use a trusted terminal to print the (card-generated) revocation values (for example, as a QR code) when the credential is issued. The user can then store the revocation values separately from the card and use them to revoke credentials.

Option 2: a trusted third party stores revocation information. A second option is for a (possibly distributed) trusted third party (TTP) to store the revocation values. During issuance, the user creates not only a revocation value, but also a verifiable encryption [START_REF] Camenisch | Practical Verifiable Encryption and Decryption of Discrete Logarithms[END_REF] of the revocation value (for example, Idemix supports this). The user proves that the TTP can decrypt its revocation value, and the issuer verifies this proof before issuing the credential to the user. Hence, the user cannot avoid revocation later on.

In theory, this allows the TTP to revoke a credential when it is abused. However, the credentials do still provide anonymity, so it is not easy to pinpoint the abuser. This is where the final option comes in.

Option 3: revocation information is escrowed during showing. For the third option, the user escrows the revocation value during a showing proof using verifiable encryption. When abuse is detected, the ciphertext can be used to recover the revocation value and thus revoke the user. The latter two solutions do reduce the efficiency of the underlying credential scheme, and introduce a lot of trust in the third party. In practice, one has to weigh whether it is better to accept some abuse or to decrease efficiency and privacy.

Instantiating epochs

To keep the protocol description simple, we assumed that all parties are aware of the current epoch. To achieve this, epochs are, in practice, based on time. The revocation authority determines the length of an epoch, by specifying its start time t s and end time t e , so the current epoch ε is modelled by the tuple ε = (t s , t e ).

In step 2 of the ShowCredential protocol, the user checks that t s ≤ t ≤ t e where t is the current time. If this equation is not correct, the user aborts. In this way, users always use the correct generator.

Embedded devices

The above description does not suffice for smart cards, our target platform, as they lack a built-in clock, and thus have no notion of time. Nevertheless, an embedded device must also be able to calculate the generators itself, to prevent a verifier from adversarially choosing them.

We propose the following solution, similar to the method used in Machine Readable Travel Documents, like the new European passport [START_REF]BSI: Advanced security mechanisms for machine readable travel documents -extended access control (eac)[END_REF]. The embedded device keeps track of an estimate t * of the current time. The estimate is always at or before the current time. Every time the embedded device interacts with a verifier, it 1. receives a description of the current epoch (t s , t e ) signed by the RA; 2. confirms that the epoch (t s , t e ) is possible given its time estimate t * by checking that t * ≤ t e (this is done in step 1 of the ShowCredential protocol); and 3. updates its estimate t * ← max(t s , t * ) if the signature is valid.

The signature by the revocation authority on the epoch makes it impossible for verifiers to trick the device into creating a too futuristic estimate t * of the current time.

How to choose the epochs

Epochs determine during what period a credential is linkable. Ideally, at most one showing happens at each verifier within an epoch. The period between two showings wildly differs among applications. For example, a citizen credential may be used only a couple of times a year for filing tax returns with the government, while it may be used weekly to prove having reached legal drinking age in a pub or a store. A credential for accessing an online newspaper subscription could even be used daily.

At the same time, computing revocation lists for every epoch can become computationally intensive and transferring uses bandwidth. Therefore, we propose not to have a global epoch, but instead create epochs per verifier. The length of the epoch should be chosen in such a way that no credential is normally reused within the epoch for that particular verifier. 9 Using time to instantiate epochs (as described in Section 6.2) allows us to use verifier-specific epochs easily.

Experiments

We did two experiments to prove the validity of our scheme: we estimated the performance impact on an existing smart card implementation and tested the impact on the revocation authority. As the extra work for the verifier is extremely small, we did not measure its overhead.

Fast smart card implementation

We estimate the efficiency of this scheme based on the work by Vullers and Alpár [START_REF] Vullers | Efficient Selective Disclosure on Smart Cards Using Idemix[END_REF] in the IRMA project. To assess the performance of the implementation, we compare it to its version without revocation. As described in Section 5, we add an extra attribute to every credential to hold the revocation value.

As group G, we use the quadratic residues modulo a 1024-bit safe prime (this is somewhat small, but matches the security level used in the implementation of Vullers and Alpár [START_REF] Vullers | Efficient Selective Disclosure on Smart Cards Using Idemix[END_REF]). This group is cyclic and the DDH problem is hard. Furthermore, hashing onto this group is easy. It takes five 256-bit hash calculations (to get a statically uniformly random element) and a squaring (which can be precomputed as part of the revocation value). Calculating a 256-bit hash takes about 10 milliseconds. We estimate a total extra time of 390 milliseconds for including the revocation value as an attribute, generating the revocation token and adding the equality proof [START_REF] De La Piedra | Towards a Full-Featured Implementation of Attribute Based Credentials on Smart Cards[END_REF]. This is very practical. Since showing a credential takes 1.0-1.5 seconds, the overhead is limited too.

We did not implement the verification of the certificate for the epoch yet, but we believe that the cost of doing this to be approximately 150 milliseconds.

Fast revocation list calculation

The main remaining burden of the revocation scheme is on the revocation authority, which has to generate revocation lists for all verifiers, and has to do so for each epoch. This can amount to a large number of exponentiations. However, the reader should be aware that the amount of work the revocation authority has to do per generator (i.e., per epoch and per verifier) equals the work that a verifier has to do for every verification in the standard VLR setting.

We implemented the calculation of the revocation list to confirm that this approach is valid. The efficiency of this calculation depends on the group. For the Idemix setting, we created a (non-optimized) implementation that calculates about 7 500 revocation tokens per second. However, one can do much better, as is shown by our optimized implementation for the ECC library by Bernstein et al. [START_REF] Bernstein | High-speed high-security signatures[END_REF]. This implementation calculates about 50 000 revocations per second. These results show that even for large scale systems revocation lists can be generated sufficiently fast.

The size of a revocation list

At the start of every epoch, verifiers retrieve new revocation lists. It might seem that when the revocation lists are big, the storage and transfer costs become prohibitive. This is not the case. Since our scheme does not do group operations on revocation tokens, it suffices to store their hashes. Furthermore, if one is willing to accept a false positive rate of 10 -7 , Bloom filters [START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] reduce the storage requirements by another order of magnitude. This allows, for example, 250000 elements to be stored in only 1 MiB.

Related Work

Revocation has been widely studied in the literature; we refer to, for example, Lapon et al. [START_REF] Lapon | Analysis of Revocation Strategies for Anonymous Idemix Credentials[END_REF] for a nice overview of current revocation techniques for attribute-based (Idemix) credentials. Traditional revocation techniques, like CRLs and OCSPs, require credentials to have a unique identifier that is always visible to the verifier. A certificate revocation list (CRL) [START_REF] Cooper | Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile[END_REF] is a list of revoked credential identifiers, published by the issuer. Alternatively, the verifier can ask the issuer if a credential is still valid using the Online Certificate Status Protocol (OCSP) [START_REF] Santesson | X.509 Internet Public Key Infrastructure Online Certificate Status Protocol -OCSP[END_REF]. Both situations require the credential to be recognizable, which is undesirable for ABCs. However, revocation is fast: there is no extra work required on the side of the user, and the verifier can test validity in constant time.

Domain-specific pseudonyms [START_REF] Brands | A Practical System for Globally Revoking the Unlinkable Pseudonyms of Unknown Users[END_REF][START_REF]Specification of the Identity Mixer cryptographic library[END_REF][START_REF] Kutylowski | Restricted identification scheme and diffie-hellman linking problem[END_REF] only slightly improve the situation: instead of being globally linkable, different uses are only linkable by the same verifier, but not across different verifiers. We believe this still weakens the unlinkability too much.

We now focus our attention on solutions that do offer sufficient privacy guarantees for the user. Table 1 compares these schemes with our scheme and the CRL scheme. A digital accumulator is a constant-sized representation of a set of values. Every value in the accumulator comes with a witness, which enables efficient membership checks. Camenisch and Lysyanskaya [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF] proposed an updatable accumulator that can be used for revocation. A credential is unrevoked as long as it appears on the whitelist, represented by the accumulator. Another approach is to accumulate revoked credentials to create a blacklist. A credential is unrevoked if it is not on this blacklist [START_REF] Li | Universal accumulators with efficient nonmembership proofs[END_REF][START_REF] Nguyen | U-prove designated-verifier accumulator revocation extension[END_REF].

Table 1. We compare CRLs [START_REF] Cooper | Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile[END_REF], accumulators [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF][START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF][START_REF] Nguyen | U-prove designated-verifier accumulator revocation extension[END_REF], traditional VLR schemes [START_REF] Ateniese | Quasi-Efficient Revocation in Group Signatures[END_REF][START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF][START_REF] Brickell | The DAA scheme in context[END_REF], VLR schemes with backward unlinkability (VLR-BU) [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF], blacklistable anonymous credentials (BLAC) [START_REF] Tsang | Blacklistable Anonymous Credentials: Blocking Misbehaving Users without TTPs[END_REF], and our scheme. We compare the complexity of the operations and data transfers. A proving time of 1 means that it is constant, while a proving time of |RL| means that it scales linearly with the size of the revocation list. Of all the constant-time proving schemes, the accumulator has the biggest overhead. Our scheme is the only privacy-friendly scheme that has constant-time proving and verification while users do not need to receive updates. Accumulators change. For whitelists, this is after an addition; for blacklists, this is after a revocation. Thus users need to receive updates (for schemes like Camenisch et al. [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF], these updates are public and can be provided by the verifier) and process them, inducing extra load on carriers like smart cards. Additionally, the (non-)membership proofs are expensive. Lapon et al. [START_REF] Lapon | Analysis of Revocation Strategies for Anonymous Idemix Credentials[END_REF] show an overhead of 300% in the showing protocol. Other schemes, like Libert et al. [START_REF] Libert | Group signatures with almost-for-free revocation[END_REF] are equally inefficient, making them impractical.

CRL Accumulators

Where accumulators place the load on the users-who need to get new witnesses after revocations or additions-and the revocation authority-who needs to create those witnesses-verifier-local revocation (VLR) [START_REF] Ateniese | Quasi-Efficient Revocation in Group Signatures[END_REF][START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF][START_REF] Brickell | The DAA scheme in context[END_REF] places the majority of the load at the verifier. As we saw in Section 2, the verifier needs to do a check that is linear in the length of the revocation list, however, apart from sending the extra revocation token, the extra work for the user is minimal.

A downside of traditional VLR schemes is that once a user is revoked, all of its transactions (also past ones) become linkable. Nakanishi and Funabiki [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] proposed a VLR scheme that is backward unlinkable, like our scheme. Similar to our scheme, they create different revocation tokens per epoch, so that verifiers cannot use the revocation token for the current epoch and apply it to earlier ones. However, their scheme is still linear in the number of revoked users, and needs to perform a pairing operation per revoked user. This makes it less efficient than previous and our solutions. The security of their scheme hinges on the fact that the per-epoch revocation tokens are maintained by a trusted party. It thus requires the same trusted party as our scheme does.

Finally, blacklistable anonymous credentials (BLAC) [START_REF] Tsang | Blacklistable Anonymous Credentials: Blocking Misbehaving Users without TTPs[END_REF] take a different approach to revocation: misbehaving users can be blacklisted without requiring a TTP to provide a revocation token. In every transaction, the user provides a ticket, similar to our revocation token, that is bound to the user. To blacklist a user, the verifier places this ticket on the blacklist. In the second step of the authentication, the user proves that her ticket is not on the blacklist. The complexity of this proof is linear in the number of items on the blacklist, so this scheme places a high load on the user. Even if a user's credential is revoked, the verifier does not learn her identity, nor can the verifier trace her.

Discussion and Conclusion

Our revocation scheme is fast. It can be combined with ABC showing protocols and can be fully implemented on a smart card. It incurs minimal overhead, while at the same time the revocation check can be performed efficiently by the verifier. We created a security model for our scheme and proved that our scheme is forward secure as long as the revocation authority is trusted. The proofs are included in the full version of this paper [START_REF] Lueks | Fast revocation of attribute-based credentials for both users and verifiers[END_REF]. We showed that we can remove this trust assumption when the users calculate the revocation tokens themselves.

To obtain this speedup, we traded some traceability, but with an appropriate choice of epoch length this should not be a problem in practice. The fact that this enables us to create a revocation system that is truly practical makes this a worthwhile trade-off.

We believe our scheme is a valuable contribution to making large scale attributebased credentials possible. It would be interesting to investigate protocols that further reduce the trust assumption on the revocation authority.

  The user keeps track of the current epoch ε. She also stores sets T C of the verifiers that she has shown credential C to in this epoch. Initially, T C = ∅.

  VLR VLR-BU BLAC Our scheme

	User can be offline		×
	Data to verifier
	per epoch	|RL|	1	|RL|	|RL|	|RL|	|RL|
	per update	1	1	1	1	1	1
	Proving (time)	1	1	1	1	|RL|	1
	Verifying (time)	1	1	|RL|	|RL|	|RL|	1
	Security	-	+	+/-	+	+	+

This is why we prefer the term 'attribute-based credentials' over the more traditional term 'anonymous credentials'.

See http://www.irmacard.org.

The credential must be able to encode a revocation value r from a sufficiently large set.[START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] This value can identify a credential if it is revoked. We use the notation C(r) to denote a credential that contains the revocation value r. Depending on the type of credential, other attributes may be present.

The issuer should be able to issue a credential C(r) without learning the revocation value r. Otherwise, the issuer can use it to trace credentials. Most credential schemes support blind issuing, which makes this possible.[START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] For simplicity, we focus on attribute-based credentials, but this is not strictly necessary. Any credential scheme that can encode the revocation value and that satisfies the second restriction can be used with our scheme. One example would be to use the user's private key as the revocation value.

GetRevocationList() This protocol is run between a verifier V and the revocation authority. The parties execute the following steps:1. The verifier V authenticates itself to the revocation authority.[START_REF] Brands | A Practical System for Globally Revoking the Unlinkable Pseudonyms of Unknown Users[END_REF] 2. The revocation authority (a) calculates the generatorg ε,V = H(ε V ) ∈ G for verifier V ; (b) computes the sorted list RL ε,V = sort({g r ε,V | r ∈ MRL}); and (c) sends RL ε,V to verifier V.[START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF] As we explain in Section 6.2, epochs are represented as time intervals. Users test their knowledge of the current time against this interval to make sure the interval is not in the past.[START_REF] Brands | A Practical System for Globally Revoking the Unlinkable Pseudonyms of Unknown Users[END_REF] The verifier reuses the authentication mechanism in the credential scheme.

For this purpose, it suffices to sort on the representation of the elements. All that matters is that the order depends only on information in the list itself.

Note that when a user does use her credential more often within the same epoch a lot of anonymity remains. The uses within this epoch are linkable, but they are still unlinkable to uses in other epochs or at other verifiers. In particular, this will usually not reveal the user's identity.


Francisco Vigário

Miguel Neto

Diogo Fonseca
email: diogompaf@penhas.di.ubi.pt

Mário M Freire

Pedro R M Inácio
email: inacio@di.ubi.pt

Assessment of the Susceptibility to Data Manipulation of Android Games with In-app Purchases

Keywords: Android, Data Manipulation, Integrity, Mobile Operating System, Security, Storage

This paper describes a study for assessing how many free Android games with in-app purchases were susceptible to data manipulation via the backup utility. To perform this study, a data set with more than 800 games available in the Google Play store was defined. The backup utility, provided by the Android Operating System (OS), was used to backup the app files into a Personal Computer (PC) in order to find and manipulate sensitive data. In the cases where sensitive data was found, the applications were restored and the games tested to assess if the manipulation was successful and if it could be used to the benefit of the user. The results included show that a significant percentage of the analyzed games save the user and app information in plaintext and do not include mechanisms to detect or prevent data from being modified.

Introduction

In the last few years we have witnessed an significant growth in the use of mobile devices [START_REF] Pieterse | Android botnets on the rise: Trends and characteristics[END_REF]. The massive adoption of these devices led several companies, as Google and Apple, to direct their efforts into the development of mobile Operating Systems (OSs), driven by the needs of users. Along with these OSs, they also provide app stores, (Google Play [START_REF]Google: Google Play (20[END_REF] and Apple Store [3]), which offer point and click access to commercial or free applications to their users. Internetworking is also increasing with the adoption of mobile devices, all contributing to a rich and heterogeneous environment where sensitive data is sometimes flowing in the network, or stored in mobile devices in an insecure manner. This data is a tempting target for malicious users or developers, which try to exploit vulnerabilities to steal it or manipulate it for their own profit.

Similarly, to traditional computer software, games comprise a substantial part of the revenue of this industry, reflected either in number of existing games or in the effort to develop them. There are several business strategies for such applications and, in the case of mobile applications, some developers prefer to provide their games for free, to then offer the users the possibility to expand the game or add functionalities in return for a payment or several micro-payments. These are nowadays known as in-app purchases. Many developers choose to ask for a fee during the installation process. Sometimes, the applications come with the additional functionalities already implemented, but blocked. Some programming logic prevents the user from accessing those parts of the application before the purchase. This programming logic may be based on the values of variables, which are stored as app information in the internal storage of the device. As such, it is often assumed that the internal storage is protected (e.g., by the OS) against manipulation by other applications, and difficult to directly access by the user.

In mobile applications, in-app purchases are used to remove advertisements included in the free versions of apps, and add additional advanced or premium functionalities. In the case of Android games, which are addressed in this work, these purchases can also be used to unlock additional levels, get extra points, progress faster in the game and obtain hidden items, apart from the aforementioned ones. This mechanism is, thus, an important block in the business model of developers.

This paper describes a study concerning the possibility of accessing and manipulating internal data storage of Android games with in-app purchase, using the backup utility provided by the Android OS. The data set used for this analysis consists of more than 800 free games offering in-app purchases, which were downloaded from the Google Play store. All games of the data set were subject to human analysis after their installation in a non-rooted smartphone and transfer to a Personal Computer (PC). The procedure includes backing up the applications to a PC, searching for interesting data, changing it, and restoring the application back to the smartphone, to then assess if the behavior of the game changes as a result of the manipulation. The results show that a notable part of the analyzed games are susceptible to data manipulation, which can be easily exploited by users. Sometimes, the procedure applied in the scope of this paper may be applied, by typical users, to enjoy blocked functionalities without paying for them. Results clearly show that developers should pay more attention to data integrity and encryption mechanisms in mobile OSs. This paper is structured as follows. Related works and the motivation underlying this study are included in section 2. Section 3 discusses the data set used in the scope of this work and elaborates on the type of applications used. The method used to perform the analysis is described in detail on section 4. Section 5 discusses the results of the analysis, as well as the number and type of applications that are susceptible to data manipulation using the described method. The main conclusions and some lines of future work are described in section 6.

Due to the popularity of the Android OS and also to the personal nature of mobile devices, security involving this OS is nowadays a hot research topic. The sub-topic discussed herein is also receiving a lot of attention lately, as shown by the recent works on this area, discussed below. In 2011, the non-for-profit organization Open Web Application Security Project (OWASP) began a project with focus on threats to the mobile environment. At the end of 2014, the threat occupying the first position of the OWASP Top 10 Mobile Risks was Weak Server Side Controls, with Insecure Data Storage and Insufficient Transport Layer Protection coming up next in the second position [START_REF]OWASP: Projects/OWASP Mobile Security Project -Top Ten Mobile Risks -OWASP[END_REF], which also motivated this work.

C. Håland, in his Masters thesis entitled An Application Security Assessment of Popular Free Android Applications [START_REF] Håland | An Application Security Assessment of Popular Free Android Applications[END_REF], includes a study of 20 popular free applications, testing them for the OWASP Top 10 mobile risks. He found several vulnerabilities of this list in the applications, namely Insecure Data Storage, Weak Server Side Controls, Insufficient Transport Layer Protection, etc. The author states that most of the attacks were only possible in rooted devices. For example, he mentions that, with root privileges, the owner of the device can access any file or folder, which comprises a Insecure Data Storage problem. He was able to change the value of the coins used in the 4Pics1Word game, without paying for that feature, by simply searching the files storing the status of the application. Wordfeud Free was another application with a similar problem but, in this case, he was able to retrieve the username and password of the Facebook account that was used to login in the application, because the credentials were stored in plaintext in an Extensible Markup Language (XML) file.

C. Xiao, a researcher in Palo Alto Networks, delivered a talk entitled Insecure Internal Storage in Android in the Taiwan Conference (HITCON) [START_REF] Xiao | Insecure Internal Storage in Android -Palo Alto Networks BlogPalo Alto Networks Blog[END_REF] regarding the subject at hands. He processed a total of 12,351 applications downloaded from Google Play, having concluded that, from these applications, only 556 were not allowing backup by means of the backup utility, and that only other 156 applications were implementing a BackupAgent to protect the data. In other words, approximately 94,2% of the most popular applications allow transferring the package and all the internal storage files to a computer in a packed format. The authorization to backup applications can be set up by adjusting the android:allowBackup property to true or false in the manifest file. His study was focused on the applications with at least 500,000 downloads. The idea of manipulating data from Android apps via the backup utility was already circulating in specialized forums and its genesis is hard to obtain.

In the Masters thesis entitled Android Application Security with OWASP Mobile Top 10 2014 [START_REF] King | Android Application Security with OWASP Mobile Top 10[END_REF], James King analyzed the FourGoats Android application, in which he identified several types of vulnerabilities, including Insecure Data Storage. The version of the application under analysis was using a local database file to store the credentials of the users in plaintext, and an attacker with physical access to the device could thus obtain them, even without root privileges (e.g., using the method described in section 4). In the Masters the-sis, the author also describes problems related with Insufficient Transport Layer Protection, stating that the majority of the applications selected for analysis were not using encryption to transmit data over the network, which leaves them vulnerable to Man-In-The-Middle (MITM) attacks. In some cases, the credentials of users could also be obtained from traffic sniffing (because they were sent unencrypted). Other vulnerabilities discussed in this study include Poor Authorization and Authentication, Broken Cryptography, Improper Session Handling and Lack of Binary Protections related problems.

In [START_REF] Fahl | Why eve and mallory love android: An analysis of android ssl (in)security[END_REF], Fahl et al. tried to assess how, and to which extent, Secure Sockets Layer (SSL)/Transport Layer Security (TLS) was being used to protect the contents of network communications from Android applications. The inadequate usage or integration of the protocol could be as serious as not using it at all, and both situations lead to MITM related vulnerabilities. In the scope of their work, the authors developed MalloDroid, which is a small tool that can be used to find broken SSL certificate validation procedures in Android apps. A total number of 13,500 popular free apps downloaded from Google Play were then analyzed with this tool. They concluded that approximately 8% of the analyzed applications (1,074 apps) were potentially vulnerable to MITM attacks.

This paper is focused on the manipulation of locally stored data (no MITM attacks were performed). Nonetheless, the procedure described herein may be combined with MITM attacks to perhaps obtain an even higher success rate, since it was noticed that some apps were using the network to store values and to detect data modification.

Data Set

The analysis described in this paper was performed on a fairly large data set of Android games, which are free to download but have the in-app purchase characteristic. Even though simple tasks of this work used automated scripts, most of the analysis was performed manually, meaning that all games were subject to human analysis. The data set was collected between September and November of 2014 and it is consists of 849 games from the 15 different categories defined in Google Play for this type of software [START_REF]Google: Google Play (20[END_REF]. Table 1 summarizes the number of games-per-category considered in the analysis. Although some applications without in-app purchases were also analyzed in the meantime, they were not considered in the scope of this particular work, because the main objective was to evaluate whether a user could use the method described below to use premium or paid functionalities without purchasing them, i.e., by only modifying internal data.

Prior studies on Android OS security (e.g., [START_REF] Barrera | A methodology for empirical analysis of permission-based security models and its application to android[END_REF][START_REF] Enck | On lightweight mobile phone application certification[END_REF][START_REF] Felt | Android permissions demystified[END_REF][START_REF] Felt | The effectiveness of application permissions[END_REF]) have mainly focused their analysis on the most popular apps available in Google Play (or Android Market, as it was designated previously). This work takes the number of downloads into account in the analysis of the results, but the popularity of the applications was not considered when choosing the games for installation. As such, our approach differs from some of the previously described ones in two ways: (i) all applications were subject to manual analysis, so that minor details concerning the way that data was stored by different applications was not overlooked;

(ii) the study is not limited to popular or to a small set of applications.

In order to give an idea of the popularity of the games comprising the data set, Table 2 shows the number of games in the data set for each of the 11 different download intervals defined by Google Play. A large slice of the data set was in the 1 to 5 billion download interval (approximately 35%), and approximately 71% had more than 1 billion downloads.

Notice that, not limiting the data set to the most popular games also provided a way to later on assess if there was an obvious relation between popularity and the problems related with Insecure Data Storage.

Number of Downloads

Number of Games-per-Interval 100 000 000 -500 000 000 13 50 000 000 -100 000 000 16 10 000 000 -50 000 000 111 5 000 000 -10 000 000 110 1 000 000 -5 000 000 296 500 000 -1 000 000 106 100 000 -500 000 157 50 000 -100 000 23 10 000 -50 000 11 5 000 -10 000 4

1 000 -5 000 2

Method

The method to perform the analysis described in this paper required the usage of a smartphone and a PC with specific software installed. The smartphone was running a non-rooted Android OS (version 4.4.2). Nonetheless, any version of the OS higher than 4.0.0 would suffice for all purposes of this work, since the backup utility (which is critical for the method) was provided natively from that version on [START_REF]Android Developers: Dashboards -Android Developers[END_REF]. As further explained below, a snapshot of each analyzed game needs to be copied to the PC. This was done via an Universal Serial Bus (USB) cable and the communications were managed by the Android Debug Bridge (ADB) tool [START_REF]Android Developers: Android Debug Bridge[END_REF], which was installed in the computer. The PC was running a Linux based OS also, with the following tools installed: pax, tar, OpenSSL, dd and grep. Some of these tools (e.g., OpenSSL and grep) come natively with most of the Linux distributions available, while others are very simple to obtain, e.g., via package managers. These tools were used to handle the package transferred from the smartphone. Typically, OpenSSL is used to perform cryptographic tasks but, in this case, it was used to compress and decompress packages resorting to the zlib library. pax was used to read and write files and copy directory hierarchies. dd and tar were responsible for converting and extracting files with the .tar format, respectively. Finally, grep was used for searching patterns in the data files of an application. After the establishment of the initial setup and installation of the tools described above, a set of steps to explore the data storage problems was applied. The method can be divided into 10 different steps. Each step resorts to a set of commands, which are entered in a traditional shell. It should be emphasized that, apart from the already available and aforementioned tools, no particular secondary application needs to be developed to apply this method, and parts of it can be found online in specialized forums (e.g., [START_REF] Forums | How to extract, create or edit android adb backups -Android Development and Hacking -XDA Forums[END_REF]), which contributes to the severity of this problem. The method explained below presumes that the game to be analyzed was previously installed in the system. The steps are described with more detail as follows:

1. The first step consists of connecting the mobile device to the computer via USB. The debug mode should be active when the connection is performed (or needs to be activated on the device). The OS normally asks the user to allow the communication in debug mode, exhibiting a dialog with an RSA public key fingerprint, as shown on Figure 1a. The connection needs to be explicitly allowed for the method to work. 2. The app backup to the computer is performed in the second step, by issuing a command similar to the following one in the terminal:

adb backup -f data.ab -apk PATH
The PATH parameter represents the fully qualified path of the game in the smartphone internal storage. This command will trigger the backup utility in the Android OS, illustrated on Figure 1b, that asks the explicit permission to perform the backup operation for that app. An optional password for encrypting the package may be provided.

Once the command is successfully executed, a compressed and non-encrypted archive (in this case referred to as data.ab), which contains a small header with 24 bytes, and the files composing the app, is transferred to the PC. 3. The third step consists of removing the header and converting the data.ab into a tar file, so as to enable the extraction of the compressed files in the subsequent step. This can be achieved by piping the following commands: This will enable packaging the application back perfectly after file manipulation and before restoring. 5. The fifth step is the one were the data.tar archive is decompressed using a command similar to the next one:

dd if=data.ab bs=1 skip=24 | openssl zlib -d | tar -xvf - 6.
The sixth step is where one tries to manipulate the data of the application. This work was just focused on trying to change data that could enable accessing paid functionalities or changing the behavior of the game without paying for them. For example, we were interested in changing the number of coins in a game. To achieve this objective, a simple procedure based on human analysis of the files and resorting to the grep tool was applied with commands similar to:

grep -R "xxx" app/PATH/ Several strategies were adopted to try to find out the interesting values. Some were based on thorough (human) analysis of the files. Another one, which proved to be very successful, consisted in playing the game in the smartphone for a limited period of time, leaving it with a given number of coins or in a given game level (which are numbers). Afterwards, those numbers were searched in the data files of the application using grep and all occurrences were further analyzed and manipulated. For example, we would legitimately play a game until 1234 coins were generated, to then look for and modify that value in this step. Sometimes, the sqlite3 tool had to be used to perform the modification, as some apps use sqlite3 to store the data. This stage included the modification of XML, sqlite, JavaScript Object Notation (JSON) and text files. 7. The seventh step begins the app restore process. First of all, it is necessary to compress all app files in the exact same order they were decompressed using the information saved in the data.list file: cat data.list | pax -wd > newdata.tar 8. The header that was previously stripped out needs to be properly inserted again so that the file has the right format, using:

echo -e "ANDROID BACKUP\n1\n1\nnone" > backup.ab 9. The application can then be compressed and concatenated to the end of the backup.ab file, which already contains the header:

openssl zlib -in newdata.tar >> backup.ab

The backup.ab is an archive compatible the Android OS. 10. The last step consists of issuing the command to restore the archive to the device, which will trigger a dialog similar to the one in Figure 1b.:

adb restore backup.ab
Notice that, all previous steps were performed on each one of the games included in the data set. After concluding the last step of the method successfully, the game was once again executed in the Android OS and it was assessed if the data modifications were producing the expected results. Sometimes, this procedure was repeated several times, to minimize the possibility of having overlooked some minor artifact. If the behavior of the game was changed without detection (some games detect modifications by storing values in the network) as a consequence of the manipulation, it was considered vulnerable. The results are discussed below.

The data set used in the scope of this work is constituted by 849 free (to download) games with the in-app purchase characteristic. From those 849, a total of 148 were susceptible to data manipulation performed using the method described in section 4, which corresponds to 17,43% of the tested games. This percentage is significant, taking into account that it refers to cases where developers are dependent of that specific income (the game is free to download, only the add-ons are paid). Also, worth of note is the fact that the method does not depend, in any way, of having the OS rooted or not and that the tools to perform data modification are readily available. Actually, it would be easy to automate the described method and pack the required tools to construct a program for cracking a given game, based on these findings.

The chart in Figure 2 compares the number of games that were found to be susceptible to data manipulation with the total number of games in the data set for each one of the Google Play categories. The results suggest that Trivia is the most affected category (with 50% of vulnerable games), but it is also one of the ones containing fewer games (only 6). Some of these games work both online and offline, and the paid add-ons are often aids to which the user may resort to answer questions right. In the vulnerable games, it was noticed that the access to such functionalities was controlled by values stored in plaintext files without any integrity mechanism. After Trivia, the two categories with the most expressive results were Racing and Arcade, where 28% and 26% of the games were susceptible to data manipulation, respectively. In these types of games, the paid add-on or functionality is also normally comprised by means to have more virtual money or faster ways to progress in levels, namely by buying certain virtual items. The results derive from the fact that the money balance of a game is frequently stored in plaintext XML or text files, or in SQLite databases, without integrity or authentication codes, which are easy to find and modify.

The categories of Role Playing, Family and Music had no vulnerable games. These results are mostly due to the fact that, in this type of games, in-app purchases are used to remove advertisements or to, for example, buy the whole game or expansions (new levels, weapons or characters). In such cases, the purchase typically requires downloading new files (or a new version of the game) to the system and, therefore, these files were not previously available for manipulation. Purchases requiring the user to interact with a remote server are inherently less susceptible to data manipulation because, in such cases, it is not about changing the flow or status information of the application. Role Playing games usually have a higher longevity, and they are updated more times than, e.g., Arcade games. Some updates address previously known issues, namely the ones related with Insecure Data Storage when crack tools leak into the Internet. Probably, the effort in implementing security features in these categories is larger.

The Cards and Strategy categories had 2.9% and 6.5% of the games susceptible to data manipulation, respectively. These low values are related with the fact that both types of games are typically played online, which means that application information is either stored remotely or checked frequently against the last known (or normal) snapshot of such values. Some games allowed changing some app related values in the PC, but they were then restored when the connection was again established.

In order to assess if there was a relation between the popularity of a game and its susceptibility to data manipulation, an analysis similar to the previous one was conducted for the same data set segregated by number of downloads. The chart in Figure 3 summarizes this part of the work.

The most vulnerable games are the ones with the number of downloads in the ranges 5000-10000 and 50000-100000, though the first interval only contained 4 games (of which 2 were vulnerable to the method applied herein). In the second interval, 7 games were vulnerable, corresponding to approximately 30% of the total number of games in that range. The results suggest that the number of vulnerable games is not dependent of their popularity, even though no vulnerable games were found in the range 50000000-100000000 (there were only 16 games in this interval). In the range with most of the games (1000000-5000000), 15.4% were vulnerable to data manipulation, which corresponds to 46 games in a total of 296.

Focusing only on the vulnerable games, Figure 4 emphasizes the type of files used to sale application data in the internal storage of the Android OS. As shown in the pie chart, 76% of the vulnerable games resort to XML files, while 9% use SQLite databases and 14% use .txt or JSON files. This distribution was expected since XML comprises a simple and standard format for storing data and, in Android, one of the suggested storage options for saving application 0 50 100 150 200 250 300 1 0 0 0 0 0 0 0 0 -5 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -5 0 0 0 0 0 0 0 5 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 -5 0 0 0 0 0 0 5 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 0 0 -5 0 0 0 0 0 5 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 -5 0 0 0 0 5 0 0 0 -1 0 0 0 0 1 0 0 0 -5 0 0 0

Number of Games

Number of Downloads

Number of Games Analyzed Number of Games Vulnerables

Fig. 3: Total number of games versus the number of games susceptible to data manipulation, segregated by popularity. related data is known as Shared Preferences, which is used to save values from primitive JAVA types in XML format. Nonetheless, these results also show that manipulation is possible in a variety of formats. Data stored within SQLite databases is also stored in ASCII, except if encoded using application logic, which also enables one to easily find patterns in the files. Finally, it should be mentioned that only 21 games, corresponding to approximately 2.5% of the data set, had the property android:allowBackup set to false in the AndroidManifest.xml. By default, this property is set to true, which means that, if the developer does not explicitly adjust it to false, the game will be inherently more prone to the method described herein. The possibility to backup an application is a commodity utility for the user and it makes sense to exist. The problem is that it can be easily exploited with different intentions. Setting the aforementioned property to false will solve the problem in non-rooted OSs, but legitimate users may miss the functionality. Apart from that, such setting would not solve the issue in rooted OSs.

Due to the reasons mention in the previous paragraph, integrating data integrity mechanisms into the application may comprise the best means to address this issue or, at least, make the exploitation more difficult. For example, developers may use hash functions, Message Authentication Code (MAC) or digital signature algorithms to calculate and store digests, MACs or signatures for the files where the sensitive data is stored (databases, text or implementation files, etc.). Encrypting the files will have a similar effect. Nonetheless, this imposes some additional computational burden, since the application needs to calculate the aforementioned codes when the contents of the files change and verify them at each execution. If encryption is used, the application needs to decrypt and encrypt the data before accessing or storing it in the files, respectively. Since the cryptographic secrets, used in these mechanisms, need to be available for the application, a specially motivated attacker may still try to manipulate the data by finding the keys and the data integrity mechanisms. If the cryptographic secrets are transferred with the backup, the manipulation is harder to achieve, but still within reach. As such, this topic needs more attention.

Curiously, 3.2% of the games in the data set (corresponding to 27 games) were publicized with the in-app purchase characteristic in Google Play, but had really nothing to buy in the application. In another 3.9% of the data set (i.e., 27 games), the in-app purchase was to remove advertisements or to buy their respective full version, which involves downloading additional files and, as such, they are not vulnerable to data manipulation.

Conclusions and Future Work

This paper is focused on the Insecure Data Storage threat defined by OWASP for mobile devices. It elaborates on the specific problem of manipulating application data from Android games to get free access to paid add-ons or functionalities. Herein, it was discussed that the backup and restore functionalities, provided natively with recent versions of the Android OS, could be used to transfer games to and from a PC, in which they could be tampered to obtain access to the aforementioned add-ons or functionalities. This procedure does not require the system to be rooted, only the users consent (for allowing the USB connection and for transferring the specific application). This procedure is already used by some tools for cheating some games since it can be easily automated for a specific application.

In order to quantify the problem, a total of 849 games offering in-app purchases were downloaded, from Google Play, and then manually analyzed using a method based on searching patterns on the data transferred with the application during the backup. An expressive number of 148 games were found vulnerable to this method, meaning that it was possible to change the application flow or status by searching for ASCII patterns on XML, JSON, txt or SQLite files. Results suggest that the vulnerability is not related with the popularity of the games and we argue that disabling the backup feature for a game should not be seen as a preventive measure against this problem, though it would certainly contribute for its attenuation. The possibility to backup the applications constitutes a commodity utility and it should not be disabled. Data integrity and encryption mechanisms comprise the best mechanisms to prevent Insecure Data Storage problems, like the ones discussed herein.

A possible line of future work consist on performing a similar assessment for other mobile OSs. For example, iOS provides also a means to transfer applications to a PC, e.g., for the cases when the user wants to switch phones.

Another line of work consists of expanding the data set to other types of applications and broaden the scope of the analysis. During the study described herein, a few other (non-game) applications were analyzed and it was found that many of them were saving user related data in plaintext files. Worst than that, some applications were enabling the access to others users online profiles via data manipulation, because they were storing other users information locally. A more detailed analysis is nonetheless required.

  (a) RSA Key fingerprint. (b) Backup utility dialog.

Fig. 1 :

 1 Fig. 1: Screenshots of important steps of the method used in the scope of this work. (a) Screenshot of the RSA key fingerprint dialog for enabling USB debugging from a given computer; (b) Screenshot of the Backup utility provided by the OS.

  dd if=data.ab bs=1 skip=24 | openssl zlib -d > data.tar 4. The fourth step consists of obtaining an exact snapshot of the names of the files and directory structure inside of the data.tar archive with: tar -tf data.tar > data.list

Fig. 2 :

 2 Fig. 2: Total number of games versus the number of games susceptible to data manipulation, per category.

Fig. 4 :

 4 Fig.4: Type of file used to save application data in Android internal storage in vulnerable games.

Table 1 :

 1 Number of analyzed games by category.

								Category
		Action	Arcade	Puzzle	Casual	Strategy	Sports	Racing	Simulation	Adventure	Role Playing	Card	Word	Family	Trivia	Music
	Number of Games	141 138 99 91 91 58 50 39 37 35 34 16 13 6 1

Table 2 :

 2 Number of games in the data set per number of downloads.

Acknowledgements Authors acknowledge the financial support from EyeSee, Lda. This work was performed in the scope of the R&D Unit 50008, financed by the applicable financial framework (FCT/MEC through national funds and when applicable co-funded by FEDER -PT2020 partnership agreement).