Per-session security: Password-based cryptography revisited

Abstract

Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved.

Keywords

Password-based encryption simulation-based security random oracle

1. Introduction

1.1. Motivation of this work

Human-memorable passwords represent one of the most widely deployed security mechanisms in practice. They are used to authenticate human users in order to grant them access to various resources such as their computer accounts, encrypted files, web services, and many more. Despite well-known problems associated with this mechanism, its practicality and simplicity from the users’ perspective is the main cause of its persisting prevalence. As an example, more than 90% of Google users employ passwords as the only authentication mechanism for accessing their accounts [28]. Acknowledging this situation, it is important that security engineers, including designers of cryptographic protocols, have a precise understanding of the security guarantees that passwords provide, especially for multiple sessions. We use the general term session here to refer to one use of a password in a protocol, such as one encryption and decryption in password-based encryption, or one login to a server.1

¹
This is also referred to as the multi-user setting in the literature, but we prefer the term session here since the same user can participate in multiple sessions.

There has been significant effort in formalizing the use of passwords, but the standard provable-security approach in cryptography, focusing on a single session, falls short of modeling the expected guarantees. The main reason for this is that passwords, in contrast to cryptographic keys, can be guessed by the attacker with a probability that can hardly be considered insignificant in the analysis (independently of whether a concrete or asymptotic security approach is being used). This is because they are chosen by the users, and therefore typically do not contain sufficient entropy. When inferring the security guarantees for multiple sessions via the standard hybrid argument, these substantial terms from the analyses of the individual sessions accumulate, and may render the overall statement trivial.

To obtain practically relevant statements about systems that allow for many sessions with passwords, one cannot resign on all security guarantees as soon as any password is guessed. Ideally, one would instead hope that as long as not all passwords were broken, the sessions with passwords that are still safe from the attacker enjoy a non-reduced degree of security. This simple yet important observation has been emphasized before, most notably in the work of Bellare et al. [6] on multi-instance security. At a very high level, their definition aims at ensuring that, in a setting where the security of each single session cannot be guaranteed, the amount of work needed for breaking many sessions cannot be amortized, i.e., it grows (linearly) with the number of sessions attacked.

This approach, while bringing to light a problem of great practical relevance, still suffers from certain shortcomings that can be illustrated on the example of password-based cryptography. By focusing only on the number of sessions that can be broken, multi-instance security cannot capture the intuition that sessions protected by strong passwords should be less vulnerable than sessions protected by weak passwords. Indeed, as the resulting guarantees are in the form of a global upper bound on the number of sessions that can be broken, they do not give any specific guarantee for a session whose password was not guessed, independently of whether other sessions were compromised.

From a broader perspective, a setting with multiple sessions relying on passwords can be seen as an instance of a scenario where the considered resource (e.g., a webmail server) can be gradually weakened by the adversary (e.g., by guessing the passwords in some of the sessions), while it is still expected to provide some security guarantees (e.g., for the other sessions) after such weakening.

1.2. Contributions of this work

This paper develops a technique for modeling resources that are available to parties and used in protocols or applications and can be gradually weakened (referred to as “downgrading”). Later, the technique is applied to password-based cryptography in the random oracle model, for analyzing the security of schemes that use password-derived keys. This work is a corrected and extended version of the conference paper with the same title [14].

Downgradable resources. The first contribution is a natural and intuitive formalization of settings where a considered resource can be potentially downgraded by the actions of an attacker, but still maintains some security guarantees afterwards. While there are many possible ways to analyze such settings, the proposed formalization allows for the natural decoupling of the descriptions of (1) the resource’s behavior at various “levels” of the downgrade; and (2) the mechanism that controls how the system is currently downgraded (as a response to the actions of the attacker). This modularity allows for simpler analyses of a wide range of resources that can be seen in this way, with the concrete case of password-based cryptography being discussed below. The technique is, however, more general, and may also find applications in other scenarios where guarantees may degrade gradually, such as the failure of (some) computational assumptions.

The modeling as proposed is carried out in the constructive cryptography framework [20,22] and does not require any modifications of its security definitions. A similar approach will be possible in any simulation-based framework, although in particular an analogy in the universal composability framework [9] will require care in bounding the number of machine instances in the formalization of the concrete type of statement discussed here.

Applications to password-based cryptography. The second contribution consists of applying the above modeling approach to several settings that involve multiple sessions using cryptographic keys derived from hashing passwords in the random oracle model. The potential downgrading considered here corresponds to guessing the passwords in some of the sessions.

Idealizing the hash function as a random oracle, a natural expectation for any such setting is that one obtains a per-session guarantee, i.e. that as long as the attacker does not guess a password in a particular session, the security guarantees provided in this session remain identical to the case where a perfect key is used (i.e., chosen uniformly at random from a large key space). In particular, the security guarantees of one session are not influenced by other sessions, such as by other users’ poor choice of a password.2

²
While this strong isolation between different sessions is naturally expected for password-based encryption, it may be less so in other settings with shared resources such as access to a common server, where shared data may be exposed or access with user permissions may enable privilege-escalation attacks.

This intuitive view is not generally correct. The reason of this breakdown (which is a variant of the commitment problem that occurs in adaptive attacks on public-key encryption) is explained below, and a series of results discussed below draws a map of settings that do/do not succumb to this problem:

Password-based MACs. If the password-derived keys are used by a MAC to authenticate insecure channels, per-session message authentication is achieved.

Single-session PBE. For password-based (symmetric) encryption (PBE), obtaining a composable statement (i.e., in a simulation-based framework) is much more delicate even in a single-session case. The reason for this is that, roughly speaking, the simulator in the ideal world is expected to produce a simulated ciphertext upon every encryption and without any knowledge of the actual plaintext. However, if the distinguisher later guesses the underlying password, and hence can derive the encryption key, it can easily decrypt the simulated ciphertext and compare the result to the (known) plaintext. But the simulated ciphertext essentially committed the simulator to a message (or a small subset of the message space), so the check will fail with overwhelming probability. Nonetheless, in the single-session setting, PBE is still secure in the expected sense.

Multi-session PBE. In line with the motivation, the desired result would be to obtain per-session confidentiality, an analogue of the above single-session statement for the setting with multiple sessions. Surprisingly, lifting this positive result to the multi-session setting is unachievable. Roughly speaking, any construction of r secure channels from r authenticated channels and the corresponding r password-derived keys will suffer from a simulation problem analogous to the single-session case described above. Yet, in the multi-session case, the simulation problem provably cannot be overcome.

Multi-session PBE with local assumptions. To side-step the above impossibility statement, the next result considers the setting of password-based encryption under an additional assumption that the number of adversarial password guesses in each of the sessions is a priori known.

While this assumption seems implausible in general, there may be specific settings in which the validity of the per-session bounds can be argued. The paper shows that the assumption of local bounds is sufficient to overcome the commitment problem, and proves that the intuitively expected guarantees described above are indeed achieved. The simulator constructed in the proof, however, depends on the password distribution.

Salting. Salting is widely used as a domain-separation technique for hash functions, and can be understood as constructing from a single hash function multiple hash functions that can be used in different sessions. It is, however, shown that salting leads to a setting where the adversary’s resources spent in the sessions can only be bounded globally. Together with the above result, this implies that salting cannot be used together with PBE for obtaining independent sessions.

PBE scheme from PKCS #5. Finally, it is observed that the arguments underlying the above impossibility result in items 3 and 5 apply to the password-based encryption as standardized in PKCS #5 [17].

Composability. Overall, the results shown in this paper yield a characterization of when password-derived keys can be used in a composable simulation-based security framework for the task of secure communication. The aim for strong, composable security guarantees is motivated by the particular relevance of password-based cryptography in the Internet, where various cryptographic schemes are used concurrently and as building blocks of larger protocols. The impossibility results are therefore also stated with respect to this strong and general definition; they do not rule out more specific and restricted security definitions that may be sufficient for certain applications.

1.3. Related work

Beyond the work on multi-instance security by Bellare et al. [6] that was discussed in the introduction above, there are large amounts of literature on passwords. On the empirical side, the weaknesses of passwords in practice were studied e.g. in [26].

For password-derived keys, most provable-security works focused on the single-session setting, analyzing ways to augment the key-derivation process to slow down offline brute-force password-guessing attacks. Techniques to achieve this include salting (which was introduced in a scenario with multiple users but without a provable-security analysis) [17], iteration [6,13,24,30], and hashing with moderately hard-to-compute functions [2,11,27]. However, the security analyses of those works have a different aim from this one as none of them considers the multi-session scenario. A notable, already mentioned exception is [6] which studied key derivation functions proposed in PKCS #5 [17] and did focus on security in a setting with multiple users.

A key-recovery security definition for password-based encryption was given in [1], but here also only single-session security was considered.

Finally, a separate line of work aims at realizing password-authenticated key exchange (PAKE) protocols [5,10,15,18] that prevent the possibility of offline password-guessing attacks and result in keys that can then safely be used for encryption or authentication. While some of these results are obtained in a composable, simulation-based framework and hence extend naturally to the multi-session case, the protocols are intrinsically interactive and cannot be used in non-interactive password-based settings such as the ones discussed in this work.

1.4. Structure of this paper

Section 2 contains preliminaries such as notational conventions and definitions that are needed for the technical sections. Section 3 introduces the formal model of downgradable systems that is used to model the failure of security guarantees, such as through a guessed password. The first application appears in Section 4, where we discuss the key-derivation from a password via a hash function that is modeled as a random oracle. Section 5 shows that using these password-derived keys in MACs achieves the desired per-session guarantee, namely that each authentication is individually secure unless the corresponding password is guessed. Section 6 discusses the more intricate case of password-based encryption, showing that while for a single session PBE satisfies the expected security guarantee, achieving a per-session guarantee for multiple sessions is impossible if only a global bound on the attacker’s resources is known. Yet, if one assumes a stronger, local bound, then security becomes possible. The section also shows that the salting technique for separating the domain of a hash function only leads to a global bound on the attacker’s resources. Finally, Section 7 sets the results shown in this work into a broader perspective.

2. Preliminaries

2.1. Basic notation

Sets are denoted by calligraphic letters or capital Greek letters (e.g., $X, Σ$ ). Throughout this paper, only discrete random variables will be considered. A discrete random variable will be denoted by an upper-case letter X, its range by the corresponding calligraphic letter $X$ , and a realization of the random variable X will be denoted by the corresponding lower-case letter x. Unless stated otherwise, $X $ \leftarrow X$ denotes a random variable X selected independently and uniformly at random from $X$ . A tuple of r integers $(q_{1}, \dots, q_{r})$ will be denoted by a vector symbol $\vec{q}$ . The set of bit strings of finite length is denoted ${0, 1}^{*}$ and $x ∥ y$ denotes the concatenation of two bit strings x and y. The empty bit string is denoted ◇, while ◆ is used as an error symbol.

2.2. Systems

Many cryptographic primitives (e.g. block ciphers, MAC schemes, random functions) can be described as $(X, Y)$ -random systems [23] taking inputs $X_{1}, X_{2}, \dots \in X$ and generating for each input $X_{k}$ an output $Y_{k} \in Y$ . In full generality, such an output $Y_{k}$ depends probabilistically on all the previous inputs $X_{1}, \dots, X_{k}$ as well as all the previous outputs $Y_{1}, \dots, Y_{k - 1}$ . Three distinct types of random systems will be considered: resources, converters and distinguishers.

Resources and converters. Resources that can be accessed by multiple parties can be viewed as random systems with multiple interfaces and formalized by making an interface identifier an explicit part of the input (or output). The resources in this work have three interfaces, which are naturally labeled by elements of the set ${A, B, E}$ , for Alice’s, Bob’s and Eve’s interface, respectively. As a notational convention, generic resources are generally denoted by upper-case bold-face letters, such as R or S, and specific resources are denoted by upper-case sans-serif words, such as ${KEY}^{}$ for a shared secret key resource or ${AUT}^{}$ for an authenticated channel resource.

A strategy (or protocol machine) employed locally by a party is modeled by a converter, which can also be viewed as a random system with two interfaces: an inside interface and an outside interface, denoted by $in$ and $out$ , respectively. In this view, the inside interface is attached to the i-interface of a resource and models how the scheme makes use of this resource, where $i \in {A, B, E}$ , while the outside interface of the converter becomes the i-interface of the composite system and models how the scheme can be used in applications and higher-level protocols. A protocol then corresponds to a pair of converters, one for each honest party. Converters are denoted by lower-case Greek letters (e.g., $α, σ$ ) or in sans-serif fonts (e.g., $enc, dec$ ). The set of all converters is denoted by Σ. Attaching the inside interface of a converter α to the i-interface of a resource R is denoted by $α^{i} R$ and the resulting system is again a resource. There is an identity converter $id$ , which satisfies ${id}^{i} R = R$ . Any two converters α and β can be composed sequentially, denoted $β \circ α$ , by connecting the inside interface of β to the outside interface of α. It can then be shown that the operations described are such that ${(β \circ α)}^{i} R = β^{i} (α^{i} R)$ , and that the application of converters at different interfaces h and i commute in the sense that $α^{h} β^{i} R = β^{i} α^{h} R$ .

For two resources R and S, their parallel composition is denoted by $[R, S]$ . For each interface $i \in {A, B, E}$ , the i-interface of R and S are merged and become the sub-interfaces of the i-interface of $[R, S]$ , which are denoted by $i_{1}$ and $i_{2}$ , respectively. A converter α that connects to the i-interface of $[R, S]$ has two inside sub-interfaces, denoted by ${in}_{1}$ and ${in}_{2}$ , where the first one connects to $i_{1}$ and the second one to $i_{2}$ . Any two converters α and β can also be taken in parallel, denoted $⟨ α, β ⟩$ , which can be defined such that ${⟨ α, β ⟩}^{i} [R, S] = [α^{i} R, β^{i} S]$ . These parallel composition operations and associated notations extend to the case of more than two systems in a straightforward manner.

Distinguishers and reductions. A natural notion of similarity for resources is based on the concept of distinguishing. Intuitively, a distinguisher D can be viewed as a random system that connects to all the interfaces of a resource R, interacts with this resource, and at the end of this random experiment outputs a single bit denoted B. The probability that the bit B is 1 in this experiment is written as $P^{D R} (B = 1)$ . For two resources R and S, the distinguishing advantage of a distinguisher D in telling apart R from S is then defined as $\begin{matrix} Δ^{D} (R, S) : = | P^{D R} (B = 1) - P^{D S} (B = 1) | . \end{matrix}$ The resources R and S are said to be equivalent, denoted $R \equiv S$ , if $Δ^{D} (R, S) = 0$ for all distinguishers D. A distinguisher D emulating a converter α at interface $i \in {A, B, E}$ induces a new distinguisher, denoted $D α^{i}$ , defined by $Δ^{D α^{i}} (R, S) : = Δ^{D} (α^{i} R, α^{i} S)$ .

