German Cryptanalytic Attacks on the British World War II “TYPEX” Machine | Hacker News Reader

German Cryptanalytic Attacks on the British World War II “TYPEX” Machine

cs.columbia.edu

73 pointssohkamyung19 comments

This is nice to see because I've always found it surprisingly difficult to get any information whatsoever on the German efforts in WWII.

Generally rotar machines were used a lot before WWII by banks and such. The Enigma and Typex were much more difficult to crack than commercial products because of the plugboard, while commercial machines only had spinning rotors. I think the Typex didn't have the weakness that letter x encrypts to x either. The Germans basically concluded that it was even tougher than the unbreakable Enigma so gave up.

Germany also had little success because, unlike in Bletchley Park, they didn't exactly tolerate eccentric academic types. The codebreaking efforts of the Germans were also so incredibly fragmented across different departments that once two different departments had a bust up on the street.

Wikipedia has some good references: https://en.wikipedia.org/wiki/German_code_breaking_in_World_...

That and they brutality exterminated many of their most talented mathematicians.

> The codebreaking efforts of the Germans were also so incredibly fragmented across different departments that once two different departments had a bust up on the street.

Hitler also systematically embedded a divide and conquer principle in organizations. Basically all institutions were duplicated to have them compete against each other instead of potentially forming an opposition against Hitler.

USSR did the same thing. Pretty sure it was done to promote competition and not for divide and conquer. Secret police was more than enough to handle dissidents. Hitler and his party actually had a lot of support because most of the bad stuff they did was hidden from the people or justified super hard through propaganda. And as bad as the Nazis were overall they still managed to have major successes in economy and science.

>And as bad as the Nazis were overall they still managed to have major successes in economy and science.

They weren't actually succeeding economically. They simply racked up internal debt, stopped paying their foreign debt, and invaded Europe in order to plunder it's riches and resources.

They had been plummetting toward economic collapse.

They knew they weren't ready to defeat the UK militarily, knew their technology wasn't properly built up yet, and actually didn't anticipate their own early military successes in mainland Europe.

But they had no choice. Fascism itself had backed Hitler into a corner. It was invasion or abdication (which was unimaginable).

> Germany also had little success because, unlike in Bletchley Park, they didn't exactly tolerate eccentric academic types.

Would Konrad Zuse qualify? If so the allies were pretty lucky he wasn't born a few years earlier.

It was the fact that a letter could never encrypt to itself that was, perhaps, the single biggest fault of the Enigma. In routine messages, the position of expected or candidate plaintext could be inferred from a lack of correlation of any characters, and any candidate plugboard configurations that forced auto-mapping could be immediately discarded. (Rotor choices, particularly the right-hand wheel, could be determined statistically, leaving the ring settings and plugboard configuration as the tedious, time-consuming bit.)

Interesting conjecture at the end; GCHQ retained two Colossus machines until the 1970's. The Russians knew that Colossus existed and GCHQ knew that the Russians knew. Why retain Colossus - people tend to say that it was because there were networks of rotor machines in use in less sophisticated countries, but given the us or them nature of the cold war it seems unlikely that there was sufficient value in retaining them through the 50's. My guess is that there was some sort of elaborate counter bluff played out with the Soviets; that they believed that the Brits thought that they were unaware of Colossus and so would be duped by traffic sent over rotor networks... but what was in it for the Brits?

Maybe because the Russians didn't know that GCHQ knew that the Russians knew that GCHQ had Colossus!

Could be...

Sounds like the plot from Cryptonomicon.

Colossus was used to break Tunny (encrypted teleprinter traffic) and, as far as I can deduce (despite that machine also using rotors of an entirely different kind) was useless in analysing Enigma-type traffic. The desire to hide the achievements of Colossus at Bletchley Park was an (apparently successful) attempt to goad the Soviet Union into adopting similar cipher systems after the war so that the same techniques could be applied by the Western powers to read Soviet signals. The ruse largely worked.

Yes! This is so important and yet so often not understood even by people who've supposedly been to Bletchley where they spell it out pretty clearly in their museum.

