Code Book code setters reveal crypto cock-up
Single DES/triple DES switcheroo
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.
Sponsored: Benefits from the lessons learned in HPC