Reusing AES-CTR Keys and IVs for File Encryption

Question

I’m implementing some file encryption module with random-access capability and AES-CTR seems the right way to go.

I understand that reusing Keys and IVs can expose the file to ‘Stream Cipher Attacks’ when portions of the file are being modified (assuming previous versions of the file are still available).

I want to avoid re-encrypting the entire content of the files when they are modified and so I thought to combine CTR with ECB. First encrypt the block with CTR and then re-encrypt the resultant cipher text with the same key again:

CTR-Cipher = Plain xor AES(IV + counter, Key)
Final-Cipher = AES(CTR-Cipher, Key)

Would that allow me to reuse the key and the IV? Or are there other secure alternatives to support random-access based encryption without a lot of re-encryption?

Answer 1

Yes, there are secure alternatives to support random-access based encryption.

I did not come up with a way to break the proposed combination. Still, instead of inventing a new mode, I would recommend to take consider existing modes for this kind of operation, such as XTS mode. The existing modes are more studied, and (in some ways) more efficient. XTS mode (as well as some other modes) only invokes cipher once per block of input. Rogaway has created a paper describing the most common modes of operation, which contains good study of XTS mode, including some critique.

Alternative: IEEE P1619

IEEE P1619 has developed standards for disc encryption. These standards contain cryptographic mechanisms for keeping disc storage encrypted. As disc storage (often) requires frequent rewrites of disc sectors, these standards capability of rewriting sectors.

IEEE P1619 specifies both length expansionless encryption mechanisms and mechanisms with length extension (P1619.1). XTS mode is one of the most commonly used cipher modes of operation, if you want to avoid length extension. It likely proves the security features you expect from CTR with ECB combination, i.e. it works on narrow blocks (16 bytes) and allows you to pass in index of the sector. Some narrow block a problem. In that case, you mate take a look at wide block encryption such as EME2, XCB from P1619.2.

Alternative: Per Block IV (Traditional)

Just for reference I also mention traditional (well studied way to do this). This approach may prove useful in case you lack cryptographic library or hardware with appropriate modes from P1619.

A well known way to do random-access based encryption is to consider data as blocks and generate random IV per each block each time a block is updated. This of course mess that the encrypted data will expand, but the percentage is not very large: consider e.g. one kilobyte blocks and 16 byte IVs: $\frac{16}{1024}\approx1.6\%$. This is only a small cost. Note: When expanding length, it is commonly good idea to add authentication tag as well.

Answer 2

Your combined mode of operation is not as easy to attack as a two-times-pad (i.e. stream-cipher with fixed IV used twice), but it still has some weaknesses.

For example, an attacker which did read your file before and after the change can easily find out which 128-bit-blocks of the file did change and which ones stayed the same. Depending on the file format this might or might not be a problem.

What often is done is to split the file (or disk volume or similar) into blocks (sectors) of larger size – about the size of what can be accessed (written/read) at once. (This depends a bit on your disk, but 4 KiB seems to be in the right order of size). Each sector gets its own random IV, which is stored at the beginning of the sector (this makes for a small size overhead). Reencrypt the whole sector when something changes.

Or use a mode of operation which is actually meant for disk encryption.

Answer 3

What you've proposed is simply a "CTR-then-ECB" over the plaintext. Just a composition of two common cipher modes.

This "double cipher" scheme will fail IND-CPA from your reuse of IV's as the encryption oracle in this case must not only take an arbitrary attacker's "messages" but also use whatever "IV's" they choose to specify as well (since the encryption oracle isn't always generating a new one at random).

So, for example, if they wish to decrypt some given block of ciphertext $c$, they can simply keep feeding "guesses" $p_1, p_2,\ldots$ into your encryption oracle with the known IV (e.g., derived from the disk location) of block $c$. Note that since user plaintexts don't usually have a high degree of entropy, this can be a problem.

Now, you might say, for example, that the encryption oracle might not take in an IV chosen by the attacker, but will just use whatever IV is predefined for some presently free/unused blocks specially reserved for the attacker for an IND-CPA challenge. In other words, the attacker cannot choose the IV that will be used. Since currently user-occupied disk blocks are not modified nor have their specific IV's used, this might not seem like a problem. And it might seem therefore that current "user data" is safe (even if the user modifies) for now.

But -- as I mentioned before, user plaintexts often have a low degree of entropy. An attacker could just spam the presently free locations on your disk to build a rainbow table of possible user plaintexts that could eventually take up the space of the presently free blocks (that are free and therefore available for attacker use). What happens if the user saves some more data on their machine, and those free locations must be written to? What happens if a user copies an existing file to a different location? (even with some modifications, like myData1.txt copied over to a myData2.txt)

The attacker can read the encrypted disk at some later time and see that some previously free / attacked locations have now have user-modifications in them. Perhaps they can run this new ciphertext offline through their previously-constructed rainbow tables that the disk encryption oracle helped them to create earlier (for those block locations)!

And what if a user deletes some data somewhere? Perhaps the attacker knows the previous ciphertext from the block locations that now just opened up, and might use them to run a rainbow table against the encryption oracle to find out what was originally in them.

Or simply copy the user's old deleted ciphertext into that free location as the attacker's own and ask the system to decrypt it!

In conclusion

Your "CTR-then-ECB" is for fine for user data in block locations that are never freed up nor were ever attacked prior. But according to Disk Encryption Theory your free and unused blocks are subject to attack anytime, and it's not unreasonable for a user to write data to previously unused block locations (which may have been attacked) nor free up previously used locations and thus make them ripe for attack.

To circumvent this, we can simply re-encrypt everything in a sector with a new random IV for the sector every time something changes, which is itself stored somewhere in the sector for a small size overhead of 16 bytes. The only case when we might not have to re-encrypt everything in the sector and that is if a file there has been modified without changing its size or block location "range" on disk -- in that case, the attacker might know which blocks have been modified, but unless they had an opportunity to attack those block earlier back when they were free before, they won't be able determine the actual corresponding plaintext nor what the plaintext changes were.

Miscellaneous

Note that in Disk Encryption Theory the attacker may have quite a few more capabilities than what an average consumer of disk encryption may envision. For example, the threat/attack model regular consumers might envision might be limited to just some attacker trying to decrypt a lost or stolen device, or even a government agent or border control officer requesting to inspect these.

In such cases, assuming the device is simply turned off / shut down at the time, then even a single pass of AES-CTR with a static but unique IV per block location would suffice. And entire sectors need not be re-encrypted for single 16-byte block changes either.

So, in other words, in such "restricted scenarios" wherein which the attacker has zero access to your encryption/decryption oracle, the only additional "protection" offered by your extra ECB step is simply preventing a known plaintext attack from recovering any new user data that overwrote the previously compromised blocks.

But, nonetheless, all of this still depends on how much you "weaken" the threat model and capabilities of your proposed attacker(s).