Re: storing an explicit nonce

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

Thanks,

Stephen