I would like to encrypt the cookies that are written by a webapp and I would like to keep the size of the cookies to minimum, hence the reason I picked AES/CTR/NoPadding.
What would you recommend to use as IV that's random enough and still keep the app stateless. I know that I can just generate a random IV and append it to the message, but that will increase the size of the cookie.
In addition, what's the recommended size of IV for 128-bit AES?
How else is everyone doing this? Do any "tried and true" ways exist? I don't want to reinvent the wheel.
CTR security requires that you never reuse an IV for two message encryptions with the same key. Actually it is even stricter: CTR mode works by encrypting successive values of a counter (the IV is just the initial value for that counter) and proper security is achieved only if the same counter value is not used twice; this means that encrypting a value with an IV actually "consumes" a sequence of successive IV values which must not be reused with another encryption.
The easy way to do that is to use a cryptographically secure random number generator, and create a new 16-byte random IV for every message. I underline "cryptographically secure" because that's important; a basic random number generator is not enough. With Java, use java.util.SecureRandom. With Win32, call CryptGenRandom(). With a random selection, the space of possible 128-bit IV is large enough that collisions are extremely improbable. Actually, that's why AES uses 128-bit blocks (thus implying 128-bit IV).
The entity which will decrypt the message must know the IV, so you have to store it along with the encrypted message. That's an extra 16 bytes. I understand that this overhead is what you want to avoid, although 16 bytes is not that much for a cookie. The effective maximum length of a cookie depends on the Web browser but 4000 characters appear to work "everywhere". A 16-byte IV, when encoded in characters (e.g. with Base64), will use about 22 characters, i.e. much less than 1% of your maximum cookie size: maybe you can afford that ?
Now we can get funky and try to reduce the IV length through trickery:
Generate the IV with a hash function: server-side, use a counter, which begins at 0 and is incremented every time a new IV is needed. To get the IV, you hash the counter with a suitable hash function, e.g. SHA-256, and you keep the first 16 bytes of the hash value. The "randomization properties" of the hash function will be enough to make the IV sufficiently random with regards to CTR requirements. This needs a cryptographically secure hash function, hence SHA-256 (avoid MD5). You then just have to store the counter value in the cookie, and the counter will be shorter than 16 bytes (e.g. if you have no more than 4 billions customers, the counter will fit in 4 bytes). However, there is a hidden cost: the server (I suppose the server is performing the encryption in your system) must make sure that it never reuses a counter value, so it must store the "current counter" somewhere in a way which persists over server reboots, and also does not fail if you scale up to several front-ends. That's not as easy at is seems.
Use an external unique value: possibly, the cookie could be part of an context which provides enough data to generate a value which will be unique to each encryption. For instance, if the request also contains (in the clear) a "user ID", you could use the user ID as an IV source. The setup is similar to the one above: you get all that data, stuff it into SHA-256, and the first 16 bytes of SHA-256 output is the IV you need. This works only if that data does not change for a given encrypted message, and if it is really unique. This is a rare occurrence: for instance, a "user ID" is good for that only if there is never a need to reencrypt a new message for the same user, and if there is never a possibility that a user ID is reused (e.g. an old user quits, a new user comes and selects the now free user ID).
Using a random 16-byte IV generated with a cryptographically secure PRNG is still the "safe" way, and the one I recommend. If you find space tight in the cookie, then this means that you are approaching the 4 kB limit, at which point you may want to use compression (on the data before encryption; after encryption, compression is very very unlikely to work). Use zlib (in Java, you can access zlib through java.util.zip).
Warning: in all of the above, I am not saying anything about whether cookie encryption does help in providing whatever security characteristics you are trying to achieve. Usually, when encryption is needed, you actually need both encryption and integrity, and then you should use a combined-encryption-and-integrity mode. Lookup GCM and CCM. Moreover, cookie encryption is mostly good for one purpose, which is to avoid the cost of storing server-side a bit of user-specific data. If you want to encrypt a cookie for something else, e.g. to authenticate a valid user, then you are doing it wrong: encryption is not the right tool for that.