Cipher Challenge Cracked

The Story Behind the Cipher Challenge - the toughest code ever cracked!

It took one year and one month to be completed, but at last the Cipher Challenge has been cracked. Congratulations to the five Swedes who successfully tackled the toughest encryption challenge so far, and who have claimed the £10,000 prize.

This page will reveal the story behind the Cipher Challenge. If you want to continue trying to crack the Challenge, then please do not read any further.

As soon as I started to write The Code Book, it seemed natural to me that a book about the history of codes and codebreaking should contain some coded messages to stretch the mind of the reader. I decided to include ten messages encrypted in ten different ways, the ten stages getting progressively harder. I hoped that all the readers would at least attempt to crack a few of the earlier stages and experience the thrill of unraveling a secret message. I also hoped that some readers would get hooked and learn some of the more sophisticated techniques required to crack stages 6, 7 and 8. And, of course, I wanted a few dedicated readers and crypto-fanatics to have a go at completing the entire Challenge.

The main aim of the Cipher Challenge was to set puzzles and get people interested in cracking codes. The Cipher Challenge seems to have achieved this, as tens of thousands of people have become involved in cracking my coded messages. I am convinced that these people are driven by curiosity and the thrill of the chase. The prize of £10,000 is merely there to add a little extra spice.

I constructed the Cipher Challenge while I was writing The Code Book, so in total it took two years to prepare. The Challenge was compiled in complete secrecy, with great care being taken than no material relating to it ever fell into the wrong hands. Whenever I had gone through a process of jotting, encrypting, checking and deciphering a particular stage, I took the precaution of burning any resulting paper. I regularly went into my little garden, dipped the papers in molten wax and set them alight.

Compiling each stage was an absorbing process. For example, when I created the Enigma stage, I used a computer emulation. To double check it, I designed a paper Enigma cipher machine, which involved half a dozen strips of paper. Sliding the strips mimicked the action of the machine's rotors.

The Cipher Challenge incorporated the following principles:

a) 10 stages of increasing difficulty so that everybody can take part in at least a few of the stages.

b) A chronological series of cipher techniques: classic substitution, Caesar cipher, homophonic substitution, Vigenère cipher, book cipher, Playfair cipher, ADFGVX cipher, Enigma cipher, and two computer ciphers known as DES and RSA.

c) A variety of languages, 6 in total, were used, each language being appropriate to the cipher. For example, in stage 2 a Latin message was encrypted with the Caesar cipher, and in stage 4 a French message was encrypted with the Vigenère cipher. This made it tougher for codebreakers, but it made it more fun and a fairer challenge for everybody around the world. Remember, this was a worldwide competition.

d) It seemed that the early stages were accessible to everybody, but the latter stages would require a certain level of technical skill. I wondered if the winner might be a team made up of an amateur who had cracked the ancient ciphers and a computer expert who had cracked the latter two ciphers. In particular, I suspected that the one year prize might be won by amateurs and that the complete prize might be won by professionals. This is more or less what happened.

f) Stage 10 was intended to be the toughest public challenge cipher yet devised. Hence, I hoped that its cracking would help test the level of current codebreaking and perhaps stretch and encourage the development of algorithms.

In order to check the details of stages 9 and 10 of the Cipher Challenge, I confided in Paul Leyland, an encryption expert working for Microsoft in Cambridge. He acted as a trusted consultant, and he was the only person in the world who was aware of the solutions to these stages of the Cipher Challenge. In 1993-4, Paul led a global collaboration of 600 people to factor the RSA-129 challenge number, an effort which was probably the largest single computation performed to that date. This made him an ideal person to help me construct a fair and formidable stage 10. (Paul, thanks for all your help! You were a great source of support.)

The Cipher Challenge began in September 1999, with the publication of The Code Book. This was a worldwide competition; The Code Book was published in Britain and America, and it was also translated into Finnish, French, German, Dutch, Norwegian, Spanish and Swedish.

Very quickly, web groups became established, the largest of which was at e-Groups. It consisted of over 2,500 members who emailed each other offering, support, advice and encouragement. I occasionally lurked on this group and was always entertained, informed and impressed by their exchanges. It was particularly entertaining to read the various theories concerning the infamous stage 5.

Another reflection of the widespread interest was shown at a cryptography seminar in Oxford, where Cipher Challengers from Britain, America, Sweden, Switzerland and Norway arranged to meet up. Whenever I gave talks, both in Britain and abroad, I would meet Cipher Challengers from all walks of life and of all ages - from novices and schoolchildren to mathematicians and professional cryptographers. There was even a Fields Medallist who became involved.

The progress of the Cipher Challenge is charted on the leaderboard on this site and is briefly documented in the updates, so I will not go through this again. However, I will say that I was initially worried that I had made the competition too easy, because the first four stages fell so rapidly. I was relieved to see that stage 5 stopped the rush for a while, but I was worried once again when Andrew Plater rattled his way through to stage 8.

The next breakthrough came when the team effort of Jim Gillogly, Jim Palagyi and EFF cracked stages 1 to 9 inclusive. Jim and John have written fascinating accounts of their exploits, which can be accessed here.

I had said that I would award £1,000 to the current leader on Oct 1, 2000, and this prize duly went to Jim, John and EFF.

