weird behavior of symmetrically encrypted file

[Tobias]

Hi Daniel,

thank you for your answer, it helped me a lot. The quick check does
explain the behavior I described in my earlier mail. Your guess is also
good: I have a 6 bit entropy per character. Therefore it is more than
likely that I stumbled into a false positive passphrase within a four
character range.

The next question is whether I can use this to speed up my brute force
attempt. Is it possible to utilize the false positive passphrase for
finding other positives, false or not? My idea is not to try and decrypt
the file with each new passphrase, but to perform the quick check on it
and then compare the result with the result of the false positive. This
way I should be able to rule out negatives fast - at least faster than
by having gpg try every passphrase from scratch (although I'd still have
to see whether it's fast enough to make the brute force attempt
reasonable).

The thing I'm unsure about is which parts of the decryption process I'd
have to apply in order to safely discriminate positives from negatives.
As far as I understand the RFC, it should suffice to compute the
decryption key from the current passphrase and compare it to the key
from my false positive. Is that correct, or am I missing a step here?

-- 
Liebe Grüße
Tobias




Daniel Kahn Gillmor wrote:
> Hi Tobias--
> 
> On 01/15/2010 04:24 AM, Tobias wrote:
>> Why do I get a passphrase ("3ity") which I can't remember having ever
>> used in my life? Why does gpg regard it as correct but still not decrypt
>> my file? And apart from these somewhat academical questions: Is there a
>> way I can use the half-correct passphrase to refine (which means, speed
>> up) my search for the truly correct one? If I can use it to
>> significantly reduce the set of possible passphrases, it may save me
>> some decades worth of blind guessing.
> 
> I suspect what you're seeing is a function of the way the OpenPGP
> standard handles passphrase calculations for "Symmetrically Encrypted
> Data Packet" [0].
> 
> Basically, the data that is being symmetrically encrypted is prefixed
> with an IV that contains a duplicated chunk of 16 bits for a
> non-normative "quick check" that the session key was correct.  This
> means that 1 out of 2^16 choices of session key will falsely pass the
> quick-check purely by chance, even though the material is actually not
> correctly decrypted.
> 
> I don't know what brute force method you were using, but i suspect you
> had about 5 bits of entropy per character in your enumerations.  For
> example, all lower-case letters plus numbers is a total of 36
> possibilities, which is just about 5 bits (2^5 == 32).  With 4-character
> passphrases at 5 bits per character, you would run through 2^20
> passphrases.  So it's likely that you exhausted 2^16 passphrases, and
> stumbled into one of the "quick check" false positives.  This does *not*
> mean that your data is insecure.  It means the quick check is advisory
> at best.
> 
> (see also the security considerations related to this "quick check" [1])
> 
> hope this helps,
> 
> 	--dkg
> 
> [0] http://tools.ietf.org/html/rfc4880#section-5.7
> [1] http://tools.ietf.org/html/rfc4880#page-84
>