Subject: Re: FUD about CGD and GBDE
To: Roland Dowdeswell <email@example.com>
From: Perry E. Metzger <firstname.lastname@example.org>
Date: 03/03/2005 18:45:17
Roland Dowdeswell <email@example.com> writes:
> I realise that PHK has been claiming that you might get false
> positives, and that you somehow have to maintain a matrix of past
> this and that. It is a lot simpler than this really.
Of course, given that the unicity distance is much less than the text
encrypted under one block.
> For each key--key sector you are brute forcing, there are 2^128
> different keys to try. Now, the key--key sector protects 32 disk
> sectors which contain 32 * 512 * 8 = 131072 bits. That means that
> there are 2^131072 possibilities for what can be in those 32 sectors.
> So, I think that we can see where I am going here?
Yes. Small unicity distance, vanishingly low chance of false positive.
> Now, granted not the entirety of the 32 sectors will be recognisable,
> or necessarily even used---but a fair percentage will. Enough to
> come up with numbers that may not be so astronomically small, are
> still staggeringly small---a staggeringly small possibility that
> such a false positive generating key actually exists at all.
There is a good paper by Dave Wagner and Steve Bellovin on how to
detect that you have the right plaintext, btw, even without needing
things that can actually "understand" what they are looking at.
> Disklabels for example have a checksum. The checksum might not be
> terribly strong, but the chance that two different valid disklabels
> could even be decrypted with different keys is small, I would
> imagine. The checksum takes off 2^32 seemingly valid disklabels
> and what about the rest of the fields? There's lots of redundant
> information in there that could be cross referenced.
You don't even need that. A very cheap statistical test will show that
you have the right key with very good probability. However, given
checksums, you pretty much have the plaintext nailed.
Perry E. Metzger firstname.lastname@example.org