Just a week later, my publishers received a fax from a team of Swedish researchers claiming that they had completed the entire Cipher Challenge.. Two days later, on October 7, the formal claim arrived in the post. I called the spokesperson, Fredrik Almgren, and a somewhat cautious dialogue ensued. How did the Swedes know that this was really Simon Singh on the phone and not some imposter trying to steal their solution? I was the only other person in the world who also knew the plaintexts, and this became the decisive factor in establishing a relationship of trust.

The challenge was over.

The Swedish team consists of Fredrik Almgren (Across Wireless), Gunnar Andersson (Prover Technology), Torbjörn Granlund (SWOX), Lars Ivansson (Royal Institute of Technology, Stockholm) and Staffan Ulfberg (freelance consultant).

They began working on the Challenge soon after The Code Book was published in September 1999, when Fredrik Almgren was in London taking part in a juggling festival.

Unlike many of the other competitors, they remained very quiet about their achievements until they had completed all ten stages. Their stealth approached seems to have paid off. They have written an excellent 40-page document that outlines their trials and tribulations, which you can download from their website.

Their report is not only an informative and amusing summary of their own approach to the Cipher Challenge, it is also a summary of the ciphertexts, keys, plaintexts and strategies.

Possibly the most interesting aspect of their achievement for expert cryptographers is that they were able to crack stage 10 without a supercomputer. The team wrote a number field sieve algorithm that was able to run on an 'ordinary' computer.

The main aim of the Cipher Challenge was to excite people, to get them interested in cryptography and codebreaking. The fact that thousands of people took up the challenge is tremendously satisfying.

A secondary aim was to demonstrate the strength of current ciphers. Stage 10 represents the sort of encryption that is sometimes used for Internet security, but the fact that it was broken does not mean that we should necessarily be worried about security on the Internet. It took a team of brilliant Swedish researchers several weeks and extremely powerful computing facilities to eventually decipher stage 10. This approach would not be practical for a thief who wanted to decipher come credit card details. The thief would require an investment of tens of thousands of pounds to get hold of a credit card with a cash limit of perhaps £1,000. Furthermore, it is easy to use a key that is orders of magnitude stronger than the one I used for stage 10. This results in an effectively unbreakable encryption system.

Perhaps more importantly, RSA is also used for so-called digital signatures, and 512-bit keys, such as the one used in stage 10, are widely used. Signatures often need to offer a guarantee of authenticity for decades, and so we need to be absolutely sure that they will remain secure in the future when computers become vastly more powerful. If a codebreaker can crack your RSA key then he can effectively forge your signature. Jumping to 1024-bit keys would re-establish a very high level of security, but a natural inertia means that many people continue to use 512-bit. The lesson is that it is important to monitor encryption standards and update them as the power of the codebreaker increases.

The third aim, a somewhat optimistic one, was the hope that the challenge might inspire some new codebreaking technique. The Swedish team did, in fact, rewrite the number field sieve algorithm so that it could operate on relatively ordinary computers, demonstrating that it is not necessary to use a supercomputer to factor a huge number.

At this point, it is time to bid a tearful farewell to the Cipher Challenge.

When I was preparing the Challenge, I sometimes wondered if it was worth it. Would anybody be interested in such a challenge? However, the reaction from readers has been incredibly gratifying, and I have been staggered by your enthusiasm, dedication, persistence, ingenuity, good humour and brilliance.

And, of course, congratulations to the winners. This includes Jim Gillogly, John Palagyi and EFF, who received a well-deserved reward of £1,000 for their considerable efforts. In particular, Jim has been enormously generous over the last year, offering limitless advice and support to novice codebreakers and potential rivals.

Nobody should underestimate the achievement of the final winners. Cracking stage 10, particularly in such an innovative way, will be of significance to the cryptographic community. And not only have Fredrik Almgren, Gunnar Andersson, Torbjörn Granlund, Lars Ivansson and Staffan Ulfberg demonstrated a talent for cracking modern computer codes, they have also devoured a wide range of classic ciphers, from homophonic substitution to the Enigma cipher. The range of skills required to accomplish all of this is substantial.

Finally, thank you to everybody who took part in the Cipher Challenge and for making it such a success. It was a genuine pleasure meeting Cipher Challengers in various parts of the world, from Sydney to Milwaukee, and I only wish that I could have met more of you. If I do meet you, at least I will no longer have to be so tight-lipped. For a blabbermouth like me, the last two years have been a real struggle.

Finally, finally, if you are still interested in cryptography, then I am currently presenting a TV series for Channel 4 in Britain, entitled The Science of Secrecy. It airs on Thursday nights at either 9.00 or 9.30pm until November 2. The final programme includes an exclusive interview with Clifford Cocks, the secret co-inventor of RSA. This is the first time that a British Government cryptographer has been permitted to talk about his work. Details of the series can be found on the Channel 4 website. The series is accompanied by a book entitled The Science of Secrecy. Please note, this is an adaptation of The Code Book, and so it will not be of interest to anybody who has already read The Code Book. It has the advantage of following the series more closely and contains more illustrations. Hence, I would certainly recommend it to anybody who has not read The Code Book, and who wants to learn more about cryptography having watched the TV series.

I hope that the TV series will be shown overseas, but as yet there are no plans to do this.

I hope that the joys of the Cipher Challenge have outweighed the sorrows.

TLLWYBV

HRNLM HRMTS