An alternative way of doing this might be use the cookie as an encrypted storage for only indirection data. You'd need some sort of unencrypted identifier that would serve as a pointer to the key (or the required information to derive the key) in the application's database, followed by a blob encrypted by the key obtained from the identifier, which itself would contain some sort of one-time-usable identifier that authenticates the session.
Given the following assumptions:
- Your database is secure (e.g., your application can access it, but your user cannot directly do so, and also assuming that the application has been proofed against SQL injection)
- Your salts are strong; that is, reasonably high-entropy enough that attempting to crack the salted password is infeasible even if the password is known
Then what this would provide is a method by which one can be reasonably certain that the session is not able to be hijacked or stolen in any way. That is to say that a copied cookie is only of limited usefulness, since the user must not have used the cookie between its theft and usage by an attacker.
While this protects against replay, it also means that if someone does manage to steal the cookie at exactly the right time, and manages also to use it before the original, legitimate user does, the attacker now is in control of the session. One can limit a session to an IP address to mitigate that risk (somewhat; if both the user and the attacker are behind the same NAT, which is the most likely scenario in any home or small-to-medium business network) then this point is pretty moot, since the IP address would appear to be the same anyway. Also useful might be limiting to the current user agent (though that can break unexpectedly if the user updates their browser and the session does not expire at browser close time), or finding some method by which one can identify the computer that the user is on just well enough that there is reasonable certainty that the user hasn't moved the cookie from one system to the next. Short of using some binary plugin (Flash, or Silver/Moonlight), I'm not sure that the latter is possible.
To protect against a permanent session hijacking, require that the user to reauthenticate him- or herself periodically (e.g., limit the allowed session lifetime or require something like a token/fob/dongle) and require that the user reauthenticates him- or herself upon entering sensitive areas of the application, such as password change and potentially dangerous actions, patterns or behaviors such as the deletion of data, unusual usage patterns, bulk actions, and so forth.
It is difficult to secure applications and yet retain their ease-of-use. If done carefully, security can be implemented in a manner which is minimally intrusive and yet still effective—well, for most Internet-facing applications, anyway.