Eugene Leitl
Tue, 05 Feb 2002 07:19:58 -0800
-- 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 <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] 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. .-. [EMAIL PROTECTED] .-. / \ .-. Software Development .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' ArgoTech `-' \ / `-' http://argote.ch/ `-' http://xent.com/mailman/listinfo/fork --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]