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:
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.
e)
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.
TLLWYBV
HRNLM HRMTS
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
TechTV.com, 12
October 2000
Computer Team Cracks World's Toughest
Code
Ny Teknik,
October 2000
Svenska
kodknackare vann Simon Singhs chiffertavling
(Swedish)
Plus Net Magazine
Cipher Challenge
Cracked |
|
