Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis
Wei Dai writes: Using a factor base size of 10^9, in the relationship finding phase you would have to check the smoothness of 2^89 numbers, each around 46 bits long. (See Frog3's analysis posted at http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html. Those numbers look correct to me.) If you assume a chip that can check one number per microsecond, you would need 10^13 chips to be able to complete the relationship finding phase in 4 months. Even at one dollar per chip this would cost ten trillion dollars (approximately the U.S. GDP). This is probably not the right way to approach the problem. Bernstein's relation-finding proposal to directly use ECM on each value, while asymptotically superior to conventional sieving, is unlikely to be cost-effective for 1024 bit keys. Better to extrapolate from the recent sieving results. http://citeseer.nj.nec.com/cavallar00factorization.html is the paper from Eurocrypt 2000 describing the first 512 bit RSA factorization. The relation-finding phase took about 8000 MIPS years. Based on the conventional asymptotic formula, doing the work for a 1024 bit key should take about 10^7 times as long or 80 billion MIPS years. For about $200 you can buy a 1000 MIPS CPU, and the memory needed for sieving is probably another couple of hundred dollars. So call it $500 to get a computer that can sieve 1000 MIPS years in a year. If we are willing to take one year to generate the relations then ($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy approximately 80 million cpu+memory combinations. This will generate the relations to break a 1024 bit key in a year. If you need it in less time you can spend proportionately more. A $400 billion dollare machine could generate the relations in about a month. This would be about 20% of the current annual U.S. federal government budget. However if you were limited to a $1 billion budget as the matrix solver estimate assumed, the machine would take 40 years to generate the relations. BTW, if we assume one watt per chip, the machine would consume 87 trillion kWh of eletricity per year. The U.S. electricity production was only 3.678 trillion kWh in 1999. The $40 billion, 1-year sieving machine draws on the order of 10 watts per CPU so would draw about 800 megawatts in total, adequately supplied by a dedicated nuclear reactor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: objectivity and factoring analysis
On Fri, 26 Apr 2002, Anonymous wrote: These estimates are very helpful. Thanks for providing them. It seems that, based on the factor base size derived from Bernstein's asymptotic estimates, the machine is not feasible and would take thousands of years to solve a matrix. If the 50 times smaller factor base can be used, the machine is on the edge of feasibility but it appears that it would still take years to factor a single value. One thousand years = 10 iterations of Moore's law plus one year. Call it 15-16 years? Or maybe 20-21 since Moore's seems to have gotten slower lately? Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: objectivity and factoring analysis
On Mon, 13 May 2002, bear wrote: One thousand years = 10 iterations of Moore's law plus one year. Call it 15-16 years? Or maybe 20-21 since Moore's seems to have gotten slower lately? Moore's law is about integration density. That has zero to do with problem-specific system performance. That one is indeed lagging. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: objectivity and factoring analysis
At 9:45 AM -0700 on 5/13/02, bear wrote: One thousand years = 10 iterations of Moore's law plus one year. Call it 15-16 years? Or maybe 20-21 since Moore's seems to have gotten slower lately? Moore himself said in an article in Forbes a few years ago that the cost of fabs themselves would eventually bring a stop to Moore's Law. He couldn't see constructing a $100 billion dollar fab, and right now, fabs are in the $1-$10 billion dollar range and going up... He figured it to be the 20-teens or so for diminishing returns to finally catch up with Moore's Law, if I remember right. If a water shortage on Taiwan doesn't stop it dead in it's tracks this summer. ;-). Cheers, RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
At 08:52 AM 04/24/2002 +0800, Enzo Michelangeli wrote: In particular, none of the naysayers explained me clearly why it should be reasonable to use 256-bit ciphers like AES with 1024-bit PK keypairs. Even before Bernstein's papers it was widely accepted that bruteforcing a 256-bit cipher requires computing power equivalent to ~16Kbit RSA or DH keys (and ~~512-bit ECC keys). Given that a cipher protects only one session, *Something* has to be the weakest link; calls for balance really come down to If Algorithm A is already the stronger part of the system, why should I waste extra time/work strengthening it instead of Algorithm B?. It doesn't hurt to make parts of the system stronger than necessary, unless there are other costs like limiting the sizes of the other keys that can fit in a UDP packet or whatever. And making the AES algorithm use longer-than-needed keys gives you some extra insurance against mathematical breakthroughs or other sorts of discovered weaknesses. The important issue about whether you can use X-bit block cyphers with Y-bit public-key cyphers is whether Y bits of PK can give you X good key bits. For Diffie-Hellman, the conventional wisdom seems to be that Y bits of public key gives you Y/2 bits of usable keying material, which means that 1024-bit DH is good enough for 256-bit AES. For RSA, I think you can protect almost up to pubkeylength bits of message, since the key generation happens separately from the public-key parts, but you're definitely into overkill range. So the question falls back to Is 1024 bits long enough?. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Is There a Quantum Mechanic in the House? (was: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis])
At 05:52 PM 4/23/2002 Tuesday, Enzo Michelangeli wrote: [...] And if the reason for the 256 bits is the possible deployment, sometimes in the future, of quantum computers, well in that case we should stop using PK cryptography altogether. Hi Enzo! Disclaimer: I am not a quantum mechanic, and I find the whole subject, including quantum computation, deeply confusing. Also, the article I refer to -- an article in Science by the guy who came up with the original factoring result -- is an article that I haven't read, and wouldn't understand if I had. (Neither do I happen to know enough to give a proper citation.) Perhaps someone on this list can fill in some of these gaps, or let us know that I've badly misinterpreted the situation, which is quite possible. All that said, my understanding is that the plausible worst case news from quantum computing would probably not require us to give up PK crypto. My understanding is that the article I'd like to cite states something like the following: 1) Factoring is special because it's all pervasively about periodicities. The author's original factoring proposal took advantage of this in an essential way in order to show a potential exponential speedup. 2) For NP problems in general, since they are search trees with only polynomial depth to an answer but exponential fanout of choices, by using superposition, quantum computation may indeed be able to give an exponential speedup on the first phase of the search -- finding the answer. 3) The problem then is reporting the answer out. The superposition that found the answer co-exists with an exponential number of superpositions that don't. My understanding is that the paper is postulating an upper bound for search problems without peculiar special properties (like the periodicities of factoring) -- the most we can get is an order-of-square-root speedup on the problem as a whole. If the above description is approximately right, then the remaining question for PK is, can one design a PK system now whose trapdoor depends on a search problem that we can be confident cannot be transformed into one with the enabling peculiar properties? AFAIK, this question has not been examined. Btw, out of fear that quantum computation might destroy PK but not single-key, I worried about whether one could do cryptographic capabilities in such a world. http://www.erights.org/elib/distrib/captp/unibus.html is a protocol sketch of a distributed capability protocol that depends only on single-key cryptography. But I hope it will never be necessary. Text by me above is hereby placed in the public domain Cheers, --MarkM - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Sorry, there's a mistake in my post, which makes the relationship finding phase look easier than it actually is. BTW, why did it take 5 days for that post to go through? On Wed, Apr 24, 2002 at 12:30:26PM -0700, Wei Dai wrote: Using a factor base size of 10^9, in the relationship finding phase you would have to check the smoothness of 2^89 numbers, each around 46 bits long. Obviously there are not 2^89 integers that are 46 bits long. Each of the numbers that need to be checked for smoothness is actually around 195 bits long. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
I have one other question about the panel analysis. Why did it focus only on the linear algebra part of the NFS algorithm? I would like to know, given the same assumption on the factor base size (10^9), how much would it cost to build a machine that can perform the relationship finding phase of the algorithm in the same estimated time frame (i.e. months)? Using a factor base size of 10^9, in the relationship finding phase you would have to check the smoothness of 2^89 numbers, each around 46 bits long. (See Frog3's analysis posted at http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html. Those numbers look correct to me.) If you assume a chip that can check one number per microsecond, you would need 10^13 chips to be able to complete the relationship finding phase in 4 months. Even at one dollar per chip this would cost ten trillion dollars (approximately the U.S. GDP). So it would seem that it's still not possible for even a major government to factor 1024-bit keys within an operationally relevant time frame unless it was willing to devote most of its national income to the effort. BTW, if we assume one watt per chip, the machine would consume 87 trillion kWh of eletricity per year. The U.S. electricity production was only 3.678 trillion kWh in 1999. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: objectivity and factoring analysis
Nicko van Someren writes: I used the number 10^9 for the factor base size (compared to about 6*10^6 for the break of the 512 bit challenge) and 10^11 for the weight of the matrix (compared to about 4*10^8 for RSA512). Again these were guesses and they certainly could be out by an order of magnitude. In his paper Bernstein uses a relatively larger factor base than in typical current choices of parameters. It's likely that the factor bases which have been used in the past are too small in the sense that the linear algebra step is being limited by machine size rather than runtime, because of the difficulty of parallelizing it. For example in http://www.loria.fr/~zimmerma/records/RSA155 we find that the sieving took 8000 mips years but the linear algebra took 224 CPU hours on a 2GB Cray. If there were a larger machine to do the matrix solution, the whole process could be accelerated, and that's what Bernstein's figures assume. Specifically he uses a factor base size of L^.7904, where L for 1024 bit keys is approximately 2^45. This is a matrix size of about 50 billion, 50 times larger than your estimate. So a closer order of magnitude esimate would be 10^11 for the factor base size and 10^13 for the weight of the matrix. The matrix reduction cells are pretty simple and my guess was that we could build the cells plus inter-cell communication in about 1000 transistors. I felt that, for a first order guess, we could ignore the transistors in the edge drivers since for a chip with N cells there are only order N^(1/2) edge drivers. Thus I guessed 10^14 transistors which might fit onto about 10^7 chips which in volume (if you own the fabrication facility) cost about $10 each, or about $10^8 for the chips. Based on past work in estimating the cost of large systems I then multiplied this by three or four to get a build cost. The assumption of a larger factor base necessary for the large asymptotic speedups would increase the cost estimate by a factor of about 50. Instead of several hundred million dollars, it would be perhaps 10-50 billion dollars. Of course at this level of discussion it's just as easy to assume that the adversary spends $50 billion as $500 million; it's all completely hypothetical. As far at the speed goes, this machine can compute a dot product in about 10^6 cycles. Actually the sort algorithm described takes 8*sqrt(10^11) or about 2.5 * 10^6 cycles, and there are three sorts per dot product, so 10^7 cycles would be a better estimate. Using the larger factor base with 10^13 entries would imply a sort time of 10^8 cycles, by this reasoning. Initially I thought that the board to board communication would be slow and we might only have a 1MHz clock for the long haul communication, but I messed up the total time and got that out as a 1 second matrix reduction. In fact to compute a kernel takes about 10^11 times longer. Fortunately it turns out that you can drive from board to board probably at a few GHz or better (using GMII type interfaces from back planes of network switches). If we can get this up to 10GHz (we do have lots to spend on RD here) we should be able to find a kernel in somewhere around 10^7 seconds, which is 16 weeks or 4 months. Taking into consideration that the sort algorithm takes about 8 times longer than you assumed, and that a few minimal polynomials have to be calculated to get the actual one, this adds about a factor of 20 over your estimate. Instead of 4 months it would be more like 7 years. This is pretty clearly impractical. Apparently Ian Goldberg expressed concerns about the interconnections when the machine was going to run at 1 MHz. Now it is projected to run 10,000 times faster? That's an aggressive design. Obviously if this speed cannot be achieved the run time goes up still more. If only 1 GHz can be achieved rack to rack then the machine takes 70 years for one factorization. Needless to say, any bit errors anywhere will destroy the result which may have taken years to produce, requiring error correction to be used, adding cost and possibly slowing the effective clock rate. Using the larger factor base from the Bernstein paper would increase the time to something like 10^11 seconds, thousands of years, which is out of the question. Lastly, I want to reiterate that these are just estimates. I give them here because you ask. I don't expect them to be used for the design of any real machines; much more research is needed before that. I do however think that they are rather more accurate than my first estimates. These estimates are very helpful. Thanks for providing them. It seems that, based on the factor base size derived from Bernstein's asymptotic estimates, the machine is not feasible and would take thousands of years to solve a matrix. If the 50 times smaller factor base can be used, the machine is on the edge of feasibility but it appears that it would still take years to factor a single value.
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis
Lucky Green writes: Given how panels are assembled and the role they fulfill, I thought it would be understood that when one writes that certain results came out of a panel that this does not imply that each panelist performed the same calculations. But rather that that the information gained from a panel (Ian: math appears to be correct, Nicko: if the math is correct, these are the engineering implications of the math) are based on the combined input from the panelists. My apologies if this process of a panel was not understood by all readers and some readers therefore interpreted my post to indicate that both Ian and Nicko performed parallel engineering estimates. What he wrote originally was: : The panel, consisting of Ian Goldberg and Nicko van Someren, put forth : the following rough first estimates: : : While the interconnections required by Bernstein's proposed architecture : add a non-trivial level of complexity, as Bruce Schneier correctly : pointed out in his latest CRYPTOGRAM newsletter, a 1024-bit RSA : factoring device can likely be built using only commercially available : technology for a price range of several hundred million dollars to about : 1 billion dollars : Bernstein's machine, once built, ... will be able to break a 1024-bit : RSA or DH key in seconds to minutes. It's not a matter of assuming parallel engineering estimates, but rather the implication here is that Ian endorsed the results. In saying that the panel put forth a result, and the panel is composed of named people, it implies that the named people put forth the result. The mere fact that Ian found it necessary to immediately post a disclaimer makes it clear how misleading this phrasing was. Another problem with Lucky's comment is that somewhere between Nicko's thinking and Lucky's posting, the fact was dropped that only the matrix solver was being considered. This is only 1/2 the machine; in fact in most factoring efforts today it is the smaller part of the whole job. Neither Nicko nor Ian nor anyone else passed judgement on the equally crucial question of whether the other part of the machine was buildable. It was not until at least a week after FC that I contacted Nicko inquiring if he still believed that his initial estimates were correct, now that that he had some time to think about it. He told me that the estimates had not changed. It is obvious that in fact Nicko had not spent much time going over his figures, else he would have immediately spotted the factor of 10 million error in his run time estimate. Saying that his estimates had not changed is meaningless if he has not reviewed them. Lucky failed to make clear the cursory nature of these estimates, that the machine build cost was based on a hurried hour's work before the panel, and that the run time was based on about 5 seconds calculation during the panel itself. It's not relevant whether this was in part Nicko's fault for perhaps not making clear to Lucky that the estimate stood in the same shape a week later. But it was Lucky who went public with the claim, so he must take the blame for the inaccuracy. In fact, if Lucky had passed his incendiary commentary to Nicko and Ian for review before publishing it, it is clear that they would have asked for corrections. Ian would have wanted to remove his name from the implied endorsement of the numeric results, and Nicko would have undoubtedly wanted to see more caveats placed on figures which were going to be attached to his name all over the net, as well as making clear that he was just talking about the matrix solution. Of course this would have removed much of the drama from Lucky's story. The moral is if you're going to quote people, you're obligated to check the accuracy of the quotes. Lucky is not a journalist but in this instance he is playing one on the net, and he deserves to be criticized for committing such an elementary blunder, just as he would deserve credit for bringing a genuine breakthrough to wide attention. For example, Bruce has been quoted in a widely-cited eWeek article that I don't assume that someone with a massive budget has already built this machine, because I don't believe that the machine can be built. Bruce shortly thereafter stated in his Cryptogram newsletter that I have long believed that a 1024-bit key could fall to a machine costing $1 billion. Since these quotes describe mutually exclusive view points, we have an example of what can happen when a debate spills over into the popular media. ... http://www.eweek.com/article/0,3658,s=712a=24663,00.asp They are not mutually exclusive, and the difference is clear. In the first paragraph, Bruce is saying that Bernstein's design is not practical. To get his asymptotic results of 3x key length, Bernstein must forego the use of sieving and replace it with a parallel ECM factoring algorithm to determine smoothness. Asymptotically, this is a much lower cost approach for finding relations,
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Further to Lucky's comments: in the last few days I have discussed keysize issues with a few people on a couple of mailing lists, and I have encountered a hostility to large keysizes of which, frankly, I don't understand the reasons. On the client side at least, performance is not an issue: PGP 7.0.3 with my new 4096-bit PGP key appears to be as snappy as it was with 1024-bit keys, and the table at http://www.mccune.cc/PGPpage2.htm#Speed looks quite reassuring. In particular, none of the naysayers explained me clearly why it should be reasonable to use 256-bit ciphers like AES with 1024-bit PK keypairs. Even before Bernstein's papers it was widely accepted that bruteforcing a 256-bit cipher requires computing power equivalent to ~16Kbit RSA or DH keys (and ~~512-bit ECC keys). Given that a cipher protects only one session, but PK protection extends to a large number of sessions, one would expect the PK part to be engineered to be the _stronger_ link of a cryptosystem, not the weaker. And if the reason for the 256 bits is the possible deployment, sometimes in the future, of quantum computers, well in that case we should stop using PK cryptography altogether. What am I missing? Enzo - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Enzo wrote: Further to Lucky's comments: in the last few days I have discussed keysize issues with a few people on a couple of mailing lists, and I have encountered a hostility to large keysizes of which, frankly, I don't understand the reasons. On the client side at least, performance is not an issue: PGP 7.0.3 with my new 4096-bit PGP key appears to be as snappy as it was with 1024-bit keys, and the table at http://www.mccune.cc/PGPpage2.htm#Speed looks quite reassuring. In particular, none of the naysayers explained me clearly why it should be reasonable to use 256-bit ciphers like AES with 1024-bit PK keypairs. Allow me to shed at least some light on the strange phenomenon that you experienced for I have experienced the same phenomenon and was able to glean at least a few of the reasons why application authors and maintainers have proven so reluctant to increase RSA key sizes or mandate minimum key sizes in their applications. 1) Very, very few applications, and no cryptographic libraries that I am aware of, that currently employ RSA perform any kind of sanity check on the size of the keys. The current release version of various programs that I looked at will happily accept a 4-bit RSA client key that anyone could factor in their head. VeriSign not too long ago signed a 384-bit SSL server key that may readers of this list could break with the old computers in their home. Such certificate signing practices, or their lack thereof, are nothing short of irresponsible. I have not tested the following hypothesis and am not willing to spend the required $125 on the experiment, but I would not be in the least surprised if many public CA's would readily sign a certificate for a 4-bit RSA key. C.f. the being caught with one's pants down observation in my previous post. If somebody want to perform this experiment, better do it quick, since the CA vendors read this mailing list. :-) There are some positive examples: as a result of my original post, the next release version of OpenSSH will enforce a 768-bit minimum size on the key. I have not been following the discussion that lead to the determination of this figure and therefore don't know on which cryptological results the OpenSSH designers based that number. However, I note that even those experts that I am aware of which assert that 1024-bit keys are sufficient for the type of long-term use SSH client keys are frequently employed for do not appear to claim that 768-bit keys should be considered secure today. Unfortunately, the OpenSSH designers have chosen to not expose the minimum key size requirement via the sshd configuration file, though at least there now there will be a known spot in the source that can easily be patched to a value the server operator might consider to be more in line with current key size recommendations. I thank the OpenSSH team for at least providing an easy hook to make the desired changes in the source, though of course I would like to see both a larger default and a corresponding option in the config file. Still, hats off to the OpenSSH team for moving implementing sanity checks that few other vendors have bothered to implement. Some other deployed applications either use libraries that can't go higher than 1024-bits or have the key sizes and structures hard coded all over the source, making a chance expensive and uneconomical absent severe customer pressure on the vendor. A much cheaper solution than rewriting good chunks of the core crypto processing code (or worse, having to upgrade hardware that is limited to 1024-bits) is putting out a press release stating why the customer doesn't need keys larger than 1024-bits, which some claim is one of the many reason why there is so much resistance to moving to larger keys. I am not quite ready to subscribe to such cynical a view point, but I heard that view point voiced by several crypto old-timers in private conversations more than once. 2) One frequently voiced argument against increasing key sizes is the resultant decrease in performance. Yes, it is absolutely true that increasing the size of an RSA key leads to a decrease in performance. However, larger keys decrease performance less than naive experiments may seem to indicate. For many applications, generating a 2048-bit key and comparing the performance with that of a 1024-bit key will lead to numbers that differ widely, much more so than can be attributed to the larger key size. The reason for this phenomenon is that RSA algorithm performance is highly dependent on optimizations that are both key size and processor specific. The same optimization strategy that will give you blazingly fast performance with a 1024-bit key will absolute kill performance with a 4096-bit key, for which a different optimization strategy is needed. Similarly, optimizations are highly processor specific. An optimization designed specifically for a Pentium III processor will run slower on a Pentium IV than your basic
Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Anonymous wrote (quoting Adam): Adam Back wrote: The mocking tone of recent posts about Lucky's call seems quite misplaced given the checkered bias and questionable authority of the above conflicting claims we've seen quoted. No, Lucky made a few big mistakes. First, he invoked Ian Goldberg's name as a source of the estimate, which was wrong. Second, he presented Nicko's estimate as being more authoritative than it actually was, as Nicko makes clear here. And third, he fostered panic by precipitously revoking his key and widely promulgating his sky is falling message. Rather than continuing with guesses by those that were not present at the time as to my motivations and objectives behind my post, allow me to establish the facts and thought processes that lead to my original post. Prior to the panel at FC, I held the belief that 1024-bit RSA keys could not be factored in an operationally significant timeframe irrespective of the budget of the attacker. I know that this belief was held by many, if not most, of the implementers of cryptographic production systems and believe that it was held by many, if not most, cryptographers. In some sense, if this belief had not been held so widely, current debate would not be as heated. So let's look at the supposed mistakes Anonymous asserts I made: 1) As is the case with many panel discussions, and in many cases the reason for choosing a panel format rather than an individual presenter, the panelists, Ian Goldberg and Nicko van Someren, were selected to represent subject matter experts in different areas of relevance to the subject to be discussed: Ian's role was to help determine the mathematical impact and correctness of Bernstein's proposal: are the mathematical assumptions correct? Did the author make a mathematical error in the paper? Ian did not identify errors in the math, though cautioned that the interconnections required by an actual device would represent a challenge of significant engineering impact. (Which, as Nicko addressed in his previous posts to this list, he too considered to be the limiting factor on performance). Having thus established, as well as it could been established at the time, that the paper that triggered the discussion appeared to not contain mathematical errors, Nicko, as the subject matter expert in building cryptographic hardware implementations, presented what the math meant from an engineering perspective. In particular, can a device be built based on the mathematical assumptions, how much would it cost to build such a device, and what would the device's operating characteristics be? It is correct that Nicko presented estimates that literally were being refined during the panel session. Naturally, I would not have even considered posting such hasty generated estimates to a widely-read mailing list. (More on that later). Interestingly enough, the reaction to the estimates from the attendees at the conference, which contained many well-known cryptographers, was quite different from what I would have expected. Nobody stood up, and FC is a conference quite amenable to open discussion, that they found the suggestion that 1024-bit RSA could be broken by a well-resourced attacker in operationally significant times to be unrealistic. The most vocal comment in the ensuing discussion came from Yvo Desmedt, who pointed out that no expert in the field should be surprised by these results, since it was pointed out in Beth, Frisch, and Simmons Public-Key Cryptography: State of the Art and Future Directions, LNCS 578, published in back 1992, ten years ago, that 1024-bit keys would be suitable for protection against a national adversary for about another 10 years: until about 2002. As it so happens, this the year 2002. Given how panels are assembled and the role they fulfill, I thought it would be understood that when one writes that certain results came out of a panel that this does not imply that each panelist performed the same calculations. But rather that that the information gained from a panel (Ian: math appears to be correct, Nicko: if the math is correct, these are the engineering implications of the math) are based on the combined input from the panelists. My apologies if this process of a panel was not understood by all readers and some readers therefore interpreted my post to indicate that both Ian and Nicko performed parallel engineering estimates. 2) Immediately after the panel, a reporter for the Financial Times in attendance approached me, inquiring if these estimates had already been published in the media. I told him that I was not aware of any such publications and that this was the first time I had heard these estimates. He informed me that he intended to publish this information in a matter of days. I don't know if he wrote the article or not; I am not a Financial Times subscriber. It was not until at least a week after FC that I contacted Nicko inquiring if he still believed that his
Re: objectivity and factoring analysis
Anonymous wrote: Nicko van Someren writes: The estimate of the cost of construction I gave was some hundreds of millions of dollars, a figure by which I still stand. But what does that mean, to specify (and stand by) the cost of construction of a factoring machine, without saying anything about how fast it runs? Heck, we could factor 1024 bit numbers with a large abacus, if we don't care about speed. A cost figure is meaningless unless in the context of a specific performance goal. You'd need a large abacus and a vary large stack of paper... If you had read the Bernstein proposal in detail you would understand that (among other things) it details the conceptual design of a machine for computing kernels in a large, sparse matrix. The design talks of the number of functional units and the nature of the communication between these units. What I set out to do was look at how complex those units are and how hard it would be to connect them and to place a cost on this. I was then asked how fast this machine would run and I tried to do the calculation on the spot without a copy of the proposal to hand, and came up with a figure on the order of a second based on very conservative hardware design. This figure is *wildly* erroneous as a result of both not having the paper to hand and also not even having an envelope on the back of which I could scratch notes. And yet here you say that it took you completely by surprise when someone asked how fast the machine would run. In all of your calculations on the design of the machine, you had apparently never calculated how fast it would be. I'm sorry, but I don't think at infinite speed. I started this process after lunch and the panel session started at 1:30pm. I did say that this was an impromptu session. How could this be? Surely in creating your hundreds of millions of dollars estimate you must have based that on some kind of speed consideration. How else could you create the design? This seems very confusing. See my comments above. The costing was based on transistor count and engineering costs. The design suggested in the Bernstein proposal does not have a simple size/time trade-off since the size of the system is proscribed by the algorithm. And, could you clarify just a few more details, like what was the size you were assuming for the factor base upper bounds, and equivalently for the size of the matrix? I used the number 10^9 for the factor base size (compared to about 6*10^6 for the break of the 512 bit challenge) and 10^11 for the weight of the matrix (compared to about 4*10^8 for RSA512). Again these were guesses and they certainly could be out by an order of magnitude. This would give us a better understanding of the requirements you were trying to meet. And then, could you even go so far as to discuss clock speeds and numbers of processing and memory elements? Just at a back of the envelope level of detail? OK, here are the numbers I used. Again I preface this all with it being order of magnitude estimates, not engineering results. It's based on a proposal, not a results paper, and there are doubtless numerous engineering details that will make the whole thing more interesting. The matrix reduction cells are pretty simple and my guess was that we could build the cells plus inter-cell communication in about 1000 transistors. I felt that, for a first order guess, we could ignore the transistors in the edge drivers since for a chip with N cells there are only order N^(1/2) edge drivers. Thus I guessed 10^14 transistors which might fit onto about 10^7 chips which in volume (if you own the fabrication facility) cost about $10 each, or about $10^8 for the chips. Based on past work in estimating the cost of large systems I then multiplied this by three or four to get a build cost. As far at the speed goes, this machine can compute a dot product in about 10^6 cycles. Initially I thought that the board to board communication would be slow and we might only have a 1MHz clock for the long haul communication, but I messed up the total time and got that out as a 1 second matrix reduction. In fact to compute a kernel takes about 10^11 times longer. Fortunately it turns out that you can drive from board to board probably at a few GHz or better (using GMII type interfaces from back planes of network switches). If we can get this up to 10GHz (we do have lots to spend on RD here) we should be able to find a kernel in somewhere around 10^7 seconds, which is 16 weeks or 4 months. There are, of course, a number of other engineering issues here. One would want to try to work out how to build this machine to be tolerant of hardware faults since getting 10^7 chips to all run faultlessly for months at a time is tough to say the least. Secondly, we are going to need some neat power reduction techniques in these chips to dissipate the huge power that it needs, which will likely run to 10^8 watts or so so the
Re: objectivity and factoring analysis
Nicko writes: [...] the Bernstein proposal [...] (among other things) it details the conceptual design of a machine for computing kernels in a large, sparse matrix. The design talks of the number of functional units and the nature of the communication between these units. What I set out to do was look at how complex those units are and how hard it would be to connect them and to place a cost on this. [...] OK, here are the numbers I used [...] we should be able to find a kernel in somewhere around 10^7 seconds, which is 16 weeks or 4 months. For people who aren't following as closely I think it would be useful to remind that this is an estimate of the building cost and running time of one aspect of computation in the overal proposal. (You give a rough running-time estimate which some might misunderstand). The _overall_ running time of the algorithm and whether it is even any faster or more economical than existing algorithms remains _unknown_ due to the asymptotic result which the experiment is intended to investigate. If the hardware were to be built it might for example turn out that the asymptotic result may only start to offer speedups at far larger key sizes and if this were the case, depending on the results it could be that the approach turns out to offer no practical speed-ups for the for-seeable future. Or it might turn out that it does offer some incremental improvement, and even that key sizes should be increased. But right now no one knows. Adam btw. As disclaimed in the original post no insult was intended -- merely more accurate information given the somewhat wild speculations. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: objectivity and factoring analysis
- Forwarded message from Adam Back [EMAIL PROTECTED] - To: Cryptography [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] From: Adam Back [EMAIL PROTECTED] Subject: objectivity and factoring analysis Date: Fri, 19 Apr 2002 14:51:59 +0100 Sender: [EMAIL PROTECTED] I'd just like to make a few comments about the apparently unnoticed or unstated conflicts of interest and bias in the analysis surrounding Bernstein's proposal. ... - I'm not sure any of the respondents so far except Bernstein have truly understood the math -- there are probably few who do, factoring being such a narrow research area. I'm inclined to agree with you there ... - Nicko van Someren -- the person credited with originally making the exaggerated, or at least highly worst case interpretation at the FC02 panel -- has a conflict interest -- hardware accelerator gear that ncipher sell will be more markedly needed if people switch to 2048 or larger keys. Nicko has made no public comments in the resulting discussion. Since you mention it, I will make a comment for the purpose of clearing up a number of misunderstandings about what I said and the context in which the comments were made. At the Financial Cryptography 2002 conference a small and impromptu panel was convened to discuss the Bernstein proposal. Since I'm in the business of building hardware I was asked to comment on the cost of building some of the hardware described therein. I limited myself to comments about the design for the engine that could be used to take the results of the sieve process and compute values leading to a pair of roots, and furthermore prefaced and qualified my comments with strong statements about any numbers being very rough back of an envelope calculations. The estimate of the cost of construction I gave was some hundreds of millions of dollars, a figure by which I still stand. I was then asked how fast this machine would run and I tried to do the calculation on the spot without a copy of the proposal to hand, and came up with a figure on the order of a second based on very conservative hardware design. This figure is *wildly* erroneous as a result of both not having the paper to hand and also not even having an envelope on the back of which I could scratch notes. The number was based on a miscalculation of the number of clock ticks the circuit would need by a factor of 10^11, which is a vast error that is only slightly moderated by the fact that on further analysis I concluded that the hardware could be made to operate on a clock that ran between 10^3 and 10^4 times faster since the inter-circuit communication did not need to be as slow as I had originally thought. Thus I think that with care a matrix reduction machine of the sort described could be built to run in a few weeks or months for 1024 bit keys. Despite all the qualifying of these statements I felt then, and still feel now, that if you have keys that you think rich governments might genuinely be interested in then you should use ones that are longer than 1024 bits. If you have personal information that you want to keep secret from rich governments for many years to come then you should probably use longer keys anyway. After all we can expect on past form that the security agencies are some years ahead of the academic state of the art in this field anyway. On the other hand if you are moving general commercial data around on an everyday basis I don't think that there is much wrong with 1024 bits keys and I would not, and have not, suggested that there is anything insecure about such key lengths for, say, electronic banking or e-commerce using SSL. I have to say that Adam's suggestion that there was some sort of ulterior motive for my comments is both disingenuous and somewhat insulting. In the context of short and impromptu discussion on a topic which people felt was a live one, I made a back of the envelope calculation in which I used the time figure as the cost figure and came up with totally the wrong number. I wasn't expecting that this was going to then be used as the basis for anything other than maybe an excuse for looking into the problem a little more deeply. The critical problem here seems to be that Lucky then quoted this number on a mailing list before I'd had a chance to look more closely. I don't think that there was any conflict of interest involved at all given both the nature of the discussion and the fact that these days cryptographic acceleration is pretty peripheral to the nature of my business. - Lucky on the other hand suggested a practical security engineering approach to start to plan for possibility of migrating to larger key sizes. Already one SSH implementation added a configuration option to select a minimum key size accepted by servers as a result. This seems like a positive outcome. Generally the suggestion to move to 2048 bit keys seems like a good idea to me. Somewhat like MD5 - SHA1, MD5 isn't broken for most
Re: objectivity and factoring analysis
Nicko van Someren writes: The estimate of the cost of construction I gave was some hundreds of millions of dollars, a figure by which I still stand. But what does that mean, to specify (and stand by) the cost of construction of a factoring machine, without saying anything about how fast it runs? Heck, we could factor 1024 bit numbers with a large abacus, if we don't care about speed. A cost figure is meaningless unless in the context of a specific performance goal. I was then asked how fast this machine would run and I tried to do the calculation on the spot without a copy of the proposal to hand, and came up with a figure on the order of a second based on very conservative hardware design. This figure is *wildly* erroneous as a result of both not having the paper to hand and also not even having an envelope on the back of which I could scratch notes. And yet here you say that it took you completely by surprise when someone asked how fast the machine would run. In all of your calculations on the design of the machine, you had apparently never calculated how fast it would be. How could this be? Surely in creating your hundreds of millions of dollars estimate you must have based that on some kind of speed consideration. How else could you create the design? This seems very confusing. And, could you clarify just a few more details, like what was the size you were assuming for the factor base upper bounds, and equivalently for the size of the matrix? This would give us a better understanding of the requirements you were trying to meet. And then, could you even go so far as to discuss clock speeds and numbers of processing and memory elements? Just at a back of the envelope level of detail? Adam Back wrote: The mocking tone of recent posts about Lucky's call seems quite misplaced given the checkered bias and questionable authority of the above conflicting claims we've seen quoted. No, Lucky made a few big mistakes. First, he invoked Ian Goldberg's name as a source of the estimate, which was wrong. Second, he presented Nicko's estimate as being more authoritative than it actually was, as Nicko makes clear here. And third, he fostered panic by precipitously revoking his key and widely promulgating his sky is falling message. We wouldn't be in this situation of duelling bias and authority if people would provide some minimal facts and figures rather than making unsubstantiated claims. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
