Slashdot Mirror

That this likely means the exact opposite. Elliptic Curve Cryptography is relatively difficult to crack (not unlike RSA). More to the point, it's also not liable to factorization attacks like RSA is. Furthermore, the best crack of elliptic curve technology is of a 109-bit key, and still took 3,600 or 15,000 computer-years (whether it's a binary or prime field case, respectively).

Nintendo's not stupid. They've used RSA encryption to keep the average hacker out of DS-wireless homebrew, and this is most likely a mandated response to the Splinter Cell hack that allowed soft modding on the Xbox. It won't stop hacking through security holes in the internet protocols (a-la PSO+BBA), but they're certainly making efforts to prevent corrupted data from opening up softmod paths.

That this likely means the exact opposite. Elliptic Curve Cryptography is relatively difficult to crack (not unlike RSA). More to the point, it's also not liable to factorization attacks like RSA is. Furthermore, the best crack of elliptic curve technology is of a 109-bit key, and still took 3,600 or 15,000 computer-years (whether it's a binary or prime field case, respectively).

Nintendo's not stupid. They've used RSA encryption to keep the average hacker out of DS-wireless homebrew, and this is most likely a mandated response to the Splinter Cell hack that allowed soft modding on the Xbox. It won't stop hacking through security holes in the internet protocols (a-la PSO+BBA), but they're certainly making efforts to prevent corrupted data from opening up softmod paths.

Of course, like most on here, I will relish the day that the LZW patent expires. But look at how long that took to expire. Every day someone patents yet another obvious invention and it holds everybody back.

Take the Certicom 'Patents' on Eliptic Curve cryptography (ECC). Certicom act as if they own ECC - the write it on practically everything they publish.

Yet on close analysis their patents give them almost no real control of ECC. The long and short of it that anything that operates on GF(p) is not covered.

The consequences of this is that NOBODY is using ECC, despite the fact that it's faster and has shorter keys. The whole field is held back for 20 years and nobody can make any progress.

It's not even used in Europe where these patents don't exist. Let me repeat this: The fact that some jerk of a company says it's theirs means the *whole* world doesn't use me.

I really wonder what goes through the minds of these poeple. Nobody wants to pay a fucktard like Certicom (tm) for a license for their mathematics. Nobody in the history of cryptography has made any serious amount of money from selling a security scheme. Why bother?

Simon

I'm suggesting they start at around 2^200, and go up from there. I found this handy little chart at certicom, so here we're looking at things more in the order of 2^400 and 2^500 as standard key sizes. Those should be quite safe for now.

I'm still curous to see the details of the attack anyway, an abstract doesn't tell you very much.

Jedidiah.

When I was an undergrad at the University of Waterloo (located in Waterloo, Ontario [Canada]), I had the benefit of having both Alfred and Scott as professors.

Alfred taught C&O 487, which is Applied Crytography. He is an excellent lecturer and actively involved in the crypto community. His level of intelligence, professionalism, and kindness never cease to amaze me.

Scott "taught" C&O 331, which is Coding Theory. He's a down-to-Earth kind of guy, who really didn't know how to teach a class, but boy did he sure know how to simplify tough concepts. His trademark is that he's what we called a "celebrity professor". He never used his office (located at St. Jerome's on campus) to the point where if you looked through his window, you'd never see him there, and everything would be packed up in boxes. His computer was never hooked up and chairs were stacked up such that no one could actually sit down with him and have a conversation :).

He was a celebrity professor because he worked at Certicom, and was one the company's original founders. He was paid the highest amount out of any C&O professor at the University, and barely ever made it to teach class. He'd spend the day at Certicom instead, and send one of his grad students over from Toronto to Waterloo (despite the weather, since Coding Theory is only available in the Winter term) to teach the class. Sometimes, when there were no grads available to do his teaching duties, he'd ask Alfred (who wrote his PhD under the supervision of Mr. Vanstone) to fill in. Whenever Alfred taught the class I learned 200% more than if Scott were to teach the exact same material.

All that aside, it's nice to see these two fellows get their name in bright lights after all of their hard work throughout the years.

