A protocol answering the usability and scalability issues

A major observation that substantially improves the protocol is that each user typically uses a limited set of computers, and that it is unlikely that a dictionary attack would be mounted against this user’s account from one of these computers. This observation can be used to answer the scalability and usability issues, while reducing security by only a negligible amount. Another helpful observation is that it would be hard for the adversary to attack accounts even if it is required to answer RTTs for only a fraction of its login attempts (and we show below how to do this without running into the problem pointed out in the comment above). This enables a great improvement in the scalability of the system.

The protocol assumes that the server has a reliable way of identifying computers. For example, in a web based system the server can identify a web browser using cookies. Other identification measures could be, for example, based on network addresses or special client programs used by the user. To simplify the exposition we assume that the login processuses a web browser, and that cookies are enabled. Our protocol can handle cookie theft, as we describe below.

User login protocol

Initialization: Once the user has successfully logged into an account, the server places in the user’s computer a cookie that contains an authenticated record of the username, and possibly an expiration date. (“Authenticated” means that no party except for the server is able to change the cookie data without being detected by the server. This can be ensured, for example, by adding a MAC that is computed using a key known only to the server. Cookies of this type can be stored in several computers, as long as each of them was used by the user.


  1. If the cookie is correctly authenticated and has not yet expired, and the user identification record stored in the cookie agrees with the entered username, then the user is granted access to the server.
  2. Otherwise (there is no cookie, or the cookie is not authenticated, or the user identification in the cookie does not agree with the entered username) the server generates an RTT and sends it to the user. The useris granted access to the server only if  he answers the RTT correctly.
  1. With probability p (where 0 < p <=1 is a system parameter, say p = 0:05), the user is asked to answer an RTT. When his answer is received he is denied access to the server, regardless of whether it is correct or not.
  2. With probability 1- p, the user is immediately denied access to the server.

This is the login protocol


The user is experiencing almost the same interaction as in the original login protocol (that uses no RTTs). The only difference is that he is required to pass an RTT in two instances (1) when he tries to login from a new computer for the first time, and (2) when he enters a wrong password (with probability p). We assume that most users are likely to use a small set of computers to access their accounts, and use other computers very in frequently (say,while traveling without a laptop). We also have evidence, from the use of RTTs in Yahoo!, Alta Vista and Paypal,that users are willing to answer RTTs if they are not asked to do so very frequently. Based on these observations we argue that the suggested protocol could be implemented without substantially downgrading the usability of the login system.


The main difference in the operation of the server, compared to a login protocol that does not use RTTs, is that it has to generate RTTs whenever they are required by the protocol. To simplify the analysis assume that most users use a small set of computers, and very seldom use a computer that they haven’t used before. We can therefore estimate that the server is required to generate RTTs only for a fraction p of the unsuccessful login attempts. Thisis a great improvement compared to the basic protocol, which requires the server to generate an RTT for every login attempt. Note that the overhead decreases as p is set to a smaller value. As for the cost of adding the new protocol to an existing system, note that no changes need to be made to the existing procedure, where the authentication module receives a username/password pair and decides whether they correspond to a legitimate user. The new protocol can use this procedure as a subroutine, together with additional code that decides whether to require the user to pass an RTT, and whether to accept the user as legitimate.

Tags : , , , , , , , , ,

If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.

Leave Comment