Q:

Securing Authentication Tokens Stored in the Server-Side Database

I'm working on extending a web application with a RESTful HTTP-based API. We decided to require the client to supply an authentication token in each request (instead of using sessions or other multi-step authentication schemes like OAuth). E.g.:
POST /foo HTTP/1.1
Authorization: Bearer <authentication token>
...

The token is an opaque string of characters to the user. The token is only shown to the user once. A single user can generate multiple tokens and associate different permissions and a descriptive name with each one. Each request to the API is recorded in a user-visible log and each log entry is associated with the specific token which was used for the request.
In our current implementation, we store an entity with the following attributes in the database:

Random UUID (primary key, used to reference the token from log entries)
Authentication Token (indexed)
Associated User Account and Permissions
User-Supplied Description
Revoked (boolean)

We discussed different security implications of this approach. One threat, which I'd like to discuss here is:
What happens if an attacker temporarily gains read access to the database?
Clearly, storing the authentication tokens makes them vulnerable. After reading the database, an attacker can use any of the non-revoked tokens to access the API. We thought about securing the tokens stored in the database from such a threat.
What approaches (and possibly, applicable algorithms or protocols) can be used to protect the authentication tokens in such a scenario?
I was thinking about hashing the token and using the result of that to find the right entry in the database.

A:

Your tokens are passwords, except you don't let users choose weak passwords. I think they should be hashed in the db. Because they have a lot of entropy (I recommend base64 of 15 bytes read from /dev/urandom), you can use a single round of SHA-256. If you don't think 120 bits of entropy is enough, use 30 bytes. Anyway GPU can't check all combinations.

