Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Password-based authentication (PA) is the most wide-spread way deployed to authenticate users. A lot of advanced forms of authentications have been developed by the research community. However, the simplest form of PA, consisting of a (login, password) pair, widely remains the method in use. Moreover, this form of authentication takes more and more place in citizen’s life. Each entity and service, own their websites and information systems, and each of them asks the user for a password to get accessed.

The server managing the access rights stores the users’ information. Fortunately, most of the time, the password is not directly stored. Instead, a one-way, hard to invert, function is applied to the password, and the output, aka the verifier, is stored on the server. This is a first step towards password protection. Given a verifier, a brute-force recovering of the password consists of computing the output of the function for all possible values of the password and comparing the results with the verifier, sometimes with the help of dictionaries. Such an attack is implicitly assumed to be impossible. However, the password is often chosen within a limited set of passwords, which makes the brute-force recovering possible. A lot of protocols aims at being secure up to dictionary attacks. In other words, the protocol ensures that the best possible attack is the dictionary attack. In this paper, we ask whether it would be possible to go beyond this bound. Ideally, we would like the verifier to leak no information at all about the password. Thus, the consequences of server compromises would be mitigated.

Our approach. First of all, we would like to enhance the security of the most common password based authentication, so we do not want to rely on specific hardware. We rather use a two-factor software-only approach. During the registration process, a user gets a value, called the token, while the server records the verifier. The two factors needed for the authentication are the password and the token. We want the brute-force recovering of the password to be impossible given only the verifier or the token. If a token is stolen, we want that only on-line attempts are possible. As usual, a bound on the number of attempts will protect the password. Such an authentication is well-suited to a mobile scenario, where the token is stored on the phone. Moreover, we do not want to rely on advanced cryptographic mechanisms, such as bilinear pairings in group of prime orders. All operations in our constructions are based on operations in a group of prime order. We propose two solutions, called pw-com and pw-hom, we now briefly introduce in this introduction. In the main body of this paper, we prove them secure in the random oracle model.

High-level view of our solution based on commitments. Our first solution, pw-com, uses the standard notion of commitments and zero-knowledge proofs. A commitment scheme enables a user to commit to a value without revealing it. The commitment binds the user to the committed value, but the user is ensured that the value is not disclosed. Then, with a zero-knowledge (ZK) proofs of knowledge (PK) of a committed value, the user proves that he knows a pair (m, r) such that \(c = \mathtt {Commit} (m; r)\) without revealing any information about (m, r). Let Com be a commitment scheme, \(\mathcal {P}\) be a set of password and \(\mathtt {H}_h:\mathcal {P} \rightarrow \mathcal {M}_\mathsf {C}\) be an injective encoding from the set \(\mathcal {P}\) to the message space \(\mathcal {M}_\mathsf {C}\) of the commitment scheme. The main idea is to store a statistically hiding commitment as verifier (on the server), and the random value used to commit to the password as token (on the client). The global parameters of the scheme are a commitment key \(\mathsf {ck}\). In the registration phase, the user draws a uniform value \(t \leftarrow \mathcal {R}_\mathsf {C}\) in the random space of the commitment scheme, stores t as token and sends \(c := \mathtt {Commit} (\mathtt {H}_h (pw); t)\). The server stores c as verifier. In the authentication phase, the user supplies a ZKPK of (h, t) such that \(c = \mathtt {Commit} (h; t)\). From a token t and a verifier c, a brute-force attack can be used to recover a password pw such that \(c = \mathtt {Commit} (\mathtt {H}_h (pw); t)\). However, the knowledge of t or c alone does not help to recover the password. On the one hand, the token t leaks no information about the password (in the information-theoretic sense), so if the token is disclosed, only guesses on-line may help to recover the password. On the other hand, the verifier c statistically hides the password, so brute-force attacks are impossible, even for an unlimited adversary. Last, but not least, an authentication session does not leak any information about the password, nor the token, thanks to the zero-knowledge property of the proof of knowledge.

High-level view of our solution based on a homomorphic encryption scheme. Updates of the password in the user’s side are not possible in the pw-com solution. We now ask the question whether it is possible for a user to update its password without interaction with the server. We introduce a solution, denoted pw-hom, based on a homomorphic encryption scheme over a prime order group that achieves this property. The basic idea is the following. Let \(\mathbb {G}\) be a group of prime order – in additive notation here by pure convention – and hom-pke be a public key homomorphic encryption scheme over \(\mathbb {G}\) as message space. After an interactive registration, the client got a pair of ciphertexts encrypting two elements \((K, [h] \cdot K)\) where \(K \in \mathbb {G}\) is a user-specific element and \(h \in \mathbb {Z}_p^*\) an encoding of the password. The verifier contains the decryption keys (there is one key pair per user) and a hash value of K. No information about the password leak from the verifier. In the authentication step, the client computes a proof of knowledge of the password over the ciphertexts thanks to the homomorphic properties of the encryption scheme. In other words, he computes a Schnorr signature [35] over the ciphertexts. Thanks to the verifier, the server is able to decrypt the ciphertexts and to check the proof. However the server could retrieve the password from an authentication, since it could retrieve the pair \((K, [h] \cdot K)\), then the password by brute-force recovering. Therefore, the password is first masked with a fresh random value, then the proof of knowledge is performed. As a result, no information about the password leaks from the server point of view. The user-specific element K allows for authentication on behalf of the user. A crucial point is to use two independent keys to produce the pair of ciphertexts, to prevent the computation of a ciphertext of \([h] \cdot K\) from a ciphertext of K.

On the salting. In both solutions, \(\mathtt {H}_h\) is just an encoding function without any security property. Common solutions include a salt in the password hashing, but there is no need here to include such a salt. A point to be noticed is that, without salt, the \(\mathtt {H}_h (pw)\) values are not uniform, because of the distribution of pw. If \(\mathtt {H}_h\) were a programmable random oracle, the defect would disappear. However, the hiding property of the commitment scheme and the semantic security of the encryption scheme are sufficient to hide the password and to avoid the random oracle assumption on \(\mathtt {H}_h\), a probably too strong and not realistic assumption. The only property we require is that \(\mathtt {H}_h\) must be injective.

