Olivier Heen
email: olivier.heen@technicolor.com

Christoph Neumann
email: christoph.neumann@technicolor.com

On the privacy impacts of publicly leaked password databases

Regularly, hackers steal data sets containing user identifiers and passwords. Often these data sets become publicly available. The most prominent and important leaks use bad password protection mechanisms, e.g. rely on unsalted password hashes, despite longtime known recommendations. The accumulation of leaked password data sets allows the research community to study the problems of password strength estimation, password breaking and to conduct usability and usage studies. The impact of these leaks in terms of privacy has not been studied. In this paper, we consider attackers trying to break the privacy of users, while not breaking a single password. We consider attacks revealing that distinct identifiers are in fact used by the same physical person. We evaluate large scale linkability attacks based on properties and relations between identifiers and password information. With these attacks, stronger passwords lead to better predictions. Using a leaked and publicly available data set containing 130 × 10 6 encrypted passwords, we show that a privacy attacker is able to build a database containing the multiple identifiers of people, including their secret identifiers. We illustrate potential consequences by showing that a privacy attacker is capable of deanonymizing (potentially embarrassing) secret identifiers by intersecting several leaked password databases.

Introduction

Data sets containing user identifiers and password related information are regularly published. In general, these data sets have been hijacked by some hackers, who then published the data on the Internet. The list of such leaks is quite long and only a small fraction of it is listed in Table 1. Taken all together this constitutes a large corpus of personal information. Two factors are worrying in this context. First, the size of the leaks tends to increase, putting more and more users at risk. Second, the passwords are often insufficiently protected, despite long time known recommendations. 1 The most prominent and important leaks over the last years -some of which are listed in Table 1 -use bad password protection mechanisms.

It is commonly accepted that insufficiently protected passwords -e.g. relying on unsalted password hashes or using the same encryption key -have weak security properties and ease the breaking of passwords. Still, in the light of the important number of leaks that actually use a bad password protection mechanism, it is important to understand all the different types of attacksincluding privacy attacks -that an attacker can perform.

These last few years, research focused on password user studies [START_REF] Das | The Tangled Web of Password Reuse[END_REF][START_REF] Ur | How does your password measure up? the effect of strength meters on password creation[END_REF][START_REF] Bonneau | The science of guessing: analyzing an anonymized corpus of 70 million passwords[END_REF], password breaking [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF][START_REF] Narayanan | Fast dictionary attacks on passwords using time-space tradeoff[END_REF] and estimation of password strength [START_REF] Dell'amico | Password strength: An empirical analysis[END_REF][START_REF] Mazurek | Measuring password guessability for an entire university[END_REF][START_REF] Schechter | Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks[END_REF][START_REF] Bonneau | The science of guessing: analyzing an anonymized corpus of 70 million passwords[END_REF][START_REF] Bonneau | Statistical metrics for individual password strength[END_REF][START_REF] Kelley | Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms[END_REF][START_REF] Castelluccia | Adaptive password-strength meters from markov models[END_REF]. Most existing attacks apply to passwords that are used by an important number of users. E.g. dictionary attacks or grammar based attacks [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF] focus on passwords that a human would generate. Password popularity is also used to measure the strength of a password [START_REF] Schechter | Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks[END_REF][START_REF] Ding | On the implications of zipf's law in passwords[END_REF][START_REF] Malone | Investigating the distribution of password choices[END_REF]. The intuition is that the more frequent a password is, the less secure it is. Conversely, rare password are found to be more secure. The popularity distribution of passwords typically follows a Zipf law [START_REF] Malone | Investigating the distribution of password choices[END_REF][START_REF] Ding | On the implications of zipf's law in passwords[END_REF] -meaning that the frequency of a password is inversely proportional to its rank -as exemplified for the data set D used in our study in Figure 1. Related work mainly concentrates on frequent passwords represented on the left hand side of this figure.

In this work, we focus on rare passwords (i.e. supposedly secure passwords), corresponding to the heavy tail of the password distribution. In our example distribution (Figure 1), this corresponds to the passwords located at the bottom right of the curve. We worry about the information that a privacy attacker can find automatically without recovering the password clear text. Data sets with insufficiently protected passwords provide password-equivalents that can be reused in subsequent attacks, even though the corresponding clear text password is never disclosed. Typical password-equivalents are unsalted password hashes and passwords encrypted with a fixed unknown key. Contributions We introduce a model for leaked identifier and password data sets regarding privacy matters. We formalize the notion of password-equivalents. We further describe the privacy attacker and define the tools and relations she will operate on identifier names and passwords.

We present classifiers for linking identifiers and revealing secret links, i.e. links that people do not reveal publicly. Using these classifiers, for a subset of these secret links the privacy attacker is able to deanonymize the associated secret identifiers.

We use a publicly leaked data set (named D in this paper) to evaluate our classifiers. It is one of the largest publicly available data set in its kind containing 153 × 10 6 identifiers and 130 × 10 6 encrypted passwords. With this dataset we show that a privacy attacker can link millions of identifiers, and deanonymize hundreds of thousands secret identifiers. Having no ground truth (for obvious privacy reasons), we estimate the precision of the classifiers through indirect measurements. Finally, we illustrate the consequences of a privacy attack that deanonymizes secret identifiers appearing in a data set related to adult content (denoted A in this paper), by intersecting A with D.

This section defines the problem being addressed by our work. We introduce the attacker model and define linkability properties. We finish with a note on legal and ethical aspects and the precautions used throughout our experiments.

Attacker model

We consider a privacy attacker that retrieved a data set D containing identifiers (e.g. name@mail) and password-equivalents. The privacy attacker's objective is to link identifiers within D. In contrast, most related work consider the confidentiality attacker willing to retrieve clear text passwords.

The privacy attacker is interested in building a large database revealing sensitive links of potential victims. This is different from an attacker focusing on a specific person and gathering information on this victim (via search engines, online social networks, approaching the victim, etc.). The privacy attacker might not carry out the final targeted attack, such as targeted scam or spam, herself. Instead, she might just sell the resulting database.

The privacy attacks presented in this paper target the passwords that are less sensitive to password breaking. Consequently, users that are subject to the privacy attacker are not necessarily subject to the confidentiality attacker and vice-versa.

Model and Definitions

Throughout the paper, we use the privacy related notions defined hereafter. Definition 1. A password-equivalent is the output of a function f (p) applied to a plain-text password p. f (p) is a function in its strict sense, meaning that each plain-text password is related to exactly one password-equivalent.

With this definition a password-equivalent encompasses unsalted hash values such as sha1(p), hash values with a fixed salt such as sha1(p."0xdeadbeef "), unsalted encrypted values such as 3DES(p, S) where S is a secret key, etc. This excludes outputs of randomized hash-functions as in [START_REF] Halevi | Strengthening digital signatures via randomized hashing[END_REF]. In this paper, we consider f (p) to be injective; we are thus neglecting collisions of hashes.

Consistently with [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF], we define linkability and k-linkability.

Definition 2. Identifiers x and y are linked, denoted L(x, y), if x and y are identifiers of the same real person.

We also introduce the informal notions of secret link and secret identifier. L (x, y) is a secret link if the attributes of x provide no information about y. Informally, x and y hide their connection, e.g. by using identifier names that are sufficiently different to not reveal the link.

