Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
On Wed, 27 Feb 2002, Lucky Green wrote: Philip, If we can at all fit it into the schedule, IFCA will attempt to offer a colloquium on this topic at FC. Based on the countless calls inquiring about this issue that I received just in the last few days, the customers of financial cryptography are quite concerned about the Bernstein paper, albeit the paper raises a number of open issues that still would need to be investigated before one should assert that the sky is falling. See you all at FC, --Lucky, IFCA President Hmmm. According to Bernstein, It's better and worse than it first appeared. On the one hand, the o(1) term may be quite large and cancel much of the speedup for keys of practical size, and even with reduced costs, that's still a lot of single-purpose hardware to build for a practical keysize. On the other hand, RSA is not the only system affected. The technique may work on Elliptic Curve systems as well. Which of these sides is better and which worse is something that you will have to work out depending on your own perspective. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Enzo Michelangeli [EMAIL PROTECTED] writes: Well, a nice characteristic that RSA doesn't have is the ability of using as secret key a hash of the passphrase, which avoids the need of a secret keyring All PK algorithms have this property; seed a CSPRNG with the passphrase and use the CSPRNG as the source of randomness in key generation. and the relative vulnerability to dictionary attacks. The protection against dictionary attacks seems to be that checking whether a given passphrase is the correct one is slow, because you have to check it against the public key. However, the minimum time to check passphrase validity can be made arbitrarily slow whatever PK algorithm is used, with techniques such as key stretching. http://www.counterpane.com/low-entropy.html Your proposal makes a system *more* vulnerable to dictionary attacks, since the attack can be mounted without the need to seize the secret keyring. -- __ Paul Crowley \/ o\ [EMAIL PROTECTED] /\__/ http://www.ciphergoth.org/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Isn't Elliptic-Curve patent-encumbered? I think we went through this a few weeks ago. Nope. Fortunately, ECC per-se is not patent encumbered. Scott Vanstone makes much of that in his ECC dog and pony show. Of course, free ECC does not mean some nice optimizations aren't patented. --mkb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
On Tue, Feb 26, 2002 at 08:40:40AM -0800, bear wrote: I'm not completely comfortable with Elliptic-Curve systems. The mathematics is relatively young and has seen a lot of progress. Right. I'm not very comfortable with Elliptic-Curve yet, either. I haven't been able to work out exactly how, but I have a gut feeling that there may be some translation or transformation of the Elliptic-Curve problem that simplifies to integer factoring, [...] Plus, I'd remind everyone that no-one managed to prove that breaking RSA is as hard as factoring (cf. ``Breaking RSA may be easier than factoring'' D.Boneh R.Venkatesan, where they show that if you manage to show that breaking RSA is algebraically as hard as factoring, then you've got for free a factoring algorithm). -- Berke Durak - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Philip, If we can at all fit it into the schedule, IFCA will attempt to offer a colloquium on this topic at FC. Based on the countless calls inquiring about this issue that I received just in the last few days, the customers of financial cryptography are quite concerned about the Bernstein paper, albeit the paper raises a number of open issues that still would need to be investigated before one should assert that the sky is falling. See you all at FC, --Lucky, IFCA President - Original Message - From: Phillip H. Zakas [EMAIL PROTECTED] To: 'bear' [EMAIL PROTECTED] Cc: 'Eugene Leitl' [EMAIL PROTECTED]; 'Cryptography List' [EMAIL PROTECTED] Sent: Monday, February 25, 2002 12:25 PM Subject: RE: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd) -Original Message- From: bear [mailto:[EMAIL PROTECTED]] Sent: Monday, February 25, 2002 2:49 PM On Thu, 21 Feb 2002, Phillip H. Zakas wrote: On Tue, 5 Feb 2002, Eugene Leitl wrote: 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 Bear Responds: I really want to read this paper; if we don't get to see the actual mathematics, claims like this look incredibly like someone is spreading FUD. Is it available anywhere? The paper is located here: http://cr.yp.to/papers.html I've not evaluated yet but I'm interested in hearing if he received his grant to try it out. Holy shit. The math works. Bernstein has found ways of using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies and redundancies because we kept thinking in terms of linear implementations. This is probably the biggest news in crypto in the last decade. I'm astonished that it hasn't been louder. It does seem doable and for not very much money. Is anyone attending the Intl. Financial Cryptography Association meeting in Bermuda from March 11-15th? Perhaps we could arrange an informal get-together for this list. Phillip - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Being a numb skull in such things does it mean IPSEC VPN is not secure? At present im running 1024bit the cpu hit is high, going to 2048 i suspect / told its even higher :( regards, Thing bear wrote: [Moderator's inquiry: Any third parties care to comment on this? --Perry] On Thu, 21 Feb 2002, Phillip H. Zakas wrote: On Tue, 5 Feb 2002, Eugene Leitl wrote: 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 Bear Responds: I really want to read this paper; if we don't get to see the actual mathematics, claims like this look incredibly like someone is spreading FUD. Is it available anywhere? The paper is located here: http://cr.yp.to/papers.html I've not evaluated yet but I'm interested in hearing if he received his grant to try it out. Holy shit. The math works. Bernstein has found ways of using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies and redundancies because we kept thinking in terms of linear implementations. This is probably the biggest news in crypto in the last decade. I'm astonished that it hasn't been louder. Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed them as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fact, likely. This work demonstrates a lack of security in a bunch of PGP Keys. All previous estimations of security level as a function of bit length, should be applied as though the bit length were one-third of its actual length. This means that effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were. I remember there was one version of PGP that allowed RSA keys longer than 2kbits - I don't remember what version it was right now, but someone is sure to remind us now that I've said so. :-) Anyway, probably very few people are using 4kbit or 8kbit PGP RSA keys anyhow, due to lack of cross-version compatibility. The secure forever level of difficulty that we used to believe we got from 2kbit keys in RSA is apparently a property of 6kbit keys and higher, barring further highly-unexpected discoveries. Recommendation to all implementors: Future applications should not offer to create RSA keys shorter than 2048 bits, and should allow users to specify keys of up to *at least* 8 kbits in length. Remember, backward compatibility is inappropriate where it compromises security. Recommendation to all crypto users: discontinue use of RSA keys shorter than 2048 bits, NOW. Issue a revocation if the software you use allows it. If the software you use is restricted to RSA keys shorter than 2048 bits, get rid of it and find something better. I predict that Elliptic-Curve systems are about to become more popular. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
At 11:49 AM -0800 2/25/02, bear wrote: ... The secure forever level of difficulty that we used to believe we got from 2kbit keys in RSA is apparently a property of 6kbit keys and higher, barring further highly-unexpected discoveries. Highly-unexpected? All of public key cryptography is build on unproven mathematical assumptions. Why should this be the last breakthrough? If you plot the curve of what key length was considered long enough as a function of time, it doesn't look very good. Perhaps it is time to stop claiming secure forever altogether until solid mathematical proofs of security are available. ... I predict that Elliptic-Curve systems are about to become more popular. I'm not completely comfortable with Elliptic-Curve systems. The mathematics is relatively young and has seen a lot of progress. Yet typical EC key length recommendations are based on the assumption that there is no way to calculate discrete logs in EC groups that is any faster than the general algorithm that applies to all finite groups. That sounds pretty aggressive to me. If we are going to have to upgrade OpenPGP standards in light of the Bernstein paper, I would suggest a standard that combines RSA, EC and, if possible, a third PK system whose algorithm is based on an apparently independent problem. The advantage of double or triple encryption is that a breakthrough in one problem area does not immediately compromise all your previously encrypted data. And you can upgrade the component key in question and distribute it signed with the old key, without have to start from scratch in establishing trust. Most personal computers are capable of this level of security. Why settle for less? Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
[Moderator's inquiry: Any third parties care to comment on this? --Perry] On Thu, 21 Feb 2002, Phillip H. Zakas wrote: On Tue, 5 Feb 2002, Eugene Leitl wrote: 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 Bear Responds: I really want to read this paper; if we don't get to see the actual mathematics, claims like this look incredibly like someone is spreading FUD. Is it available anywhere? The paper is located here: http://cr.yp.to/papers.html I've not evaluated yet but I'm interested in hearing if he received his grant to try it out. Holy shit. The math works. Bernstein has found ways of using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies and redundancies because we kept thinking in terms of linear implementations. This is probably the biggest news in crypto in the last decade. I'm astonished that it hasn't been louder. Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed them as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fact, likely. This work demonstrates a lack of security in a bunch of PGP Keys. All previous estimations of security level as a function of bit length, should be applied as though the bit length were one-third of its actual length. This means that effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were. I remember there was one version of PGP that allowed RSA keys longer than 2kbits - I don't remember what version it was right now, but someone is sure to remind us now that I've said so. :-) Anyway, probably very few people are using 4kbit or 8kbit PGP RSA keys anyhow, due to lack of cross-version compatibility. The secure forever level of difficulty that we used to believe we got from 2kbit keys in RSA is apparently a property of 6kbit keys and higher, barring further highly-unexpected discoveries. Recommendation to all implementors: Future applications should not offer to create RSA keys shorter than 2048 bits, and should allow users to specify keys of up to *at least* 8 kbits in length. Remember, backward compatibility is inappropriate where it compromises security. Recommendation to all crypto users: discontinue use of RSA keys shorter than 2048 bits, NOW. Issue a revocation if the software you use allows it. If the software you use is restricted to RSA keys shorter than 2048 bits, get rid of it and find something better. I predict that Elliptic-Curve systems are about to become more popular. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
-- 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]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
-- 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
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Although the headers and quoting have gotten munged, this appears to be a reply to my message. Eugene Leitl [EMAIL PROTECTED] writes: -- 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. And this is how fast? 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. It's the only real argument that ECC's got going for it. RSA can be made arbitrarily fast by making it arbitrarily slow. 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. If you care about Perfect Forward Secrecy, you shouldn't be using RSA at all. You should be using DH with a fresh key for each exchange. The probability that in the next 50 years your key will be compromised in some other way than factoring is sufficiently high to motivate this tactic. (In my view, it's vastly higher than that of your key being broken by factoring). This message actually makes my point quite nicely. I frequently see long detailed arguments by ECC proponents about how wonderful ECC is and how it should replace RSA. This is one such argument. That's not what's needed. For ECC to take off, someone will have to actually write it into protocols. This requires someone to identify a specific ECC algorithm that meets the properties that I laid out, and document those properties with literature citations, performance numbers, securtiy estimates, etc. That's what's needed before the COMSEC people will feel comfortable adding ECC to their systems. Until someone's willing to step up to the plate on that, we're not going to see ECC deployment in standard protocols. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
At 2:25 AM -0800 2/5/02, Eugene Leitl wrote: -- 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] ... 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. IMHO, interactive protocols (e.g. certain modes of SSL/TLS) which are subject to this attack should be retired. Non-interactive protocols (e.g. PGP email), are much more difficult to fix. Cheers - Bill - Bill Frantz | The principal effect of| Periwinkle -- Consulting (408)356-8506 | DMCA/SDMI is to prevent| 16345 Englewood Ave. [EMAIL PROTECTED] | fair use. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
-- On 27 Jan 2002, at 21:17, Eugene Leitl wrote: I think the only patents of particular note for ECC are Certicom and H.P.'s ones on point-compression. The original paper on ECC proposed point compression and described the algorithm in 1985. See Bernstein's web page http://cr.yp.to/nistp224/patents.html Use the 1985 method. If the methods patented are the same, and as far as I can tell they are, the patents are invalid. If the methods patented differ, you are not using them. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG V2lKe8/zPipRJIcZE97A49gog89BMHmZrKWJ0GA8 4sl5ZBNjSI2/m083cg2ed9OSfY9/uWraeiBqyR+Dj - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
At 7:38 AM -0800 1/29/02, Eric Rescorla wrote: Ben Laurie [EMAIL PROTECTED] writes: Eric Rescorla wrote: BTW, I don't see why using a passphrase to a key makes you vulnerable to a dictionary attack (like, you really are going to have a dictionary of all possible 1024 bit keys crossed with all the possible passphrases? Sure!). Unfortunately, dictionary attack is used differently by different people. There are two different kinds of attacks here: (1) A brute-force attack such as is used by Crack where you successively try a small subset of the passphrase space in the expectation that it is the space that people are likely to populate. (This is what RFC 2828 calls a dictionary attack). (2) A table-driven attack where you have an enormous table (say of passphrases to keys) and just do a lookup in the table. I was referring to the former, which is quite practical against such a system. The latter probably consumes too much memory to be practical. I think there are significant advantages to a passphrase-derived public key system. It allows total portability and the encryption hardware can be totally zeroized between uses. One of the biggest threats to modern cryptosystems is their large electronic footprint that leaves too much room to hide things. Passphrase-derived public keys also allow very long term storage of keys (e.g. on acid free paper in a vault) without worries about deterioration of media or inability to read old formats. Method 2 is totally impossible in systems that use long salt (48 bits or more) or probably unique salt e.g an e-mail address or complete phone number. Here are three very practical techniques to protect against Method 1: The first is aggressive key stretching that burns up on the order of 1 second of processing time and utilizes silicon-consuming resources like memory and 32-bit multiplies. The second is for the system itself to suggest strong passphrases. Users could ignore the suggestion but nothing can protect a user who is not willing to follow recommended precautions. With good key stretching even a 5 word diceware passphrase (64-bit entropy) would provide strong protection. The third would be to combine the password and salt with a secret stored in the encryption device. This makes the key dependent on the device, but requires the attacker to capture both the device and the passphrase. Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Ben Laurie [EMAIL PROTECTED] writes: Eric Rescorla wrote: I don't know exactly what Pegwit does, but most of these schemes are still vulnerable to dictionary attacks by trying arbitrary passphrases and seeing if they generate the correct public key. It's of course slower since the test operation is slower. If you want to slow down test operations, then iteration is good. I agree. BTW, I don't see why using a passphrase to a key makes you vulnerable to a dictionary attack (like, you really are going to have a dictionary of all possible 1024 bit keys crossed with all the possible passphrases? Sure!). Unfortunately, dictionary attack is used differently by different people. There are two different kinds of attacks here: (1) A brute-force attack such as is used by Crack where you successively try a small subset of the passphrase space in the expectation that it is the space that people are likely to populate. (This is what RFC 2828 calls a dictionary attack). (2) A table-driven attack where you have an enormous table (say of passphrases to keys) and just do a lookup in the table. I was referring to the former, which is quite practical against such a system. The latter probably consumes too much memory to be practical. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Eugene Leitl [EMAIL PROTECTED] writes: -- Forwarded message -- Date: Sun, 27 Jan 2002 21:10:09 +0100 (CET) From: Robert Harley [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: Cringely Gives KnowNow Some Unbelievable Free Press... Adam Beberg wrote: I'm preaty sure the reason we're all using RSA _now_ is the same reason we were using DH a couple years ago - the patents are all expired. ECC has a bunch of patents still living, and the word among the crypto crowd I know is still avoid like the plague. I usually have no particular desire to respond to Beberg's negativism, but I suppose that I should do so this time. [Discussion of patents deleted] I see this sort of point-by-point discussion of EC patents a lot. I think it misses the point. 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, particularly by the big players. [extra points if you're willing to indemnify] (2) significantly better than RSA (this generally means faster) (3) has seen a significant amount of analysis so that we can have some reasonable confidence it's secure. Until someone does that, the cost of information in choosing an EC algorithm is simply too high to justify replacing RSA in most applications. Mr. Beberg's comment about avoiding ECC like the plague matches my impression of the COMSEC community pretty well. I'm not really part of the crypto community so I can't speak for that. -Ekr - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
- Original Message - From: Eric Rescorla [EMAIL PROTECTED] To: Eugene Leitl [EMAIL PROTECTED] Sent: Monday, 28 January, 2002 6:33 AM [...] 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, particularly by the big players. [extra points if you're willing to indemnify] (2) significantly better than RSA (this generally means faster) (3) has seen a significant amount of analysis so that we can have some reasonable confidence it's secure. Until someone does that, the cost of information in choosing an EC algorithm is simply too high to justify replacing RSA in most applications. Well, a nice characteristic that RSA doesn't have is the ability of using as secret key a hash of the passphrase, which avoids the need of a secret keyring and the relative vulnerability to dictionary attacks. See e.g. the Pegwit application, which, in its version 9 (http://groups.yahoo.com/group/pegwit/) does not, AFAIK, infringe on any EC patent. Enzo - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
Enzo Michelangeli [EMAIL PROTECTED] writes: - Original Message - From: Eric Rescorla [EMAIL PROTECTED] To: Eugene Leitl [EMAIL PROTECTED] Sent: Monday, 28 January, 2002 6:33 AM [...] 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, particularly by the big players. [extra points if you're willing to indemnify] (2) significantly better than RSA (this generally means faster) (3) has seen a significant amount of analysis so that we can have some reasonable confidence it's secure. Until someone does that, the cost of information in choosing an EC algorithm is simply too high to justify replacing RSA in most applications. Well, a nice characteristic that RSA doesn't have is the ability of using as secret key a hash of the passphrase, which avoids the need of a secret keyring and the relative vulnerability to dictionary attacks. See e.g. the Pegwit application, which, in its version 9 I don't know exactly what Pegwit does, but most of these schemes are still vulnerable to dictionary attacks by trying arbitrary passphrases and seeing if they generate the correct public key. It's of course slower since the test operation is slower. And of course you can do the same sort of thing with RSA by using the passphrase as the seed for the PRNG. This is quite practical on modern machines where RSA key generation is extremely fast. (And practical even on slow machines if you use Schiller's trick of remembering a hint). -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)
-- 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: Sun, 27 Jan 2002 21:10:09 +0100 (CET) From: Robert Harley [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: Cringely Gives KnowNow Some Unbelievable Free Press... Adam Beberg wrote: I'm preaty sure the reason we're all using RSA _now_ is the same reason we were using DH a couple years ago - the patents are all expired. ECC has a bunch of patents still living, and the word among the crypto crowd I know is still avoid like the plague. I usually have no particular desire to respond to Beberg's negativism, but I suppose that I should do so this time. The basic patent on RSA has expired (RSA was widely used before that too - you might have noticed). An equivalent basic patent on ECC never existed. There are various other patents to be aware of, and this is the case whether you're working with ECC or RSA, or making paper clips. You can avoid them if you know what you're doing, and walk right into them if you don't. For instance RSA Security holds a patent on fast exponentiation, which can be used for RSA or ECC (but not paper clips, AFAIK). Various protocols, whether used over RSA or ECC, are patented. The Diffie-Hellman patent expired (before that people often used El Gamal instead). Other protocols such as Nyberg-Rueppel or Menezes-Qu-Vanstone are still covered. Specific to ECC: There are Crandall's patents on using certain primes of a special form. So don't use them. I recommend using random primes anyway (patent or no patent) or else binary fields. The NSA has patented a particular exponentiation algorithm for Koblitz curves. So don't use it. However they will probably place it in the public domain like their DSA patent. I recommend not using Koblitz curves anyway (patent or no patent). Certicom has some patents on fast arithmetic (whether for ECC or other stuff) but they cover circuit designs for finite-field multipliers, with low transistor count and/or using normal bases. They are irrelevant for software and irrelevant for polynomial bases which I recommend anyway. For hardware they can be avoided e.g., Siemens has ECC hardware which doesn't infringe. I think the only patents of particular note for ECC are Certicom and H.P.'s ones on point-compression. For DH, you just use the x-coordinate so you don't need points, never mind point-compression. For signatures such as ECDSA, you need points so just use them uncompressed. It makes very little difference. The issue is if you want to verify signatures produced by somebody else who used point-compression. I would hazard a guess that in such a situation it would be OK to check the x-coordinate and ignore the one bit of extra information in y (but I would have to study the details to be sure). Patents are a pain in the ass but, in this instance at least, they hardly constitute a minefield. We wont be touching ECC for a very long time. Fine! 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]