Related work. The literature about password based authentication is vast. A lot of protocols are designed to derive a session key, an issue we do not address here. The seminal work of [3] addresses authentication base on passwords only (without additional assumptions) and proposes the Encrypted Key-Exchange protocol (EKE). EKE was followed by several works [4, 21, 31, 38, 40]. The IEEE P1363.2 Password-Based Public-Key Cryptography Working Group [20] contains several of the proposals designed during the nineties. Formal models for Password-based Authenticated Key Exchange (PAKE) appeared in [2, 7]. The GL’s framework [16] is an abstraction of the construction of [26] (KOY), and was the first to propose a solution in the standard model. This framework underlies a lot of subsequent constructions [15, 24, 25, 27, 28]. The GK’s framework [18] is an abstraction of the construction in [23], also achieves PAKE in the standard model, but without trusted setup. A third framework (KV) [29] achieves one-round PAKE in the standard model. Recent work explicitly includes the verifier in Authenticated Key Exchange [5, 30]. However, they only consider security up to the brute-force attack, according to the min-entropy of the passwords.

Turning our attention to two-factor password authentication, the constructions of [36] achieve some of the properties we look for. However, they are based on pairings, a tool we want to avoid in this paper, and they lack a formal analysis. Several commercial solutions exist, such as Google Authenticator [13], Duo Security [10], HotPin [19], and PhoneFactor [33]. The work of [37] introduces a framework to analyse these two-factor authentication protocols, then proposes several efficient constructions, and apply them in different scenarios. The participants in the protocols above are, apart from the user, a client (say a web browser), a server, and a device (say a smartphone). When authenticating, the user submits a password and some additional information supplied by the device. Our model is not the one they follow. We only assume a device (say a smartphone) authenticating to a server; i.e., we do not split between a client and a device. Nevertheless, our solutions can be adapted in some of the scenarios described in [37]. We elaborate on this point in the full version of our paper.

In most existing solutions, including [37], a hashed password is stored on the server and the password is sent during the authentication protocol. To the contrary, in our solutions, the password is never sent when the user authenticates.

In anonymous password authentication [39, 41], several password-based sessions from the same user cannot be linked. Although, several constructions of anonymous password authentication use homomorphic encryption, our solutions do not address the same problem – we protect the passwords against the servers, without privacy of the identities –, and are more efficient.

Finally, let us mention recent concurrent and independent work which also aims at mitigating server breaches for diverse authentication tasks. [8] introduces Virtual Smart Card, a software-only solution for signature generation, in which a signature is jointly generated by a device and a server while the user owning the device authenticates to the server with a password. The signing key is distributed between the device and the server, however the server’s data alone is not sufficient to produce a signature or to mount a brute-force password-recovery attack, and the same holds for the device’s data. Another work [22] introduces Device-Enhanced PAKE, in which the presence of a device in the client’s side is integrated into the notion of Password-based AKE. Their model is not exactly the same as ours: the value stored in the device in their model could be the token in our model, but they also assume computation abilities in the user’s side, whereas we only consider the user as the owner of a device. Last, [6] also aims at mitigating server breaches in PAKE, but with a different approach: the password database is split among several servers.

Organisation of the paper. Section 2 introduces some notations. Section 3 formally defines the two factor authentication we consider in this paper. Section 4 describes our solution based on commitments, and Sect. 5 our solution based on homomorphic encryption.

2 Notations

Notations. If x and y are strings over some alphabet, \(x \Vert y\) denotes their concatenation. \(\varepsilon \) denotes the empty string. \(\mathbb {R}\) denotes the set of real numbers, \(\mathbb {R}^+\) the set of non-negative real numbers, \(\mathbb {N}\) the set of non-negative integers, and \(\mathbb {Z}_n\) the ring \(\mathbb {Z}/n\mathbb {Z}\) of modular integers modulo the integer n. \(1^n\) denotes the unary representation of the integer n. For an integer \(n \ge 1\), [1, n] denotes the set \(\{1, \dots , n\}\). If S is a set and D a distribution, \(x \leftarrow _D S\) means that x is drawn from S according to D. \(x \leftarrow S\) means that x is drawn according to the uniform distribution. \(D \approx E\) denotes that two distributions D and E are indistinguishable (in a computational, statistical, or perfect sense depending on the context). If A is a (probabilistic) algorithm, \(x \leftarrow \mathtt {A} (y)\) means that x is the result of the execution of A on input y, for some internal random coins. If these random coins used by A are made explicit, we note \(x := \mathtt {A} (y; r)\), and A is deterministic. We note \(x \in \mathtt {A} (y)\) to denote that x belongs to the support of A on input y, i.e., that x might be an output of A on input y. The assignment phrase \(a := E\) means that the value a receives the result of the evaluation of the (deterministic) expression E. A function \(f: \mathbb {N} \rightarrow \mathbb {R}^+\) is said negligible if it decreases faster than any polynomial. \(\mathsf {negl} (\cdot )\) denotes some unspecified negligible function.

3 Security Model

In this section, we formally defined the primitive we consider in this paper and the security properties it should satisfy. A two-factor password-based authentication TFPA scheme is given by a finite set \(\mathcal {U} \subseteq \mathbb {N}\) of users and a set of functionalities {Setup, Join, Issue, Prove, Verify} described as follows.

  • Setup. This algorithm derives global parameters param together with a master key \(\mathsf {mk}\), according to a security parameter \(\lambda \). We note: \( \mathtt {Setup} (1^\lambda ) \rightarrow (\mathsf {param}, \mathsf {mk}). \)

  • Registration: Join \(\leftrightarrow \) Issue. During the registration step, the user supplies a password \(pw \in \{0, 1\}^*\) (possibly with low entropy) and gets a token T. The token is recorded on the user’s side and the password pw is discarded. The issuer owns the master key \(\mathsf {mk}\), and might additionally use some user-specific auxiliary information \(info \in \{0, 1\}^*\) as input. The issuer outputs a user-specific value V, called the verifier, stored on a server. We note: \( T \leftarrow \mathtt {Join} (\mathsf {param}, i, pw) \leftrightarrow \mathtt {Issue} (\mathsf {param}, \mathsf {mk}, i, info) \rightarrow V. \)

  • Authentication: Prove \(\leftrightarrow \) Verify. On input a token T and a fresh password \(\tilde{pw}\), a user authenticates to a server. The latter knows the verifier V recorded during the registration, and outputs a decision \(dec \in \{\mathsf {accept}, \mathsf {reject}\}\). We note: \(\mathtt {Prove}\)(\(\mathsf {param}\), i, \(\tilde{pw}\), T)\(\leftrightarrow \mathtt {Verify}\)(\(\mathsf {param}\), i, V)\(\rightarrow dec\).

