Possible bug in gpg?

[Brad Tilley]

<snip>

Thanks for the reply David. The file was actually cracked so we'll know
the plaintext sometime soon, although that may likely matter not.

> However, people being people, they can easily typo the passphrase, and
> given the method above, if the passphrase is wrong, the session key will
> be wrong, and the data decrypted will be gibberish.  To combat this,
> OpenPGP has two "quick check" bytes in the encrypted data packet.
> Basically, they're a repetition of two random bytes from earlier in the
> message.  The idea is that if the session key is wrong (i.e. the
> passphrase is wrong), the original random bytes won't match their
> repetition, and the client can immediately say "Wrong passphrase!" rather
> than blithely continue and potentially decrypt lots of data that won't
> turn out to be valid.

That seems like a reasonable check to make in most cases. I know that
symmetric-key algorithms will happily output garbage when the wrong
password is used and that may confuse some people, but then again, some
others may actually prefer that. If I was expecting a pdf file (upon
successful decryption) and there was no pdf header up front (only
randomish looking bytes all through the file), then that would be a decent
indication, to me, that the bytes I saw were not actually decrypted.

> The practical upshot of this design is that while it works most of the
> time (in that virtually all incorrect passwords will be immediately
> flagged as such), each symmetrically encrypted message has the chance for
> other, incorrect, passphrases that nevertheless will pass the quick check.
>  Obviously, these cannot decrypt the message, but they mangle into
> (invalid) session keys that just so happen to decrypt the data so that the
> 16-bit quick check matches, allowing the client to proceed, and decrypt
> (incorrectly) the rest of the data.  Usually this fails fairly quickly
> afterwards as the data decrypted is not valid OpenPGP structures, so the
> client will stop with an error message about being unable to read the
> file.
>
> In this particular case, the !=X passphrase passes the quick check, and
> the incorrectly decrypted data happens to look like a packet of packet
> type 0, of length 942141745.  GPG ignores the invalid packet (there is no
> packet type 0), and so no output is generated.
>
> So, assuming my guess is right, it's not a bug in OpenPGP or GnuPG (though
> perhaps giving an error when it saw the packet type of 0 would have been
> better), but a pretty unlikely confluence of events.  How did you come up
> with the !=X passphrase?  Exhaustive search?  I'd be curious to find out
> what the real password is, once it is revealed.

I wrote a small shell script to loop sending password attempts to gpg. I
found three words that caused this behavior in about two hours of trying.
Two of the words worked on the file I initially posted and the other one
on a different file in the contest. So, it seems rather common. Within a
day or so, I could probably generate dozens of words that cause this
behavior.

Thanks again,

Brad

> Incidentally, these quick check bytes were used as the basis for an
> ingenious attack against OpenPGP a few years ago.  See
> http://eprint.iacr.org/2005/033.pdf
>
> David