Re: What's the latest in factoring?

[Alan Tu <ATU5713@compuserve.com>]

Dear Bill,

Sorry, but you may see this message twice.

Bill Stewart wrote:

>>>>>
There are two countervailing arguments about very long keys;
one is that if you understand cryptography well enough to 
evaluate the issue, you'll know you don't need to bother,
but the other is that if you don't understand crypto very well,
maybe you should be overly conservative.
<<<<<

Well, personally, I guess by your def I'm in the second group, since I
didn't know I don't need to bother.

>>>>>
Remember that factoring difficulty is roughly exponential;
adding logn bits about doubles the cracking workload 
(depending on which factoring method is being used).  
Factoring a 1024-bit number is _much_ harder than factoring a 512-bit
number, and factoring a 2048-bit number is well into age-of-the-universe 
difficulty level.  The practical level of factoring right now
is about 512 bits, for either a distributed internet effort or
an NSA internal one;
<<<<<

I kind of knew this from a hypothesis, so PGP 5.x is being conservative,
possibly overly so by your definition.  I've seen a screen on a friend's
computer and the default is something like 2048.  By the way, we don't know
about NSA.  They may be able to factor any number, if they have an
algorithm.

>>>>>
in the unlikely event that Moore's law lets
us double processing power 100 times in the next 150 years,
that means a 1500-bit key could be crackable.  So 2048 bits
is certainly more than enough for _your_ lifetime.
Increasing processing power 2**100 times is likely to be tough :-)
After all, features in current microprocessors are on the order
of 100 atoms wide.  And by the time we've developed the level of 
nanotechnology needed to speed up processing that much,
there'll be tiny audio bugs listening to you type your passphrase
into your keyboard and reporting it back to the Central Intelligence
Corporation, or picking up the electromagnetic fields from your
direct neural interface, so the crypto strength won't matter much.
<<<<<

I believe in Moore's law, since in 1992-1993 I read an analysis that
Moore's law was true for the last 100 years.  I think its still true today.
 Your last set of thoughts is chilling, isn't it?

But consider this.  People 10, 20, 30 years ago like us are saying that the
government can eavesdrop on their communication in the future, just as you
are saying now.  Look now.  I am very proud that I am part of the e-crypto
revolution (my coined word).  I am helping to slow down NSA.  I hope that,
by the time the tech you hypothesize about is here, we again will have
technology to slow down NSA.

>>>>>
But do you really _need_ to factor the prime number to crack PGP?  No.
Remember that PGP uses the RSA key to encrypt session keys for IDEA,
or for signing MD5 hashes of documents, rather than using it directly.
So you can decrypt the message by cracking IDEA, or forge a message
by finding MD5 collisions.  Cracking IDEA's 128-bit keys was estimated
to be about as hard as factoring a 3100-bit number, though improvements
to factoring technology may make a 4096-bit number as easy as IDEA.
Also, PGP 2.x passphrases are encrypted with IDEA, so if they've
got your secring.pgp and can crack 4096-bit keys, you're toast,
<<<<<

I know this.  The point is that most if not all people know that RSA is the
weak link, not IDEA.  Would you rather start to work on a 1024-bit RSA key
or IDEA passphrase of an enemy?  Obviously the RSA key.  Barring any
mathematical weakness in IDEA, I am not worried about IDEA.  By the way, my
three-year-old info says that IDEA was being mathematicly attacked in many
quarters, civilian and non-civilian alike.  If they was anything, I would
have heard by now, but I still want to ask.  Has any significant
cryptanalysis attack against IDEA been "successful"?

>>>>>
even if your passphase isn't just your dog's name spelled backwards.
Similarly, by the time processing power doubles 100 times making your
1500-bit key insecure, MD5 will be long toasted.  Either way,
there's no need to go beyond 4096-bit keys ever, with old-style PGP.
Even if you're being overly conservative, that's more than enough.
<<<<<

You seem to be suggesting that MD5 will lead to the downfall of all of our
keys.  Let's think about your toasting of MD5.  The worst thing that can
happen to a one-way hash function is that it can go both ways.  So its dead
for signatures.  So let's suppose now that I can take any document and
produce another document with a higher or lower dollar figure in it and
come up with the same hash.  I can do this easily.  But to somehow exploit
MD5 to crack a passphrase it is impossible because you have nothing to
start working with.  You only have an encrypted key, encrypted with an
128-bit IDEA key.

Look, for our lifetimes, I don't see much point in going beyond 4096 bits
either, maybe even 3072.

>>>>>
Newer versions of PGP dump RSA and IDEA for patent reasons, 
but they also offer alternatives to IDEA and MD5 which may be stronger.
(SHA-1 is stronger than MD5, triple-DES requires immense amounts of
storage to reduce it to a strength similar to IDEA, and just being
extensible means you can replace algorithms that are obsolete.)
<<<<<

Triple-DES is not stronger than IDEA, although it is secure for the most
part.  According to Phil Zimmerman, its effective key length is 112 bits to
128 bits for IDEA.  Its also 3 times slower than DES, which is comparably
slow anyway.  Also, to settle this issue once and for all in my mind, the
Win95 version of PGP, what symetric algorithms do you have to choose from?

Does anyone have any comments on the relative strength of Blowfish?  What
about the mathematics of Blowfish?  Has anyone tried to cryptanalyze it
yet?  Also, I apologize for going on like this, I'll post a separate
question on that.

>>>>>
The other side of practical is how much work it takes to use long keys,
and how many people who want to talk to you use them.
The answer to the latter is "Not many" for RSA keys over 2048.
The former is about N**2 for decryption and N**3 for key generation,
and about linear for encryption with short exponents,
so it'll take you 64 times as long (once) to generate the key,
and 16 times as long to decrypt or sign anything, compared to
the far-more-than-strong-enough 2048-bit key, which is already
4 times as hard to use and 8 times as hard to generate as a 1024.
<<<<<

As I said, I have a 2048-bit key in hibernation.  I haven't posted it to a
key server, but a friend who recently got PGP decided to use my public key
ring, and use my 2048-bit key.  There are only two places in which this key
of mine is accessible.  Anyway, I don't see the 4 time slowdown for using
my secret key.  (I have a 133 MHz).  However, the effect is probably true
for slower processors.  I agree that we shouldn't bother with keys above
4096 bits because its not necessary and it takes too long to communicate
with people who have slower processors.

>>>>>
It's not worth the bother, unless you know have a really, really 
special application that needs to remain secret until long after
you've overthrown the government.  On the other hand,
at least the RSA patent will have expired by then :-)
<<<<<

I already addressed this point.

>>>>>
The Diffie-Hellman implementations in PGP 5.x will let you use
key lengths up to 4096, but the speed behaviour is a bit different.
In particular, key generation is much faster, so generating
overkill-length keys isn't as boring.
<<<<<

First of all, Win95 (not my computer) seems slow to me, even if that
person's processor is faster than mine.  And I hear so much disk reading or
writing, no wonder its slow.  Boring?  Win95 cannot make you bored.  Go do
something else, or play a MIDI file.  You can multi-task.

--Alan