We assume that the registration protocol is carried out over a secure channel. We stress that the password is discarded after the registration. If the token is stolen (for instance on a mobile phone), the UF-pw security property below ensures that only guesses on-line are possible with the token. The password chosen by the user might depend on the information used to identify him. For instance, a 4 digits PIN on a mobile phone might be chosen by the user according to its mobile number (say the last 4 digits), the phone number being precisely the information used to enrol the user and to index the verifier. Our model takes into account such dependencies through the auxiliary information info.

Parameters and password entropy. A TFPA scheme is parametrized by three integers \(\lambda , \beta , \tau \in \mathbb {N}\). \(\lambda \) manages the length of the keys, as in standard cryptographic primitives. \(\beta \) manages the min-entropy of the password. \(\tau \) is a bound on the number of attempts to authenticate on behalf of a given user. An adversary could always try to guess the password on-line and brute-forcing the password takes \(2^\beta \) attempts on average. In practice, \(\tau \) is set according to \(\beta \). One usually sets \(\tau < \beta \) (such that \(\tau \ll 2^\beta \)). For instance, let us assume that a PIN number is composed of four uniform digits. The server usually aborts after \(\tau = 3 < \beta \approx 13\) attempts that failed.

Security properties for TFPA. Intuitively, we address two kinds of problems. From the authentication point of view, we want that only a registered user can authenticate to the server, knowing a valid (token, password) pair. We handle this with two unforgeability games UF-token and UF-pw. In each game, the adversary tries to authenticate knowing a factor among (password, token) and ignoring the other. From the password protection point of view, we do not want the password to be guessable, neither from an adaptive external adversary, nor from corrupted authorities. In the security game, Password-Leakage, the adversary tries to guess the password, knowing the server’s data (including the master key) but without knowing the client’s data.

Game-based definitions. Properties are expressed by games played between an adversary \(\mathtt {A}\) against a scheme \(\varPi \) and a challenger \(\mathtt {C}\). The adversary has access to a set of oracles, described below. The set \(\mathcal {L}\) records what leaks to \(\mathtt {A}\). The tables \(\mathsf {pw}\), \(\mathsf {client}\) and \(\mathsf {server}\) record respectively the password, data on the client’s side (aka the token) and data on the server’s database (aka the verifier).

  • Password sampling. First of all, each security game is carried out according to a set \(\mathcal {P}\) of passwords and a password distribution P with min-entropy \(\beta \). The challenger uses them to sample the passwords (if needed).

  • AddUser. A supplies (i, info, pw) where i is new. If \(pw \ne \bot \), the challenger adds \((i, \mathsf {pw})\) to \(\mathcal {L}\). If \(pw = \bot \), the challenger picks a random password in \(pw \leftarrow _P \mathcal {P}\) according to the distribution P. In both cases the challenger computes the token T and the verifier V from pw, info, \(\mathsf {mk}\), records \(\mathsf {client}[i] := T\), \(\mathsf {server}[i] := V\) and \(\mathsf {pw}[i] := pw\).

  • SendToIssuer. \(\mathtt {A}\) may interact with the issuer, and potentially deviate from the protocol during the registration. \(\mathtt {A}\) supplies (i, info). Values \(\mathsf {pw}[i]\) and \(\mathsf {client}[i]\) stay undefined. The challenger adds \((i, \mathsf {pw})\), \((i, \mathsf {client})\) to \(\mathcal {L}\).

  • UserData. The adversary might ask for the i-th user’s data: \(\mathsf {pw}[i]\), \(\mathsf {client}[i]\), or \(\mathsf {server}[i]\). The corresponding pair (i, table) is added to \(\mathcal {L}\), where \(table \in \) {\(\mathsf {pw}\), \(\mathsf {client}\), \(\mathsf {server}\)}.

  • \({\textsf {IssuerImpersonation: SendToUser}}_{issuer}\). The adversary might impersonate the issuer in front of a new user i (and deviate from the protocol). The challenger plays the role of the user i, records the corresponding \(\mathsf {pw}[i]\) and \(\mathsf {client}[i]\), and sets \(\mathsf {server}[i] := \bot \). The pair \((i, \mathsf {server})\) is added to \(\mathcal {L}\).

  • SendToServer. An adversary tries to authenticate on behalf of a user i of her choice. According to the functionality, the challenger accepts up to \(\tau \) attempts per registered user.

    The verification procedure enables authentication of registered users only. As a consequence, the challenger responds only if i has already been enrolled.

  • \({\textsf {ServerImpersonation: SendToUser}}_{server}\). The adversary might impersonate the server in front of a registered user i. There is no restriction on the number of attempts for this oracle.

UF: UnForgeability. In the unforgeability games, the adversary tries to authenticate to the challenger on behalf of an existing user. The adversary may attempt an authentication without a token (she might know the password of the target user, and data from other users) or without knowing a password (she might know the token of the target user, and data from other users). The first property prevents an adversary to authenticate itself without being registered. The second property prevents an adversary to authenticate itself if it stole the token. We stress that the adversary knows whether an authentication attempt is successful or not (Fig. 1).

  • Property UF-token. Given a scheme \(\varPi \), a probabilistic polynomial adversary \(\mathtt {A}\) and security parameters \(\lambda , \beta , \tau \in \mathbb {N}\), the probability of success in the \(\mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf{UF-token}}\) game is negligible as a function of \(\lambda \):

    $$ \Pr \left[ \mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf{UF-token}} (\lambda , \beta , \tau ) \Rightarrow 1 \right] < \mathsf {negl} (\lambda ). $$

  • Property UF-pw. Given a scheme \(\varPi \), a probabilistic polynomial adversary \(\mathtt {A}\) and security parameters \(\lambda , \beta , \tau \in \mathbb {N}\), the probability of success in the \(\mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf{UF-pw}}\) game is negligible as a function of \(\lambda \), up to on-line guesses:

    $$ \Pr \left[ \mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf{UF-pw}} (\lambda , \beta , \tau ) \Rightarrow 1 \right] < \tau /2^\beta + \mathsf {negl} (\lambda ). $$
