Stephan Neumann

Manuel Noll
email: mnoll@student.ulg.ac.be

Melanie Volkamer

Election-Dependent Security Evaluation of Internet Voting Schemes

The variety of Internet voting schemes proposed in the literature build their security upon a number of trust assumptions. The criticality of these assumptions depends on the target election setting, particularly the adversary expected within that setting. Given the potential complexity of the assumptions, identifying the most appropriate Internet voting schemes for a specific election setting poses a significant burden to election officials. We address this shortcoming by the construction of an election-dependent security evaluation framework for Internet voting schemes. On the basis of two specification languages, the core of the framework essentially evaluates election-independent security models with regard to expected adversaries and returns satisfaction degrees for security requirements. These satisfaction degrees serve election officials as basis for their decision-making. The framework is evaluated against requirements stemming from measure theory.

Introduction

Significant research efforts have been made to establish security requirements for Internet voting schemes [START_REF] Grimm | Security requirements for non-political internet voting[END_REF][START_REF] Gritzalis | Secure electronic voting[END_REF][START_REF] Mitrou | Revisiting legal and regulatory requirements for secure e-voting[END_REF][START_REF] Neumann | A holistic framework for the evaluation of internet voting systems. Design, Development, and Use of Secure Electronic Voting Systems[END_REF]. Amongst the most prevalent requirements, there are vote secrecy (also referred to as vote privacy [START_REF] Delaune | Verifying privacy-type properties of electronic voting protocols[END_REF][START_REF] Ryan | Pretty good democracy[END_REF]), i.e. an adversary must not be able to establish the link between the voter and her cast vote, vote integrity, i.e. an adversary must not be able to undetectably manipulate votes, and eligibility, i.e. an adversary must not be able to cast votes for abstaining voters. The numerous Internet voting schemes proposed in the literature, e.g. [START_REF] Adida | Helios: Web-based open-audit voting[END_REF][START_REF] Budurushi | Pretty understandable democracy-a secure and understandable internet voting scheme[END_REF][START_REF] Clarkson | Civitas: A secure voting system[END_REF][START_REF] Juels | Coercion-resistant electronic elections[END_REF][START_REF] Ryan | Pretty good democracy[END_REF], implement these requirements by making certain assumptions. For example, the JCJ/Civitas [START_REF] Clarkson | Civitas: A secure voting system[END_REF][START_REF] Juels | Coercion-resistant electronic elections[END_REF] scheme builds vote secrecy upon the assumption that the device used to cast a vote is trustworthy. Pretty Good Democracy [START_REF] Ryan | Pretty good democracy[END_REF] enforces vote secrecy in the presence of malicious voting devices, yet the scheme assumes that the voter can cast her vote without adversarial influence. The criticality of these assumptions, and therefore the security of Internet voting in general, differs within different election settings. To face this reality, our goal is to construct an election-dependent security evaluation framework for Internet voting schemes that measures to what extent an Internet voting scheme satisfies security requirements within concrete election settings. Related Work. Several works have addressed the assessment of risks for electronic voting systems [START_REF] Bannister | A risk assessment framework for electronic voting[END_REF][START_REF] Buldas | Practical security analysis of e-voting systems[END_REF][START_REF] Kim | Development and application of a framework for evaluating multi-mode voting risks[END_REF][START_REF] Nevo | How to compare and analyse risks of internet voting versus other modes of voting[END_REF][START_REF] Pardue | E-voting risk assessment: A threat tree for direct recording electronic systems[END_REF][START_REF] Pardue | Towards internet voting security: A threat tree for risk assessment[END_REF] by deriving threats trees for these systems. The fine-grained threats considered in these works require decision makers to assign probabilities to specific threats. Reviewing threat trees for Internet voting systems poses a significant burden on election officials, e.g. [START_REF]Threat trees and matrices and threat instance risk analyzer[END_REF] provides a 18-page threat tree for Internet voting. While this approach facilitates the interpretation of large and complex threat trees, the approach is tailored towards system analysts. Hence, the approach does not foresee the incorporation of election settings by election officials. Volkamer and Grimm [START_REF] Volkamer | Determine the Resilience of Evaluated Internet Voting Systems[END_REF] propose the concept of resilience terms to capture complex trust distributions of Internet voting schemes and to express which central entities have to be trusted in order to fulfill security requirements. These trust distributions do, however, not incorporate the election setting into the security evaluation and expression. Furthermore, adversaries might consider other attack targets to violate security requirements, for instance voting devices or influencing voters throughout the vote casting process. On the foundation of resilience terms, Schryen et al. [START_REF] Schryen | A formal approach towards measuring trust in distributed systems[END_REF] develop a quantitative trust metric upon propositional logic. As foundation for their quantification, the authors determine resilience terms for security requirements in distributed systems. Thereafter, they compute the probability that security requirements might be violated on the basis of failure probabilities of individual entities. The approach inherits one essential shortcoming of the resilience term evaluation, namely the fact that the evaluation focuses on central entities of the voting system.

Contribution. We build the election-dependent security evaluation framework upon two specification languages: The language of qualitative security models enables system analysts to specify the security of Internet voting schemes in an election-independent manner, i.e. system analysts specify canonical assumptions about adversarial capabilities under which the scheme enforces security requirements. Intuitively, these canonical assumptions indicate the weakest successful adversary (refer to Pamula et al.'s notion [START_REF] Pamula | A weakest-adversary security metric for network configuration security analysis[END_REF]) in terms of abstract capabilities. The language of election settings allows election officials to specify their election settings in terms of expected adversaries and the number of voters. Upon the specification of qualitative security models and an election setting, the framework computes satisfaction degrees of Internet voting schemes with regard to the security requirements within the concrete election setting. Before its actual construction, the requirements for the security evaluation framework are determined. Ultimately, the framework is evaluated against these requirements.

Requirements for the Security Evaluation Framework

By its nature, the envisioned framework closely relates to the mathematical concept of a measure (refer for instance to Salamon [START_REF] Salamon | Measure and Integration[END_REF]). We therefore base the requirements for the construction upon the properties of a measure and adapt them to our context. The first property a measure possesses is that it must assign the empty set of the σ-algebra in the measure space, to the measurement 0. Transferring this property to our context, two requirements are derived: First, if the Internet voting scheme under investigation faces an adversary that has no capabilities, then the scheme's satisfaction degrees must be 1 with regard to all security requirements, unless the security requirement can be violated without any adversarial capabilities 4 .We refer to this requirement as no capabilities -perfect security. Second, if the Internet voting scheme under investigation proves to be resistant against a specific adversarial capability, then in the presence of any two adversaries that differ only with regard to that capability, the scheme's satisfaction degrees are equal. We refer to this requirements as capability resistance.

The second property a measure possesses is continuity. In measure theory, the property of continuity is defined by stating that 1) the measurement of the union of a countable infinite sequence of increasing sets (E n ) n∈N is equal to the measurement of the last set of the infinite sequence and 2) the measurement of the intersection of an infinite sequence of decreasing sets (E n ) n∈N is equal to the measurement of the last set of the infinite sequence. Transferring this property, we require that if the Internet voting scheme under investigation faces a sequence of adversaries, of which the capabilities converge towards the capabilities of a fixed adversary, then also the scheme's satisfaction degrees in the presence of the sequence of adversaries converges towards the scheme's satisfaction degree in the presence of the fixed adversary.

