weird behavior of symmetrically encrypted file

[Daniel Kahn Gillmor]

Hi Tobias--

On 01/16/2010 09:03 PM, Tobias wrote:
> thank you for your answer, it helped me a lot. 

You're welcome!  Glad to be helpful.

> 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?

my understanding of the steps involved is slightly different -- i don't
think you'll be able to speed things up much the way you describe.  (if
you could, it would certainly reflect poorly on the OpenPGP packaging
format!)

I think the steps needed are:

 * generate the key from the proposed passphrase, using whatever S2K
technique is indicated by the file; you can get this from

  gpg --list-packets <file.gpg

which will say somthinig like s2k 3, hash 2 (you can look these values
up in the table in RFC 4880)  (--list-packets will also prompt you for a
passphrase, but you can just hit enter, as the metadata you're gathering
here is *outside* of the encryption)

 * using the indicated cipher (also from the output above, it will say
something like "cipher 3") with the generated key, decrypt the first few
blocks of the encrypted material, and test whether the two indicated
pairs of bytes are repeated.

 * if they are, then you can try the passphrase using full gpg and
inspect the output.

so basically, what i'm saying is that the speedup is that you get to
throw away (2^16-1) of every 2^16 possible passphrases, but you still
need to do a signficant amount of work to figure out if you can throw
them away.  the main speedup would be to write these routines in C,
using a good fast crypto-primitives library for the S2K digests and the
initial cipher block decryption.  this speedup would be an
implementation detail (no need to re-exec gpg each time, no repeated
packet parsing, etc), and not a crypto attack at all.

for smaller files and reasonable (i.e. large) repeat counts for iterated
S2K, the computational cost for the S2K operation should *by far* exceed
the actual computational cost of running the cipher algorithm to decrypt
the  secret material.  So there's not much of a win here, i think, other
than the small factor you can get from a sped-up implementation.

if you have any knowledge about how the passphrase was likely to be
formed (e.g. if you always start your passphrases with a capital
letter), that reduction in brute force search space alone will probably
far outweigh any of the possible gains from the steps outlined above.

(needless to say, this is why choosing long, high-entropy passphrases is
important).

Regards,

	--dkg

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 891 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20100118/354b757b/attachment.pgp>