[2981] in cryptography@c2.net mail archive
Re: Turing Bombe story
daemon@ATHENA.MIT.EDU (Carl Ellison)
Thu Jul 16 21:52:53 1998
Date: Thu, 16 Jul 1998 21:40:48 -0400
To: "Scott G. Kelly" <skelly@redcreek.com>
From: Carl Ellison <cme@acm.org>
Cc: Carl Ellison <cme@acm.org>, Steve Reid <sreid@alpha.sea-to-sky.net>,
Marcus Leech <Marcus.Leech.mleech@nt.com>, cryptography@c2.net
In-Reply-To: <35AE7E00.AEF5534@redcreek.com>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
At 03:26 PM 7/16/98 -0700, Scott G. Kelly wrote:
>> As for a modern Pentium beating the Bombe, maybe -- but the Bombe did an
>> incredible number of LIPS. It was testing for logical contradictions and if
>> you were to do the Bombe in Prolog, it could bog down a modern processor....
>
>So, just out of curiosity, could someone build a similar (specialized)
>machine for DES... or skipjack?
Yes, that machine could be built. I have a design for it. Unfortunately,
DES doesn't lend itself to logical contradiction searches. That means that
Wiener's design is probably the best for DES searches, at this time.
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.
BTW, the max plugboard uncertainty wasn't with 6 unplugged as I said
earlier, but with 4 -- for C(26,4)*21*19*17*...*3 = 2.06E14 -> 47.5 bits of
plugboard key.
The total Enigma key search space is then: 5.9 + 14.1 + 47.5 = 67.5 bits or
3018 times harder to brute force than DES [40 years before DES].
So, a brute force of Enigma with a non-Bombe design might take a substantial
length of time even on today's silicon.
- Carl
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.5.3
iQA/AwUBNa6rn5SWoQShp/waEQLmLACfdWbEv4bsjf3UkTkhFqbL0uw0QdcAoI1G
f2GZ54cSimBPm0bsDEdLW+gC
=Nf8J
-----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.--+
