XTS cipher mode for cluster file encryption

Greetings,

* Bruce Momjian (bruce@momjian.us) wrote:

As you might have seen from my email in another thread, thanks to
Stephen and Cybertec staff, I am back working on cluster file
encryption/TDE.

Stephen was going to research if XTS cipher mode would be a good fit for
this since it was determined that CTR cipher mode was too vulnerable to
IV reuse, and the LSN provides insufficient uniqueness. Stephen
reported having trouble finding a definitive answer, so I figured I
would research it myself.

Of course, I found the same lack of information that Stephen did. ;-)
None of my classic cryptographic books cover XTS or the XEX encryption
mode it is based on, since XTS was only standardized in 2007 and
recommended in 2010. (Yeah, don't get me started on poor cryptographic
documentation.)

Therefore, I decide to go backward and look at CTR and CBC to see how
the nonce is used there, and if XTS fixes problems with nonce reuse.

First, I originally chose CTR mode since it was a streaming cipher, and
we therefore could skip certain page fields like the LSN. However, CTR
is very sensitive to LSN reuse since the input bits generate encrypted
bits in exactly the same locations on the page. (It uses a simple XOR
against a cipher). Since sometimes pages with different page contents
are encrypted with the same LSN, especially on replicas, this method
failed.

Second is CBC mode. which is a block cipher. I thought that meant that
you could only encrypt 16-byte chunks, meaning you couldn't skip
encryption of certain page fields unless they are 16-byte chunks.
However, there is something called ciphertext stealing
(https://en.wikipedia.org/wiki/Ciphertext_stealing#CBC_ciphertext_stealing)
which allows that. I am not sure if OpenSSL supports this, but looking
at my OpenSSL 1.1.1d manual entry for EVP_aes, cipher stealing is only
mentioned for XTS.

Anyway, CBC mode still needs a nonce for the first 16-byte block, and
then feeds the encrypted output of the first block as a IV to the second
block, etc. This gives us the same problem with finding a nonce per
page. However, since it is a block cipher, the bits don't output in the
same locations they have on input, so that is less of a problem. There
is also the problem that the encrypted output from one 16-byte block
could repeat, causing leakage.

So, let's look how XTS is designed. First, it uses two keys. If you
are using AES128, you need _two_ 128-bit keys. If using AES256, you
need two 256-bit keys. The first of the two keys is used like normal,
to encrypt the data. The second key, which is also secret, is used to
encrypt the values used for the IV for the first 16-byte block (in our
case dboid, relfilenode, blocknum, maybe LSN). This is most clearly
explained here:

https://www.kingston.com/unitedstates/en/solutions/data-security/xts-encryption

That IV is XOR'ed against both the input value and the encryption output
value, as explained here as key tweaking:

https://crossbowerbt.github.io/xts_mode_tweaking.html

The purpose of using it before and after encryption is explained here:

https://crypto.stackexchange.com/questions/24431/what-is-the-benefit-of-applying-the-tweak-a-second-time-using-xts

The second 16-byte block gets an IV that is the multiplication of the
first IV and an alpha value raised to the second power but mapped to a
finite field (Galois field, modulus a prime). This effectively means an
attacker has _no_ idea what the IV is since it involves a secret key,
and each 16-byte block uses a different, unpredictable IV value. XTS
also supports ciphertext stealing by default so we can use the LSN if we
want, but we aren't sure we need to.

Yeah, this all seems to be about where I got to too.

Finally, there is an interesting web page about when not to use XTS:

https://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

This particular article always struck me as more of a reason for us, at
least, to use XTS than to not- in particular the very first comment it
makes, which seems to be pretty well supported, is: "XTS is the de-facto
standard disk encryption mode." Much of the rest of it is the well
trodden discussion we've had about how FDE (or TDE in our case) doesn't
protect against all the attack vectors that sometimes people think it
does. Another point is that XTS isn't authenticated- something else we
know quite well around here and isn't news.

Basically, what XTS does is to make the IV unknown to attackers and
non-repeating except for multiple writes to a specific 16-byte block
(with no LSN change). What isn't clear is if repeated encryption of
different data in the same 16-byte block can leak data.

Any time a subset of the data is changed but the rest of it isn't,
there's a leak of information. This is a really good example of exactly
what that looks like:

https://github.com/robertdavidgraham/ecb-penguin

In our case, if/when this happens (no LSN change, repeated encryption
of the same block), someone might be able to deduce that hint bits were
being updated/changed, and where some of those are in the block.

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

This probably needs more research and maybe we need to write something
up like the above and let security researchers review it since there
doesn't seem to be enough documentation for us to decide ourselves.

The one issue identified here is hopefully answered above and given that
what you've found matches what I found, I'd argue that moving forward
with XTS makes sense.

The other bit of research that I wanted to do, and thanks for sending
this and prodding me to go do so, was to look at other implementations
and see what they do for the IV when it comes to using XTS, and this is
what I found:

https://wiki.gentoo.org/wiki/Dm-crypt_full_disk_encryption

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Now, to address the concern around re-encrypting a block with the same
key+IV but different data and leaking what parts of the page changed, I
do think we should use the LSN and have it change regularly (including
unlogged tables) but that's just because it's relatively easy for us to
do and means an attacker wouldn't be able to tell what part of the page
changed when the LSN was also changed. That was also recommended by
NIST and that's a pretty strong endorsement also.

I'm all for getting security folks and whomever else to come and review
this thread and chime in with their thoughts, but I don't think it's a
reason to hold off on moving forward with the approach that we've been
converging towards.

Thanks!

Stephen

On 10/15/21 21:22, Stephen Frost wrote:

Greetings,

* Bruce Momjian (bruce@momjian.us) wrote:

As you might have seen from my email in another thread, thanks to
Stephen and Cybertec staff, I am back working on cluster file
encryption/TDE.

Stephen was going to research if XTS cipher mode would be a good fit for
this since it was determined that CTR cipher mode was too vulnerable to
IV reuse, and the LSN provides insufficient uniqueness. Stephen
reported having trouble finding a definitive answer, so I figured I
would research it myself.

Of course, I found the same lack of information that Stephen did. ;-)
None of my classic cryptographic books cover XTS or the XEX encryption
mode it is based on, since XTS was only standardized in 2007 and
recommended in 2010. (Yeah, don't get me started on poor cryptographic
documentation.)

Therefore, I decide to go backward and look at CTR and CBC to see how
the nonce is used there, and if XTS fixes problems with nonce reuse.

First, I originally chose CTR mode since it was a streaming cipher, and
we therefore could skip certain page fields like the LSN. However, CTR
is very sensitive to LSN reuse since the input bits generate encrypted
bits in exactly the same locations on the page. (It uses a simple XOR
against a cipher). Since sometimes pages with different page contents
are encrypted with the same LSN, especially on replicas, this method
failed.

Second is CBC mode. which is a block cipher. I thought that meant that
you could only encrypt 16-byte chunks, meaning you couldn't skip
encryption of certain page fields unless they are 16-byte chunks.
However, there is something called ciphertext stealing
(https://en.wikipedia.org/wiki/Ciphertext_stealing#CBC_ciphertext_stealing)
which allows that. I am not sure if OpenSSL supports this, but looking
at my OpenSSL 1.1.1d manual entry for EVP_aes, cipher stealing is only
mentioned for XTS.

Anyway, CBC mode still needs a nonce for the first 16-byte block, and
then feeds the encrypted output of the first block as a IV to the second
block, etc. This gives us the same problem with finding a nonce per
page. However, since it is a block cipher, the bits don't output in the
same locations they have on input, so that is less of a problem. There
is also the problem that the encrypted output from one 16-byte block
could repeat, causing leakage.

So, let's look how XTS is designed. First, it uses two keys. If you
are using AES128, you need _two_ 128-bit keys. If using AES256, you
need two 256-bit keys. The first of the two keys is used like normal,
to encrypt the data. The second key, which is also secret, is used to
encrypt the values used for the IV for the first 16-byte block (in our
case dboid, relfilenode, blocknum, maybe LSN). This is most clearly
explained here:

https://www.kingston.com/unitedstates/en/solutions/data-security/xts-encryption

That IV is XOR'ed against both the input value and the encryption output
value, as explained here as key tweaking:

https://crossbowerbt.github.io/xts_mode_tweaking.html

The purpose of using it before and after encryption is explained here:

https://crypto.stackexchange.com/questions/24431/what-is-the-benefit-of-applying-the-tweak-a-second-time-using-xts

The second 16-byte block gets an IV that is the multiplication of the
first IV and an alpha value raised to the second power but mapped to a
finite field (Galois field, modulus a prime). This effectively means an
attacker has _no_ idea what the IV is since it involves a secret key,
and each 16-byte block uses a different, unpredictable IV value. XTS
also supports ciphertext stealing by default so we can use the LSN if we
want, but we aren't sure we need to.

Yeah, this all seems to be about where I got to too.

Finally, there is an interesting web page about when not to use XTS:

https://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

This particular article always struck me as more of a reason for us, at
least, to use XTS than to not- in particular the very first comment it
makes, which seems to be pretty well supported, is: "XTS is the de-facto
standard disk encryption mode." Much of the rest of it is the well
trodden discussion we've had about how FDE (or TDE in our case) doesn't
protect against all the attack vectors that sometimes people think it
does. Another point is that XTS isn't authenticated- something else we
know quite well around here and isn't news.

Basically, what XTS does is to make the IV unknown to attackers and
non-repeating except for multiple writes to a specific 16-byte block
(with no LSN change). What isn't clear is if repeated encryption of
different data in the same 16-byte block can leak data.

Any time a subset of the data is changed but the rest of it isn't,
there's a leak of information. This is a really good example of exactly
what that looks like:

https://github.com/robertdavidgraham/ecb-penguin

In our case, if/when this happens (no LSN change, repeated encryption
of the same block), someone might be able to deduce that hint bits were
being updated/changed, and where some of those are in the block.

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

Yeah. With CTR you pretty learn where the hint bits are exactly, while
with XTS the whole ciphertext changes.

This also means CTR is much more malleable, i.e. you can tweak the
ciphertext bits to flip the plaintext, while with XTS that's not really
possible - it's pretty much guaranteed to break the block structure. Not
sure if that's an issue for our use case, but if it is then neither of
the two modes is a solution.

This probably needs more research and maybe we need to write something
up like the above and let security researchers review it since there
doesn't seem to be enough documentation for us to decide ourselves.

The one issue identified here is hopefully answered above and given that
what you've found matches what I found, I'd argue that moving forward
with XTS makes sense.

+1

The other bit of research that I wanted to do, and thanks for sending
this and prodding me to go do so, was to look at other implementations
and see what they do for the IV when it comes to using XTS, and this is
what I found:

https://wiki.gentoo.org/wiki/Dm-crypt_full_disk_encryption

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Seems reasonable, on the assumption the threat models are the same.

Now, to address the concern around re-encrypting a block with the same
key+IV but different data and leaking what parts of the page changed, I
do think we should use the LSN and have it change regularly (including
unlogged tables) but that's just because it's relatively easy for us to
do and means an attacker wouldn't be able to tell what part of the page
changed when the LSN was also changed. That was also recommended by
NIST and that's a pretty strong endorsement also.

Not sure - it seems a bit weird to force LSN change even in cases that
don't generate any WAL. I was not following the encryption thread and
maybe it was discussed/rejected there, but I've always imagined we'd
have a global nonce generator (similar to a sequence) and we'd store it
at the end of each block, or something like that.

I'm all for getting security folks and whomever else to come and review
this thread and chime in with their thoughts, but I don't think it's a
reason to hold off on moving forward with the approach that we've been
converging towards.

+1

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

--
Robert Haas
EDB: http://www.enterprisedb.com

Hi,

On 2021-10-15 15:22:48 -0400, Stephen Frost wrote:

* Bruce Momjian (bruce@momjian.us) wrote:

Finally, there is an interesting web page about when not to use XTS:

https://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

This particular article always struck me as more of a reason for us, at
least, to use XTS than to not- in particular the very first comment it
makes, which seems to be pretty well supported, is: "XTS is the de-facto
standard disk encryption mode."

I don't find that line of argument *that* convincing. The reason XTS is the
de-facto standard is that for generic block layer encryption is that you can't
add additional data for each block without very significant overhead
(basically needing journaling to ensure that the data doesn't get out of
sync). But we don't really face the same situation - we *can* add additional
data.

With something like AES-GCM-SIV we can use the additional data to get IV reuse
resistance *and* authentication. And while perhaps we are ok with the IV reuse
guarantees XTS has, it seems pretty clear that we'll want want guaranteed
authenticity at some point. And then we'll need extra data anyway.

Thus, to me, it doesn't seem worth going down the XTS route, just to
temporarily save a bit of implementation effort. We'll have to endure that
pain anyway.

Greetings,

Andres Freund

On 10/15/21 23:02, Robert Haas wrote:

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

TrueCrypt/VeraCrypt uses XTS too, I think. There's an overview of other
FDE products at [1]https://en.wikipedia.org/wiki/Comparison_of_disk_encryption_software, and some of them use XTS, but I would take that
with a grain of salt - some of the products are somewhat obscure, very
old, or both.

What is probably more interesting is that there's an IEEE standard [2]https://en.wikipedia.org/wiki/IEEE_P1619
dealing with encrypted shared storage, and that uses XTS too. I'd bet
there's a bunch of smart cryptographers involved.

[1]: https://en.wikipedia.org/wiki/Comparison_of_disk_encryption_software

[2]: https://en.wikipedia.org/wiki/IEEE_P1619

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

I haven't been following the discussion about using LSN, but I agree
that while using it seems convenient, the consequences of some changes
not incrementing LSN seem potentially disastrous, depending on the
encryption mode.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Oct 15, 2021 at 10:57:03PM +0200, Tomas Vondra wrote:

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

Yeah. With CTR you pretty learn where the hint bits are exactly, while with
XTS the whole ciphertext changes.

This also means CTR is much more malleable, i.e. you can tweak the
ciphertext bits to flip the plaintext, while with XTS that's not really
possible - it's pretty much guaranteed to break the block structure. Not
sure if that's an issue for our use case, but if it is then neither of the
two modes is a solution.

Yes, this is a vary good point. Let's look at the impact of _not_ using
the LSN. For CTR (already rejected) bit changes would be visible by
comparing old/new page contents. For CBC (also not under consideration)
the first 16-byte block would show a change, and all later 16-byte
blocks would show a change. For CBC, you see the 16-byte blocks change,
but you have no idea how many bits were changed, and in what locations
in the 16-byte block (AES uses substitution and diffusion). For XTS,
because earlier blocks don't change the IV used by later blocks like
CBC, you would be able to see each 16-byte block that changed in the 8k
page. Again, you would not know the number of bits changed or their
locations.

Do we think knowing which 16-byte blocks on an 8k page change would leak
useful information? If so, we should use the LSN and just accept that
some cases might leak as described above. If we don't care, then we can
skip the use of the LSN and simplify the patch.

Not sure - it seems a bit weird to force LSN change even in cases that don't
generate any WAL. I was not following the encryption thread and maybe it was
discussed/rejected there, but I've always imagined we'd have a global nonce
generator (similar to a sequence) and we'd store it at the end of each
block, or something like that.

Storing the nonce in the page means more code complexity, possible
performance impact, and the inability to create standbys via binary
replication that use cluster file encryption.

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

--
Bruce Momjian <bruce@momjian.us> https://momjian.us
EDB https://enterprisedb.com

If only the physical world exists, free will is an illusion.

Hi,

On 2021-10-16 10:16:25 -0400, Bruce Momjian wrote:

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

You're just deferring / hiding the complexity. For one, we'll need integrity
before long if we add encryption support. Then we'll deal with a more complex
on-disk format because there will be two different ways of encrypting. For
another, you're spreading out the security analysis to a lot of places in the
code and more importantly to future changes affecting on-disk data.

If it's really just a checkbox feature without a real use case, then we should
just reject requests for it and use our energy for useful things.

Greetings,

Andres Freund

On Sat, Oct 16, 2021 at 09:15:05AM -0700, Andres Freund wrote:

Hi,

On 2021-10-16 10:16:25 -0400, Bruce Momjian wrote:

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

You're just deferring / hiding the complexity. For one, we'll need integrity
before long if we add encryption support. Then we'll deal with a more complex
on-disk format because there will be two different ways of encrypting. For
another, you're spreading out the security analysis to a lot of places in the
code and more importantly to future changes affecting on-disk data.

If it's really just a checkbox feature without a real use case, then we should
just reject requests for it and use our energy for useful things.

Agreed. That is the conclusion I came to in May:

/messages/by-id/20210526210201.GZ3048@momjian.us
/messages/by-id/20210527160003.GF5646@momjian.us

--
Bruce Momjian <bruce@momjian.us> https://momjian.us
EDB https://enterprisedb.com

If only the physical world exists, free will is an illusion.

On 10/16/21 16:16, Bruce Momjian wrote:

On Fri, Oct 15, 2021 at 10:57:03PM +0200, Tomas Vondra wrote:

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

Yeah. With CTR you pretty learn where the hint bits are exactly, while with
XTS the whole ciphertext changes.

This also means CTR is much more malleable, i.e. you can tweak the
ciphertext bits to flip the plaintext, while with XTS that's not really
possible - it's pretty much guaranteed to break the block structure. Not
sure if that's an issue for our use case, but if it is then neither of the
two modes is a solution.

Yes, this is a vary good point. Let's look at the impact of _not_ using
the LSN. For CTR (already rejected) bit changes would be visible by
comparing old/new page contents. For CBC (also not under consideration)
the first 16-byte block would show a change, and all later 16-byte
blocks would show a change. For CBC, you see the 16-byte blocks change,
but you have no idea how many bits were changed, and in what locations
in the 16-byte block (AES uses substitution and diffusion). For XTS,
because earlier blocks don't change the IV used by later blocks like
CBC, you would be able to see each 16-byte block that changed in the 8k
page. Again, you would not know the number of bits changed or their
locations.

Do we think knowing which 16-byte blocks on an 8k page change would leak
useful information? If so, we should use the LSN and just accept that
some cases might leak as described above. If we don't care, then we can
skip the use of the LSN and simplify the patch.

Not sure - it seems a bit weird to force LSN change even in cases that don't
generate any WAL. I was not following the encryption thread and maybe it was
discussed/rejected there, but I've always imagined we'd have a global nonce
generator (similar to a sequence) and we'd store it at the end of each
block, or something like that.

Storing the nonce in the page means more code complexity, possible
performance impact, and the inability to create standbys via binary
replication that use cluster file encryption.

Would it really be that complex? Reserving a bunch of bytes at the end
of each encrypted page (a bit like the "special" space, but after
encryption) seems fairly straightforward. And I don't quite see why
would this have a measurable impact, given the nonce is 16B at most. The
encryption is likely way more expensive.

Moreover, it seems fairly reasonable to trade a bit of code complexity
for something LSN-based which seems simpler but apparently has various
weak points and is much harder to reason about.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 10/16/21 18:28, Bruce Momjian wrote:

On Sat, Oct 16, 2021 at 09:15:05AM -0700, Andres Freund wrote:

Hi,

On 2021-10-16 10:16:25 -0400, Bruce Momjian wrote:

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

You're just deferring / hiding the complexity. For one, we'll need integrity
before long if we add encryption support. Then we'll deal with a more complex
on-disk format because there will be two different ways of encrypting. For
another, you're spreading out the security analysis to a lot of places in the
code and more importantly to future changes affecting on-disk data.

I've argued for storing the nonce, but I don't quite see why would we
need integrity guarantees?

AFAICS the threat model the patch aims to address is an attacker who can
observe the data (e.g. a low-privileged OS user), but can't modify the
files. Which seems like a reasonable model for shared environments.

IMO extending this to cases where the attacker can modify the data moves
the goalposts quite significantly. And it's quite possible authenticated
encryption would not be enough to prevent that, because that still works
only at block level, and you can probably do a lot of harm with replay
attacks (e.g. replacing blocks with older versions). And if you can
modify the data directory / config files, what are the chances you can't
just get access to the database, trace the processes or whatever?

We already have a way to check integrity by storing page checksum, but
I'm not sure if that's good enough (there's a lot of subtle issues with
building proper AEAD scheme).

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Just a mention. the HMAC (or AE/AD) can be disabled in AES-GCM. HMAC in
AES-GCM is an encrypt-then-hash MAC.

CRC-32 is not a crypto-safe hash (technically CRC-32 is not a hash
function). Cryptographers may unhappy with CRC-32.

I think CRC or SHA is not such important. If IV can be stored, I believe
there should have enough space to store HMAC.

Show quoted text

On 2021/10/18 05:23, Tomas Vondra wrote:

I've argued for storing the nonce, but I don't quite see why would we
need integrity guarantees?

On 2021/10/16 04:57, Tomas Vondra wrote:

Seems reasonable, on the assumption the threat models are the same.

On 2021/10/16 03:22, Stephen Frost wrote:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement

On 2021/10/18 05:23, Tomas Vondra wrote:

AFAICS the threat model the patch aims to address is an attacker who can
observe the data (e.g. a low-privileged OS user), but can't modify the
files. Which seems like a reasonable model for shared environments.

I agree this threat model.

And if PostgreSQL is using XTS, there is no different with dm-encrypt.
The user can use dm-encrypt directly.

Greetings,

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/15/21 21:22, Stephen Frost wrote:

Now, to address the concern around re-encrypting a block with the same
key+IV but different data and leaking what parts of the page changed, I
do think we should use the LSN and have it change regularly (including
unlogged tables) but that's just because it's relatively easy for us to
do and means an attacker wouldn't be able to tell what part of the page
changed when the LSN was also changed. That was also recommended by
NIST and that's a pretty strong endorsement also.

Not sure - it seems a bit weird to force LSN change even in cases that don't
generate any WAL. I was not following the encryption thread and maybe it was
discussed/rejected there, but I've always imagined we'd have a global nonce
generator (similar to a sequence) and we'd store it at the end of each
block, or something like that.

The 'LSN' being referred to here isn't the regular LSN that is
associated with the WAL but rather the separate FakeLSN counter which we
already have. I wasn't suggesting having the regular LSN change in
cases that don't generate WAL.

* Robert Haas (robertmhaas@gmail.com) wrote:

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

This argument doesn't come across as very strong at all to me,
particularly when we have explicit recommendations from NIST that having
the IV vary more is beneficial. While this would be using the LSN, the
fact that the LSN changes most of the time but not all of the time isn't
new and is something we already have to deal with. I'd think we'd
address the concern about mis-thinking around how this works by
providing a README and/or an appropriate set of comments around what's
being done and why.

* Andres Freund (andres@anarazel.de) wrote:

On 2021-10-15 15:22:48 -0400, Stephen Frost wrote:

* Bruce Momjian (bruce@momjian.us) wrote:

Finally, there is an interesting web page about when not to use XTS:

https://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

This particular article always struck me as more of a reason for us, at
least, to use XTS than to not- in particular the very first comment it
makes, which seems to be pretty well supported, is: "XTS is the de-facto
standard disk encryption mode."

I don't find that line of argument *that* convincing. The reason XTS is the
de-facto standard is that for generic block layer encryption is that you can't
add additional data for each block without very significant overhead
(basically needing journaling to ensure that the data doesn't get out of
sync). But we don't really face the same situation - we *can* add additional
data.

No, we can't always add additional data, and that's part of the
consideration for an XTS option- there are things we can do if we use
XTS that we can't with GCM or another solution. Specifically, being
able to perform physical replication from an unencrypted cluster to an
encrypted one is a worthwhile use-case that we shouldn't be just tossing
out.

With something like AES-GCM-SIV we can use the additional data to get IV reuse
resistance *and* authentication. And while perhaps we are ok with the IV reuse
guarantees XTS has, it seems pretty clear that we'll want want guaranteed
authenticity at some point. And then we'll need extra data anyway.

I agree that it'd be useful to have an authenticated encryption option.
Implementing XTS doesn't preclude us from adding that capability down
the road and it's simpler with fewer dependencies. These all strike me
as good reasons to add XTS first.

Thus, to me, it doesn't seem worth going down the XTS route, just to
temporarily save a bit of implementation effort. We'll have to endure that
pain anyway.

This isn't a valid argument as it isn't just about implementation but
about the capabilities we will have once it's done.

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/15/21 23:02, Robert Haas wrote:

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

TrueCrypt/VeraCrypt uses XTS too, I think. There's an overview of other FDE
products at [1], and some of them use XTS, but I would take that with a
grain of salt - some of the products are somewhat obscure, very old, or
both.

What is probably more interesting is that there's an IEEE standard [2]
dealing with encrypted shared storage, and that uses XTS too. I'd bet
there's a bunch of smart cryptographers involved.

Thanks for finding those and linking to them, that's helpful.

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

I haven't been following the discussion about using LSN, but I agree that
while using it seems convenient, the consequences of some changes not
incrementing LSN seem potentially disastrous, depending on the encryption
mode.

Yes, this depends on the encryption mode, and is why we are specifically
talking about XTS here as it's an encryption mode that doesn't suffer
from this risk and therefore it's perfectly fine to use the LSN/FakeLSN
with XTS (and would also be alright for AES-GCM-SIV as it's specifically
designed to be resistant to IV reuse).

* Bruce Momjian (bruce@momjian.us) wrote:

On Fri, Oct 15, 2021 at 10:57:03PM +0200, Tomas Vondra wrote:

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

Yeah. With CTR you pretty learn where the hint bits are exactly, while with
XTS the whole ciphertext changes.

This also means CTR is much more malleable, i.e. you can tweak the
ciphertext bits to flip the plaintext, while with XTS that's not really
possible - it's pretty much guaranteed to break the block structure. Not
sure if that's an issue for our use case, but if it is then neither of the
two modes is a solution.

Yes, this is a vary good point. Let's look at the impact of _not_ using
the LSN. For CTR (already rejected) bit changes would be visible by
comparing old/new page contents. For CBC (also not under consideration)
the first 16-byte block would show a change, and all later 16-byte
blocks would show a change. For CBC, you see the 16-byte blocks change,
but you have no idea how many bits were changed, and in what locations
in the 16-byte block (AES uses substitution and diffusion). For XTS,
because earlier blocks don't change the IV used by later blocks like
CBC, you would be able to see each 16-byte block that changed in the 8k
page. Again, you would not know the number of bits changed or their
locations.

Do we think knowing which 16-byte blocks on an 8k page change would leak
useful information? If so, we should use the LSN and just accept that
some cases might leak as described above. If we don't care, then we can
skip the use of the LSN and simplify the patch.

While there may not be an active attack against PG that leverages such a
leak, I have a hard time seeing why we would intentionally design this
in when we have a great option that's directly available to us and
doesn't cause such a leak with nearly such regularity as not using the
LSN would, and also follows recommendations of using XTS from NIST.
Further, not using the LSN wouldn't really be an option if we did
eventually implement AES-GCM-SIV, so why not have the two cases be
consistent?

Not sure - it seems a bit weird to force LSN change even in cases that don't
generate any WAL. I was not following the encryption thread and maybe it was
discussed/rejected there, but I've always imagined we'd have a global nonce
generator (similar to a sequence) and we'd store it at the end of each
block, or something like that.

Storing the nonce in the page means more code complexity, possible
performance impact, and the inability to create standbys via binary
replication that use cluster file encryption.

Right- the point of XTS is that we can do things that we can't with GCM
and that it's simpler.

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

That's an argument based on how things stand today. I appreciate that
it's no small thing to consider changes to those other systems but I
would argue that having authentication of the heap is still better than
not (but also agree that XTS is simpler to implement and therefore makes
sense to do first and see how things stand after that's done). Surely,
we would want progress made here to be done so incrementally as a patch
that attempted to change all of those other systems to be encrypted and
authenticated with AES-GCM-SIV would be far too large to consider in one
shot anyway.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

Presuming that 'checkbox feature' here means "we need it to please
$someone but no one will ever use it" or something along those lines,
this is very clearly not the case and therefore we shouldn't be
describing it or treating it as such. Even if the meaning here is
"there's other ways people could get this capability" the reality is
that those other methods are simply not always available and in those
cases, people will choose to not use PostgreSQL. Nearly every other
database system which we might compare ourselves to has a solution in
this area and people actively use those solutions in a lot of
deployments.

* Andres Freund (andres@anarazel.de) wrote:

On 2021-10-16 10:16:25 -0400, Bruce Momjian wrote:

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

You're just deferring / hiding the complexity. For one, we'll need integrity
before long if we add encryption support. Then we'll deal with a more complex
on-disk format because there will be two different ways of encrypting. For
another, you're spreading out the security analysis to a lot of places in the
code and more importantly to future changes affecting on-disk data.

I don't follow this argument. The XTS approach is explicitly the same
on-disk format as what we have unencrypted today, just encrypted, and
that's the whole point of going with that approach. If we were to
implement AES-GCM-SIV, then that would introduce a new on-disk format
and then we'd have two- one which has space on each page for the
authentication information, and one which doesn't.

If it's really just a checkbox feature without a real use case, then we should
just reject requests for it and use our energy for useful things.

This capability certainly has a real use-case and it's one that a lot of
organizations are looking for PG to provide a solution for. That we
don't today is keeping those organizations from using PG in at least
some cases, and for some organizations, it prevents them from using PG
at all, as they understandably would rather not deal with a hybrid of
using PG for some things and having to use another solution for other
things.

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/16/21 16:16, Bruce Momjian wrote:

Storing the nonce in the page means more code complexity, possible
performance impact, and the inability to create standbys via binary
replication that use cluster file encryption.

Would it really be that complex? Reserving a bunch of bytes at the end of
each encrypted page (a bit like the "special" space, but after encryption)
seems fairly straightforward. And I don't quite see why would this have a
measurable impact, given the nonce is 16B at most. The encryption is likely
way more expensive.

There's a patch to do exactly this- make space available towards the end
of the page. If we go down the route of using a different page format
then we lose the ability to do physical replication between an
unencrypted cluster and an encrypted one. That's certainly a nice
capability to have and it will help people migrate to an encrypted PG
instance, plus it's overall simpler to work with, which is also an
advantge.

Moreover, it seems fairly reasonable to trade a bit of code complexity for
something LSN-based which seems simpler but apparently has various weak
points and is much harder to reason about.

This isn't just about code complexity but is also about the resulting
capabilities from these different approaches.

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/16/21 18:28, Bruce Momjian wrote:

On Sat, Oct 16, 2021 at 09:15:05AM -0700, Andres Freund wrote:

On 2021-10-16 10:16:25 -0400, Bruce Momjian wrote:

As a final comment to Andres's email, adding a GCM has the problems
above, plus it wouldn't detect changes to pg_xact, fsm, vm, etc, which
could also affect the integrity of the data. Someone could also restore
and old copy of a patch to revert a change, and that would not be
detected even by GCM.

I consider this a checkbox feature and making it too complex will cause
it to be rightly rejected.

You're just deferring / hiding the complexity. For one, we'll need integrity
before long if we add encryption support. Then we'll deal with a more complex
on-disk format because there will be two different ways of encrypting. For
another, you're spreading out the security analysis to a lot of places in the
code and more importantly to future changes affecting on-disk data.

I've argued for storing the nonce, but I don't quite see why would we need
integrity guarantees?

AFAICS the threat model the patch aims to address is an attacker who can
observe the data (e.g. a low-privileged OS user), but can't modify the
files. Which seems like a reasonable model for shared environments.

There are multiple threat models which we should be considering and
that's why we may want to eventually add integrity.

IMO extending this to cases where the attacker can modify the data moves the
goalposts quite significantly. And it's quite possible authenticated
encryption would not be enough to prevent that, because that still works
only at block level, and you can probably do a lot of harm with replay
attacks (e.g. replacing blocks with older versions). And if you can modify
the data directory / config files, what are the chances you can't just get
access to the database, trace the processes or whatever?

I agree that working towards an authenticated solution is a larger task.
I don't agree that we should throw out the possibility that we may want
to implement it eventually as there are certainly threat models where an
attacker might have access to the storage but not to the database or the
system on which the database is running. Implementing a system to
address such an attack vector would take more consideration than just
having authenticated encryption provided by PG, but it certainly
couldn't be done without that either.

We already have a way to check integrity by storing page checksum, but I'm
not sure if that's good enough (there's a lot of subtle issues with building
proper AEAD scheme).

No, it isn't good enough.

* Sasasu (i@sasa.su) wrote:

Just a mention. the HMAC (or AE/AD) can be disabled in AES-GCM. HMAC in
AES-GCM is an encrypt-then-hash MAC.

Not sure why you would though.

CRC-32 is not a crypto-safe hash (technically CRC-32 is not a hash
function). Cryptographers may unhappy with CRC-32.

Yes, that's correct (and it isn't even CRC-32 that we have, heh).

I think CRC or SHA is not such important. If IV can be stored, I believe
there should have enough space to store HMAC.

This would be the case, yes. If we can find a way to make room for an
IV then we could make room to store the tag too, and we certainly should
(and we should include a variety of additional data in the AEAD- block
number, relfileno, etc).

* Sasasu (i@sasa.su) wrote:

On 2021/10/16 04:57, Tomas Vondra wrote:

Seems reasonable, on the assumption the threat models are the same.

On 2021/10/16 03:22, Stephen Frost wrote:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement

On 2021/10/18 05:23, Tomas Vondra wrote:

AFAICS the threat model the patch aims to address is an attacker who can
observe the data (e.g. a low-privileged OS user), but can't modify the
files. Which seems like a reasonable model for shared environments.

I agree this threat model.

And if PostgreSQL is using XTS, there is no different with dm-encrypt.
The user can use dm-encrypt directly.

dm-encrypt is not always an option and it doesn't actually address the
threat-model that Tomas brought up here anyway, as it would be below the
level that the low-privileged OS user would be looking at. That's not
the only threat model to consider, but it is one which could potentially
be addressed by either XTS or AES-GCM-SIV. There are threat models
which dm-crypt would address, of course, such as data-at-rest (hard
drive theft, improper disposal of storage media, backups which don't
have their own encryption, etc), but, again, dm-crypt isn't always an
option that is available and so I don't agree that we should throw this
out just because dm-crypt exists and may be useable in some cases.

Thanks,

Stephen

On Fri, Oct 15, 2021 at 5:21 PM Andres Freund <andres@anarazel.de> wrote:

I don't find that line of argument *that* convincing. The reason XTS is the
de-facto standard is that for generic block layer encryption is that you can't
add additional data for each block without very significant overhead
(basically needing journaling to ensure that the data doesn't get out of
sync). But we don't really face the same situation - we *can* add additional
data.

Yes. The downside is that there is some code complexity, and also some
runtime overhead even for cases that don't use encryption, because
some things that now are compile time constants might need to be
computed at runtime. That can probably be made pretty small, though.

With something like AES-GCM-SIV we can use the additional data to get IV reuse
resistance *and* authentication. And while perhaps we are ok with the IV reuse
guarantees XTS has, it seems pretty clear that we'll want want guaranteed
authenticity at some point. And then we'll need extra data anyway.

Thus, to me, it doesn't seem worth going down the XTS route, just to
temporarily save a bit of implementation effort. We'll have to endure that
pain anyway.

I agree up to a point, but I do also kind of feel like we should be
leaving it up to whoever is working on an implementation to decide
what they want to implement. I don't particularly like this discussion
where it feels like people are trying to tell other people what they
have to do because "the community has decided X." It's pretty clear
that there are multiple opinions here, and I don't really see any of
them to be without merit, nor do I see why Bruce or Stephen or you or
anyone else should get to say "what the community has decided" in the
absence of a clear consensus.

I do really like the idea of using AES-GCM-SIV not because I know
anything about it, but because the integrity checking seems cool, and
storing the nonce seems like it would improve security. However, based
on what I know now, I would not vote to reject an XTS-based patch and,
as Stephen and Bruce have said, maybe with the right design it permits
upgrades from non-encrypted clusters to encrypted clusters. I'm
actually kind of doubtful about that, because that seems to require
some pretty specific and somewhat painful implementation decisions.
For example, I think if your solution for rotating keys is to shut
down the standby, re-encrypt it with a new key, start it up again, and
fail over to it, then you probably ever can't do key rotation in any
other way. The keys now have to be non-WAL-logged so that the standby
can be different, which means you can't add a new key on the master
and run around re-encrypting everything with it, WAL-logging those
changes as you go. Now I realize that implementing that is really
challenging anyway so maybe some people wouldn't like to go that way,
but then maybe other people would. Another thing you probably can't do
in this model is encrypt different parts of the database with
different keys, because how would you keep track of that? Certainly
not in the system catalogs, if none of that can show up in the WAL
stream.

But, you know, still: if somebody showed up with a fully-working XTS
patch with everything in good working order, I don't see that we have
enough evidence to reject it just because it's XTS. And I would hope
that the people favoring XTS would not vote to reject a fully working
GCM patch just because it's GCM. I think what we ought to be doing at
this point is combining our efforts to try to get some things
committed which make future work in this area committed - like that
patch to preserve relfilenode and database OID, or maybe some patches
to drive all of our I/O through a smaller number of code paths instead
of having every different type of temporary file we write reinvent the
wheel. These discussions about what encryption type we ought to use
are useful for ruling out options that we know are bad, but beyond
that I'm not sure they have much value. AES in any mode could seem
like a much less safe choice by the time we get a committed feature
here than it does today - even if somehow that were to happen for v15.
I expect there are people out there trying to break it even as I write
these words, and it seems likely that they will eventually succeed,
but as to when, who can say?

--
Robert Haas
EDB: http://www.enterprisedb.com

On 10/18/21 04:19, Sasasu wrote:

Just a mention. the HMAC (or AE/AD) can be disabled in AES-GCM. HMAC in
AES-GCM is an encrypt-then-hash MAC.

CRC-32 is not a crypto-safe hash (technically CRC-32 is not a hash
function). Cryptographers may unhappy with CRC-32.

True. If you can flip enough bits in the page, it probably is not very
hard to generate a page with the desired checksum. It's probably harder
with XTS, but likely not much more.

I think CRC or SHA is not such important. If IV can be stored, I believe
there should have enough space to store HMAC.

Right, I agree.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 10/18/21 17:56, Stephen Frost wrote:

Greetings,

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/15/21 21:22, Stephen Frost wrote:

Now, to address the concern around re-encrypting a block with the same
key+IV but different data and leaking what parts of the page changed, I
do think we should use the LSN and have it change regularly (including
unlogged tables) but that's just because it's relatively easy for us to
do and means an attacker wouldn't be able to tell what part of the page
changed when the LSN was also changed. That was also recommended by
NIST and that's a pretty strong endorsement also.

Not sure - it seems a bit weird to force LSN change even in cases that don't
generate any WAL. I was not following the encryption thread and maybe it was
discussed/rejected there, but I've always imagined we'd have a global nonce
generator (similar to a sequence) and we'd store it at the end of each
block, or something like that.

The 'LSN' being referred to here isn't the regular LSN that is
associated with the WAL but rather the separate FakeLSN counter which we
already have. I wasn't suggesting having the regular LSN change in
cases that don't generate WAL.

I'm not very familiar with FakeLSN, but isn't that just about unlogged
tables? How does that help cases like setting hint bits, which may not
generate WAL?

* Robert Haas (robertmhaas@gmail.com) wrote:

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

Specifically: The default cipher for LUKS is nowadays aes-xts-plain64

and then this:

https://gitlab.com/cryptsetup/cryptsetup/-/wikis/DMCrypt

where plain64 is defined as:

plain64: the initial vector is the 64-bit little-endian version of the
sector number, padded with zeros if necessary

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

This argument doesn't come across as very strong at all to me,
particularly when we have explicit recommendations from NIST that having
the IV vary more is beneficial. While this would be using the LSN, the
fact that the LSN changes most of the time but not all of the time isn't
new and is something we already have to deal with. I'd think we'd
address the concern about mis-thinking around how this works by
providing a README and/or an appropriate set of comments around what's
being done and why.

I don't think anyone objects to varying IV more, as recommended by NIST.
AFAICS the issue at hand is exactly the opposite - maybe not varying it
enough, in some cases. It might be enough for MVCC purposes yet it might
result in fatal failure of the encryption scheme. That's my concern, at
least, and I assume it's what Robert meant by "fuzzy thinking" too.

FWIW I think we seem to be mixing nonces, IVs and tweak values. Although
various encryption schemes place different requirements on those anyway.

* Andres Freund (andres@anarazel.de) wrote:

On 2021-10-15 15:22:48 -0400, Stephen Frost wrote:

* Bruce Momjian (bruce@momjian.us) wrote:

Finally, there is an interesting web page about when not to use XTS:

https://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

This particular article always struck me as more of a reason for us, at
least, to use XTS than to not- in particular the very first comment it
makes, which seems to be pretty well supported, is: "XTS is the de-facto
standard disk encryption mode."

I don't find that line of argument *that* convincing. The reason XTS is the
de-facto standard is that for generic block layer encryption is that you can't
add additional data for each block without very significant overhead
(basically needing journaling to ensure that the data doesn't get out of
sync). But we don't really face the same situation - we *can* add additional
data.

No, we can't always add additional data, and that's part of the
consideration for an XTS option- there are things we can do if we use
XTS that we can't with GCM or another solution. Specifically, being
able to perform physical replication from an unencrypted cluster to an
encrypted one is a worthwhile use-case that we shouldn't be just tossing
out.

Yeah, XTS seems like a reasonable first step, both because it doesn't
require storing extra data and it's widespread use in FDE software (of
course, there's a link between those). And I suspect replication between
encrypted and unencrypted clusters is going to be a huge can of worms,
even with XTS.

It's probably a silly / ugly idea, but can't we simply store a special
"page format" flag in controldat - when set to 'true' during initdb,
each page would have a bit of space (at the end) reserved for additional
encryption data. Say, ~64B should be enough. On the encrypted cluster
this would store the nonce/IV/... and on the unencrypted cluster it'd be
simply unused. 64B seems like a negligible amount of data. And when set
to 'false' the cluster would not allow encryption.

With something like AES-GCM-SIV we can use the additional data to get IV reuse
resistance *and* authentication. And while perhaps we are ok with the IV reuse
guarantees XTS has, it seems pretty clear that we'll want want guaranteed
authenticity at some point. And then we'll need extra data anyway.

I agree that it'd be useful to have an authenticated encryption option.
Implementing XTS doesn't preclude us from adding that capability down
the road and it's simpler with fewer dependencies. These all strike me
as good reasons to add XTS first.

True. If XTS addresses the threat model we aimed to solve ...

Thus, to me, it doesn't seem worth going down the XTS route, just to
temporarily save a bit of implementation effort. We'll have to endure that
pain anyway.

This isn't a valid argument as it isn't just about implementation but
about the capabilities we will have once it's done.

* Tomas Vondra (tomas.vondra@enterprisedb.com) wrote:

On 10/15/21 23:02, Robert Haas wrote:

On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost@snowman.net> wrote:

That is, the default for LUKS is AES, XTS, with a simple IV. That
strikes me as a pretty ringing endorsement.

Yes, that sounds promising. It might not hurt to check for other
precedents as well, but that seems like a pretty good one.

TrueCrypt/VeraCrypt uses XTS too, I think. There's an overview of other FDE
products at [1], and some of them use XTS, but I would take that with a
grain of salt - some of the products are somewhat obscure, very old, or
both.

What is probably more interesting is that there's an IEEE standard [2]
dealing with encrypted shared storage, and that uses XTS too. I'd bet
there's a bunch of smart cryptographers involved.

Thanks for finding those and linking to them, that's helpful.

I'm not very convinced that using the LSN for any of this is a good
idea. Something that changes most of the time but not all the time
seems more like it could hurt by masking fuzzy thinking more than it
helps anything.

I haven't been following the discussion about using LSN, but I agree that
while using it seems convenient, the consequences of some changes not
incrementing LSN seem potentially disastrous, depending on the encryption
mode.

Yes, this depends on the encryption mode, and is why we are specifically
talking about XTS here as it's an encryption mode that doesn't suffer
from this risk and therefore it's perfectly fine to use the LSN/FakeLSN
with XTS (and would also be alright for AES-GCM-SIV as it's specifically
designed to be resistant to IV reuse).

I'm not quite sure about the "perfectly fine" bit, as it's making XTS
vulnerable to traffic analysis attacks (comparing multiple copies of an
encrypted block). It may be a reasonable trade-off, of course.

* Bruce Momjian (bruce@momjian.us) wrote:

On Fri, Oct 15, 2021 at 10:57:03PM +0200, Tomas Vondra wrote:

That said, I don't think that's really a huge issue or something that's
a show stopper or a reason to hold off on using XTS. Note that what
those bits actually *are* isn't leaked, just that they changed in some
fashion inside of that 16-byte cipher text block. That they're directly
leaked with CTR is why there was concern raised about using that method,
as discussed above and previously.

Yeah. With CTR you pretty learn where the hint bits are exactly, while with
XTS the whole ciphertext changes.

This also means CTR is much more malleable, i.e. you can tweak the
ciphertext bits to flip the plaintext, while with XTS that's not really
possible - it's pretty much guaranteed to break the block structure. Not
sure if that's an issue for our use case, but if it is then neither of the
two modes is a solution.

Yes, this is a vary good point. Let's look at the impact of _not_ using
the LSN. For CTR (already rejected) bit changes would be visible by
comparing old/new page contents. For CBC (also not under consideration)
the first 16-byte block would show a change, and all later 16-byte
blocks would show a change. For CBC, you see the 16-byte blocks change,
but you have no idea how many bits were changed, and in what locations
in the 16-byte block (AES uses substitution and diffusion). For XTS,
because earlier blocks don't change the IV used by later blocks like
CBC, you would be able to see each 16-byte block that changed in the 8k
page. Again, you would not know the number of bits changed or their
locations.

Do we think knowing which 16-byte blocks on an 8k page change would leak
useful information? If so, we should use the LSN and just accept that
some cases might leak as described above. If we don't care, then we can
skip the use of the LSN and simplify the patch.

While there may not be an active attack against PG that leverages such a
leak, I have a hard time seeing why we would intentionally design this
in when we have a great option that's directly available to us and
doesn't cause such a leak with nearly such regularity as not using the
LSN would, and also follows recommendations of using XTS from NIST.
Further, not using the LSN wouldn't really be an option if we did
eventually implement AES-GCM-SIV, so why not have the two cases be
consistent?

I'm a bit confused, because the question was what happens if we encrypt
the page twice with the same LSN or any tweak value in general. It
certainly does not matter when it comes to malleability or replay
attacks, because in that case the attacker is the one who modifies the
block (and obviously won't change the LSN).

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 10/18/21 17:56, Stephen Frost wrote:

...
I've argued for storing the nonce, but I don't quite see why would we need
integrity guarantees?

AFAICS the threat model the patch aims to address is an attacker who can
observe the data (e.g. a low-privileged OS user), but can't modify the
files. Which seems like a reasonable model for shared environments.

There are multiple threat models which we should be considering and
that's why we may want to eventually add integrity.

So what are these threat models? If we should be considering them it'd
be nice to have a description, explaining what capabilities must the
attacker have ...

My (perhaps naive) understanding is that the authentication / integrity
provides (partial) protection against attackers that may modify instance
data - modify files, etc. But I'd guess an attacker with such capability
can do various other (simpler) things to extract data. Say, modify the
config to load an extension that dumps keys from memory, or whatever.

So what's a plausible / practical threat model that would be mitigated
by the authenticated encryption?

It'd be a bit silly to add complexity to allow AEAD, only to find out
there are ways around it.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2021/10/19 00:37, Robert Haas wrote:

I think what we ought to be doing at
this point is combining our efforts to try to get some things
committed which make future work in this area committed - like that
patch to preserve relfilenode and database OID, or maybe some patches
to drive all of our I/O through a smaller number of code paths instead
of having every different type of temporary file we write reinvent the
wheel.

A unified block-based I/O API sounds great. Has anyone tried to do this
before? It would be nice if the front-end tools could also use these API.

As there are so many threat models, I propose to do the TDE feature by a
set of hooks. those hooks are on the critical path of IO operation, add
the ability to let extension replace the IO API. and also load extension
when initdb, single-mode, and in front-end tools.
This sounds Like using $LD_PRELOAD to replace pread(2) and pwrite(2),
which widely used in folder based encryption. but the hook will pass
more context (filenode, tableoid, blocksize, and many) to the under
layer, this hook API will look like object_access_hook.
then implement the simplest AES-XTS. and put it to contrib. provide a
tool to deactivate AES-XTS to make PostgreSQL upgradeable.

I think this is the most peaceful method. GCM people will not reject
this just because XTS. and XTS people will satisfied(maybe?) with the
complexity. for performance, just one more long-jump compare with
current AES-XTS code.

On Tue, Oct 19, 2021 at 11:46 AM Sasasu <i@sasa.su> wrote:

As there are so many threat models, I propose to do the TDE feature by a
set of hooks.

This is too invasive to do using hooks. We are inevitably going to
need to make significant changes in core.

--
Robert Haas
EDB: http://www.enterprisedb.com