Re: 112-bit prime ECDLP solved
At 7:54 AM -0600 7/18/09, Zooko Wilcox-O'Hearn wrote: This involves deciding whether a 192-bit elliptic curve public key is strong enough... Why not just go with 256-bit EC (128-bit symmetric strength)? Is the 8 bytes per signature the issue, or the extra compute time? --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
On Sunday,2009-07-19, at 13:24 , Paul Hoffman wrote: At 7:54 AM -0600 7/18/09, Zooko Wilcox-O'Hearn wrote: This involves deciding whether a 192-bit elliptic curve public key is strong enough... Why not just go with 256-bit EC (128-bit symmetric strength)? Is the 8 bytes per signature the issue, or the extra compute time? Those are two good guesses, but no. The main concern is the size of the public key. This is why (if I understand correctly), hyperelliptic curves might eventually offer public key signatures which are twice as good for the purposes of TahoeLAFS as elliptic curves. (By which I mean, the keys are half as big.) I discussed this topic a bit in a subsequent message to the cryptography mailing list entitled Why hyperelliptic curves?. Actually, the computation time matters, too. Our measurements on an ARM 266 MHz embedded system showed a significant penalty for 256-bit ECDSA vs. 192-bit: http://allmydata.org/pipermail/tahoe-dev/2009-June/002083.html Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
By the way, we've recently been planning our next crypto-capabilities design for the TahoeLAFS secure distributed filesystem. This involves deciding whether a 192-bit elliptic curve public key is strong enough, as well as subtler and more unusual issues involving embedding keys directly into filehandles or URLS, multiple-targets attacks, and a novel public key scheme that I invented (and that therefore I think we shouldn't use): http://allmydata.org/pipermail/tahoe-dev/2009-July/002314.html Your comments would be appreciated! I've added ta...@hyperelliptic.org and jam...@echeque.com to the list of addresses that can post to tahoe-dev without being subscribed. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
On Jul 14, 2009, at 12:43 PM, James A. Donald wrote: 2033130 Subsequent expansions in computing power will involve breaking up Jupiter to build really big computers, and so forth, which will slow things down a bit. So 144 bit EC keys should be good all the way to the singularity and a fair way past it. Prediction is very difficult, especially about the future. I have researched the possibility of 50 or 100 year key sizes. All we have to do is look back 50 years to the (unbreakable) Enigma, and 30 years to the famous Sci.Am article by Rivest that said it would take 40 quadrillion years to break the challenge, which actually took 25, or more recently, or FEAL, or RC-4 (WEP), or MD-5, or SHA-1, or, or need I say more? If we assume that all knowledge to be discovered has been discovered, and all mathematical insight humanity is capable of has been achieved, you are correct that 144 bit EC keys are good all the way to the singularity (which actually depends on the Hubble constant, but I digress) and that everything that could be invented has been invented. I believe it is folly to suggest that 144 bit keys will never be broken. Frankly, I hope to see the day. Jim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
So with about 1 000 000 USD and a full year you would get 122 bits already now and agencies have a bit more budget than this! Furthermore, the algorithm parallelizes extremely well and can handle a batch of 100 targets at only 10 times the cost. No it cannot handle a bunch of a hundred targets at only ten times the cost. It is already parallelized. A hundred targets is a hundred times the cost. NO. Read Fabian Kuhn, René Struik: Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms. Selected Areas in Cryptography 2001: 212-229 Section 4. Besides, the estimates assume only playstations and the EPFL code instead of special purpose hardware which would give an extra speed up. And, no, I'm not suggesting to use the entire US gross national product for a year to break your key but given that that breaks 172 bits (SHARCS 2006 estimates for ECC-163 and 9 bits to scale from USD 5.8*10^11 to the GDP 1.4*10^13) I'm not comfortable with 160 bits, let alone 144. All the best Tanja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
Tanja Lange wrote: So with about 1 000 000 USD and a full year you would get 122 bits already now and agencies have a bit more budget than this! Furthermore, the algorithm parallelizes extremely well and can handle a batch of 100 targets at only 10 times the cost. No it cannot handle a bunch of a hundred targets at only ten times the cost. It is already parallelized. A hundred targets is a hundred times the cost. But let us not think small. Suppose the president says Break James Donald's key. I don't care how much it costs. The sky is the limit and they devote the entire US gross national product for a year to breaking James Donald's key in a year. Then they can break a 170 bit key. But I rather doubt that they will. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
Hi all, We are pleased to announce that we have set a new record for the elliptic curve discrete logarithm problem (ECDLP) by solving it over a 112-bit finite field. The previous record was for a 109-bit prime field and dates back from October 2002. See for more details our announcement at http://lacal.epfl.ch/page81774.html. Computing power doubles every 18 months to two years, so the required EC length should gain a bit every year or every nine months. Which suggests that existing deployments should default to 128 bits. with 160 bits being overkill. Of course overkill does not cost much. If one shoots someone the head, it is wise to follow up with a second shot through the head at very short range just to be on the safe side. YearBreakable keys. 2009112 2010113 2015117 2020121 2025124 I am assuming a rapid rate of progress, in which case line widths halve every four years. In which case Moore's law breaks in 2033 when we get nanometer line widths, for lines will then be molecules - probably carbon nanotubes. 2033130 Subsequent expansions in computing power will involve breaking up Jupiter to build really big computers, and so forth, which will slow things down a bit. So 144 bit EC keys should be good all the way to the singularity and a fair way past it. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 112-bit prime ECDLP solved
We are pleased to announce that we have set a new record for the elliptic curve discrete logarithm problem (ECDLP) by solving it over a 112-bit finite field. The previous record was for a 109-bit prime field and dates back from October 2002. First of all congratulations to the team at EPFL! Which suggests that existing deployments should default to 128 bits. with 160 bits being overkill. Of course overkill does not cost much. If one shoots someone the head, it is wise to follow up with a second shot through the head at very short range just to be on the safe side. James, do I really have to point out the obvious that just because 112 bits is a new record this does not mean that 113 is undoable today. The coolness of this result is that a smallish cluster of low cost machines could do this computation in only half a year. 200 PS3s cost you no more than 200 x 400 USD at published prices - and less if you buy that many at once. So with about 1 000 000 USD and a full year you would get 122 bits already now and agencies have a bit more budget than this! Furthermore, the algorithm parallelizes extremely well and can handle a batch of 100 targets at only 10 times the cost. So, yes, we sure will be able to break 130 bits in 2033 - but certainly much sooner if anyone tries. Tanja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
112-bit prime ECDLP solved
Hi all, We are pleased to announce that we have set a new record for the elliptic curve discrete logarithm problem (ECDLP) by solving it over a 112-bit finite field. The previous record was for a 109-bit prime field and dates back from October 2002. Our calculation was done on a cluster of more than 200 PlayStation 3 game consoles at the EPFL. See for more details our announcement at http://lacal.epfl.ch/page81774.html. Best regards, Joppe Bos - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
