How to renew keys for a statically-encrypted database

Question

Preamble

Before I ask this question, please accept that I fully understand that 'rolling your own' is never a good idea, and that I am a relative n00b. The only reason I am doing this the way I am is that there are major constraints - I have no high-level crypto libraries (like, say, NaCl) available, and this will run on a mainframe. The crypto API I must use makes initialisation vectors my responsibility, but not keys -- I simply present a key token, and encryption and decryption are performed elsewhere in a 'leakproof' part of the system. So please don't criticise me for my environment, and please recognise that 'don't' do anything' is not an option.

Environment

• A legacy database which will contain credit card numbers (PANs)
• The PANs will be encrypted to protect against unauthorised online access by (eg) sysadmins and offline access to backups of the DB
• A single key will be used for all PANs
• Cipher will most likely be AES256 in CBC mode (the API may restrict me to ECB mode, but I'm trying to change that).
• Each PAN will be encrypted with a different initialisation vector, which will be stored with the encrypted PAN
• PANs are constantly being purged from the system. We can establish a maximum lifetime.
• Storage space is limited -- I can pull an extra 16 bytes for the IV, but any more will be hard.
• It is not practical to scan and update the database if I want to change the single key -- the DB runs at about 40,000 I/O per second for most of the 24-hour day and the system runs non-stop.

The Challenge

Find a way to be able to expire the single key and introduce a new one

The Proposal

Here's my current thinking, which I recognise has weak points.

Cryptographic keys are generated, and stored encrypted under a master key, in a completely separate component of the system, with its own access rules. Keys are identified for use by an alphanumeric key token.

At any time, I have two available keys, called 'A' and 'B'

For encryption:

• Obtain a 16-byte cryptographically sound random number
• Set the last bit on, signifying key A
• Call the encryption API with the resulting IV, and key token A
• Store the IV and the encrypted data

For decryption:

• Test the last bit of the stored IV
• If the bit is 1, select key Token A; if not, select key Token B
• Call the decryption API with the IV and the selected key token

Now, when I need to expire the key, I simply need to change the encryption to set the last IV bit off and use key B. Decryption does not change.

Around six months later, when I have no more A IVs left in the system, I can swap again.

Each time I swap, I can generate a new key for encryption from this point on.

My questions are these:

1. If I cannot obtain a cryptographically sound random IV, just how bad would it be to use a high-resolution clock? The clock I have in mind is high-resolution (10 nanoseconds or better, and guaranteed not to repeat, as I won't be doing more than about 10k encryptions per second). I understand that the IV should not be predictable, but just how (precisely) predictable is such a clock?

2. I have to cater for the possibility that a PAN may get left over from a previous key which is no longer available; for example, a PAN which was encrypted with an earlier A key, but which fails to decrypt with the current A key. Assuming I don't want to increase the number of bits I 'steal' from the IV, is there a good, simple way to verify that the decryption is with correct key. I'd prefer to avoid the extra overhead of something more complex, like, say, an HMAC. Suggestions?

3. Any other comments or criticisms (within my constraints)?

Answer 1

Some remarks:

• a 16 byte IV is required by CBC, but you may not require a 128 bit unique value for your protocol
• CBC relies on an IV that is indistinguishable from random to an attacker, fixing bits in the IV is not a good idea
• CBC requires a padding mechanism, unless you can use ciphertext stealing

Now a few calculations reveal that if you rely on the non-repeating counter, that you need an number of 8 bytes to have enough precision (584 years should be enough). Store just this number. You can create a good IV from this number by pre-pending the number with zero's and performing a single block encrypt (in the black box of course).

Now you have got 8 bytes left. I would suggest you use these for the key indicator (make it one byte instead of 1 bit, to avoid key management issues later on). You could use the additional 7 bytes for storing an authentication tag, so that nobody can change the ciphertext (and thus the PAN) unnoticed.

Finally note that the "default" padding mode for CBC mode of operation, PKCS#7 padding mode, will use 1 to 16 additional bytes of overhead. This is overhead you can sorely miss on size constrained systems, especially since it can be avoided without penalties on the security of the protocol. Look up ciphertext stealing, or go with another mode of operation that does not require padding.

This answer is provided as is. I remain convinced that you should hire a consultant that has experience protecting credit card related data.

Answer 2

You should consider using an authenticated encryption (AEAD) mode. As @d-w says, and as the name implies, it will detect malicious manipulations of the cipher text stored in the DB with high probability.

On top of that:

1. you will also detect all cases where you are using the wrong key by mistake.
2. you can authenticate any metadata associated to the credit card number, like row id in the database. That's useful to detect more subtle attacks like transfer of credentials. Metadata does not need to be stored with the key and does not enlarge the cipher text.
3. for most AEAD modes, no padding is needed. Is your BCD-encoded credit card number 8 bytes long? Then your ciphertext will be 8 bytes long too. With CBC, you would have "wasted" 8 bytes to align that to the AES block boundary.

IV and nonces

None of the AEAD modes I know of uses IVs. Instead they use nonces, which have to be unique across all messages protected under the same key.

If you are not confident you can guarantee such uniqueness, you may consider the SIV AEAD mode (RFC5297). The nice thing about SIV is that it only recommends to use a nonce. If you don't use it or fail to keep it unique, the "only" leakage you get is that an attacker (or auditor) will be able to tell when two users have the same credit card number. Is that a security concern? Apart from that, confidentiality and authenticity are still provably preserved.

Drawbacks

If that sounds to good to be true, here are the drawbacks of using SIV:

1. You need 2 independent AES keys in your "leakproof" part of the system, not just one.
2. The overhead in bytes is 16 bytes (the MAC tag) + the length of the key identifier you choose (no more, assuming no nonce). You cannot cleverly reuse any part of the MAC tag as key identifier. However, if you can store extra 16 byte as you say, it may be OK to store 17 too. Again, note that no padding is needed.
3. You need to implement the SIV construction. It is not trivial, but not rocket science either: you can use CBC and ECB modes as building blocks. Availability of CTR greatly helps.

Answer 3

Your scheme lacks any authenticated. I recommend you use authenticated encryption. Yes, this will require additional storage. It's necessary.

ECB mode is not recommended.

To expire a key and introduce a new one, why don't you just decrypt all of the current stuff under the previous key and re-encrypt under the new key?

Applying bit-flipping to IVs is a bit sketchy. I don't recommend it. Suggested alternative: store a 127-bit random number, and then form the IV by encrypting the random number using AES in ECB mode with a separate key. That leaves you an additional 1 bit for the key identifier.

CBC mode requires a crypto-strength pseudorandom number as the IV. If you have something that's guaranteed to be non-repeating but might be predictable, you need to encrypt it first (using AES-ECB) to form the IV; in general it is not recommended to use that directly as the IV.

I recommend you hire a professional cryptographer as a consultant to help you with your problem.