Feeds

Maths boffins topple Certicom crypto

Not a small task

  • alert
  • submit to reddit

Providing a secure and efficient Helpdesk

What do you get if you cross 109-bit elliptical curve cryptography with a very determined mathematician? If you have 2600 computers and 17 months and few more maths wizards to throw into the mix, you get a cracked key.

Chris Monico, an assistant professor at Texas Tech university, and his team have solved the Certicom Elliptic Curve Cryptography (ECC)2-109 Challenge. There are three reasons that this is good news: firstly, the algorithm is still sound, as Monico explains below. Secondly the CPU power it took to break the key is equivalent to an Athlon XP 3200+ working nonstop for about 1200 years. Lastly, commercial grade crypto uses 163-bit keys. To solve one of those is around one hundred million times harder.

Monico told El Reg: "We used a collision-based version of the well-known Pollard-rho algorithm. While this is much better than brute-force, which would have required about 4.5 quadrillion times as much work, it is still exponential - every two bits added to the keysize make the attack take twice as long."

The same team also solved the ECCp-109 challenge in 2002. In this contest, the key was the same length, but was solved over a field of characteristic 2 rather than a prime field. As well as the professional acknowledgement, Monico and his team win $10,000 for cracking the key.

But money is not the prime motivator. "I think public-key cryptography based on ECC is what we should and will be moving toward," Monico argued. "And besides, the fact that this is likely the last of the ECC challenges to be solved in the next few years was a big motivator. The only way to get at the 130-bit level challenges are by a combination of Moore's Law (wait around for computers to get faster) and gathering more computers. Personally, I think it's unlikely to happen soon."

The Certicom challenge was first issued in 1997, and has three levels, starting with some more basic crypto exersizes. This solution, impressive as it is, is just the first part of Level I. Level I also includes 131-bit challenges; and Level II involves 163-bit, 191-bit and 359-bit challenges. The 131-bit challenges are 2000 times more difficult than the 109 bit challenges, and the level II challenges are considered computationally unfeasible. Bring on the quantum processors... ®

Related stories

109-bit Elliptic Curve Cryptography knocked over with brute force
IT security to become political battleground
Cable modem hackers conquer the co-ax
Crypto booster tech for mobile phones

New hybrid storage solutions

More from The Register

next story
Apple Pay is a tidy payday for Apple with 0.15% cut, sources say
Cupertino slurps 15 cents from every $100 purchase
Google recommends pronounceable passwords
Super Chrome goes into battle with Mr Mxyzptlk
Reddit wipes clean leaked celeb nudie pics, tells users to zip it
Now we've had all THAT TRAFFIC, we 'deplore' this theft
YouTube, Amazon and Yahoo! caught in malvertising mess
Cisco says 'Kyle and Stan' attack is spreading through compromised ad networks
TorrentLocker unpicked: Crypto coding shocker defeats extortionists
Lousy XOR opens door into which victims can shove a foot
Greater dev access to iOS 8 will put us AT RISK from HACKERS
Knocking holes in Apple's walled garden could backfire, says securo-chap
Microsoft to patch ASP.NET mess even if you don't
We know what's good for you, because we made the mess says Redmond
NORKS ban Wi-Fi and satellite internet at embassies
Crackdown on tardy diplomatic sysadmins providing accidental unfiltered internet access
prev story

Whitepapers

Providing a secure and efficient Helpdesk
A single remote control platform for user support is be key to providing an efficient helpdesk. Retain full control over the way in which screen and keystroke data is transmitted.
Top 5 reasons to deploy VMware with Tegile
Data demand and the rise of virtualization is challenging IT teams to deliver storage performance, scalability and capacity that can keep up, while maximizing efficiency.
Reg Reader Research: SaaS based Email and Office Productivity Tools
Read this Reg reader report which provides advice and guidance for SMBs towards the use of SaaS based email and Office productivity tools.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.
Secure remote control for conventional and virtual desktops
Balancing user privacy and privileged access, in accordance with compliance frameworks and legislation. Evaluating any potential remote control choice.