How to pick an appropriate IV (Initialization Vector) for AES/CTR/NoPadding?

Question

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.

Glaucoma

Why should you care if the size of the cookie is made a few bytes larger? – Paramedic

Answer 1

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.

Airily

How about taking a hash of the data as the IV? This still needs to be transmitted with the encrypted data, but needs no server side resources between requests and should give different IVs for different messages. Or is there a flaw with this scheme? – Windhover

Using a data hash as the IV has two possible flaws: 1. if you encrypt twice the same message, then you get twice the same encrypted result, and the attacker can see it. This may or may not be a problem in your specific context. 2. Publishing the hash of the message (as the IV) allows the attacker to run an exhaustive search on the plaintext message: trying possible plaintext messages until a match is found. There usually are much fewer possible plaintext messages than possible keys. To fix that, the IV should not be a hash of the message, but, say, a MAC (with HMAC). – Airily

If you prefer, computing the IV from the message itself is a sound idea, but it requires some care. Also, it prevents streaming encryption: you have to buffer all the data to first hash/MAC it, and only then can you begin the encryption. Depending on the context, this may or may not be a problem. – Airily

I have a question on the length of the IV: You suggest 16 bytes, but shouldn't be the length of the whole counter block be 16 bytes (see RFC-3686) and the IV a part of that counter block? This could then for example be a 12 byte IV and a 4 byte block counter or, if you look at RFC-3686, a 4 byte nonce, 8 byte IV and 4 byte block counter. Thanks and BR – Howsoever

Answer 2

I dont have a direct answer for you question but a few things to add though.

First of all, encrypting the cookie does not make sense to me. If you want confidentiality of your data, you shouldn't store it in a cookie anyway. If you want integrity (i.e. not possible to tamper with the content of the cookie), you should use a keyed hash (HMAC, for example).

Another note is to never use a IV which is all 0 just for convenience.

IV's are equal in size with of your block. In case of AES-128, the blocksize is 128, the keysize is 128 and hence the IV is 128 bits.

The best way to do this is by creating a random AES key and using it as IV. This random IV may be public as long as it is not reused in subsequent encryptions with the same key

edit:

You may want to look at this wiki page for more info on which mode to use. However, never use ECB unless you're sure you should use it. And even then, verify with an expert. CBC is as far as I know the safest (together with PCBC).

http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation

Eventide

Indeed, CTR mode provides no integrity protection at all - it is possible to flip any chosen bits of the plaintext, so if the plaintext is known to contain, say, admin=0, then converting that to admin=1 is trivial. If you want integrity, use a HMAC. – Demigod

Why would you CTR mode instead of CBC? Its harder to screw up with CTR than with CBC I think – Eventide

Answer 3

If you don't make the IV random (i.e., you use some repeating group of numbers), it will be easier to figure out the key if the cookie always start with the same clear text.

The IV size for AES-128 is 128 bits. IIRC, the IV is the same size as the cipher block. 128 bits is 16 bytes. 32 bytes if you store it as a ASCII hex string. Is that really too much? 32 bytes in this day and age is not much at all...

Brandie

Answer 4

It is possible to avoid the random IV by using CBC and storing the HMAC in front of the message. Using a randomly picked constant IV is ok. But you have to be sure messages are all different.

This is the case when the encrypted message is always different. A license key with a serial number would match this criteria. A cookie with a user id or session id would match it too.

You may use CBC with a random constant IV if you store the hmac in front of the message. The hash will cumulate all the variations spread in the message in the first block. You may also add a few random bytes or preferably a serial number if you can ensure that it will be unique or not reused in a very long time.

Don't even think of using CTR with a constant IV.

Arnhem

Answer 5

Include a large random number with the cookie. A 64 or 128 bit number is probably large enough. It needs to be large enough for it to be very difficult to get duplicates. Be sure to put enough entropy into this number. Don't just use gettime(). If you have access to CRNG then use it here.

Store a 256 bit master key with your application. Use SHA256 to derive your key information. Again, use a CRNG for this.

$keyblob = sha256( concat("aeskeyid", $masterkey , $randomnumberwithcookie ) )
$aeskey = $keyblob[0..15]
$aesiv = $keyblob[16..31]

You may also want to derive a key for an HMAC.

$mackeyblob = sha256( concat("hmackeyid", $masterkey , $randomnumberwithcookie ) )

Alternatively, you could combine the above two hash operations into one by using SHA512.

$keyblob = sha512( concat("randomkeyid", $masterkey , $randomnumberwithcookie ) )
$aeskey = $keyblob[0..15]
$aesiv = $keyblob[16..31]
$hmackey = $keyblob[32..63] 

Patronize

Answer 6

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.

This is trickier as it sounds as you really don't want to repeat the nonce (the random part of the IV), and you have to take the birthday bound into account because this is true over all the input messages (cookies in your case). Now you could say and try for a one in 2^64 chance of collision, but then you'd need a 127 bit counter anyway; that would leave you with a single bit for the counter before it may overflow; i.e. your cookie size would be maximized to 32 bytes.

Personally I don't like using the full 128 bits because that actually increases the chance of collisions. I would try and decide the maximum size of the cookies, divide that with 16 - rounded upwards - to decide the number of blocks, and then keep as many bits required to fit that (unsigned) number to zero. Then you can fill the other (leftmost, lowest index) bytes with random bits. Cookies have a maximum size of 4096 bytes so you can easily see that it is fine with a one byte counter.

---

You can use the algorithms for the birthday attack here to calculate the chances of a collision for a particular nonce size (the nonce size in bits is log_2(H), as H is the space in the Wikipedia article). Then you can make the number of bytes used as small as you like and calculate the risk of a duplicate counter value.

Say that you're fine with a 1/2^32 risk of a collision and you expect no more than 4 billion (~2^24) cookies. The calculation I used in WolframAlpha is log_2(n^2 / (2p)) where p = 1 / 2^32, n = 2^24. Then you can use a nonce value with the size of 79 bits; let's round that up to 80 bits or 10 bytes. In other words, in Java, you would create a 16 byte IV and fill the lowest index bytes (i.e. the most significant bits of the counter, as CTR mode commonly is big endian) with 10 bytes of secure random data.

As only the highest index byte is increased for cookies you'd have 5 spare bytes, which is nice if the maximum cookie size ever gets increased.

Mandarin