Feeds

Code Book code setters reveal crypto cock-up

Single DES/triple DES switcheroo

  • alert
  • submit to reddit

Beginner's guide to SSL certificates

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

Remote control for virtualized desktops

More from The Register

next story
Nexus 7 fandroids tell of salty taste after sucking on Google's Lollipop
Web giant looking into why version 5.0 of Android is crippling older slabs
Be real, Apple: In-app goodie grab games AREN'T FREE – EU
Cupertino stands down after Euro legal threats
Download alert: Nearly ALL top 100 Android, iOS paid apps hacked
Attack of the Clones? Yeah, but much, much scarier – report
SLURP! Flick your TONGUE around our LOLLIPOP – Google
Android 5 is coming – IF you're lucky enough to have the right gadget
Microsoft: Your Linux Docker containers are now OURS to command
New tool lets admins wrangle Linux apps from Windows
Bada-Bing! Mozilla flips Firefox to YAHOO! for search
Microsoft system will be the default for browser in US until 2020
prev story

Whitepapers

Choosing cloud Backup services
Demystify how you can address your data protection needs in your small- to medium-sized business and select the best online backup service to meet your needs.
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.
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.
The hidden costs of self-signed SSL certificates
Exploring the true TCO for self-signed SSL certificates, including a side-by-side comparison of a self-signed architecture versus working with a third-party SSL vendor.
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.