The third property a measure possesses is monotonicity. In terms of measure theory, the property ensures that the measurement of a subset of another set from the σ-algebra must be smaller than the measurement of the set. The fourth property a measure shall must possess is σ-additivity. In terms of measure theory, the property requires that the measurement of a union of disjoint subsets of the σ-algebra equals the sum of the measurement of the disjoint subsets. Both properties are transferred to the context of security evaluation for Internet voting schemes. Hence, we require that if the Internet voting scheme under investigation faces two adversaries, of which one is stronger than the other, then the scheme's satisfaction degrees must not be larger when facing the stronger adversary as compared to the weaker adversary.

Construction of the Security Evaluation Framework

The section is dedicated to the construction of the security evaluation framework. We emphasize that the herein presented construction mainly builds upon our previous construction published in 2016 [START_REF] Neumann | Secivo: a quantitative security evaluation framework for internet voting schemes[END_REF]. Before diving into the details of the construction, we provide the necessary definitions. We subsequently show how the security of Internet voting schemes is assessed by evaluating the electionindependent security within the concrete election settings.

Definitions

Before presenting the construction of the security evaluation framework, we recall several definitions [START_REF] Neumann | Secivo: a quantitative security evaluation framework for internet voting schemes[END_REF] while we slightly adapted the notations for this paper.

Definition 1 (Qualitative Adversary Model) Let an Internet voting scheme A with the set of instantiated capabilities C A be given. An adversary model A A , or simply adversary, against scheme A is defined by a subset of instantiated capabilities C A , i.e.

A A ⊆ C A .
Definition 2 (Qualitative Security Model) Let an Internet voting scheme A with the set of instantiated capabilities C A be given. We say that

M A,r,i = (α A,r,i 1 ∨ • • • ∨ α A,r,i ξ A,r,i ) with α A,r,i j = (c A,r,i j,1 ∧ • • • ∧ c A,r,i j,λ A,r,i j ) and c A,r,i j,k ∈ C A
is a qualitative security model of A with regard to security requirement r and impact level i if there exists a set of adversaries S = {A 1 , . . . , A ξ A,r,i } where A j is specified by capabilities {c A,r,i j,1 , . . . , c A,r,i j,λ A,r,i j }, such that 1. all adversaries A ∈ S are capable of causing impact i on r, and 2. for all adversaries A ∈ S, there is no adversary A ⊂ A such that A is capable of causing impact i on r, and 3. for all adversaries A capable of causing impact i on r, there is an adversary A ∈ S, such that A ⊆ A .

Definition 3 (Resistance Against Abstract Capability) Let an Internet voting scheme A with the set of instantiated capabilities C A and the qualitative security models M A,r,1 , . . . , M A,r,n be given. We say that the scheme A is resistant against capability C o ∈ C with regard to requirement r, if for all impact levels 1 ≤ i ≤ n and for all c A,r,i j,k in all α A,r,i j , capability c A,r,i j,k

∈ C A is not an instantiation of C o .
Definition 4 (Election Setting) Given probability distributions P C1 , . . . , P C l for all abstract capabilities C o ∈ C, the number of eligible voters n el , and the number of expected voters n ex , a tuple of the form E = (P C1 , . . . , P C l , n el , n ex ) is referred to as an election setting.

While being generous in definition, we simply require election officials to provide uniform distributions U (a, b) for adversarial capabilities probabilities.

Determination of Satisfaction Degrees in Election Settings

As baseline of the framework, we show how to evaluate qualitative security models within specific election settings. Therefore, it is first shown how the probability of an adversary violating a qualitative security model can be calculated. Thereafter, it is outlined how Monte-Carlo simulations [START_REF] Metropolis | The monte carlo method[END_REF] are adapted for the quantitative evaluation of qualitative security models against probabilistic adversaries. The herein described algorithms build upon our previous work [START_REF] Neumann | Secivo: a quantitative security evaluation framework for internet voting schemes[END_REF]Section 7.3]. As we noticed that this description is difficult to understand, we present, in the following paragraphs, the algorithm in a more readable manner. We abbreviate the probability of the event that the adversary A satisfies a security model X or possesses a specific (abstract or instantiated) capability, i.e. P A (X = 1), by P (X).

Determination of Satisfaction Degrees with Given Probabilities. To determine the satisfaction degree of an Internet voting scheme A with qualitative security models M A,r,i under given probabilities P (C o ) for all C o ∈ C and under n impact levels (the instantiation of impact levels will be explained in the following paragraph), the following function f (P (C 1 ), . . . , P (C l )) is defined:

1. For each instantiated impact level 1 ≤ i ≤ n, the probability formula of the qualitative security model is evaluated based on the given probabilities. Note, we show in [16, Section 7.1] how to transform qualitative security models into probability formulas. 2. For each instantiated impact level 1 ≤ i ≤ n, a risk value is calculated by multiplying the normalized impact i n with the evaluated probability formula of the respective qualitative security model. 3. The largest risk value is identified. 4. The satisfaction degree estimator is the inverse of the largest risk value.

Algorithm 1 Satisfaction Degree Estimation (SDE)

Input: Level size n, probabilities {P (Ci)} l i=1 Output: Satisfaction degree estimator e 1 for i ← 1, 2, . . . , n do pi ← P ( ξ A,r,i j=1 α A,r,i j ) P (C 1 ),...,P (C l )

2 for i ← 1, 2, . . . , n do ri ← pi • i n 3 rmax ← max 1≤i≤n ri. 4 e ← 1 -rmax 5 return e
Extension towards Probabilistic Adversaries. Rather than precise probabilities, election officials assign probability distributions to adversarial capabilities. While we currently assume that instantiated capabilities are independent, the framework is generated in a way that also caters for dependent instantiated capabilities. Therefore, to determine the satisfaction degree of an Internet voting scheme A with regard to a security requirement r within a specified election setting E, we build upon Monte-Carlo simulations [START_REF] Metropolis | The monte carlo method[END_REF]. Therefore, the following process is defined:

Instantiation of Impact Levels. The number of impact levels and probability formulas are instantiated by the number of eligible voters n el and the number of expected voters n ex .

Generation of

M := f (P (C 1 ), P (C 2 ), . . . , P (C l ))
Processing of Satisfaction Degree Estimators. We define the statistical satisfaction degree of scheme A with regard to requirement r and election setting E as the expected value of random variable M , i.e. E(M ).

3.

To approximate E(M ) by the m satisfaction degree estimators generated in step 2, namely e 1 , . . . , e m , the average of these estimators is calculated. Hence, the empirical satisfaction degree M m (in the remainder simply referred to as satisfaction degree) of scheme A with regard to requirement r and election setting E is defined as:

M m := 1 m (e 1 + • • • + e m ) = 1 m m k=1 f (p (k) 1 , p (k) 2 , . . . , p (k) l )
By the weak law of large numbers, it holds that the empirical satisfaction degree converges in probability towards the statistical satisfaction degree, i.e.

M m m→∞ -→ E[M ].
To evaluate the quality of the empirical satisfaction degree with regard to the statistical satisfaction degree, a confidence interval is calculated. Within this work, we focus on the core of the framework and omit the confidence interval from further consideration (see [START_REF] Neumann | Secivo: a quantitative security evaluation framework for internet voting schemes[END_REF] for further details).

