Relative merits of AES ECB and CBC modes for securing data at rest

Question

I need to store several million Payment Card Numbers (PCNs) securely in a mainframe database (that is, 'at rest'). I assume that any attacker will have access to all of the stored data.

I assume the availability of a secure device that can:

• Store a unique, constant ('master') key that is to be used for all PCNs
• If necessary, store a unique, constant IV to be used for all encryption with the master key
• Encrypt (AES-256) data in ECB or CBC mode
• Decrypt (AES-256) data in ECB or CBC mode

What are the relative merits and demerits of the following possible options for encryption and decryption?:

1. Use the master key in ECB mode. I have heard/read that this is cryptographically weak (Why?).

2. Use the master key and IV in CBC mode.

3. Prepend a 16-byte, microsecond-or-finer, timestamp to the PCN, then use the master key and IV in CBC mode. This would mean storing an additional 16-byte block of ciphertext, but this isn't a problem. On decryption, just discard the first 16 bytes of the resulting plaintext.

4. (If available) As (3), but have the device provide a 16-byte pseudo-IV.

5. Something better (please specify)

Extra kudos for explaining possible attacks on a large quantity of sixteen-digit numbers encrypted under any of these schemes.

I'm new at this, and I know it's very easy for noobs to produce stuff that an average cryptologist would find laughable, so please be gentle -- I'm just trying to learn.

I've placed this here, rather than on security.SE, because it looks like a better fit; if y'all disagree, I shall be most grateful if you will migrate it, rather than closing as off-topic.

---

For additional clarification, following the answer from @curious :

The reason I include ECB mode here is that it could allow me to save half the storage space. Since the messages are only one block long, I suspect this may affect the 'traditional' arguments against ECB.

But I am interested in understanding whether there are any specific vulnerabilities arising from:

• The relatively low entropy of the messages (message space of 1E16 possibilities, reduced by PCN checksums)
• The use of a fixed, universal key or key+IV

Answer 1

Use the master key in ECB mode. I have heard/read that this is cryptographically weak (Why?).

The reason I include ECB mode here is that it could allow me to save half the storage space. Since the messages are only one block long, I suspect this may affect the 'traditional' arguments against ECB.

Because any identical plaintexts will encrypt to the same ciphertext value. Unless each plaintext is encrypted only once, ever, for the lifetime of the key, you are revealing information about your plaintexts.

ECB mode should be out of the question for any cryptosystem which actually desires to keep its ciphertexts secure.

Use the master key and IV in CBC mode.

This is must better, but still weak. However, you must use a cryptographically random IV of the same block size as the cipher (AES-256 uses a 128-bit block size). Use of a constant IV is essentially indistinguishable from ECB mode, and use of weak, predictable IVs isn't much better.

Prepend a 16-byte, microsecond-or-finer, timestamp to the PCN, then use the master key and IV in CBC mode. This would mean storing an additional 16-byte block of ciphertext, but this isn't a problem. On decryption, just discard the first 16 bytes of the resulting plaintext.

You are essentially inventing your own encryption mode. This is both unnecessary and highly dangerous.

Something better (please specify)

You should almost certainly be using authenticated encryption. For instance, the crypto_secretbox functions in NaCl. If you are unable to use NaCl, you use AES in EAX or GCM mode, or approximate your own by doing Encrypt-Then-MAC (computing the HMAC with a completely separate key; e.g., not the same key you used to perform encryption). When decrypting, you must require the HMAC to be sent along with the ciphertext and IV, and you must verify the HMAC (using a constant-time string comparison algorithm) before attempting to decrypt the ciphertext. The whole point of this is to deprive the attacker from being able to execute chosen-ciphertext attacks.

If you do not use authenticated encryption, and an attacker is capable of sending you messages which you then decrypt, the attacker can almost certainly read the contents of your ciphertexts even if you do not send him the decrypted result. The most worrying type of attack of this nature is the CBC padding oracle attack.

If you do not use a constant-time string comparison algorithm, then an attacker can forge valid HMACs, and thus can execute the padding oracle attack and thus get at your secret data.

The takeaway from this should be that encryption is hard. If at all possible, use a higher-level library like NaCl that has already made the correct decisions about cryptography and has been implemented by highly respected cryptographers.

But I am interested in understanding whether there are any specific vulnerabilities arising from:

1. The relatively low entropy of the messages (message space of 1E16 possibilities, reduced by PCN checksums)
2. The use of a fixed, universal key or key+IV

The entropy of the messages themselves is irrelevant if you use cryptography properly.

For example, if you use ECB mode (or a constant IV in CBC mode, which is cryptographically equivalent) and an attacker is able to provide his own data to be encrypted, your data is as good as stolen. The attacker merely has to enumerate through likely card numbers (use of a checksum or particularly common prefixes, like most credit cards have, cuts down on the search space dramatically) and compare the resulting ciphertexts.

Again, if you use encryption, you must do so properly if you wish to provide any realistic guarantees about the security of the data you wish to protect. You should, if at all possible, not be dealing with encryption at the level you are attempting — it is the wrong layer of abstraction. Use something like NaCl.

Answer 2

While I'll try to answer your question at a theoretical level below, I'd like to first stress the following: It's a bad sign if, in the course of writing software, one is making such low-level decisions about encryption methods. Encryption security is extremely brittle, with seemingly insignificant details causing complete failure.

With that said, the question brings up some interesting issues with encryption security versus efficiency.

As the other answer notes, ECB reveals when the same block has been enciphered twice and CBC does not (as long as the IV is unique or random). If you are, for some reason, absolutely sure the same block will never be enciphered, then ECB is in theory fine. (One technique might be to encipher the blocks in "batches" using a wide-input blockcipher, so that now a ciphertext will repeat only if an entire "batch" repeats.) But in my opinion this is an unnecessary risk.

Will you ever change blocks of the data once it is written? This need is one of the distinguishing requirements when dealing with "data at rest" (as opposed to e.g. data being sent over an SSL connection). ECB, while insecure, will allow you to efficiently change the data in place while CBC will not. But be aware that the security your are achieving in either case is not ideal.

In general, and especially if local updates are needed, a better technique is to employ a "tweakable block cipher" with the disk location as the tweak. This will hide repeats amongst different blocks if one uses the block's index (disk location, etc) as the "tweak." Moreover, it will allow for efficient updates. This can be combined with the "batching" technique above to provide a level of security that seems pretty strong: A repeat will only be noticed by an adversary who can watch you change the data, and only when you write the same batch of numbers to the same location twice. Otherwise the data will be kept private in a strong sense.

It might be help to look at the IEEE 1619 standards documents and associated references for information about tweakable blockciphers and the wide-input batching technique. The theory outlined there is a long way from a "secure" implementation, and again it seems you probably want to use an existing implementation of this stuff rather than roll own.

Answer 3

ECB mode is totally insecure. The same block in the plaintext results in the same ciphertext. That means that it's deterministic and the attacker can distinguish between two ciphertexts so it's not CPA secure. Suppose the attacker is giving the challenger 2 equal blocks of messages m0||m1 . He will receive co||c1 where c0=c1.And then he submits another message of two blocks m2||m3 where m2<>m3 along with the first message m0||m1.Since he can distinguish between those two the sceme is insecure under Choosen Plaintext Attacks.