[Cryptography] retro crypto

[John Denker]

On 1/7/20 8:02 PM, Ray Dillinger wrote:

> The problem with rotor machines in general isn't that they're
> insecure.  Although many of the early ones were insecure, that's not
> endemic to rotor machines as a class.  In fact, as they run on systems
> that are known with absolute certainty to NOT be running any kind of
> malware or spyware (because they can't), they can arguably be even more
> secure than modern ciphers.
> 
> The *real* problem with rotor machines is that if you try to operate
> them fast enough to manage an internet data link, they explode. Random
> explosions, sadly, aren't really a feature consistent with the
> harmonious operation of modern office environments. For starters you
> have to explain to OSHA. 
> 
> I happen to have a soft spot for rotor machines in my heart, but I
> don't mistake them for a viable alternative to modern ciphers for data
> communication.  Written correspondence is pretty much the limit of
> their applicable domain. 
> 
> I will have a look at the shift-register machines.

Using 1970s technology, you can build a cipher machine on
rotor-like principles.  It has the virtue of "not running
any kind of malware because it can't".

For example:  Use LFSRs (linear feedback shift registers)
to drive the address lines on a bunch of EPROMs.  XOR the
EEPROM outputs.

Discussion:  If you use a LFSR directly, as a stream cipher,
it is straightforward to ascertain the current state, whereupon
you can predict the future state for all time.  But if you
muddy it up using an EPROM (as a form of S-box) then that's
not so easy.

By EPROM I mean something like a 27c1001:
  https://www.nteinc.com/specs/27C/pdf/nte27c1001.pdf
It is organized as 128k of 8-bit bytes.  You can easily
program all the bits yourself, so the manufacturer does
not know.  It has 17 bits of address.  The cost is a
few bucks per chip.

You can easily build LFSRs out of SSI (small-scale ICs)
to drive the address lines.  In particular, you can use
counters with the following periods:
1: 2**19 - 1		    (could drive 4 EPROMS)
2: 2**17 - 1
3: 2**13 - 1,  2**4 - 1	    (two LFSRs drive one EPROM)
4: 2**11 - 1,  2**6 - 1	    (ditto)
5: 2**10 - 1,  2**7 - 1	    (ditto)
6: 2**17		    (binary counter, not LFSR)

Conceptually this is just a rotor machine with 6 rotors,
but the rotors are electronic.  Each rotor has a period
on the order of 2**17, which is rather long ... and
every rotor moves a lot at every step.

This is sorta like a SIGABA in the sense that a PRNG is
used to control the stepping of the rotors.

The 6-rotor version has a combined period of 1 × 10²⁴.
It's slightly smaller than the simple product, because
the factors are almost but not quite all relatively
prime.

Initialize the counters according to the session key.
That gives 96 bits of key.

EPROMs have the advantage that when they go out of
date (or if you think you're about to be captured)
you can erase them.  This provides forward secrecy.

Such a device could operate at a rate of many megabytes
per second.

The device is open to related-key attacks, but the
key space is big enough to make that difficult, and
there are tricks for making it even more difficult.
There are a few weak keys, involving long strings
of consecutive zero bits, but they are trivial to
detect and defend against.

This is not mathematically secure by modern standards,
but it is probably at the point of diminishing returns,
in the sense that it is more secure than many other
elements in the system (such as whatever device you
used to type up the plaintext).