Is RESTful API Suitable for Computational Services?

First of all, let me say that I agree 100% with @MvdD, that a REST API should not include login/logout semantics. However, as I'm sure you've heard/read OAuth is a headache you really don't want if you aren't "required" to have federated auth!

As other answers have pointed out, there is no one pattern to accomplish this, with several being accepted as answers in previous similar questions (mostly from SO). I'm also assuming you've looked at previous related questions and such. There is also this question (RESTful Authentication) on SO, which details 4 techniques (some more RESTful than others). If you're (seemingly?) happy to transmit the password as cleartext in HTTPS then option #1 of that answer (HTTP basic auth) would work with pretty much any HTTP library your REST tools are wrapping.

If you must...

Since there's a bounty and all (and because it's an interesting challenge), I thought about it, and (after about 1.5 cups of coffee) have had the following idea: POST to a "challenge" resource, which then redirects to a resource identifier for that challenge, (and no this is not idempotent).

What am I talking about?

Well, as pointed out here (Table 1, page 3), resource identifiers are different to resources themselves. Ergo, you can RESTful-ly POST to one URI but be causing a change (i.e. RESTful change, such as CREATE, UPDATE) in a resource not necessarily located there. Let me explain in action...

Authentication Process:

1. Client sends POST /challenges with payload of username. This triggers the server to create necessary backend entry in DB table, allocate resources, etc.
2. Server responds with a 303 See Other (which is just a newer version of 302 Moved temporarily), directing client to /challenges/<some random request code>.
3. Client GET's /challenges/<some random request code> (Note, will be GET, as 303 is used instead of 302). Which returns (with a 200 OK) a JSON-encoded challenge (more on this later).
4. Client responds to challenge, this time with POST to /challenges/<some random request code> with a hash meeting the challenge as payload.
5. Server responds with either 403 Forbidden (if challenge failed, ergo, wrong password, etc) or a 200 OK (optionally with a JSON payload containing your session info or user profile or what-have-you).

A word on Challenges: (As promised in step #3)

The challenge given by the server is basically just some task (usually hashing, but possibly a two-way encryption/decryption, etc) given by the server to the client. The server knows (computes) the result (hence why hashes are good, since they're cheap) ahead of time, and compares that with the challenge-responce given by the client.

This can be as simple as some random text (or even static text, like your application name, etc) sent to the client in plaintext (or hash, not important) with the server having worked out the hash of that text (essentially a salt) concatenated with the (hashed, since it's in the DB - and we don't store plaintext passwords in databases) password. If the client can concatenate this salt with the password (after hashing the password locally) and then hash that concatenation, it can answer the challenge.

Example:

• server: salt = md5("MaryHadALittleLamb") -> 8c20828418ca489f5b949f25f35abaa0 (sends to client in step #3).
• client: hashes the password "password" ('username' is a notoriously insecure password selector) to produce 5f4dcc3b5aa765d61d8327deb882cf99, this is then concatenated with 8c20828418ca489f5b949f25f35abaa0 to produce "5f4dcc3b5aa765d61d8327deb882cf998c20828418ca489f5b949f25f35abaa0".
• client: hashes this md5("5f4dcc3b5aa765d61d8327deb882cf998c20828418ca489f5b949f25f35abaa0") -> 09f3bb66a44153c4053857d4b57fdf3b and sends to server (step #4).
• server: (having already done the above itself) compares 09f3bb66a44153c4053857d4b57fdf3b with it's own result, and (if they match) allows username to login (or begin a session, etc).

Note: This is a fairly naive way to implement challenges, as there's no temporal component of the salt it's vulnerable to replay attacks, etc. But you can ask more about that on Security.SO if need be.

I think there are two solutions in your list that fit your use case best; the read query before the update (solution 2) and sending an update token with the read request (solution 5).

If you're worried about performance, I'd decide on one or the other depending on how many reads vs updates to a resource you expect. If you expect way more updates than reads, then obviously solution 5 is better, because you don't need to do an additional database fetch to figure out the owner of the resource.

However, you shouldn't forget the security implications of giving out an update token. With solution 2, assuming authentication is secure, then updating a resource is probably also secure because you determine the owner of a resource on the server.

With solution 5, You don't double-check the claim the client makes, except that you check for a valid signature. If you're letting the update happen over a cleartext link (eg, no SSL), then only encoding the resource and user id in the token isn't secure. For one, you're opening yourself to replay attacks, so you should include a nonce that grows with each request. Also, if you don't encode a timestamp/expiration date in the update token, you basically give indefinite update access to anyone who has that token. Finally, if you don't want the nonce, then you should at least include an hmac of the fetched resource, so that the update token is only valid for the state of the resource as it was fetched. This makes replay attacks more difficult and further limits the damage knowledge of the update token can do, since the update token is only valid when the resource is in the given state.

I think that even if you're communicating over a secure link, adding a nonce (or at least an hmac of the state of the resource) and an expiration date for the update token would be a clever thing to do. I don't know the application domain, but you may deal with malicious users and they might wreck all kinds of havoc with the power of unlimited update access to their own resources.

Adding a nonce will mean an additional column per resource in your database where you store the value of the nonce you sent with the last fetch request. You can compute the hmac over the serialized json representation of your resource. You can then send your token not as part of the message body but as an additional HTTP header.

Oh, and I'd use a token, not a URL; in REST, the update URL for a given resource should be the same URL the resource was fetched from, right? I'd move all authentication & authorization-related stuff to the HTTP headers, e.g. you could provide the update token in the Authorization Header of the PUT request.

Note that adding a nonce that grows with each resource fetch will also require a database update (the new value for the nonce) for each resource fetch request (although you may get away with only updating the nonce when the state of the resource is actually changed, so it would be free from a performance standpoint), unless you want to keep that information in transient memory and simply have the clients retry when your server is restarted between a fetch and an update request.

A side note to your solution 4 (client side sessions): Depending on the number of resources your users can create, the session size might not be a problem. The client side session update problem might be fairly easy to solve, as well: If an update request to a resource fails because the resource is not listed in the session data you received from your client, but the user is correct, then you do a check in the backend whether the session data from that client is outdated. If it is, you allow the update and send back an updated cookie with the answer to the update request. This will only cause a database lookup when a user tries to update a resource from a client with outdated local session data (or when he is malicious and tries to ddos you, but rate limiting to the rescue!). However, I agree that solution 4 is more complicated than the others and you're better of with one of your other ideas. Solution 4 also has various security considerations you should take into account; storing this much authorization state on the client really needs your security to be watertight.