How to do stateless (session-less) & cookie-less authentication?

Bob uses a web application in order to achieve something. And:

• His browser is on diet, therefore it does not support cookies.
• The web application is a popular one, it deals with a lot of users at a given moment - it has to scale well. As long as keeping session would impose a limit to the number of simultaneous connections, and, of course, will bring a non-negligible performance penalty, we might like to have a session-less system :)

Some important notes:

• we do have transport security (HTTPS and its best friends);
• behind the curtains, the web application delegates a lot of operations to external services, on current user's behalf (those systems do recognize Bob as one of their users) - this means that we have to forward them Bob's credentials.

Now, how do we authenticate Bob (on each and every request)? Which would be a reasonable way to implement such a thing?

• playing tennis with the credentials via HTML form hidden fields... the ball contains the credentials (username & password) and the two rackets are the browser and the web application respectively. In other words, we may transport data back and forth via form fields instead of via cookies. At each web request, the browser posts the credentials. Though, in the case of a single-page application, this may look like playing squash against a rubber wall, instead of playing tennis, as the web form containing the credentials might be kept alive the entire lifetime of the web page (and the server will be configured not to offer the credentials back).
• storing the username & the password in the context of the page - JavaScript variables etc. Single-page required here, IMHO.
• encrypted token - based authentication. In this case, the log-in action would result in the generation of an encrypted security token (username + password + something else). This token would be served back to the client and the upcoming requests will be accompanied by the token. Does this make sense? We already have HTTPS...
• others...
• last resort: do not do this, store credentials in the session! Session is good. With or without cookies.

Does any web / security concern come into your mind, regarding any of the previously described ideas? For example,

• time-outing - we may keep a timestamp, along with the credentials (time-stamp = the time Bob entered his credentials). E.g. when NOW - timestamp > threshold, we might deny the request.
• Cross-site scripting protection - should not be different in any way, right?

Thank you a lot for taking the time to reading this :)

Ah, I love these questions - maintaining a session without a session.

I've seen multiple ways to do this during my stints during application assessments. One of the popular ways is the playing tennis way that you mentioned - sending the username and password in every request to authenticate the user. This, in my opinion, is unsafe, especially if the application isn't single page. It is also not scalable, especially if you want to add authorization to your app in addition to authentication in the future (although I guess you could build something based on logins too)

One popular, although not completely stateless mechanism (assuming you have JavaScript execution) is to embed the session cookie in the JavaScript. The security guy in me is screaming at this, but it could actually work - every request has a X-Authentication-Token header or something like that, and you map that to a database, file-store in memory, etc. on the backend to validate the user. This token can have a timeout of whatever time you specified, and if it times out, the user has to log in again. It's fairly scalable - if you store it in a database, its one SQL statement executed, and with the correct indexes, it should take very little time to execute, even with multiple simultaneous users. Load testing here would definitely help though. If I read the question correctly, this would be your encrypted token mechanism - although, I would strongly suggest that you use a cryptographically random token of say 32 characters, versus using a combination of username + password + whatever else - this way, it stays unpredictable, but you can still associate it with the user ID or some such thing.

Whichever you do end up using, ensure it is sent to you safely. HTTPS protects you across the wire, but it doesn't protect you if you leak the session token via the URL (or worse, credentials via the URL). I would recommend using a header, or if that's not feasible, sending the token via a POST request every time (this would mean a hidden form field on the user's browser.) The latter approach of using a POST request should use CSRF defenses, just in case, though I suspect using the token itself might be some sort of a CSRF defense.

Last, but not the least, make sure you have some mechanism in the backend to purge expired tokens. This has been the bane of many applications in the past - a rapidly growing database of authentication tokens which never seems to go away. If you need to support multiple user logins, make sure you either limit the number, or have a shorter time limit on each token. As I said before, load testing may be the answer to this.

There are some other security concerns that I can think of, but they are too broad to be addressed at this stage - if you keep all the use (and abuse) cases in mind, you should probably be able to do a fairly good implementation of this system.