Re: storing an explicit nonce

Greetings,

* Antonin Houska (ah(at)cybertec(dot)at) wrote:
> Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> > * 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.

What I think is missing from this discussion is the fact that, with XTS
(and XEX, on which XTS is built), the IV *is* run through a forward
cipher function, just as suggested above needs to be done for CBC. I
don't see any reason to doubt that OpenSSL is correctly doing that.

This article shows this pretty clearly:

https://en.wikipedia.org/wiki/Disk_encryption_theory

I don't think that changes the fact that, if we're able to, we should be
varying the tweak/IV as often as we can, and including the LSN seems
like a good way to do just that.

Now, all that said, I'm all for looking at what others do to inform us
as to the right way to go about things and the above article lists a
number of users of XTS which we could go look at:

XTS is supported by BestCrypt, Botan, NetBSD's cgd,[13] dm-crypt,
FreeOTFE, TrueCrypt, VeraCrypt,[14] DiskCryptor, FreeBSD's geli, OpenBSD
softraid disk encryption software, OpenSSL, Mac OS X Lion's FileVault 2,
Windows 10's BitLocker[15] and wolfCrypt.

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

Except that it isn't. If you're using someone else's computer, they're
going to be able to look into shared buffers at tons of unencrypted
data, including the keys to decrypt everything. That doesn't mean we
shouldn't try to be good about using a different IV to make it harder on
someone who has somehow gotten access to watch the writes go by, but TDE
isn't a solution to protect someone from their cloud provider gaining
access to their data.

Thanks,

Stephen