Is it bad design to reuse an AES key?

Question

The company I work for needs to develop a simple system where, for each client, we encrypt a token on our server, which is then transmitted to the client. The decryption is performed by the server itself when the client transmits the token (thus the only machine that performs crypto is the server).

The token is for an external service, so integrity checking is not an issue.

I wrote code that encrypts these tokens using AES/CBC, using the same key and a unique IV; I am not aware of any practical attacks against AES, even with an arbitrarily large number of known ciphertexts.

My colleague insists that an adversary could break this (i.e. get the key and decrypt stuff) after collecting a (possibly large) amount of ciphertexts; thus, he argues that we should have one key per client on the server.

Who is correct?

Answer 1

Now, on to your question.
But, since reusing the IV with the same key is something that you should never, ever, ever do, I'm going to assume that instead, you are generating a new random IV for each encryption, but using the same global encryption key.

The answer really depends on what your colleague means when he says break. There are academic breaks and there are practical breaks.

Your colleague is correct if we are referring to academic breaks. Assuming you are generating good, random IVs for each encryption, after capturing $2^{64}$ ciphertexts, we can expect to have had one duplicate IV (this comes from the birthday problem). Given the two ciphertexts that have duplicate IVs, the attacker can distinguish whether or not the two ciphertexts encrypt the same plaintext. Or even more accurately, the attacker can determine the number of blocks starting from the beginning that are the same. Once one block is different, however, the attacker cannot distinguish any further. That is an academic break. Capturing $2^{64}$ ciphertexts would be a very noisy attack and would require lots of disk space to store. But is not outside the realm of possibility.

That said, I don't see any way an attacker could feasibly break the key or a plaintext only given access to a huge (but practical) number of ciphertexts.

A better design
What would probably be a better design would be to generate a new, random key and IV for every encryption. Encrypt the plaintext with those (and use HMAC or an authenticated encryption mode). On the server you should have an asymmetric key pair (for example, an RSA key pair). Encrypt that random symmetric key using the public (RSA) key. Send the ciphertext and the encrypted symmetric key to the client.

When the client sends this back, you would decrypt the symmetric key using your private (RSA) key. Then decrypt the ciphertext with that key and check the HMAC or authentication tag.

My final suggestion is to hire somebody very knowledgable in this area to review your design and implementation (or even to help out with the design process) so you are not putting your customers at risk. I doubt it would cost very much.