Re: storing an explicit nonce - Mailing list pgsql-hackers

On Tue, May 25, 2021 at 07:48:54PM -0400, Stephen Frost wrote:
> Greetings,
> 
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Tue, May 25, 2021 at 05:22:43PM -0400, Stephen Frost wrote:
> > > * Bruce Momjian (bruce@momjian.us) wrote:
> > > > OK, this is good to know.  I know the never-reuse rule, so it is good to
> > > > know it can be relaxed for certain data without causing problems in
> > > > other places.  Should I modify my patch to do this?
> > > 
> > > Err, to be clear, I was saying that we could exclude the hint bits
> > > *entirely* from what's being encrypted and I don't think that would be a
> > > huge issue.  We still absolutely need to continue to implement a
> > > never-reuse rule when it comes to nonces and making sure that we don't
> > > encrypt different sets of data with the same key+nonce, it's just that
> > > if we exclude the hint bits from encryption then we don't need to worry
> > > about making sure to use a different nonce each time the hint bits
> > > change- because they're no longer relevant.
> > 
> > So, let me ask --- I thought CTR basically took an encrypted stream of
> > bits and XOR'ed them with the data.  If that is true, then why are
> > changing hint bits a problem?  We already can see some of the bit stream
> > by knowing some bytes of the page.  I do think skipping encryption of
> > just the hint bits is more complex, so I want to understand why if is
> > needed.  (This is a question I eventually wanted to discuss, just like
> > my XXX questions.)
> 
> That's how CTR works, yes.  The issue that you run into is that once
> you've got two pages which have different data but were encrypted with
> the same key and nonce then you can use crib-dragging.
> 
> A good example of how this works is here:
> 
> http://travisdazell.blogspot.com/2012/11/many-time-pad-attack-crib-drag.html
> 
> Once you've got the two different pages which had the same key+nonce
> used, you can XOR them together and then start cribbing, scanning the
> page for legitimate data which doesn't have to be in the part of the
> data that was different between the two original pages.
> 
> Not sure what you're referring to in the second half ... simply knowing
> that some of the data has a given plaintext (such as having a really
> good idea that the word 'the' exists in a given message) doesn't provide
> you the same level of information as two pages encrypted with the same
> key+nonce but having different data.  Indeed, AES is generally believed
> to be quite effective against even given plaintext attacks:
> 
>
https://math.stackexchange.com/questions/51960/is-it-possible-to-guess-an-aes-key-from-a-series-of-messages-encrypted-with-that/57428

Agreed.  I was just reinforcing that, and trying to say that hint bit
change might also be considered known information.

Anyway, if you think the hint bit changes would leak, I an accept that. 
It means we need to wal log hit bit changes, no matter if the nonce is
the LSN or a custom one.

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

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