The contest website doesn't mention a $1M prize, but from the "details" pdf, it looks like you can earn the $1M prize by solving 19 smaller problems, each with their own bounty. $30k for an "infeasable" problem seems a little low to me... I imagine the mob may pay more ;-)

From the pdf: The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course, a new algorithm for the ECDLP is discovered.

The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by existing and forthcoming ANSI banking standard

Challenge Field-size(in-bits) Estimated-number-of-machine-days Prize(US$)
Elliptic curves over f2^m - Exercises:
ECC2-79 79 352 Handbook of Applied Cryptography & Maple V software
ECC2-89 89 11278 Handbook of Applied Cryptography & Maple V software
ECC2K-95 97 8637 $ 5,000
ECC2-97 97 180448 $ 5,000

Level I challenges:
ECC2K-108 109 1.3 x 10 6 $ 10,000
ECC2-109 109 2.1 x 10 7 $ 10,000
ECC2K-130 131 2.7 x 10 9 $ 20,000
ECC2-131 131 6.6 x 10 10 $ 20,000

Level II challenges:
ECC2-163 163 6.2 x 10 15 $ 30,000
ECC2K-163 163 3.2 x 10 14 $ 30,000
ECC2-191 191 1.0 x 10 20 $ 40,000
ECC2-238 239 2.1 x 10 27 $ 50,000
ECC2K-238 239 9.2 x 10 25 $ 50,000
ECC2-353 359 1.3 x 10 45 $ 100,000
ECC2K-358 359 2.8 x 10 44 $ 100,000

Elliptic curves over Fp - Exercises:
ECCp-79 79 146 Handbook of Applied Cryptography & Maple V software
ECCp-89 89 4360 Handbook of Applied Cryptography & Maple V software
ECCp-97 97 71982 $ 5,000

Level I challenges:
ECCp-109 109 9.0 x 10 6 $ 10,000
ECCp-131 131 2.3 x 10 10 $ 20,000

Level II challenges:
ECCp-163 163 2.3 x 10 15 $ 30,000
ECCp-191 191 4.8 x 10 19 $ 40,000
ECCp-239 239 1.4 x 10 27 $ 50,000
ECCp-359 359 3.7 x 10 45 $ 100,000

The contest website doesn't mention a $1M prize, but from the "details" pdf, it looks like you can earn the $1M prize by solving 19 smaller problems, each with their own bounty. $30k for an "infeasable" problem seems a little low to me... I imagine the mob may pay more ;-)

From the pdf: The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course, a new algorithm for the ECDLP is discovered.

The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by existing and forthcoming ANSI banking standard

Challenge Field-size(in-bits) Estimated-number-of-machine-days Prize(US$)
Elliptic curves over f2^m - Exercises:
ECC2-79 79 352 Handbook of Applied Cryptography & Maple V software
ECC2-89 89 11278 Handbook of Applied Cryptography & Maple V software
ECC2K-95 97 8637 $ 5,000
ECC2-97 97 180448 $ 5,000

Level I challenges:
ECC2K-108 109 1.3 x 10 6 $ 10,000
ECC2-109 109 2.1 x 10 7 $ 10,000
ECC2K-130 131 2.7 x 10 9 $ 20,000
ECC2-131 131 6.6 x 10 10 $ 20,000

Level II challenges:
ECC2-163 163 6.2 x 10 15 $ 30,000
ECC2K-163 163 3.2 x 10 14 $ 30,000
ECC2-191 191 1.0 x 10 20 $ 40,000
ECC2-238 239 2.1 x 10 27 $ 50,000
ECC2K-238 239 9.2 x 10 25 $ 50,000
ECC2-353 359 1.3 x 10 45 $ 100,000
ECC2K-358 359 2.8 x 10 44 $ 100,000

Elliptic curves over Fp - Exercises:
ECCp-79 79 146 Handbook of Applied Cryptography & Maple V software
ECCp-89 89 4360 Handbook of Applied Cryptography & Maple V software
ECCp-97 97 71982 $ 5,000

