What encryption algorithm is best for encrypting cookies?

Question

Since this question is rather popular, I thought it useful to give it an update.

Let me emphasise the correct answer as given by AviD to this question:

You should not store any data that needs encrypting in your cookie. Instead, store a good sized (128 bits/16 bytes) random key in the cookie and store the information you want to keep secure on the server, identified by the cookie's key.

---

I'm looking for information about 'the best' encryption algorithm for encrypting cookies.

I hava the following requirements:

• It must be fast
  encrypting and decrypting the data will be done for (nearly) every request
  

• It will operate on small data sets, typically strings of around 100 character or less

• It must be secure, but it's not like we're securing banking transactions

• We need to be able to decrypt the information so SHA1 and the like are out.

Now I've read that Blowfish is fast and secure, and I've read that AES is fast and secure. With Blowfish having a smaller block size.

I think that both algorithms provide more than adequate security? so the speed would then become the decisive factor. But I really have no idea if those algorithm are suited for small character string and if there are maybe better suited algorithm for encrypting cookies.

So my question is:
What encryption algorithm is best for encrypting cookie data?

Update
To be more precise, we want to encrypt 2 cookie: one with session information and the other with 'remeber me' information.

The platform is PHP as apache module on Linux on a VPS.

Update 2
I agree with cletus that storing any information in a cookie is insecure.

However, we have a requirement to implement a 'remeber me' feature. The accepted way to go about this is by setting a cookie. If the client presents this cookie, he or she is allowed access the system with (almost) equal rights as if he/she presented the valid username password combination.

So we at least want to encrypt all data in the cookie so that it:
a) malicious users can't read it's contents,
b) malicious users can't fabricate their own cookie or tamper with it.

(All data from cookies is sanitized and checked for validity before we do anything with it, but that's another story)

The session cookie contains a sessionId/timestamp nothing more. It could probably be used without encryption, but I see no harm in encrypting it? (other than computation time).

So given that we have to store some data on in a cookie, what is the best way to encrypt it?

Update 3
The responses to this question made me reconsider the chosen approach. I can indeed do the same without the need for encryption. Instead of encrypting the data, I should only send out data that is meaningless without it's context and cannot be guessed.

However, I'm also at a loss:
I thought that encryption enabled us send data out in to the BigBadWorld™, and still be (fairly) sure that nobody could read or tamper with the it...
Wasn't that the whole point of encryption?

But the reactions below push toward: Do not trust encryption to accomplish security.

What am I missing??

Answer 1

No real reason not to go with AES with 256 bits. Make sure to use this in CBC mode, and PKCS#7 padding. As you said, fast and secure.

I have read (not tested) that Blowfish may be marginally faster... However Blowfish has a major drawback of long setup time, which would make it bad for your situation. Also, AES is more "proven".

This assumes that it really is necessary to symmetrically encrypt your cookie data. As others have noted, it really shouldnt be necessary, and there are only a few edge cases where there's no other choice but to do so. Commonly, it would better suit you to change the design, and go back to either random session identifiers, or if necessary one-way hashes (using SHA-256).
In your case, besides the "regular" random session identifier, your issue is the "remember me" feature - this should also be implemented as either:

• a long random number, stored in the database and mapped to a user account;
• or a keyed hash (e.g. HMAC) containing e.g. the username, timestamp, mebbe a salt, AND a secret server key. This can of course all be verified server-side...

Seems like we've gotten a little off topic of your original, specific question - and changed the basis of your question by changing the design....
So as long as we're doing that, I would also STRONGLY recommend AGAINST this feature of persistent "remember me", for several reasons, the biggest among them:

• Makes it much more likely that someone may steal that user's remember key, allowing them to spoof the user's identity (and then probably change his password);
• CSRF - Cross Site Request Forgery. Your feature will effectively allow an anonymous attacker to cause unknowing users to submit "authenticated" requests to your application, even without being actually logged in.