The Cipher Challenge was a set of ten encrypted messages to be found at the end of The Code Book, a history of codes and code breaking that I published last year. In addition to the intellectual reward of cracking all ten messages, there was a prize of £10,000 for the first person to solve the Challenge.
The Challenge was officially solved on October 7, 2000, after one year and one month of arduous effort by codebreakers, amateur and professional, around the world. This part of the website attempts to tell the story behind the Cipher Challenge. It also contains essays by Jim Gillogly and John Palagyi, who might be considered as runners-up, and a highly readable 40-page report by the Swedish team who solved the Challenge (see below).
This section also contains the final leaderboard, which shows who cracked what, and a small gallery of photos that relate to the cipher challenge. You can also find the actual ciphertexts on-line. Although the solutions are now public knowledge, you might want to exercise your brain and crack a few of them.
If you want to know more about the background to the Cipher Challenge then you can start by reading the rest of this introductory page, or you will find articles about the Challenge in The Telegraph, The Hindu, you will find out how it was cracked, and an archive of material published during the competition.
Before continuing, for those of you intending to complete the Cipher Challenge for yourself, I must warn you that this page contains spoilers!
When 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 unravelling 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 it. The Challenge was compiled in complete secrecy, with great care being taken that 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:
- 10 stages of increasing difficulty so that everybody can take part in at least a few of the stages.
- 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.
- 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.
- 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.
- 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, which was published in Britain and America, and 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 and is briefly documented in the updates there, 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, John Palagyi and EFF cracked stages 1 to 9 inclusive. Jim and John have written fascinating accounts of their exploits.
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 impostor 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), Torbjorn 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 approach seems to have paid off. They have written an excellent 40-page document that outlines their trials and tribulations, available in the following formats:
HTML files
PDF files
PS files
DVI files
You can download the Adobe Acrobat Reader here.
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, and have thus demonstrated that factoring large numbers does not necessarily require supercomputers.
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 some 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 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, Torbjorn 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.
To read news stories about the cracking of the Cipher Challenge, please visit these sites:
The Daily Telegraph, Thursday 12 October, 2000
Swedish team cracks code to win £10,000
Ny Teknik, October 2000
Svenska kodknackare vann Simon Singhs chiffertavling (Swedish)
Plus Net Magazine