The proofs in this paper will often reduce one distinguishing problem to another one. That is, a distinguisher D trying to tell apart two resources U and V is transformed into a new distinguisher whose task is instead to distinguish the resource R from S. Such a reduction is done by exhibiting a reduction system C which translates one setting into the other. More formally, such a reduction system C is a converter (with one inside and one outside interface), where the inside interface of C connects to the merged interfaces of the resource R, denoted $C R$ , and the outside interface of C can be accessed by a distinguisher. To reduce the task of distinguishing U from V to that of R and S, one exhibits a reduction system C such that $U \equiv C R$ and $V \equiv C S$ . For all distinguishers D it then follows that $Δ^{D} (U, V) = Δ^{D} (C R, C S) = Δ^{D C} (R, S)$ , where the last equality comes from the fact that C can also be thought of as being part of the distinguisher.

2.3. Games

A central tool in deriving an indistinguishability proof between two systems is to characterize both systems as being equivalent until a certain condition arises [7,23]. Thus, being able to distinguish both systems requires to provoke this condition, and one is then interested in upper-bounding the probability of this event. Interacting with a random system in order to provoke a certain condition is naturally modeled by defining an additional monotone binary output (MBO) on the original system, where the binary output is monotone in the sense that it is initially set to 0 and that, once it has turned to 1, it can not turn back to 0. An $(X, Y \times {0, 1})$ -system where the second output component is monotone is often indicated by using a system symbol with a hat, such as $\hat{R}$ . In this context, the system $\hat{R}$ is often referred to as a game, where winning the game means setting the MBO $A_{1}, A_{2}, \dots$ to 1, where $A_{1}, A_{2}, \dots$ are the values of the MBO after $1, 2, \dots$ rounds of interaction.

For an $(X, Y \times {0, 1})$ -system $\hat{R}$ with an MBO, the $(X, Y)$ -system obtained from $\hat{R}$ by ignoring the MBO will usually be referred to as R (i.e., simply omitting the hat). Two $(X, Y \times {0, 1})$ -systems $\hat{R}$ and $\hat{S}$ with an MBO $A_{1}, A_{2}, \dots$ are said to be game equivalent, denoted $\hat{R} \overset{g}{\equiv} \hat{S}$ , if they behave identically as long as they are not won.

Given a distinguisher D and an $(X, Y \times {0, 1})$ -system $\hat{R}$ with an MBO, denote by $Γ^{D} (\hat{R})$ the probability that D provokes the MBO in the random experiment formed by D interacting with $\hat{R}$ . In this context, D will often be referred to as a game winner.

Lemma 1 ([21, Lem. 1, 2]).

Let $\hat{R}$ and $\hat{S}$ be two games such that $\hat{R} \overset{g}{\equiv} \hat{S}$ . Then, for any distinguisher D $\begin{matrix} Δ^{D} (R, S) ⩽ Γ^{D} (\hat{R}) = Γ^{D} (\hat{S}) . \end{matrix}$

2.4. The construction notion in the (Alice, Bob, Eve)-setting

The security of protocols is formalized by the following notion of construction, which was introduced in the work of Maurer [20] and is a special case of the abstract cryptography framework developed by Maurer and Renner [22]. To be considered secure, a protocol must satisfy two requirements. First, the protocol must construct the desired resource in a setting where no attacker is present. This condition is referred to as the availability or correctness condition and excludes trivial protocols. Second, the protocol must also construct the desired resource when the adversary is present, which is referred to as the security condition. This condition requires that everything the adversary can achieve in the real-world system (i.e., the assumed resource together with the protocol) he can also accomplish in the ideal-world system (i.e., the desired resource with the simulator). The two conditions are stated with respect to pairs of resources $(R, R_{⊥})$ , where $R_{⊥}$ stands for the resource R when no adversary is present. (Formally, $R_{⊥} : = γ^{E} R$ for some converter γ modeling the actions of a non-malicious adversary.)

