Re: [Proposal] Table-level Transparent Data Encryption (TDE) and KeyManagement Service (KMS)

On Wed, Aug  7, 2019 at 08:56:18AM -0400, Sehrope Sarkuni wrote:
> On Mon, Aug 5, 2019 at 9:02 PM Bruce Momjian <bruce@momjian.us> wrote:
> 
>     On Wed, Jul 31, 2019 at 09:25:01AM -0400, Sehrope Sarkuni wrote:
>     > Even if we do not include a separate per-relation salt or things like
>     > relfilenode when generating a derived key, we can still include other
>     types of
>     > immutable attributes. For example the fork type could be included to
>     eventually
>     > allow multiple forks for the same relation to be encrypted with the same
>     IV =
>     > LSN + Page Number as the derived key per-fork would be distinct.
> 
>     Yes, the fork number could be useful in this case.  I was thinking we
>     would just leave the extra bits as zeros and we can then set it to '1'
>     or something else for a different fork.
> 
> 
> Key derivation has more flexibility as you're not limited by the number of
> unused bits in the IV.

Understood, though I was not aware of the usefulness of key derivation
until this thread.

>     > WAL encryption should not use the same key as page encryption so there's
>     no
>     > need to design the IV to try to avoid matching the page IVs. Even a basic
>     > derivation with a single fixed WDEK = HKDF(MDEK, "WAL") and TDEK = HKDF
>     (MDEK,
>     > "PAGE") would ensure separate keys. That's the the literal string "WAL"
>     or
>     > "PAGE" being added as a salt to generate the respective keys, all that
>     matters
>     > is they're different.
> 
>     I was thinking the WAL would use the same key since the nonce is unique
>     between the two.  What value is there in using a different key?
> 
> 
> Never having to worry about overlap in Key + IV usage is main advantage. While
> it's possible to structure IVs to avoid that from happening, it's much easier
> to completely avoid that situation by ensuring different parts of an
> application are using separate derived keys.

Understood.

>     > Ideally WAL encryption would generating new derived keys as part of the
>     WAL
>     > stream. The WAL stream is not fixed so you have the luxury of being able
>     to add
>     > a "Use new random salt XZY going forward" records. Forcing generation of
>     a new
>     > salt/key upon promotion of a replica would ensure that at least the WAL
>     is
>     > unique going forward. Could also generate a new upon server startup,
>     after
> 
>     Ah, yes, good point, and using a derived key would make that easier.
>     The tricky part is what to use to create the new derived key, unless we
>     generate a random number and store that somewhere in the data directory,
>     but that might lead to fragility, so I am worried. 
> 
> 
> Simplest approach for derived keys would be to use immutable attributes of the
> WAL files as an input to the key derivation. Something like HKDF(MDEK, "WAL:" |

So, I am thinking we should use "WAL:" for WAL and "REL:" for heap/index
files.

> | timeline_id || wal_segment_num) should be fine for this as it is:

I considered using the timeline in the nonce, but then remembered that
in timeline switch, we _copy_ the part of the old WAL up to the timeline
switch to the new timeline;  see:


https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/access/transam/xlog.c;h=f55352385732c6b0124eff5265462f3883fe7435;hb=HEAD#l5502

   * Initialize the starting WAL segment for the new timeline. If the switch
   * happens in the middle of a segment, copy data from the last WAL segment
   * of the old timeline up to the switch point, to the starting WAL segment
   * on the new timeline.

We would need to decrypt/encrypt to do the copy, and just wasn't sure of
the value of the timeline in the nonce.  One value to it is that if
there some WAL that generated after the timeline switch in the old
primary that isn't transfered, there would be potentially new data
encrypted with the same key/nonce in the new primary, but if that WAL is
not used, odds are it is gone/destroyed/inaccessible, or it would have
been used during the switchover, so it didn't seem worth worrying about.

One _big_ reason to add the timeline is if you had a standby that you
recovered and rolled forward only to a specific transaction, then
continued running it as a new primary.  In that case, you would have
different WAL encrypted with the same key/nonce, but that sounds like
the same as promoting two standbys, and we should just document not to
do it.