Tunny (the German thought of this as "Lorenz" because that was the manufacturer name) is an actual stream cipher, more or less. It's making pseudo-random bits and XORing them with plaintext to produce a ciperhtext. The plaintext is Baudot code rather than, say, ASCII, but it's definitely bits. Lorenz is doing this in (by modern standards) a ludicrously mechanical steampunk-looking way, but that's what it's doing. Even though to our modern eyes it looks not so different from Enigma in terms of the principle of operation it's entirely different and radically more like how things would be done decades later.

Salsa20 and ChaCha are modern stream ciphers, they're designed for modern binary computers rather than a mechanical contraption, but the core underlying principles are the same as Lorenz. If you can make a lot of "random-looking" bits from a small key you can XOR them with your plain input to produce a ciphertext, nobody can decipher it without knowing the key in order to generate the same "random" bits.

Most cryptosystems you use today have block ciphers inside them, which work quite differently, but some will have a stream cipher, a descendent of Lorenz inside them - spiting out "random-looking" bits.

Thank you for this excellent explanation of stream ciphers.

Yeah, the efforts of Bill Tutte and Tommy Flowers to break the Lorenz were amazing. People only remember Turing, but there are plenty of forgotten heroes in Bletchley who never got the recognition they deserve.

Bill Tutte is a local hero here in Waterloo. He was already an extremly respected professor of the math faculty, but since the moratorium on secrets at Bletchley has been lifted he has been inducted into the Order of Canada and had a street named after him, among other honours.

It is sad the revelation of his involvement came so close to the end of his life. He certainly deserved much more recognition.

There are ways to use a block cypher as a stream cypher for example by using it with a CTR mode.

Or think of it in this way...

One-time pad is the simplest, yet secure symmetric encryption algorithm, i.e, you have a 128-byte plaintext, you can take a 128-byte random string from your one-time pad, XOR it with your plaintext to encrypt it. As long as the random string is not shorter than the plaintext and not reused, the encryption is information-theoretic secure.

However, an one-time pad is often too problematic to be practical. First, the one-time pad has a large size (it needs to be larger the entire plaintext you want to encrypt), which is difficult to be stored and shared securely, also, the one-time pad needs to be created from a physical process, which takes time.

But if you have an algorithm to generate random number, you can just initialize it with a random seed, then the it starts to produce random strings of indefinite length, which can be used to create an one-time pad. Since the RNG algorithm is deterministic, only the short seed is needed to be shared between Alice and Bob. Subsequently, they can create their own copies of the identical one-time pad by running the algorithm with the same random seed.

Now, the one-time pad encryption algorithm is still the same one, the only difference is the pad is generated from a software random number generator, instead of a true random process. Therefore, the security of the encryption is reduced to the security properties of the random number generator. If the RNG is completely unpredictable and cryptographically secure (aka CSPRNG), it would be as good as true random strings.

You can take the step further, wrap the CSPRNG and the XOR function in a blackbox, call the blackbox a "cipher", and call the random seed of this CSPRNG as the "key", you've just created a "stream cipher".

In other words, the core of a stream cipher is a CSPRNG, which is used as an approximation of one-time pad. Historically, RC4, and now ChaCha, is widely used for both purposes.

When the CSPRNG does not produce uniformly-distributed random strings, bad things happen. RC4 is weak because of the existence of multiple types of biases in its random stream, same bytes appear more often that others.

If you traveled 300 years back in time, the first thing you would need to work on is a CSPRNG. When you have one, a strong stream cipher naturally appears. Luckily, you can make a random number generator from various forms of common permutations, like a deck of cards. https://en.wikipedia.org/wiki/Solitaire_(cipher) If you use this algorithm, your communication would be safe for 100 years, as the cryptanalysis tools required to exploit the bias didn't exist from that time. Or even better, use the LC4 cipher, https://news.ycombinator.com/item?id=16586257, which the random number generator can be obtained by making a simple toy.

But the Soviets knew that Tunny was broken, because Cairncross passed it to them, GCHQ knew this. The Russians weren't stupid - it was very clear that the Brits could read SS cipher traffic, the SS used Lorenz. I have read (but can't find it) that the Soviets used captured Lorenz.. but it is odd.

Reply on news.ycombinator.com