Evaluation of the Security Evaluation Framework

After its construction, the security evaluation framework is evaluated with regard to the requirements determined in Section 2. The following proofs build upon the weak law of large numbers and hold therefore for a sufficiently large number of Monte-Carlo iterations. No Capabilities -Perfect Security. The first requirement that the security evaluation framework shall possess is that the satisfaction degree of all schemes must be 1 with regard to all security requirements, if the adversary has no capabilities, unless the security requirement can be violated without any adversarial capabilities. This void of capabilities is equivalent to the absence of randomness as the adversary's capability is determined. Hence the probability distributions that are passed by the election official, degenerate to deterministic functions. Within a probabilistic framework, such deterministic functions are called constant random variables. Their distribution function is the Dirac delta function δ x , where x ∈ R denotes the point of mass [START_REF] Hazewinkel | Encyclopedia of Mathematics[END_REF]. In particular, it holds U (a, a + 1/n) n→∞ ----→ δ a . Hence, for each C o ∈ C the Dirac delta function δ 0 is passed, as there is only one probability that can be assigned to the event that an adversary has capability C o , namely zero. Theorem 1. Let δ 0 be the distribution function for all abstract capabilities C o ∈ C. The satisfaction degree of scheme A is 1 for all security requirements r, unless the security requirement can be violated without any adversarial capabilities.

Proof. If the probability of having an abstract capability C o ∈ C is 0 for all C o ∈ C, then all instantiated capabilities c A,r,i j,k , with 1 ≤ k ≤ λ A,r,i j for the impact level i have probability 0, i.e. P (c A,r,i j,k ) = 0. This leads to P (α A,r,i j ) = 0 and thus

P ( ξ A,r,i j=1 α A,r,i j ) ≤ ξ A,r,i j=1 P (α A,r,i j ) = 0.
As this holds true for all impact levels, the maximum risk of all impact levels equals 0. Consequently, the satisfaction degree estimator results in 1. Given the fact that the random variables for capability probability have their entire density at 0, each Monte-Carlo iteration assigns the value 0 to all capability probabilities. Hence, the resulting random variable M has its entire density on the value 1, such that E(M ) = 1.

Capability Resistance. The second requirement refers to the resistance of Internet voting schemes against specific abstract adversarial capabilities.

Theorem 2. Let Internet voting scheme A be resistant against abstract capability C o with regard to requirement r. Let P (C 1 ), P (C 2 ), . . . , P (C o ), . . . , P (C l ) denote random variables for the probabilities of adversarial capabilities C 1 , C 2 , . . . C o , . . . C l . If random variable P (C o ) is replaced by a differently distributed random variable P (C o ) , then the resulting satisfaction degrees of scheme A with regard to requirement r do not differ.

Proof. For the random variables P (C 1 ), P (C 2 ), . . . , P (C o ) , . . . , P (C l ), we denote the random variable generated by the Monte-Carlo simulations by:

M := f (P (C 1 ), P (C 2 ), . . . , P (C o ) , . . . , P (C l ))
Due to A's resistance, it holds for all c A,r,i j,k in all α A,r,i j that c A,r,i j,k is no instantiation of C o . Consequently, function f is neither affected by random variable P (C o ) nor by P (C o ) . As a consequence, it holds

M = f (P (C 1 ), P (C 2 ), . . . , P (C o ), . . . , P (C l )) = f (P (C 1 ), P (C 2 ), . . . , P (C o ) , . . . , P (C l )) = M ,
and hence E(M ) = E(M ).

Continuity. Election officials provide uniform probability distributions for capability probabilities, e.g. distributions P (C i ) ∼ U (a i , b i ), i = 1, 2, . . . , l. To prove continuity of the framework with regard to the expected adversary, we study the framework's result under sequences of random variables (P (C i,n )) n∈N where P (C i,n ) ∼ U (a i , b i + 1/n) for i = 1, 2, . . . , l. We say that continuity is given if the framework's results are identical under the random variables P (C i ) ∼ U (a i , b i ) and P (C i,n ) ∼ U (a i , b i + 1/n) for n converging to infinity. Formally, this is expressed as follows:

E(M n ) = E( f (P (C 1,n ), P (C 2,n ), . . . , P (C l,n )) ) n→∞ -→ E( f (P (C 1 ), P (C 2 ), . . . , P (C l )) ) = E(M )
Before proving the main theorem, we define two lemmata. Due to space limitations, we omit proofs of the lemmata herein 5 . Lemma 3. The satisfaction degree estimator for requirement r in scheme A is continuous with regard to a sample probability P (C o ) for any C o ∈ C. Definition 5 A sequence of random variables (X n ) n∈N weakly converges to a random variable X, if for every continuous function f , it holds

lim n→∞ Xn f (x)dP Xn = X f (x)dP X ,
where P Xn denotes the probability distribution of X n and P X the probability distribution of X, shortly X n d -→ X.

5 These proofs will be published in a technical report.

Lemma 4. Let X ∼ U (a, b) be a uniformly distributed random variable and let (X n ) n∈N ∼ U (a, b + 1/n) be a sequence of random variables. Then it holds

X n d → X.
Theorem 5. Let P (C i ) ∼ U (a i , b i ), i = 1, 2, . . . , l denote uniformly distributed random variables for the probabilities of adversarial capabilities C i . The satisfaction degree of A with regard to requirement r is continuous with regard to any weakly convergent sequence of random variables (P (C i,n )) n∈N where

P (C i,n ) ∼ U (a i , b i + 1/n) for i = 1, 2, . . . , l.
Proof. Let M n denote a framework's satisfaction degree calculation for a given sample of random variables p i,n ← P (C i,n ), i = 1, 2, . . . l. For the random variables P (C 1,n ), P (C 2,n ), . . . , P (C l,n ), we denote the resulting random variable generated by f as:

M n := f (P (C 1,n ), P (C 2,n ), ..., P (C l,n )).
Analogously to M m , we define the satisfaction degree calculated by the framework as

M m n = 1 m m k=1 f (p (k) 1,n , p (k)
2,n , . . . , p Lemma 4) and the fact that the satisfaction degree estimator is continuous (refer to Lemma 3), it holds:

(k) l,n ). By the law of large numbers, M m n m→∞ -→ E[M n ] holds. Given the weak convergence of P (C i,n ) n→∞ -→ P (C i ) (re- fer to
M n = f (P (C 1,n ), P (C 2,n ), . . . , P (C l,n )) d -→ f (P (C 1 ), P (C 2 ), . . . , P (C l )) = M
For the sequence of expected values (E[M n ]) n∈N , it consequently holds:

|E[M n ] -E[M ]| = |E[M n -M ]| n→∞ -→ 0
Monotonicity. We study the framework's result under the random variables

P (C i ) ∼ U (a i , b i ), i = 1, 2, . . . , o, . . . l, when P (C o ) is exchanged by a random variable P (C o ) ∼ U (a o , b o ) with a o ≥ a o and b o ≥ b o .
We say that monotonicity is given if the framework's result is larger under P (C i ) ∼ U (a i , b i ), i = 1, 2, . . . , c, . . . l than under the same set where P (C o ) is exchanged by a random variable P (C o ) . Formally, this is expressed as follows:

E(M ) = E( f (P (C 1 ), P (C 2 ), . . . , P (C o ) , . . . , P (C l )) ) ≤ E( f (P (C 1 ), P (C 2 ), . . . , P (C o ), . . . , P (C l )) ) = E(M )
Before proving the main theorem, we define two lemmata. Due to space limitations, we omit proofs of the lemmata herein. By Lemma 7 and the fact that the satisfaction degree estimator is nonincreasing (refer to Lemma 6), we are able to conclude that E(M ) = E( f (P (C 1 ), P (C 2 ), . . . , P (C o ) , . . . , P (C l )) )

E[f (X)] ≤ E[f (Y )] Theorem 8. Let P (C i ) ∼ U (a i , b i ), i = 1,
≤ E( f (P (C 1 ), P (C 2 ), . . . , P (C o ), . . . , P (C l )) ) = E(M ).

Conclusion

We constructed an evaluation framework for Internet voting schemes that incorporates the expertise of system analysts and election officials to evaluate schemes within concrete election settings. The framework's internal consistency was evaluated against requirements derived from measure theory. We summarize limitations of the constructed framework as basis for future research: The framework's generic nature requires election officials to estimate probability distributions for abstract adversarial capabilities. Estimating presence probabilities on this level of abstraction might be more challenging than estimating probabilities of concrete capabilities for election officials and should be investigated in the future. Currently, the framework does not incorporate varying adversary motivations, i.e. probability distributions remain invariant over different election types and sizes. We assume adversaries specified by qualitative security models to always succeed. One might consider refining the constructed framework towards assigning success probabilities to qualitative security models.

In the future, the framework will be generalized further: Among these generalizations, the framework will be extended towards the case in which instantiated capabilities might be considered dependent. Based upon its actual concept, the framework will be extended to handle non-uniform probability distributions for abstract capabilities, i.e. normal distributions. Furthermore, we plan to publish the framework as collaborative platform: There, security experts are invited to discuss and jointly determine qualitative security models of Internet voting schemes. After specifying their election setting, the platform should support election officials to determine the most adequate voting scheme(s) for their setting.

Algorithm 2

 2 Monte-Carlo based Satisfaction Degree Computation (MCSDC) Input: Iterations m, probability distributions {PC i } l i=1 Output: Satisfaction degree M m 1 for j ← 1, 2, . . . , m do p (j) 1 ← P (C1) ∼ PC 1 , . . . , p (j) l ← P (C l ) ∼ PC l 2 for j ← 1, 2, . . . , m do ej ← SDE(n, p

Lemma 6 .Lemma 7 .

 67 The satisfaction degree estimator for requirement r in scheme A is non-increasing with regard to a sample probability P (C o ) for any C o ∈ C. Let two random variables X ∼ U (a, b) and Y ∼ U (c, d) with c ≥ a and d ≥ b be given. For any non-decreasing function f , it holds:

  2, . . . , c, . . . , l denote uniformly distributed random variables for the probabilities of adversarial capabilities C i . The satisfaction degree of A with regard to requirement r is non-increasing with when random variable P (C o ) is exchanged by P (C o ) ∼ U (a o , b o ), with a o ≥ a o and b o ≥ b o . Proof. For P (C 1 ), . . . , P (C o ) , . . . , P (C l ), we denote the resulting random variable generated by f by M , and the respective expected value by E[M ].

  Monte-Carlo based Satisfaction Degree Estimators. The following steps are conducted m times (number Monte-Carlo iterations). The process steps are shown for the j-th Monte-Carlo iteration. 1. For each abstract adversarial capability C o ∈ C, an estimator of the probability P (C o ) is sampled according to the probability distribution P Co . 2. For each vector of probability estimators p

	(j) 1 , . . . , p	(j) l , f is called.
	Conducting these two steps yields samples of the following random variable:

This holds for instance true if vote secrecy is not required and the Internet voting scheme under investigation publishes the relation between a voter and her vote.

Acknowledgment. The research that led to these results has been funded from a project in the framework of Hessen Modell Projekte (HA project no. 435/14-25), financed with funds of LOEWE Landes-Offensive zur Entwicklung Wissenschaftlichökonomischer Exzellenz, Förderlinie 3: KMU-Verbundvorhaben (State Offensive for the Development of Scientific and Economic Excellence). The second author is grateful to the F.R.S.-FNRS for a doctoral grant (1.A.320.16F).


Cecilia Pasquini

Pascal Schöttle

Rainer Böhme

Decoy Password Vaults: At Least As Hard As Steganography ?

Cracking-resistant password vaults have been recently proposed with the goal of thwarting offline attacks. This requires the generation of synthetic password vaults that are statistically indistinguishable from real ones. In this work, we establish a conceptual link between this problem and steganography, where the stego objects must be undetectable among cover objects. We compare the two frameworks and highlight parallels and differences. Moreover, we transfer results obtained in the steganography literature into the context of decoy generation. Our results include the infeasibility of perfectly secure decoy vaults and the conjecture that secure decoy vaults are at least as hard to construct as secure steganography.

Introduction

User-chosen passwords are still the most common authentication standard in online services and users likely cumulate a high number of passwords for different domains. To alleviate the memory effort and possibly let users choose stronger passwords, IT security professionals recommend the use of password vaults (also called "password managers"), which store a user's set of passwords in a container generally encrypted using a single master password.

This encrypted container, stored together with domains and usernames in plaintext, allows users to access websites by just remembering a single password. Furthermore, it can be stored on several (potentially) insecure devices and be backed up in the cloud. Thus, an attacker might get hold of such a container [START_REF] Li | The emperor's new password manager: security analysis of web-based password managers[END_REF][START_REF] Silver | Password managers: attacks and defenses[END_REF] and mount an offline attack against the master password. In comparison to online attacks, which are likely blocked by websites detecting multiple failed login attempts, the effectiveness of an offline attack is only limited by the attacker's computational power. Brute-force attacks are likely successful, as it was shown that human-chosen master passwords have limited entropy and are relatively easy to guess [START_REF] Florencio | A large-scale study of web password habits[END_REF][START_REF] Bonneau | Guessing human-chosen secrets[END_REF].

Although current password-based encryption (PBE) schemes (e. g., PKCS#5 [START_REF] Kaliski | PKCS# 5: Password-based cryptography specification version 2[END_REF]) adopt countermeasures (like the use of a key-derivation function to increase the encryption key entropy, salting to prevent rainbow attacks, or iterative hashing to slow down brute-force attacks), none of these methods can prevent a successful offline attack, as an attacker will always be able to recognize the correctly decrypted result. In fact, all wrong master password candidates will provide a response that clearly does not resemble user-chosen passwords.

To circumvent this problem, so-called cracking-resistant password vaults (CR-PVs) have been proposed [START_REF] Bojinov | Kamouflage: loss-resistant password management[END_REF][START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF][START_REF] Golla | On the security of cracking-resistant password vaults[END_REF]. The purpose of all CRPVs is to provide an attacker with honey or decoy vaults even if she decrypts the vault under a wrong master password. These decoy vaults have to be (statistically) indistinguishable from the real vault, so that the real vault is undetectable among decoys and the attacker is forced to mount additional online login attempts to identify it.

Another area in information security that shares the protection goal of undetectability is steganography [START_REF] Fridrich | Steganography in Digital Media: Principles, Algorithms, and Applications[END_REF]. A steganographer wants to communicate a secret message over a communication channel monitored by a warden (the attacker in that scenario). The steganographer covertly communicates by modifying a socalled cover object (e.g., a digital image) and obtaining a stego object that is sent to the intended recipient, and she wants stego objects to be undetectable among cover objects by the warden.

We can summarize the contributions of our paper as follows:

1. we point out the parallels of CRPVs and steganography (Sec. 2); 2. we present a unified model of password vaults and CRPVs (Sec. 3); 3. we transfer established results and security definitions from steganography to the domain of CRPVs, show that perfect security for CRPVs is infeasible and propose the notion of ε-security instead (Sec. 4); 4. we highlight the differences between CRPVs and steganography, conjecturing that secure CRPVs are at least as hard to construct as secure steganography (Sec. 5).

Finally, we give an overview of the results obtained and future directions in Section 6.

Merging two streams of related work

The already highlighted protection goal of object undetectability represents a clear parallel between CRPVs and steganography, and both communities have made strikingly similar advances.

To overcome security weaknesses of the first CRPV system proposed in [START_REF] Bojinov | Kamouflage: loss-resistant password management[END_REF], the authors of [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] propose the NoCrack system, where decryption under any master password yields a plausible decoy vault. The instant creation of decoy vaults is achieved by applying the mechanism of Honey Encryption and Decryption [START_REF] Juels | Honey encryption: beyond the brute-force barriers[END_REF]. Despite the name, this approach does not change the encryption/decryption itself, but rather adds another encoding/decoding layer. In particular, a so-called distribution transformation encoder (DTE) encodes a plaintext into a bit string and decodes bit strings to plaintexts. The DTE is designed in such a way that random bit strings are decoded to plaintexts following a target statistical distribution, which is hard-coded into the DTE [START_REF] Juels | Honey encryption: beyond the brute-force barriers[END_REF]. For instance, an application proposed in [START_REF] Juels | Honey encryption: beyond the brute-force barriers[END_REF] is a DTE that mimics the distribution of RSA secret primes and outputs synthetic primes when decoding a uniform bit string. As we will describe in Section 3.2, a specific DTE is used in the NoCrack system to generate decoy vaults when a wrong master password is used to decrypt the container. A similar approach in steganography has been proposed in 1992, where so-called mimic functions [START_REF] Wayner | Mimic functions[END_REF] are used. Here, Huffman encoding is employed to create text that is statistically indistinguishable from human written text while embedding the secret message. The technique was then extended to arithmetic encoding in model-based steganography [START_REF] Sallee | Model-based steganography[END_REF], where parts of the cover object are replaced by other parts that follow an estimated distribution, similarly to DTEs.

To demonstrate the security of NoCrack, the authors of [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] show that a machine-learning based ranking attack cannot detect the real vault among decoys. A further improvement to the NoCrack system is proposed in the most recent work on CRPVs [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF], where the target distribution of the DTE is empirically mixed with the one of the real vault (thus decreasing the statistical difference between real and decoy vaults), and it is also tested against machine-learning classifiers. A relevant similarity to steganography exists, where machine-learning based attacks are used and the results obtained by this are employed to influence "design principles leading to more secure steganography" [8, p. 69].

The NoCrack system [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] with the extension proposed in [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] currently represents the state-of-the-art for CRPVs. In fact, [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] first shows a weakness of the NoCrack system, arguing that the correct vault can be statistically distinguished from the decoys. To achieve this, they use the Kullback-Leibler divergence (KLD) between real and decoy vault distribution, which was proposed as an information-theoretical security measure in steganography in 1998 [START_REF] Cachin | An information-theoretic model for steganography[END_REF].

Due to the high dimensionality of cover and stego objects, steganographers often design their embedding strategies according to projections of the whole objects, which are typically simplified models with lower dimensionality [START_REF] Sallee | Model-based steganography[END_REF]. On her side, the warden can employ a different projection that enables her to detect stego objects [START_REF] Fridrich | Steganography in Digital Media: Principles, Algorithms, and Applications[END_REF]. This triggered a cat-and-mouse race towards the best projection. In the same way, the DTE in CRPVs reproduces the distribution of a specific projection and the authors of [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] identify the security weaknesses of NoCrack by adopting a different one.

Summarizing, the shared protection goal of undetectability has also led to the use of similar approaches and tools, although, to the best of our knowledge, this link has not been established in the literature yet. This further motivates us to exploit known results in steganography for CRPVs regarding security issues.

Password vault model

In this section, we formalize a unified model for CRPV systems. In Section 3.1 we first introduce a general definition for vault objects and identify potential influencing factors. Then, we describe the main components of a CRPV in Section 3.2, focusing on the Honey Encryption and Decryption scheme used.

Defining password vaults

Password vaults essentially contain credential data. We can formalize credentials as triples (d,u,pw), where d is the domain, u is the username employed and pw is the secret password chosen by the user. Then, a vault v is a tuple of N credential triples that can be arranged as v = (d 1 , . . . , d N , u 1 , . . . , u N , pw 1 , . . . , pw N ).

(

) 1
In practice, d 1 , . . . , d N and u 1 , . . . , u N are plaintext while the vector

x . = [pw 1 , . . . , pw N ] (2)
containing the passwords is encrypted to a ciphertext C under a master password mpw (also user-chosen). We explicitly consider the case where domains and usernames are not encrypted, as in [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF][START_REF] Golla | On the security of cracking-resistant password vaults[END_REF], and thus the object to be modeled is given by the vector x. Then, with a slight abuse of notation, in the rest of the paper we will use the term "vault" to indicate only x instead of the entire tuple v. We can see x as a realization of a random vector X with sample space χ L (χ is the alphabet of symbols used and L is the sum of the N password lengths) and joint probability distribution P real .

The first part of v, composed by domains and usernames, can have influence on x. It is known that different websites usually adopt specific policies forcing the user to follow certain constraints in choosing the password [START_REF] Bojinov | Kamouflage: loss-resistant password management[END_REF], for instance by requiring a minimum number of symbols, a minimum number of digits and special characters, or the use of both upper-and lower-case letters. Moreover, usernames are often also human-chosen and correlation between the choice of username and password could exist. Thus, the distribution P real should be conditioned on the knowledge of domains and usernames, although existing approaches do not always exploit this information. For instance, one of the attacks in [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] specifically uses nonconformity to password policies to successfully detect the real vault among the decoys produced by NoCrack [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF].

Even if we discard the dependency on domains and usernames, estimating P real is a challenging task, since the statistical behaviour of human-chosen passwords in a vault is highly complex and hard to model. In fact, the partition of x into independent components (for instance, modeling single password distribution and assuming independence among domains) is highly questionable, as passwords of the same user are typically strongly correlated [START_REF] Bojinov | Kamouflage: loss-resistant password management[END_REF].

Thus, we deal with a joint distribution of L symbols which is hardly observable. However, existing approaches [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF][START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] employ a projection Proj(x) of the entire vector x and estimate the distribution P Proj(X) from available datasets, which is then used to generate synthetic vaults.

Mimicking vault distribution

CRPVs extend conventional PBE schemes, where a successful or unsuccessful decryption is perfectly recognized, by introducing the use of decoy vaults. We now describe how the state-of-the-art CRPV (NoCrack [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF]) works and specify which changes are proposed in [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF].

NoCrack is a CRPV system that consists of a specific Honey Encryption and Decryption scheme. As introduced in Section 2, the peculiarity of such a mechanism is the use of a DTE, which is a pair of functions (encode, decode) with the following properties:

the input of encode is a password vault x and the output is a binary string s.

Conversely, decode takes as input any bit string s and outputs a vault x. It is required that a DTE is correct, that is, decode(encode(x)) = x. -If applied to uniformly distributed bit strings, decode should output vaults whose projections follow a known distribution P Proj(X) .

The authors of [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] devise strategies based on different projections and assumptions, e.g., considering -gram and Probabilistic Context Free Grammar (PCFG) models, but the details of DTE design are out of the scope of this section.

The resulting system works as depicted in Fig. 1. For the sake of clarity, we represent the Honey Encryption (HE) and Honey Decryption (HD) modes of the CRPV separately, and for the latter we further distinguish the case of HD with the correct and wrong master password. As mentioned in Section 2, Fig. 1 shows that the DTE (encode, decode) is used in combination with a pair of functions (encrypt, decrypt), which are based on standard techniques and will not be discussed in detail (we refer the reader to [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] for a thorough description).

When the user chooses the password vault x real and the master password mpw real , the HE mode is activated (see Fig. 1(a)). The vault x real is processed by the encode function to obtain the string s real , which is then encrypted under mpw real into a ciphertext C real by means of encrypt. 1In order to get access to x real , the user has to decrypt the ciphertext C real by submitting to the system the master password mpw real , thus activating the HD mode. If C real is decrypted under the correct master password mpw real , the user gets as output the real vault x real as shown in Fig 1(b).

If an attacker trial-decrypts C real under a wrong master password, decrypt outputs a random bit string s decoy . This string is then given to decode that transforms it into a decoy password vault x decoy , which is delivered to the attacker (see Fig. 1(c)). From her side, the attacker receives a set of password vaults (as many as the number of trial-decryptions), which includes x real if and only if mpw real has been used for trial-decrypting.

Regardless of the quality of the algorithm decode (i.e., how accurately it transforms random strings into vaults following P Proj(X) ), the use of a DTE will result in a joint distribution P decoy of the decoded vaults that is an approximation of P real . They should be as similar as possible, but the quality of P decoy as approximation of P real depends on the projection chosen and the database used for the training. In fact, in the attack in [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] the authors identify the correct vault among all the decoys by exploiting a different projection P Proj(X) enabling a better distinction. Their improvement then consists exactly in designing the DTE by taking into accounts some statistical properties of the real vault.

Security of CRPV systems

In this section we discuss the security of CRPV systems. First, we compare and translate the definition of perfect security from steganography to the domain of CRPVs in Section 4.1, arguing that this is fundamentally related to the knowledge of the distribution P real . Then, in Section 4.2 we analyze the computational bounds encountered in studying P real , giving insights on the practical difficulties in estimating this distribution. Finally, we extend the definition of ε-security to the domain of CRPVs in Section 4.3.

Perfect security

In steganography, the goal of the steganographer is to transform cover objects x (0) to stego objects x (1) containing the secret message, in such a way that the resulting distribution of stego objects P stego is close to the distribution of cover objects P cover . The setup of an attack against a general steganographic system is depicted in Fig. 2(a): depending on the position of the switch (red), cover or stego objects appear on the communication channel. The warden does not control the switch but monitors the channel and applies detect to every object x (i) that she observes. The output of detect is either 0 indicating that the object communication channel

x (0)
x (1) detect is assumed to be a cover object or 1 if the warden classifies it as stego. The warden wants to identify a secret communication, so her goal is to detect the stego objects among covers.

/ x (i) n i ∈ {0, 1} (
Attacks against CRPVs can be translated to a very similar setup, as depicted in Fig. 2(b). Here, the attacker has an encrypted password vault C real and chooses a set of n master passwords for trial-decryption that might contain the real master password mpw real but will be mostly composed of wrong passwords mpw wrong . Again, the switch (red) indicating whether the chosen password was real or wrong is not under the control of the attacker, although she can decide which and how many master passwords to submit. By this, she ends up with n different password vaults x i and she also applies detect to every object x i she observes. The output of detect is either real, indicating that x i was generated by inputting mpw real or decoy, if a mpw wrong was chosen. The goal of the attacker is to detect the real vault among the decoys.

Figure 2 opens the way for a formal relationship between P cover and P stego from steganography and P real and P decoy in CRPVs. Intuitively, we can view the distribution of real vaults P real as the counterpart of the cover distribution P cover , as both are given by nature and cannot be influenced by either the attacker nor the defender. Both, the distribution of the decoy vaults P decoy and the stego distribution P stego somehow depend on P real and P cover , respectively.

Based on this analogy, we can recall the definition of perfectly secure steganographic system given in [START_REF] Cachin | An information-theoretic model for steganography[END_REF] and extend it to CRPVs. According to [START_REF] Cachin | An information-theoretic model for steganography[END_REF], perfect security in steganography is achieved if and only if the Kullback-Leibler divergence (KLD) between P cover and P stego is zero, i.e.: KLD(P cover ||P stego ) = 0.

(

) 3
Accordingly, perfect security in CRPV systems is achieved iff:

KLD(P real ||P decoy ) = 0. ( 4
)
In light of that, the action of the detect function in the CRPV domain can be formulated in an hypothesis testing framework, where the null and alternative hypotheses are given by: H 0 : the observed object follows P real (i.e., it is a real vault) H 1 : the observed object follows P decoy (i.e., it is a decoy vault)

(5)

The identification of the real vault is achieved by repeatedly performing the hypothesis test on the n vaults by means of detect. Having zero KLD between two distributions essentially means that they are exactly the same distribution. Thus, with perfect security, the hypotheses in (5) are undecidable.

A fundamental question is whether perfect security in the sense of ( 4) is possible at all and under which assumptions. In steganography, it is commonly agreed upon by now that this is only possible for so-called artificial cover sources, i.e., sources for which the joint distribution P cover is fully known, including any conditional dependencies. However, artificial sources do rarely exist in practice. In contrast to that, we deal with empirical cover sources, whose distribution is obtained outside the steganographic system from a finite set of observations.

The difference between artificial and empirical cover sources has been proposed in [START_REF] Böhme | An epistemological approach to steganography[END_REF], where it is observed that perfect security defined as in (4) generally exists for artificial sources but is impossible for empirical sources. This is related to the fact that in the latter case P cover is arguably incognisable, and statistical representations by means of proper projections of the sample space will never achieve a zero KLD.

As mentioned in Section 3.2, existing datasets with a finite number of vaults are used to train the DTEs, which then replicate specific statistical properties observed (for instance, -gram statistics or PCFG statistics). In the next section, we show how hard it is to provide a full characterization of P real , arguing that P real belongs to the class of empirical distributions and is indeed incognisable.

Computational bounds for the estimation of P real

As we introduced in Section 3, in order to fully represent real vaults x, we should consider them as vectors of L symbols regardless of the actual partitioning in different passwords. Thus, each x is the realization of a L-dimensional discrete random vector X = [X 1 , . . . , X L ] and the corresponding distribution function P real is a joint distribution of L random variables with sample space χ.

Then, P real can be expressed by means of the chain rule as follows:

P real (x) = L =1 P X |X 1: -1 =x 1: -1 (x ), (6)
where X i:j is the random vector composed of the random variables (r.v.) in X from index i to index j and x i:j is its realization, P X|Y=y (•) is the conditional probability mass function (cpmf) of a r.v. X given the realization y of a random vector Y and we define P X1|X1:0 (x 1 ) . = P X1 (x 1 ). Let us now suppose to estimate P real starting from an available dataset of password vaults, i.e., to approximate each cpmf by means of relative frequencies. In the following, we perform a simple feasibility analysis where we compute the minimum numerosity of the dataset that is necessary to estimate the cpmfs. In doing that, we first consider the joint distribution P real in a) and then the case of a specific projection (Markov models) in b) and c): a) Joint distribution. We want to have an approximation of every cpmf in [START_REF] Filler | Minimizing additive distortion in steganography using syndrome-trellis codes[END_REF]. Thus, we need P X |X 1: -1 =x 1: -1 (•) for each possible realization x 1: -1 of X 1: -1 , and this holds for = 1, . . . , L. A pictorial representation is reported in Fig. 3(a). For each a number of |χ| -1 cpmfs are then involved. Thus, even assuming that each cpmf is estimated by one single observation (i.e., the support of each cpmf will consist in a single character) the number of necessary vaults is given by |χ| -1 . If γ = log 10 (|χ|), it is then O(10 γ( -1) ).