Level I challenges:
ECCp-109 109 9.0 x 10 6 $ 10,000
ECCp-131 131 2.3 x 10 10 $ 20,000

Level II challenges:
ECCp-163 163 2.3 x 10 15 $ 30,000
ECCp-191 191 4.8 x 10 19 $ 40,000
ECCp-239 239 1.4 x 10 27 $ 50,000
ECCp-359 359 3.7 x 10 45 $ 100,000

Okay, so why does the linked webpage indicate that the 109 challenge was Completed in November of 2002?

The contest website doesn't mention a $1M prize, but from the "details" pdf, it looks like you can earn the $1M prize by solving 19 smaller problems, each with their own bounty. $30k for an "infeasable" problem seems a little low to me... I imagine the mob may pay more ;-)

From the pdf: The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course, a new algorithm for the ECDLP is discovered.

The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by existing and forthcoming ANSI banking standard

Challenge Field-size(in-bits) Estimated-number-of-machine-days Prize(US$)
Elliptic curves over f2^m - Exercises:
ECC2-79 79 352 Handbook of Applied Cryptography & Maple V software
ECC2-89 89 11278 Handbook of Applied Cryptography & Maple V software
ECC2K-95 97 8637 $ 5,000
ECC2-97 97 180448 $ 5,000

Level I challenges:
ECC2K-108 109 1.3 x 10 6 $ 10,000
ECC2-109 109 2.1 x 10 7 $ 10,000
ECC2K-130 131 2.7 x 10 9 $ 20,000
ECC2-131 131 6.6 x 10 10 $ 20,000

Level II challenges:
ECC2-163 163 6.2 x 10 15 $ 30,000
ECC2K-163 163 3.2 x 10 14 $ 30,000
ECC2-191 191 1.0 x 10 20 $ 40,000
ECC2-238 239 2.1 x 10 27 $ 50,000
ECC2K-238 239 9.2 x 10 25 $ 50,000
ECC2-353 359 1.3 x 10 45 $ 100,000
ECC2K-358 359 2.8 x 10 44 $ 100,000

Elliptic curves over Fp - Exercises:
ECCp-79 79 146 Handbook of Applied Cryptography & Maple V software
ECCp-89 89 4360 Handbook of Applied Cryptography & Maple V software
ECCp-97 97 71982 $ 5,000

Level I challenges:
ECCp-109 109 9.0 x 10 6 $ 10,000
ECCp-131 131 2.3 x 10 10 $ 20,000

Level II challenges:
ECCp-163 163 2.3 x 10 15 $ 30,000
ECCp-191 191 4.8 x 10 19 $ 40,000
ECCp-239 239 1.4 x 10 27 $ 50,000
ECCp-359 359 3.7 x 10 45 $ 100,000

The contest website doesn't mention a $1M prize, but from the "details" pdf, it looks like you can earn the $1M prize by solving 19 smaller problems, each with their own bounty. $30k for an "infeasable" problem seems a little low to me... I imagine the mob may pay more ;-)

From the pdf: The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course, a new algorithm for the ECDLP is discovered.

The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by existing and forthcoming ANSI banking standard

Challenge Field-size(in-bits) Estimated-number-of-machine-days Prize(US$)
Elliptic curves over f2^m - Exercises:
ECC2-79 79 352 Handbook of Applied Cryptography & Maple V software
ECC2-89 89 11278 Handbook of Applied Cryptography & Maple V software
ECC2K-95 97 8637 $ 5,000
ECC2-97 97 180448 $ 5,000

Level I challenges:
ECC2K-108 109 1.3 x 10 6 $ 10,000
ECC2-109 109 2.1 x 10 7 $ 10,000
ECC2K-130 131 2.7 x 10 9 $ 20,000
ECC2-131 131 6.6 x 10 10 $ 20,000

