ALT.2600
 Subj : On 'cracking' PGP...                                                    

    Ok.  There has been alot of discussion on this topic as of late,
    and I feel it is time to clarify a few things.  This information
    will be, in future, available from the ole .plan, so direct
    inqueries there.


          Cracking PGP Myth Banishment Notes

    by Route

    PGP is a hybrid cryptosystem.  It contains 4 crytpographic elements,
    each of which is subject to a different type of cryptographic
    attack.  It contains a symmetric cipher, an asymmetric cipher, a
    one-way hash, and a random number generator.


    -- The symmetric cipher --

    IDEA, finalized in 1992 by Lai and Massey is strong.  It is the
    toughest block cipher known of today.  There have be no advances
    in the cryptanalysis of standard IDEA that are publically known.
    (I know nothing of what the NSA has done, nor does most anyone.)
    The best method of attack, therefore, is brute force.  As we all
    know the keyspace of IDEA is 128-bits.  To recover a particular
    key, one must, on average, search half the keyspace.  That is 127
    bits.  Fine.  If you, for the sake of argument, had 1 billion
    machines that could try 1 billion keys/sec.  It would still take
    all these machines longer than the universe as we know has existed
    and then some, to find the key.  Not a likely event.  IDEA, as far
    as present technology goes, not vulnerable to attack, pure and
    simple.


    -- The asymmetric cipher --

    RSA, the first *full fledged* public key cryptosystem was designed
    by Rivest, Shamir, and Adleman.  It has withstood *years* of
    *intense* cryptographic scrutiny.  RSA gets it's security from
    the apparent difficulty in factoring very large composites.
    However, nothing has been proven with RSA.  It is not *proven*
    that factoring the public modulous is the only (best) way to
    factor RSA.  It is also not proven that factoring *has* to be
    as hard as it is.  There exists the possiblity that an advance in
    number theory may lead to the discovery of polynomial time factoring
    algorithm.  But, none of these things has happened, and nothing
    points in that direction.  However, 3 things that *are* happening
    and *will* continue to happen are the advances in: factoring
    technique and computing power, and the decrease in the cost of
    computing hardware.  These things, esp. the first one, work against
    the security of RSA.  However, as computing power increases, so
    does the ability to generate larger keys.  It is *much* easier to
    multiply very large primes than it is to factor the resulting
    composite.
    So, as it stands now, the best way to crack RSA is through factoring
    the public modulus.  This, as far as we know, is not an easy task,
    if the public modulous is large enough (there are numerous examples
    of smaller keys falling to concerted effort).  Using the General
    Number Field Sieve, a 1024-bit key would likely require 3E11 MIPS
    years to factor.  20 years from now (assuming no breakthoughs in
    factoring technology) this keyspace will likely be insecure.  Today,
    it is not.  But, the ultra-conservative will opt for 2048-bit
    keys, which is not a bad idea in my opinion.
    It is very difficult to make predictions in this area of computing/
    cryptography.  Arjen Lenstra the most succesful factorer will not
    make predictions oast 10 years.
    To sum it up:  RSA is vulnerable to factoring. --DON'T LET ANYONE
    WITHOUT A PHD IN THEORECTICAL MATH TELL YOU OTHERWISE--    If you use
    a large enough public key, all the worlds computers cannot factor
    your key (using present factoring technology).  RSA would not have
    lastest this long if it was as fallible as some crackpots would
    like you to believe.


    -- The one-way hash --

    MD5 is the hash used to hash the passphrase into the IDEA key and
    to sign documents.  Message Digest 5 was designed by Rivest.  It's
    output is four 32-bit blocks, which form a 128-bit hash of the
    input.  MD5 has no known practical security weaknesses.  It has a
    weakness in the compression function, allowing for collisions, but
    this does not allow for any practical attack.  There are two attacks
    against MD5 (or any hash function).  The first is to find a another
    input that will hash to same value.  Not very practical or likely.
    Remember the output is 128-bits.  That's a BIG number.  The other
    attack, the birthday attack, trys to find two random messages that
    hash to the value.  This is also impractical (although not as much
    as the first one).
    Since English has 1.3 bits of information per character, and IDEA
    uses a 128-bit key, a passphrase of about 100 characters will
    maximize the randomness of the resulting hash.  How many of you
    use 100 character passphrases?


    -- The PRNG --

    I do not have enough info on the PSNG used by PGP as of yet.  This
    section under construction.

--
 ----| Infinity / Route / daemon9 |--------|------------------|--------------
--| Founding member: The 0x47 0x75 0x69 0x6C 0x64 | Finger for information |--
    [RSADSALUCGARGOYLEIDEADESLUCIFERLOKIFEALSHAMD5HAVALSNEFRU]
      Business wants to make money, Government wants to have control.
       Our privacy is at stake.  Use strong cryptography.