[Cryptography] Imitation Game: Can Enigma/Tunney be Fixed?

[Ray Dillinger]

On 01/05/2015 09:41 AM, Tony Arcieri wrote:

> Enigma is fatally flawed in its current design, AFAIK. Due to the nature of
> how its rotors operate, it can't encrypt a letter to itself, introducing a
> statistical bias into the ciphertext.
> 
> Enigma would need to be modified so all letters have equal probabilities.
> Someone who knows the intricacies of these rotor machines better than me
> might know what's involved.

The Enigma actually had two fatal weaknesses.  First, as you
correctly point out, the allies exploited the can't-map-to-
itself property to great effect; t was how the Bombes
eliminated possibilities in great quantities once they were
started.

Second, there were not nearly enough different rotors.  The
Germans never deployed more than eight different movable
rotors, plus a couple (beta and gamma) that, though they
could be hand set to any position, were immovable, could
only be deployed in a single known location, and could
not be combined.

The Allies eventually worked out the wiring of all these rotors,
and this formed the set of possibilities that the Bombes started
from.  Once you know that the message is encrypted using a
selection of four out of just eight different movable rotors,
whose geometry you know, and and you know the geometry of the
input/output signals, and you know that there can be one of only
53 remappings of the signals at the reflector (beta and gamma
"rotors" in each of 26 positions, or just plain reflector)...
you have a limited set of possibilities to check.  Limited
enough that they might have been able to run through them
even without the cant-map-to-itself property.  It would have
been much harder to break and, on the relatively rare breaks
would have given much less timely information - but it would
be possible.

The steckerbrett helped the security a lot by rearranging the
geometry of the input-output signals. The "beta" and "gamma"
rotors did the same basic job at the reflector end, but they
could only be used to make a very limited number of remappings.

Fixing the cant-map-to-itself property would be the highest
priority.

In terms of electromechanical parts count/intricacy, that
could be done by doubling the amount of wiring and contact
points in each rotor.  Providing separate electrical paths to
and from the reflector would permit each letter to map to any
other letter including itself, giving the Germans the
cryptographic mileage they *believed* they were getting out
of their reflector mechanism.

A possible implementation of this would have two sets of
contacts in concentric rings in each rotor, so that signals
going *to* the reflector passed in one ring and signals
coming *from* the reflector passed via the other.

That would have slowed down the Bombe's drastically, because
they would then be unable to eliminate possibilities automatically
based on the can't-map-to-itself property.  But you still have
the not-enough-different-rotors problem.  Bluntly, with only
eight distinct movable rotors, and the rotors each having a
geometry known to the allies, a brute-force attack would still
be somewhat feasible - though much more expensive and usually
providing untimely results.

It would be beneficial to have about half the rotors map paths
from the inner to the outer ring of contacts and vice versa.
Cryptographically this would help with the not-enough-rotors
problem because downstream of such a 'swap' the rotors have the
effect of reversed inner and outer permutations, so now there
are four possible ways a rotor can "face" instead of just two.
Depending on the disks closer to the I/O than it is, it can be
"inside out" or "right side out" as well as "facing left" or
"facing right".

If I wanted to secure the Enigma with WWII tech (against
WWII tech), I'd use the doubly-complex rotors described
above.

With the doubled contacts and paths, each steckerbrett would
have to be 26 rather than 13 sockets, which would double the
complexity of the steckerbrett but extend the key by 26!
possibilities as compared to 13! possibilities, which is  bad
for our parts count but good for our key length.

Next, I would get rid of the "beta" and "gamma" non-movable
rotors entirely and replace them with a second steckerbrett
on the reflector side. That would do the same job of remapping
electrical paths at the reflector, but would do it in a much
more versatile way, with 26! possibilities (again) rather
than 53.

At that point you'd have effectively doubled the physical
complexity and added a factor of probably at least 20% to
the manufacturing costs of each machine.  If at all possible
I would deploy it with 26 rotors to choose from instead of
8, which would probably increase manufacturing costs again
by another 20% or so and also increase the effective weight
and bulk of each machine.  At that point though, I am
confident that it would be every bit as unbreakable in
practical terms (given WWII capabilities) as the Germans
believed it to be.

But it would still crumble (not easily, but given realistic
amounts of traffic it could be broken) in the face of
modern methods to use against rotor machines.

There are some additional things you could do to introduce
displacements of the positions at which rotor movements
take place from the wiring geometry, or introduce
displacements of the inner "ring" of contacts relative
to the outer "ring" on each rotor, thus adding bits to
the key -- but while they'd force the allies to run
through more guesses they would add greater complexity
(and potential mistakes) for not-very-much-greater
encryption strength relative to the above improvements.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150106/bdcfd663/attachment.sig>