Level II challenges:
ECC2-163 163 6.2 x 10 15 $ 30,000
ECC2K-163 163 3.2 x 10 14 $ 30,000
ECC2-191 191 1.0 x 10 20 $ 40,000
ECC2-238 239 2.1 x 10 27 $ 50,000
ECC2K-238 239 9.2 x 10 25 $ 50,000
ECC2-353 359 1.3 x 10 45 $ 100,000
ECC2K-358 359 2.8 x 10 44 $ 100,000

Elliptic curves over Fp - Exercises:
ECCp-79 79 146 Handbook of Applied Cryptography & Maple V software
ECCp-89 89 4360 Handbook of Applied Cryptography & Maple V software
ECCp-97 97 71982 $ 5,000

Level I challenges:
ECCp-109 109 9.0 x 10 6 $ 10,000
ECCp-131 131 2.3 x 10 10 $ 20,000

Level II challenges:
ECCp-163 163 2.3 x 10 15 $ 30,000
ECCp-191 191 4.8 x 10 19 $ 40,000
ECCp-239 239 1.4 x 10 27 $ 50,000
ECCp-359 359 3.7 x 10 45 $ 100,000

I stated this in another post, but I've got a link now:

The NSA is not lisencing software, it is lisencing the right to use Certicom's ECC cryptosystem. Cryptosystems now are usually known even when proprietary to allow mathematicians and cryptographers the ability to test the security of it. (The RSA cryptosystem for instance is thoroughly explained on RSA's web-site, but you would still need a lisence to use the algorithm in a program)

I found a tutorial by Certicom on their ECC cryptosystem here.

PS. I could be wrong, but from the article it seems that "intellectual property" and "This is the first time that the NSA has endorsed any sort of public-key cryptography system." that they are not actually lisencing software but are in fact lisencing the cryptosystem. If I am wrong, I humbly apologize.

The algorithm they used is patented and very much open for criticism. It would need to be fore NSA to choose it. Think of it like RSA where the algorithm was patented as well (many open source applications use RSA now, since the license has expired).

