The main feature of the protocol that is relevant for the security analysis is that for a p fraction of the incorrect passwords, as well as for the correct password, the attacker must solve an RTT before it receives a yes/no answer that distinguishes the correct password from the incorrect ones. Suppose that the set of all passwords includes N passwords. The attacker can identify, without answering any RTT, that the correct password is a member of a subset of size p(N ¡ 1) + 1 ¼ pN of the passwords – these are the passwords for which it does not receive an immediate “reject” answer but is rather asked to solve an RTT. Given that the implementation requirement is satisfied, there is only one way that the attacker can receive additional information about the passwords – by choosing a password value that it wants to verify and paying with an “RTT solution” in order to learn whether it is the correct value of the password. Let us assume for simplicity that all password values have the same probability of being the correct password. (This is the case if passwords are chosen at random by the server. Even if the passwords are chosen by the user we can limit P in our analysis to the set of passwords that occur with high probability, and assume that the password is chosen among them with uniform probability. The analysis for the case of a non-uniform probability distribution of passwords is similar.) We can model the attacker as playing the following game: it receives pN identical envelopes,
and it knows that a winning ticket is hidden in exactly one of them, chosen uniformly at random. In order to open an envelope it has to pay one coin (i.e. RTT solution). Its goal is to minimize its expected payment until it finds the winning ticket. The analysis of this game is simple. The expected number of coins that have to be paid (i.e. RTTs that have to be solved) is pN=2. If the attacker pays c coins (i.e. solves c RTTs), it finds the winning ticket (password) with probability c=(pN).
Subscribe to email feed