Maybe we need to consider this further.

> * Unique per WAL file
> * Known prior to writing to a given WAL file
> * Known prior to reading a given WAL file
> * Does not require any additional persistence

Agreed.

>     We have pg_rewind,
>     which allows to make the WAL go backwards.  What is the value in doing
>     this?
> 
> 
> Good point re: pg_rewind. Having key rotation records in the stream would
> complicate that as you'd have to jump back / forward to figure out which key to
> use. It's doable but much more complicated.

Yep.

> A unique WDEK per WAL file that is derived from the segment number would not
> have that problem. A unique key per-file means the IVs can all start at zero
> and the each file can be treated as one encrypted stream. Any encryption/
> decryption code would only need to touch the write/read callsites.

So, I am now wondering when we should be using a non-zero nonce to
start, and when we should be using derived keys.   Should we add the
page-number to the derived key for heap/index files too and just use the
LSN for nonce, or add the LSN to the derived key too?

>     > every N bytes, or a new one for each new WAL file. There's much more
>     > flexibility compared to page encryption.
>     >
>     > As WAL is a single continuous stream, we can start the IV for each
>     derived WAL
>     > key from zero. There's no need to complicate it further as Key + IV will
>     never
>     > be reused.
> 
>     Uh, you want a new random key for each WAL file?  I was going to use the
>     WAL segment number as the nonce, which is always increasing, and easily
>     determined.  The file is 16MB.
> 
> Ideally yes as it would allow for multiple replicas promoted off the same
> primary to immediately diverge as each would have its own keys. I don't
> consider it a requirement but if it's possible without significant added
> complexity I say that's a win.

Yeah, it is probably lots of added complexity, and there would be
duplicates unless we got random numbers for heap/index pages too.  We
would then have to modify the heap/index page format, and then the
non-encrypted format might not fit in the encrypted format, and then we
can't do the conversion offline --- as you can see, the negatives pile
up.
 
> I'm still reading up on the file and record format to understand how complex
> that would be. Though given your point re: pg_rewind and the lack of handling
> for page encryption divergence when promoting multiple replicas, I doubt the
> complexity will be worth it.

Yep, there is _ideal_, and what is reasonable complexity to implement in
Postgres, while still remaining secure.

>     > If WAL is always written as full pages we need to ensure that the empty
>     parts
>     > of the page are actual zeros and not "encrypted zeroes". Otherwise an XOR
>     of
>     > the empty section of the first write of a page against a subsequent one
>     would
>     > give you the plain text.
> 
>     Right, I think we need the segment number as part of the nonce for WAL.
>
> +1 to using segment number but it's better as a derived key instead of coming
> up with new IV constructs and reusing the MDEK.

OK.

>     > The non-fixed size of the WAL allows for the addition of a MAC though I'm
>     not
>     > sure yet the best way to incorporate it. It could be part of each
>     encrypted
>     > record or its own summary record (providing a MAC for a series of WAL
>     records).
>     > After I've gone through this a bit more I'm looking to put together a
>     write up
>     > with this and some other thoughts in one place.
> 
>     I don't think we want to add a MAC at this point since the MAC for 8k
>     pages seems unattainable.
> 
> Even without a per-page MAC, a MAC at some level for WAL has its own benefits
> such as perfect corruption detection. It could be per-record, per-N-records,
> per-checkpoint, or per-file. The current WAL file format already handles
> arbitrary gaps so there is significantly more flexibility in adding it vs
> pages. I'm not saying it should be a requirement but, unlike pages, I would not
> rule it out just yet as it may not be that complicated.

We already have a CRC in the WAL that detects corruption, and that would
be encrypted, so it is a MAC.  It is an int32, so twice as many bits as
the heap/index page CRC --- better, but not great.  It would be pretty
trivial to increase that to 64 bite if desired.

-- 
  Bruce Momjian  <bruce@momjian.us>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +