Re: storing an explicit nonce

Stephen Frost <sfrost(at)snowman(dot)net> wrote:

> Greetings,
>
> * Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> > On Thu, Oct 7, 2021 at 3:38 PM Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> > > While I certainly also appreciate that we want to get this as right as
> > > we possibly can from the start, I strongly suspect we'll have one of two
> > > reactions- either we'll be more-or-less ignored and it'll be crickets
> > > from the security folks, or we're going to get beat up by them for
> > > $reasons, almost regardless of what we actually do. Best bet to
> > > limit the risk ( ;) ) of the latter happening would be to try our best
> > > to do what existing solutions already do- such as by using XTS.
> > > There's things we can do to limit the risk of known-plaintext attacks,
> > > like simply not encrypting empty pages, or about possible known-IV
> > > risks, like using the LSN as part of the IV/tweak. Will we get
> > > everything? Probably not, but I don't think that we're going to really
> > > go wrong by using XTS as it's quite popularly used today and it's
> > > explicitly used for cases where you haven't got a place to store the
> > > extra nonce that you would need for AEAD encryption schemes.
> >
> > I agree that using a popular approach is a good way to go. If we do
> > what other people do, then hopefully our stuff won't be significantly
> > more broken than their stuff, and whatever is can be fixed.
>
> Right.
>
> > > As long as we're clear that this initial version of TDE is with XTS then
> > > I really don't think we'll end up with anyone showing up and saying we
> > > screwed up by not generating a per-page nonce to store with it- the point
> > > of XTS is that you don't need that.
> >
> > I agree that we shouldn't really catch flack for any weaknesses of the
> > underlying algorithm: if XTS turns out to be secure even when used
> > properly, and we use it properly, the resulting weakness is somebody
> > else's fault. On the other hand, if we use it improperly, that's our
> > fault, so we need to be really sure that we understand what guarantees
> > we need to provide from our end, and that we are providing them. Like
> > if we pick an encryption mode that requires nonces to be unique, we
> > will be at fault if they aren't; if it requires nonces to be
> > unpredictable, we will be at fault if they aren't; and so on.
>
> Sure, I get that. Would be awesome if all these things were clearly
> documented somewhere but I've never been able to find it quite as
> explicitly laid out as one would like.
>
> > So that's what is making me nervous here ... it doesn't seem likely we
> > have complete unanimity about whether XTS is the right thing, though
> > that does seem to be the majority position certainly, and it is not
> > really clear to me that any of us can speak with authority about what
> > the requirements are around the nonces in particular.
>
> The authority to look at, in my view anyway, are NIST publications.
> Following a bit more digging, I came across something which makes sense
> to me as intuitive but explains it in a way that might help everyone
> understand a bit better what's going on here:
>
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-38G.pdf
>
> specifically: Appendix C: Tweaks
>
> Quoting a couple of paragraphs from that appendix:
>
> """
> In general, if there is information that is available and statically
> associated with a plaintext, it is recommended to use that information
> as a tweak for the plaintext. Ideally, the non-secret tweak associated
> with a plaintext is associated only with that plaintext.
>
> Extensive tweaking means that fewer plaintexts are encrypted under any
> given tweak. This corresponds, in the security model that is described
> in [1], to fewer queries to the target instance of the encryption.
> """
>
> The gist of this being- the more diverse the tweaking being used, the
> better. That's where I was going with my "limit the risk" comment. If
> we can make the tweak vary more for a given encryption invokation,
> that's going to be better, pretty much by definition, and as explained
> in publications by NIST.
>
> That isn't to say that using the same tweak for the same block over and
> over "breaks" the encryption (unlike with CTR/GCM, where IV reuse leads
> directly to plaintext being recoverable), but it does mean that an
> observer who can see the block writes over time could see what parts are
> changing (and which aren't) and may be able to derive insight from that.

This reminds me of Joe Conway's response to me email earlier:

https://www.postgresql.org/message-id/50335f56-041b-1a1f-59ea-b5f7bf917352%40joeconway.com

In the document he recommended

https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38a.pdf

specifically, in the Appendix C I read:

"""
For the CBC and CFB modes, the IVs must be unpredictable. In particular, for
any given plaintext, it must not be possible to predict the IV that will be
associated to the plaintext in advance of the generation of the IV.

There are two recommended methods for generating unpredictable IVs. The first
method is to apply the forward cipher function, under the same key that is
used for the encryption of the plaintext, to a nonce. The nonce must be a
data block that is unique to each execution of the encryption operation. For
example, the nonce may be a counter, as described in Appendix B, or a message
number. The second method is to generate a random data block using a FIPS-
approved random number generator.
"""

This is about modes that include CBC, while the documend you refer to seems to
deal with some other modes. So if we want to be confident that we use the XTS
mode correctly, more research is probably needed.

> Now, as I mentioned before, that particular case isn't something that
> XTS is particularly good at and that's generally accepted, yet lots of
> folks use XTS anyway because the concern isn't "someone has root access
> on the box and is watching all block writes" but rather "laptop was
> stolen" where the attacker doesn't get to see multiple writes where the
> same key+tweak has been used, and the latter is really the attack vector
> we're looking to address with XTS too.

I've heard a few times that database running in a cloud is also a valid use
case for the TDE. In that case I think it should be expected that "someone has
root access on the box and is watching all block writes".

--
Antonin Houska
Web: https://www.cybertec-postgresql.com