Fig. 1.
figure 1

The unforgeability experiment

Full size image

Remarks. In the UF-pw game, the possibility to query \(\mathsf {server}[i^*]\) is disallowed, and it is inherent to the notion: from \(\mathsf {server}[i^*]\) and \(\mathsf {client}[i^*]\), an adversary could brute-force recover \(\mathsf {pin}[i^*]\). Moreover, we assume that the registration protocol is carried out over a secure channel; so the adversary has no access to a \(\texttt {SendToUser}_{issuer}\) oracle, neither to transcripts of registration sessions.

PL: Password Leakage. We do not want the issuer or the verifier to be able to recover the password. This point is not addressed by the UF games above. We formalize a game where the adversary knows the master key and the verifiers, but is not allowed to know the password nor the token for a target user i (it might know these data for other users). If it knew the token, it could brute-force recover the password (Fig. 2).

  • Property Password-Leakage. Given a scheme \(\varPi \), a probabilistic polynomial adversary \(\mathtt {A}\) and security parameters \(\lambda , \beta , \tau \in \mathbb {N}\), the probability of success in the \(\mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf {PL}}\) game is negligible as a function of \(\lambda \), up to a simple guess of the password:

    $$ \Pr \left[ \mathsf {Experiment}_{\varPi , \mathtt {A}}^{\mathsf {PL}} (\lambda , \beta , \tau ) \Rightarrow 1 \right] < 1/2^\beta + \mathsf {negl}(\lambda ). $$
Fig. 2.
figure 2

The password leakage experiment

Full size image

The non-interactive authentication setting. By non-interactive setting, we mean that the authentication procedure is the non-interactive signing of a random message. The message to be signed is fresh for each authentication. It might be a random challenge chosen by the verifier, or a hash value of a context-dependent message (time, verifier identity, etc.), determined by the protocol specification. In this setting, the \({\texttt {SendToUser}}_{server}\) oracle becomes a signature oracle and the SendToServer oracle becomes a verification oracle. According to the standard existential unforgeability notion for signatures [17], we allow the adversary to choose the message to be signed in the security experiment.

  • \({\textsf {SendToUser}}_{server}\). The adversary supplies (i, m), where i is a user, and m a message; and receives a signature \(\sigma \) on m on behalf of i.

  • SendToServer. The adversary supplies \((i, m, \sigma )\); and receives the decision of the verifier about the validity of the signature.

At the end of the game, there is no interaction with the challenger. The adversary eventually outputs a tuple \((i^*, m^*, \sigma ^*)\) and wins if the non-triviality conditions hold (\(\mathsf {server}[i^*] \ne \bot \), etc.), if \(m^*\) has not been queried to the signature oracle, and if \(\mathtt {Verify}\)(\(\mathsf {param}\), \(i^*\), \(\mathsf {server}[i^*]\), \(m^*\), \(\sigma ^*\)) \(=\) \(\mathsf {accept}\).

Local updates. We now discuss the possibility of password updates on the client’s side into our definition. May the user change its password and update its token accordingly without interaction with the server? In fact, this property is not contradictory with the notion. However, if such a procedure exists, the client cannot check if the token is correctly updated. By contradiction, he could carry out a verification protocol on its own, and therefore the adversary could try, given a token, to guess the password and check its guess. In practice, one can imagine that the old token is backed up and an authentication protocol is done with the new token. If successful, then the old token is removed. If not, the new token is removed and the old one is kept.

4 A Solution Based on Commitments

In this section, we give a simple solution that uses the standard notions of commitments and proofs of knowledge of committed values.

Commitments and ZK proofs. A commitment scheme Com is composed of a message space \(\mathcal {M}_\mathsf {C}\), a random value space \(\mathcal {R}_\mathsf {C}\), a commitment space \(\mathcal {C}_\mathsf {C}\), and a set of functionalities {\(\mathtt {Setup}\), \(\mathtt {Commit}\), \(\mathtt {Open}\)} as follows. On input a security parameter \(\lambda \in \mathbb {N}\), the setup procedure \(\mathtt {Setup}\) outputs a commitment key \(\mathsf {ck}\). The (deterministic) commitment procedure \(\mathtt {Commit}\) takes as input a commitment key \(\mathsf {ck}\), a message \(m \in \mathcal {M}_\mathsf {C}\) and a random value \(r \in \mathcal {R}_\mathsf {C}\), and outputs a committed value \(c \in \mathcal {C}_\mathsf {C}\). Given a commitment key \(\mathsf {ck}\) and a commitment c, the \(\mathtt {Open}\) procedure simply reveals a pair (m, r): everyone can check whether \(c = \mathtt {Commit} (\mathsf {ck}, m; r)\). A commitment scheme is binding if it is impossible to reveal a distinct pair \((m', r') \ne (m, r)\) such that \(c = \mathtt {Commit} (m'; r')\). It is hiding if c does not leak any information about m. Both security notions can be defined in a computational, statistical or perfect (information-theoretic) sense. In our constructions, we use standard ZK proofs of knowledge, known as \(\varSigma \)-protocols, and their standard transformation into signatures of knowledge [9] through the Fiat-Shamir heuristic [12]. A \(\varSigma \)-protocol is proof of knowledge that consists of three messages: a commitment message R, a random uniform challenge \(c \leftarrow \{0, 1\}^{\lambda _c}\) for some security parameter \(\lambda _c\), and a response s. The Fiat-Shamir heuristic makes this ZKPK non-interactive by generating the random challenge with a hash function. The resulting signature – denoted SoK – is as secure as the underlying \(\varSigma \)-protocol in the programmable random oracle model.

Description of the solution. Let Com be a computationally binding, statistically hiding commitment scheme, and \(\mathcal {P}\) be a set of passwords. Let \(\mathtt {H}_h : \mathcal {P} \rightarrow \mathcal {M}_\mathsf {C}\) be an injective encoding function from the passwords to the message space of the Com scheme. The Setup procedure picks a commitment key \(\mathsf {ck} \leftarrow \textsc {Com}.\mathtt {Setup} (1^\lambda )\) and returns ck as global parameter. The registration and authentication protocols are described Fig. 3.

