RESTful authentication - resulting poor performance on high load?

Question

For a RESTful web service we say that that the server shouldn't store any state. Now for every request the 'user' must be authenticated and must have an authorization for the action(s) he/she wishes to carry out.

Now every request will contain authorization data for that user. Here are my confusions:

Assuming there is a login and password field on the home-page. The user enters the username/password which is sent back to the server, user verified and then 'some token' is returned. Now this token is sent to the server on every request. Question(s):

• Does the backend DB need to have a separate table to store these tokens indexed by username?
• Assuming the token is stored in a DB then every request needs to make a DB call. Doesn't that make the DB server a bottleneck in times of high load?
• If the token is not really stored in the DB what is the best 'restful' place of storing it?
• Having sessions is probably NOT restful, but then I fail to see how restful authentication/authorization scale up (w.r.t. the above points)?
• If it's NOT a token then does the username/password be need to be sent back-n-forth? (sounds like a bad idea :)

I may be misunderstanding the concept of RESTful authentication/authorization. But is this really the case that for every http request the 'service' needs to make a trip to the DB to verify the credentials? Is there something that can shortcut the process and still hold true to restful principles? I could think of having a cache that stores the details and in case of server-restart it just makes the trip to the DB. That is just a performance benefit that could complicate the system (maybe worth it, don't know). Is this the only solution?

So from a theoretical/conceptual standpoint of REST (not necessary implementation) how is this issue handled (if at all it is an issue)? How have you in your professional experience handled this issue and how Restful was the approach?

We are working on a Restlet+J2EE+MySQL Restful web service and I had this question pop up but no satisfactory answers (Google, Stackoverflow etc.,) I'm aware of HTTP's Basic and Digest authorization, but I'm not familiar with the internals of storage/retrieval as per the above explanation.

Benedic

the general guideline: the less you use the disk/database the higher load the application can achieve. – Moyna

Answer 1

The spirit of REST is statelessness. This does not mean that client state cannot be persisted by a service, but in practice it does mean that client state held in memory by a server is generally a bad thing.

Instead of keeping authentication data in memory, or going to the DB for verification every time, what you can do is keep a function in memory (i.e., code) that is used to crypt/decrypt user information. This is a technique that is also suggested by:

What should I store in cookies to implement "Remember me" during user login

So, for example, what you would do is the following:

1. When a client first contacts the service, it has no cookie.
2. You issue a cookie that contains user info and "sign" it using your function (which all servers, running your code, can do)
3. When the client contacts the service again, you check if it has a cookie; if not, repeat (2).
4. However, if it does have a cookie, you attempt to decrypt (again, using your single function which is replicated across your infrastructure) and verify that you can unwrap and digest that user ID info.
5. This verifies the user and gives you identity info, all without going to the DB more times than is necessary. And it's RESTful.

Keep in mind that this "function" I describe is not a novel thing - it's a standard secure hash, but one that is based off a unique private key that only your collective servers know about. And you can rotate such a key, etc. as needed.

Bagman

@Bagman : Good point. I was thinking about the same 'concept' but couldn't put it so lucidly. So if that solves for authentication, could the same technique be 'extrapolated' in a sense to serve for authorization too? This is in sense the concept of 'business rules' which are persisted in the DB - I am not sure if it'd be a good thing to do the same for authorization. Ideas? – Benedic

@Nupul: In your "encrypted cookie value", you could store anything you want -- username, ID, auth info (role), etc. So yes, I think it's possible; depends to what extent auth info is data driven (in which case, looking up in the DB is useful). BTW, keep in mind that with the whole cookie thing, it is important to look at the issue of expiration; users that delete their account for example, should have their cookies removed. – Bagman

@kvista: Nice point about the deletion. In the case of our system, the user can't delete the account but the sysadmin can - by going to the DB :) Say I delete the account at time = t and the cookie was to expire at t+5, but the user whose account is now deleted tries to access the system with the 'cookie' at t+2 - then what? Should we rely on foreign key constraints failing?? Some may not! – Benedic

@Nupal: I think you need to m general decision about whether you will be optimizing authentication and authorization or not. Your original question was about whether there's a "shortcut" possible, outside of verifying credentials every time. That's a fair question. But let's first keep in mind that we've made the decision to that, we've made the decision to optimize. In that case, you have a few options. First, it's likely you'll want to rotate the decryption function. However, for deletes prior to rotation, you can probably maintain a blacklist in memory of users to disallow. More below – Bagman

@Nupal (contd): Personally, I don't like the blacklist idea as a general rule; my suggestion assumed the common case on the Web -- deletions are very infrequent and can be user-driven even in the few times they are needed (in which you can expire the cookie manually). Another option is to expire cookies after 30 min of inactivity, which means an admin can delete a user anytime and the user will be disallowed entry "next time" (after any current session is idle 30 min). This may be permissible for your type of app. It really depends - but keep in mind there's complexity cost to optimization. – Bagman

Agreed! It was just a corner case that instantly cropped up. Thanks for the answers! Really helpful viewpoints there. – Benedic

The problem with this approach is the vulnerability to "replay attacks." While there are additional layers of restive hack one can layer atop session authentication (e.g., expiration time for credentials), all of these are essentially stop-gaps to correct the inherent shortcoming of RESTful API. – Estovers

Answer 2

You only verify the credentials (e.g. username/password) at the time of login. When the user successfully logs in, you send them a cookie containing an unguessable "session ID". This session ID becomes the token which allows further access after credentials have been checked. The server application verifies the token by finding it in some in-memory data structure. The tokens expire after some reasonable amount of time, to prevent exhaustion of memory. The tokens are explicitly removed from the in-memory store if the user explicitly logs off (pressed the 'logoff' button).

It is important to use https when sending and receiving the token -- otherwise sniffing the token allows a hacker to "hijack the session." In other words, use https for the entire application workflow from login to logout.

Estovers

@Health :Will this strategy survive a server restart?? Won't the in-memory data structure need to be also stored on persistent storage (back to square 1)? Isn't then effectively just a cache that I mentioned? – Benedic

So it's just a regular user session, using a JSESSIONID cookie? Maybe the OP figured this is a form of state and as such doesn't belong in a RESTful architecture? – Kitts

No it won't survive a restart, unless you persist it around the restart. One way you could handle this is not worry about it, don't restart the server often, and require that users log in again rather than continuing the session across a restart. – Estovers

@Kitts -- If you want to require authenticated users, and you don't want to re-authenticate every request, how are you going to accomplish that with zero state? The OP's problem is he thinks RESTful is his priority and also maintaining session state is his priority. – Estovers

sure you can survive the restart, keep a thread (or few) persisting the state on the background, w/ an explicit persist during the session unload; tomcat supports sessions load/unload by default but that excludes server crash. – Moyna

Answer 3

RESTful services are supposed to be stateless, so yes a client does need to provide authentication credentials every time it calls a RESTful service.

There is no real benefit to replacing username/password with some kind of hash or token or session ID. All are just different forms of authentication that must be validated against some bit of data in persistent storage. The drawback of sessions and tokens is that they violate the statelessness requirement.

If database performance is an issue then use memcached or some other high-performance data cache. You'll probably find that ALL of your database access benefits from this, not just retrieving auth credentials.

Finally, there's no problem with sending username/password every time as long as you're doing it over HTTPS. Never, ever send important auth credentials over plain text HTTP.

Quiver

There most certainly is a disadvantage to sending U/P every time: the client must keep it around rather than being able to discard it as soon as it is passed to the server, making the client less secure. In some schemes, this can be much less secure. Another disadvantage is speed: verifying a token or cookie can be faster than verifying U/P, especially if you've properly encrypted your password using a password hash like bcrypt. – Unexampled