Definition 2.
Let $ε_{1}$ and $ε_{2}$ be two functions mapping each distinguisher D to a real number in $[0, 1]$ . A two-party protocol $π : = (α, β) \in Σ^{2}$ constructs a pair of resources $(S, S_{⊥})$ from an assumed pair of resources $(R, R_{⊥})$ relative to simulator $σ \in Σ$ and within $ε : = (ε_{1}, ε_{2})$ , denoted $(R, R_{⊥}) \overset{(π, σ, ε)}{⟾} (S, S_{⊥})$ , if $\begin{matrix} \{\begin{matrix} Δ^{D} (α^{A} β^{B} R_{⊥}, S_{⊥}) ⩽ ε_{1} (D) & (availability) \\ Δ^{D} (α^{A} β^{B} R, σ^{E} S) ⩽ ε_{2} (D) & (security), \end{matrix} \end{matrix}$ for all distinguishers D.

In many construction statements in this paper, the distinguisher may access the real- and ideal-world systems only in a restricted manner; for instance, the number of queries allowed at a certain interface of a system may be bounded. This is formalized by having the system return fixed “error” symbols to queries at all interfaces after such a bound is exceeded. The bound may be defined in a resource or in one of the converters, and is signified by outputting a value ⊤.

An important property of Definition 2 is its composability. Intuitively, if a resource S is used in the construction of a larger system, then the composability implies that S can be replaced by $α^{A} β^{B} R$ without affecting the security of the composed system. Availability and security are preserved under sequential or parallel composition. More details can be found in [20,29].

All the constructions stated in this paper are such that the availability condition is trivially satisfied, it is therefore omitted from now onwards. That is, the notation $R \overset{(π, σ, ε)}{⟾} S$ will be used for $(R, R_{⊥}) \overset{(π, σ, (0, ε))}{⟾} (S, S_{⊥})$ , where $R_{⊥}$ (respectively, $S_{⊥}$ ) is implicitly understood from R (respectively, S).
2.5. Symmetric cryptographic schemes

Message authentication. A message authentication code (MAC) scheme with message space $M \subseteq {0, 1}^{*}$ , key space $K : = {0, 1}^{n}$ , and tag space $U \subseteq {0, 1}^{*}$ is defined as a pair $(tag, vrf)$ , where $tag$ is a (possibly probabilistic) function taking as input a key $k \in K$ and a message $m \in M$ to produce a tag $u \leftarrow tag (k, m)$ , and $vrf$ is a deterministic function taking as input a key $k \in K$ , a message $m \in M$ and a tag $u \in U$ to output a bit $b : = vrf (k, m, u)$ asserting the validity of the input tag u. A MAC scheme is correct if $vrf (k, m, tag (k, m)) = 1$ , for all keys $k \in K$ and all messages $m \in M$ .

A MAC scheme $MAC : = (tag, vrf)$ is considered weakly unforgeable under chosen-message attack (WUF-CMA) if it is computationally infeasible, even when given access to an oracle producing valid tags for chosen messages, to generate a valid tag for a fresh message that was not queried before to the oracle. The associated security game, denoted $G^{CMA} (MAC)$ is detailed in Alg. 1.

Algorithm 1:

WUF-CMA game $G^{CMA} (MAC)$

Algorithm 2:

IND-CPA system $G_{b}^{CPA} (SE)$

Symmetric encryption. A symmetric encryption scheme with message space $M \subseteq {0, 1}^{*}$ , key space $K : = {0, 1}^{n}$ , and ciphertext space $C \subseteq {0, 1}^{*}$ is defined as a pair $(enc, dec)$ , where $enc$ is a (possibly probabilistic) function taking as input a key $k \in K$ and a message $m \in M$ to produce a ciphertext $c \leftarrow enc (k, m)$ , and $dec$ is a deterministic function taking as input a key $k \in K$ and a ciphertext $c \in C$ to output a plaintext $m^{'} : = dec (k, c)$ . The output of $dec$ can also be the error symbol ◆ to indicate an invalid ciphertext. An encryption scheme is correct if $dec (k, enc (k, m)) = m$ , for all keys $k \in K$ and all messages $m \in M$ .

The security of an encryption scheme can be defined using the “real or random” version of indistinguishability under chosen-plaintext attack (IND-CPA), which matches more closely constructive security definitions involving the comparison of a “real” system with an “ideal” one. Relations to other notions of IND-CPA follow from the work of Bellare et al. [3]. An encryption scheme $SE : = (enc, dec)$ is said to be IND-CPA-secure if no efficient distinguisher can tell apart the system $G_{0}^{CPA} (SE)$ , which encrypts input messages, from the system $G_{1}^{CPA} (SE)$ , which encrypts random messages of the same length as the input messages. The system $G_{b}^{CPA} (SE)$ is described in Alg. 2, where $M_{ℓ}$ stands for messages of length ℓ in $M$ .

3. Transformable systems

This section presents a new approach to modeling systems that can be gradually transformed, in a way that clearly separates the effects of the transformation from how it can be provoked. This separation is formalized by splitting into core systems that describe the behavior and triggers that model the condition provoking a transformation. The methodology is then applied to describe concrete resources, keys and secure channels, that can be downgraded to an “insecure” mode.

3.1. Core systems and triggers

As a warm-up example, consider a key obtained by hashing a secret password shared between two users Alice and Bob. Idealizing the hash function as a random oracle, the resulting key is completely random from the perspective of any third party Eve unless she also queried the random oracle on the same input; in other words, unless she correctly guessed the password. Hence, if one models the key obtained by this process as a resource, one can consider two separate parts of it. The first part specifies the behavior of the resource before and after the transformation (a “strong” version gives the key only to Alice and Bob, a “weak” version also gives it to Eve); the second part triggers one of these two versions based on Eve’s actions (providing a password-guessing game for her, triggering the weaker version as soon as she wins).

In general, a transformable system is therefore the combination of two random systems: a core and a trigger system. The core system specifies how it behaves as an internal switch value changes, while the trigger system specifies how this switch value can be changed. More formally, a core system S is simply an $(X \cup S, Y)$ -random system, where the set of inputs is partitioned into two sets $X$ and $S$ with $X \cap S = \emptyset$ . The set $X$ is the set of “normal” inputs, while $S$ is the set of possible switch values, such as ${0, 1}$ in the example above. A trigger system T is a $(T, S)$ -random system which outputs a switch value. Elements of $T$ are called trigger values and correspond to password guesses in the example above.

Definition 3.
Let $X, Y, S$ and $T$ be four discrete sets such that $X \cap S = \emptyset$ and $X \cap T = \emptyset$ . An $(X \cup S, Y)$ -random system S and a $(T, S)$ -random system T form an $(X \cup T, Y)$ -random system, denoted $S_{T}$ , defined as follows. On input $x \in X$ , the system $S_{T}$ outputs $y \in Y$ , where y is the output of the system S when queried on the input x. On input $t \in T$ , the system $S_{T}$ outputs $y^{'} \in Y$ , where $y^{'}$ is the output of S when queried on the output $s \in S$ of the system T which was queried on the original input t (see Fig. 1). The random system $S_{T}$ will be referred to as a transformable system, the random system S as a core system, and the random system T as a trigger system.

Fig. 1.
A transformable system $S_{T}$ formed by combining a core system S with a trigger system T. “Normal” inputs $x \in X$ are processed directly by S, while trigger values $t \in T$ go instead first through the system T whose output $s \in S$ is then used as an input to the system S.

Note that a transformable system is just a particular type of a random system, hence any security definition applying to random systems (e.g. the construction notion of Definition 2) also applies to transformable systems.

Fixed switches. Given an $(X \cup S, Y)$ -core system S, it will be sometimes convenient to argue about the behavior of S for a particular fixed switch value $s \in S$ . This is achieved through $S_{s}$ , the $(X, Y)$ -random system obtained by initializing S as follows: the switch value s is initially input to S and its resulting output is discarded. In other words, $S_{s}$ corresponds to the system S where the value of its switch is fixed from the beginning to s and cannot be changed. In particular, the input space of $S_{s}$ is only $X$ and not $X \cup S$ . Given a random variable S over $S$ , the term $S_{S}$ denotes the system selected at random in ${S_{s} ∣ s \in S}$ according to S.
3.2. Downgradable keys and downgradable secure channels

The core systems considered in this paper are actually resources, i.e., random systems with 3 interfaces $A, B$ and $E$ for Alice, Bob, and Eve, respectively, where the switch values are controlled via the interface $E$ . Formally, this interface is modeled as being split into two sub-interfaces: $E_{N}$ (for “normal” inputs/outputs) and $E_{S}$ (for switch values). Resources obtained by fixing the switch of such core resources to a particular value will no longer have this interface $E_{S}$ . Typically, Eve will not have a direct access to the interface $E_{S}$ of the core resource, instead she will only be allowed to access a trigger system T, which itself produces the switch values. Neither Alice nor Bob have access to T. Such a core resource combined with a trigger system will be called a downgradable resource.

Downgradable key resources and downgradable secure channels are examples of such resources that will be used throughout the paper. These resources are parameterized (among other) by a fixed number r of sessions. Intuitively, these resources provide a graceful deterioration of security by associating each session with a password and guaranteeing that a session remains secure as long as its password is not guessed, irrespectively of the state of other sessions. The corresponding core resources are described first, followed by the trigger systems.

Example 4 (Key).

The core resource ${KEY}^{r}$ for r sessions takes as switch at interface $E_{S}$ an r-bit string $(s_{1}, \dots, s_{r})$ which specifies for each session whether it is “broken” ( $s_{j} = 1$ ) or not ( $s_{j} = 0$ ). Alice and Bob can retrieve a uniform and independent key for a given session, while Eve can only retrieve it if the session is marked as “broken”. The resource ${KEY}^{r}$ is specified in Alg. 3. Each of the r sessions corresponds to a single use of a password. The re-use of passwords is modeled by password distributions that output multiple copies of the same password. (To match the formal definition of a random system, which provides an output for each received input, the core resources ${KEY}^{r}$ and ${SEC}^{r}$ should output a dummy message at the $E_{N}$ -interface every time a switch value is input at the $E_{S}$ -interface. This technicality is omitted here and below for the sake of clarity.)

Example 5 (Secure channel).

The core resource ${SEC}^{r}$ for r sessions also takes as switch value at interface $E_{S}$ an r-bit string which specifies for each session whether or not confidentiality is “broken”. The resource ${SEC}^{r}$ allows Alice to send one message per session to Bob. Eve learns nothing about the transmitted message but its length, unless this session was marked as “broken”, in which case the message is leaked to her. The channel ${SEC}^{r}$ does not allow Eve to inject any message, regardless of the value of the switch, and is formalized in Alg. 4.

Example 6 (Local and global password-guessing triggers).

Eve will not be allowed to influence the switch values of ${KEY}^{r}$ or ${SEC}^{r}$ directly, instead she will have to interact with a trigger system which captures the guessing of per-session passwords. Two different such trigger systems will be important in this work; in both of them the number of guesses allowed to Eve is restricted. These two systems differ in whether the restriction on the number of guesses is local to each session or global over all r sessions. They are referred to as local and global (password-guessing) triggers and denoted by $LT$ and $GT$ , respectively.

Formally, both triggers are parameterized by a password distribution $P$ over $W^{r}$ (where $W \subseteq {0, 1}^{*}$ is a set of passwords) and the number of password guesses allowed, either locally for each of the sessions (a tuple $\vec{q} : = (q_{1}, \dots, q_{r})$ ) or globally (a parameter q). Both $LT (P, \vec{q})$ and $GT (P, q)$ initially sample r passwords $(w_{1}, \dots, w_{r})$ according to $P$ . When a password guess $(j, w)$ for the jth session is received, both triggers change the state of this session to “broken” if the password guess is correct and their respective constraint on the number of password-guessing queries is satisfied. Both triggers $LT (P, \vec{q})$ and $GT (P, q)$ are only accessible by Eve and are detailed in Algs. 5 and 6.

Algorithm 3:

Core resource ${KEY}^{r}$

Algorithm 4:

Core resource ${SEC}^{r}$

Algorithm 5:

Local trigger $LT (P, \vec{q})$

Algorithm 6:

Global trigger $GT (P, q)$

Combining the core systems and triggers given above via Definition 3 leads to four downgradable resources: two with local restrictions, ${KEY}_{LT (P, \vec{q})}^{r}$ and ${SEC}_{LT (P, \vec{q})}^{r}$ , where the number of password-guessing queries is restricted per session; and two with a global restriction, ${KEY}_{GT (P, q)}^{r}$ and ${SEC}_{GT (P, q)}^{r}$ , where only the total number of password-guessing queries is limited. To simplify the notation, the parameters $P$ , q, $\vec{q}$ will often be omitted when clear from the context. The results presented in the next sections hold for any distribution $P$ of r passwords, including correlated distributions, unless explicitly stated otherwise.

4. Password-based key derivation

The simple protocol for deriving a key from a password via hashing as considered in Section 3 can be proven to construct, from a pre-distributed password and a random-oracle in each session, a downgradable key resource. Multiple independent random oracles can be constructed from a single one via salting (i.e., domain separation), a point that will be discussed in Section 6.4.

More formally, the shared passwords are modeled as an explicit resource denoted $PW$ . It is parameterized by a joint distribution $P$ of r passwords. The resource $PW (P)$ first samples from the distribution $P$ to obtain r passwords $(w_{1}, \dots, w_{r})$ and then outputs $(j, w_{j})$ at interface $i \in {A, B}$ whenever it receives as input $(j, getpwd)$ at the same interface i. Note that Eve does not learn anything about the sampled passwords except for the a priori known distribution $P$ .

Each hash function is modeled as a random oracle available to all parties, denoted by $RO$ . Notably, the restriction on Eve’s computational power is modeled by a restriction on the number of invocations of the random oracles that she is allowed to do. (For a rationale behind this choice and how it allows to model complexity amplification via iteration, see [13].) This is useful for modeling either a tuple of random oracles with local restrictions denoted $[{RO}_{q_{1}}, \dots, {RO}_{q_{r}}]$ , where each random oracle has its own upper bound $q_{j}$ on the number of adversarial queries it allows; or a tuple of random oracles with one global restriction denoted ${[RO, \dots, RO]}_{q}$ , where at most q adversarial queries are allowed in total.

The key-derivation protocol $KD : = (kd, kd)$ consists of both parties applying a converter $kd$ . Upon a key request $(j, getkey)$ for the jth session, $kd$ queries $PW (P)$ to retrieve the shared password $w_{j}$ for this session, then queries the jth random oracle on $w_{j}$ and returns its output.

The following simple lemma shows that the protocol $KD : = (kd, kd)$ , where each party simply applies the converter $kd$ , allows users to obtain downgradable keys in the sense of Section 3.2.

Lemma 7.
For the key derivation protocol $KD : = (kd, kd)$ described above, there exist simulators $σ_{kd, \vec{q}}$ and $σ_{kd, q}$ such that for all distributions $P$ of r passwords, for all integers $\vec{q} : = (q_{1}, \dots, q_{r})$ and q, it holds that $\begin{array}{l} [[{RO}_{q_{1}}, \dots, {RO}_{q_{r}}], PW (P)] \overset{(KD, σ_{kd, \vec{q}}, 0)}{⟾} {KEY}_{LT (P, \vec{q})}^{r} and \\ [{[RO, \dots, RO]}_{q}, PW (P)] \overset{(KD, σ_{kd, q}, 0)}{⟾} {KEY}_{GT (P, q)}^{r} . \end{array}$
Proof.
The simulators $σ_{kd, \vec{q}}$ and $σ_{kd, q}$ emulate r random oracles mostly by lazy sampling. More precisely, upon an adversarial query x made to the jth random oracle, the simulators forward x as a password guess for the jth session to the trigger $LT (P, \vec{q})$ or $GT (P, q)$ at their ${in}_{S}$ interface and then try to retrieve the key associated with that session by querying their ${in}_{N}$ -interface. If the password guess was correct, then the simulators output the retrieved key as a simulated output of the random oracle, and otherwise they just sample a uniform n-bit string. The simulators $σ_{kd, \vec{q}}$ and $σ_{kd, q}$ are described in Alg. 7.

The simulation is perfect in both settings, independently of whether the random oracles are locally or globally restricted. □

Algorithm 7:
Simulators $σ_{kd, \vec{q}}$ and $σ_{kd, q}$ , respectively

This lemma is very similar to [6, Theorem 3.3], which additionally provides the passwords in clear to the distinguisher.
5. Password-based message authentication

Password-derived keys can be used for message authentication using MACs. This section shows that such a construction meets the intuitive expectation that in a multi-user setting, as long as a password for a particular session is not guessed, the security (in this case: authenticity) in that session is maintained at the same level as if a perfectly random key was used. The real and the ideal experiment involved in the construction statement are depicted in Fig. 2.

Fig. 2.

Left: The assumed resource, a downgradable key ${KEY}_{T}^{r}$ and an insecure channel ${INSEC}^{r}$ , with protocol converters $tag$ and $vrf$ attached to interfaces $A$ and $B$ , denoted ${tag}^{A} {vrf}^{B} [{KEY}_{T}^{r}, {INSEC}^{r}]$ . Right: The constructed downgradable unordered authenticated channel ${UAUT}_{T}^{r}$ with simulator $σ_{MAC}$ attached to interface $E$ , denoted $σ_{MAC}^{E} {UAUT}_{T}^{r}$ . Simulator $σ_{MAC}$ must emulate Eve’s interface in the left picture, i.e., key retrieval queries at $E_{1, N}$ , trigger queries at $E_{1, S}$ and the insecure channel at $E_{2}$ .

Assumed resources. The construction statement shown below assumes the availability of a password-derived key and an insecure communication channel for each of the r considered sessions. Password-derived keys are modeled by the downgradable resource ${KEY}_{T}^{r}$ which can be constructed e.g. via one of the statements in Lemma 7 (here T stands for either $LT$ or $GT$ ). The insecure channels are formalized as the resource ${INSEC}^{r}$ which forwards any message sent by Alice to Eve, while any message injected by Eve is forwarded to Bob.

MAC schemes as protocols. Recall the definition of a MAC scheme stated in Section 2.5. Given a MAC scheme $(tag, vrf)$ , the protocol for Alice and Bob works in the natural way (their converters are denoted by $tag$ and $vrf$ , respectively). When $tag$ receives as input a message m for the jth session consisting of a pair $(j, m)$ , it retrieves the key $k_{j}$ associated to this session from the downgradable key resource ${KEY}_{T}^{r}$ , computes the tag $u : = tag (k_{j}, m)$ and outputs to the insecure channel ${INSEC}^{r}$ the pair $(j, m ∥ u)$ . On the other end of the channel, whenever $vrf$ receives a message and a tag for some session, consisting of a pair $(j^{'}, m^{'} ∥ u^{'})$ , it first retrieves the key $k_{j^{'}}$ associated to this session from ${KEY}_{T}^{r}$ , computes $vrf (k_{j^{'}}, m^{'}, u^{'})$ and outputs $(j^{'}, m^{'})$ only if the verification succeeds.3

Note that in practice the verification protocol would typically output an error symbol in case the verification did not succeed instead of not outputting anything. Our explanations in Section 5 would also hold in that scenario if the systems used are modified appropriately to output such an error symbol whenever necessary. We therefore omit this technicality.

Constructed resource. The channel that Alice and Bob obtain by using the protocol $(tag, vrf)$ guarantees that any message that Bob receives for a particular session must have been sent before by Alice, unless this session was “broken.” This (core) unordered authenticated channel, denoted ${UAUT}^{r}$ takes an r-bit string $(s_{1}, \dots, s_{r})$ as a switch value, specifying for each session j whether it is broken ( $s_{j} = 1$ ), in which case Eve can send any message to Bob for this particular session, or not ( $s_{j} = 0$ ), in which case the messages that Eve can send to Bob for session j are limited to those that Alice already sent. The channel ${UAUT}^{r}$ does not offer any secrecy, every message input by Alice is directly forwarded to Eve independently of the current switch value, while the switch value $s_{j}$ of a particular session can also be retrieved by Eve. Note that the unordered authenticated channel ${UAUT}^{r}$ , similarly to a MAC scheme, only aims to prevent Eve from being able to inject a fresh message, it does not a priori prevent the injection of a legitimate message multiple times, the reordering of legitimate messages, or the loss of some messages.

The next theorem proves that if the MAC scheme employed is WUF-CMA secure, then the protocol $MAC$ constructs an unordered authenticated channel ${UAUT}_{T}^{r}$ , where ${UAUT}^{r}$ is described in Alg. 8, from a downgradable key resource ${KEY}_{T}^{r}$ and an insecure channel ${INSEC}^{r}$ , for any trigger system $T \in {LT (P, \vec{q}), GT (P, q)}$ . The real and the ideal experiment involved in the constructions statement are represented in Fig. 2. The arguments used in the proof of Theorem 8 could easily be extended to the case of any trigger T with output space ${0, 1}^{r}$ and bit-wise non-decreasing output.

Algorithm 8:

Channel ${UAUT}^{r}$

Algorithm 9:

Simulator $σ_{MAC}$

Algorithm 10:

Reduction $C_{T, j^{*}}^{CMA}$

Theorem 8.

Let $MAC : = (tag, vrf)$ be a correct MAC scheme and consider the associated protocol $MAC : = (tag, vrf)$ . Then, there exists a simulator $σ_{MAC}$ described in Alg. 9 such that for every distribution $P$ of r passwords, every tuple of r integers $\vec{q} : = (q_{1}, \dots, q_{r})$ and any integer q, and any trigger $T \in {LT (P, \vec{q}), GT (P, q)}$ , $\begin{matrix} [{KEY}_{T}^{r}, {INSEC}^{r}] \overset{(MAC, σ_{MAC}, ε_{T})}{⟾} {UAUT}_{T}^{r}, \end{matrix}$ where $ε_{T} (D) : = r \cdot Γ^{D C_{T}^{CMA}} (G^{CMA} (MAC))$ , for every distinguisher D, where the reduction system $C_{T}^{CMA}$ depends on the trigger T and is described below in the proof.

Proof.

The simulator $σ_{MAC}$ initially selects for each session j a key $k_{j}$ uniformly at random and uses it to either compute tags, whenever a message is received at its $in$ -interface, or to verify the tag of a message, whenever an injection query $(j, m^{'} ∥ u^{'})$ is input at its ${out}_{2}$ -interface. The simulator forwards any password guessing query to the trigger of the resource and outputs the selected key $k_{j}$ only if the password associated with this session was broken. The simulator $σ_{MAC}$ is described in more details in Alg. 9.

In order to have shorter notations within the proof, the real system ${tag}^{A} {vrf}^{B} [{KEY}_{T}^{r}, {INSEC}^{r}]$ will be denoted by $R_{T}$ and the ideal system $σ_{MAC}^{E} {UAUT}_{T}^{r}$ will be denoted by $S_{T}$ , where $T \in {LT (P, \vec{q}), GT (P, q)}$ . Observe that the only difference between the systems $R_{T}$ and $S_{T}$ is that if a fresh message $m^{'}$ is injected by Eve together with a successfully forged tag, such a message $m^{'}$ is always output at Bob’s interface $B$ in the system $R_{T}$ , whereas in $S_{T}$ such a message $m^{'}$ is only output if the password associated with that session was previously guessed. A monotone binary output must be added to the systems $R_{T}$ and $S_{T}$ , to obtain the corresponding games ${\hat{R}}_{T}$ and ${\hat{S}}_{T}$ , defined as follows: the MBO $A_{1}, A_{2}, \dots$ becomes 1 as soon as $(j, m^{'} ∥ u^{'})$ is input to the $E_{2}$ -interface such that the message $(j, m^{'})$ was never input to the $A$ -interface before, the tag is valid (i.e., $vrf (k_{j}, m^{'}, u^{'}) = 1$ ), and the jth password was not guessed ( $s_{j} = 0$ ). Then, the previous observation implies that ${\hat{R}}_{T} \overset{g}{\equiv} {\hat{S}}_{T}$ and together with Lemma 1 it holds that $\begin{matrix} Δ^{D} (R_{T}, S_{T}) ⩽ Γ^{D} ({\hat{R}}_{T}), \end{matrix}$ for all distinguishers D.

The task of winning the game ${\hat{R}}_{T}$ can now be reduced to the task of winning the WUF-CMA security game $G^{CMA} (MAC)$ described in Alg. 1. To do so, consider a sequence of reduction systems $C_{T, 1}^{CMA}, \dots, C_{T, r}^{CMA}$ , where each reduction $C_{T, j^{*}}^{CMA}$ has 5 outside sub-interfaces (labeled $A, B, E_{1, N}, E_{1, S}$ and $E_{2}$ ) and connects at its inside interface to the WUF-CMA game $G^{CMA} (MAC)$ , for all $j^{*} \in {1, \dots, r}$ . The basic idea of the reduction $C_{T, j^{*}}^{CMA}$ is to forward any tag or verification query for session $j^{*}$ to the system connected at its inside interface, while other sessions are handled locally. The reduction $C_{T, j^{*}}^{CMA}$ also emulates internally the trigger T, which in the case of $LT (P, \vec{q})$ or $GT (P, q)$ corresponds to first sampling r passwords according to $P$ and then to appropriately count the number of password-guessing queries, in order to keep track of which session should be considered “broken”. Key retrieval queries are handled as usual, excepted for session $j^{*}$ for which the error symbol ◆ is always returned. A more formal description of the reduction system $C_{T, j^{*}}^{CMA}$ is given in Alg. 10.

Consider a distinguisher D interacting with the game ${\hat{R}}_{T}$ in order to provoke its MBO. Let $F_{j}$ be the event that in this random experiment the distinguisher D won the game ${\hat{R}}_{T}$ by finding a forgery for a fixed session j, i.e., $(j, m^{'} ∥ u^{'})$ was input at the $E_{2}$ -interface such that $(j, m^{'})$ was never input to the $A$ -interface before, the tag is valid (i.e., $vrf (k_{j}, m^{'}, u^{'}) = 1$ ), and the jth password was not guessed ( $s_{j} = 0$ ), for some message $m^{'} \in M$ and tag $u^{'} \in U$ . The probability that this event $F_{j}$ happens in this random experiment is denoted $P^{D {\hat{R}}_{T}} (F_{j})$ . Note that winning the game ${\hat{R}}_{T}$ involves provoking one of the events $F_{j}$ , for some session $j \in {1, \dots, r}$ , and thus $\begin{matrix} Γ^{D} ({\hat{R}}_{T}) ⩽ \sum_{j \in {1, \dots, r}} P^{D {\hat{R}}_{T}} (F_{j}) . \end{matrix}$ Now fix the randomness used in the random experiment $D {\hat{R}}_{T}$ (consisting of the randomness of the distinguisher D, the r keys used for tagging, the r passwords and the randomness of the algorithm $tag$ ). Conditioned on this randomness, any transcript of queries which provokes the event $F_{j}$ in $D {\hat{R}}_{T}$ also wins the game $C_{T, j}^{CMA} G^{CMA} (MAC)$ . Moreover, in such a transcript the password associated with the jth session is not guessed ( $s_{j} = 0$ ) and thus such a transcript happens with the same probability in the random experiment $D C_{T, j}^{CMA} G^{CMA} (MAC)$ . Hence, $\begin{matrix} P^{D {\hat{R}}_{T}} (F_{j}) ⩽ Γ^{D C_{T, j}^{CMA}} (G^{CMA} (MAC)), \end{matrix}$ for all sessions $j \in {1, \dots, r}$ . The previous equations implies that the reduction $C_{T}^{CMA}$ , which consists in selecting a session $j^{*}$ uniformly at random in ${1, \dots, r}$ and then implementing the reduction $C_{T, j^{*}}^{CMA}$ is such that $\begin{matrix} Γ^{D} ({\hat{R}}_{T}) ⩽ r \cdot Γ^{D C_{T}^{CMA}} (G^{CMA} (MAC)), \end{matrix}$ for all distinguishers D. □

6. Password-based encryption

This section investigates the use of password-derived keys for symmetric encryption. In a multi-session setting, one may expect that as long as a password for a particular session is not guessed, the confidentiality in that session is maintained. This would, roughly speaking, correspond to a construction of (downgradable) secure channels from authenticated channels and password-derived keys. This desired construction is described in greater detail below, referring to Fig. 3 for the depictions of the real and the ideal experiment.

Fig. 3.

Left: The assumed resource, a downgradable key ${KEY}_{T}^{r}$ and an authenticated channel ${AUT}^{r}$ , with protocol converters $enc$ and $dec$ attached to interfaces $A$ and $B$ , denoted ${enc}^{A} {dec}^{B} [{KEY}_{T}^{r}, {AUT}^{r}]$ . Right: The desired downgradable secure channel ${SEC}_{T}^{r}$ with simulator σ attached to interface $E$ , denoted $σ^{E} {SEC}_{T}^{r}$ . The simulator σ must emulate Eve’s interface in the left picture, i.e., key retrieval queries at $E_{1, N}$ , trigger queries at $E_{1, S}$ and the authenticated channel at $E_{2}$ .

Assumed resources. These construction statements assume the availability of a password-derived key and an authenticated communication channel for each of the r sessions. Password-derived keys are modeled by the downgradable resource ${KEY}_{T}^{r}$ , where T typically stands for either $LT (P, \vec{q})$ or $GT (P, q)$ . Note that if the assumed authenticated channel were ${UAUT}_{T}^{r}$ , which can for example be obtained by using MAC schemes as described in Section 5, then the overall channel resulting from doing encryption (the exact protocol is described in greater detail in the paragraph below) on top of it would necessarily have to encompass a mechanism to decide when a message is delivered to Bob based on Eve’s actions (since Eve can drop or try to inject messages in the channel ${UAUT}_{T}^{r}$ ).

To avoid such a technicality, the construction statements below will instead assume an authenticated communication channel without any weakness, denoted ${AUT}^{r}$ . The channel ${AUT}^{r}$ takes as input a pair $(j, c)$ at Alice’s interface $A$ , corresponding to a ciphertext c to be transmitted for the jth session, and outputs $(j, c)$ at both Eve’s interface $E$ and Bob’s interface $B$ . Eve can neither replay messages nor drop those coming from Alice. For convenience, it is also assumed that at most one message is transmitted per session, but the results can easily be extended to the case of multiple messages per session. The channel ${AUT}^{r}$ is described in Alg. 11.

Algorithm 11:

Channel ${AUT}^{r}$

Encryption schemes as protocols. Recall the definition of an encryption scheme stated in Section 2.5. Given an encryption scheme $(enc, dec)$ , the protocol for Alice and Bob again works in the natural way (their converters are denoted $enc$ and $dec$ , respectively). Both $enc$ and $dec$ expect two resources at their respective inside interface $in$ : a downgradable key resource ${KEY}_{T}^{r}$ at their interface ${in}_{1}$ and an authenticated communication channel ${AUT}^{r}$ at their interface ${in}_{2}$ . The converter $enc$ takes as input a pair $(j, m)$ at its outside interface $out$ , corresponding to a message m to be transmitted for the jth session. It retrieves the shared secret key $k_{j}$ for this session by inputting $(j, getkey)$ at its ${in}_{1}$ -interface, computes the ciphertext $c \leftarrow enc (k_{j}, m)$ and finally outputs $(j, c)$ to the channel at its ${in}_{2}$ -interface. Similarly, when a pair $(j, c)$ is input to the ${in}_{2}$ -interface of the converter $dec$ , corresponding to an encrypted message sent for the jth session, the converter $dec$ retrieves the shared secret key $k_{j}$ for this session (by inputting $(j, getkey)$ at its ${in}_{1}$ -interface) and outputs $(j, dec (k_{j}, c))$ at its $out$ -interface. Throughout this section, the underlying encryption scheme $(enc, dec)$ will be assumed to be correct.

Constructed resource. The channel that Alice and Bob wish to obtain by using the protocol $SE : = (enc, dec)$ is the downgradable resource ${SEC}_{T}^{r}$ described in Section 3.2, which guarantees that any message sent by Alice for a particular session is transmitted confidentially to Bob, unless this session was “broken”.

The goal of password-based encryption can then be loosely phrased as achieving the following construction $\begin{matrix} [{KEY}_{T}^{r}, {AUT}^{r}] \overset{(SE, σ, ε)}{⟾} {SEC}_{T}^{r}, \end{matrix}$ for some simulator σ and “reasonable” distinguishing advantage ε.

6.1. PBE for a single session

The first focus is on PBE with a single session. This will serve as an introduction to the study of the multi-session setting, given in Sections 6.2 and 6.3.

In the particular case of a single session, the local password-guessing trigger $LT (P, q)$ and the global one $GT (P, q)$ are actually identical for any distribution $P$ of a single password and any number q of password-guessing queries. To be consistent with what lies ahead in Section 6.3, the notation $LT (P, q)$ will be used in this section. In the considered special case, the exponent r indicating the number of sessions and the index j of the session associated with any input or output can also be omitted, thus simplifying the notation.

The aim of this section is to construct the downgradable secure channel ${SEC}_{LT (P, q)}^{}$ from a downgradable key ${KEY}_{LT (P, q)}^{}$ and an authenticated channel ${AUT}^{}$ using the protocol $SE = (enc, dec)$ . According to Definition 2, this requires finding a simulator σ such that the systems ${enc}^{A} {dec}^{B} [{KEY}_{LT (P, q)}^{}, {AUT}^{}]$ and $σ^{E} {SEC}_{LT (P, q)}^{}$ represented in Fig. 3 with $T = LT (P, q)$ , are indistinguishable.

The commitment problem. In the real world, whenever a message m is input at Alice’s interface $A$ , the corresponding ciphertext is output at Eve’s interface $E_{2}$ . On the other hand, in the ideal world only the length $| m |$ of the transmitted message m is output by the channel ${SEC}_{LT (P, q)}^{}$ to the simulator σ. The simulator must therefore emulate that a ciphertext was sent by only knowing the length $| m |$ of the transmitted message and not the message m itself.

A naïve simulation strategy could start as follows. The simulator σ initially selects a key k uniformly at random and emulates the transmission of a ciphertext by encrypting a fresh random message v of the correct length under key k, while password-guessing queries are simply forwarded to the trigger $LT (P, q)$ of the downgradable channel ${SEC}_{LT (P, q)}^{}$ .

However, this approach does not work. To see this, consider what happens when the password is guessed and the session is broken (which, depending on $P$ , may happen with a large probability). In the real world, the distinguisher can retrieve the key k used for encryption and check that the previously seen ciphertext c is indeed an encryption of the transmitted message m. In contrast, in the ideal world the simulator σ can retrieve the transmitted message m, but note that it cannot output the key k that it chose at the beginning to simulate encryption since $dec (k, c) = v$ is a random message which (with overwhelming probability) is different from the actual transmitted message m. The simulator σ must therefore “decommit” by finding a key $k^{'}$ such that the decryption of the simulated ciphertext c under that key $k^{'}$ yields the transmitted plaintext m, i.e., $dec (k^{'}, c) = m$ . However, it is not hard to see that unless the key space of the encryption scheme contains as many keys as there are messages (which is only true for impractical schemes such as the one-time pad), it is highly unlikely that such a key even exists and the simulation therefore fails.

Brute-force to the rescue. The previous paragraph only shows that one particular simulation strategy fails. The source of the commitment problem is that the simulator σ only breaks the session after having output the simulated ciphertext. The key insight is that this does not have to be the case.

To prevent the simulation breakdown, one can instead consider a different simulator $σ_{LT}$ which, in contrast to σ, tries to break the session before having to output any ciphertext. So, instead of faithfully forwarding the q password-guessing queries, the simulator $σ_{LT}$ initially exhausts all of the allowed q queries to optimally brute-force the session by querying the q most likely passwords. If this initial brute-force step fails, $σ_{LT}$ simply encrypts a random message of the correct length and declares any password guess as incorrect so that the actual key used to simulate the encryption is never output. However, if the initial brute-force step succeeds, $σ_{LT}$ has access to the transmitted message and can therefore perfectly simulate the corresponding ciphertext, while password-guessing queries can be appropriately “scaled up” to match the guessing probability of the real world. In this case, the key used to simulate encryption can obviously be output since the ciphertext produced is an actual encryption of the transmitted message. Intuitively, this simulation strategy is successful because password-guessing queries made by $σ_{LT}$ are never output to a distinguisher.

In this setting with a single session, password-based encryption is therefore possible with respect to the simulation strategy $σ_{LT}$ sketched above.

Corollary 9 (Informal).

For every distribution $P$ of a single password and every integer q, there exists a simulator $σ_{LT}$ such that $\begin{matrix} [{KEY}_{LT (P, q)}^{}, {AUT}^{}] \overset{(SE, σ_{LT}, ε)}{⟾} {SEC}_{LT (P, q)}^{}, \end{matrix}$ where the distinguishing advantage ε can be reduced to the IND-CPA security of the underlying encryption scheme.

The generalization of the above statement for r sessions is discussed in Section 6.3. This corollary then follows by taking $r = 1$ in Theorem 15.

6.2. General impossibility of PBE

The positive result for a single session can in general not be lifted to multiple sessions. In fact, there is a distinguisher $D_{ℓ}$ that distinguishes the systems ${enc}^{A} {dec}^{B} [{KEY}_{T}^{r}, {AUT}^{r}]$ and $σ^{E} {SEC}_{T}^{r}$ depicted in Fig. 3, for any trigger system T with output space ${0, 1}^{r}$ and any simulator σ, with an advantage that will not be negligible in most settings. The lower bound depends on the properties of the trigger system T and while giving a clear impossibility result for some triggers, for others it becomes moot. In particular, while it gives a strong bound for the case of the global password-guessing trigger $GT (P, q)$ , the bound is inconclusive for the local trigger $LT (P, \vec{q})$ and independently distributed passwords, where in Section 6.3 it is shown that password-based encryption is actually possible.

The core of the impossibility result lies in exploiting the commitment problem explained in Section 6.1. The simulator $σ = σ_{LT}$ there avoids this commitment problem by trying to break the session associated with the plaintext before having to output the corresponding ciphertext. This works out if σ follows the optimal strategy for breaking this particular session, since an arbitrary distinguisher would not be able to do better. However, since σ does not a priori know which session will have to be “decommitted”, the simulator σ must be able to follow the optimal strategy for each session. This might be possible depending on the trigger system T (such as in the case of $LT (P, \vec{q})$ with independent passwords), but in general following the optimal strategy for a particular session may prevent σ from following the optimal strategy for another session. This is the case for the trigger $GT (P, q)$ where following the optimal strategy for a particular session consists of exhausting all the q allowed password-guessing queries on this session.

The high level idea of the distinguisher $D_{ℓ}$ is therefore to first force the simulator to be committed to a ciphertext in every session; and second, to pick a session $j^{*}$ uniformly at random and to follow the optimal strategy to break it. To avoid the commitment problem, the simulator must in contrast try to break the maximum number of sessions before simulating the ciphertexts since it does not know which session $j^{*}$ will be chosen by the distinguisher.

Some further notation is needed to quantify more precisely the distinguishing advantage achieved by $D_{ℓ}$ . Let T denote an arbitrary trigger system with output space ${0, 1}^{r}$ , and consider a distinguisher D interacting with the trigger T alone. Note in particular that such a distinguisher sees the output $(s_{1}, \dots, s_{r}) \in {0, 1}^{r}$ of T. The interaction of the distinguisher D with the trigger T defines a random experiment, and $G_{j}$ denotes the event that the jth session is “broken”, i.e., T output at least once an r-bit string $(s_{1}, \dots, s_{r})$ with $s_{j} = 1$ , for all $j \in {1, \dots, r}$ . The probability that this event $G_{j}$ happens in this random experiment is denoted $P^{D T} (G_{j})$ and it will be convenient to see it as a function of both j and D. To do so, let $D$ denote the set of distinguishers for T and consider the function $Γ^{T} : {1, \dots, r} \times D \to [0, 1]$ , where $Γ^{T} (j, D) : = P^{D T} (G_{j})$ , for all $j \in {1, \dots, r}$ and $D \in D$ .

In the following, denote by $Γ_{opt}^{T}$ the average of the maximum probability in breaking a particular session, while $Γ_{avg}^{T}$ denotes the maximum average probability of breaking all sessions, $\begin{matrix} (1) & \begin{array}{l} Γ_{opt}^{T} : = \frac{1}{r} \sum_{j \in {1, \dots, r}} sup_{D \in D} Γ^{T} (j, D), \\ Γ_{avg}^{T} : = \frac{1}{r} sup_{D \in D} \sum_{j \in {1, \dots, r}} Γ^{T} (j, D) . \end{array} \end{matrix}$

Note that ${sup}_{D \in D} Γ^{T} (j, D) ⩾ Γ^{T} (j, D^{*})$ , for every $j \in {1, \dots, r}$ and $D^{*} \in D$ , and thus $Γ_{opt}^{T} ⩾ Γ_{avg}^{T}$ . In other words, $Γ_{opt}^{T}$ measures the success of an optimal strategy for breaking a known randomly chosen session j, while $Γ_{avg}^{T}$ measures the success of an optimal strategy for breaking an unknown randomly chosen session. Knowing in advance which session will be “attacked” is a clear advantage that is measured by the difference $Γ_{opt}^{T} - Γ_{avg}^{T} ⩾ 0$ .

Algorithm 12:

Distinguisher $D_{ℓ, ε}$

Theorem 10.

Let $SE : = (enc, dec)$ be a correct encryption scheme with key space $K : = {0, 1}^{n}$ and message space $M \subseteq {0, 1}^{*}$ , and consider the associated protocol $SE : = (enc, dec)$ . Let T be a trigger system with output space ${0, 1}^{r}$ and let $M_{ℓ}$ denote a non-empty set of messages of fixed length ℓ in $M$ , for some integer ℓ. Then, for any $ε > 0$ there exists a distinguisher $D_{ℓ, ε}$ described in Alg. 12 such that for all simulators σ it holds that $\begin{matrix} (2) & Δ^{D_{ℓ, ε}} ({enc}^{A} {dec}^{B} [{KEY}_{T}^{r}, {AUT}^{r}], σ^{E} {SEC}_{T}^{r}) ⩾ δ^{T} - \frac{| K |}{| M_{ℓ} |} - ε, \end{matrix}$ where $δ^{T} : = Γ_{opt}^{T} - Γ_{avg}^{T} ⩾ 0$ , with $Γ_{opt}^{T}$ and $Γ_{avg}^{T}$ defined in ( 1 ).

Remark 11.

Some comments on the lower bound obtained in (2) are in order. If there are almost as many keys as messages, such as in the one-time pad, then the bound in (2) becomes trivial. (Note that if the encryption scheme is the one-time pad, then password-based encryption is obviously possible since there is no “commitment” problem: doing the xor of a given ciphertext and of a given message leads to the appropriate key.) However, most encryption schemes used in practice have significantly less keys than messages and in this case the dominant term in (2) is $δ^{T}$ , which quantifies for a trigger system T the advantage that can be obtained on average by knowing which session will be “attacked”.

For example, if $P$ is a distribution of r independent passwords, then $δ^{GT (P, q)}$ will typically be large. For such a distribution, the optimal guessing strategy for a particular session consists of querying the q most likely passwords for this session. Thus, following the optimal strategy for a particular session reduces the number of globally available password-guessing queries and prevents following the same guessing strategy for another session. An obvious exception is if the passwords are cryptographic keys, i.e., they are uniformly distributed over some large space, then the “passwords” are unguessable and $δ^{GT (P, q)}$ is negligible.

In contrast for the same distribution $P$ of r independent passwords, the quantity $δ^{LT (P, \vec{q})}$ will be null for the local password-guessing trigger $LT (P, \vec{q})$ , for any number of password-guessing queries $q_{1}, \dots, q_{r}$ . This is because the optimal strategy can be executed for each session, since for this trigger each session is truly independent.

Depending on the trigger system T, the distinguisher $D_{ℓ, ε}$ given in Alg. 12 may not necessarily be efficient, since it must be able to implement the optimal strategy for an arbitrary session of its choice. Nonetheless, it is worth mentioning that in the particular case where the trigger system is $GT (P, q)$ , computing the optimal guessing strategy for a particular session is “easy” if the passwords are independently distributed. One simply queries the q most likely passwords for this session. Clearly, this assumes that the distinguisher $D_{ℓ, ε}$ knows the password distribution $P$ , and is able to sort the passwords according to their respective probability to determine the q most likely for a particular session.

Proof of Theorem 10.

The main idea of the distinguisher $D_{ℓ, ε}$ is to exploit the advantage quantified by $δ^{T}$ in knowing in advance which session $j^{*} \in {1, \dots, r}$ is going to be “attacked”. In order to have shorter notations within the proof, let $R_{T}$ denote the system ${enc}^{A} {dec}^{B} [{KEY}_{T}^{r}, {AUT}^{r}]$ , while $S_{T}$ denotes $σ^{E} {SEC}_{T}^{r}$ , for some simulator σ.

In a first step, the distinguisher $D_{ℓ, ε}$ selects r messages of length ℓ uniformly at random, one for each session, and sends them at the $A$ -interface to observe the corresponding ciphertexts $c_{1}, \dots, c_{r}$ at the $E_{2}$ -interface, which are real encryptions when interacting with $R_{T}$ or simulated encryptions when interacting with $S_{T}$ instead. Distinguisher $D_{ℓ, ε}$ selects uniformly at random a particular session $j^{*} \in {1, \dots, r}$ . $D_{ℓ, ε}$ then tries to break it by “running” an ε-optimal strategy $D_{opt, ε} (j^{*})$ for that particular session, where $\begin{matrix} Γ^{T} (j, D_{opt, ε} (j)) > sup_{D \in D} Γ^{T} (j, D) - ε, \end{matrix}$ for all $j \in {1, \dots, r}$ . “Running” $D_{opt, ε} (j^{*})$ consists of the following three steps. First, the trigger value t output by $D_{opt, ε} (j^{*})$ is forwarded to the interface $E_{1, S}$ , which when interacting with $R_{T}$ corresponds to querying the trigger T on t. Second, distinguisher $D_{ℓ, ε}$ outputs 1 if this query t resulted in breaking the session $j^{*}$ and the key retrieved allows to decrypt the ciphertext $c_{j^{*}}$ to the original message $m_{j^{*}}$ . Otherwise, if the session $j^{*}$ is still not broken, distinguisher $D_{ℓ, ε}$ queries the interface $E_{1, N}$ to retrieve a switch value $(s_{1}, \dots, s_{r})$ , which when interacting with $R_{T}$ corresponds to the last switch value output by T, and feed it to $D_{opt, ε} (j^{*})$ to obtain the next trigger value. Overall, distinguisher $D_{ℓ, ε}$ outputs 1 if and only if it managed to break session $j^{*}$ and the decryption of the ciphertext with the retrieved key matches the original message. Distinguisher $D_{ℓ, ϵ}$ is given in more details in Alg. 12.

The next step is to lower-bound the distinguishing advantage $Δ^{D_{ℓ, ε}} (R_{T}, S_{T})$ . Note that when $D_{ℓ, ε}$ interacts with $R_{T}$ , the distinguisher breaks a given session $j^{*}$ with probability at least ${sup}_{D \in D} Γ^{T} (j^{*}, D) - ε$ . If session $j^{*}$ is broken, then $D_{ℓ, ε}$ always outputs 1 by correctness of the encryption scheme. Thus, $\begin{matrix} P^{D_{ℓ, ε} R_{T}} (1) ⩾ \frac{1}{r} \sum_{j^{*} \in {1, \dots, r}} sup_{D \in D} Γ^{T} (j^{*}, D) - ε = Γ_{opt}^{T} - ε . \end{matrix}$

In contrast, when distinguisher $D_{ℓ, ε}$ interacts with $S_{T}$ , the event that matters is whether the simulator σ managed to break the session $j^{*}$ before sending the ciphertext $c_{j^{*}}$ , and later distinguisher $D_{ℓ, ε}$ chooses the session $J^{*} = j^{*}$ . In the random experiment $D_{ℓ, ε} S_{T}$ , let $G_{j}^{'}$ be the event that the session j was broken at least once (the trigger T output at least once a switch value with $s_{j} = 1$ ) before simulator σ outputs the simulated ciphertext $c_{j}$ , for all $j \in {1, \dots, r}$ . We will denote the complementary event by $\overline{G_{j}^{'}}$ .

Note that if the simulator σ in S manages to break the chosen session $j^{*}$ before having sent the ciphertext $c_{j^{*}}$ , which corresponds to the event $G_{j^{*}}^{'} \land J^{*} = j^{*}$ , then σ has the possibility of retrieving the corresponding message $m_{j^{*}}$ and thus could potentially perfectly simulate this ciphertext, so that $P^{D_{ℓ, ε} S_{T}} (1 ∣ G_{j^{*}}^{'} \land J^{*} = j^{*}) = 1$ is possible. In contrast, when $\overline{G_{j^{*}}^{'}} \land J^{*} = j^{*}$ , the simulator σ is committed to the ciphertext $c_{j^{*}}$ without knowing anything about the message $m_{j^{*}}$ but its length ℓ. For distinguisher $D_{ℓ, ε}$ to output 1 in this case, the simulator must be able to provide a key $k^{'}$ such that $dec (k^{'}, c_{j^{*}}) = m_{j^{*}}$ . Since the decryption algorithm $dec$ is deterministic, it implies that for a fixed ciphertext $c_{j^{*}}$ the output of $dec (\cdot, c_{j^{*}})$ can take at most $| K |$ values. The message $m_{j^{*}}$ is uniformly distributed over $M_{ℓ}$ and thus $\begin{matrix} P^{D_{ℓ, ε} S_{T}} (1 ∣ \overline{G_{j^{*}}^{'}} \land J^{*} = j^{*}) ⩽ \frac{| K |}{| M_{ℓ} |} . \end{matrix}$

Note that if the simulator σ can provoke the event $G_{j}^{'}$ in the random experiment $D_{ℓ, ε} S_{T}$ , then σ can be used to win the event $G_{j}$ against the trigger T alone. Since σ does not know in advance which session is going to be selected by $D_{ℓ, ε}$ , its success is therefore at most the maximum of the average, i.e., $\begin{matrix} \sum_{j^{*} \in {1, \dots, r}} P^{D_{ℓ, ε} S_{T}} (G_{j^{*}}^{'} \land J^{*} = j^{*}) ⩽ Γ_{avg}^{T} . \end{matrix}$ Thus, $\begin{array}{l} P^{D_{ℓ, ε} S_{T}} (1) & = \sum_{j^{*} \in {1, \dots, r}} \sum_{E \in {G_{j^{*}}^{'}, \overline{G_{j^{*}}^{'}}}} P^{D_{ℓ, ε} S_{T}} (E \land J^{*} = j^{*}) \cdot P^{D_{ℓ, ε} S_{T}} (1 ∣ E \land J^{*} = j^{*}) \\ ⩽ \sum_{j^{*} \in {1, \dots, r}} P^{D_{ℓ, ε} S_{T}} (G_{j^{*}}^{'} \land J^{*} = j^{*}) + \frac{| K |}{| M_{ℓ} |} \\ ⩽ Γ_{avg}^{T} + \frac{| K |}{| M_{ℓ} |} . \end{array}$ Combining the previous equations gives the desired lower bound. □

6.3. PBE with local assumptions

As mentioned in Remark 11, the impossibility result does not apply to the particular case of the local password-guessing trigger $LT (P, \vec{q})$ if the passwords are independently distributed, allowing for the existence of password-based encryption under these assumptions. Intuitively, since each session has its own restriction on the number of password-guessing queries, the simulation strategy can optimally brute-force each session independently to avoid the commitment problem in the same way as in the case of a single session in Section 6.1.

It is therefore assumed in this section that the passwords are independently, but not necessarily identically, distributed. That is, there exist r password distributions $P_{1}, \dots, P_{r}$ such that the distribution $P$ of the r passwords can be written as $P (w_{1}, \dots, w_{r}) = P_{1} (w_{1}) \times \dots \times P_{r} (w_{r})$ , for all $w_{1}, \dots, w_{r} \in W$ . Such a distribution $P$ will be called a product distribution.

Note that passwords in $W$ can be sorted according to their likelihood of being chosen in the jth session as given by $P_{j}$ . Let $γ_{j, q} \in [0, 1]$ be the probability that the password selected in the jth session belongs to the q most likely passwords (according to $P_{j}$ ), for all $j \in {1, \dots, r}$ and any integer q.

The following technical lemma shows that when constructing the downgradable secure channel ${SEC}_{LT (P, \vec{q})}^{r}$ from the downgradable key ${KEY}_{LT (P, \vec{q})}^{r}$ where the switch value can be changed through the trigger system $LT (P, \vec{q})$ , it is sufficient to instead look at systems ${KEY}_{S^{*}}^{r}$ and ${SEC}_{S^{*}}^{r}$ where the switch value is randomly chosen and fixed at the beginning according to some random variable $S^{*}$ .

Algorithm 13:

Converter $σ_{KEY, \vec{q}}$

Lemma 12.

Let $P$ be a product distribution of r passwords as described above and consider a tuple of r integers $\vec{q} : = (q_{1}, \dots, q_{r})$ . For each session $j \in {1, \dots, r}$ , let $S_{j}^{*}$ be a binary random variable which is 1 with probability $γ_{j, q_{j}}$ , and let $S^{*} : = (S_{1}^{*}, \dots, S_{r}^{*})$ . Then, there exist converters $σ_{KEY, \vec{q}}$ and $σ_{SEC}$ , described in Algs. 13 and 14 , respectively, such that $\begin{matrix} {KEY}_{LT (P, \vec{q})}^{r} \equiv σ_{KEY, \vec{q}}^{E} {KEY}_{S^{*}}^{r} and {SEC}_{S^{*}}^{r} \equiv σ_{SEC}^{E} {SEC}_{LT (P, \vec{q})}^{r} . \end{matrix}$

Proof.

The core systems ${KEY}^{r}$ and ${SEC}^{r}$ introduced in Section 3.2 are such that a change in their switch value modifies the behavior of the system only at the adversarial $E_{N}$ interface and not at the others (interface $A$ or $B$ ).

In the case of the key system, the converter $σ_{KEY, \vec{q}}$ has to be indistinguishable from ${KEY}_{LT (P, \vec{q})}^{r}$ , where the value of the switch can be changed progressively, by having only access to ${KEY}_{S^{*}}^{r}$ , where the value of the switch is (randomly) fixed at the beginning. To do so, the converter $σ_{KEY, \vec{q}}$ uses the fact it can easily infer the value of $S^{*}$ by simply querying $(j, getkey)$ at the $E_{N}$ -interface of ${KEY}_{S^{*}}^{r}$ . If the answer contains the error symbol ◆, then $S_{j}^{*} = 0$ , and otherwise $S_{j}^{*} = 1$ , for all $j \in {1, \dots, r}$ . If $S_{j}^{*} = 0$ , then $σ_{KEY, \vec{q}}$ cannot retrieve the key associated to this session and therefore declares any password guess for that session as invalid. In contrast, if $S_{j}^{*} = 1$ , which happens with probability $γ_{j, q_{j}}$ , the converter $σ_{KEY, \vec{q}}$ must then “scale up” the password-guessing probabilities accordingly in order to match those of ${KEY}_{LT (P, \vec{q})}^{r}$ . For the first query of a password w in session j with $S_{j}^{*} = 1$ , scaling factor is exactly ${γ_{j, q_{j}}}^{- 1}$ and the guess is considered valid if a coin tossed with probability $P_{j} (w) \cdot {γ_{j, q_{j}}}^{- 1}$ is 1. For subsequent queries, the scaling also has to account for the previous unsuccessful guesses, which appears by tossing the coin with probability $P_{j} (w) \cdot {(γ_{j, q_{j}} - \sum_{\bar{w}} P_{j} (\bar{w}))}^{- 1}$ , where the sum is over the wrong passwords guessed before. Note that $γ_{j, q_{j}}$ is cumulative in $q_{j}$ , and the subtraction term accounts for the probabilities of the previous guesses. (Generally, if the same w is guessed repeatedly by the distinguisher, then $σ_{SEC}$ does not toss the coin again, but instead responds consistently.) Note that this is indeed a probability distribution since $γ_{j, q_{j}}$ represents the winning probability of the optimal guessing strategy for the jth session with $q_{j}$ queries and therefore $P_{j} (w) + \sum_{\bar{w}} P_{j} (\bar{w}) ⩽ γ_{j, q_{j}}$ . Overall, the probability of retrieving the key used in the jth session is therefore $P_{j} (w)$ and thus ${KEY}_{LT (P, \vec{q})}^{r} \equiv σ_{KEY, \vec{q}}^{E} {KEY}_{S^{*}}^{r}$ . A more formal description of $σ_{KEY, \vec{q}}$ is in Alg. 13.

Algorithm 14:

Converter $σ_{SEC}$

In contrast to $σ_{KEY, \vec{q}}$ , the task of $σ_{SEC}$ is to emulate ${SEC}_{S^{*}}^{r}$ , where the value of the switch is (randomly) fixed at the beginning, from ${SEC}_{LT (P, \vec{q})}^{r}$ , where its value can be changed progressively. To do so, $σ_{SEC}$ simply does the optimal password-guessing strategy, i.e., $σ_{SEC}$ queries the $q_{j}$ most likely passwords for the jth session, for all $j \in {1, \dots, r}$ , which implies ${SEC}_{S^{*}}^{r} \equiv σ_{SEC}^{E} {SEC}_{LT (P, \vec{q})}^{r}$ . A more detailed description of $σ_{SEC}$ is in Alg. 14. □

Remark 13.

The strategies described by the converters $σ_{KEY, \vec{q}}$ or $σ_{SEC}$ in Lemma 12 have demanding preconditions: They need to know the password distribution and, for each session, to also know an upper bound on the number of password-guessing queries as well as to be able to sort through the set of passwords in order to determine the most likely ones.

The next lemma shows that the protocol $(enc, dec)$ constructs a secure channel ${SEC}_{S}^{r}$ from a key resource ${KEY}_{S}^{r}$ and an authenticated channel ${AUT}^{r}$ if the encryption scheme used is IND-CPA secure, for every random switch value S.

Lemma 14.

Let $SE : = (enc, dec)$ be a correct encryption scheme and consider the associated protocol $SE : = (enc, dec)$ . Let S be a random variable arbitrarily distributed over ${0, 1}^{r}$ . Then, there exist a simulator $σ_{CPA}$ described in Alg. 15 and an (efficient) reduction system $C^{CPA}$ described in the proof such that $\begin{matrix} [{KEY}_{S}^{r}, {AUT}^{r}] \overset{(SE, σ_{CPA}, ε)}{⟾} {SEC}_{S}^{r}, \end{matrix}$ where $ε (D) : = r \cdot Δ^{D C^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE))$ , for all distinguishers D.

Proof.

Let S be a random switch value arbitrarily distributed over ${0, 1}^{r}$ . Although the simulator $σ_{CPA}$ does a priori not know the value of the random switch S, it can easily retrieve it by querying the channel ${SEC}_{S}^{r}$ on $(j, getmsg)$ . If the answer contains the error symbol ◆, then $S_{j} = 0$ , otherwise $S_{j} = 1$ , for all $j \in {1, \dots, r}$ . If $S_{j} = 0$ , then the simulator $σ_{CPA}$ will never be able to retrieve the transmitted message of the jth session and simulates therefore the transmission of a ciphertext by encrypting a random message of the correct length under a random key. For such a session, any key retrieval query $(j, getkey)$ will be responded with the error symbol ◆. In the other case, if $S_{j} = 1$ , the simulator $σ_{CPA}$ can simply retrieve the transmitted message and encrypt it under a uniform random key to simulate perfectly the sent ciphertext. For such a session, the actual key used for simulating the encryption will be leaked if the simulator $σ_{CPA}$ receives a key retrieval query. The simulator $σ_{CPA}$ is described more precisely in Alg. 15.

Algorithm 15:

Simulator $σ_{CPA}$

Algorithm 16:

Reduction $C_{j^{*}}^{CPA}$

In order to have shorter notations within the proof, denote by $R_{S}$ and $S_{S}$ the real system ${enc}^{A} {dec}^{B} [{KEY}_{S}^{r}, {AUT}^{r}]$ and the ideal system $σ^{E} {SEC}_{S}^{r}$ , respectively. Note that for sessions which are “broken” ( $S_{j} = 1$ ) the simulation is perfect, while for the other sessions the only difference between the two systems $R_{S}$ and $S_{S}$ lies in the way ciphertexts are produced: $R_{S}$ produces encryptions of messages which were input at interface $A$ , whereas $S_{S}$ produces encryptions of random messages of the same length as messages input at $A$ . Distinguishing $R_{S}$ from $S_{S}$ can therefore be reduced to the IND-CPA security of the underlying encryption scheme via a hybrid argument as follows.

Define a sequence of reduction systems $C_{1}^{CPA}, \dots, C_{r}^{CPA}$ , where each reduction $C_{j^{*}}^{CPA}$ has 4 outside sub-interfaces (labeled $A, B, E_{1, N}$ , and $E_{2}$ ) and connects at its inside interface $in$ to one of the two IND-CPA systems $G_{0}^{CPA} (SE)$ or $G_{1}^{CPA} (SE)$ described in Alg. 2, for all $j^{*} \in {1, \dots, r}$ . Initially, the reduction system $C_{j^{*}}^{CPA}$ selects r keys $k_{1}, \dots, k_{r}$ uniformly at random, as well as a switch value $(s_{1}, \dots, s_{r})$ according to $P_{S}$ , the distribution of the random switch S. Upon input $(j, m)$ at its outside sub-interface $A$ , the reduction system $C_{j^{*}}^{CPA}$ outputs $(j, m)$ at its outside sub-interface $B$ and $(j, c)$ at $E_{2}$ , where the ciphertext c is computed as follows. If session j is “broken” ( $s_{j} = 1$ ), then c is a local encryption of the input message m under key $k_{j}$ . Otherwise, if session j is not “broken” ( $s_{j} = 0$ ), then c is a local encryption of a fresh random message of length $| m |$ under key $k_{j}$ for session $j < j^{*}$ , while for session $j > j^{*}$ the ciphertext c is an actual encryption of the input message under key $k_{j}$ . Finally, only for an unbroken session $j = j^{*}$ is the ciphertext c the result of querying the system connected at its inside interface on the message m. Key retrieval queries $(j, getkey)$ made to the outside sub-interface $E_{1, N}$ of $C_{j^{*}}^{CPA}$ are replied by $(j, ◆)$ or $(j, k_{j})$ according to the value of $s_{j}$ . The reduction system $C_{j^{*}}^{CPA}$ is described more formally in Alg. 16.

Note that ciphertexts produced by $C_{1}^{CPA} G_{0}^{CPA} (SE)$ are always encryptions of messages which were input at interface $A$ and thus $R_{S} \equiv C_{1}^{CPA} G_{0}^{CPA} (SE)$ . Similarly, ciphertexts produced by $C_{r}^{CPA} G_{1}^{CPA} (SE)$ are encryptions of random messages of the same length as messages input at $A$ , unless they are for a “broken” session in which case the actual input message is encrypted, and thus $S_{S} \equiv C_{r}^{CPA} G_{1}^{CPA} (SE)$ . Furthermore, note that unless a session is broken, both $C_{j + 1}^{CPA} G_{0}^{CPA} (SE)$ and $C_{j}^{CPA} G_{1}^{CPA} (SE)$ produce encryptions of random messages of the appropriate length until the jth session, while ciphertexts for sessions $j + 1, \dots, r$ are actual encryptions of input messages. Thus, the sequence of reduction systems $C_{1}^{CPA}, \dots, C_{r}^{CPA}$ is such that $C_{j + 1}^{CPA} G_{0}^{CPA} (SE) \equiv C_{j}^{CPA} G_{1}^{CPA} (SE)$ , for all $j \in {1, \dots, r - 1}$ . For a reduction system $C^{CPA}$ which selects a session $j^{*} \in {1, \dots, r}$ uniformly at random and then implements the reduction $C_{j^{*}}^{CPA}$ it holds that $\begin{matrix} Δ^{D C^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE)) = \frac{1}{r} \cdot Δ^{D} (R_{S}, S_{S}), \end{matrix}$ for every distinguisher D. □

The previous lemmas allow to easily prove that password-based encryption with these additional local assumptions is possible if the encryption scheme used is IND-CPA secure and the r passwords are independently distributed.

Theorem 15.

Let $SE : = (enc, dec)$ be a correct encryption scheme and consider the associated protocol $SE : = (enc, dec)$ . For every product distribution $P$ of r passwords and every tuple of r integers $\vec{q} : = (q_{1}, \dots, q_{r})$ , there exist a simulator $σ_{LT}$ and an (efficient) reduction system $C^{LT}$ described in the proof such that $\begin{matrix} [{KEY}_{LT (P, \vec{q})}^{r}, {AUT}^{r}] \overset{(SE, σ_{LT}, ε)}{⟾} {SEC}_{LT (P, \vec{q})}^{r}, \end{matrix}$ where $ε (D) : = r \cdot Δ^{D C^{LT}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE))$ , for every distinguisher D.

Proof.

Consider a product distribution $P$ of r passwords and a tuple of r integers $\vec{q} : = (q_{1}, \dots, q_{r})$ . In order to have shorter notations within the proof, let $R_{LT (P, \vec{q})}$ denote the downgradable resource $[{KEY}_{LT (P, \vec{q})}^{r}, {AUT}^{r}]$ and let $S_{LT (P, \vec{q})}$ denote ${SEC}_{LT (P, \vec{q})}^{r}$ . Given the encryption protocol $SE : = (enc, dec)$ and some resource U, it will convenient to write $SE U : = {enc}^{A} {dec}^{B} U$ .

Then, Lemma 12 implies that there exist two converters $σ_{KEY, \vec{q}}$ and $σ_{SEC}$ , as well as a random variable $S^{*}$ over ${0, 1}^{r}$ , such that $\begin{matrix} R_{LT (P, \vec{q})} \equiv σ_{KEY, \vec{q}}^{' E} R_{S^{*}} and S_{S^{*}} \equiv σ_{SEC}^{E} S_{LT (P, \vec{q})}, \end{matrix}$ where $σ_{KEY, \vec{q}}^{'} : = ⟨ σ_{KEY, \vec{q}}, id ⟩$ and accounts for the presence in parallel of the channel ${AUT}^{r}$ in R. Lemma 14 implies then that for such a random switch value $S^{*}$ , there exist a simulator $σ_{CPA}$ and a reduction $C^{CPA}$ , such that for all distinguishers D $\begin{matrix} Δ^{D} (SE R_{S^{*}}, σ_{CPA}^{E} S_{S^{*}}) ⩽ r \cdot Δ^{D C^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE)) . \end{matrix}$ The proof then follows by composition. To see that, note that the previous system equation implies that $\begin{matrix} SE R_{LT (P, \vec{q})} \equiv SE σ_{KEY, \vec{q}}^{' E} R_{S^{*}} \equiv σ_{KEY, \vec{q}}^{' E} SE R_{S^{*}}, \end{matrix}$ using the fact that converters connected at different interfaces commute. Let the simulator $σ_{LT}$ be defined as the sequential composition of the aforementioned simulators, i.e., $σ_{LT} : = σ_{KEY, \vec{q}}^{'} \circ σ_{CPA} \circ σ_{SEC}$ . Then, it holds that ${σ_{LT}}^{E} S_{LT (P, \vec{q})} \equiv σ_{KEY, \vec{q}}^{' E} σ_{CPA}^{E} S_{S^{*}}$ , and thus $\begin{matrix} Δ^{D} (SE R_{LT (P, \vec{q})}, {σ_{LT}}^{E} S_{LT (P, \vec{q})}) = Δ^{D^{'}} (SE R_{S^{*}}, σ_{CPA}^{E} S_{S^{*}}), \end{matrix}$ where $D^{'} : = D σ_{KEY, \vec{q}}^{' E}$ . The proof is then finished by combining both distinguishing advantages and defining the overall reduction $C^{LT}$ as $C^{LT} : = σ_{KEY, \vec{q}}^{' E} C^{CPA}$ . □

Remark 16.

The simulation strategy employed by $σ_{LT}$ in the construction of Theorem 15 is rather peculiar. Informally, whenever $σ_{LT}$ has to simulate a ciphertext for a particular session, it first tries to brute force the password of this session by probing the most likely passwords (as described by $σ_{SEC}$ in Alg. 14). If this step succeeds, $σ_{LT}$ can perfectly simulate the transmitted ciphertext, otherwise it simply encrypts a random message of the appropriate length (as described by $σ_{CPA}$ in Alg. 15). Finally, even though $σ_{LT}$ exhausts its password-guessing queries at the beginning, it can emulate the correct answer to an outside password-guessing query by appropriately scaling the probabilities (as described by $σ_{KEY, \vec{q}}$ in Alg. 13). Note that the assumptions discussed in Remark 13 are also required for $σ_{LT}$ .

6.4. Salting and per-session security

This section examines the well-known salting technique, a standard tool to achieve domain separation in password hashing. This technique consists of prefixing all queries made to a single random oracle by a distinct bit string in each of the r sessions, making the queries from different sessions land in different subdomains of the random oracle. In practice, a randomly chosen bit string is used for every session, maintaining the same properties with high probability.

Assumed resources. The construction statement below assumes the availability of a single random oracle and the strings used for salting. The random oracle ${RO}_{q}$ is restricted by allowing Eve to ask at most q queries. The source of salts is formalized as a resource $SALT$ and parameterized by a distribution $R$ of r distinct t-bit strings, for some appropriate integer t. The resource $SALT (R)$ first samples $(v_{1}, \dots, v_{r})$ from $R$ and then outputs $(j, v_{j})$ at interface $i \in {A, B, E}$ whenever it receives a query $(j, getsalt)$ at the same interface, for any $j \in {1, \dots, r}$ . Note that the prefixes used in each session are public and can be retrieved by Eve.

The prefixing protocol. Both Alice and Bob use the bit strings provided by the salting resource to prefix their queries as described by the following converter $pre$ : Upon input $(j, x)$ at its interface $out$ , corresponding to hashing a message $x \in {0, 1}^{*}$ for the jth session, the converter $pre$ retrieves the prefix $v_{j}$ associated with that session by querying $SALT (R)$ on $(j, getsalt)$ and then outputs the value returned by the single random oracle when queried on $v_{j} ∥ x$ .

Desired resource. The goal of the prefixing protocol $PRE : = (pre, pre)$ is to construct r independent random oracles. Since the assumed random oracle ${RO}_{q}$ can be queried by Eve at most q times, the constructed resource will naturally have a similar restriction. Namely, the following lemma shows that the prefixing protocol $PRE$ constructs r globally restricted random oracles ${[RO, \dots, RO]}_{q}$ .

Lemma 17.
Consider the prefixing protocol $PRE : = (pre, pre)$ described above. Then, for every distribution $R$ of r distinct bit strings of equal length and every integer q, there exists a simulator $σ_{pre}$ such that $\begin{matrix} [{RO}_{q}, SALT (R)] \overset{(PRE, σ_{pre}, 0)}{⟾} {[RO, \dots, RO]}_{q} . \end{matrix}$
Proof.
The simulator $σ_{pre}$ first selects r bit strings $(v_{1}, \dots, v_{r})$ of equal length according to the distribution $R$ . Then, whenever a salt retrieval query $(j, getsalt)$ for the jth session is input at its interface ${out}_{2}$ , the simulator $σ_{pre}$ returns $(j, v_{j})$ at the same interface. When a message $x \in {0, 1}^{}$ to be hashed is input at its interface ${out}_{1}$ , the simulator $σ_{pre}$ first checks whether one of the strings $v_{j}$ is a prefix of x, i.e., whether $x = v_{j} ∥ x^{'}$ for some $j \in {1, \dots, r}$ and $x^{'} \in {0, 1}^{}$ . If this is the case, then $σ_{pre}$ returns the answer of the jth random oracle when queried on $x^{'}$ . Otherwise, the simulator $σ_{pre}$ simply returns a uniform n-bit string. The simulator $σ_{pre}$ replies consistently to any repeating query and in addition keeps track of the number of queries to avoid too many “dummy” queries, i.e., queries which are not prefixed by one of the strings $v_{j}$ . It can be readily verified that the simulation is perfect. □

Unfortunately, it is easy to show that the same salting protocol $PRE$ cannot construct r locally restricted random oracles $[{RO}_{q_{1}}, \dots, {RO}_{q_{r}}]$ , at least not unless $q_{j} ⩾ q$ for all $j \in {1, \dots, r}$ (the latter would render this construction uninteresting due to the blow-up in the number of adversarial queries). More formally, let us consider a simulator σ such that $[{RO}_{q}, SALT (R)] \overset{(PRE, σ, ε)}{⟾} [{RO}_{q_{1}}, \dots, {RO}_{q_{r}}]$ . Then, $\begin{matrix} q_{j} ⩾ q for all j \in {1, \dots, r} or there exists a distinguisher D such that ε (D) ⩾ 1 - 2^{- n}, \end{matrix}$ where n is the output length of the random oracle $RO$ .

To see this, consider the systems $R : = {pre}^{A} {pre}^{B} [{RO}_{q}, SALT (R)]$ and $S : = σ^{E} [{RO}_{q_{1}}, \dots, {RO}_{q_{r}}]$ for some arbitrary simulator σ. In the real experiment, a distinguisher making a query $(j, x)$ to the interface $A$ and a query $(j, v_{j} ∥ x)$ to the interface $E_{1}$ of R, where $v_{j}$ is the prefix for the jth session output by the salting resource, observes the same output. Hence, in the ideal experiment, for any query of the type $(j, v_{j} ∥ x)$ the simulator σ has to query the jth random oracle ${RO}_{q_{j}}$ on x in order to be able to mimic this behavior. Thus, a distinguisher can choose any session j and make all its q queries to the associated random oracle ${RO}_{q_{j}}$ by appropriately prefixing each query, hence requiring $q_{j} ⩾ q$ for any successful simulator to exist.

Consequences for local restrictions. The above observation implies that relying on local query restrictions for multi-session security of password-based encryption (as in Theorem 15) appears to be in general rather unrealistic. The salting technique employed in PKCS #5 [17] (and more generally, any domain separation technique which is public) fails to construct locally restricted random oracles $[{RO}_{q_{1}}, \dots, {RO}_{q_{r}}]$ from a single random oracle ${RO}_{q}$ for any meaningful values of $q_{1}, \dots, q_{r}$ .
6.5. On the per-session security of PBE from PKCS #5

This section shows how the arguments used to prove Theorem 10 also apply to the password-based encryption standard described in PKCS #5 [17], which thus in general does not achieve per-session confidentiality.

Algorithm 17:

Distinguisher $D_{ℓ, ε}^{'}$

Algorithm 18:

Distinguisher $D_{ℓ, q}^{CPA}$

Recall that the protocol described in [17] consists of hashing a salt concatenated with a password and of using the result as a key for encryption. (Additionally, it also increases the cost of a brute-force attack by iterative hashing. This is, however, an orthogonal aspect, see [13] for a detailed discussion.) Formalized as a pair of converters $(pbe, pbd)$ , this protocol corresponds to first doing the salting step via the protocol $(pre, pre)$ described in Section 6.4, then the key derivation protocol $(kd, kd)$ described in Section 4 and finally symmetric encryption $(enc, dec)$ described in Section 6. As detailed in previous sections, such a protocol assumes the following resources to be available: a random oracle ${RO}_{q}$ , a source of salts $SALT (R)$ , a source of shared passwords $PW (P)$ , and finally an authenticated communication channel ${AUT}^{r}$ for each of the r sessions. Denote by $RKDF (q, R, P)$ the resources used for key derivation, i.e., $\begin{matrix} RKDF (q, R, P) : = [{RO}_{q}, SALT (R), PW (P)] . \end{matrix}$

Theorem 18.

Let $SE : = (enc, dec)$ be a correct encryption scheme with key space $K : = {0, 1}^{n}$ and message space $M \subseteq {0, 1}^{*}$ , and consider the combined protocol $(pbe, pbd)$ described above. Let T be a trigger system with input space ${1, \dots, r} \times W$ and output space ${0, 1}^{r}$ , and let $M_{ℓ}$ denote a non-empty set of messages of fixed length ℓ in $M$ , for some integer ℓ. Then, for every integer q, such that $\forall m \in M, c \in C : q < \frac{2^{n}}{| {k : dec (k, c) = m} |},$ every $ε > 0$ , every distribution $R$ of r distinct bit strings of the same length and every distribution $P$ of r passwords, there exists a distinguisher $D_{ℓ, ε}^{'}$ described in Alg. 17 such that for all simulators σ it holds that $\begin{matrix} Δ^{D_{ℓ, ε}^{'}} ({pbe}^{A} {pbd}^{B} [RKDF (q, R, P), {AUT}^{r}], σ^{E} {SEC}_{T}^{r}) ⩾ δ_{T}^{GT (P, q)} - μ - ε, \end{matrix}$ where $δ_{T_{1}}^{T_{2}} : = Γ_{opt}^{T_{2}} - Γ_{avg}^{T_{1}}$ , with $Γ_{opt}^{T_{2}}$ and $Γ_{avg}^{T_{1}}$ defined in ( 1 ), and $\begin{matrix} μ ⩽ 2 r \cdot Δ^{D_{ℓ, q}^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE)) + (2 r + 1) \cdot \frac{| K |}{| M_{ℓ} |}, \end{matrix}$ for a distinguisher $D_{ℓ, q}^{CPA}$ described in Alg. 18 .

The proof is analogous to that of Theorem 10 and consequently the same limitations mentioned in Remark 11 also apply to Theorem 18. Indeed, if the encryption scheme used is IND-CPA secure and uses significantly less keys than messages, then the dominant term in the lower bound above is $δ_{T}^{GT (P, q)}$ which may become moot depending on the trigger T considered in the constructed resource. However, in the case where the passwords are independently distributed and $T : = GT (P, p)$ , the quantity $δ_{T}^{GT (P, q)}$ will be large for most password distributions if $p < r q$ , since following the optimal guessing strategy for a particular session usually requires to exhaust all q guesses. Likewise, if instead $T : = LT (P, \vec{q})$ , for some integers $\vec{q} : = (q_{1}, \dots, q_{r})$ , then $δ_{T}^{GT (P, q)}$ will be large if $q_{j} < q$ for some $j \in {1, \dots, r}$ .

Proof of Theorem 18.

The main idea is to use the same strategy as distinguisher $D_{ℓ, ε}$ in Alg. 12 which, very roughly, consists of the following three steps: 1) input r messages $m_{1}, \dots, m_{r}$ of length ℓ chosen uniformly at random; 2) observe the corresponding ciphertexts $c_{1}, \dots, c_{r}$ ; and 3) use an almost-optimal strategy to break a session $j^{*}$ chosen uniformly at random. This last step has to be adapted since the resources considered, contrary to those in Theorem 10, do not have a switch value $s_{j}$ indicating whether session j is broken.

