REST Web Service authentication token implementati

I'm implementing a REST web service using C# which will be hosted on Azure as a cloud service. Since it is a REST service, it is stateless and therefore no cookies or session states.

The web service can only be accessed over HTTPS (Certificate provided by StartSSL.com).

Upon a user successfully logging into the service they will get a security token. This token will provide authentication in future communications.

The token will contain a timestamp, userid and ip address of the client.

All communication will only happen over HTTPS so I'm not concerned about the token being intercepted and used in replay attacks; the token will have an expiry anyway.

Since this is a public facing service I am however concerned that someone could register with the service, login and then modifying the token that they receive to access the accounts of other users.

I'm wondering how best to secure the content of the token and also verify that it hasn't been tampered with.

I plan on doing the following to secure the token:

The client successfully logs into the service and the service does:

Generate a random value and hash it with SHA256 1000 times.
Generate a one-time session key from private key + hashed random value.
Hash the session key with SHA256 1000 times and then use it to encrypt the token
Use private key to sign the encrypted token using RSA.
Sends the encrypted token + the signature + the hashed random value to the client in an unencrypted JSON package.

When the client calls a service it sends the encrypted token and signature in an unencrypted JSON package to the service. The service will

Recreate the session key from the private key + the hashed random value
Use the private key to verify the signature
Use the hashed session key to decrypt the token
Check that the token hasn't expired
Continue with the requested operation...

I don't really know anything about encryption so I have some questions:

Is this sufficient or is it overkill?
I read that to detect tampering I should include an HMAC with the token. Since I am signing with the private key, do I still need an HMAC?
Should I be using Rijndael instead of RSA?
If Rijndael is preferred, is the generated IV required for decrypted? i.e. can i throw it away or do I need to send it will the encrypted token? e.g. Encrypted Token + HMAC + IV + hashed random value.

Since all communication happens over HTTPS the unencrypted JSON package isn't really unencrypted until it reaches the client.

Also I may want to re-implement the service in PHP later so this all needs to be doable in PHP as well.

Thanks for your help

You are really over-thinking the token. Truthfully, the best token security relies on randomness, or more accurately unpredictability. The best tokens are completely random. You are right that a concern is that a user will modify his/her token and use it to access the accounts of others. This is a common attack known as "session stealing." This attack is nearly impossible when the tokens are randomly generated and expired on the server side. Using the user's information such as IP and/or a time stamp is bad practice because it improves predictability. I did an attack in college that successfully guessed active tokens that were based on server time stamps in microseconds. The author of the application thought microseconds would change fast enough that they'd be unpredictable, but that was not the case.

You should be aware that when users are behind proxy servers, the proxy will sometimes view their SSL requests in plain text (for security reasons, many proxies will perform deep packet inspection). For this reason it is good that you expire the sessions. If you didn't your users would be vulnerable to an attack such as this, and also possible XSS and CSRF.

RSA or Rijndael should be plenty sufficient, provided a reasonable key length. Also, you should use an HMAC with the token to prevent tampering, even if you're signing it. In theory it would be redundant, since you're signing with a private key. However, HMAC is very well tested, and your implementation of the signing mechanism could be flawed. For that reason it is better to use HMAC. You'd be surprised how many "roll your own" security implementations have flaws that lead them to compromise.

You sound pretty savvy on security. Keep up the good work! We need more security conscious devs in this world.

EDIT:

It is considered safe to include timestamps/user IDs in the token as long as they are encrypted with a strong symmetric secret key (like AES, Blowfish, etc) that only the server has and as long as the token includes a tamper-proof hash with it such as HMAC, which is encrypted with the secret key along with the user ID/timestamp. The hash guarantees integrity, and the encryption guarantees confidentiality.

If you don't include the HMAC (or other hash) in the encryption, then it is possible for users to tamper with the encrypted token and have it decrypt to something valid. I did an attack on a server in which the User ID and time stamp were encrypted and used as a token without a hash. By changing one random character in the string, I was able to change my user ID from something like 58762 to 58531. While I couldn't pick the "new" user ID, I was able to access someone else's account (this was in academia, as part of a course).

An alternative to this is to use a completely random token value, and map it on the server side to the stored User ID/time stamp (which stays on the server side and is thus outside of the clients control). This takes a little more memory and processing power, but is more secure. This is a decision you'll have to make on a case by case basis.

As for reusing/deriving keys from the IV and other keys, this is usually ok, provided that the keys are only valid for a short period of time. Mathematically it is unlikely someone can break them. It is possible however. If you want to go the paranoid route (which I usually do), generate all new keys randomly.