search

Percona-Lab / pg_tde

MIT License
107 stars 19 forks source link

Repeated use of AES-CTR on the same block is vulnerable to a chosen-plaintext attack #112

Closed mpalmer closed 7 months ago

mpalmer commented 8 months ago

AES-CTR, as with all stream ciphers (and block cipher modes that emulate a stream cipher) is vulnerable to key stream recovery if the same key stream is used to encrypt multiple blocks of data, when at least one of the encryptions is over a known plaintext (either predictable, such as all-zeroes, or provided by an attacker).

The vulnerability comes from the fact that the per-block key, which I'll call X, is statically derived from the encryption of the block counter with the main key. The stored ciphertext is simply the XOR of the plaintext, P, with the per-block key, X, to produce C. If plaintext P is known, the per-block key X can be trivially recovered with C XOR X. This allows all other encryptions of the same block to be decrypted with C_n XOR X.

The most appropriate solution to this problem would be to switch to using a tweakable cipher mode, such as AES-XTS, for which there is an existing OpenSSL function, EVP_aes_128_xts.

dutow commented 8 months ago

Hello @mpalmer!

Thank you for the feedback. Generally you are right about the vulnerability of AES-CTR, but please also take into consideration the following details in our implementation:

  1. We are using separate keys for each table - the attack you describe could only happen within a specific table, not across multiple tables.
  2. Postgres generally doesn't reuse existing space, but creates new tuples in the table file, which means the updated data will use a different position value for encryption. To reuse existing space, you also have to run VACUUM for example.
  3. After we merge the currently open PR #107 we will be using a modified AES-CTR: the basic idea is the same (using an increasing sequence number, while making sure that there are no overlaps), but we are not using the offset in the file for the counter, instead it's based on the CTID for HEAP data, and the valueid for TOAST. While we implemented this change primarily for a different reason, it also improves this issue: with these changes, counter reuse will be even more limited.
  4. We are also considering adding additional field(s), for example the commandId/transactionId into the counter calculation, which would resolve the issue completely: with those also included, intentional counter reuse would be impossible.
  5. Other improvements are also on our roadmap, for example the ability to change the internal encryption key of tables periodically.

Even with the current state of things, without 4/5, the described attack is not that practical: the attacker needs the ability to run for example VACUUM FULL on the table after a known and complete modification to it - and if he can do that, we can assume that the data is already compromised. I'm not saying that it's impossible, just that it is a very unlikely and specific scenario.

As for using XTS, or any other better algorithm: our current implementation approach (minimal modifications to the heap engine at the tuple level, as an extension) leaves us with limited options. We are actively discussing other approaches, but all of those would require modifications in postgres itself. We might also go in that direction in the future, but one of the requirements for this extension is that it works with postgres without any modifications.