Feeds

Code Book code setters reveal crypto cock-up

Single DES/triple DES switcheroo

  • alert
  • submit to reddit

Providing a secure and efficient Helpdesk

Interview Following the news that the final cipher of Simon Singh's Code Book challenge had been broken, The Register caught up with him and Paul Leyland, who between them set the ten ciphers in the challenge.

A team of researchers in Sweden cracked all the ciphers and claimed the £10,000 prize. It took a year and month between publication of the challenge and its completion without the use of a super computer.

Singh set a challenge to would be cryptologists at the end of his book, which catalogues the history and development of ciphers and codes from a mono-alphabetic substitution cipher through to current Internet encryption standards. It was intended to be the toughest public cipher challenge ever set.

"I really didn't have the foggiest idea how long it would take to be solved, but I think a year is a good time. If it had gone on for longer, say five years or so, it would have become frustrating and lost its pace. It is very hard to set a cipher that isn't either trivial or impossible," said Singh, thoughts echoed by his colleague in this endeavour, Paul Leyland.

"Designing a good cipher isn't easy," he said. "Designing a bad one, however, is easy. In general terms, first off you have to decide what you are protecting. Is it information of low value, or high? Is it short-lived or must it be protected for many years?"

Equally important are the resources of the enemy you are trying to evade, and your own resources to encrypt the data in the first place.

Leyland continues: "In more familiar terms, do you want a simple bolt on a bathroom door to advise others that the room is occupied, or do you need a vault with three-foot thick steel walls to keep out professional thieves armed with explosives and cutting torches, or something in between? All these factors are important and must be properly considered before designing or choosing a cipher."

As for the timing, the cracking of the cipher coincided with the start of Singh's TV serialisation of "The Code Book." Pure coincidence? Well, it seems so. Rather wistfully Singh says: "Last week would have been nice, it would have saved me a thousand pounds."*

Because the ciphers in the challenge had been following a historical theme, the final stage had to be a realistic application of public key cryptography.

Again, we defer to Leyland for an explanation: "The archetypal public key algorithm is RSA, and one of its major uses in real life is to encrypt a cipher key. The key would then be used to encrypt a message with a cipher far too hard to break by key search as for the DES stage. We chose triple-DES for the cipher, and encrypted its 112-bit key with a RSA public key, which was 512-bits in size."

And in the way of all things code related, the final cipher turned out to have another final trick up its sleeve.

"The last text was supposed to be triple DES encrypted," said Singh. "This is impossible to crack, but we had encrypted the key to the passage with a 512-bit asymmetric cipher, and this was the way to solve the final stage."

However, by accident, the passage ended up being only single DES encrypted. Since the previous text, once deciphered, hinted strongly that the next passage was encrypted using triple DES, the Swedes used the key to un-triple DES the passage. Obviously after this it made no sense at all.

"It took them a couple of hours to work out what was going on," Singh remarks. "I'm not embarrassed by it, its just part of cryptography that things are not always perfect. I'm sure there were spelling mistakes running through all the other texts as well."

As for the implications of such a strong cipher being broken without the use of a super computer, this is the part that really impressed Leyland and Singh.

However, according to David Shapland, enterprise product manager at BT Trustwise, the UK face of Verisign, said that we should be neither concerned nor surprised that a 512 bit key has been broken.

"Most things are secured using a 1024-bit key these days," he said. "And if you bear in mind that starting from a 512 bit key, each additional bit doubles the number of available keys that is pretty secure against a brute force attack."

He went on to explain that if one could test all the possibilities of a 40-bit symmetric key in a microsecond, it would take longer that the lifetime of the universe to test every possible combination.

The puzzle was finally solved by Fredrik Almgren, Gunnar Andersson, Torbjörn Granlund, Lars Ivansson and Staffan Ulfberg from Stockholm, on 7 October 2000. ®

*When the challenge was set, Singh promised £1000 to the person who was leading the race at the one year mark. The final cipher was cracked just a week after this milestone had been passed.

Related Stories

Swedes mash 512-bit Code Book crypto challenge to get £10,000

Secure remote control for conventional and virtual desktops

More from The Register

next story
Microsoft WINDOWS 10: Seven ATE Nine. Or Eight did really
Windows NEIN skipped, tech preview due out on Wednesday
Business is back, baby! Hasta la VISTA, Win 8... Oh, yeah, Windows 9
Forget touchscreen millennials, Microsoft goes for mouse crowd
Apple: SO sorry for the iOS 8.0.1 UPDATE BUNGLE HORROR
Apple kills 'upgrade'. Hey, Microsoft. You sure you want to be like these guys?
ARM gives Internet of Things a piece of its mind – the Cortex-M7
32-bit core packs some DSP for VIP IoT CPU LOL
Microsoft on the Threshold of a new name for Windows next week
Rebranded OS reportedly set to be flung open by Redmond
Lotus Notes inventor Ozzie invents app to talk to people on your phone
Imagine that. Startup floats with voice collab app for Win iPhone
'Google is NOT the gatekeeper to the web, as some claim'
Plus: 'Pretty sure iOS 8.0.2 will just turn the iPhone into a fax machine'
prev story

Whitepapers

Forging a new future with identity relationship management
Learn about ForgeRock's next generation IRM platform and how it is designed to empower CEOS's and enterprises to engage with consumers.
Storage capacity and performance optimization at Mizuno USA
Mizuno USA turn to Tegile storage technology to solve both their SAN and backup issues.
The next step in data security
With recent increased privacy concerns and computers becoming more powerful, the chance of hackers being able to crack smaller-sized RSA keys increases.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.
A strategic approach to identity relationship management
ForgeRock commissioned Forrester to evaluate companies’ IAM practices and requirements when it comes to customer-facing scenarios versus employee-facing ones.