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

[Jon Callas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


On Jan 4, 2015, at 3:56 PM, Henry Baker <hbaker1 at pipeline.com> wrote:

> Since The Imitation Game is playing & is quite likely to win some awards, I was wondering if anyone has written an analysis of the Enigma & Lorenz encryption systems using 2015 eyes?
> 
> What would be required to "fix" these codes for modern usage, e.g., converting the mechanical bits into software, adding more wheels, etc. ?

Here's a quick bit of commentary.

The Lorentz machine is surprisingly good. Architecturally, it uses the same stream cipher structure we use to this day -- you set up a PRNG, XOR it on to the plain text, and poof, you're done. Its flaws are the same ones you see today -- the PRNG isn't quite good enough. The final nails in the coffin of RC4 that we saw a year ago are surprisingly similar to the thing that killed Lorentz. Lorentz is so good that they had to invent a computer to break it.

Engima is also much better than people give it credit for. It has the flaw that you can't encrypt a letter to itself, and this gives the cryptanalyst a huge jump on the game. From modern eyes, that's a fatal flaw and we can move on now because it's toast. Note that the Bombes were not full-fledged computers. But it's still a lot better than it's typically given credit for. Variants of the Enigma were used up until the early-to-mid-1990s, with the eleven rotor NEMA. It's also worth noting that the whole CRYPTO AG scandal was over these variant Enigmas.

The real problems were in key management and use protocols.

There was no good way to use a key per message in those days, so there was typically a key-of-the-day that all messages of that day used. That's the real downfall of both systems, because you now get a lot of places for there to be known plaintext. Known plaintext with repeated messages in stream ciphers is bad because it allows you to propagate what you know in one message to another. Since all messages were broadcast-encrypted (permit me that term) as opposed to point-to-point-encrypted (I'm trying not to say end-to-end as that's a modern term with context), it's the *system* that falls apart before the crypto does.

The Enigma protocols had the start of a message start with a three-character marker that's repeated twice ("ABC" || "ABC") and oh, by the way, that's the encryption key. With modern eyes, this moves you from "surprisingly good" to "facepalm" in one easy step. Since Enigma was used for trivial traffic, things like weather reports start being sources of known plaintext (they called them "cribs" in those days) as well as ways to collate and file all the messages encrypted with a certain key. When you throw the fact that a letter can't be encrypted onto itself with all of that, you get -- the Bombe, and the whole Enigma cryptanalysis program.

- From modern eyes, both machines have keyspace that's way too small. That's why NEMA went up to eleven rotors. One might speculate that in those days they kept the Enigma design because it was easier for the likes of NSA and GCHQ to cryptanalyze it as opposed to the essentially-modern design of Lorentz, which could be improved by a better PRNG. It's a pretty speculation, but it's just a speculation. I have my opinions, but they're just opinions.

It's really hard to get a stream cipher that's hard to crack with physical devices as opposed to bits. I'd say that's the biggest thing to answer your question with. This is the computer age, and let's use the fact that a computer is a machine that doesn't have physical constraints like you'd get with rotors or whatever.

Let's go back and consider RC4 for a moment, which is one of my favorite ciphers in the world. Despite it being broken, it is one of the prettiest, most elegant ciphers ever done.

You can consider RC4 to be a single self-modifying rotor. Imagine if you will, a rotor that has in each position a Scrabble tile. You do a little math based on the tile that are the contents of two slots, swap two tiles, and then output a result. Then you advance the rotor. 

Not only is it an algorithmic beauty, but as an intellectual bridge between the age of machine crypto into the age of computer crypto it's just drop-dead gorgeous. It would be really, really difficult to make a physical version of RC4, but you could. As software, though, it's a paragraph. Even the new, improved RC4 (I'm forgetting its name) is barely more complex.

The biggest problem with any rotor design is that you only get a character per click of the rotor. Or perhaps I should restate that and say that the "chunk" you encrypt is by necessity small. It is much harder to make a rotor with 100 clicks as opposed to 30. Modern ciphers get much of their strength from encrypting blocks -- to the point that these days you're seeing stream ciphers being better when constructed from a block cipher in counter mode. Block ciphers are software machines, not physical ones.

If you go further and look at a tweakable block cipher, you get even better stuff. I'm one of the co-authors of Threefish, and let's look at that for a moment. It has a large block size -- 512 or 1024 bits (I'm ignoring the 256 bit one) -- and runs at twice the speed of AES *because* it has a larger block size. In fact, the 1024 bit variant runs slower on an Intel processor than 512 only because the processor doesn't have enough registers to hold the state -- and even then, it's only like 10% slower.

The tweak lets you get over a lot of the problems with nonces, counters, IVs, etc. A tweak is a formalization of those ideas. The large block size means that you get less known plaintext. Look at an XML file, and its header is larger than the block size of AES. You start out with the same *issue* as with Enigma, albeit with a much better system. I call it an issue intentionally. I don't imagine it being a problem, but if you can fix it, it's worth fixing.

Large block ciphers are a good thing, for these old reasons. 

But anyway, summing up, those cryptosystems fell down more because they were systems rather than ciphers. Enigma+DH may not have been seriously broken. Lorentz had a PRNG problem and likely would have fallen anyway. An Enigma break with DH supporting it would have been different.

	Jon


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.3.0 (Build 9060)
Charset: us-ascii

wsBVAwUBVKrzVPD9H+HfsTZWAQhOGQf/dnnkw9VD9CoMJJQh+2D7vTszEzF8amuS
we+495tlQ8L25iQhzL1+qKQWeFRMIFF4piAXEFZsI31JpDYnd6QmhVL0Ol/DZg8c
uzX+UB0vBhDm9tlwXyWj1tzDwl6J1VT7SN8PKxndl6DGyoch2NrT/qZXSv718tL1
Rx6iEv34q3CpFqb1J5MaDLZlNkKK0iSPa+6sHso1CigBTQdrMv0nxq9Htk0UIK66
LuamrRneps1J11ONU1D10vIGsN/raYTQWb7PtIVjBz1uw2s6PLwpWZutNbRehK0u
Yl9BZYi3vq+20eDX857g0vsOjqME00axt1eGDXTOzfR9fNACgT3AkQ==
=ONcb
-----END PGP SIGNATURE-----