[3072] in cryptography@c2.net mail archive
Re: Turing Bombe story
daemon@ATHENA.MIT.EDU (Clive D.W. Feather)
Fri Jul 24 18:48:02 1998
Date: Fri, 24 Jul 1998 18:45:29 +0100
To: cryptography@c2.net
From: "Clive D.W. Feather" <clive@on-the-train.demon.co.uk>
Reply-To: "Clive D.W. Feather" <clive@linx.org>
In-Reply-To: <3.0.3.32.19980717014012.031a4110@pop3.clark.net>
In article <3.0.3.32.19980717014012.031a4110@pop3.clark.net>, Carl
Ellison <cme@acm.org> writes
>Hash: SHA1
>
>At 12:44 AM 7/17/98 -0400, Marc Horowitz wrote:
>>Can you explain what "logical contradiction testing" is?
>
>In the case of the Bombe, there was assumed plaintext (with reasonably high
>probability).
[...]
I've been meaning to write a description of how the Bombes worked for
some time, and this has pushed me to do so.
The Enigma consisted of the following parts:
- keyboard and lamp board
- a plugboard
- three rotors
- the reflector
I won't describe the details of how it worked, because they're well
known. However, it should be noted that the plugboard and the
rotors+reflector combination (the "scrambler") were symmetric - if they
mapped a B to a Q, they would also map Q to B. It's also worth
introducing a device called a "double-ended scrambler" (DES). This is
functionally equivalent to the scrambler, but has *two* sets of 26
contacts. Each rotor is actually a duplicate rotor, with 4 (not 2) rings
of 26 contacts. It is wired thus:
26 26
in --/----+ +----/-- out
| |
######## right rotor
| |
######## middle rotor
| |
######## left rotor
| |
@@@@ reflector
Now, suppose that with some specific plugboard setup and rotor
arrangement, the message TEST is encrypted as ESQS (i.e. this is our
crib). Now let us build a circuit simulating this:
[1] [5]
| |
PB PB
| |
DES1 DES4
| |
PB PB
| |
[2]--PB--DES2--PB--[3]--PB--DES3--PB--[4]
PB is a plugboard, DESn is a double-ended scrambler (the numbers
indicate the relative positions in the message) and all connections are
26-way.
If we put a voltage on line T at point [1], we should see it appear on
line E at [2], line S at [3], line Q at [4], and line T at [5]. However,
if any of the following are true:
- the crib is wrong
- the rotor arrangement is wrong
- the plugboard setup is wrong
then it will appear at different places.
Now let's try to simplify the circuit. Firstly, notice that the
plugboards are symmetric and we can eliminate most of them:
[1] [5]
| |
PB PB
| |
[6] [7]
| |
DES1 DES4
| |
[2]--DES2--[3]--DES3--[4]
Now we can no longer predict where the voltage will appear at points
[2], [3], [4], [6], and [7] (because it will depend on the plugboard),
but it should be the T wire at [5]. Now let's connect [1] to [5]:
[1]--------[5]
| |
PB PB
| |
[6] |
| |
DES1 DES4
| |
[2]--DES2--[3]--DES3--[4]
Now when we apply a voltage to line T at [1], it should appear on
exactly one line at every point. If something is wrong, however, it will
appear on a different line at [5], and so go round the circuit again.
Probably it will now appear on a third line, and a fourth, and rapidly
appear on all 26 lines.
In other words, if our setup is correct, line T at [1] is electrically
isolated from the other 25 lines, while if we have anything wrong all 26
lines are connected together.
Next, let's make another rewiring:
[1]
|
PB
|
[6]---------+
| |
DES1 DES4
| |
[2]--DES2--[3]--DES3--[4]
Instead of putting the voltage on line T at point [1], let's put it on
an arbitrary line (say line A) at point [6]. Now the possibilities are:
* The plugboard connects A to T. The voltage will appear on no other
line at point [6].
* The plugboard does not alter T. The voltage will appear on 24 of the
other lines at [6], but not T.
* The plugboard connects T to (say) B. The voltage will appear on 24 of
the other lines at [6], but not B.
* Something is wrong in our setup: the voltage will appear on all of the
other 25 lines at point [6].
Note that if we'd chosen line T at point [6], the first three cases are
replaced by:
* The plugboard does not alter T. The voltage will appear on no other
line at point [6].
* The plugboard connects T to (say) B. The voltage will appear on 24 of
the other lines at [6], but not B.
Note that, at this point, we no longer need either point [1] or the
plugboard.
So if we take our circuit, inject a voltage on to line A at point [6],
and "logical AND" the other 25 lines together (which can be done with
relays), we know that something is wrong if the result is true, while
our assumptions are correct if the result is false. So our final circuit
is:
1 25
+ve --/---+---/--- test equipment
|
/26
|
[6]---------+
| |
DES1 DES4
| |
[2]--DES2--[3]--DES3--[4]
Now, let's assume we have the correct choice of rotors but don't know
their starting position. All we do is spin the four double-ended
scramblers through every one of the 26^3 positions. When the test
equipment signals that the result is false, we stop and see what's
happened. Dealing with the rotor choice is harder, but this is a
government project after all, so we just build 60 sets of equipment and
try each of the possible orderings at the same time.
Notice that, although we hope that all the wires will be connected
together if we've made an error, there's no guarantee that that's the
case. Instead, we must do everything possible to increase the
possibility. One thing to do is to have more loops - the more loops that
a crib generates, the more chance there is of the circuit detecting a
contradiction. In fact, it turns out that the expected number of "false
drops" is 26^(3-L), where L is the number of loops in the circuit. So we
really want cribs with 4 loops or more.
However, a much better invention was the "diagonal board". Let us write
$A to mean the line connected to A by the plugboard. Then in our
original case, if we put a voltage on line $T at point 6, it should
appear on $E at [2], line $S at [3], and line $Q at [4]. Now, suppose
that we connect S[2] to E[3]. If $E=S, then $S=E, and so both these
lines will have the voltage on them and the wire has no effect. However,
suppose one of our assumptions is wrong. Then at [3] not only will the
current appear on $S through DES2, but also on E through this new wire.
Thus we have a new path for our bad assumption to spread voltage through
the wiring. In general, if two points [X] and [Y] represent X and Y in
the crib, then we want to link X at [Y] to Y at [X]. This was done
through the "diagonal board".
The board consists of a grid of 26x26 terminals, with the rows and
columns each labelled A to Z. The 26 terminals of a row are connected to
the point in the main circuit representing the letter labelling the row
(thus row E to [2], row S to [3], row Q to [4], and row T to [6]); in
each case wire A goes to column A, wire B to column B, and so on.
Finally, the grid connects all points not on the main diagonal in pairs:
AB-BA, AC-CA, AD-DA, ... BC-CB, BD-DB, ... YZ-ZY.
The diagonal board was said to reduce the number fo false drops by a
factor of about 100. Much more importantly, it allowed letters in a crib
to be used even when they didn't form part of a loop, and allowed useful
cribs to have less than 4 loops.
So now we can see how to convert a crib to a Bombe setting. Each DES has
two 26-way cables coming out of it. If one letter pair in the crib is
(say) J to U at position 6, connect one cable to cable J from the
diagonal board and the other to cable U, and set the rotors by hand to
ZZF (F being the 6th letter). Repeat for all the other letters in the
crib. Connect either cable from any rotor to the test kit (the voltage
source on one wire and the 25 test relays on the others). Now set the
rotors spinning, and whenever the test kit says something's happened,
note the results. [It was normal to then continue the run, because it
would finish faster than the "drop" could be tested.]
The Bombes had no way of allowing for the middle or left rotors stepping
within a crib. Thus it was essential for the crib to be limited in
length (a 13 letter crib makes the probability 50%, though of course two
adjacent 13 letter cribs are best, because one of them won't have the
problem).
The four extra wheels seen on pictures of some Bombes are nothing to do
with the above system, but were used for testing drops. At other sites
these wheels were part of a separate device. There was a process for
testing the drops, but I don't have notes of it.
Hope this all made sense. Please ask if anything's unclear.
--
Clive D.W. Feather | Regulation Officer, LINX | Work: <clive@linx.org>
Tel: +44 1733 705000 | (on secondment from | Home: <cdwf@i.am>
Fax: +44 1733 353929 | Demon Internet) | <http://i.am/davros>
Written on my laptop; please observe the Reply-To address
