next up previous
Next: Afterpiece Up: Stage 9 Previous: The client/server connection

How we Found the solution

Slowly but steadily, the clients worked their way through the vast key space. After a week or so, the key server sent an email containing an alleged plaintext! Unfortunately, this was a key which passed the tests but did not yield a plaintext which looked reasonable. A couple of days later, another such key was discovered. Then, three weeks after the clients were started, the key server sent the following message:

Date: Fri, 12 Nov 1999 06:10:26 +0100 (CET)
From: DES server <des-server@multivac.fatburen.org>
Subject: Good news

This is a message from the server that coordinates the code-breaking
effort on Stage 9.

A client just reported that it might have found the correct DES key.
The key and the ciphertext decrypted with the candidate key follows.

Key: d3cd1694cba126fe

Message:
O!.cursed,.cursed.slave...Whip.me,.ye.devils,.From.the.possessio
n.of.this.heavenly.sight!.Blow.me.about.in.winds!.roast.me.in.su
lphur!.Wash.me.in.steep-down.gulfs.of.liquid.fire!.O.Desdemona!.
Desdemona!.dead!..Only.one.more.phase.to.go...Your.token.for.thi
s.one.is."Armstrong"...The.final.hurdle.contains.two.ciphertexts
...The.longer.one.is.encrypted.with.triple-DES.in.electronic.cod
e.book.mode...It.uses.a.128-bit.EDE.key...The.RSA.public.key.cry
ptosystem.has.been.used.to.encipher.the.triple-DES.key;.this.for
ms.the.shorter.ciphertext...The.public.exponent.is.3735928559.in
.decimal.and.the.public.modulus.is.the.following.155-digit.decim
al.integer:..10742.78829.12665.65907.17841.12799.42116.61266.392
17.94753.29458.88778.17210.35546.41509.80121.87903.38329.26235.2
!D<..t]s06.72083.50494.19964.33143.42555.83344.01855.80898.94268
....`h...Your.task.is.to.decipher.the.longer.message.and.so.disc
over.the.final.code.word...How.you.do.th.y..R(?..to.you,.but.it.
will.almost.certainly.be.much,.much.easier.to.break.the.RSA.ciph
ertext.by.factoring.the.public.modulus.than.by.any.other.approac
h...Good.luck!..
We had found the right key, yielding the codeword ARMSTRONG for this stage. Some parts of the message looked a bit strange, though. After checking these sections by hand, we discovered that the OCR scanner software we had used for importing the ciphers from the book into electronic form had made a couple of errors. After having corrected these, all the text looked good. We were aware that scanning errors could have occurred, and we had checked the first 12 blocks carefully as errors there could result in the correct plaintext being discarded.

We were a bit lucky; only about 17% of the key space had been searched when the correct key was found. This corresponded to about a CPU year on the hardware we had available. The client actually running into the correct key was one of the screensavers, running on a rather slow PC, and the job which contained the key would have been aborted if the user of that particular PC had not been a bit later to work than usual that day. If this would have happened, a lot of time could have been lost: Jobs that had been assigned to a client but not finished were placed last in the job queue by the server. Sometimes luck can be as important as a good approach.


next up previous
Next: Afterpiece Up: Stage 9 Previous: The client/server connection
solvers@codebook.org