From: pmetzger@shearson.com (Perry E. Metzger)
Date: Fri, 4 Dec 92 09:43:36 PST
To: VANGUARD@gribb.hsr.no
Subject: Weakness of the PGP scheme ?
In-Reply-To: <MAILQUEUE-101.921204152203.416@gribb.hsr.no>
Message-ID: <9212041720.AA05323@newsu.shearson.com>
MIME-Version: 1.0
Content-Type: text/plain


>From: VANGUARD@gribb.hsr.no

>The underlying security of the PGP scheme is based on two different
>systems, the RSA asymetric cipher and the IDEA cipher. For standard
>encryption the plaintext is encrypted with a IDEA using a "random"
>key, then the key is communicated using RSA. Then we have two direct
>ways of analysing a message, we might have a run a plaintext attack
>on the ciphertext trying out all possible IDEA keys which will tak
>a lot of effort, or we might break the RSA key to get the IDEA key.

>But I propose an easier attack; Using a Encrypted Ciphertext together
>with the public key used for encryption, It would be possible to run
>a trial encrypting all possible IDEA keys using the RSA public key
>and compare it with the encrypted IDEA key, if a match is found then
>you have the IDEA key for this one message. Using an RSA chip that is
>capable of performing exponetsiations VERY fast I dont think that
>this would be unfeasable.

This is quite wrong. This only makes sense if RSA were inherently much
faster than IDEA. In fact, IDEA is orders of magnitude slower than
RSA; thats the whole reason that we use IDEA session keys encrypted
with RSA and not RSA itself to encrypt the message -- RSA is way too
slow. The result of this is that trying all possible IDEA keys
directly to break the cypher is far far faster than trying to encrypt
all possible IDEA keys with RSA. Now, since the security of IDEA
depends on it being secure from brute force attacks like trying all
possible IDEA keys and seeing which one produces a good message, the
result is that if IDEA is secure, PGP is certainly secure from the
attack you mention.

>The most important factor in this attack is the length of the IDEA
>key. But another concern is the generation of the IDEA key, is it
>possible knowing the value of the RANDSEED to know all the subsequent
>IDEA keys?, or would knowing the last IDEA key drastically reduce the
>time needed to search for a subsequent one?

If the random number generator is good, then it should not be possible
to predict the next session key. If it is bad, all bets are off. I
would agree that questions of the quality of the RNG have been
inadequitely explored.

Perry