Feeds

Code Book code setters reveal crypto cock-up

Single DES/triple DES switcheroo

  • alert
  • submit to reddit

Protecting against web application threats using SSL

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

The next step in data security

More from The Register

next story
New 'Cosmos' browser surfs the net by TXT alone
No data plan? No WiFi? No worries ... except sluggish download speed
'Windows 9' LEAK: Microsoft's playing catchup with Linux
Multiple desktops and live tiles in restored Start button star in new vids
iOS 8 release: WebGL now runs everywhere. Hurrah for 3D graphics!
HTML 5's pretty neat ... when your browser supports it
Mathematica hits the Web
Wolfram embraces the cloud, promies private cloud cut of its number-cruncher
Google extends app refund window to two hours
You now have 120 minutes to finish that game instead of 15
Intel: Hey, enterprises, drop everything and DO HADOOP
Big Data analytics projected to run on more servers than any other app
Mozilla shutters Labs, tells nobody it's been dead for five months
Staffer's blog reveals all as projects languish on GitHub
SUSE Linux owner Attachmate gobbled by Micro Focus for $2.3bn
Merger will lead to mainframe and COBOL powerhouse
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.
WIN a very cool portable ZX Spectrum
Win a one-off portable Spectrum built by legendary hardware hacker Ben Heck
Saudi Petroleum chooses Tegile storage solution
A storage solution that addresses company growth and performance for business-critical applications of caseware archive and search along with other key operational systems.
Protecting users from Firesheep and other Sidejacking attacks with SSL
Discussing the vulnerabilities inherent in Wi-Fi networks, and how using TLS/SSL for your entire site will assure security.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.