Fig. 3.
figure 3

The two factor pw-com solution

Full size image

Security analysis. The pw-com solution is token-unforgeable in the programmable random oracle for \(\mathtt {H}_c\) if the SoK scheme is sound, zero-knowledge, and if the Com scheme is computationally binding and statistically hiding. It is password-unforgeable in the programmable random oracle for \(\mathtt {H}_c\) if the SoK scheme is sound, zero-knowledge, and if the Com scheme is computationally binding and statistically hiding. Finally, no information about the password is available from the issuer’s and server’s point of view, in the random oracle for \(\mathtt {H}_c\) under the zero-knowledge property of the SoK scheme and the statistical hiding property of the Com scheme. For the sake of reading, we use the following notations in the proofs: S is the signature oracle (instead of SendToUser \(_{server}\)), V the verification oracle (instead of SendToServer). Moreover we analyse the security for a single user, the extension to several users being straightforward.

Theorem 1

Let \(\mathtt {A}\) be an adversary against the \(\mathsf {UF}\)-\(\mathsf {token}\) property of the \(\mathsf {pw}\)-\(\mathsf {com}\) scheme with a single user, running in time at most t, making at most \(q_s\) signature queries, and at most \(q_v\) verification queries. Then:

Proof. Let \(T = t\) be the token of the user, pw its password, and \(V = C\) its verifier. Game \(\mathsf {G}_0\) is the token-unforgeability security experiment. The adversary gets pw and V but does not have access to T. In game \(\mathsf {G}_1\), the S oracle simulates the signature with the simulator of signature of knowledge, in the random oracle, without knowing the password, nor the token t, but knowing the verifier C. Games \(\mathsf {G}_0\) and \(\mathsf {G}_1\) are identical up to the simulation failure. Game \(\mathsf {G}_2 (\mathsf {ck}, pw, C)\) takes as input a commitment key \(\mathsf {ck}\), a random password \(pw \leftarrow \mathcal {P}\), and a random commitment \(C \leftarrow \mathcal {C}_\mathsf {C}\). During the registration step, \(\mathsf {G}_2\) sets \(T = \bot \) and \(V = C\). The token is not available to the simulation, but is not needed to simulate the signatures. From the statistical property of the commitment scheme, we know that for all pw and commitment C, there exists \(t \in \mathcal {R}_\mathsf {C}\) such that \(C = \mathtt {Commit} (\mathtt {H}_h (pw); t)\) with overwhelming probability. It remains to show that the probability of success of A in game \(\mathsf {G}_2\) is negligible. Let \(\mathtt {B}\) be the following reduction. B receives a challenge \(\mathsf {ck}\) for the computational binding property of the commitment scheme, picks \(pw \leftarrow _D \mathcal {P}\), \(C \leftarrow \mathcal {C}_\mathsf {C}\), and runs A simulating game \(\mathsf {G}_2 (\mathsf {ck}, pw, C)\). A eventually outputs a valid signature \(\sigma \) for some message m. If A is successful, then the soundness of the SoK scheme is broken. \(\square \)

Theorem 2

Let \(\mathtt {A}\) be an adversary against the \(\mathsf {UF}\)-\(\mathsf {pw}\) property of the \(\mathsf {pw}\)-\(\mathsf {com}\) scheme with a single user, running in time at most t, making at most \(q_h\) random oracle queries, \(q_s\) signature queries, and \(q_v < \tau \) verification queries. Then:

The proof is very similar to the proof of Theorem 1. However, we must take care of the password distribution, which is not assumed to induce a uniform distribution over the message space of the commitment scheme.

Proof. Let \(T = t\) be the token of the user, pw its password, and \(V = C\) its verifier. Game \(\mathsf {G}_0\) is the password-unforgeability security experiment. The adversary gets t but does not have access to pw nor to C. The only difference between \(\mathsf {G}_0\) and \(\mathsf {G}_1\) lies in the responses from the verification oracle for ‘fresh’ queries, i.e., message/signature pairs that do not correspond to a previous query/response pair from the signature oracle. When a valid fresh verification query is supplied, \(\mathsf {G}_1\) stops and returns 1. \(\mathsf {G}_0\) and \(\mathsf {G}_1\) returns 1 with the same probability, but by doing this we ensure that all fresh verification queries returns reject before the forgery. In game \(\mathsf {G}_2\), the signatures are simulated in the random oracle for \(\mathtt {H}_c\) with the simulator of the signature of knowledge. Game \(\mathsf {G}_3 (\mathsf {ck}, t, C)\) is a transition step. It takes as input a commitment key \(\mathsf {ck}\), a random value \(t \leftarrow \mathcal {R}_\mathsf {C}\), a commitment \(C := \mathtt {Commit} (\mathtt {H}_h (pw); t)\) for some password \(pw \leftarrow _D \mathcal {P}\), and sets \(T = t\) and \(V = C\). The password pw is not given, but is not needed for the simulation. Game \(\mathsf {G}_4 (\mathsf {ck}, t, C)\) is as game \(\mathsf {G}_3\), except that \(C \leftarrow \mathcal {C}_\mathsf {C}\). If \(2^\beta \ll |\mathcal {C}_\mathsf {C}|\), it is unlikely that (event E): there exists pw such that \(C = \mathtt {Commit} (\mathtt {H}_h (pw); t)\). The probability of E is at most \(2^\beta /|\mathcal {C}_\mathsf {C}|\), given that the encoding \(\mathtt {H}_h\) is injective. However, the commitment key, the token and the simulated signatures are identical in both games. The S oracle can still simulate signatures since the SoK simulator can simulate signatures even for false statements. A gets information about C only through the verification oracle. If E does not happen, a potential bias of \(1/2^\beta \) is introduced per verification query from \(\mathtt {A}\)’s point of view. This is because a negative response from the verification oracle reveals at most one bit of information about the password (recall that all responses from V are negative). So we bound the difference between \(\mathsf {G}_3\) and \(\mathsf {G}_4\) as follows: \(\Pr \left[ \mathtt {A}^{\mathsf {G}_3} \Rightarrow 1 \right] - \Pr \left[ \mathtt {A}^{\mathsf {G}_4} \Rightarrow 1 \right] \le q_v/2^\beta \cdot \left( 1 - 2^\beta /|\mathcal {C}_\mathsf {C}|\right) \). It remains to show that the probability of success of A in game \(\mathsf {G}_4\) is negligible. This is shown by reduction to the soundness of the SoK signature, as in Theorem 1. \(\square \)

