Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)

Eugene Leitl Eugene.Leitl at lrz.uni-muenchen.de
Tue Feb 5 05:25:16 EST 2002



-- Eugen* Leitl <a href="http://leitl.org">leitl</a>
______________________________________________________________
ICBMTO: N48 04'14.8'' E11 36'41.2'' http://www.leitl.org
57F9CFD3: ED90 0433 EB74 E4A9 537F CFF5 86E7 629B 57F9 CFD3

---------- Forwarded message ----------
Date: Tue,  5 Feb 2002 11:10:49 +0100 (CET)
From: Robert Harley <harley at argote.ch>
To: fork at xent.com
Subject: Re: Cringely Gives KnowNow Some Unbelievable Free Press...

Eugene Leitl wrote:
>If you want to see EC used you need to describe a specific algorithm
>which has the following three properties:
>
>(1) widely agreed to be unencumbered, [...]

No problem.  Use a random secure curve over a binary field with a
polynomial basis (or over a random prime field).  Do it in software
using standard text-book algorithms.  Use a protocol that is
in the clear such as plain Diffie-Hellman key exchange.

That is what we do e.g., sharing a symmetric key for
encryption/decryption using Rijndael.  The only patent that is
relevant for us is our own one (pending) on a fast method for
generating random secure curves.


EL:
>(2) significantly better than RSA (this generally means faster)

This seems a little bit simplistic...  Whatever way you cut it, RSA
will beat ECC on public key ops (encryption, signature verification...)
whereas ECC will beat RSA on private key ones (decryption, signing...)

The speed argument can be compelling or not depending on what you want
to do.  On standard PCs doing occasional crypto operations, both ECC
and RSA are plenty fast.  The speed issue is on small devices like
hand-helds or mobile phones, and on heavily loaded servers.

For instance with signatures, people might want to sign on slow client
devices which take 1 second with ECC but many seconds with RSA; and
then verify the signatures on servers fast enough for thousands per
second.  It is easier to upgrade your servers if needed than to
upgrade the users who aren't using your service because it is too slow.

One hears of crazy stuff like network setups which time out when you
try to do DH with 1024-bit RSA on some slow hand-helds, but work fine
when doing equivalent DH with 163-bit ECC.

In our work with Mailwatcher, servers talk to each other doing equal
numbers of encryptions and decryptions for many users.  Even according
to RSA Security's own numbers, ECC wins easily in this case!



EL:
>(3) has seen a significant amount of analysis so that we can have
>some reasonable confidence it's secure.

The FUD campaign on this point has been too successful.

Serious study of factoring and related stuff dates from the early 19th
century with people like Gauss.  Serious study of elliptic curves and
related stuff dates from... umm... the early 19th century with people
like... umm... Gauss.

Modern study of discrete-log based cryptosystems dates from the
invention of public-key systems in 1976.  Modern study of factoring
based cryptosystems dates from the invention of RSA in 1977.  ECC is
in the former family, although it dates from 1985.

The relative paucity of results on ECC is a good thing.  There has
been no progress on breaking ECC with properly chosen curves.  On the
contrary there is a negative result that discrete logs using generic
group operations do take exponential time.  The problem in this
area is with some people sailing too close to the wind and picking
curves with tonnes of useful properties to speed up their
cryptosystems (and, unfortunately, attacks on some of them).


For RSA, it was claimed in 1977 that factoring a certain 426-bit
number would take quadrillions of years.  This in spite of the fact
that a sub-exponential algorithm for factoring was already known.
Knowledge was pretty fuzzy about its runtime and practicality.  Some
widely-deployed big-budget systems were designed using RSA as low as
320 bits.  That's easily broken.

During the 1980's, the research community perfected the early
sub-exponential methods and the 426-bit number was broken in 1994 by a
team led by Arjen Lenstra (I was in it...)

There was also a new faster algorithm, the NFS.  Knowledge was pretty
fuzzy about its runtime and practicality.  During the 1990's, the
research community perfected it.  Then recently 512 bits was broken.

The current record, as of a few days ago, is 524 bits attained by Jens
Franke et al. when completing the factorization of 2^953+1 (there were
three other factors previously found by Paul Zimmerman, Torbjorn
Granlund and myself).  It would be feasible to break 600 bits or more
with some effort.


Things have been quiet on the "new algorithms" front for a few years.
But at Crypto last August, Dan Bernstein announced a new design for a
machine dedicated to NFS using asymptotically fast algorithms and
optimising memory, CPU power and amount of parallelism to minimize
asymptotic cost.  His conclusion, recently detailed in a paper, should
be a bombshell, but apparently everyone is asleep:

DB:
>This reduction of total cost [...] means that a [approx 3d-digit]
>factorization with the new machine has the same cost as a d-digit
>factorization with previous machines.

Knowledge is pretty fuzzy about its runtime and practicality, but it
means that it may well be much easier than previously believed to
break 1024 bits.  You may need, say, 3000 bits to be safe.

Meanwhile ECC is still fine with 163 bits.


EL:
>Until someone does that, the cost of information in choosing an EC
>algorithm is simply too high to justify replacing RSA in most
>applications.

Personally, I no longer trust RSA for long term security.

This is public-key crypto, not symmetric, so a break of your RSA key
means that all your encrypted traffic becomes readable rather than
just one message.  E.g., if a few years ago you used 512-bit RSA to
encrypt a will that was not to be read by anybody until you die,
that's tough because it could be read today.  Doesn't matter that you
moved to 768 bits and then 1024 in the meantime.

All that secured info that was supposed to be absolutely positively
definitely safe for 50 years may not be after all but, hey, you just
have to increase your key size again and people won't be able to read
your stuff anymore "this time it's really true, promise!"


BTW, at the ECC conference last October, an NSA speaker said that they
were transitioning sensitive data to ECC.

Wall.  Writing.  Etc.



Bye,
  Rob.
     .-.                    Robert.Harley at argote.ch                    .-.
    /   \           .-.      Software Development       .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'       ArgoTech      `-'         \   /
             `-'                http://argote.ch/              `-'


http://xent.com/mailman/listinfo/fork


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list