In order to have shorter notations within the proof, the real system ${pbe}^{A} {pbd}^{B} [RKDF (q, R, P), {AUT}^{r}]$ will be denoted by R and the ideal system $σ^{E} {SEC}_{T}^{r}$ will be denoted by $S_{T}$ , for some simulator σ and some $({1, \dots, r} \times W, {0, 1}^{r})$ -trigger system T. Eve’s interface in R is split as follows: sub-interfaces $E_{1, 1}, E_{1, 2}$ and $E_{1, 3}$ denote the respective $E$ -interface of the resources ${RO}_{q}$ , $SALT (R)$ and $PW (P)$ in the combined resource $RKDF (q, R, P)$ ; while the sub-interface $E_{2}$ of R denotes the $E$ -interface of the authenticated channel ${AUT}^{r}$ .

Similarly to $D_{ℓ, ε}$ , the new distinguisher $D_{ℓ, ε}^{'}$ uses the ε-optimal strategy $D_{opt, ε} (j^{*})$ for guessing the password used in a randomly chosen session $j^{*}$ , analogously to Theorem 10. Note that $D_{opt, ε} (j^{*})$ expects as input an r-bit string indicating the “broken” state of each session. To do so, distinguisher $D_{ℓ, ε}^{'}$ keeps a state $(s_{1}, \dots, s_{r})$ which is updated as follows. Given a password guess $(j, w)$ for session j (which could a priori be different from $j^{*}$ ), the new distinguisher $D_{ℓ, ε}^{'}$ declares session j “broken” if the output k of the random oracle when queried on $v_{j} ∥ w$ , where $v_{j}$ is the prefix used for session j, is such that $dec (k, c_{j}) = m_{j}$ . The distinguisher $D_{ℓ, ε}^{'}$ is specified in Alg. 17.