x is a secret identifier of y (i) if there exists a secret link L(x, y) and (ii) if the identifier x does not reveal the identity of the person (the identity being e.g. the person's family name or the URL of a public profile page) while the identifier y does.

Definition 3. Given a data set D of identifiers, a person is k-linkable in D if there exists a subset D of D such that L(x i , x j ); ∀x i , x j ∈ D and | D| = k.

In this work, we evaluate a linkability attack on the data set D. This linkability attack infers links between identifiers, and we provide a lower bound probability p that identifiers are indeed linked. More formally, we define p as P r[L(x i , x j ); ∀x i , x j ∈ D] ≥ p. In Section 5, we provide estimates and statistics for k and p.

The privacy attacker employs similarities to compare identifiers. One first similarity, denoted ls(x, y), is the complement of the normalized Levenshtein distance between character strings x and y. A second similarity, denoted jw(x, y), is the Jaro-Winkler similarity. The Jaro-Winkler similarity was created for re-conciliating user names from heterogeneous databases, the so-called record linkage problem. The Jaro-Winkler similarity provides good results for short strings such as names [START_REF] Cohen | A comparison of string distance metrics for name-matching tasks[END_REF]. Noticeably, jw(x, y) is generally higher than ls(x, y) for pairwise comparisons of strings such as: ''ic", ''icomputing", ''ingrid.computing", ''computing.ingrid".

Last, the privacy attacker computes the sets defined below.

Definition 4. For any identifier x in D, let sp(x) = {y|y ∈ D and pwd(y) = pwd(x)}, the Same Rare Password function is:

srp r (x) = sp(x) if |sp(x)| = r ∅ otherwise
The extension of srp r to subsets of D is srp r ({x 1 , . . . ,

x n }) = n i=1 srp r (x i )
In practice, we consider values in the range 2 ≤ r ≤ 9.

Note on ethics

Dealing with passwords and personal identifiers raises legal and ethical concerns. Accordingly, we took a set of considerations and employed appropriate precautions. The objective of this work is to understand, as researchers, the privacy implications of password leaks, poor password storage practices, and to raise awareness amongst colleagues, administrators and the community at large.

As a first precaution, all our results are non-nominative, i.e., they do not include any real personal identifiers. In particular, in this paper, we build examples such that: (i) the exemplified property is still clear, (ii) no single element leads back to any real identifier attribute. The example names, emails and encrypted passwords are invented, such as ''ingrid.computing" in Table 2.

As a second precaution, for all treatments not requiring word distance computations or requiring the detection of some pattern, we anonymize the name part of the account using a keyed SHA256 function. For all treatments requiring word distance computations or requiring the detection of some pattern (e.g. detection of separators) we perform the same anonymization operation just after pwdr: significant bytes of the encrypted right part of the password if any. name: identifier before '@' if any. mail: identifier after '@'. hint: hint string.

the distance computation or pattern detection. These precautions guarantee that no real identity appears as a result of a treatment. As a third precaution, we key-hashed the passwords regardless whether there were already protected or not in their initial dataset. None of our treatments require the knowledge of the real password.

In addition, we took classical security measures to protect and clean the files and the programs used for this study.

Our results rely on leaked and publicly available password data sets, and there is a debate whether researchers should use such data sets (see [START_REF] Egelman | Its not stealing if you need it: A panel on the ethics of performing research using public data of illicit origin[END_REF]). Still, there exists an important body of related work that already rely on such type of data sets [2, 3, 5--7, 14, 23, 26]. Individuals willing to know if their accounts appear in publicly leaked datasets may use online services such as haveibeenpwned.com or sec.hpi.uni-potsdam.de/leak-checker.

We would also like to emphasize our ethics regarding identifier providers. While we use publicly available data sets leaked from real organizations, our conclusion are not targeted against these organization. Our conclusions apply to any identifier provider using password-equivalents. Even though it is easy to reconstruct which data set we used, we anonymized the names of the related organizations or companies in this paper.

Description of the databases

In this Section, we describe the databases that we use for our study. We use four leaked password databases that we call A, B, C and D. Table 1 summarizes some characteristics of these data sets. We set emphasis on the database D as it is our main data set for this paper.

Data set D

In October 2013, a password and identifier database -denoted D in the rest of the paper -was stolen from a software company and publicly released. At the time of its release, D was the largest data set in its kind, with 153 × 10 6 identifiers (including email addresses) and 130 × 10 6 encrypted passwords. The company quickly reacted by warning users and locking accounts. Anticipating contagion due to password reuse [START_REF] Florencio | A large-scale study of web password habits[END_REF][START_REF] Das | The Tangled Web of Password Reuse[END_REF], other identifier providers promptly asked their users to change their password.

D was probably used by an authentication server used to access numerous products and services offered by the software company. D covers a long time span of 12 years; the first identifiers were created in 2001. It seems that are very large and diverse set of services and applications of that company relied on the identifiers and passwords in D. While we do not know the exact list of services and applications that use D, they certainly include many standard applications provided by this software company. Users showing up in D may also just have tried once an application, on a PC, on a phone, on a tablet, or registered to some web service (possible third party). Because of the above reasons a given user might have multiple identifiers and forgotten identifiers in D.

Analysts focused on password retrieval from D. Despite 3DES encryption, some passwords could be recovered because of three main reasons: (i) D contains user provided hints in the clear, (ii) the passwords are encrypted with an unsalted 3DES, allowing comparison across different users, (iii) the encryption mode is Electronic Code Book, allowing the comparison of independent ciphertexts blocks of 8 characters. This combination of factors leads to an online ''crossword'' game for retrieving weak passwords 2 . D has long been searchable through sites like pastebin.com and it is still accessible through peer-to-peer downloads.

The raw file contains 153 004 874 lines. We removed irregularities such as absurdly long or short lines, empty lines every 10 000 records, etc. In order to ease subsequent searches, we normalized the fields. Figure 2 shows the result of the normalization. The password equivalents in D have the following structure: pwdl = 3DES(lef t, S), pwdr = 3DES(right, S) where lef t is the first 8 characters of the clear password, right is the next 8 characters. S is a 3DES key only known by the software company. Only the owner of S is able to formally verify clear passwords. In contrast, password equivalents made from unsalted hashes allow public verification. Without the key S, only an accumulation of evidences will reveal possible pairs of clear text passwords and password equivalents. Typical evidences are explicit hint such as: 'my password is frog35', 'frog + 7x5', '53gorf reverse'.

Other password databases

Data set C -a social network The leaked data set contains 164x10 6 identifiers of a social network. The data set stores the users email address (name@mail) and a non-salted password hash. An entry in the data set C is associated with a profile page on the social network.

Data set B -a social network The leaked data set contains 1 057 596 identifiers of a social network. This data set stores the users email address (name@mail) and a salted and hashed password. The data set includes URLs towards public profile pages (Facebook, Twitter, LinkedIn, Yahoo) if provided by the user.

Data set A -an adult content site The leaked data set contains 1 504 128 identifiers of an adult content site. This data set stores the users email address (name@mail) and a password in clear-text.

Privacy Attacks

In this section we describe three privacy attacks on D. We propose a set of classifiers that reveal potential links and secret links in Section 4.1 and Section 4.2 respectively. We also describe a method to deanonymize potentially secret identifiers in Section 4.3. Throughout this Section we depict our classifiers and methods using the examples of Table 2 (k = 2) and Table 3 (k = 4).

We evaluate, extend and discuss the presented classifier and methods in Section 5. Let us consider the fictive case of Ingrid Computing as shown in Table 2. The privacy attacker will notice that only two identifiers in D have the same password cipher ''gt...dfm Qa...D". The attacker suspects a link between the two identities ingrid.computing@mycompany.com and sexy single 69@somedatingsite.com. Both identifiers may of course relate to different persons, in which case the attacker makes a false positive in assessing a link. A motivated attacker may use external sources (search engines, OSN etc.) to collect more evidences, which is out of our scope. The above imaginary example depicts our first simple classifier for revealing links that we describe below.

Revealing links

A classifier for 2-linkability : The classifier tells that L(x, y) (i.e. x and y are linked) if {x, y} ∈ srp 2 (D). srp 2 (D) is the set of identifiers having encrypted passwords appearing only twice in D.

The above classifier can be extended to k-linkability, i.e. to cases of password ciphers appearing exactly k times in D. An illustrative example for k = 4 is provided in Table 3.

A classifier for k-linkability : The classifier tells that x 1 , x 2 . . . x k are k-linked if {x 1 , x 2 . . . x k } ∈ srp k (D). srp k (D) is the set of identifiers having encrypted passwords appearing exactly k times in D.

Revealing secret links

Secret links are a subset of links. Coming back to the example shown in Table 2 the attacker might suspect a secret link since the name of both identifiers have nothing in common (have a small similarity). We propose the following classifier for secret links:

A classifier for secret links for k = 2: The classifier tells that L(x, y) is a secret link if {x, y} ∈ srp 2 (D) and jw(x, y) < s with a small s. jw is the Jaro-Winkler similarity as defined in Section 2.2.

We also propose a classifier for secret links for cases where k > 2. We consider the cases where k -1 identifiers employ similar names and the remaining identifier is either a pseudonym of the same user or a different user. An example is provided in Table 3.

A classifier for secret links for 3 ≤ k ≤ 9: We consider identifiers x ∈ D such that srp k (x) = ∅ and having the following properties: (i) k -1 identifiers in srp k (x) have similar name, for a chosen similarity and a threshold s, (ii) the remaining single identifier in srp k (x) does not have a similar name to any of the k -1 identifiers. We use the Stochastic Outlier Selection (SOS) [START_REF] Janssens | Stochastic Outlier Selection[END_REF] method to automate and build the above classifier. SOS is an unsupervised outlier-selection algorithm that provides an outlier probability for each data point. In our case the outlier is the remaining single identifier, which uses a name very different from the k -1 others. We apply SOS on srp k (x) and keep all sets of linked identifiers that exhibit a single and clear outlier. We conservatively consider an outlier to be an outlier if the SOS outlier probability is at least 0.98. Privacy attackers may adjust the threshold differently, according to their needs and resources.

Deanonymizing secret identifiers

Secret links can be used to deanonymize secret identifiers. Within the sets of identifiers that have a secret link, we search for sets of identifiers where at least one identifier reveals an identity, while the other linked identifiers do not. In the example of Table 2 the attacker might suspect that both identifiers relate to the same person, the first revealing a person's identity (the name of the person) while the second by itself does not reveal the person's identity (thus being a secret identifier ). Similarly in Table 3, the phone number might be a secret identifier of a person which identity is revealed by the name of the other identifiers. We employ three heuristics, described below, to determine if an identifier reveals an identity of a person or not.

Social network B:

The first heuristic uses the leaked data set B of a social network. We consider that an identifier reveals an identity of a person if there exists an URL to a public profile page in the data set B. The data sets D and B both store the users email address (name@mail), allowing us to calculate joins of the two data sets.

Social network C:

The second heuristic uses the leaked data set C of a social network. An identifier in the data set C is associated with a profile page on the associated social network, and we therefore consider that it reveals the identity of a person. The data sets D and C both store the users email address (name@mail), allowing us to calculate joins of the two data sets.

US census:

The last heuristic verifies if the name part by itself reveals the identity of its owner. We use surnames provided by the US census 3 . We consider that an identifier reveals its owner's identity if the name contains a substring of at least four characters long equal to any surname occurring 100 or more times in the US. This heuristic is not very strict and may therefore include many false positives.

Evaluation

Evaluating classifiers for links

One objective of our analysis is to demonstrate k-linkability in D, and to provide an estimate of the probability p that identifiers are actually linked. The main obstacle in such an analysis is the lack of ground truth. This prevents us from evaluating the results of our classifiers (e.g. calculate accuracies, false positives etc.) as it is done classically with machine learning problems. From a user perspective, the lack of such widely available ground truth in this domain is good news.

Instead of ground truth we use a set of heuristics on the password, the identifier name and the password hint. We also analyze the frequencies of these features to provide further evidence that two identifiers are in fact linked.

2-linkability

We first evaluate the classifier for 2-linkability proposed in Section 4.1. The cumulated number of identifiers returned by this classifier is 13 507 724 (6 753 862 identifier pairs), representing 8.8% of identifiers out of D.

To estimate p (the probability that two identifiers are actually linked) we use the heuristic that two identifiers link to the same person if the name fields are similar, i.e. jw(x, y) ≥ s or ls(x, y) ≥ s. The strict equality (s = 1) provides a lower bound for p. The strict equality on the name field e.g. establishes that ingrid.computing@gmail.com and ingrid.computing@hotmail.com are the same person. The intuition is that the probability that two different users use the same rare password and the same name is almost zero. 10% identifier pairs have identical name in srp 2 (D). We consider this value as a pessimistic lower bound for p, i.e. p ≥ 0.1.

By decreasing s we obtain more optimistic values for p (e.g. establishing that ingrid.computing@gmail.com and i.computing@hotmail.com are the same person). At the same time we may introduce more false positives. Figure 3 plots the cumulative distribution function of similarities of identifier pairs in srp 2 (D) for ls and jw-similarities. Using a rather strict value for s = 0.7, we increase the proportion of linked identifiers to 23% with ls-similarity and 29% with jw-similarities. While we cannot provide more precise evidence, we strongly suspect that identifiers in srp 2 (D) are 2-linkable with probability p greater than the pessimistic value 0.29.

We now compare the similarities of name between randomly sampled pairs out of D (supposedly not linked) and identifier pairs in srp 2 (D) (supposedly linked). Figure 3 plots the cumulative distribution function of the similarities for both sets. We notice that the similarities are in general higher in srp 2 (D); the mean ls-similarity in srp 2 (D) is 0.42 versus 0.19 for random pairs. Similarly, the mean jw-similarity in srp 2 (D) is 0.58 versus 0.40 for random pairs. Finally, the proportion of random identifier pairs having identical name is in the range of 0.003%, compared to 10% in srp 2 (D). These numbers confirm the name is in general closer between identifier pairs in srp 2 (D), than any other random identifier pair.

As a further indirect evidence, we show that the propensity of a user to reuse passwords is much higher within srp 2 (D). We use the hint field to estimate the propensity of a user to reuse passwords. More precisely, we count the number of hint fields containing terms indicating password reuse: 'as usual', 'always', etc. See Annex 7.3 for the full list. The result is shown in Figure 4. Among the 66 493 790 identifiers with unique passwords within D, 435 842 identifiers (0.7%) have a 'as usual' kind of hint. Among the 13 507 724 identifiers that share their password exactly once with some other identifier, 173 272 (1.3%) have a 'as usual' kind of hint. The proportion almost doubles, confirming the higher propensity of In light of the above discussion, we propose a more accurate classifier for 2-linkability, i.e. the classifier has higher values for p, at the price of returning a smaller number of identifiers. The classifier tells that L(x, y) if: (x, y) ∈ srp 2 (D) and jw(x, y) ≥ s for a similarity parameter s. With s = 1, we link 683 722 identifier pairs of D with a p close to 1. As discussed before, decreasing s increases the number of linked identifiers but decreases p. The precision of this classifier can be further extended by adding the condition that the hint indicates password reuse. k-linkability Figure 5 shows the number of k-links (being |srp k (D)|) revealed by the classifier for k-linkability of Section 4.1. Table 4 provides the cumulative number of links for k = 2 . . . 9. We can observe, that the number of revealed k-links gradually decreases with k. As discussed in Section 5.1, the probability p that the corresponding identifiers are linked to a same user should decrease when k increases. To demonstrate this trend we consider the propensity of a user to reuse a password (Figure 4). The ratio of hints indicating password reuse is similar with k = 3 and k = 2. For k > 3 this ratio regularly decreases, indicating that p also decreases.

The absolute numbers of k-links of Figure 5 are difficult to interpret, particularly because it is difficult to estimate the probability p. Still, the results of the k-link classifier can be further filtered and refined to reveal secret links and secret identifiers.

Evaluating classifiers for secret links and secret identifiers

We now evaluate the classifier for secret links and secret identifiers proposed in Section 4.2 and Section 4.3. Secret links and secret identifiers are supposed to be secret and it is even more difficult to find ground truth than with links (e.g. the secret links will in general not appear on Google, Facebook or LinkedIn profile pages). We therefore first provide global results and numbers and then focus on a corner-case experiment consisting in deanonymizing role based emails. We also intersect the revealed secret identifiers with external data sets (A) and discuss the potential impacts.

Secret links and secret identifiers global results

For secret links, we set s = 0.4 (as defined in Section 4.2) and therefore require that jw(x, y) < 0.4. This threshold corresponds to the first ''elbow'' in Figure 3. Doing so, we estimate that an attacker would reveal 1 million potential secret links. Figure 5 also shows the number of revealed potential secret links with k > 2; Table 4 provides the cumulative numbers. While it is difficult to assess the p of this classifier, we know that we can increase p by adding the condition that the hint indicates password reuse. Figure 5 and Table 4 further shows the number of secret identifiers we could deanonymize in D, according to the three deanonymization heuristics proposed in Section 4.3.

Deanonymizing role-based emails

The classifiers may discover real names behind generic email addresses like support, admin, security, etc. An attacker can use this knowledge to bypass an 'administrator' or 'support' email address and directly contact the real person in charge. For this application, we select pairs of identifiers in srp 2 (D) such that: (i) one name is generic (see Annex 7.3), (ii) both identifiers have the same mail part, (iii) the mail part is rare within D (less than 100 occurrences in our experiment). From such pairs, the privacy attacker can automatically generate a human readable statement such as: ''Ingrid Computing is 'sysadmin' at this-company.com''. The fact that linked identifiers have the same rare mail part reinforces the link, at least from a Bayesian perspective. The above method generates 25 253 statements involving at least one generic identifier. Among those, 2 858 statements involve a name part with a separator (''.",'' ") and forenames and lastnames that are not reduced to a single letter.

Intersecting with other databases We demonstrate the impact of our attack by deanonymizing secret identifiers in the data set A, a data set related to adult content. We use the A since we expect to find more users that would like to remain anonymous with a service related to adult content. This is confirmed by the numbers of identifiers revealing person identities using the US census, social network C and social network B heuristics (see Table 5). The proportion of identifiers that reveals person identities is systematically smaller in the data set A. We deanonymize a secret identifier in the data set A by (i) extracting all secret identifiers in D and (ii) keeping only the secret identifiers (name@mail) that also appear in A. The data sets A, B, C and D all include email addresses (name@mail), allowing us to calculate joins. Table 6 reports the number of deanonymized identifiers.

We further highlight the existence of embarrassing secret links. In Table 6, we report the number of secret links between an identifier in A and identifiers that verify a set of criteria: (all) no restriction on the mail address, (corporate) corporate mail addresses from major companies, (gov) mail addresses from government agencies, (univ) mail addresses from universities.

Related Work

Related work focuses on password cracking, password strength, password user studies and deanonymization of public data sets.

The most common password cracking attacks are the brute-force and dictionary attacks using popular tools such as John the Ripper. Many improvements for password cracking have been proposed: using rainbow tables [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF], using Markov models [START_REF] Narayanan | Fast dictionary attacks on passwords using time-space tradeoff[END_REF], using probabilistic context-free grammars [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF], etc. Some works try to assess or measure the strength of a password [START_REF] Dell'amico | Password strength: An empirical analysis[END_REF][START_REF] Mazurek | Measuring password guessability for an entire university[END_REF][START_REF] Schechter | Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks[END_REF][START_REF] Bonneau | The science of guessing: analyzing an anonymized corpus of 70 million passwords[END_REF][START_REF] Bonneau | Statistical metrics for individual password strength[END_REF][START_REF] Kelley | Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms[END_REF][START_REF] Ding | On the implications of zipf's law in passwords[END_REF]. In this context, password meters are supposed to help users to improve their password. However, Ur et al. [START_REF] Ur | How does your password measure up? the effect of strength meters on password creation[END_REF] show that in general password meters only marginally increase the resistance to password cracking. Only very strict password meters tend to increase the password strength [START_REF] Ur | How does your password measure up? the effect of strength meters on password creation[END_REF][START_REF] Castelluccia | Adaptive password-strength meters from markov models[END_REF]. Password popularity is also used to measure the strength of a password [START_REF] Schechter | Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks[END_REF][START_REF] Ding | On the implications of zipf's law in passwords[END_REF][START_REF] Malone | Investigating the distribution of password choices[END_REF]. To strengthen a password, Schechter et al. [START_REF] Schechter | Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks[END_REF] use the quite simple idea of discouraging the use of popular passwords. This latter approach is clearly beneficial for the privacy attacker of this work. The above works often use well-known password data sets to evaluate their performance.

Other work considered user behavior regarding passwords [START_REF] Mazurek | Measuring password guessability for an entire university[END_REF][START_REF] Florencio | A large-scale study of web password habits[END_REF][START_REF] Das | The Tangled Web of Password Reuse[END_REF]. [START_REF] Florencio | A large-scale study of web password habits[END_REF][START_REF] Das | The Tangled Web of Password Reuse[END_REF] study the problem of password reuse across sites. Both show that the reuse of the same or a similar password is a predominant practice for end-users. In particular, [START_REF] Das | The Tangled Web of Password Reuse[END_REF] studies how users transform their password for different online accounts. Both papers focus on an attacker breaking passwords, e.g. [START_REF] Das | The Tangled Web of Password Reuse[END_REF] builds a password guessing algorithm based on the observed user behavior. These works do not consider the privacy attacker which does not require to break passwords.

Most privacy attacks focus on the deanonymization of social networks and rating systems. [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF] deanonymizes the public Netflix data set, by matching movie ratings provided by users of the Internet Movie Database. [START_REF] Narayanan | De-anonymizing social networks[END_REF] re-identifies users of an anonymized Twitter graph, matching them against Twitter and Flicker identifiers. [START_REF] Narayanan | On the feasibility of internet-scale author identification[END_REF] identifies anonymous online authors by comparing writing styles. [START_REF] Mishari | Exploring Linkability of User Reviews[END_REF] links reviewers of community review sites. We consider a radically different type of data set that has not been studied in terms of privacy so far.

To the best of our knowledge, the work that comes closest to ours is [START_REF] Perito | How unique and traceable are usernames?[END_REF]. The authors use identifier names to link or uniquely identify users. They further leverage textual similarities between identifier names for estimating the linkability probabilities. Our work is different as (i) we use encrypted information rather than textual information and (ii) we link to secret identifiers that are --by definition --very dissimilar from their linked identifiers.

Discussion and Conclusion

We presented linkability attacks based on password equivalents in leaked identifier and password data sets. The attacks do not require breaking a single password, and the efficiency increases with the password strength. Having no ground truth, which is expected in this domain, we provided indirect assessment of the performance of our classifiers. We demonstrated the consequences of our attack by showing that a privacy attacker can reveal sensitive private information such as secret identifiers. In particular, we evaluated how privacy attackers can deanonymize secret identifiers of users of adult content sites. State of the art attacks analyzing online social networks do not reveal this kind of information.

Tractability of privacy attacks

We would like to emphasize several risks for people's privacy. First, the presented privacy attacks require little computation resources. For instance, the k-linkability analysis on D took only 400 cumulated computation hours. The complexity of most treatments does not exceed O(n.log(n)). The attacker does not need to break any password, which saves a lot of resources. Further, the attacks can be performed using publicly available data sets. There is no need to crawl social networks or to have access to a social network graph. These two facts make our attacks tractable to most individuals without requiring any specific privileges or computing power. Finally, D is much larger than other data sets in this domain. This allows retrieving a fair amount of results, typically thousands, even when using multiple refinement requests. The number and size of publicly available data sets of that kind tends to increase, meaning that the number of retrieved results will also further increase over time.

Mitigations

The mitigations and countermeasures are rather classical. End-users achieve best results in terms of both privacy and security by using a strong and different password for each service. Since it might be difficult for a user to remember all these passwords, we recommend users to segment linkability according to their estimated privacy needs. Users should use unique passwords for the few services that they never want to be linked to. For other non-privacy critical services, users may use a password based on one single root (e.g. frog35!), and prefix the password with a character or string related to the service (e.g. FB for Facebook, LI for LinkedIn). This ''poor man's salt'' does not reinforce the security of the password, but decreases the impact of linking attacks. Password managers that generate randomized passwords also provide an efficient countermeasure. Finally, identifier providers should use salted hashing functions. These recommendations have been published several years ago and still, numerous leaked files reveal bad practices. In addition, we encourage identifier providers to encrypt both the hints and the email addresses. Obviously the hints are private, while massively leaked email addresses are a gift to spammers. Finally, identifier providers should avoid incremental uid's and use random numbers [START_REF] Gambs | A Comparative Privacy Analysis of Geosocial Networks[END_REF].4

Future work

We found several cases where additional private information can be inferred from the available data sets. For instance, a privacy attacker could deduce people ''histories'' from the set of successive identifiers of a same person. Table 7 shows one example. Using time reconciliation this history reads: ''In 2001, Joe was at corp1, he joined corp2 before mid-2008, then he went to corp3 before 2012''. Building such histories requires linking identifiers through names [START_REF] Perito | How unique and traceable are usernames?[END_REF] , in addition to the links established through passwords. The first entry in Table 7 is linked to the second via distances introduced in [START_REF] Perito | How unique and traceable are usernames?[END_REF]. The second entry is linked to the third entry via the password. The fourth item is linked to all others via a combination of both techniques.

Fig. 1 .

 1 Fig.1. Distribution of passwords in the data set D used in our study. For each password appearing in the data set we compute its rank in the data set (horizontal axis) and its number of occurrences (vertical axis). The relatively flat aspect on a log/log representation is characteristic of a Zipf law[START_REF] Newman | Power laws, pareto distributions and zipf's law[END_REF].

Fig. 2 .

 2 Fig.2. Top: original text. Bottom: result after normalization. uid: internal user identifier zero-padded to 9 digits. pwdl: significant bytes of the encrypted left part of the password. pwdr: significant bytes of the encrypted right part of the password if any. name: identifier before '@' if any. mail: identifier after '@'. hint: hint string.

Fig. 3 .

 3 Fig. 3. Cumulative distribution function of similarities in srp2 and in randomly sampled pairs of identifiers of D.

Fig. 4 .

 4 Fig. 4. Percentage of ''as usual'' terms in the hint, as a function of k in k-linkability. k takes values in {1, 2, . . . , 10, 11 -20, 21 -40}.

Fig. 5 .

 5 Fig. 5. Number of links, secret links and secret identifiers in D for k between 2 and 9.

Table 1 .

 1 Large leaked password databases. Most of them use password-equivalents.

	Top 5 confirmed password leaks on ''';--have i been pwned?" a in February 2017:
	Site	#identifiers Year b	Protection	Password-equivalent?
	MySpace 360 million 2008 (2016)	hash, sha1	yes
	LinkedIn 164 million 2012 (2016)	hash, sha1	yes
	Adobe	153 million 2013	encryption, 3des yes
	VK	100 million 2012 (2016)	plaintext	yes
	Rambler 100 million 2014 (2016)	plaintext	yes
	Data sets used in this paper:
	Name	#identifiers Category	Protection	Password-equivalent?
	A	1, 5 million adult	plaintext	yes
	B	1 million	social network	salt + hash, md5 no
	C	164 million social network	hash, sha1	yes
	D	153 million software company encryption, 3des yes

a https://haveibeenpwned.com/PwnedWebsites -retrieved February 2017. b If the release year is different from the hack year, the release year is provided in parenthesis.

Table 2 .

 2 Example case for 2-linkability.

	uid	pwdl	pwdr name	mail	hint
	042...89 gt...dfm Qa...D ingrid.computing mycompany.com	as usual
	151...06 gt...dfm Qa...D sexy single 69	somedatingsite.com

Table 3 .

 3 Example data for a secret link with k = 4.

	uid pwdl pwdr name	mail	hint
	05... G...F	ic.computing email.xx 1st cat
	05... G...F	0699999996 telco.xx 1st cat
	06... G...F	computing.ic telco.xx kitty
	15... G...F	iccomputing corp.xx kitty

Table 4 .

 4 Cumulative number of links, secret links and secret identifiers in D for k between 2 and 9.

	#links	11 038 079
	#secret links	1 937 634
	#secret identifiers using US census	763 348
	#secret identifiers using social network C 348 892
	#secret identifiers using social network B	4 003
	in comparison: size of D	153 004 874

Table 5 .

 5 Proportion of identifiers in D and A revealing person identities according to different heuristics.

	US census social network C social network B
	D 93.83 %	8.33 %	0.07 %
	A 78.03 %	3.91 %	0.02 %

Table 6 .

 6 Number of deanonymized secret identifiers in A, and number of secret links according to different criterions

	Deanonymized secret identifiers		Secret links
	US census social network C social network B all corporate gov univ
	851	337	5	2979	3	4 104

Table 7 .

 7 Probable history of a user w.r.t data set D. uid pwdl pwdr name mail hint 06...83 hc...si joe.target corp1.com 10...68 sj...f2 Tr...G joe target corp2.com 16...80 sj...f2 Tr...G tryjoe isp.com usual 17...22 Fg...st tryjtarget corp3.uk other

Such as recalled in the OWASP Password Storage Cheat Sheet

See https://www.census.gov/genealogy/www/data/2000surnames

The uid of D increases monotonically with the time of creation of the identifier. It allows the reconstruction of a timeline, by e.g. using creation dates of some identifiers or by searching in the fields name and hint for events having a worldwide notoriety.

Acknowledgements

We thank the Program Committee and reviewers for the many valuable comments that significantly improved the final version of this paper.

Appendix

Terms for 'as usual' always, usual, the rest, for all, normal, same as, standard, regular, costumbres, siempre, sempre, wie immer, toujours, habit, d'hab, comme dab, altijd.

List of generic email addresses

abuse admin administrator contact design email info intern it legal kontakt mail marketing no-reply office post press print printer sales security service spam support sysadmin test web webmaster webmestre.


The Relationship between Constitutions, Politics and Islam: A Comparative Analysis Baudouin Dupret

I. Introduction

Contemporary experiences of integrating Sharia in the legal body of nation-states took place in such a way that we can talk about disruption of the economy and the epistemology of Islamic normativity. Its overall balance, its fundamentals and its morphologyor what we might call its grammarhave been transformed completely. This is true at a substantial level, where applicable norms are largely formulated through codification. This is also true at an institutional level, with the establishment of constitutional architectures dedicated to the separation of powers, the hierarchy of jurisdictions, the legislative principle, the popular representation, and the fundamental rights and freedoms, within which Sharia is deemed to be a reference framework rather than specific and directly applicable rules.

The use of certain terminology does not necessarily mean the use of the same language. It is thus seen that the vocabulary of Sharia is mobilized in different contexts, without any greater permeability between the argumentative logic of any register. This is not due to different levels of truth, but in fact it is due to the purposes towards which the people involved orient themselves in terms of these discursive activities. As a law, the Sharia is an invention of the nineteenth century. As a reference in the political register, it is a formulation of the second half of the twentieth century. However, as a constitutionalized source of legislation, it is an innovation of the last quarter of twentieth century. But as an ethical paradigm autonomous from legal normativity, it is a current resurgence. Sharia went through, to use Armando Salvatore's heuristic formula, a true implosion. 1 This has led, in terms of the positivist 19 th century logic, to the dissociation of normativity between law and ethics. Each of these realms became autonomous, at least in appearance, according to very specific terms. In the mid-20th century, the Islamic referent was marginalized in the political, ethical or legal discourse. Then, under pressure exercised from national, regional and international dynamics, Sharia began to gain more sphere, both from belowwhat might be called the Islamization of societiesand from aboveits come-back as a constitutional and political referent. This dynamic, however, is more variegated than it appears at first glance, as the advent of Islamic-conservative government does not necessarily mean the establishment of Sharia-centered political and constitutional systems.

II. Implosion, eclipse and come-back in politics

Nowadays, what is called Sharia belongs primarily to morality, and the tensions observed in political and constitutional matters derive from complex relationship maintained in modern societies between politics, religion, law and morality. In some former work, I talked about the invention of Islamic law, a phenomenon that is part of the political emergence of the nationstate and the corollary development of a positive legal system.2 'As in Japan during the Meiji era, says Shibli Mallat, there was a need for clear, simple and complete codes that would address the most common legal transactions, and only the Napoleonic Code could provide the right necessary model'. 3 As Sharia is Islamic normativity, it may have ethical, religious, political and legal dimensions without necessarily making it a 'law' in the current sense of the word. This composite nature is found torn apart by a tendency to the autonomization of each of these dimensions, due to, among other, the Islamic reform movement (islah). In Egypt, for instance, especially during the late 19 th century, one observed at the same time the organization of a public sphere, the dynamics of codification of the law and the emergence of a constitutional movement. This reorganization of the public sphere -which brought about the establishment of a state apparatus and the means with which it legally regulates its relationship with its citizensled to the progressive fragmentation of Sharia between a legal framework, where it found itself both positivised and confined; and a public sphace where it acquired the place of a hegemonic reference built around a core that was characterized as authentic, civilizing and normative.

The ambivalence of Sharia is reflected in the conception that people demanding Sharia have4 .

It can sometimes be 'the basis on which the law is based', sometimes 'a life project', and sometimes even something else: 'Islam is not limited and can never be reduced to mere laws', as an Egyptian lawyer told me in the 1990s5 . Thus, in general, Sharia is a reference, not a specific content, and it refers to the idea of an authentic tradition that a society would keep for only legitimate. As for the purpose of this reference, it varies depending on the many worldviews of the people.

Originally, Pan-Arabism was not but a variant of 19 th century nationalism. The Arab idea was first expressed around the concept of Arab Caliphate, as formulated by Abdelrahman al- Kawakibi (d.1902) in the Mother of Cities, or by Rashid Rida (d.1935), in The Caliphate. We note, however, that the Arab argument was during all times combined with an Islamic affirmation. This trend was reflected into the doctrine of the Ba'th, the Arab nationalist party par excellence. In his Manifesto of 1943, Michel 'Aflaq (d.1989) speaks of the 'Arab Spirit'(ruh 'arabiyya), 'the irreducible essence' in which Islam is a fundamental component: 'Islam is the vital impulse which revealed to the Arabs the forces residing in them and which made them known in the stage of history'. 'Aflaq attempted to make a synthesis in which Islam is Arab as well as Arab is Muslim, in which Arabism is the body and Islam is the soul. In addition to that, and within the Arab context, the failure of nationalism, the 1967 defeat, the lack of freedom and the impossible success of authoritarian policies of modernization were all factors that facilitated the emergence of a political Islamic vision. If the first phase of the 20 th century was marked by a translation of the Caliphate utopia to the Arab nation utopia, the second phase was more however characterized, within the Islamist movement, by a return to the original utopia. This return was made possible by the failure of the nationalist culture to play a competitor role over that of religion, and therefore a role in enabling the development of ideologies as a counterweight to religion.

At the same time, the return of such religious referent to the forefront was largely sponsored by the ruling regimes that had little difficulty in exploiting the ideological points of convergence such as the Unitarian utopia. Some Islamist movements have not hesitated to use the term 'ba'th islami' (Islamic resurrection), while nationalists appropriated the term of 'Umma' (community), characterized as Arab for the occasion, in parallel to the Umma islamiyya, the Islamic Community, to which all religious literature refers. The concept of social justice is one of those convergence points, as it is attested in Sayyid Qutb's (d.1966) writings, the rhetoric of the deprived people (mustad'ifun) in the Iranian revolution or the socialist discourse of most Arab states in the 1960s.

The multiple conjunctions of nationalism and Islamism allow us to realize how much the nationalist enterprise never intended to stand out from the Muslim anchorage of societies, but rather to find Islamic roots endorsing the advanced project, while taking the power away from the first proponents of this return to sources.

The stumbling block is therefore not ideological, at least not in principle. The issue is more political. The denunciation of the illegitimacy of the existing powers, the indictment of authoritarian practices, the fight against nepotism and corruption, are all the constants of Islamism. The challenge was even greater for in-power regimes that secular forms of opposition had failed or were recuperated by the regimes. Their reactions varied between concessions and violence, intimidation and State Islamism. The last technique was to ensure the system stability that coercion failed to provide and to give it a legitimacy making therefore Islamist demands inoperative.

In fact, it is the dual status of ideological convergence of nationalism and Islamism, and the instrumental recovery of the Islamist rhetoric by in-power regimes that explains the inversely proportional size of the victory of Islamist groups in the rise of the so-called 'Arab Spring', and the return to the use of Islam and Sharia repertoires. The resurgence of old partisan oppositions firmly grounded in political Islam was not surprising, if one wants to remember that the only organized opposition groups regarding authoritarian regimes had left the shores of marxism and socialism and resorted to those of religious authenticity. But at the same time, on the ground of Islam, little features distinguished the regimes from their oppositions.

In Egypt, the heads of the National Democratic Party competed under the dome of the Parliament to show their piety. 8 In Algeria, several parties claiming Islamism involved for years in government, which is also engaged in the construction of the largest mosque in the world. Sudan, on its part, has adopted a criminal Code labelled 'Islamic'. And one can hardly be more dogmatic than the Saudi monarchy. In a nutshell, the Islamic relevance had long been imposed in the public space to the point of becoming unavoidable; to the extent that it was no longer possible not to pay it tribute; and to the extent that it was not necessary to enter in an inflationary process regarding Islamic reference, since the most important thing had already been acquired as to the matter. In this regard, we can say that ideological Islam is dissolved in political Islam, that is to say, in the game of power and politics.

II. An essential reference, a diversified content

The reference to the Sharia can be achieved in different ways, only some of which are political. In this latter case it means that one can resort to the Sharia in an institutional setting, in an electoral process or in opposition demonstrations against the ruling power. These political uses rely upon a religious dimension which gives credibility to the action committed in the name of religion. This does not mean that religion and politics are combined; on the contrary, each one of them responds to multiple logics, which are sometimes convergent. This does not mean either that the political use of religion is purely cynical, nor does it preclude any calculation of costs and benefits.

Hence, when a politician wants to pass, in the name of religion and his conviction, a law prohibiting the sale of alcohol, it is not only the effect of his will to apply the divine order; in fact, he also formulates a political position that is beneficial to him, since it corresponds, in his way of assessing the situation, to something that is expected by the public opinion. He may predict popularity gain or even electoral gain. At the same time, this calculation is only possible if the reference system on which he bases his proposal is credible, that is to say, in an Islamic context, if the religious language is widely present, disseminated and accepted. In this respect, there is no reason to exclude that he himself accepts this language game. We see that the religious reference belongs, in this case, to something other than politics and therefore cannot be reduced to that only.

However, it also directly affects politics. In other words, the fact that he acts according to political calculation does not contradict his conviction of the rightness of his claim: we can desire power, struggle for a standard and try to attain the first using the second9 . From this point of view, the political uses of the divine Law does not draw a Muslim conception of politics, but a natural way of making policy using an Islamic frame of reference. This reference frame functions ordinarily, since it refers a position to principles commonly agreed upon and therefore taken for granted. As self evidence does not require to be demonstrated, this promotes argumentative economy and obliges the others to show a discursive alignment: in fact, it is not easy to publicly challenge what is recognized by many others. This does not mean that the content given to this common reference repertoire is shared by all, by far. All that people place behind a referent such as Sharia can be contrasted and the consequences they derive from the invocation of the commonly accepted reference may be different and even contradictory.

One specific characteristic of the political use of Sharia lies in the prevailing consensus on the need to use it as a reference. At the same time, variations may be very important regarding its content. As it is almost impossible to withdraw from the necessity to refer to Sharia, the political actors anticipate positions that others might have adopted, pre-empt their argument or prejudge their ends and intents. Political strategies are outlined that aim at forcing opponents to align to the prescribed register and thus reduce their room for manoeuvre.

Yet, these strategies have a cost : involving in the religious repertoire, one finds oneself in an argumentative framework that makes some debates more difficult than others, among other things in the field of manners and freedoms. I think of issues related to equality of men and women, freedom of conscience or liberalization of sex. Moreover, it is noted that it is the particular circumstances that give the Sharia register a specific content. The latter is not substantiated until it is invoked in specific situations. Thus, it is not possible to know in advance with certainty what will be the arguments and, most importantly, what will be said regarding diverse subjects such as loan interest, divorce by compensation, biomedical ethics, restoration of virginity, homosexuality, alcohol sales, tourism, wearing the veil, apostasy or blasphemy.

It is not that the content is opportunistically invented by cynical politicians, but there is an extremely wide range of possible solutions as to Islamic standard reference. It is thus a balance of political forces, backed by a moral vision of the world, which leads to one configuration rather than another. In other words, what varies is not the content of Sharia, but the state of public opinion towards this content. 'From this point of view, relying on divine Law in the course of a political action is first relying on a state of public opinion-at least as it is interpreted. This attitude is of course highly political. This is what politicians generally do.

By the way, nothing is more natural, since it is the opinion course and variations that, at least, partially determine their future (if not more bluntly their career)'10 . This political game is primarily that of conformism, out of which it is difficult for a political actor to stand without paying a heavy price. This conformism in today Muslim majority societies goes through a conservative reference to Islam and its normativity, the Sharia. Certainly, everyone can make it appropriate for his own ends, but that still requires the acceptance of the obligatory track: doing politics in a Muslim context means recognizing the primacy of the Islamic referent, be it purely symbolic.

III. Reference to Islam and the devolution of power in religious matters

The term 'Islamic law' has become unfit to designate both the law of a Muslim majority country and a range of mechanisms that do not belong to the continuity of doctrine (fiqh) but rather to techniques specific to contemporary law-drafting and constitutionalism. A particular phenomenon is actually observable, among others in the constitutions of the states with Muslim majority. It is that of referencing to Islam, to Sharia, or to fiqh. It is no longer here the issue of codifying Islamic normativity, but most importantly, to refer contemporary legislators to this divine Law in order to inspire their works. Thus, there will be provisions making Islam the religion of the State, providing that the Head of the State is a Muslim or making the Islamic normativity the inspiration source of positive law.

With the transition movement initiated by the overthrow of the Tunisian regime in January 2011 and the beginning of the drafting of new constitutional texts, this issue has taken a new urgency, especially as there are Islamic-conservative political forces that have emerged as winners of the elections. The concern with political consensus yet often seems to have prevailed over the desire of religious hegemony, and ideological pragmatism to have prevailed over the utopian ideal. One of the reasons helping to explain the ease with which this pragmatic trend has emerged is doubtlessly due to the plasticity of the reference that the Sharia constitutes and its ability to function as a flexible resource rather than as a set of binding rules.

Many are the state constitutions in predominantly Muslim population that refer to Islam. This is illustrated, generally, at four levels: the preamble, the determination of a state religion, the principle of conformity of the legislation to the principles of the religion, and the conditions to be met by the head of the state. The inclusion of Islam as the state religion is an ancient practice that dates back to the 1950s11 . Some constitutions reserve high positions to Muslims and devolution to the throne in monarchies is through Muslim geniture. Many constitutions also limit the scope of certain rights and freedoms in respect of Sharia, as they affirm the centrality of the family formed around the religion and the Islamic values. Numerous basic texts consecrated the normative value of Sharia, principles of sharia or Islamic fiqh, but they differ on the place given to it. Two specific constitutional experiences will allow us to explore the contrasting nature of reference to Islam.

A. Egypt

In Egypt, the Constitution of September 11 th , 1971 marks a break, in the sense that it introduces, for the first time, a reference to the normativity of Islam in the institutional system by providing, in Article 2 that 'the principles of Islamic Sharia are a main source of legislation.' On May 22 d , 1980 Article 2 has been amended and has stated since that time that 'the principles of Islamic Sharia are the main source of legislation.' For the special commission in charge of preparing the constitutional reform, the new formulation aimed to 'compel the legislator to make use of the commands of the Shariah, to the exclusion of any other source, to discover what it looks for. If it finds no explicit command, it may, by deduction from the sources of interpretation (ijtihad) of Sharia find out the rules to be followed and that do not violate Sharia's fundamentals and general principles.' On the basis of this article, many constitutional complaints have been brought before the Supreme Constitutional Court (SCC), the case-law of which is of particular interest. Initially, the Court had tendency, when it was asked to review the constitutional character of laws and decrees, to avoid engaging in the field of interpretation of Sharia. Thus in 1985 the SCC canceled the decree Jihan (which borrowed the name of the late President Anwar Sadat's wife, who inspired it), reforming the personal status 12 , not for its alleged contravention to Article 2 as recently amended, but for the purely technical reason that there was no need to use the exceptional powers granted by the Constitution to the President of the Republic in order to change a text dating back to 1929 and not modified since then. In another decision taken on the same day, the SCC formulated a principle that constitutes a precedent. In the origin of the lawsuit, there was condemnation of the Ministry of Waqfs (endowments) and the Faculty of Medicine at the University of al-Azhar to pay a large debt that had been added default interest as provided by the Civil Code. This article was the subject of a case of unconstitutionality and the SCC then established the principle of the non-retroactivity of Article 2: 'The obligation of the legislature to adopt the principles of the Sharia as the main source of legislation... extends only to legal texts promulgated after the date of its entry into force... Concerning texts that preceded that date, they cannot for that reason alone be subject to this obligation, and are thereby out of the control of constitutionality. 'The SCC added that the application of Sharia as if it were codified rules would risk conflict and destabilization of the legal order. However, over time, the possibilities to sue on unconstitutionality of texts subsequent to this reform have increased. Thus, in a judgment of 15 May 1993, the Court was required to take stance in the field of Sharia and its interpretation. It explained what is meant by Sharia and what, in this context, can be a work of interpretation. It was the case of a divorced woman who had filed a petition for custody of her son and the right to stay with him in the former marital home, according to law No. 100 of 1985. She also claimed the right to receive compensation in an amount equivalent to ten years of alimony. On the basis of the noncompliance of these provisions to the Sharia, the ex-husband had gone to the SCC. In its decision, the Court drew a distinction between Islamic absolute and relative principles. For it, only the principles 'whose origin and meaning are absolute', that is to say, the principles that represent unquestionable Islamic norms, whatever their source is (Qur'an, Sunna, consensus, analogy) or their significance, must be applied without margin for interpretation. However, there is also, for the SCC, a set of rules considered as relative, which are subject to interpretation, are evolving in time and space, are likely to be different in interpretation and can adapt to the changing needs of the society.

As noted Nathalie Bernard-Maugiron: 'The Supreme Constitutional Court gave great freedom to the authorities of the State to adapt the rules relating to Sharia to the evolution of the society'. Indeed, it is the legislator's responsibility to procede to the interpretation of Sharia principles by referring to one or the other doctrinal school, without being bound by previous opinions of jurists. The only conditions which apply to it are to make rules consistent with the current social conditions, based on the general principles of Islamic law and without violating an absolute principle... If it recognized the legal value of the principles of the Islamic Sharia and the need for the legislature to meet those 'whose origin and meaning are absolute', it is paradoxically to better limit its effects. The Court declared to be bound by the norms derived from the Islamic sharia, but reserved itself the right to determine the content.' 13 A new constitution was promulgated in Egypt on December 26, 2012, following the 2011 revolution and the Muslim Brotherhood's electoral successes. It fully duplicates Article 2, while adding a new provision, Article 219, which states that 'the principles of Islamic Sharia include its general evidence and its fundamental and doctrinal rules, as well as its sources considered by schools of the People of tradition and consensus (ahl al-sunna wa'l-jama'a).'

The convoluted wording of this article and its insertion at the end of the constitutional text show the precipitate adoption of the Egyptian constitution, but they also reflect the desire to limit the power of the SCC, by defining, instead of the Court itself, the terms 'sharia principles' formulated in Article 2. These principles are expressed in a an all-embracing manner: the term 'general evidence' (adilla kulliyya) refers to everything that comes from the Revelation; that of 'fundamental rules' (qawa'id usuliyya) refers to the science of the foundations of doctrine ('ilm usul al-fiqh), that of 'doctrinal rules' (qawa'id fiqhiyyah) refers to Islamic doctrine, fiqh; that of the 'sources taken into consideration by schools' refers to everything on which the Sunni schools of thought are based. In other words, the principles of Sharia correspond to all sources of Islamic normativity. Nothing is said, however, as to the constrain these principles have on the Egyptian legislator and hence on the SCC when it is required to check the compliance to them. More than ever, the Sharia imposes itself as a reference register, not as a substantial and compelling content.

With the military coup of July 2013, the 2012 Constitution was suspended. The new regime, which ousted the Muslim Brotherhood, appointed a commission of experts in charge of presenting propositions of amendment. A new constitutional text was drafted, which again duplicates Article 2 as amended in 1980, but discards the controversial Article 219. The new constitution was approved by referendum in January 2014.

B. Tunisia

Contrary to Egypt, there is no provision in Tunisia making of the Sharia a formal source of legislation. In the 1959 Constitution, Article 1 provided: 'Tunisia is a free, independent and sovereign state; its religion is Islam, its language is Arabic and its regime is the Republic'. This formulation was adopted under the initiative of Tunisia's first President, Habib Bourguiba, in order to overcome the differences which had appeared within the first constituent assembly, although it was monopolized by the members of the National Front (i.e. the Neo-Destour party and its allies). Together with the constitution's preamble, which invokes Islam, it created interstices in which some representatives of the conservative forces (often supporters of Salah Ben Youssef) within the judiciary. 14 Some judges used this opportunity to give Sharia the status of a subsidiary source in case the law is silent or obscure, especially in the field of personal status. In the rulings which make reference to it, it becomes 'the source' of personal status, although it is only one of its many sources in principle. In other domains of civil law, some judges also used Sharia by invoking its being one of the material sources of the Code of obligations and contracts. Tunisian jurisprudence questioned for long the judges' rights to elevate Sharia to the status of a subsidiary source. For those who were in favor of it, the issue was to know which was the right interpretation of Sharia, while for those who were against it, the question was to imagine a means to expel it from the positive legal order. 15 Of course these tensions came back to the surface after the ousting of President Ben Ali and his clique in 2011. The place of Islam and Sharia was the object of tense debates. One of the many paradoxes was the polarization of the political scene around the opposition Islamists v. Liberals, while there was little reference in the official texts to Islam and Sharia. Under the pressure of its opponents and because of its political pragmatism, the Islamist party Ennahda, which lead the government since the 2011 elections, renounced making any mention of Sharia in the Constitution. It does not mean, however, that Ennahda renounced its project of the Islamic moralization of the society, but as in the Erdoğan's Turkey, it prefers to substitute to symbolic moves a more gradualist approach using the de facto acceptance of Sharia as a source of legislation and case-law. As Rashid al-Ghannouchi put it in press conference on the 26 th of March, 2012: 'nearly 90% of our legislation finds its origins or sources in Sharia'. All this shows the importance of Islam as a resource and constraint in the inchoative structuring of the political field. 16 After many turbulences a new constitution was adopted in January 2014. It states in its Article 1 that Islam is the religion of the state. Article 6 provides: 'The state is the guardian of religion, the protector of the freedom of belief, conscience and religious practice, the guarantor of the neutrality of mosques and of cult places against partisan uses. The state is committed to the spreading of the principles of equity and of tolerance, to the protection of the sacred, and to the forbidding of any blow against it. It is also committed to the forbidding of apostasy accusations and of the inducement to hatred and violence'. Thus, Sharia is not given the role of a legislative referent, but this does not mean that Islam cannot be legally mobilized, since it is the religion of a state which is required to protect the sacred. It is the political climate that will determine the interpretation given to provisions which are not consensual.

C. Morocco

The case of Morocco also is interesting, regarding the reference to Islam and the devolution of religious competences. The constitutional history of the country is rich. After the authoritarian constitution of 1970, there was the 1972 constitution, which reintroduced the parties in politics after the king was convinced, following two attempted coups, that he could not rely only on the security apparatus. A major reform was made in 1996, which prepared the consensual 1998 alternation and laid the bases of succession. The constitution of 2011 is in line with the reformist trend, accelerated by the Moroccan version of the Arab Spring, which the power has seized as an opportunity to engage in a consensual political remodeling.

The Constitution has three essential features: delineation of a wide scope of action of the head of government who has the necessary means to carry out its task and, above all, to control the parliamentary majority supporting it; the affirmation of the arbitration and influence powers of the sovereign; the establishment of independent bodies responsible for the protection and development of rights. This separation is aimed less at separating the Executive, the Legislative and the Judiciary than to define the spheres of influence of three functional blocks.

If it comes to provisions relating to religion, we note the distinction between Islamic frame of reference and devolution of powers in religious matters. The reference to Islam in the Moroccan case is both prolific and non-implicative. Article 3 states that it is 'the religion of the state,' while recognizing 'the free exercise of religion.' Although freedom of conscience is not recognized in the Constitutiondespite its inclusion in an earlier draft -Article 25 states that 'are guaranteed freedoms of thought, opinion and expression in all its forms'.

Unlike the technique of limiting the scope of the provision by reference to the lawwhich draws its limits or affects its applicationthis text establishes an inviolable principle. Thus, we see that the predominance of Islam is not coupled with a reference to Islamic normativity (Sharia or fiqh). Islam, the religion of the state, is primarily a national frame of reference. The text reads, in fact, that in its 'moderate version', the 'Islamic religion' is one of the unifying elements of the state, with national unity, territorial integrity and the one and indivisible identity of the nation (Article 1). The articles of the Constitution that refer to Islam almost always emphasize the principles of tolerance and openness, and freedom of worship. What is characteristic of the Moroccan constitutional system is, unlike situations where the religious legitimacy of the head of state is lacking, the superfluous nature of the identification of the In other words, the Constitution distinguishes the two 'bodies' of the king and seeks to reduce the possibility of confusing the powers of the one with the other. In the course of a development that, as Hassan Rachik underlines, marks the secularization of Sultanic function that began with the establishment of the Protectorate and was pursued by the nationalist movement, this allows us to imagine the long term, a deepening demarcation of the two functions, where the executive role of the head of the state always become even more a role of arbitration, while his role as the supreme religious authority would be exercised in a strong and extensive way. 18 For now, however, it is in an exclusive manner that the king exercises the powers of commandery (imara) of believers. The differentiated devolution of royal powers is accompanied by a maximum definition of his powers in the field of religious regulation. The question, then, is to know what exactly the commandery of the believers is. It is not the subject of a list either illustrative or exhaustive, listing the powers that are related to it. We can talk in this regard, of a subsidiarity principle: everything that is not explicitly outside the religion is likely to be attached to it by the will of the commander of the faithful. Recent history has provided an example of this type of connection, when the king committed himself to the reform of the family Code (mudawwanat al usra). The regulation of this legal domain does not strictly belong to the realm of religion, but it is under the umbrella of commander of the believers that Mohamed VI took stance. One can imagine a number of areas where the same mechanism would be activated, and neither the legislative nor the executive, nor the Constitutional Court can much oppose it: freedom of conscience, abortion, death penalty, heritage, public organization of fasting in Ramadan, legality of extramarital sexual relations, Islamic finance, etc.

The Moroccan system is unique in that it is able to narrow the normative field of Sharia. As noted by Mohamed Mouaqit, it operates in a way inversely proportional to the centrality of the commandery of the believers. Where, as in Morocco, the symbolism of the commandery is constitutionally strong the normativity of sharia is less relevant politically, 'as if the strength of the former had a compensatory effect on the weakness of the latter.' Morocco is a case of over-determination of the monarchical order rather than Sharia. The power of the king enhances or undermines the normativity of it as he wants to take advantage of or, conversely, contains it. When it comes to nationalize the legal order through the islamizing of its sources or to defeat the leftist political forces, the trend is that of an opportunistic exploitation of this resource. On the contrary, when it comes to stem the Islamist surge, the trend is to establish limits on the normativity of Sharia through the use of the Islamic commandery 19 .

IV. Conclusion: Sharia as an ideology

We know that religions change, however unsettling these thoughts for those who are attached to permanence. This applies to Islam, which is not a 'nomocracy' that would be irreducibly frozen in its past. How religious and political spheres are articulated affects very directly the form of discourses legitimizing authority. They oscillate between ideology and utopia. While it is difficult to identify a political, constitutional or moral truth from the sources of Islamic normativity, it is equally clear that people, when they refer to a foundational past and interpret it, participate in the recreation of their tradition. In doing so, they feed on utopias.

When these utopias are anchored again in the political and social reality, and take a concrete form in it, they become ideologies. It is not absurd to think that Sharia is today confirmed in this function, especially in the context of accession to power of Islamic-conservative forces.

By ideology, this author, following Paul Ricoeur, refers to this set of shared representations, in a given society, transformed into action. These representations are both moral and normative. When they are projected into the political arena, these value-ideas often acquire 19 M Mouaqit, 'Marginalité de la charia et centralité de la Commanderie des croyants : le cas paradoxal du Maroc' in B Dupret (ed.) (n. 9). an unquestionable status. This is what Jean-Noel Ferrie calls an effect of negative solidarity 20 .

In their development, political ideas ground themselves on what makes sense in a given context, in a movement of retrieval that allows them to add the weight of normativity while remaining free enough to give it a new content. From this process of ideological sedimentation emerge new rationalizations. Political discourse claims then to expresswhen in fact it createswhat everyone is supposed to know, thereby producing metaphors and a sense of belonging, continuity and consistency. Whatever the degree of innovation, the discourse constantly reaffirms its roots in pre-existing and deep moral ties, which can project a very personal version of reality in the world of public consensus and, at the same time , to naturalize its authority.

Islamic normativity is in the process of being integrated in the political and constitutional, but also moral and social domains. Sharia, as it combines an understanding of the world and a set of values, and as long as it is represented as such, tends to be particularly usable in ideological terms. Sharia has become somehow consubstantial with the public and political life, in the context of predominantly Muslim societies. Most protagonists of politics tend to throw the representation they make and the use they claim to have of it in the public arena, which is not expected to see but the expression of evidence. Views on its contents remain very diverse, but it has become difficult in the contemporary Muslim world, to position outside the space it defines. It is certainly only a framework, but it is the framework of a sieve through which all discourse seems to have to go.

  Nasser's discourse, although less doctrinaire, is marked by the same characteristics. Islam is considered the easiest way to permeate the country in depth. However, Islam has also a global purpose. Thus, in an annex to the National Action Charter of 1962, a reference text of Nasserism, a Charter Report was published. The first chapter thereof was entitled 'Religion and Society'. It aimed to reconcile those who held a 'sociological perception of Islam' and the 'defenders of a conformist conception' 6 , as well as to conciliate, through ambiguous formula, modernity and the Islamic legacy. The content of this Islamic socialism coincided pretty much with the Muslim Brotherhood's Islamic socialism: 'It believes in God and His prophetic messages, in religious and moral values; it believes in the community ... while respecting human dignity and individual liberty.' This shows, incidentally, that the opposition between the Muslim Brothers and Gamal Abdel Nasser (d.1970) was more for a fight for power than an ideological opposition. The Algerian socialism was not devoid of any reference to Islam either, or even to early Islamism. The Association of Algerian Muslim Scholars, founded in 1931, had during independence a strong position. Its influence is materialized in the development of the doctrine of Islamic socialism which was different from the Muslim Brotherhood's. The early 1970s was marked by the strengthening of Islamic tone in public discourse, with the launch of the Authenticity magazine (al-Asala). The magazine reflected the ambivalence of Algerian Islamism, both in and outside the state. The magazine actually symbolized both the instrumentalization of Islam by the leading team, and the performance of the fundamentalist purpose by part of the elite. It was in the process of Arabization and the adoption of the Personal Status Code that such tone was fully expressed. 7 It is therefore incorrect to claim that the Islamic referent disappeared from the scene in the first three quarters of the 20 th century. Nevertheless, it was subject to the overriding goal of building a nation-state. If one examines the constitutional translations in the Arab context, one observes the inclusion of the objective of 'creating a unified Arab state' (Article 1 of the Iraqi Constitution of 1970), but also the primacy of 'defending the socialist gains, their consolidation and preservation' (Article 59 of the Egyptian Constitution of 1971).

  Islamic normativity as a legal reference. The constitution of 2011 is no exception to this constant 17 . The new constitution differs from previous texts in the dissociation that occurs between the functions of the king 'Head of State, the supreme representative, symbol of the unity of the nation, guarantor of the perpetuation and the continuity of the State and Supreme Referee between its institutions' (Art. 42); and the king 'Commander of the Faithful' (amir almu'minin). In Article 41, it states, in effect: 'The King, Commander of the Faithful, ensures respect for Islam. He guarantees the free exercise of religion. He chairs the Higher Council of Ulema, responsible for the study of questions submitted to it. The Council is the only body empowered to give religious consultations (fatwa) officially approved on matters referred to it and that, based on the principles and precepts of Islam tolerant designs. The powers, composition and procedures of the Council are set by Dahir. The king exercises by Dahirs religious prerogatives inherent to the institution of the commander of the believers conferred exclusively by this article.'

  20 J-N Ferrié, Le Régime de la civilité. Public et réislamisation en Égypte (CNRS-Editions, Paris 2004).

A Salvatore, 'La sharî'a moderne en quête de droit : raison transcendante, métanorme publique et système juridique' (1998) 39 Droit et Société,

293-316.

L Buskens and B Dupret 'L'invention du droit musulman. Genèse et diffusion du positivisme juridique dans le contexte normatif islamique', in F Poullion et J C Vatin (eds.), L'Orient créé par l'Orient (Karthala, Paris 2011), 71-92.

C Mallat, 'Islamic law, droit positif and codification: reflections on longue durée': Plurality of Norms and State Power from 18 th to 20 th Century, Vienna, Workshop 1997.

B Dupret, Au nom de quel droit ? (Droit et Société, Recherches et Travaux du Réseau Européen Droit et Société à la Maison des Sciences de l'Homme, Série anthropologie, LGDJ, Paris 2000).

Ibid.

CAMAU, Michel, personnal communication.

J-C Vatin, 'Chronique Algérie', (1976) vol. XV Annuaire de l'Afrique duNord,

B Dupret and J-N Ferrié, Délibérer sous la coupole. L'activité parlementaire dans les régimes autoritaires (Presses de l'IFPO, Beyrouth 2014).

J-N Ferrié, 'Usages politiques de la Charia' in B Dupret (ed.), La Charia aujourd'hui, (La Découverte, Paris 2012) ; see also: B Dupret and J-N Ferrié, 'Participer au pouvoir, c'est imposer la norme : sur l'affaire Abu Zayd(Égypte, 1992-1996)' (1997) vol. 47 no. 6 RFSP, 762-775.

J-N Ferrié (n. 9).

Although countries such as Indonesia do not do so; and others, such as Turkey, emphasize the secular character of the state.

This lawamong other thingsgranted the first wife whose husband remarries an almost automatic right to divorce.

Y Ben Achour, 'Statut de la femme et État de droit au Maghreb' in Y Ben Achour, J-R Henry, R Mehdi (eds.), Le débat juridique au Maghreb. De l'étatisme à l'État de droit. Études en l'honneur de Ahmed Mahiou (Iremam, Paris 2009).

M Ben Jemia, 'Le juge tunisien et la légitimation de l'ordre juridique positif par la charia' in B Dupret (ed.) (n. 9).

Note also Article 175 of the Constitution: 'No review can be on the provisions relating to the Muslim religion, the monarchical form of the state, the democratic choice of the nation or the achievements in matters of freedoms and fundamental rights stated in this Constitution.'