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

Ray Dillinger bear at sonic.net
Tue Jan 13 16:28:48 EST 2015



On 01/09/2015 01:56 PM, ianG wrote:

>> Does every large-scale military organization make stupid mistakes
>> subordinating security to petty officiousness, redundant procedure,
>> personal ego, and just plain laziness?
> 
> 
> Oh, absolutely.  Think of it this way.  In every routine battle, one
> side will lose, and the search for reasons for failure will be on, for
> that side at least.  The other side will have as many reasons, but will
> be able to sweep them under the carpet due to their "brilliant" victory.
> 

After finally doing a thorough analysis of the Enigma cipher, I
conclude that the biggest cryptographic weakness wasn't the
antireflexive property (though that was bad) or the way its
slow evolution allowed the easy extraction of cyclometric
information on the first rotor which allowed the wiring to be
worked out (though that was bad too). Those were both weaknesses
of the machine, which is what we're all trained to look for given
that we work with modern electronic ciphers.

But we've been thinking about the machine, and not about the
attacks.

The biggest single cryptographic problem is in the way it was used -
specifically in the selection of the rotor settings as the part of
the machine state that was used for a message key.

There was a day key consisting of the sequence and selection of
the rotors and the ring settings, and a message key consisting
of the rotor positions.

The rotor positions.  The only thing that changed during the
transmission of the message.  And the thing whose change during
the transmission of a message were nothing but offsets on the
exact same cycle of states.

D'oh!

Had the axis used the ring settings instead of the rotor
positions for the message key, every message transmitted
with a nonidentical message key would have been on a different
cycle of states, and not subject to this devastating related
key attack.

The sequence of states produced by the message key AAC was
exactly the same as the sequence of states produced on that same
day by the message key AAA, offset by two positions in that day's
single cycle.  And the sequence of states produced by the message
key ABA was the same as the sequence produced by the message key
AAA, offset by twenty-six positions.

The Germans were transmitting the message keys at the head of
every message, encrypted with a common setting.  This allowed
the allied cryptographers to know immediately which keys were
related by differences only in the last rotor (ie, sequence
offsets within 26 positions of each other).  They could then
find the index of coincidence for those messages, correlating
the different letters of the ciphertext message keys in the
last position with offset distances.  Then they could repeat
the process on keys having only the first rotor setting in
common, knowing that the sequence offset in those cases would
be the offset derived from the last rotor, plus some multiple
of 26 depending on the second rotor - rinse, repeat.  This
made a related-key attack from hell!

With three rotors, there were only 17576 possible rotor
positions, meaning Enigma traffic could be completely broken ---
easily, knowing NOTHING ABOUT THE ROTORS WIRING OR THE
POSITIONS OF THE RINGS, using nothing but armchair pencil-
and-paper methods not much different than crossword puzzles
-- on any day when the Allies intercepted more than about
30K characters of traffic.

And this was the state of things at the beginning of the war.
And although the Axis fixed other things, they continued to
use the rotor positions rather than the ring settings, or
rather than literally ANYTHING EXCEPT the rotor positions -
for message keys for the whole war.

The allies were able to use the information about the rotors
that they derived from all the broken traffic, to break more
traffic even as the Axis slowly built better enigma systems
and better procedures.

The four-rotor naval Enigma wasn't tougher due to having
a more complex cipher - the last rotor hardly ever moved
anyway and the reflector stator never moved at all.  It
was tougher because there were more rotor positions, and the
reflector stator could be in any of 26 different rotations
too - and therefore traffic was 676 times less likely to
overlap in its keying sequence.  Or, alternatively, you
could transmit 676 times as much traffic before breaking
it became trivial.  But by that time the Allies had wiring
diagrams of all the rotors....

Holy crap, I never realized how trivial it was to break at
the start of the war.  Or how much harder the Allies would
have had to work had they used the ring settings instead
of the rotor positions for message keys.

				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/20150113/43170618/attachment.sig>


More information about the cryptography mailing list