Certicom offers crypto contest

Taking a cue from a competitor, Canadian encryption vendor Certicom has issued a challenge to cryptographers, mathematicians, and hackers to try to break its elliptic curve cryptography (ECC) algorithms.

Certicom is offering prizes of up to $100,000 for the first person to break its keys, including some it believes can be broken.

The challenge is similar to contests run by Certicom rival RSA Data Security to illustrate that weak encryption algorithms--the only kind approved for export by the U.S. government--can be cracked.

Certicom aims to publicize its encryption as an alternative to RSA's, since elliptic curve cryptography is frequently challenged as being "untested" compared to RSA's algorithms, which have been well-known for years.

"We're trying to make sure that people have the chance to slug away at our system if they want and to put some money behind it," said Certicom chief executive Philip Deck, who unveiled the contest last week before a mathematics conference at the University of Waterloo.

"We don't think the hackers are going to make too many advances on this," Deck said. "The audience we launched it to are people who really understand the deep mathematics behind the curve."

Elliptic curve cryptography is regarded as more efficient than RSA algorithms for small devices without a lot of computing power--smart cards, cellular phones, and TV set-top boxes, for example.

Certicom is trying to persuade Visa and MasterCard to add elliptic curve algorithms to their protocol for secure card transactions over the Net, known as Secure Electronic Transactions (SET).

The easier exercises, designed to get mathematicians comfortable with the elliptic curve algebra, involve breaking key lengths of 79, 89, and 97 bits. Certicom believes its 79-bit exercise can be solved in hours, the 89-bit in days, so the first person to do so gets a crypto handbook and software.

The company figures the 97-bit key can be broken in a matter of weeks--using a network of thousands of computers. The first person to break a 97-bit key gets $5,000.

But the real challenge begins in breaking keys of 109 and 131 bits--Certicom estimates the 109-bit key can be broken in several months with a network of 100,000 computers. Prizes are $10,000 for three separate 109-bit keys and $20,000 for 131-bit keys.

To back up its claim that breaking keys of 163, 191, 239, and 359 bits is "computationally infeasible," Certicom is offering cash prizes from $30,000 for breaking a 163-bit key to $100,000 for the 359-bit key. Certicom said 163-bit elliptic curve keys are the recommended minimum key size, claiming it is as secure as RSA algorithms of 1,024 bits.

"I don't think anybody is going to work on the 163-bit challenge," said Deck. "For anyone who really knows the area, it's too large a problem, so it's silly to start. It's a bit of a fruitless task."