Theorem 3

Let \(\mathtt {A}\) be an adversary against the \(\mathsf {PL}\) property of the \(\mathsf {pw}\)-\(\mathsf {com}\) scheme making at most \(q_h\) queries to the random oracle and \(q_s\) queries to the signature oracle. Then:

Proof. Game \(\mathsf {G}_0\) is the PL security game. \(\mathtt {A}\) eventually outputs \((i^*, pw^*)\) and wins if it correctly guesses the password. In game \(\mathsf {G}_1\), signatures are simulated as in Theorem 1. In game \(\mathsf {G}_2\), in the registration protocol, a random commitment \(C \leftarrow \mathcal {C}_\mathsf {C}\) is drawn, instead of computing C according to the user’s password. Thanks to the mask value t, the simulated C is statistically close from a real one, under the hiding property of the Com scheme. Finally, in game \(\mathsf {G}_2\), no password is used. The probability to win is then bound by the probability to guess a password. \(\square \)

A DL instantiation. Let \((p, \mathbb {G}, G)\) be a group of prime order. During the registration step, the client takes a password hash \(h := \mathtt {H}_h (pw)\), picks \(t \leftarrow \mathbb {Z}_p\), and sets \(C := [h] \cdot G + [t] \cdot H\). It stores t as token and sends C to the server which stores it as verifier. During the authentication step, the client takes a password hash \(\tilde{h} := \mathtt {H}_h (\tilde{pw})\), picks \(r_h, r_t \leftarrow \mathbb {Z}_p\), sets \(R := [r_h] \cdot G + [r_t] \cdot H\);, \(c := \mathtt {H}_c (R, \mathsf {m})\), \(s_h := r_h + c \cdot \tilde{h} \mod p\), and \(s_t := r_t + c \cdot t \mod p\). It sends \((c, s_h, s_t)\) to the server, which computes \(\tilde{R} := [s_h] \cdot G + [s_t] \cdot H - [c] \cdot C\), \(\tilde{c} := \mathtt {H}_c (\tilde{R}, \mathsf {m})\);, and checks \(c = \tilde{c}\).  For 128 bits of security, the user’s response \((c, s_h, s_t)\) takes 640 bits.

5 A Solution Based on Homomorphic Encryption

In this section, we give a construction based on a homomorphic encryption scheme over group of prime order, which includes local updates of the password.

Hash functions. A hash function H is given by two procedures {\(\mathtt {KeyGen}\), \(\mathtt {Eval}\)} as follows. On input a security parameter \(\lambda \), the KeyGen procedure outputs some public parameters. In case of keyed hash function, the procedure also outputs a random uniform evaluation key \(\mathsf {ek} \leftarrow \{0,1\}^\lambda \). On input a message \(m \in \{0, 1\}^{\ell (\lambda )}\) for some polynomial \(\ell \), the evaluation function Eval outputs a hash value in some space \(\mathcal {H}\). We need collision-resistant (unkeyed) hash functions and pseudo-random keyed hash functions. The collision-resistance requires that it should impossible to exhibit two distinct messages that share the same hash value. A keyed hash function is pseudo-random if a polynomial adversary cannot distinguish whether it interacts with a pseudo-random function or a truly random one.

Homomorphic Encryption. Our constructions make use of an encryption scheme that supports some homomorphic operation and its efficient iteration. By pure convention we use here the additive symbol. A homomorphic public key encryption scheme hom-pke is composed of a message space \(\mathcal {M}_\mathsf {E}\) supporting some operation \(+\), a ciphertext space \(\mathcal {C}_\mathsf {E}\), and a set of functionalities {\(\mathtt {KeyGen}\), \(\mathtt {Enc}\), \(\mathtt {Dec}\), \(\mathtt {Add}\), \(\mathtt {SMul}\)} as follows.

On input a security parameter \(\lambda \in \mathbb {N}\) and the particular message space \(\mathcal {M}_\mathsf {E}\), the key generation procedure KeyGen outputs a pair of public/private keys \((\mathsf {pk}, \mathsf {sk})\). The (probabilistic) encryption procedure Enc takes as input a public key pk and a message \(m \in \mathcal {M}_\mathsf {E}\), and outputs a ciphertext c. The (deterministic) decryption procedure takes as input a secret key sk and a ciphertext c, and outputs a message m. The homomorphic procedure takes as input a public key pk and two ciphertexts \(c_1, c_2\), and outputs a ciphertext \(c'\). The homomorphic operation Add is extended to an efficient scalar multiplication SMul which takes as input a public key pk, a ciphertext c and a scalar \(n \in \mathbb {N}\), \(n > 1\), and outputs a ciphertext \(c'\) such that for all \(m \in \mathcal {M}_\mathsf {E}\) we have: \( n \times m \leftarrow \mathtt {Dec} (\mathsf {sk}, \mathtt {SMul} (\mathsf {pk}, \mathtt {Enc} (\mathsf {pk}, m), n)). \) Sometimes we note \(c_1 \oplus c_2\) as a short-cut for \(\mathtt {Add} (\mathsf {pk}, c_1, c_2)\), and \([n] \cdot c\) for \(\mathtt {SMul} (\mathsf {pk}, c, n)\), the public key being clear from the context.

The one-wayness OW property states that it is impossible given a ciphertext to recover the underlying plaintext. The semantic security, or indistinguishability against chosen plaintext attacks IND-CPA, state that no information about the plaintext leak from the ciphertext. We also assume that ciphertexts produced by the homomorphic procedures are indistinguishable from those directly produced by the encryption procedure.