x xL X L X 1: -1 X1:L-1 P X |X 1: -1 =x 1: -1 (x ) P X L |X 1:L-1 =x 1:L-1 (xL) (a) Joint distribution x xL X L X -¯ +1: -1 X L-¯ +1:L-1 P X |X -¯ +1: -1 =x -¯ +1: -1 (x ) P X L |X L-¯ +1:L-1 =x L-¯ +1:L-1 (xL) (b) Markov chain
Let us consider an optimistic setup where a vault contains 10 passwords with average length of 5 characters [START_REF] Bojinov | Kamouflage: loss-resistant password management[END_REF][START_REF] Florencio | A large-scale study of web password habits[END_REF], so that we can reasonably fix L = 50. Moreover, let us assume an alphabet corresponding to the printable ASCII characters, thus |χ| = 95 and γ ≈ 1.97. The number of vaults required for the estimation of every P X50|X1:49=x1:49 (•) with one observation would have a decimal order of magnitude at least equal to γ(50 -1) = 96.5. The number of protons in the universe is estimated by the Eddington number and it is assumed to have on order of magnitude equal to 79. It is worth pointing out that password policies could reduce this number as not the whole alphabet should be used. However, even supposing a restrictive policy where only digits are allowed, this would still result in 10 49 necessary vaults.

