From: Hal <hfinney@shell.portal.com>
Date: Fri, 1 Jul 94 18:30:23 PDT
To: cypherpunks@toad.com
Subject: Re: Physical storage of key is the weakest link
In-Reply-To: <199407012226.PAA01800@netcom7.netcom.com>
Message-ID: <199407020131.SAA11491@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


Tim May writes:
>Speculatively, knowing the passphrase-encrypted secret key may make it
>easier to crack RSA; this is just a speculation. It is not yet even
>been proven that RSA is a strong as factoring. i.e., we don't know for
>sure that the RSA information provided as part of the protocol doesn't
>in some way make the problem simpler than straight factoring of the
>modulus.

Here is a little-known fact.  In fact, I had forgotten it myself until
what Tim said reminded me.  Your PGP secret key file is partially encrypted
using IDEA keyed with the hash of your pass phrase.  But some fields are
left in the clear.  In particular, the number of bits in p and q is left
exposed, as is the number of bits in d, the decryption exponent.

Now, this is not really a big deal.  Usually with a 1024-bit key p and
q will both be 512 bits long, so knowing this for sure doesn't add that
much information.  And I don't think that knowing the exact number of
bits in the factors will help with the factoring when the two factors are
about the same size.  Nevertheless it does represent an information leak
that many people may not be aware exists.

One way an attacker might exploit this is as follows.  Suppose he wants
to do an exhaustive search of pass phrases.  As Tim said, a lot of people
may have ones which are easy to guess.  How does he know when he's guessed
correctly?  The secret key has a checksum (in the clear).  After decrypting
all of d, p, q, and u, PGP accumulates a checksum as it does this and com-
pares it with the checksum stored in the secret key.  If they match, PGP
(or the cracker) knows that he has used the right pass phrase.

This requires decrypting all four of these numbers, a total of about
320 bytes.  But he can do a provisional check much faster by using the
in-the-clear lengths.  Just decrypting the first byte of each MP number
allows you to see immediately what the bit length of the resulting MP
value will be since they are stored in MSB form.  For the most extreme
case, suppose the length of p were one more than a multiple of 8, say
505 bits.  Now we decrypt the first part of p and see if the first byte
of the decryption is exactly 1.  If not, we can know immediately that we
have the wrong pass phrase and move on without doing any more IDEA op-
erations.  This will immediately reject 255 out of 256 wrong pass phrases.

I don't know how much of a speedup you would actually see from this; IDEA
has a setup phase and you still have to run MD5 on each pass phrase.
But possibly it could be significant.


Hal Finney
hfinney@shell.portal.com