Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
×
Encryption Security

Crack the Code and Win a Million Bucks 276

JS_RIDDLER noted a Toronto Star article about a sort of contest to crack some encryption and win a million bucks. The article is a bit fluffy, but it getst the point across... we wasted all those RC5 keys ;)
This discussion has been archived. No new comments can be posted.

Crack the Code and Win a Million Bucks

Comments Filter:
  • 2 bad... (Score:5, Interesting)

    by internet-redstar ( 552612 ) * on Tuesday January 20, 2004 @09:52AM (#8031063) Homepage
    ... they should have left an option open for people finding holes in the ACTUAL implementation... Now only mathematicians stand a chance - go, go, go, you few good number theoretisists not employed by the NSA! =-= insert favorite conspiricy theory here =-=
    • Re:2 bad... (Score:5, Interesting)

      by TedCheshireAcad ( 311748 ) <ted@fUMLAUTc.rit.edu minus punct> on Tuesday January 20, 2004 @10:19AM (#8031342) Homepage
      Modern cryptographic algorithms are good enough - it's the protocols that need work. Security problems happen in the implementation, most of the time the algorithms are rock-solid. DES, being as old as it is, is still a pretty prominent work horse (at least in the form of 3DES). Phasing it out with Rijndael (AES) just takes alot of time and money.

      As for Elliptic Curve Cryptography as mentioned in this article - it's still in its infancy - at least compared to other ciphers. This is just a stupid publicity show. But I bet I can win that $1M with an investment of under $20.

      There is an old KGB proverb: "It is easier to break fingers than it is to break codes." So, using my $20 budget on a pipe cutter, fifty feet of rope, and an ice pick, I believe I can recover the key. ;)
    • " Now only mathematicians stand a chance - go, go, go, you few good number theoretisists not employed by the NSA! "

      We'll change that after they win.
    • It's quite easy to create a code that no one can crack. I've done it myself, and it was posted here at slashdot a couple of years ago. No one even came close to solving it. However, although very little math was used, it was practically unusable :-)

      Here's a cipher contest for mere mortals [jdueck.net]. It's been going on since mid-december. The prize is a tin of penguin mints and a boost to your self-respect. And anyone with a decent knowledge of basic cryptography should be able to crack it.
  • by pherris ( 314792 ) on Tuesday January 20, 2004 @09:54AM (#8031088) Homepage Journal
    it's really a one time pad. =)
    • If you run a brute-force search on it, you'll see that it is really part of a paper I wrote last year.
      I demand that they pay for the copyright violation.

      If you use another key, you'll see that it also includes SCO's source code.
  • by ObviousGuy ( 578567 ) <ObviousGuy@hotmail.com> on Tuesday January 20, 2004 @09:55AM (#8031098) Homepage Journal
    They are using keys that sound big 168 bits, 256 bits, etc. But those aren't really that big, only 21 bytes and 32 bytes respectively. These sentences are longer than those keys.

    Then I note that UNIX limits passwords to 8 bytes. A measly 64 bits.

    I don't think I can sleep well knowing that all that stands between my data and some hacker is such a small string.
    • by mbyte ( 65875 ) on Tuesday January 20, 2004 @09:58AM (#8031139) Homepage
      Most modern unix system can use 128bit MD5 or 160bit SHA1 hash algorithms (instead of the standard 56 bit unix-crypt) .. get a better unix and sleep well again :)
    • Then I note that UNIX limits passwords to 8 bytes. A measly 64 bits.

      Actually, neither any commercial Unix that I know of nor Linux limits your password length to 8 bytes. However, some Unix implementation currently only support 8-byte usernames.
    • They are using keys that sound big 168 bits, 256 bits, etc. But those aren't really that big, only 21 bytes and 32 bytes respectively. These sentences are longer than those keys.

      So?
      2^64 is a big number, about 18,000,000,000,000,000,000.

      Assume your computer can hash and test a billion passwords a second. It'll take you 584 years to test all combinations, a little less than three centuries on average.

      Even the worst users out there change their passwords more often than THAT.
      • Yes, 2^64 is a pretty large number. Your math depends on the fact that the password is padded to a 64-bit length before being hashed, though. What if it is padded to some other length, or indeed not padded at all? (This could for example be done using a stream cipher. Encrypt the password, followed by a known fixed-length string. The hash is the encrypted known string. I'm not saying such a scheme would be secure, though.)

        However, how many use the entire eight-bit character set in their completely random p
      • Or about 80 minutes [sdsc.edu] with the right hardware or several months with $10,000 in equipment.
    • If a black hatter can read your shadow file, you have bigger problems than protecting your 64-bit hashed password from them.
  • RSA vs ECC (Score:5, Informative)

    by noelp ( 524550 ) on Tuesday January 20, 2004 @09:55AM (#8031107)
    For those of you who are suprised at the number of bits needed to secure data using ECC compared to RSA, a good discussion can be found here

    http://www.cs.uct.ac.za/courses/CS400W/NIS/papers0 0/mlesaoan/paper.html [uct.ac.za]

    • Ack! Just when I thought that ECC meant Error Correction Code, along comes ECC, which means Elliptical Curve Cryptography.

      It seems that these two two acronyms, which are very different in meaning, are likely to show up in the context of computer-related discussions :

      • "The kernel does ECC"
      • "ECC is built into the chipset"
      • " ... including 28 bit ECC"
      • "The ECCs in East D.C. are pieces of the PCs"
  • by morcheeba ( 260908 ) * on Tuesday January 20, 2004 @09:56AM (#8031121) Journal
    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
    • Currently there is a project [ecc2.com] underway to crack ECC2-109. This is 'just' a $10.000 project though (half goes to the project leads and half to the two winners). There will be two winners because the trick is to find two related points which mathematicians can use to calculate the answer (Frankly, I don't even understand how exactly, see the forum [ecc2.com] for details).

      Anyway, there are different clients available if you want to participate. I would suggest this client [dcworld.nl] and this GUI [gilchrist.ca]. The project is moving to the end fa
    • 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 ;-)

      I'm guessing that's something I won't be seeing on the next season of the Sopranos.

      "Hey Tony - some geek here says he wants to talk to you. Somethin 'bout a code?"

      "What's he want?"
      "Says he's cracked the lip tic curve something er other

  • by bc90021 ( 43730 ) * <bc90021 AT bc90021 DOT net> on Tuesday January 20, 2004 @09:57AM (#8031125) Homepage
    ...is that it uses much smaller keys with the same level of encryption. This makes it useful for handhelds and phones, and network devices. If you've never heard of this before, chances are you're already using it, too, as this is prevalent already in many of the aforementioned devices.
  • Fallacy (Score:5, Informative)

    by savagedome ( 742194 ) on Tuesday January 20, 2004 @09:58AM (#8031143)
    From the guru Bruce Schneier, Fallacy of cracking contests [schneier.com]
    • Honeypot! (Score:3, Interesting)

      by redelm ( 54142 )
      There may be some acedemic credit, but isn't this most likely a honeypot or TLA recruiting/watchlist scheme?

      • Although Certicom does have some links to the NSA [certicom.com], they're a Canadian company and it's unlikely they're doing the NSA's recruiting. This is much more like the RSA challenges [rsasecurity.com].

      • if you want to compete anonymously, you can hire a lawyer to claim the prize for you. many people do this for the lottery.
        • you can hire a lawyer to claim the prize for you. many people do this for the lottery.

          Not around here, they don't. If you read the Terms and Conditions for the lottery, they state that if you win over a certain threshold (i.e., the jackpot), then in order to claim the prize, you have to consent to being photographed and having your name released. It is impossible to claim lottery winnings anonymously. It's actually the law. Think about it. If people could claim lottery winnings anonymously, how would
          • in ohio, the lottery ticket is a bearer ticket. whoever is holding the ticket can redeem it. so if you lose the ticket or it's stolen, you'll have a very hard time proving you should get the winnings.
    • Re:Fallacy (Score:5, Informative)

      by mistered ( 28404 ) on Tuesday January 20, 2004 @10:22AM (#8031367)
      Much more relevant is Schneier's Essay on Certicom and ECC [schneier.com]. Note though that this isn't your typical doghouse style "crack our code for $1 MEELEEON dollars" contest with fine print that says you have to do it in three days on a Commodore 64. It's a fair contest for a "real" algorithm. Anyone who completes any of the sub-contests is (a) not in it for the money and (b) unlikely to be a generic Slashdot hacker.

      By the way this is Schneier's recommendation on ECC:

      My recommendation is that if you're working in a constrained environment where longer keys just won't fit -- smart cards, some cellphones or pagers, etc. -- consider elliptic curves. If the choice is elliptic curves or no public-key algorithm at all, use elliptic curves. If you don't have performance constraints, use RSA. If you are concerned about security over the decades (almost no systems are), use RSA.

    • Not a Fallacy (Score:3, Interesting)

      by jmegq ( 33169 )
      Of course, if you *read* the counter-argument you link to, you see that Schneier thinks this sort of contest is fine:

      There are exceptions, but they are few and far between. The RSA challenges, both their factoring challenges and their symmetric brute-force challenges, are fair and good contests. These contests are successful not because the prize money is an incentive to factor numbers or build brute-force cracking machines, but because researchers are already interested in factoring and brute-force crac

  • Huh? (Score:3, Interesting)

    by madgeorge ( 632496 ) on Tuesday January 20, 2004 @09:59AM (#8031157)

    Agree or disagree, I usually at least understand Slashdot editorial comments. But I don't get "we wasted all those RC5 keys". You mean we cracked them when they could have been used? I hope not. You mean we cracked them without the promise of 1 meelion dollar bills? Ok, greedy, but I'm with you.

    Seriously, how do you waste a key?

    -madgeorge

  • Better than RSA? (Score:5, Interesting)

    by jrockway ( 229604 ) <jon-nospam@jrock.us> on Tuesday January 20, 2004 @10:04AM (#8031192) Homepage Journal
    I think the company who came up (or rather markets) ECC [eliptic curce cryptography] should be careful about saying that ECC is more secure than RSA. RSA has stood up to A LOT of cryptanalysis, simply because of it's age. ECC might have bad keys or something else we don't know about simply because we have not have time to try all attacks yet. Who knows, tomorrow someone may find a trivial algorithm for taking the discrete logarithm on an EC (rendering ECC useless). Then again, someone may find a way of doing a simple discrete logarithm (rendering RSA useless). Both are highly unlikely, but hey -- stranger things have happened.

    Basically, take a company's claim with a grain of salt. Right now I'll keep my data encrypted with something more tested (3DES anyone?).
    • Re:Better than RSA? (Score:3, Informative)

      by bluGill ( 862 )

      Go ahead, use 3DES for your encryption, PLEASE. I'd love to be a spy next time you do a key exchange, so many ways to find out what your key is, and then read your data without you knowing. Please trust your data to 3DES.

      For those who know nothing of encryption, 3DES and ECC solve different problems in practice. ECC is public key, meaning you can publicly give the key to everyone, and have no worrys that someone who copys your transmission will be able to understand what is said because there are actual

  • by CaptainAlbert ( 162776 ) on Tuesday January 20, 2004 @10:05AM (#8031197) Homepage
    The problem with ECC is that the "hard problem" on which its security relies is based on some non-trivial mathematics which, until recently, no-one's really been interested in. Contrast this with RSA, which is based on a comparatively easy-to-understand problem (factoring a product of two primes) which has been known about for centuries.

    What this means is, it's possible (very unlikely, but possible) that the conjecture that the elliptic curve logarithm problem is very hard to solve might be proved wrong tomorrow. That is much less of a risk with RSA (although see under quantum computing, if you go in for that sort of thing).

    Last time I checked, the best "brute force" algorithm to attack ECC was the Pollard rho method. Is that still true?
    • based on some non-trivial mathematics which, until recently, no-one's really been interested in.

      By recently I take it you mean within the last century or so. Elliptic curves are pretty much a staple now in number theory and modern algebra.

      the conjecture that the elliptic curve logarithm problem is very hard to solve might be proved wrong tomorrow.

      And large integer factoring (RSA) and the discrete logarithm problem (DSA) are both believed to be hard, but both could be proved/demostrated to not be as h
    • Quantum computing kills both equally, the same algorithms that get RSA and discrete log can get the elliptic curve discrete log.
  • by drfishy ( 634081 ) on Tuesday January 20, 2004 @10:05AM (#8031198)
    One million dollars split between 500,000 people is what??? TWO DOLLARS!!! Well, at least we'll be able to pay that annoying paper boy...
  • What about the DMCA? (Score:3, Interesting)

    by Martigan80 ( 305400 ) on Tuesday January 20, 2004 @10:07AM (#8031220) Journal
    and we'd most certainly be happy to consider them for a lifetime position

    What position are the lawyers thinking about after the break the encryption? ;-)
  • Yawn (Score:5, Insightful)

    by fruey ( 563914 ) on Tuesday January 20, 2004 @10:16AM (#8031304) Homepage Journal

    This company is saying their encryption can't reasonably be brute forced with current computing, even if you got pretty much everyone on the internet (more than are currently running SETI) to start brute forcing the keys. It's harder than RSA encryption mathematics theory, on a key which is like 163 bits for the $20,000 prize, and to get a million you'd have to break the scheme for any bit length I imagine, not just the 224 bit key they mention earlier in the article.

    So, unless there is a quantum leap (how ironic that quantum computing would indeed be a quantum leap) this is not some kind of Distributed project. RC5 was fairly simple bruteforcing at the end of the day.

    The summary of the article is like so dumb I cannot believe it passes muster. And the million bucks are as likely to be awarded as a release of Duke Nukem Forever and Ever Amen. Nothing to see here, move along.

    • So, unless there is a quantum leap (how ironic that quantum computing would indeed be a quantum leap) this is not some kind of Distributed project.
      Of course, a quantum leap is a very small leap.
      • But how quickly and in what direction?
      • Of course, a quantum leap is a very small leap.

        The reason for the saying is that it is a leap, with no intermediate stage. There is a before, and an after. Compared to say an object going from warm to cold - there's always intermediate stages, no matter how quickly the object is cooled.

        That's why quantum computing is a quantum leap - because there's no intermediate stages between that and electronic coputing. There's a before, and an after.

        Kjella
    • start brute forcing the keys.

      Ah, you don't bother to bruce force the public key to recovery the private key. You use factoring.
  • by Anonymous Coward on Tuesday January 20, 2004 @10:16AM (#8031305)
    It's a trick.

    Mathwiz: "Hello? I think I may have cracked your encryption".
    NSA: "Great. Just stay where you are and we'll over with you money in a second".

    [40 seconds later]

    Police: "Drop your weapon and step out side!"
    Mathwiz: "But I'm unarmed!! Dude!"
    Police: "I said DROP YOUR WEAPON".
    [BLAM!]
  • Time for some coding (Score:3, Interesting)

    by adrianbaugh ( 696007 ) on Tuesday January 20, 2004 @10:18AM (#8031327) Homepage Journal
    Anyone (outside patent encumbered countries) working on a Free implementation? It should be okay in the EU, for "allowing interoperability with existing products".
    • Free implementation?

      See OpenSSL [openssl.org] and Sun's announcement [sun.com] for including ECC code in OpenSSL.
      • Which isn't "free". Sun included some rather un-nice licensing things in their ECC when they gave it to OpenSSL. I believe the issue was that it forbids sueing Sun for anything but I'm not sure. There was a rather large thread on the OpenBSD mailing list about it.

        Last I heard, OpenBSD was going to fork OpenSSL off and maintain their own version as these restrictions no longer allowed them to include OpenSSL that fit their charter.

        Perhaps someone that knows more about this could comment?
  • by WegianWarrior ( 649800 ) on Tuesday January 20, 2004 @10:19AM (#8031345) Journal

    ...to crack it, but as of how long it will take them. Information that is worth a lot today may be worthless tomorrow, and by next week it'll be history. So the question isn't about making a perfect encoding (we allready have one, namely 'one time pads'), but finding the best encoding for the application. Also bear in mind the rule of thumb that states that the thoughter the code, the more difficult (think CPU-cycles and batterydrain) it is to encode it in the first place. Off course, just how strong thats strong enought will change as the tools for encryption, decryption and codebreeaking gets stronger.


    Remember folks, an encrypted message don't have to be unbreakable, it just has to be hard enought to break. One rule of thumb is that it should cost more to break than the one breaking it will earn on doing so.


    Besides, one can learn a lot about whats going on even if you can break the code. Where does the signal originates? Where is it heading. Does it occour on a frequent basis? What is the matter of transmitting? The more you learn about the message, the more you learn about the reason it's beeing sendt - even if you don't know what it says. THEN you can often start using social enginering to gain access to the key, or better yet, to the unencrypted message.

  • Book (Score:3, Informative)

    by savagedome ( 742194 ) on Tuesday January 20, 2004 @10:22AM (#8031369)
    If any of you is seriously considering going at this, I recommend the well known Applied Cryptography [schneier.com]

    Slashdot has reviewed [slashdot.org] this before.
  • XM Radio (Score:5, Interesting)

    by Silicon Mike ( 611992 ) on Tuesday January 20, 2004 @10:34AM (#8031486)
    I went over to their website and parused around... Seems they did the security to XM Radio, http://www.certicom.com/download/aid-78/success_XM Radio.pdf) which humors me because XM Radio was hacked about 2 months after it went live.. All you need is a part from an old Dish Network reciever and a soldier iron.
    • Irrelevant, any sort of DRM system (including things like XM radio and satallite TV) are inherently flawed. While they happen use encryption, they don't have any actual cryptographic security. They are actually based on GIVING people the keys while trying to keep them from LOOKING at the key have. You never need to try to crack the encryption, you just need to dig around inside looking for the key you already have.

      They may make it a pain in the butt to find the key, but it is an inherently "easy" problem,
  • This isn't news (Score:4, Informative)

    by krysith ( 648105 ) on Tuesday January 20, 2004 @11:12AM (#8031909) Journal
    In the grand tradition of "It came over the wire service", Slashdot posts an article about a contest that has been going on since 1997. IIRC, I bookmarked http://www.certicom.com/research/ch2.html last january (I'm not sure because I have changed computers since then). Its been long enough that Certicom has changed their website too.

    ECC is interesting, although I am not 100% sure that it is as relatively strong as Certicom claims. Elliptic curves are similar to the discrete log method, which can be shown to be approximately as strong as RSA (factoring). I am not an expert in Elliptic curves, so I can't speak as to whether there are any 'shortcuts' which would reduce the problem to a discrete log one, but if so, then the ECC would be no stronger than RSA. Elliptic curves, by the way, are the same branch of mathematics which brought us the proof of Fermat's last theorem.

  • hmm (Score:2, Funny)

    by ajs318 ( 655362 )
    As has been pointed out, demonstrably crackable encryption is OK for data with an expiry date. Credit card numbers, for instance, are usually only good for 3 years or so -- you get a new number with the new card.

    Still, I worry about any closed-source encryption technology. Imagine somebody coming up to you and saying in a cheesy mexican accent: "Hey, extranjero! You want to send top-secret message? No problemo, Amigo! I know secret code, so secret only me and my brother know it. You give me message
  • If you can just wait a few more months, Best Will Hunting: Good Will Hunting II will be out and superstar Matt Damon will be writing the answer up on the MIT blackboards all across campus.

    So get ready to hit the pause button, and have pencil and paper ready.

  • Now imagine if they put out bounties for distributed projects that found cures for cancer, aids, the common cold, alzheimers, m.s., and thousands of other diseases. Philanthropy can only take you so far; use the "greedy" free market to drive progess even further!
  • by CognitiveFusion ( 602570 ) on Tuesday January 20, 2004 @11:49AM (#8032319) Homepage
    I wouldn't waste a CPU cycle on this contest.

    Bruce Schneier nailed the truth about cracking contests in a December 1998 article in his crypto-gram newsletter, "The Fallacy of Cracking Contests [schneier.com]".

    Here is another article he published in November 1999, "Elliptic Curve Public-Key Cryptography [schneier.com]".

    Interesting reading.
  • But I won't take credit. For a measley hundred grand I'll tell how I did it :)

  • ... but the monetary rewards of reading all that cracked traffic is worth way more than $1 million. Just last month I extorted $250,000 from a rich exec who didn't want his wife to find out about Mistresses 1 and 2. Also sold some high-tech secrets to an oil-rich third world country for a good bit of cash (I assume they'll use it to keep development of alternative-fuel vehicles from progressing very quickly, but what do I care as long as I get my money?)

    You keep right on developing that uncrackable ECC st

  • RSA is free of patents!
  • It's shameful how much they brag about their patent portfolio. The RSA and Diffie-Hellman patents presented a very real impediment to the uptake of public key cryptography until very recently, when the patents finally started expiring.

    And why don't we have digital cash? Well, social problems primarily, but it doesn't help that David Chaum and Stefan Brands, after developing *phenomenally* cool techniques for preserving privacy in electronic cash, carpeted the whole area with patents.

    So, thanks for setti
  • by Thuktun ( 221615 ) on Tuesday January 20, 2004 @04:47PM (#8035617) Journal
    Quoth the article:
    The standard encryption level for online banking or purchases these days uses something called a secure socket layer, or SSL, which typically provides privacy between computer connections at 128 bits, an acceptable level. [...]

    A much smaller 224-bit ECC key offers the same level of encryption as 2048-bit key in the competing RSA format. In other words, a company would need 16 times stronger encryption to get the same level of protection that Certicom offers in the ECC format.
    This is comparing an apple and an orange and concluding something about a strawberry.

    When it comes to encryption keys, it's not the size, it's how you use it.
  • IT'S CANADIAN!

    That's like, what, US$25?

    Go to goodwill and pick up a bunch of monopoly sets for that price and save yourself the trouble!
  • I am sorry to be against this topic but I do seriously urge any person competent not to participate in such a bullshit test. Asking people to "crack" something while offering cash doesn't mean it's secure (which is what is implied, which is insanely stupid for people that work in security and professionnals involved in cryptography). It just proves that no one that cared to break it came over it to break it. Serious cryptographers ask people to present their work in a formalized scientific form. We have a H

"Protozoa are small, and bacteria are small, but viruses are smaller than the both put together."

Working...