b) Markov chain of order ¯ -1. In [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] and [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF], DTEs based on ¯ -gram models are trained on an external corpus. As an example, they consider ¯ = 4 and estimate the cpmf P X4|X1:3=[H,e,l] (l) as the number of occurrences of the substring "Hell" divided by the number of occurrences of the substring "Hel" in the corpus. Then, by repeating this for each 3-grams, they estimate a cpmf for each of them and use it to design the DTE. 2This is equivalent to considering Markov chains of order ¯ -1, that is, it is assumed that the probability of a character in a certain position depends only on the previous ¯ -1 characters in the vault. As represented in Fig. 3(b), expression ( 6) is then approximated as

P real (x) ≈ P X1 (x 1 ) • . . . • P X¯ -1 |X 1: ¯ -2 =x 1: ¯ -2 (x¯ -1 ) • L = ¯ P X |X -¯ +1: -1 =x -¯ +1: -1 (x ). (7)
Again, to obtain each cpmf in expression [START_REF] Florencio | A large-scale study of web password habits[END_REF] we would need to observe at least once each possible realization of each X i:j such that j -i = ¯ -1, and we can again consider a lowerbound of the minimum number of necessary vaults to be O(10 γ( ¯ -1) ). We report in Table 1 the exponent γ( ¯ -1) as a function of ¯ in the same setup as before (|χ| = 95). Table 1. Order of magnitude of the minimum number of vaults necessary to the estimation of all the cpmf's when considering a Markov chain of order ¯ -1.

