During the Cipher Challenge, I maintained a website on my publisher’s website. Just for the record, the postings to that site are maintain in this archive. The leaderboard was also available on my publisher’s website and this is still accessible via the main Cipher Challenge page.
Stages 6 to 9 Cracked
Cipher Challenge Update 1
9th November 1999
I was impressed by the rapid progress that was made when I first issued the Cipher Challenge. Within a few days of publishing The Code Book codebreakers had deciphered the first four parts of the 10-stage Cipher Challenge. The codebreakers included a speech therapist, a philosopher, a medical researcher and a fifteen-year-old student, suggesting that a wide variety of people are attempting to crack the codes.
During the last two months, however, the leaderboard has remained unchanged, because nobody has been able to crack the mysterious stage 5. It might seem that decipherment has ground to a halt, but in fact I have been informed that codebreakers have succeeded in deciphering stages beyond stage 5. Unless these codebreakers can crack stage 5 (and stages 1 to 4), they will not appear on the leaderboard, but I thought that readers of The Code Book might be interested in these breakthroughs, and so I have summarised what has happened so far in this Cipher Challenge Update.
While codebreakers around the world, professionals and amateurs alike, were scratching their heads over stage 5, I was contacted by James J. Gillogly, a former President of the American Cryptogram Association (ACA), an organisation for amateur codebreakers. He recently hit the headlines when he deciphered a secret message inscribed on a sculpture in a courtyard of the CIA headquarters building in Langley, Virginia, just outside Washington DC.
Gillogly claimed, and then proved to me, that he had deciphered stages 1 to 4 and stages 6 to 9. In other words, for him, only the notorious stage 5 and the final stage 10 remain.
Although this does not change the leaderboard, I contacted the current leaders, who then told me of their progress. Souraya Dyer, a fifteen-year-old London student, has cracked stage 6 and is currently attempting stage 7. Dr Roger Gunn, a medical researcher from Ealing Common, is doing even better. Having cracked stages 1 to 4 alone, he is now working with his brother, Dr Steve Gunn, a lecturer in Intelligent Systems, and has cracked stages 6, 7 and 8. Together, they are currently working on stage 9.
But what about the mysterious stage 5? The encrypted message contains a list of numbers, and when I created stage 5, I certainly did not think that it would prove to be so difficult. I do not want to give away any clues, but I will say the following: even though the encrypted message is made of numbers, you do not need to be a mathematician to crack it. In fact, a schoolchild is as likely as a professional codebreaker to decipher stage 5. The encrypted message has much in common with the infamous Beale Ciphers, which also contain a series of numbers. To decipher the three Beale Ciphers it is necessary to find the so-called key-texts. One of them has been deciphered, and the key-text turned out to be the Declaration of Independence. The key-text for the other two ciphers is missing, and, of course, the key-text for stage 5 of my Cipher Challenge is also a mystery.
It will be interesting so see how long it will take to crack stage 5. It could be that people will start working in teams. The Cipher Challenge is already being discussed on the “sci.crypt” Usenet news group, and someone has set up a mailing list to generate discussion. It is also possible that somebody has already cracked stage 5, but has not been able to crack stages 1 to 4. Such a person would not qualify for the leaderboard, and so would not have contacted me.
All this discussion of higher stages may be dispiriting to challengers who are only just beginning or to those who are having trouble with the early stages. I would offer the following words of encouragement. Many amateur codebreakers cracked stages 1 to 4 in a matter of days, and these stages were designed so that any non-expert could crack them with just a little effort and dedication. Perhaps I should warn you that stage 3 is a little harder than stage 4. Hence, if you get stuck with stage 3, you might want to have a go at stage 4, and then return to stage 3 with renewed vigour.
And once you have cracked stages 1 to 4, then you might be the person who has the insight that cracks stage 5, at which point you would be leading the Cipher Challenge.
Ps. Although I was glad to be contacted by James J. Gillogly, in general I would prefer to hear only from codebreakers who have made a breakthrough that affects the leaderboard. In other words, please do not send me any decipherments unless you can decipher stage 5. Good Luck.
Stage 5 Cracked
Cipher Challenge Update 2
7th December 1999
After three months of effort, stage 5 has now been deciphered.
Andrew Plater, a British mathematician from Cambridge who specialises in factoring, has sent in the code word for stage 5, along with the code words for stages 1 to 4.
Cipher Challenge Update 3
20th March 2000
Unfortunately, there is not much to report in the way of recent breakthroughs, but having remained silent for a couple of months I thought that I would provide a brief update and some clarification.
First, I have received queries regarding the international nature of the competition. I would like to confirm that there is one worldwide Cipher Challenge. However, the Italian edition of “The Code Book” does not carry the world Cipher Challenge, because of local laws that have made it difficult to extend the Challenge to Italy. Instead, the Italian edition contains a separate competition with a separate prize. I am sorry if this has caused any confusion.
Second, following his decipherment of Stage 5, Andrew Plater has gone on to decipher Stages 6, 7 and 8. The leaderboard points out who is leading the Cipher Challenge, but it does not reflect the worldwide activity and progress. For example, a poll conducted by one of the Cipher Challenge discussion groups suggests that Stage 5 has also been broken by at least five other people. Furthermore, dozens of other codebreakers have temporarily sidestepped Stage 5 and have cracked subsequent stages, including Stage 9.
Although the leaderboard is dominated by Britons, I feel that the Cipher Challenge is a fair competition for codebreakers of all nationalities. At the moment Andrew Plater is in pole position, but I know that a number of other codebreakers from a variety of countries are hot on his heels.
Six months have now passed since the Challenge began, and six months remain until I will award the £1,000 prize for whoever has progressed the furthest. And, of course, it might be that the entire Challenge will be completed before October 1, 2000, in which case the entire £10,000 will be awarded to the successful codebreaker. Good luck.
Guest article for the 4th Estate Website
Cipher Challenge Update 4
When my publishers asked me to write an essay on the subject of the Cipher Challenge for their website, I must admit to feeling somewhat dubious. As long as the Cipher Challenge is still ongoing, it is difficult to write much that is particularly interesting, because at all times I have to be careful not to give away any clues. Nevertheless, working within the obvious constraints, I will attempt to address a couple of the questions that people often ask.
For those who do not know about the Cipher Challenge, it consists of ten encrypted messages at the end of my book about the history of cryptography, “The Code Book”. Having learnt about the secrets of codebreaking, I thought that some readers might enjoy trying to decipher some encrypted messages. To make it a little more interesting, I have offered a prize of £10,000 for the first person to crack all ten messages.
The question that I am most often asked is: “Who is paying the £10,000?” The answer is me, the author. The next question invariably is: “Are the codes so difficult that nobody can crack them and claim the money?” No … at least I do not think so. In any case, I have stated in the rules of the contest that if the entire Challenge has not been completed by 1 January 2010 then the money will be given to whoever has got furthest quickest. I hope and expect that the money will be won before that date. Having mentioned the prize, I would emphasise that the main goal for any codebreaker should be the challenge of decipherment. Readers who attack the stages will experience the thrill and satisfaction of cracking a code, whether or not they win the prize. And I would hope that all readers attempt to decipher at least a few of the stages, especially as the early stages are certainly aimed at the beginner. The middle stages are intended for the intermediate codebreaker and the later stages are for the truly determined.
As I said, there is not much that I can say about the Cipher Challenge, but I will finish by pointing you towards a website where you can find more information. Challengers have formed a group at the eGroups website, which now has 1,700 members, including schoolchildren, amateur codebreakers, beginners, enthusiasts and professionals. Members of the group exchanges e-mails on a daily basis, offering hints, tips, ideas, support and some lighter comments about the joys and sorrows of codebreaking.
If you decide to take up the Cipher Challenge or are already ploughing through the stages then may I wish you the best of luck. I hope that you will enjoy many minutes, hours, or weeks of happy cracking.
Ps. When the Cipher Challenge has been completed, I intend to work with the successful codebreaker to write a proper essay about the Challenge, describing how each stage was constructed and broken.
PPs. On the rare occasion that I say or write anything about the Cipher Challenge, invariably there are challengers who search for clues in the hope that I have dropped a sneaky hint. In fact, I am far too boring and not cunning enough to do this. Please do not bother scrutinising this essay for hidden clues, because I can assure you that there is nothing to find!
Cipher Challenge Update 5
On October 1, 2000, the leaders in the Cipher Challenge were Jim Gillogly and John Palagyi, who had worked with the EFF team (John Gilmore, with assistance from Simon Cooper, Landon Noll and half of Deep Crack).
Congratulations to Jim and John, who will receive the intermediate prize of £1000 ($1500). Of course, the full £10,000 prize remains for the first person to decipher all ten stages.
Later this week, I will be adding more information about this latest development. In the meantime, British cipher challengers might be interested to know that I am hosting a 5-part series for Channel 4 on the history of codes and codebreaking. The series starts on Thursday 5 October at 9.30pm. The series will contain its own mini code challenge.
Cipher Challenge Cracked
Cipher Challenge Update 6
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.
Cipher Challenge Correction
Please note that some printings of the book have omitted a character in Stage 8 of the Cipher Challenge. In the box entitled ‘Schriftzeichen’, there should be a back tick as the only character on the third line, i.e., below the left bracket and above ‘end’. By back tick, I mean the character that already appears twice in the box, on line two, in positions five and thirteen.