[2983] in cryptography@c2.net mail archive
Re: Turing Bombe story
daemon@ATHENA.MIT.EDU (Carl Ellison)
Thu Jul 16 23:16:21 1998
Date: Thu, 16 Jul 1998 22:40:32 -0400
To: "Marcus Leech" <Marcus.Leech.mleech@nt.com>
From: Carl Ellison <cme@acm.org>
Cc: Carl Ellison <cme@acm.org>, "Scott G. Kelly" <skelly@redcreek.com>,
Steve Reid <sreid@alpha.sea-to-sky.net>,
"Marcus Leech" <Marcus.Leech.mleech@nt.com>, cryptography@c2.net
In-Reply-To: <35AE445E.2A5EC434@nortel.ca>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
At 08:20 PM 7/16/98 +0200, Marcus Leech wrote:
>Carl Ellison wrote:
>
>> I should write up my modern Bombe design. There may be a cipher out there
>> that could be vulnerable to such an attack -- not to mention Enigma itself.
>> It might be fun just to show out how fast we could make a Bombe in today's
>> technology with no moving parts and modern gate switching times.
>>
>> I wouldn't be surprised if we could test 10^8 keys a second, which would
give
>> a total exhaustive search time of about 10 msec. or 5 msec. average time
>> to a drop.
>>
>Yes, Carl, do it.
>
>What I'd like to see is it translated into something you could
> code in C, without Prolog intervening. Given the relatively
> simple electro-mechanical nature of the Bombe, you'd expect
> to be able to translate it into software relatively easily.
> You mentioned a ballpark of about 10^6 high-level operations
> required; even if that breaks down into (let's say) 10^3
> micro-operations, that's still doable in software, with
> an impressive break time.
I'm not sure it's that fast. You might have 10^6 micro-operations for
each of the 10^6 rotor positions. I guess we just have to program it
to find out.
The thing that made the Bombe so blazingly fast was that Turing (and the
Poles before him) used voltage on a wire as a logical TRUE and used
switches, with bi-directional voltage flooding. What would be the execution
of many hundreds of lines of C happened at the speed of light, in this 1940
machine. From the time the rotors were in a new position, the actual
logical contradiction testing took just a few nanoseconds -- or effectively
0, since it took so long to move the rotors. That processing time didn't
depend on the complexity of the Bombe menu -- only on the physical
dimensions of the Bombe itself. In fact, the more complex the menu, the
faster the Bombe would decide that it had a logical contradition and could
move on.
With a modern processor, we could do the rotor movement much faster than the
Bombe did -- but I know we'd be significantly slower at the logical
contradiction testing. Instead of a few nanoseconds, it would take a
substantial fraction of a second (just a guess). If I remember correctly,
the Bombe got into a new rotor position in about 10 msec. I don't know if
we could do the logical contradition testing in less than that without the
custom hardware I had envisioned.
A S/W solution would probably take programming similar to what one does in
a chess playing program when it scans for threat and does a static
evaluation of a board -- only the "board" is much more complex and the
evaluation needs to be iterated. It's a flooding algorithm. Imagine a
board whose topology changes with each rotor position and whose pieces spawn
children everywhere the piece can go....
>I'm glad my little post stimulated an intellectually interesting
> topic :-)
To me, this is a fascinating topic. It was trying to understand Enigma back
in the early 80's that led me into real cryptology.
--------
Well, let's look at some code fragments...
typedef struct {
int l, m, r; /* left, middle and right offsets */
int lw, mw, rw; /* left, middle and right wheel selection */
} POSIT ;
void step( POSIT *p )
{ int x ;
p->r = x = (p->r + 1) % 26 ;
if (x != 0) return ;
p->m = x = (p->m + 1) % 26 ;
if (x != 0) return ;
p->l = (p->l + 1) % 26 ;
return ;
} /* step */
So, stepping each Enigma copy (let's say 12 per Bombe) is pretty cheap.
We can do 12 executions of step() in much less than the 10 msec the
mechanical bombe may have taken.
Now let's look at the propagation of voltage along wires of the bombe.
typedef int ROTOR[26] ;
ROTOR r1 = { ..... } ;
ROTOR r2 = { .... } ;
etc. through r5
ROTOR u = {...} ; /* reflecting rotor -- Umkehrwalze */
ROTOR ir1 = {...} ; /* inverse of r1 */
etc.
ROTOR r[5] = { r1, r2, r3, r4, r5 } ;
ROTOR ri[5] = { ri1, ri2, ri3, ri4, ri5 } ;
int propagate( POSIT *p, int v )
{
v = (v+p->r) % 26 ;
v = r[p->rw][v] ;
v = (v + p->m + 26 - p->r) % 26 ;
v = r[p->mw][v] ;
v = (v + p->l + 26 - p->m) % 26 ;
v = r[p->lw][v] ;
v = (v + 26 - p->l) % 26 ;
v = u[v] ;
v = (v + p->l) % 26 ;
v = ri[p->lw][v] ;
v = (v + p->m + 26 - p->l) % 26 ;
v = ri[p->mw][v] ;
v = (v + p->r + 26 - p->m) % 26 ;
v = ri[p->rw][v] ;
v = (v + 26 - p->r) % 26 ;
return ( v ) ;
} /* propagate */
propagate() will need to be called probably 600 times, along with other
code, while doing the logical contradiction testing for a single rotor
position.
Of course, this hasn't been optimized beyond the obvious, but I think you
see what I mean. In the 1940 bombe, each propagate() happened in about 1
nanosecond -- and was happening in parallel through as many as 300 parallel
"machines" (each wire of each of the 12 enigma copies).
That's why I'm not so sure we can do that much better on modern processors.
- Carl
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.5.3
iQA/AwUBNa65n5SWoQShp/waEQJ30wCfRLqrb0eZSJ6Co4YBfTzepDgvaAcAoI2n
N5MIbTHtvuTaG7uNUnFG4dJH
=ioAM
-----END PGP SIGNATURE-----
+------------------------------------------------------------------+
|Carl M. Ellison cme@acm.org http://www.pobox.com/~cme |
| PGP: 08FF BA05 599B 49D2 23C6 6FFD 36BA D342 |
+-Officer, officer, arrest that man. He's whistling a dirty song.--+
