Forgot your password?
typodupeerror
Encryption Security

ECC2-109 Winners Certified 133

Posted by CowboyNeal
from the stamp-of-approval dept.
An anonymous reader writes "The ECC2-109 encryption challenge has now been broken and certified! Certicom announced on Tuesday that the winners, a team from Ars Technica and a member of TeamIMO, will both receive $2500 each for the matching distinguished pairs that has solved the elliptical curve encryption scheme."
This discussion has been archived. No new comments can be posted.

ECC2-109 Winners Certified

Comments Filter:
  • Hmmm... (Score:5, Funny)

    by thewiz (24994) * on Thursday April 15, 2004 @10:56PM (#8877696)
    $2,500 for breaking an encryption scheme. I wonder what SETI@Home will pay me for discovering an extraterrestrial...
  • The ECC2 Challenge, sponsored by Certicom, began in November 2002, and the gross CPU time used to solve the challenge was roughly equivalent to an Athlon XP 3200+ working nonstop for 1,200 years. This victory is especially notable because it is the biggest ECC encryption challenge ever solved and will likely remain so for a while since the next challenges are an order of magnitude larger and would require years to complete using current processors.

    That's some pretty hardcore encryption.
    • Re:Wow. (Score:3, Interesting)

      by joe90 (48497)
      So I guess the moral of the story is to not use this Certicom encryption system for valuable information - it's trivially brute-forceable, for a sufficiently motivated organisation.

      Hmm, 1200 years of CPU time for a commodity PC, or to put it another way, as little as 1.5 weeks with 50,000 PC's - a cost of less than $5,000,000 in total costs to brute-force.
      • Re:Wow. (Score:5, Informative)

        by NotAnotherReboot (262125) on Thursday April 15, 2004 @11:19PM (#8877851)
        Well, obviously you adjust your encryption to what you think people will be throwing at it. That goes without saying.

        Like it said, the next one is not expected to be cracked for some time because it is far more complicated to brute force.

        If it's valuable- determine how valuable it is to others, and encrypt based on that plus some.

        For instance, this would work fine for credit cards, seeing as the cost of cracking the number would be far greater than the cost of processing power. Most of the time, however, it is far easier to avoid encryption altogether and hit those who do not bother.
        • Re:Wow. (Score:4, Interesting)

          by timeOday (582209) on Friday April 16, 2004 @12:46AM (#8878241)
          Better just to use overkill"encryption all the time. EG instead of thinking long and hard about whether it would be worth cracking something encrypted with DES, just use 3DES all the time and save your brainpower for something else.
        • Re:Wow. (Score:2, Interesting)

          by KrisHolland (660643)
          "Well, obviously you adjust your encryption to what you think people will be throwing at it. That goes without saying."

          How are you going to adjust your encryption when quantum computers will make most encryption schemes obsolete?
          • by Ckwop (707653) *
            "How are you going to adjust your encryption when quantum computers will make most encryption schemes obsolete? "

            Why FUD my friend? This just isn't true!

            The truth about quantum cryptography is that RSA and DH will be destroyed by quantum cryptography. This is due to the work of Shor [psu.edu] who famously proved that you could factor in cubic time.

            This sounds bad but we've already had good success [lanl.gov] in performing quantum key exchanges (that are unbreakable in a theoretical sense).

            What does this mean for symme
            • "This sounds bad but we've already had good success in performing quantum key exchanges (that are unbreakable in a theoretical sense). "

              That is for exchanging keys securely at a distance, for secure communication. i.e. the message is destroyed if someone tries to evesdrop on the conversation. Shor's algorithm will still shread current encryption to pieces.

              Even more interesting is that if the government, or anyone else, was smart they'd collect all the communcations that are 'secured', or people think th
        • Well, obviously you adjust your encryption to what you think people will be throwing at it. That goes without saying. ...or, actually, completely not. It's nearly always so cheap to use encryption that's completely infeasable to attack directly that you should always do that; it's crazy to use anything less to save a few cycles unless you're in a very limited resource environment.
      • Re:Wow. (Score:5, Interesting)

        by Deraj DeZine (726641) on Thursday April 15, 2004 @11:24PM (#8877880)
        I wonder what would happen if China began requiring all computers in the country to run some unspecified distributed application.

        Not trolling, just musing. I doubt such a thing would happen in any country.
      • Re:Wow. (Score:5, Informative)

        by rasafras (637995) <tamas @ p h a . j h u . edu> on Thursday April 15, 2004 @11:28PM (#8877906) Homepage
        This is a small key size for the scheme. On the website they have other challenges posted where the key size is four or eight times as long, which are deemed 'infeasible'. This was not a completely realistic security test of the ECC algorithm, they expected it to be solved.
        If this was used for real data, the key would be much longer and it would take probably a few billion years to solve.
      • by Paul Crowley (837) on Friday April 16, 2004 @03:36AM (#8878881) Homepage Journal
        ECC ("this Certicom encryption system") has turned out to be exactly as hard to break as Certicom and everyone else expected - if anything, the results of this challenge increase our confidence in it.

        109 bits was deliberately chosen to be short enough to break. The next challenge is 131 bits, which is also considered breakable (though it will be about 2048 times harder).

        After that, you get on to the "Level II" challenges, which are not considered breakable. They start at 163 bits, the least recommended for real use, and would be about 140 billion times harder to break.

        I worry about the /. moderators sometimes...
    • and would require years to complete using current processors.

      That's why I gave up on RC5-72. Even if computers continue to double every 2 years, it would still take much over a couple decades before they ever complete the contest. The extra burden it would put on CPU's must amount to several hundreds of thousands of dollars in power consumption. Hardly worth it for a $10,000 price to one individual.

      Now, unless someone spends the money to build a custome RC5 decryption hardware using massively parallel p
    • Yeah, but obviously it wasn't hardcore enough. If that encrypted message happened to be my email, I wouldn't be a very happy chap.
    • Re:Wow. (Score:3, Interesting)

      by spectrokid (660550)
      If you count 100 Watts for one of these athlons, you end up with 1025280 kWh of electrical power going in this. Even in Canada, where power is cheap (4.72/kWh) you get a total cost of 48393,216 $ CAN in power consumption alone. Kind of puts things in perspective.
  • bah (Score:5, Informative)

    by wviperw (706068) on Thursday April 15, 2004 @10:59PM (#8877706) Homepage Journal
    Only $2500? Some of the contests I've seen (namely having to do with the RSA encryption scheme) have been offering prizes upwards of 100 grand IIRC.

    I bet the computing time just to break the code probably costed a wee bit more than $2500.
    • Re:bah (Score:5, Informative)

      by stienman (51024) <adavis@ub a s i c s . com> on Thursday April 15, 2004 @11:13PM (#8877793) Homepage Journal
      This contest was $10,000. Half went to the project maintainers, and then half of the remainder (1/4) is given to each of the people who found the collision.

      So the individuals got $2,500, and whoever put the project together and hosted it got $5,000.

      -Adam
    • Re:bah (Score:5, Informative)

      by Bobdoer (727516) on Thursday April 15, 2004 @11:15PM (#8877820) Homepage Journal
      One of the other crypto distributed computing projects that's testing a higher level on encryption is only giving away $1,000 to the winner out of the $10,000 coming from RSA. Here's Distributed.net [distributed.net]'s cash distribution:
      $1000 to the winner
      $1000 to the winner's team (or to the winner if not on a team)
      $6000 to a non-profit organization chosen by all participants
      $2000 to distributed.net for building the network and supplying the code

      And as ECC2-109 in being run by the company that owns the process, the costs of running the severs that support the project are not factored into the prize distrobution.
    • Re:bah (Score:3, Insightful)

      by Grant29 (701796)
      I'll take it any day.. What's my loss? My computer's always on, so I guess I'm burning some electricity and lost CPU cycles. But it's probably cheaper than the lottery and I'm sure it's got about the same odds. At least you are donating something towards research. In the end, the contest host always wins, but it's a way for the USA to advance our tech research.

      --
      Retail Retreat [retailretreat.com]
    • Re:bah (Score:3, Informative)

      by AArmadillo (660847)
      Many of the problems worth lots of money from RSA are significantly harder than this one is. For example, it took distributed.net almost 5 years to solve RC5-64, worth $10000. The RSA factoring challenges worth lots of money are also extremeley difficult problems; the top one (2048 bits for $200,000) would probably take several thousand years even if every machine on the planet constantly worked on it and nothing else.
      • I don't have the figures here to do the sums, but off the top of my head I'd say that's an underestimate for the difficulty of breaking 2048-bit RSA using current algorithms.
  • by api_syurga (443557) on Thursday April 15, 2004 @11:03PM (#8877726)
    1) Put the decryptors in a remote island
    2) Make them wear skimpy clothing
    3) get them to compete in small subgames, such as
    blow the fish up etc..
    4) Get an affable good looking host to..err host..
    5) Get cameman to zoom in on their mental games an
    anguish as they try their best to out-decrypt the
    other contestants.

    voila..$1Million Cash Prize
    • by syousef (465911) on Thursday April 15, 2004 @11:12PM (#8877786) Journal
      Nahhhh.

      Have you watched any reality TV? It may be reality but its reality for stupid people.

      Anything intellectual means immediate ellimination. Dumb as a brick eye-candy stays and rates highly. Hypocrisy, backstabbing, lack of general knowledge and an overinflated ego equate to bonus points.

      Pretty + dumb + egotistical + hypocrit + backstabbing = "reality"
      • by nadda (613664) on Thursday April 15, 2004 @11:25PM (#8877890)
        Anything intellectual means immediate ellimination. Dumb as a brick eye-candy stays and rates highly. Hypocrisy, backstabbing, lack of general knowledge and an overinflated ego equate to bonus points.

        I think my work place must be a reality show.
        • Anything intellectual means immediate ellimination. Dumb as a brick eye-candy stays and rates highly. Hypocrisy, backstabbing, lack of general knowledge and an overinflated ego equate to bonus points.

          I think my work place must be a reality show.

          You were joking (well, modded funny at least), but my university Swedish teacher said that the reality shows (well, he was talking about the Swedish Expedition Robinson) are interesting because they depict how society in general works: the very best and very wo

      • + screened and groomed "contestants" + directing + makeup + content controlled + advertisements + etc.

        Reality for not just stupid people. Reality for vapid, stupid people.

        I'm pretty sure, I mean, at least I think, the last time I was in reality there wasn't a director there telling me "yeah, that's good, do that." Nor a makeup artist touching me up for the "personal" aside.
      • Former Boss? Is that you?
      • Pretty + dumb + egotistical + hypocrit + backstabbing = "reality"

        Oh, yeah, that's *totally* different from everyday reality. Oh, wait .. no it's not. doh!

        So I guess the reality shows *are* realistic after all..

    • by Anonymous Coward

      - Donald Trump per episode (first season) 'The Apprentice' $50,000.00
      - Donald Trump per episode (next season) 'The Apprentice' $215,000.00
      - Britney Spears reality show per episode $1,000,000.00
      - Exercises in F2m elliptic curve discrete log computation intended to probe the limits of a particular cryptography system $2,500

      Need we say more?
  • by Anonymous Coward on Thursday April 15, 2004 @11:09PM (#8877761)
    The contest website [certicom.com] doesn't mention a $1M prize, but from the "details" pdf [certicom.com], 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
  • Why the challenge? (Score:2, Insightful)

    by kentsin (225902)
    Just one crack is enough? Or shall we wait for better crack? To find if the method have weakness, we should open for more easy crack forever.

    The current scheme does not encourage a better crack. Or expose the method for fully tested.

    It will be very dangerous if the I.T. security is based on such a weak test system. Especially when many policy maker buy these security protection without aware of full picture.

    In the real world, people grant trust based on the information they got from the media, the more m
    • Insightful?

      > Just one crack is enough? Or shall we wait for better crack? To find if the
      > method have weakness, we should open for more easy crack forever.
      > The current scheme does not encourage a better crack. Or expose the method for
      > fully tested.

      The system wasn't `cracked` - we've not learned anything which will let us crack similar systems in a few seconds - it was `brute forced`. There's not weakness, any more than using every computer on the internet to brute force a PGP encrypted file
    • Just one crack is enough? Or shall we wait for better crack? To find if the method have weakness, we should open for more easy crack forever.
      The current scheme does not encourage a better crack. Or expose the method for fully tested.


      Huh? How is this insightful?

      I'm not sure what you mean by "a better crack". What they did was solve a single instance of a mathematical problem. They didn't "crack" anything in the traditional sense of the word.

      It sounds like you're complaining that solving a single in
    • Insightful?!?!

      That shit post was about as Insightful as a Fox news commentary on perpetual motion machines.

      Bah! I suppose I shouldn't really be surprised though.
  • by Gizzmonic (412910) on Thursday April 15, 2004 @11:11PM (#8877782) Homepage Journal
    What about the ED-209 winners? Remember, that robot from Robocop?

    No, not that one, that was Robocop. The other one. He was all robot. He didn't have Robocop's human side. But he did have some cool machine guns.
    • What about the ED-209 winners?

      They did not comply...
  • Certicom announced on Tuesday that the winners, a team from Ars Technica and a member of TeamIMO, will both receive $2500 each for the matching distinguished pairs that has solved the elliptical curve encryption scheme."
    The grammar nazi says, "Tsktsk!"
    ...will each receive $2500 for matching distinguished pairs that have solved...
  • by haxeh (766837) on Thursday April 15, 2004 @11:22PM (#8877868)
    Now let's run the same test, but instead of attacking the algorithm, let's see how many hours it takes to social engineer the key :)
  • by Anonymous Coward
    "Annie says: don't forget to drink your Ovaltine."
  • by Anonymous Coward
    D035 @Ny0n3 G07z @ 53rI@L5 0r cR@CkZ f0r 7urb07@x!!!
    I'v3 G07 14 MiNu735 70 l0@D i7 uP @Nd g37 My 7@X3$ DoNe!
  • by dj245 (732906) on Thursday April 15, 2004 @11:46PM (#8877997) Homepage
    team from Ars Technica and a member of TeamIMO, will both receive $2500 each for the matching distinguished pairs that has solved the elliptical curve encryption scheme."

    I bet $2500 that the other half of each of the team's "matching distinguished pairs" will:

    1. Go shopping for shoes
    2. Go shopping for jewelry
    3. Go shopping gor shoes AND jewelry

    Unless they are single, there is no way this gets spent on hardware.

    • Unless they are single

      How many NON-single guys would put that much time into decrypting this thing?
      • 5 in the row and carry the 1....
        Oh, they don't do this by hand and its an excuse to keep the noisey computer on 24x7 incase you win the prise. Single guys don't need an excuse to keep the computer(s) on 24x7
  • Brute force (Score:5, Insightful)

    by Anonymous Coward on Thursday April 15, 2004 @11:59PM (#8878059)
    Is it just me, or is there no real point to these encryption challenges? Brute forcing one particular key doesn't help you attack the encryption algorithim in general, and we can already calculate about how long it will take to crack with current processors. Other than the prize money, there is no reason to participate (except maybe for bragging rights, but finding an algorithmic flaw would get you so much more). Perhaps the prize money and CPU time might be better spent searching for a cure for cancer? I know there's a distributed computing project out there that does just that (no link right now, I'm lazy), and this *is* a case where the computers are just as good at calculating numbers for cracking encryption as calculating numbers for saving lives.
    • It's just you. :-)

      But seriously, the challenges draw attention to the encryption algorithm being used. The company gets to point at it and say "See, it took ALL THAT power to break our encryption! We're really, really, secure!"

      Which probably means a lot more to many managers than "we calculate that breaking the encryption would be THIS hard."
    • It's a publicity stunt, mostly. Also, it does provide an objective check on our theoretical analysis of the difficulty of the attack, but mostly it's so the company can turn around and say "Our encryption takes 1200 years to crack!" or "Our encryption takes $5000000 to crack!"
    • by Sycraft-fu (314770) on Friday April 16, 2004 @01:50AM (#8878554)
      1) It gives you a real world baseline of what kind of current power it takes to break your keys. You can then make some educated projections about what kind of security these keys will offer in the future. Computing power has and continues to grow at a fairly predictable rate. Thus you can infer how long a specific level of key will take to crack at a given point in the future, assuming no new mathematical or processing systems. Which leads us to

      2) It encourages people to try novel types of attacks. Yes, there are those that are just doing a brute attempte and they are there fore reason #1. However there are those that will try to come up with new algorithms, new hardware, or a combination, to defeat your encryption and prove it weak. This is what it's all about. You don't prove encryption strong, you continually prove that it's not weak, lending creedence to the theory that it is strong.
    • As others say it provides a baseline. But it's also a means of promoting research related to cryptography. Some of the prizes cannot be won without a) a tremendous breakthrough in factoring algorithms, b) a tremendous breakthrough in computer hardware, c) a working quantum computer, or d) some combination of the above.
    • Perhaps the prize money and CPU time might be better spent searching for a cure for cancer? I know there's a distributed computing project out there that does just that (no link right now, I'm lazy), and this *is* a case where the computers are just as good at calculating numbers for cracking encryption as calculating numbers for saving lives.

      Thaat would be www.grid.org [grid.org]. You can download it from this page [grid.org]. It does several projects, including the cancer one. For me, it seems to switch between smallpox an
  • "... the gross CPU time used to solve the challenge was roughly equivalent to an Athlon XP 3200+ working nonstop for 1,200 years."

    - Would that theoretical uptime be 1,200 years running Linux?

    If this computer is running Windows, I think it needs to be put back on the Area 51 shelf next to the perpetual motion machines, hen's teeth and Tesla weapons.
  • by enosys (705759) on Friday April 16, 2004 @12:51AM (#8878285) Homepage
    Trying to crack encryption with brute force is so pointless. I don't think it actually accomplishes anything useful. The length of time and amount of resources that are needed can be understood theoretically, without any need for running the experiment. The real threat to an encryption scheme is from new much faster methods cracking methods and these sorts of contests don't seem to encourage that; it's mostly about brute forcing it.

    More importantly there are more useful distributed computing projects. Here is a pretty good index [aspenleaf.com]. For example there's Folding@Home [stanford.edu] which furthers our onderstanding of proteins, which are so important in so many life processes and diseases, and fightAIDS@home [scripps.edu] which has already found a promising new drug [aspenleaf.com]. Or how about SETI@home [berkeley.edu]? Trying to crack encryption by brute force seems like such a waste in comparison to these.

    Perhaps the encryption contests are so popular just because you can win money. It's like a lottery. Maybe the only thing that could be done would be to have a cash prize for significant findings in other projects, or if who did it can't be defined due to the nature of the algorithm, maybe even just an ordinary lottery?

  • ECC2-109 is the same encryption scheme I have on my luggage!
  • It would appear that the technical/geek community on /. has little to say to articles like this. However, to the silliest shit posted get's incredible feedback. Most of it moderated funny. I come here everyday and I'm not sure why.
  • by NonSequor (230139) on Friday April 16, 2004 @03:29AM (#8878851) Journal
    An elliptic curve is the set of solutions to a cubic equation in two variables on some field (a field is a set on which two operations which behave like multiplication and division are defined). The solutions form a cyclic group. A group is a set on which an operation is defined such that there is an identity element, every element has an inverse, and the associative property holds. In a cyclic group, if you "multiply" any element by itself enough times, you'll get the original element.

    What makes all of this junk more interesting to computer people is that if you use a field with finitely many elements, you end up with some tools that can be used for things like factoring and other problems in number theory.

    Elliptic curve cryptography is based around the discrete log problem. That is, you are given two elements of the group, a and b, you want to find what value of k makes a^k=b. This problem can be solved in polynomial time in some cyclic groups, but elliptic curve groups lack certain niceties that make solving the problem for them tough.

    It is believed that elliptic curve cryptography will allow one to use significantly smaller keys than those needed by RSA without a loss of security.
  • ...that has solved the elliptical curve encryption scheme.

    Ahem; that should be elliptic.

    just being pedantical.
  • by Wellmont (737226) on Friday April 16, 2004 @04:28AM (#8879009) Homepage
    These contests were not designed by the encryption companies to have brute force used on them...Thus you have higher level challenges with "realistic" prizes. Sadly there is no reverse engineering when most of these teams think up their strategem, or even basic engineering for that matter. The RSA and eliptical encryption schemes were not thought up for mearly "normal" encryption....OBVIOUSLY if you have the key you have the file, but the underlying code (once encrypted) is meant to resemble nothing noticable, nothing useful to its cracking. Thus you have these contests, battles to see if people have a scheme, not brute force power.

    Chances are they would want to find the one dude who thinks up a program that can hack that encryption to bits in 4 minutes instead of trying every password from here to "timbucktoo" on hundreds of computers at once just because you work the janatorial shift at the San Diego Super Computer Center.
  • by dbaigrie (219410) on Friday April 16, 2004 @08:27AM (#8879785)
    The companies providing these encryption breaking challenges do not wish for someone to come up with some super quick method of breaking their products encryption scheme. Instead what they want is proven statistics that it takes X amount of time to crack their encryption scheme at rediculously low key lengths. This is so they can go around quoting their 1200 years and simillar to crack and sell more of their encryption product.

    Please do not take this as me saying that these encryption systems are or are not any good - I am not a cryptographer. It is just that these competitions are obviously organised from a marketing perspective.
  • Congratulations to #$%D$%^ERT^&%^RFYU%^&TRYU%& 456RTY456%^&RU*& for this astounding decryption.

    Make the suckers decrypt the new message to find out who the winners where in the last competition.
  • Not that I'm paranoid or anything. Ok, ok, so I'm paranoid and the governments' out to get me, but I still gotta wonder how quickly it was cracked by the boys with the big iron [nsa.gov]. Even though private/personal computational horsepower has increased dramatically over the years, while govt funding has decreased, I still can't see a general purpose CPU or network of CPUs being able to compete with dedicated crypto hardware .... Am I wrong??
    Another interesting link here [thinkquest.org]
    Paper: "Architectural considerations for [berkeley.edu]

Please go away.

Working...