A proper length of the Markov chain is hard to determine and the choice relies on heuristic considerations. However, as we optimistically assumed an average password length equal to 5 symbols, in order to capture the dependencies between different passwords in the vault we should at least consider a Markov chain of order 5 ( ¯ =6), so that the probability of the 6-th symbol (likely the first character of the second password) depends also on the realization of the first one. From Table 1, we have that a dataset of at least 7.7 billion (≈ 10 9.89 ) vaults would be necessary for this purpose. As of December 2016, the world population was estimated at 7.5 billion, thus implying that the dataset should contain at least one vault for every human being on earth. c) Markov model of order ¯ -1 with relaxed assumptions. We can assume that, for a fixed ¯ , only a fraction p of the cpmfs is actually relevant and the remaining ones can be considered as uniform or estimated via smoothing techniques, as suggested in [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF] when building the Markov-based DTE. Then, we can assume that a number of observations T > 1 is required for each cpmf in order to have a more accurate approximation. By doing so, the number of vaults is lower bounded by p

• |χ| ¯ -1 • T , thus it is O(10 δ+γ( ¯ -1)
) where δ = log 10 (pT ). The order of magnitude δ + γ( ¯ -1) is tabulated in Table 2 for different values of p and T and ¯ fixed to 6. The values show that even considering as relevant the 0.1% of the realizations of X 1:5 and accepting a single observation of each related cpmf (T = 1) would require a number of vaults that almost equals the population of Austria (around 8.5 million). In this framework, we should consider that, while the popular RockYou dataset contains more than 32 million passwords in total, the only database of vaults available at the moment (PBvault, see [START_REF] Chatterjee | Cracking-resistant password vaults using natural language encoders[END_REF]) consists of 276 vaults only. Coupled with the analysis above, which already relies on simplifying assumption like the independence of password from domains and usernames, this strongly motivates our concern on the observability of the full distribution P real , or even an approximated version of it. So, we can safely say that P real is incognisable.

ε-security

According to our observations in the last subsection, the equality in (4) expressing perfect security is hardly achievable in practice, thus suggesting to consider a non-zero statistical distance between P real and P decoy . In [START_REF] Cachin | An information-theoretic model for steganography[END_REF], the definition of ε-security is introduced, where a system is called ε-secure if

KLD(P real ||P decoy ) ≤ ε. ( 8
)
If we recall the hypothesis testing framework in (5), we can encounter two different kind of errors:

Type I error: classifying the real vault as a decoy.

Type II error: classifying a decoy vault as the real one.

Denoting with α and β the probabilities of Type I and Type II errors, respectively, inequality ( 8) is relevant to derive bounds for α and β. With this respect, the Type I error is more relevant than the Type II error for an attacker, since once the real vault is discarded there is no other possibility to successfully obtain the correct passwords. If we accept non-zero KLD, and thus, that α and β cannot be minimized at the same time, we can reasonably think that an attacker would try to achieve α = 0 to the detriment of β. It can be shown [START_REF] Maurer | A unified and generalized treatment of authentication theory[END_REF][START_REF] Cachin | An information-theoretic model for steganography[END_REF] that, if [START_REF] Fridrich | Feature-based steganalysis for JPEG images and its implications for future design of steganographic schemes[END_REF] holds and α = 0, the Type II error probability is subject to the lower bound