Dr. Scott A. Vanstone is a professor at University of Waterloo, so it is kind of neat to see one of my profs in the news (I knew about the company, but they haven't had much going for them for a while). He teaches Coding Theory (CO 331) and is the Executive Director of Centre for Applied Cryptographic Research

Certicom Corp.
5520 Explorer Drive, 4th Floor
Mississauga, Ontario
Canada L4W 5L1

So where's the discrepancy? Did we get really lucky and hit the answer 5% of the way through the search? Do the "10308 members" really represent 10 machines each? Did the initial estimate assume 500MHz machines and by 547 days later, most people were running 1.5GHz machines? Or did the implementers do some good programming hacks to make a much faster search program? Or was one of the implementors using Pixar's rendering cluster at night in between movies?

According to Ulf Möller there will be a patch made before the next release to isolate the ECC code in case of patent concerns. The ECC code can be included or excluded based on a configure flag like the present RC5 and IDEA algorithms which are still patented in various parts of the world.

Compile-time flags already exist to turn on and off ECC code in OpenSSL - they are OPENSSL_NO_EC, OPENSSL_NO_ECDH, and OPENSSL_NO_ECDSA. Additionally, there's a compile-time flag to turn on or off the code that is allegedly encumbered by Sun patents and a compile-time flag to turn off code that might be encumbered by another company's patents.

Furthermore, this is not new to OpenSSL nor to the crypto world in general. Lots of algorithms included in OpenSSL are covered by patents, RC5 and IDEA being prime examples. The OpenSSL license and most other open-source licenses only give you rights to copy and distribute the code, not necessarily to use it. Just as it was illegal to use RSA cryptography in the United States before Sept. 2000 without licensing it from RSA Security, so too is it illegal to use RC5 without licensing it. The OpenSSL license does not and cannot grant you those rights.

The Sun provision is there to grant users additional rights. As the previous poster indicates, it allows you to use any algorithm that Sun has a patent on in the context of OpenSSL and be free from threat of patent infringement lawsuit provided you don't sue Sun over a related issue.

Is it reasonable for Sun to ask you to not to sue them for code they gave away for free in return for not suing you? That's a business decision you make when you decide to use OpenSSL code.

Is it reasonable for Sun to say you can use the encumbered code in the context of OpenSSL but not in other contexts (like a hardware accelerator)? Under US law, they've got the right to do that. Whether you agree with patents or not is a different argument.

'elliptic curve' encryption technology, (developed by Whitfield Diffie of Diffie-Hellman public key fame)

Elliptic curve cryptography was indepentantly
invented by Neal Koblitz, Professor of Mathematics at the University of Washington and Victor Miller who was then at IBM.
(Source)

Whitfield Diffie is Sun's chief security officer, and co-invented public-key cryptography.

...given that it was invented by NeXT?

Sorry, Ellipitic curve cryptography was invented independantly by Neal Koblitz, Professor of Mathematics at the University of Washington and Victor Miller who was then at IBM.
(Source)

To be clear, what has been broken is a single key on an elliptic curve which has a 108 bit order. The smallest key size which Certicom commercially recommends is a 160 bit key, which is on the order of 2^26 times as hard to break (a factor of approximately 67 million).

The papers available at www.cryptosavvy.com are a good, independent, and recent reference for key size comparisons.

Tim Dierks
Chief Technical Officer, Certicom
tdierks@certicom.com

Actually, this just validates ECC, as it was fully expected that the 108-bit challenge was feasible (ie. could be broken in reasonable time with massive computing power). The linked site seems to indicate it took about 5 months (searching about 76% of the problem space), which is roughly what the challenge issuers anticipated.

The 97-bit challenge was broken (by the same project) in a couple of months, also in line w/ prediction.

The next challenge is 131 bits, which should take a LOT more time and power to break. The challengers can use these results to justify their claim that the 161+ bit challenges are infeasible.

FWIW, people in the field believe a 160 bit ECC problem to be roughly equivalent to 1024 bits of RSA, which is currently WAY beyond what can be feasibly attacked (barring no advances in factoring technology)

ECC has a bright future and these challenges only serve to emphasize that point.

See the link on the Certicom ECC challenge for more info.

• Secret!
• Strip

Now that the congradulations are over. I would like to say "DARN!" RSA has not exactly been overly kind to the OpenSource community inside the US. C2Net Software has been extreamly kind to ensure funding of the SSLeay development. Even in the face of SSLeay based Apache mod_SSL and in the face of mod_SSL based RedHat Secure Web Server (which was clearly directly competting with C2Net's Stronghold), C2Net has continued to push SSLeay forward. Counterpane Systems has pritty much dontated Twofish encryption to the world, thus putting crypto experts in a better position to attack companies that have promoted their XOR "encryption" enabled product as being secure. Since Twofish is free, fast and impliments well in software and hardware there is no excuse for continuing to push XOR as "encryption." Certicom Corp. has been extreamly friendly regarding third-party non-commerical implimentations of Elliptic Curve Crypto (which has shown itself to be a possible alternative to RSA). How does RSA measure up to all these other companies? Well, RSA puts on additional restrictions on RSA than ITAR ever has or well! While ITAR makes it *difficult* to make cryptography available on the internet for peer-review. RSA makes alternate implimentations of RSA *impossible* to legally make available for peer-review. The only RSA "educational" use there can be is on their own RSAlib. While exploring alternative meathods (languages, done via hardware, etc) of existing crypto algorithms can help keep cryptographer's minds sharp, RSA attacks any peer review of other methods. To take things a step further, RSA goes all out in enforcing it's patent on both encryption and *DEcryption*. This is despite that finding a solution to a formula (2+x=4 hence x=2) is not patentiable. While using prime numbers for encryption maybe a unique patentable concept, the formula for decryption has pritty much been dictated by the formula used for encryption. Hence, the decryption of RSA is pritty much the solution of a formula and should not be patentable. RSA knows this but continues to ride on the stupidity of the US patent office and the non-crypto savvy court system. Hence, I definately think there are preferable companies in the crypto game other than RSA.

Btw, to see creative use of applied cryptography, look into Zeroknowledge. They are presently looking for beta tester for their linux (the first platform type they have software available for!) privacy software. This is one product you have to check out!