Generating cryptographically secure authentication tokens

Background:

This is really a general best-practices question, but some background about the specific situation might be helpful:

We are developing a "connected" application for the iPhone. It will communicate with the backend application via REST services. In order to not have to prompt the user for a username and password every time they launch the application, we will expose a "Login" service that validates their username and password on initial launch and returns an authentication token that can be used for future web service requests for real data. The token may have an expiration time after which we'll ask them to re-authenticate with their username/password.

The Question:

What are the best practices for generating this sort of token to be used for authentication?

For example, we could...

• Hash (SHA-256, etc) a random string and store it in the database for the given user along with an expiration date. Do a simple lookup of the token on subsequent requests to make sure it matches.
• Encrypte the user id and some additional information (timestamp, etc) with a secret key. Decrypt the token on subsequent requests to make sure it was issued by us.

This feels like it must be a solved problem.

Based on the feedback from the other answers to this question, additional research, and offline discussions, here is what we ended up doing...

It was pointed out pretty quickly that the interaction model here is essentially exactly the same as the model used by Forms Authentication in ASP.NET when a "remember me" checkbox is checked. It's just not a web browser making the HTTP requests. Our "ticket" is equivilant to the cookie that Forms Authentication sets. Forms Authentication uses essentially an "encrypt some data with a secret key" approach by default.

In our login web service, we use this code to create a ticket:

string[] userData = new string[4];

// fill the userData array with the information we need for subsequent requests
userData[0] = ...; // data we need
userData[1] = ...; // other data, etc

// create a Forms Auth ticket with the username and the user data. 
FormsAuthenticationTicket formsTicket = new FormsAuthenticationTicket(
    1,
    username,
    DateTime.Now,
    DateTime.Now.AddMinutes(DefaultTimeout),
    true,
    string.Join(UserDataDelimiter, userData)
    );

// encrypt the ticket
string encryptedTicket = FormsAuthentication.Encrypt(formsTicket);

Then we have an operation behavior attribute for the WCF services that adds an IParameterInspector that checks for a valid ticket in the HTTP headers for the request. Developers put this operation behavior attribute on operations that require authentication. Here is how that code parses the ticket:

// get the Forms Auth ticket object back from the encrypted Ticket
FormsAuthenticationTicket formsTicket = FormsAuthentication.Decrypt(encryptedTicket);

// split the user data back apart
string[] userData = formsTicket.UserData.Split(new string[] { UserDataDelimiter }, StringSplitOptions.None);

// verify that the username in the ticket matches the username that was sent with the request
if (formsTicket.Name == expectedUsername)
{
    // ticket is valid
    ...
}

Building your own authentication system is always a "worst practice". That's the kind of thing best left to professionals who specialize in authentication systems.

If you're bent on building your own "expiring ticket from a login service" architecture rather than re-using an existing one, it's probably a good idea to at least familiarize yourself with the issues that drove the design of similar systems, like Kerberos. A gentle introduction is here:

http://web.mit.edu/kerberos/dialogue.html

It would also be a good idea to take a look at what security holes have been found in Kerberos (and similar systems) over the last 20 years and make sure you don't replicate them. Kerberos was built by security experts and carefully reviewed for decades, and still serious algorithmic flaws are being found in it, like this one:

http://web.mit.edu/kerberos/www/advisories/MITKRB5-SA-2003-004-krb4.txt

It's a lot better to learn from their mistakes than your own.

Amazon.com uses a HMAC SHA-1 message token to authenticate and authorize requests. They use this for a fairly large commercial service, so I'd be liable to trust their engineering decisions. Google publishes the OpenSocial API which is somewhat similar. Based on Google and Amazon.com using similar and openly published approaches to securing web requests, I suspect these are probably good ways to go.

Either of the two answers you've provided will suffice. You may find frameworks out there that do this for you, but the truth is it's not that hard to build. (Every company I've worked for has rolled their own.) The choice of database-stored tokens versus encrypted data "cookies" is an architectural decision -- do you want to incur a database lookup on every page view, or would you rather chew up CPU with cookie decryption? In most applications, using encrypted cookies provides a performance win at scale (if that's a concern). Otherwise it's just a matter of taste.

Since you're using WCF, you have a variety of options if using CFNetwork -- for instance NTLM or Digest Authentication:

http://developer.apple.com/documentation/Networking/Conceptual/CFNetwork/Concepts/Concepts.html#//apple_ref/doc/uid/TP30001132-CH4-SW7

I know this doesn't answer your specific question, but I have also been faced with this problem (iPhone - Tomcat) and decided to use the authentication services on the web server as much as possible. There's no significant penalty for including the authentication information with each request in most cases. A quick Google turns up lots of blog posts about WCF and RESTful services (and some related questions on StackOverflow).

Hope this helps!

You should implement:

1. OAuth2 Implicit Grant - for third-party applications https://www.rfc-editor.org/rfc/rfc6749#section-1.3.2
2. OAuth2 Resource Owner Password Credentials — for your own mobile application https://www.rfc-editor.org/rfc/rfc6749#section-1.3.3

which are exactly the workflows, from OAuth2, that you are looking for. Do not reinvent the wheel.

This simply sounds like a session identifier with a long expiration time. The same principles used for this in web applications could apply here.

Rather than encoding information, session identifiers are randomly chosen from a very large space (128 bits). The server keeps a record associating the session identifier with the user and other desired information such as expiration time. The client presents the session identifier over a secure channel with each request.

Security relies on the unpredictability of the session identifiers. Generate them with a cryptographic RNG, from a very large space.