The next step is to lower-bound the distinguishing advantage $Δ^{D_{ℓ, ε}^{'}} (R, S_{T})$ . Let $G_{j}$ be the event that the password used in session j was correctly guessed in the random experiment $D_{ℓ, ε}^{'} R$ , i.e., a query prefixed by $v_{j}$ made to the random oracle at interface $E$ matches a previous query made to the random oracle at interface $A$ or $B$ , where $v_{j}$ is the prefix used for session j output by the salting resource $SALT (R)$ . The complementary event will be denoted by $\overline{G_{j}}$ . If distinguisher $D_{ℓ, ε}^{'}$ manages to guess the password of the chosen session $J^{*} = j^{*}$ , it will necessarily output 1 due to the correctness of the encryption scheme, $\begin{matrix} P^{D_{ℓ, ε}^{'} R} (1) = \sum_{j^{*} = 1}^{r} P^{D_{ℓ, ε}^{'} R} (J^{*} = j^{*}) P^{D_{ℓ, ε}^{'} R} (1 ∣ J^{*} = j^{*}) ⩾ \frac{1}{r} \sum_{j^{*} = 1}^{r} P^{D_{ℓ, ε}^{'} R} (G_{j^{*}} ∣ J^{*} = j^{*}) . \end{matrix}$

Yet, the switch values $(s_{1}, \dots, s_{r})$ emulated by distinguisher $D_{ℓ, ε}^{'}$ and input to $D_{opt, ε} (j^{*})$ have a different distribution than when $D_{opt, ε} (j^{*})$ interacts with the trigger $GT (P, q)$ alone. Indeed, in the random experiment $D_{ℓ, ε}^{'} R$ , if a session j is declared to be “broken” ( $s_{j} = 1$ ), it does not necessarily mean that $D_{opt, ε} (j^{*})$ correctly guessed the password used in session j, it could also be due to either collisions in the random oracle or to the existence of a second key k such that $dec (k, c_{j}) = m_{j}$ . This implies that $P^{D_{ℓ, ε}^{'} R} (G_{j^{*}} ∣ J^{*} = j^{*})$ may be smaller than ${sup}_{D \in D} Γ^{GT (P, q)} (j^{*}, D)$ , and this difference must be bounded.

To do so, let $B_{j}$ be the event in the random experiment $D_{ℓ, ε}^{'} R$ that a query made to the random oracle at its $E$ interface resulted in session j being declared “broken” ( $s_{j} = 1$ ) even though the password used in session j was not yet guessed (corresponding to the event $\overline{G_{j}}$ ) and let $B$ be the union of these events $B_{j}$ , for all $j \in {1, \dots, r}$ . Conditioned on the event $B$ not happening, a session is declared “broken” if and only if its password is guessed and thus $\begin{matrix} P^{D_{ℓ, ε}^{'} R} (G_{j^{*}} ∣ J^{*} = j^{*}) ⩾ sup_{D \in D} Γ^{GT (P, q)} (j^{*}, D) - ε - P^{D_{ℓ, ε}^{'} R} (B ∣ J^{*} = j^{*}), \end{matrix}$ for every session $j^{*} \in {1, \dots, r}$ .

From the union bound, it follows that $P^{D_{ℓ, ε}^{'} R} (B ∣ J^{*} = j^{*}) ⩽ \sum_{j \in {1, \dots, r}} P^{D_{ℓ, ε}^{'} R} (B_{j} ∣ J^{*} = j^{*})$ , which means that now the probability of the event $B_{j}$ happening in the random experiment $D_{ℓ, ε}^{'} R$ , for some session j, must be upper-bounded. Consider a query $v_{j} ∥ w$ made to the random oracle at its interface $E$ , for some password guess $w \in W$ and where $v_{j}$ is the prefix associated with session j, such that this query provoked the event $s_{j} = 1$ even though the event $\overline{G_{j}}$ happened. Note that such a query $v_{j} ∥ w$ was never asked before to the random oracle at interface $E$ (since it provoked the event $s_{j} = 1$ ), and was also never queried by the honest parties at interface $A$ or $B$ of the random oracle since the password for that session is not guessed (because of the event $\overline{G_{j}}$ ) and other sessions use different prefixes. Thus, the answer of the random oracle on such a fresh query $v_{j} ∥ w$ is uniformly and independently distributed and conditioned on a given message $m_{j}$ and ciphertext $c_{j}$ the probability that the event $B_{j}$ happens is thus at most $q \cdot 2^{- n} | {k^{'} \in K ∣ dec (k^{'}, c_{j}) = m_{j}} |$ since there are at most q queries made to the random oracle at interface $E$ . As $c_{j}$ is an encryption of $m_{j}$ under a random key, it then follows that for all j, $j^{*}$ , $\begin{matrix} P^{D_{ℓ, ε}^{'} R} (B_{j} ∣ J^{*} = j^{*}) ⩽ q \cdot \frac{{\bar{κ}}_{ℓ}}{2^{n}}, \end{matrix}$ where $κ_{ℓ} (m, c) : = | {k^{'} \in K ∣ dec (k^{'}, c) = m} |$ is the number of keys decrypting a ciphertext c to a message m, and ${\bar{κ}}_{ℓ} : = E_{m, c} [κ_{ℓ} (m, c)]$ denotes the average for the original random message of length ℓ, where the expectation is taken over a message m chosen uniformly at random in $M_{ℓ}$ and $c \leftarrow enc (k, m)$ for a uniformly chosen key k.

Note that if the encryption scheme used is IND-CPA secure, then the ratio $q \frac{{\bar{κ}}_{ℓ}}{2^{n}}$ will be small. To see that, consider a distinguisher $D_{ℓ, q}^{CPA}$ which interacts with the CPA systems $G_{b}^{CPA} (SE)$ described in Alg. 2. The distinguisher $D_{ℓ, q}^{CPA}$ first selects a message m uniformly at random in $M_{ℓ}$ , then outputs it to $G_{b}^{CPA} (SE)$ to retrieve the ciphertext c and finally tries to decrypt it by selecting q keys uniformly at random.

Distinguisher $D_{ℓ, q}^{CPA}$ outputs 0 when connected to $G_{0}^{CPA} (SE)$ with probability $\begin{matrix} P^{D_{ℓ, q}^{CPA} G_{0}^{CPA} (SE)} (0) = \sum_{m \in M_{ℓ}, c \in C} P^{D_{ℓ, q}^{CPA} G_{0}^{CPA} (SE)} (M = m \land C = c) \cdot (1 - {(1 - \frac{κ_{ℓ} (m, c)}{2^{n}})}^{q}), \end{matrix}$ which can be lower-bounded by $\begin{matrix} \sum_{m \in M_{ℓ}, c \in C} P^{D_{ℓ, q}^{CPA} G_{0}^{CPA} (SE)} (M = m \land C = c) \cdot q \frac{κ_{ℓ} (m, c)}{2^{n + 1}} = q \frac{{\bar{κ}}_{ℓ}}{2^{n + 1}}, \end{matrix}$ given that $\frac{κ_{ℓ} (m, c)}{2^{n}} < \frac{1}{q - 1}$ , as assumed in the theorem statement.4

⁴

For $x \in (0, \frac{1}{q - 1})$ , it holds that $1 - {(1 - x)}^{q} ⩾ \frac{x q}{2}$ .

In contrast, when interacting with

G_{1}^{CPA} (SE)

, the ciphertext c produced is independent of the message and thus

D_{ℓ, q}^{CPA}

outputs 0 with probability at most

\frac{| K |}{| M_{ℓ} |}

. Thus,

\begin{matrix} q \cdot \frac{{\bar{κ}}_{ℓ}}{2^{n + 1}} ⩽ Δ^{D_{ℓ, q}^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE)) + \frac{| K |}{| M_{ℓ} |} . \end{matrix}

The previous equations imply that

\begin{matrix} P^{D_{ℓ, ε}^{'} R} (1) ⩾ Γ_{opt}^{GT (P, q)} - ε - 2 r \cdot (Δ^{D_{ℓ, q}^{CPA}} (G_{0}^{CPA} (SE), G_{1}^{CPA} (SE)) + \frac{| K |}{| M_{ℓ} |}) . \end{matrix}

Similarly to the proof of Theorem 10, the disitnguisher $D_{ℓ, ε}^{'}$ outputs 1 when interacting with the ideal system $S_{T}$ with probability at most $Γ_{avg}^{T} + \frac{| K |}{| M_{ℓ} |}$ . The desired bound is then obtained by combining the last two equations. □

7. Conclusion

The work of Bellare et al. [6] initiated the provable-security analysis of the techniques used in the password-based cryptography standard [17] and its application in password-based encryption. As discussed in Section 1, however, they do not prove the desired per-session security guarantee for PBE.

Even though Theorem 15 shows that the results of [6] carry over to a composable model with per-session guarantees, this requires corresponding per-session assumptions on the distribution of adversary computation, and the simulation strategy used is already quite peculiar: the simulator needs to know the password distribution and it must also make all password-guessing attempts before simulating the first ciphertext. This means that the constructed resource allows the attacker to aggregate its entire “computational power” and spend it in advance rather than distributed over the complete duration of the resource use.

The general impossibility result in Theorem 10 shows that bounding the adversary’s queries per session, although an unrealistic assumption (as discussed in Section 6.4), is necessary for our simulation-based proof of security of PBE. Otherwise, a commitment problem akin to the one in adaptively secure public-key encryption (PKE) [25], functional encryption [4,8,19], and identity-based encryption [16], surfaces. Does that mean that one should stop using PBE in practice? In line with Damgård’s [12] perspective on adaptively secure PKE, this question can be viewed as being a fundamental research question still to be answered. On the one hand, there is no attack that would convincingly break PBE, but on the other hand there is also limited provable-security support, at least if one seeks for strong, composable guarantees. Pointing out this commitment problem for PBE, analogously to adaptively secure PKE, can be seen as an important contribution of this paper.

Footnotes

Acknowledgments

Grégory Demay was supported by the Zurich Information Security and Privacy Center (ZISC). Peter Gaži was supported by the European Research Council under an ERC Consolidator Grant (682815-TOCNeT). Björn Tackmann was supported by the Swiss National Science Foundation (SNF) through fellowship P2EZP2-155566 and the National Science Foundation (NSF) under grant CNS-1228890. We are grateful to various anonymous reviewers for their comments that greatly helped us to improve the paper.

References

Abadi and

Warinschi, Password-based encryption analyzed, in: ICALP 2005,

Caires,

G.F.

Italiano,

Monteiro,

Palamidessi and

Yung, eds, LNCS, Vol. 3580, Springer, Heidelberg, 2005, pp. 664–676.

Alwen and

Serbinenko, High parallel complexity graphs and memory-hard functions, in: 47th ACM STOC,

R.A.

Servedio and

Rubinfeld, eds, ACM Press, 2015, pp. 595–603.

Bellare,

Desai,

Jokipii and

Rogaway, A concrete security treatment of symmetric encryption, in: 38th FOCS, IEEE Computer Society Press, 1997, pp. 394–403.

Bellare and

O’Neill, Semantically-secure functional encryption: Possibility results, impossibility results and the quest for a general definition, in: CANS 13,

Abdalla,

Nita-Rotaru and

Dahab, eds, LNCS, Vol. 8257, Springer, Heidelberg, 2013, pp. 218–234.

Bellare,

Pointcheval and

Rogaway, Authenticated key exchange secure against dictionary attacks, in: EUROCRYPT 2000,

Preneel, ed., LNCS, Vol. 1807, Springer, Heidelberg, 2000, pp. 139–155. doi:10.1007/3-540-45539-6_11.

Bellare,

Ristenpart and

Tessaro, Multi-instance security and its application to password-based cryptography, in: CRYPTO 2012,

Safavi-Naini and

Canetti, eds, LNCS, Vol. 7417, Springer, Heidelberg, 2012, pp. 312–329. doi:10.1007/978-3-642-32009-5_19.

Bellare and

Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, in: EUROCRYPT 2006,

Vaudenay, ed., LNCS, Vol. 4004, Springer, Heidelberg, 2006, pp. 409–426. doi:10.1007/11761679_25.

Boneh,

Sahai and

Waters, Functional encryption: Definitions and challenges, in: TCC 2011,

Ishai, ed., LNCS, Vol. 6597, Springer, Heidelberg, 2011, pp. 253–273.

Canetti, Universally composable security: A new paradigm for cryptographic protocols, Report 2000/067, Cryptology ePrint Archive, 2000. http://eprint.iacr.org/2000/067.

10.

Canetti,

Halevi,

Katz,

Lindell and

P.D.

MacKenzie, Universally composable password-based key exchange, in: EUROCRYPT 2005,

Cramer, ed., LNCS, Vol. 3494, Springer, Heidelberg, 2005, pp. 404–421. doi:10.1007/11426639_24.

11.

Corrigan-Gibbs,

Boneh and

Schechter, Balloon hashing: Provably space-hard hash functions with data-independent access patterns, 2016.

12.

Damgård, A “proof-reading” of some issues in cryptography (invited lecture), in: ICALP 2007,

Arge,

Cachin,

Jurdzinski and

Tarlecki, eds, LNCS, Vol. 4596, Springer, Heidelberg, 2007, pp. 2–11.

13.

Demay,

Gazi,

Maurer and

Tackmann, Query-complexity amplification for random oracles, in: ICITS 15,

Lehmann and

Wolf, eds, LNCS, Vol. 9063, Springer, Heidelberg, 2015, pp. 159–180.

14.

Demay,

Gazi,

Maurer and

Tackmann, Per-session security: Password-based cryptography revisited, in: ESORICS 2017, Part I,

S.N.

Foley,

Gollmann and

Snekkenes, eds, LNCS, Vol. 10492, Springer, Heidelberg, 2017, pp. 408–426.

15.

Gennaro and

Lindell, A framework for password-based authenticated key exchange, in: EUROCRYPT 2003,

Biham, ed., LNCS, Vol. 2656, Springer, Heidelberg, 2003, pp. 524–543, http://eprint.iacr.org/2003/032.ps.gz . doi:10.1007/3-540-39200-9_33.

16.

Hofheinz,

Matt and

Maurer, Idealizing identity-based encryption, in: ASIACRYPT 2015, Part I,

Iwata and

J.H.

Cheon, eds, LNCS, Vol. 9452, Springer, Heidelberg, 2015, pp. 495–520. doi:10.1007/978-3-662-48797-6_21.

17.

B.S.

KaliskiJr., PKCS #5: Password-based cryptography specification, RFC 2898, 2000.

18.

Katz,

Ostrovsky and

Yung, Efficient password-authenticated key exchange using human-memorable passwords, in: EUROCRYPT 2001,

Pfitzmann, ed., LNCS, Vol. 2045, Springer, Heidelberg, 2001, pp. 475–494. doi:10.1007/3-540-44987-6_29.

19.

Matt and

Maurer, A definitional framework for functional encryption, in: IEEE 28th IEEE CSF, 2015, pp. 217–231.

20.

Maurer, Constructive cryptography – a new paradigm for security definitions and proofs, in: Theory of Security and Applications,

Mödersheim and

Palamidessi, eds, LNCS, Vol. 6993, Springer, Berlin, Heidelberg, 2012, pp. 33–56. doi:10.1007/978-3-642-27375-9_3.

21.

Maurer, Conditional equivalence of random systems and indistinguishability proofs, in: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), 2013, pp. 3150–3154. doi:10.1109/ISIT.2013.6620806.

22.

Maurer and

Renner, Abstract cryptography, in: The Second Symposium in Innovations in Computer Science, ICS 2011,

Chazelle, ed., Tsinghua University Press, 2011, pp. 1–21.

23.

U.M.

Maurer, Indistinguishability of random systems, in: EUROCRYPT 2002,

L.R.

Knudsen, ed., LNCS, Vol. 2332, Springer, Heidelberg, 2002, pp. 110–132. doi:10.1007/3-540-46035-7_8.

24.

Morris and

Thompson, Password security: A case history, Communications of the ACM 22(11) (1979), 594–597. doi:10.1145/359168.359172.

25.

J.B.

Nielsen, Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case, in: CRYPTO 2002,

Yung, ed., LNCS, Vol. 2442, Springer, Heidelberg, 2002, pp. 111–126. doi:10.1007/3-540-45708-9_8.

26.

O’Gorman, Comparing passwords, tokens, and biometrics for user authentication, Proceedings of the IEEE 91(12) (2003), 2021–2040. doi:10.1109/JPROC.2003.819611.

27.

Percival, Stronger key derivation via sequential memory-hard functions, Self-published (2009), 1–16.

28.

Petsas,

Tsirantonakis,

Athanasopoulos and

Ioannidis, Two-factor authentication: Is the world ready? Quantifying 2FA adoption, in: Proceedings of the Eighth European Workshop on System Security, ACM, 2015, p. 4.

29.

Tackmann, A theory of secure communication, PhD thesis, ETH Zürich, 2014.

30.

F.F.

Yao and

Y.L.

Yin, Design and analysis of password-based key derivation functions, in: CT-RSA 2005,

Menezes, ed., LNCS, Vol. 3376, Springer, Heidelberg, 2005, pp. 245–261.

Per-session security: Password-based cryptography revisited

Abstract

Keywords

1. Introduction

1.1. Motivation of this work

1 This is also referred to as the multi-user setting in the literature, but we prefer the term session here since the same user can participate in multiple sessions.

1.4. Structure of this paper

2. Preliminaries

2.1. Basic notation

2.2. Systems

2.3. Games

Lemma 1 ([21, Lem. 1, 2]).

2.4. The construction notion in the (Alice, Bob, Eve)-setting

3.1. Core systems and triggers

Example 4 (Key).

Example 5 (Secure channel).

Example 6 (Local and global password-guessing triggers).

Corollary 9 (Informal).

6.2. General impossibility of PBE

Footnotes

Acknowledgments

References

¹
This is also referred to as the multi-user setting in the literature, but we prefer the term session here since the same user can participate in multiple sessions.