Re: XTS cipher mode for cluster file encryption

Greetings,

* Tomas Vondra (tomas(dot)vondra(at)enterprisedb(dot)com) wrote:
> On 10/18/21 17:56, Stephen Frost wrote:
> >* Tomas Vondra (tomas(dot)vondra(at)enterprisedb(dot)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?

Errr, there seems to have been some confusion in this thread between the
different ideas being tossed around.

The point of using FakeLSN for unlogged tables consistently is to
provide variability in the value used as the IV. I wasn't suggesting to
use FakeLSN to provide a uniqueness guarantee- the reason we're talking
about using XTS is specifically because, unlike CTR, unique IVs are not
required. Further, we don't need to find any additional space on the
page if we use XTS, meaning we can do things like go from an unencrypted
to an encrypted system with a basebackup+physical replication.

> >* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> >>On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost(at)snowman(dot)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.

Great.

> 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.

XTS does not require the IV to be unique for every invocation, and
indeed other systems like dm-crypt don't use a unique IV for XTS. We
really can't divorce the encryption methodology from the parameters that
are being used. CTR and GCM are the methods that require a unique IV
(or, at least, a very very very likely unique one if you can't actually
implement a proper counter) but that's *not* what we're talking about
here. The methods being discussed are XTS and GCM-SIV, the former
explicitly doesn't require a unique IV and the latter is specifically
designed to reduce the impact of an IV being re-used. Both are, as NIST
points out, better off with a varying IV, but having the IV be reused
from time to time in either XTS or GCM-SIV does not result in a fatal
failure of the encryption scheme.

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

The differences between those are pretty subtle and it gets a bit
confusing when things like OpenSSL accept an IV but then use it as the
'tweak', such as with XTS. In general though, most methods accept a
key, a nonce/IV/tweak, and then produce ciphertext and possbily a tag,
so I don't think we've been incorrect in usage but rather perhaps a bit
sloppy by not using the right term for the specific methodology.

> >* Andres Freund (andres(at)anarazel(dot)de) wrote:
> >>On 2021-10-15 15:22:48 -0400, Stephen Frost wrote:
> >>>* Bruce Momjian (bruce(at)momjian(dot)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.

Glad you agree with XTS being a reasonable first step. XTS will at
least make physical replication possible- other methods (such as below)
simply won't work.

> 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.

This is essentially what the patch that was posted does, but the problem
is that you can't do physical replication when 64B have been stolen off
of a page because the page in the unencrypted database might be entirely
full and not able to physically fit those extra 64B, and then what?

> >>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 ...

It addresses a valid threat model that people are interested in PG
having a solution for, yes.

> >>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(dot)vondra(at)enterprisedb(dot)com) wrote:
> >>On 10/15/21 23:02, Robert Haas wrote:
> >>>On Fri, Oct 15, 2021 at 3:22 PM Stephen Frost <sfrost(at)snowman(dot)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.

Considering the default usage in dmcrypt isn't even varying the IV as
much as what we're talking about here, I'd say that, yes, it's quite
reasonable for our use-case and allows us to vary the IV quite a bit
which reduces the attack surface in a meaningful way. That dmcrypt has
this risk and it isn't considered enough of an issue for them to use
something other than plain64 as the default makes it certainly seem
reasonable to me.

> >* Bruce Momjian (bruce(at)momjian(dot)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).

The question that I was responding to above was specifically about if
knowing which 16-byte blocks on an 8K page changes was an issue or not
and that's what I was addressing. As for if we encrypt the page twice
with the same LSN/tweak/IV or not- that depends on the specific
encryption methodology being used as to how much of an issue that is, as
discussed above.

* Tomas Vondra (tomas(dot)vondra(at)enterprisedb(dot)com) wrote:
> 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 ...

The first and simplest to consider is the basic "data at rest" threat
model, where a hard drive is not properly wiped or a backup isn't
properly encrypted, or a laptop or other removable media is stolen, etc.
These are well addressed through XTS as in those cases what is needed is
confidentiality, not integrity, as the attacker isn't able to modify the
existing system in such cases.

Another threat model to consider is if the attacker has read-only access
to the data directory through, say, unix group read privileges or maybe
the ability to monitor the traffic on the SAN, or the ability to
read-only mount the LUN on to another system. This might be obtained by
attacking a backup process where the system was configured to run
physical backups using an unprivileged OS user who only has group read
access to the cluster (and the necessary but non-superuser privleges in
the database system to start/stop the backup), or various potential
attacks at the storage layer. This is similar to the "data at rest"
case above in that XTS works well to address this, but because the
attacker would have ongoing access (rather than just one-time, such as
in the first case), information such as which blocks are being changed
inside of a given 8k page might be able to be determined and that could
be useful information, though a point here: they would already be able
to see clearly which 8k pages are being changed and which aren't, and
there's not really any way for us to prevent that reasonably. As such,
I'd argue that using XTS is reasonable and we can mitigate some of this
concern by using the LSN in the tweak instead of just the block number
as the 'plain64' option in dmcrypt does. That doing so would mean that
we'd also be able to reasonably use the same IV for both XTS and
AES-GCM-SIV, should we choose to implement that at some point down the
road, is a nice perk to this approach.

> 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.

Another attack vector to consider is an attacker who is able to actively
modify files on the system in some way. The specific files they are
able to modify matter in such a case. There's no doubt that it's more
difficult to address such an attack vector and it's unlikely we'd be
able to provide a 100% solution in all cases, but that doesn't mean we
should throw out the idea entirely.

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

In a similar vein to above- consider a storage-level attacker who is
able to gain read/write access to a particular volume. If that volume
is used only for a tablespace, a TDE implementation which uses
AES-GCM-SIV would go a long way towards protecting the system. We may
even go so far as to encourage users to ensure that their 'main' PG data
directory, where configuration, transaction log, et al, are stored be
kept on a more secure (perhaps local) volume. This isn't a 100%
solution, of course, due to the visibility map and the free space map
being stored with the tables in the tablespaces, but attacks on those
would be much more coarse and difficult to mount effectively.

We should also be thinking about ways to address those other subsystems
and improve the situation around them (and not just for encryption but
also for detection of corruption) but trying to get all of that done in
one patch or even one major release would make this a massive change
that would almost certainly be rejected as too destablizing.

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

There are ways around it. There likely always will be. We need to be
clear about what it provides and what it doesn't. We need to stop
telling ourselves that the only answer is a 100% solution and therefore
it's impossible to do. Users who care about these capabilities will
understand that it's not 100% and they will still happily use it because
it's better than 0% which is where we are today and is why they are
going with other solutions. Yes, if it's trivial to get around then
perhaps it's not much better than 0% and if that's the case then it
doesn't make sense to do it, but none of what has been discussed here
thus far has made me feel like either the XTS or the GCM-SIV approaches
would be trivial to to circumvent for the threat models they're intended
to address, though it certainly takes more care and more thought when
we're trying to address someone who has write access to part of the
system and that we need to be clear what is addressed and what isn't in
all of these cases.

Thanks,

Stephen