From: Derek Atkins <warlord@MIT.EDU>
Date: Fri, 29 Oct 93 23:23:26 PDT
To: nobody@Menudo.UH.EDU
Subject: Re: Paranoid
In-Reply-To: <199310300500.AA06657@Menudo.UH.EDU>
Message-ID: <9310300622.AA04325@binkley.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


> "unknown" doesn't provide anyone with very much reassurance.

Well, sorry.  But if you think about it, Shamir figured out a way to
crack a DES key given 2^53 plaintexts (I think this is the right order
of magnitude).  This is with DES, which has 56-bit keys.  PGP uses
IDEA, which is 128-bit keys.  However, the IDEA algorithm is
relatively new, and has not been as throroughly tested.  With DES, it
is fairly easy to say that "knowing the plaintext and cyphertext does
not allow you to easily find the key used".  Is this statement also
true with IDEA?  I don't know.  Also, this is knowing a full block of
plaintext, or the WHOLE plaintext.  Partial plaintext helps even less.

> Not all versions of UUENCODE start each line with an "M" and there are
> other programs similar to UUENCODE that can be used. The synergistic effect
> would also be due to the fact that the cracker would be clueless to the fact
> that UUENCODE was being used, but only if there is no type of checksum or
> compression signature that was being used instead of a spell checker.

Wait a second, *why* do you want to use UUENCODE?  The reason
compression is used is to 1) reduce the size of the message, and 2) to
reduce the amount of redundancy in the message.  The redundancy can
help an attacker break it.  (If you know that it is ASCII text, it is
easier to try to break it than if its compressed ASCII text, since the
compressed ASCII text is now binary text!).  Why UUENCODE?  Now you
again reduce the problem to fixed-format, fixed line length ASCII
text!  This doesn't help you.  This helps the attacker.  You want to
remove as much redundancy from the plaintext as possible before it is
encrypted.

> A spell checker?? This is insane. There has got to be some type of checksum
> code that verifies if the text was decrypted properly or not. Crackers can't
> possibly be trying keys and word searching for "the" or "and". Where have all
> the code writters vanished to?

There is.  There is a header *byte* that lets you know that the block
was decrypted.  Read my statements about partial plain-text.  A good
encryption algorithm will not give you any information about a key
given access to both the plain text and cyphertext.

> My opinion ---> What TotalFuckingBullshit(tm) <---
[stuff deleted]
> Is there some type of design flaw that limits RSA keys to 1024 bits??

You asked "Is there an easy way to generate keys larger than 1024
bits?"  I answered No.  This is true, there is no way, currently, in
PGP, to generate keys larger than 1024 bits.  Is there a design flaw?
No.  It was an implementation decision.  It does not mean that the key
size will not be increased in a future release.

There is one flaw limiting to 1024-bit keys.  RSAREF.  It currently
has a limit of 1024 bit keys.  If there is ever to be a PGP that uses
RSAREF, then either RSAREF needs to be capable of larger keys, or PGP
is going to have to keep itself limited to 1024-bit keys.

> Technology is growing exponentially. Try: "for over 10 year[sic]"

Technology is not growing exponentially, it is growing geometrically.
And there is a finite limit to the amount it can grow.  It is called
quantum physics!  If you assume that no significant improvements are
made to the factoring problem, algorithmically, then all you can do is
apply more computer power towards the problem.

As a concrete example, there is currently a project to try to factor
RSA129, a 129 digit RSA modulus.  This is equivalent to approximately
425 bits.  The estimated time for completion of this problem is about
6000-10000 MIP-years.  That means it would take 10000 1-MIP machines
one full year to factor the number.  From personal experience in this
project, I can tell you *there is no damn way you are going to factor
a 1024-bit number in 10 years*.  Not until every person on this planet
has hundreds of computers at their disposal that are many orders of
magnitude more powerful than today's most powerful machines, and you
devote every single one of them to the problem for those 10 years,
basically shutting down the planet for 10 years.

Remember, factoring is an exponential problem.  I don't remember the
exact formula for the complexity, offhand, however the number of
MIP-years for a 1024-bit key was somewhere around 10^20 MIP-years.
Don't compare factoring to breaking DES, they are totally different
problems.

> Any decent "personal computer" can crack mediocre DES encryptions in a semi
> reasonable amount of time. 10 years ago how many people do you think thought
> that this would be possible?

Define a reasonable about of time?  Currently, the best we have
currently is the $1M machine that can crack DES in 3.5 hours, on
average.  You consider that a "decent personal computer"?  Or do you
consider "semi reasonable amount of time" to be 10 years?

Clearly, you have a lot to learn about orders of magnitude!

-derek

         Derek Atkins, SB '93 MIT EE, G MIT Media Laboratory
     Secretary, MIT Student Information Processing Board (SIPB)
         PGP key available from pgp-public-keys@pgp.mit.edu
            warlord@MIT.EDU       PP-ASEL        N1NWH