Description of the solution. The Setup procedure picks a prime order group \((p, \mathbb {G}, G)\) in additive notation, with null element \(\mathbf {0}\), and a master key \(\mathsf {mk} \leftarrow \{0, 1\}^\lambda \). Let hom-pke \(:=\) {KeyGen, Enc, Dec, Add, SMul} be an additively homomorphic encryption scheme over \(\mathcal {M}_\mathsf {E} := (p, \mathbb {G}, G)\). Let \(\mathtt {H}_u:\{0, 1\}^\lambda \times \{0, 1\}^* \rightarrow \mathbb {Z}_p\) be a pseudo-random hash function, \(\mathtt {H}_c: \{0, 1\}^\lambda \times {\mathcal {C}_\mathsf {E}}^2 \times \{0, 1\}^\ell \rightarrow \{0, 1\}^\lambda \) a hash function (for a message length \(\ell \)), \(\mathtt {H}_v: \mathcal {C}_\mathsf {E} \rightarrow \{0, 1\}^\lambda \) another hash function, and \(\mathtt {H}_h:\mathcal {P} \rightarrow \mathbb {Z}_p^*\) an injective encoding function of the passwords.

The Setup procedure returns the global parameters \(\mathsf {param} := (p, \mathbb {G}, G)\). The registration and authentication protocols are described Fig. 4. In the registration step, the user has got a password pw, the server knows the master key \(\mathsf {mk}\) and some user information info, and both know the parameters \((p, \mathbb {G}, G)\). In the authentication step, the user supplies a fresh \(\tilde{pw}\) value and owns a token \((\mathsf {pk}_1, \mathsf {pk}_2, B, C)\), the server knows the verifier \((H, \mathsf {sk}_1, \mathsf {sk}_2)\), and both formerly agreed on a message \(\mathsf {m}\) to be signed.

Local updates. Local updates on the client’s side are possible in the pw-hom construction: (i) ask the user for \(pw_\mathsf {old}\), \(pw_\mathsf {new}\); set \(h_\mathsf {old} := \mathtt {H}_h (pw_\mathsf {old})\), \(h_\mathsf {new} := \mathtt {H}_h (pw_\mathsf {new})\); (ii) given \(T := (\mathsf {pk}_1, \mathsf {pk}_2, B, C)\), update \(C \leftarrow \mathtt {SMul} (\mathsf {pk}_2, C, h_\mathsf {new} \cdot (h_\mathsf {old})^{-1}\mod p).\)

Fig. 4.
figure 4

The pw-hom two factor solution

Full size image

Security analysis. The pw-hom scheme is UF-pw secure under the semantic security of hom-pke, the pseudo-randomness of \(\mathtt {H}_u\) and the collision-resistance of \(\mathtt {H}_v\) in the random oracle for \(\mathtt {H}_c\). It is (weakly) UF-token secure under the one-wayness of hom-pke, the pseudo-randomness of \(\mathtt {H}_u\) and the collision-resistance of \(\mathtt {H}_v\) in the random oracle for \(\mathtt {H}_c\). It is \(\mathsf {PL}\) resistant in the random oracle for \(\mathtt {H}_c\).

Theorem 4

Let \(\mathtt {A}\) be an adversary against the \(\mathsf {UF}\)-\(\mathsf {pw}\) property of the \(\mathsf {pw}\)-\(\mathsf {hom}\) scheme with a single user, running in time at most t, making at most \(q_h\) random oracle queries, \(q_s\) signature queries and \(q_v < \tau \) verification queries. Then:

Note on the bound. We are not able to prove that the bound is negligible beyond \(\tau /2^\beta \), but only beyond \(\tau ^2/2^\beta \). This means that one should set \(\tau ^2 < \beta \) rather than \(\tau < \beta \) in practice. If the encryption scheme is one-way under a computational problem, this bound could be taken back to \(\tau /2^\beta \) at the cost of an interactive Gap assumption [32], according to which the adversary has access to an oracle for the corresponding decision problem.

Proof. Let \(T = (\mathsf {pk}_1, \mathsf {pk}_2, B, C)\) be the token of the user, pw its password, and \(V = (H, \mathsf {sk}_1, \mathsf {sk}_2)\) its verifier. Game \(\mathsf {G}_0\) is the UF-pw security experiment. The adversary gets T but does not have access to pw nor to V. In game \(\mathsf {G}_1\), the S oracle simulates the signatures, in the random oracle, without knowing the password, nor the ciphertext C, but knowing the ciphertext B and the public encryption keys. During the n-th query, on input a message \(m_n\), game \(\mathsf {G}_1\) generates the signature as follows: pick \(s_n \leftarrow \mathbb {Z}_p\); \(c_n \leftarrow \{0, 1\}^\lambda \); \(L_n \leftarrow \mathbb {G}\), set \(F_n \leftarrow \mathtt {Enc} (\mathsf {pk}_2, L_n)\); \(E_n \leftarrow \mathtt {Enc} (\mathsf {pk}_1, [-c_n] \cdot L_n) \oplus \mathtt {SMul} (\mathsf {pk}_1, B, s_n)\), if \(\mathtt {H}_c (E_n, F_n, m_n) \ne \bot \), abort, otherwise program \(\mathtt {H}_c (E_n, F_n, m_n) := c_n\), return \(\sigma := (E_n, F_n, s_n)\). Game \(\mathsf {G}_2\) is game \(\mathsf {G}_1\), except that the master key \(\mathsf {mk}\) is dropped and \(\mathsf {G}_2\) has an oracle access to \(\mathtt {H}_u (\mathsf {mk}, \cdot )\). In game \(\mathsf {G}_3\), the oracle access to \(\mathtt {H}_u\) is replaced by an oracle which draws random values in \(\mathbb {Z}_p^*\). The success probability of a distinguisher between \(\mathsf {G}_2\) and \(\mathsf {G}_3\) is bound by the advantage to break the PRF property of \(\mathtt {H}_u\) within the same time. In game \(\mathsf {G}_3\), A supplies \(q_v + 1\) message/signature pairs, either to the verification oracle, or at the end of the game. Game \(\mathsf {G}_4\) guesses the first query \(\mathsf {j} \in [1, q_v + 1]\) where A gives a valid ‘fresh’ message/signature pair. For all \(j < \mathsf {j}\), the verification oracle returns 0. At the \(\mathsf {j}\)-th query (or at the end of the game if \(\mathsf {j} = q_v + 1\)), game \(\mathsf {G}_4\) returns 1 and stops. The oracle V no longer needs the secret keys, at the price of a security loss linear in the number of verification queries. Game \(\mathsf {G}_5 (\mathsf {pk}_1, B, \mathsf {pk}_2, C)\) is a transition step. It takes as input two public keys \(\mathsf {pk}_1\), \(\mathsf {pk}_2\), a ciphertext B of a group element \([k] \cdot G\) under \(\mathsf {pk}_1\), and a ciphertext C of a group element \([\mathtt {H}_h (pw) \cdot k] \cdot G\) under \(\mathsf {pk}_2\) for some \(pw \leftarrow _P \mathcal {P}\) and \(k \leftarrow \mathbb {Z}_p\). The password pw is not given, but the simulation of signatures is not affected. Likewise, the secret keys are not given, but they are not needed in the simulation of the verification oracle. In game \(\mathsf {G}_6\), a random exponent \(h \leftarrow \mathbb {Z}_p^*\) is taken instead of computing h from the password. With probability at most \(2^\beta /p\), there exists \(pw \in \mathcal {P}\) such that \(h = \mathtt {H}_h (pw)\). Otherwise, the distribution of C is not as in the real protocol. Under the semantic security of hom-pke, C does not leak information about the password. However the verification queries might leak information about the password. We bound the difference between \(\mathsf {G}_5\) and \(\mathsf {G}_6\) as follows: It remains to bound the probability of success of A is game \(\mathsf {G}_6\). We adapt the standard forking lemma techniques [1, 34] to our case, which do not involve difficulties. For the sake of place, we postpone it to the full version of our paper. \(\square \)

