[Cryptography] Hypothetical WWII cipher machine.

Sat Jul 18 12:39:40 EDT 2015

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 07/17/2015 10:56 PM, Ray Dillinger wrote:
[....]
> He asked me for a detailed design for something that (A) could
> realistically have been built around WWII, (B) is not a rotor
> machine, (C) is very much more secure than Enigma, (D) that he
> could do a cool, interesting, understandable illustration of,
> (E) whose basic operation could be explained in one page or
> less, and (F) would not make real cryptographers laugh if they
> read his book.

Do you want good fiction, or good cryptography?  The
two are not entirely aligned.  
  a) For the story to work, most authors would want 
   the MacGuffin to be revolutionary and weird.
  b) For good practical cryptography, you probably want
   a machine that is an incremental improvement over
   the existing rotor machines.

If I were writing the story, I would defy the first
assumption and lampshade it:  The most remarkable
thing about my Mark-II Plot Device is that there is
nothing very remarkable about it.  It's a bundle of
relatively prosaic refinements that work well together.

> The diagram and one-page explanation are at
> 
> http://www.sonic.net/~bear/DiabolusCipherMachine.png
> 
> My only objections to it are practicality, not security; key
> setup would be a big pain in the butt, and during the
> process small removable parts could become lost making the
> machine useless.

Practicality is relevant here.  Cryptography exists 
at the intersection of esoteric mathematics and 
down-to-earth engineering.  The mechanical details
of the proposed Plot Device are unexplained, and 
seem implausible.  Unless you are going to send 
Ernő Rubik back in time to design the thing, it 
seems unlikely that the mechanics would operate
reliably.

> One of the problems with Enigma, and most rotor machines, is
> that too much of their state is static.  While their setup can
> have a lot of crucial bits, most of them are things that don't
> change during encryption/decryption

Slowly-changing state is "one" of the problems, 
but nowhere near the worst of the problems.

> [....] make
> the machines very prone to related-key attacks (which was how
> Bletchley Park worked). 

Yes, related-key attacks are a Big Deal.  Reference: 
excellent post by Ray Dillinger on 01/13/2015 02:28 PM.

> In fact the only thing that changes
> during encryption is the rotor positions, and those only
> describe a small fraction of the total state.

I don't see that as the essence of the problem.  The
Plot Device has a tremendously long cycle time ... 
but cycle time isn't the problem that most needed 
solving.  If the messages aren't hugely long, a 
modest cycle time suffices.  Conversely, it doesn't
matter how long the cycle time is, if the IVs span
only a small part of the state-space.  A longer and 
more secure IV is much closer to the heart of the 
matter.  That's a major contribution to the size of 
the search space the cryptanalyst must deal with.

To be specific:  Here's my Mark-II Plot Device:  Let's
drop requirement (B).  It's still a rotor machine, 
just a much-improved rotor machine.  My objectives are:
 *) The machine is mechanically reliable.
 *) The machine is electrically reliable.
 *) The machine is readily manufacturable using
  contemporary technology.
 *) The operating procedures don't place undue burdens
  on the ordinary code clerk.
 *) The hardware and procedures are cryptologically sound.

Description:

  1) Use 6 rotors straight-through (as in the M-209).
   That's better than using 3 rotors and a reflector.
   For starters, it gives a larger key-space.  Also it
   gets rid of the reciprocity bug.  If you want to get
   fancy, use 8 rotors.
  2) Choose those rotors from a set of 20. That's much
   better than choosing 3 from a set of 5, or even 4 
   from a set of 8.
  3) Make frequent changes to the Ringstellungen.
  4) Have a more sophisticated way of deciding which
   wheels advance (again, as in the M-209).  In my 
   Mark-II Plot Device, the wheels are advanced by
   solenoids (not by a motor).  Steppers of this
   kind were well-developed technology at the time,
   used in e.g. telephone switchgear.  Advancement
   is controlled by a some wheels in the "back 
   stage" area (taking the place of the drum+lugs 
   of the M-209).  Advancement depends in part on
   the plaintext and ciphertext, so there is an
   element of cipher chaining.  Each wheel has 
   roughly a 50% chance of advancement per character.
  5) Implement the permutation circuits (i.e. the
   inner wheels) using printed circuit boards.
   This was well-developed technology at the time.
   Millions of PCBs were made for e.g. proximity 
   fuses for anti-aircraft shells.  This means the
   wheels are cheap, lightweight, thin, strong, and
   reliable. This makes it feasible to ship 20 or
   more inner wheels with each machine.  The PCBs
   snap into the rings.
  6) Provide a set of dice, and require operators
   on pain of death to use the dice to select the
   message indicator (which nowadays would be called
   the initialization vector) ... and also the nulls.
  7) At the beginning of each message, and the clerk
   MUST insert a random number of random null words.
   Among other things, this means that no two cipher
   texts have the same length, even if a message
   has to be re-sent.
  8) There is a strict limit on the size of each message.
   If the payload is longer, break it into multiple
   messages, each with its own IV.  Also note that
   shorter messages are better in case retransmission
   becomes necessary.
  9) When generating the IV, whenever one character
   is needed, use the dice to generate a /pair/ of
   characters.  The IV as transmitted contains the
   pairs (duly encrypted), but when the IV is used
   for initializing the machine, each pair is collapsed
   to a single character using a lookup table.  Here
   is what the lookup table might look like for a 
   five-letter alphabet;  you can readily generalize
   it to the full alphabet:

           A  B  C  D  E
       A:  e  b  b  d  d
       B:  a  d  e  c  e
       C:  a  a  d  c  a
       D:  b  c  c  d  e
       E:  c  a  b  b  e

   That is, the bigraph (row,column) = (A, E) maps to
   the single character "d" in the upper-right corner
   of the table.  This makes it very much harder for
   the cryptanalyst to recognize related keys.  (This
   is an elaboration of the way the Naval enigma IVs 
   were handled.)
 10) The IV is encrypted /once/ using the key of the 
   day.  Then for redundancy, the encrypted version is
   transmitted twice.  The *exact same* ciphertext is 
   transmitted twice.  Let's be clear: the IV is not 
   encrypted twice;  it is encrypted only once and 
   transmitted twice.  
     (Otherwise the first encryption would serve as
      depth for cracking the second.)
 11) Test messages MUST consist solely of nulls;  not
  German proverbs;  not dirty jokes;  not 200 copies
  of the letter "L".  Validity is ensured by re-using
  the first null as the last;  due to chaining, this
  won't come through correctly unless all the rest
  is correct.

======================

Although the Allies could afford to build Bletchley Park,
they could not afford to build a million Bletchley Parks,
or even a thousand.

Expanding the key space by a factor of a million, and
hardening the IVs by even more than that, would make
the rotor machine secure for the duration of the war,
and for several years more than that.

=====================

This becomes a spy thriller as follows:  A couple of
Abwehr cryptanalysts are given a captured M-209 and
discover that it is (just barely) breakable.  They
put 2 and 2 together and figure that the Enigma must
be far more breakable.  They come up with a proposal
for a much stronger machine.

The Abwehr is thoroughly penetrated by people who
hate Hitler.  They want to suppress the Plot Device
proposal.  They can't just kill the analysts, because
that would just attract attention.  They have to
discredit them first........