Re: storing an explicit nonce

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

Thanks,

Stephen