Theorem 5

Let \(\mathtt {A}\) be an adversary against the \(\mathsf {UF}\)-\(\mathsf {token}\) property of the \(\mathsf {pw}\)-\(\mathsf {hom}\) scheme with a single user, running in time at most t, making at most \(q_h\) random oracle queries, \(q_s\) signature queries and \(q_v\) verification queries. Then:

Proof. Let \(T = (\mathsf {pk}_1, \mathsf {pk}_2, B, C)\) be the token of the user, pw its password, and \(V = (H, \mathsf {sk}_1, \mathsf {sk}_2)\) its verifier. Game \(\mathsf {G}_0\) is the token-unforgeability security experiment. The adversary gets pw but does not have access to T nor V. Games \(\mathsf {G}_1\) to \(\mathsf {G}_4\) are as in Theorem 4. Game \(\mathsf {G}_5 (\mathsf {pk}, \mathsf {B})\) takes as input a public key \(\mathsf {pk}\), and the ciphertext \(\mathsf {B}\) of \([k] \cdot G\) for some uniform \(k \leftarrow \mathbb {Z}_p\). \(\mathsf {G}_4\) sets \(\mathsf {pk}_1 := \mathsf {pk}\) and \(B := \mathsf {B}\). The distributions of B in \(\mathsf {G}_4\) and \(\mathsf {G}_5\) are identical. The ciphertext C is not computed and is never used. It remains to show that the probability of success of A in game \(\mathsf {G}_5\) is negligible. This is done as in Theorem 4, under the one-wayness of hom-pke and the collision-resistance of \(\mathtt {H}_v\). \(\square \)

Theorem 6

Given an adversary \(\mathtt {A}\) making at most \(q_h\) requests to the random oracle and \(q_s\) requests to the signature oracle, we have:

Proof. The proof is fairly straightforward, as in the pw-com scheme. \(\square \)

Security in presence of local updates. We add an oracle to the security game, to catch the possibility of local updates. The adversary supplies \((i, pw')\), for i such that \(\mathsf {pw}[i]\) and \(\mathsf {client}[i]\) are well-defined. If \(pw' = \bot \), \(\mathtt {C}\) picks a new password \(pw' \leftarrow _P \mathcal {P}\) at random, according to the password distribution P. In both cases, \(\mathtt {C}\) updates the tables. If UserData has already been called on \(\mathsf {pw}[i]\) (or \(\mathsf {client}[i]\)), \(\mathtt {C}\) sends the corresponding updated value to \(\mathtt {A}\). This oracle has an effect during the game \(\mathsf {G}_6\) in the UF-pw proof. The ciphertext C is replaced by another ciphertext \(C = \mathtt {SMul} (\mathsf {pk}_2, C, t)\) for some uniform \(t \leftarrow \mathbb {Z}_p^*\). The value t is not distributed as in the real protocol, but the simulation remain correct under the semantic security of the encryption scheme.

A concrete instantiation with ElGamal. The black-box construction above might be instantiated with the ElGamal encryption scheme [14]. Let ElG be the following scheme. The key generation procedure takes as input a prime order group \((p, \mathbb {G}, G)\), picks a secret key \(\mathsf {sk} \leftarrow \mathbb {Z}_p^*\), computes the public key \(\mathsf {pk} := [\mathsf {sk}] \cdot G\), and returns the key pair \((\mathsf {pk}, \mathsf {sk}) \in \mathbb {G} \times \mathbb {Z}_p^*\). Then encryption procedure takes as input an element \(M \in \mathbb {G}\) and a public key pk, picks \(r \leftarrow \mathbb {Z}_p\) and outputs a ciphertext \(C([r] \cdot G, M + [r] \cdot \mathsf {pk}) \in \mathbb {G}^2\). The decryption step takes as input a ciphertext \((C_1, C_2)\) and a secret key sk, and outputs \(M = C_2 - [\mathsf {sk}] \cdot C_1\). The one-wayness of the ElG scheme is equivalent to the CDH problem and its semantic security is equivalent to the DDH problem. When instantiated with the ElG scheme, a token is given by 6 group elements, a verifier by two scalars and a hash, and a signature by 4 elements plus a scalar. According to the state of the art (see for instance [11]), for 100 bits of security, the ElG scheme might be instantiated with an elliptic curve over a prime field \(\mathbb {F}_q\) with a 200-bits prime q. As a result, for 128 bits of security, a token needs \(\approx \)3k bits to be stored without compression (and half this value with compression), a verifier takes \(\approx \)640 bits, and a signature \(\approx \)2300 bits without compression (\(\approx \)1300 with compression).