β ≥ 2 -ε . (9)
Inequality ( 9) provides an interesting link to the required number of online login attempts. In fact, in performing brute force attacks, the attacker will be provided with a set of n vaults, supposedly including the real one. If she enforces α = 0 (i. e., the real vault is not misclassified), the number φ of plausible candidate vaults identified by detect will be approximately at least:

φ = 1 + (n -1)2 -ε . ( 10
)
Assuming no further refinements of the candidate selection, φ /2 represents the expected number of online login attempts the attacker is forced to execute. This also addresses an issue that was not explicitly discussed in [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF], i.e., the relationship between the ability of detecting the real vault and the total number of decoy vaults. In fact, the authors of [START_REF] Golla | On the security of cracking-resistant password vaults[END_REF] consider n = 1000 (including the real vault), while an attacker will have to deal with a dramatically higher value of n (equal to the number of trial decryptions) and the performance of the ranking operation in this case is not studied.

Differences between steganography and CRPVs

Previous sections concentrated on the similarities of steganography and CRPVs, neglecting obvious differences. In this section, we highlight the main differences and point out their influence on the security of both systems.

(i) Message embedding. The most obvious difference between steganography and CRPVs is that in steganography we want to embed a message, which has no direct counterpart in CRPVs. But, in accordance with steganography literature, message embedding can be either seen as a randomization of encode or naturally implemented in an adapted version of the DTE. The message encoding problem in steganography is mainly solved, due to the existence of asymptotically perfect codes [START_REF] Filler | Minimizing additive distortion in steganography using syndrome-trellis codes[END_REF]. So, this difference will not affect the security comparison. (ii) Attacker's influence. Another evident difference is the role of the attacker: in steganography, the warden passively monitors the communication channel and has little influence on the total number n of objects she observes or the relative amount of cover or stego objects. In contrast to that, an attacker against a CRPV can choose (up to her computational bound) how often she samples P decoy and, thus, might refine her model of P decoy as accurately as her computational power allows. Even with knowledge of the steganographic algorithm, this is not possible for a warden. Furthermore, with CRPVs the attacker knows that there is at most one real vault. This additional knowledge of an attacker against CRPVs, most likely will have a negative influence on the achievable security of CRPVs. (iii) Guessing strategy. Another degree of freedom that is available to an attacker against CRPVs but not to a steganographic warden is the guessing strategy for the master passwords. If we assume that master passwords are human-chosen, every strategic attacker will choose master passwords in decreasing order of probability, following some model about the prior distribution of master passwords P mpw . For the same arguments explored in Section 4.2, P mpw is incognisable. But, the lower dimensionality with respect to P real and the higher number of (single) passwords available, e. g., RockYou, would allow for a more accurate estimate of the joint distribution. (iv) Oracle queries. Finally, the possibility of confirming or disproving a vault candidate identified by detect with an online login is probably the highest advantage an attacker against a CRPV has over a warden in steganography. Each online login acts like an oracle query, and the number is only limited by the number of passwords in the vault and the maximum number of wrong login attempts allowed by the different websites. The attacker against a CRPV not only exactly knows when she has the real vault, even negative oracle responses can be used to further refine her estimate of P decoy and thus possibly further decreasing β. A warden can only dream of such an oracle in steganography.

Summarizing the above, we conjecture that secure CRPVs are at least as hard to construct as secure steganography. Although far away from a formal proof, the existing differences between steganography and CRPVs suggest that the advantage in knowledge an attacker against any CRPV possesses over a warden in steganography will make security of CRPVs ever harder to achieve.

Ultimately, achievable security depends on the evolution of the real distributions. If a cover channel consisting of noise is plausible, then secure steganography reduces to cryptography with the protection goal of indistinguishability of ciphertexts from random sequences. If the users of password vaults choose truly random passwords, constructing secure CRPVs reduces to the generation of random looking sequences. But then, we do not need CRPVs anymore.

Conclusion

In this paper we have shown that the parallels between CRPVs and steganography go deeper than the protection goal of undetectability: both fields experienced a similar development, starting from encoding schemes and ending with the employment of machine learning to influence the design of more secure schemes.

While research on CRPVs only started in 2010, the field of digital steganography can look back on more than 25 years of scientific research, thus allowing us to transfer known results to the domain of CRPVs. We believe that leveraging established results in steganography will increase the awareness of researchers when designing new approaches to CRPVs.

Specifically, we argued that the joint distribution of real vaults P real is incognisable, due to the data requirements for its full estimation. Even for an approximated version, a dataset containing one password vault for every human being currently living on earth would be needed. The incognisability of P real implies that achieving perfect security in CRPVs is as hard as constructing perfectly secure steganographic systems in case of empirical sources, thus infeasible in practice. We follow up by arguing that we should rather consider ε-security instead of perfect security. Again, we can leverage established results in steganography and show that we can lower bound the expected amount of online login attempts an attacker is forced to execute when attacking an ε-secure CRPV.

Finally, we conjecture that security in CRPVs is at least as hard to achieve as security in steganography due to the differences in both domains' setup. An attacker against a CRPV has several advantages when mounting an attack over a warden in steganography: she can choose the number of trial-decryptions, thus getting a very accurate estimate of the distribution of decoy vaults; she can apply an advanced guessing strategy against the master password, following recent research on how humans choose passwords; and, last but not least, every online login attempt acts as an oracle query, giving the attacker a certain response on whether the vault she faces is the real one or a decoy.

Future work should include formal proofs regarding the effects of the attacker's knowledge on the security of CRPV systems. Moreover, we believe that the conceptual link between steganography and CRPVs is based on the employment of Honey Encryption. Thus, our observations could be extended to other applications of Honey Encryption in practical systems.

  Honey Encryption of the user-chosen password vault. CRPV (HD mode) C real mpw real decrypt s real decode x real ∼ P real (b) Honey Decryption under the correct master password. CRPV (HD mode) C real mpwwrong decrypt s decoy decode x decoy ∼ P decoy (c) Honey Decryption under a wrong master password.

Fig. 1 .

 1 Fig. 1. Honey Encryption and Decryption mechanisms in CRPVs.

Fig. 2 .

 2 Fig. 2. Comparison of attacks against steganography and CRPVs

Fig. 3 .

 3 Fig. 3. Representation of the joint and Markov chain distributions.

  -1) 1.97 3.96 5.93 7.91 9.89 11.89 13.84 15.82 17.80

Table 2 .

 2 Lowerbound of the minimum number of vaults for the estimation of all the cpmfs when considering a Markov chain of order 5.

	p/T 1	5	10	20
	0.001 6.85 7.55 7.85 8.15
	0.2 9.15 9.85 10.15 10.45
	0.4 9.45 10.15 10.45 10.75
	0.6 9.63 10.33 10.63 10.93
	0.8 9.75 10.45 10.75 10.05

In case of password addition or updating, x real is modified and encoded to a new string s real , which is then encrypted under mpw real to obtain a new ciphertext.

It is to be noted that the authors estimate the cmpfs from datasets of single passwords instead of entire vaults.

Acknowledgments. This research was funded by Deutsche Forschungsgemeinschaft (DFG) under grant "Informationstheoretische Schranken digitaler Bildforensik" and by Archimedes Privatstiftung, Innsbruck, Austria.