A historical look at decrypting the Enigma

[Vanadium 50]

TL;DR Summary

Why did the Enigma decryption take the path that it did, as opposed to a different one?

I've been thinking about the German Enigma machine, and how it might have been analyzed in a more modern perspective, without using attacks using known (or guessed) plaintext.

My understanding how the Engima worked is as follows: there are 3 (sometimes 4) rotars, each with 26 letters A-Z marked on it. Each rotar has one of several rings attactched to it, and each ring performs a simpler substitution cipher. As each letter is encrypted, the rings are advanced (AAA, AAB, AAC...ABA, ABB...BAA< BAB...) so the whole thing is a giant substitution cipher with period 26³ or 17576. At the end there is a plugboard, which does another simple substitution cipher, and a reflector sending the message back through teh system: so messages are encrypted by Ring 1, Ring 2, Ring 3, Plugboard, Ring 3, Ring 2 and Ring 1.

The initial rotor position was sent in cleartext at the start of each message - the idea was to spread messages evenly over the the 175786 period to make cryptanalysis harder.

The Germans assumed (more or less correctly) that the Allies had Enigmas, but did not have the daily code settings.

If I have this substantially wrong, please correct me.

Given this, an ahistorical means of attack would be as follows:

(1) Two simple substitution ciphers in series is equivalent to one simple substitution cipher. If A encrypts to Q, it doesn't matter if iut goes via H and T and K first. So the whole complicated process can be turned into a ring set selection, a ring set initial position, and a substitution cipher.

(2) Simple substitution ciphers are easy to decrypt via frequency analysis. If we decrypt it to the point where we are left with a Simple substitution cipher, we're done.

(3) What's left is not too bad: ~10² ring choices and ~10⁴ settings, so we're talking a few 10⁶ possibilities. You would essentially try all the possibilities looking for repeated letters: it takes a shockingly short time for English (or German) to repeat a letter: 4-6 letters in my unscientific look at random bits of text. (And about 8 for gibberish) Counting the rate of multiple letters would be a good metric to see that the ring choice is right.

That seems to be in the possibility for an exhaustive search with 1940's era technology. A few machines running fgor a few hours could break the code in a day or less. All electronic - not electromechanical.

I suspect the fastest solution is progressive - drop 90% of the permutations quickly, then spend 10x as much time on the remaining ones, etc.

I'm sort of curious why things didn't work this was. Is my analysis flawed? Is it that the observation that multiple simples substitutions are equivalent to one? (The Enigma sure depended on these) Is it that the idea you could build an all-electronic solution too new? Or that you could brute-force it with existing technology?

 

[jedishrfu]

I would compare the enigma to a boot of cards at the casino. With a single deck of cards, a card counter can easily estimate the probabilities, but with six decks shuffled together, it was much harder.

With respect to Enigma, several rotors could be installed. The Germans had a schedule set up for what rotors were to be used, what rotor order and what passcodes were to start messages.

Weaknesses in what the Germans chose for passcodes allowed Allied code breakers to guess the passcode (one operator used "Hitler," and another used his girlfriend's name). In one case, there was a screwup in the sent message, so the operator sent the same message in the clear, giving the silent Allied listeners a great gift for decoding future messages.

https://www.theguardian.com/technology/2014/nov/14/how-did-enigma-machine-work-imitation-game

Inside the box, the system is built around three physical rotors. Each takes in a letter and outputs it as a different one. That letter passes through all three rotors, bounces off a “reflector” at the end, and passes back through all three rotors in the other direction.

The board lights up to show the encrypted output, and the first of the three rotors clicks around one position – changing the output even if the second letter input is the same as the first one.

When the first rotor has turned through all 26 positions, the second rotor clicks around, and when that’s made it around all the way, the third does the same, leading to more than 17,000 different combinations before the encryption process repeats itself. Adding to the scrambling was a plugboard, sitting between the main rotors and the input and output, which swapped pairs of letters. In the earliest machines, up to six pairs could be swapped in that way; later models pushed it to 10, and added a fourth rotor.

","alt":"Enigma machine: how it worked","index":5,"isTracking":false,"isMainMedia":false}" style="max-width: 680px;">
Despite the complexity, all the operators needed was information about the starting position and order of the three rotors, plus the positions of the plugs in the board. From there, decoding is as simple as typing the cypher text back into the machine. Thanks to the reflector, decoding was the same as encoding the text, but in reverse.

But that reflector also led to the flaw in Enigma and the basis on which all codebreaking efforts were founded: no letter would ever be encoded as itself. With that knowledge, as well as an educated guess at what might be encrypted in some of the messages (common phrases included “Keine besonderen Ereignisse”, or “nothing to report” and “An die Gruppe”, or “to the group”), it was possible to eliminate thousands of potential rotor positions.

Wikipedia has a good summary of the machine here:

https://en.wikipedia.org/wiki/Enigma_machine

and Youtube has several videos with this one from Simon Singh:



I think the problem in decrypting then is running all variations of rotor order and rotor starting positions with variations of the passcodes to see if you get a viable message out in german at the end. The mechanical components would have a limited speed in the bombe of operation as well to prevent jamming or shearing of rotor gearing. Basically, it would take a lot of time to solve it.

 

[Vanadium 50]

Weaknesses in what the Germans chose for passcodes

Another one was that, at least until they knew better, the initial rotor order was sent twice, once unencrypted and once encrypted. So if you got ABCQWE, you knew the plaintext for letters 4,5, and 6. That removed a large number of cases.

Or my favorite - to foil traffic analysis, some stations transmitted constantly. One message was a zillion letters long without a single L. (I think it was L, although it doesn't matter) Since the Enigma never encrypts a letter to itself, this meant the plaintext was nothing but L's.

But my question is a little different. Historically it was cracked by, as you say, knowing (or guessing) the corresponding plaintext and using that. My question is why a brute-force attack wasn't chosen instead. It seems tractable by 1940's technology, if just barely.

 

[jedishrfu]

Yes, I don't think a brute-force attack was feasible, considering the rate of change of passcodes and rotors and the sheer amount of possible combinations. Simon Singh mentions some other Enigma adjustments that extend the range of the device to millions of possibilities.

Numberphile gets into that, along with the possible number combos:



The video has links to other Enigma numberphile content.

 

[jedishrfu]

Here's Grimes discussion with some combinatorial stats:

 

[Vanadium 50]

So for the Enigma variant they chose, they have 60 rotor choices, 26!/10! plugboard combinations (which is wrong, because they could use fewer than all 10 plugboard combinations, but we'll go wityyh it for now). In this version, apparently the ring is fixed on the rotors - he didn't mention that setting. They get some very high number of possibilities.

BUT the plugboard combinations are just simple substitution ciphers, and that is vulnerable to a frequency analysis. So it's actually just 60 rotor choices. You could break this by hand.

Agree?

 

[jedishrfu]

I'm not really qualified to comment on it. I mean if I only got an encoded text, it would be really difficult to break it in a timely fashion. I think that is the real question.

Can blunt force break it before the message goes stale? I say no otherwise, they would have done it that way, but honestly, I just don't know.

 

[Vanadium 50]

If the Enigma worked as described, brute force is trying 60 combinations to find the one that yields a non-uniform letter distribution, and once you had that you have the sort of substitution cipher, which was broken in the 9th century.

 

[Vanadium 50]

Maybe this helps. One of these is a famous sentence in German through a simple substitution cipher. Another is a set of random letters. Even without knowing the plaintext, I think you can tell which is which:

AAB CDE FGH IJK LHM FK
ABC DAE FAE DFH IAE FH

If it helps, the first has 4 pairs of duplicate letters and the latter 14. Or, if you like, the first has 13 unique letters out of 17 total. The latter has 9.

In English it takes only about 30 letters to break a substitution cipher. German can't be too different.

PS I thought the title was supposed to be A-historical. Or maybe an-historical.

 

[jedishrfu]

You had both An A Historical, and so I edited it, picking the "A."

so the rule apparently is if the "h" is pronounced to use "A" and if silent then "An":
- an heir to the empire
- a historical event
- I'll be there in an hour
- a helicopter will pick you up.

https://www.thefreedictionary.com/A...=Is it an historical study,: a one-room house.

 

[jedishrfu]

Your theory would make a good movie plot. A Scientist transported back in time uses the blunt force method to crack Enigma only to be caught by the SS before he reveals the method to the Allies, never seen again.

 

[Baluncore]

Why did the Enigma decryption take the path that it did, as opposed to a different one?

That seems to be in the possibility for an exhaustive search with 1940's era technology. A few machines running fgor a few hours could break the code in a day or less. All electronic - not electromechanical.

Enigma was a commercial system in 1931. The security of the military version was then improved by step-wise refinement, a big mistake by Germany, but certainly not their biggest. The three Polish cryptanalysts, headed by Rejewski, climbed the steps of that refinement ladder, remaining in touch until 1939. The Poles then handed the solution to France and to Britain, complete with their duplicate Enigma machines and the plans of their electromechanical Bomba, which became the British Bombe. Everything then used or developed to read Enigma by Britain, was passed on to the USA, where it was partially duplicated at a secure location, a girls school in Washington DC.

Alan Turing was a mathematician. When he started at Bletchly in 1939, he could not follow the Enigma decryption process, so he went to Paris where, among others, he attended a meeting with the Polish cryptanalysts, who explained again the cryptanalytic process for Enigma. The Poles were not impressed by Turing, who was more interested in the toxicology of the flowers on the dinner table. Turing explained that the irrational 8.47 mm squared graph-paper used by the British cryptanalysts, was based on the convenient Barleycorn unit.
Many people credit Turing with breaking Enigma, because they did not know, or could not discuss the high level international cooperation. Turing died in 1954, then later, in the 1970s, when the Enigma story broke, they could say “Turing told me that … ” which deflected the official secrets act, and blamed it on a homosexual. “The Imitation Game” movie is a fiction that denies the extremely tight security, and wrongly attributes the work of many others.

Electronics were not used to break Enigma during WWII. At no point could the cryptanalysts have stepped off the mechanical ladder, to start afresh with a future technology, so Enigma was all done with electromechanical switches. Ordinary tactical Enigma was not sufficiently important to justify electronics. The more complex naval Enigma, used by U-boats, was important during the battle of the Atlantic, so the settings were several times taken from the enemy, one technique of many described as “practical cryptanalysis”.

The greatest information value was in the strategic, high level German Fish messages, that were broken statistically, electronically, by Colossus. There were about a dozen Colossi working at the end of WWII. The first statistical electronic code breaking was of the Fish, 5 bit teletype rotor machines, done by Colossus at Bletchley.
It looks like there may have been international cooperation with that. Beurling in Sweden originally broke the German teletype cipher and had ongoing access to the traffic on wires from Berlin, through Stockholm to Oslo, and to some plain text delivered to the Swedish foreign office. Sweden employed the information gained to remain “neutral”.

Sweden had great ongoing success without a local Colossus, but there was a “diplomatic” nightly Mosquito return flight, between Britain and Sweden that may have carried paper tape, (along with SKF ball bearings), while the solved keys could have been returned by radio, encrypted by one-time pad. There are no reports of Britain originally cracking the Fish systems, but they must have got the solution from somewhere.

The Red and Purple Japanese diplomatic teletype ciphers were broken by Friedman in the USA. They were similar to the German Fish systems. Rotor machines, Sigaba (US) and Typex (UK) were modified to emulate the Japanese and German machines for reading decrypts.

To sum it all up from my viewpoint, reading between many lines;

Marian Rejewski in Poland broke the German Enigma, (NOT Turing).
https://en.wikipedia.org/wiki/Marian_Rejewski

Arne Beurling in Sweden, broke the German Lorenz (Fish) system.
https://en.wikipedia.org/wiki/Arne_Beurling

William Friedman in the US broke the Japanese Red and Purple ciphers.
https://en.wikipedia.org/wiki/Type_B_Cipher_Machine

Britain broke no new cipher system of importance, but maintained exceptional Ultra security, while creating the first electronic tools, and building international cooperation.

 

[Vanadium 50]

a big mistake by Germany, but certainly not their biggest

Never get involved in a land war in Asia?

 

[jedishrfu]

They should have talked to Napoleon.

 

[Vanadium 50]

At no point could the cryptanalysts have stepped off the mechanical ladder

But why not? That's the question.

Mechanical computation speeds are of order 10 Hz. Contemporary electronic speeds were of order 10 kHz. So there's a factor of 1000. That's enough, more or less, to Brute-force the Army Enigma. The Naval enigma was, of course almost 2 orders of magnitude harder, but that would make this approach more desirable, rather than less?

It wouldn't have to be general purpose - it's not executing an arbitrary program. It's executing only the one.

 

[Baluncore]

Never get involved in a land war in Asia?

Starting any war by invading a neighbour is a massive mistake. By all means seduce them, trade with them, play football and make deprecating jokes, but not war.

The failure of the Luftwaffe to persist in the Battle of Britain, for just a couple of more days in 1940, resulted in the survival of fortress Britain. That opened another front for Germany when it attacked the Soviet Union. Instead of focussing its forces on one small island, it spread its forces over the longest front line in the East, while still building the Atlantic Wall defences in the West. The outcome of the Battle of Britain therefore became a nexus, through which very many threads of European history have flowed, including D-Day, the NATO of today and the defence of Ukraine right now.

But why not? That's the question.

Never change horses in midstream.

It is easy to be wise after the event, but at the time there were very few engineers capable of creating the vision of such a new electronic technology, and they were all heavily invested in RADAR development, or building a Colossus to crack Fish.

Reliability comes from using a technology that has been around for 10 years. Vacuum tube electronics were seen as unreliable at the time, mainly because people kept turning the power to their radio on, and then off again, to save the batteries. We now know that electronics should be turned off and then on again, but only when it gets its knickers in a knot.

Cipher systems evolve through punctuated equilibrium. There is a good chance that everything will be changed by next year, if not at the end of this month. The existing code sheets and mechanical systems for reading Enigma did the job. Those mechanical systems would not work for Fish, so the new electronics technology needed to be applied to Fish, not Enigma.

Perfection is the enemy of progress. Robert Watson-Watt's "cult of the imperfect" says; Give them the third best to get on with now, we are working on the second best, perfection never comes. No matter what you do, by definition you must always be using the third best. Whenever the music stops, the technology must always be what was third best at that time.

Everyone did the best they could under the circumstances, and that was the way the cookie crumbled. There is little point in looking back and imagining "what if" when you should be looking forwards, because that is the way you are going now.

 

[anorlunda]

Elizabeth Friedman and her team at the US Coast Guard independently cracked Enigma without use of computers and without the intercepts that Turing used. She sent an envoy to Bletchly Park to inform them, but they said we already did it.

See the book "The Woman Who Cracked Codes"

https://en.m.wikipedia.org/wiki/Elizebeth_Smith_Friedman

So @Vanadium 50 , the cracking was plural with a plurality of methods. But still, the question is a great one.

 

[Vanadium 50]

he cracking was plural with a plurality of methods.

But one method was not "brute force with electronics". I'm still curious was to why not. Reliability, as @Baluncore suggests was an issue. But Eniac appeared only a few months after the war, and it had 18000 vacuum tubes. To compare, the 8080 had 4500 transistors, and I believe that it is far, far more powerful than necessary to do what I describe. Could you do this with 10% of the tubes of Eniac? 20%? Whatever the factor is, it would be that much m,ore reliable.

And of course, tubes were used in all sorts of military applications. Ever see those vintage "portable" two-way radios? So if this was an aversion to tubes, it didn't last much longer.

 

[Vanadium 50]

Never get involved in a land war in Asia?

For those who didn't get it...

 

[anorlunda]

But one method was not "brute force with electronics". I'm still curious was to why not.

That book, "The Woman Who Smashed Codes" makes it sound like it was sexism that determined the method.

William and Elizabeth Friedman were husband and wife, and also both code cracking wizards. The book hints that Elizabeth was the stronger genius of the two, but we'll never know for sure. William was recruited into the OSS and the CIA, and his name is honored on the wall at CIA headquarters, histories, awards, and fame. CIA had the money and electronics. But Elizabeth was sent to the US Coast Guard. She had no computers, and only a tiny budget, yet she and her team did much of the successful US cracking during the war. She fed the results to J Edgar Hoover at the FBI. Hoover falsely claimed that it was the FBI that should get the credit, so he too hid Elizabeth's contributions.

Elizabeth's team did it with pencil and paper. The team was immensely successful during WWII against Nazi, and North/South American spies. But the did little in the Pacific/Japanese theater.

We can never know what secrets William and Elizabeth shared in the marital bed.

The book makes a fascinating story, extending from WW1 to the 1960s.

 

[Baluncore]

Reliability, as Baluncore suggests was an issue.

No. Reliability was wrongly thought to be an issue. It was found that if the equipment was operated continuously, under conservative stress levels, that reliability was greatly improved.

Just as RADAR stimulated radio astronomy, experience with Colossus stimulated an explosion of people interested in electronic computers. That was true in the UK and in the US, as secure reports of Colossus reached the US. Like Colossus, early computers were based on AC coupled coincident pulses, not DC logic states. It took time for the fundamental concepts needed for binary digital computers to form, and so dispel the decimal thyratron ring pulse counters.

The organisation of GC&CS at Bletchley was secure. Most people knew what they needed to do, but were not told why. Couples met in the canteen, got married, and never discussed their different jobs, or the work of different huts. Someone with electronics skills cannot know what is needed if top management is hermetically secret. Only those who needed to know had any opportunity to make suggestions and educate management as to what might be possible. Tommy Flowers was in the right place at the right time.

There may well have been an electronic Bombe by 1946. The Enigma machines were collected at the end of the war. They were then handed out to Third World countries, where they were used for the next decade or so. The US and the UK had no trouble reading that Enigma traffic, until the Enigma story broke 20 years later.

We can never know what secrets William and Elizabeth shared in the marital bed.

At least one bedtime conversation has been reported. A cipher machine inventor submitted an encrypted text in the hope the US would buy the device. Said one to the other, I've found the word cipher dear, what do you think the next word might be? Machine possibly? Yes it is. The inventor was given the clear text back the next day, and the US did not purchase the device. (I think that might come from David Khan's book, The Codebreakers).

 

[Vanadium 50]

I still find it remarkable that at a time when electronic computers were emerging - the ABC machine was in 1942 - nobody thought to adapt them to decryption.

I am also starting to suspect that while the security of the repeated substitution was low, both sides considered it to be high. It doesn't seem that anyone considered that an output that isn't plaintext but just a simple substitution cipher was justy one quick step away from full decryption. Not the answer, but almost as good as the answer.

 

[anorlunda]

I am also starting to suspect that while the security of the repeated substitution was low, both sides considered it to be high

I'm not sure that is true. The book about Elizabeth Friedman discusses all the methods used up through WWII. Probably repeated substitution too.

The Friedmans wrote 5 pamphlets on cracking methods in the 1920s. The book says they are still classified today. So maybe we still don't know all of their paper and pencil strategies.

I also suspect that use of computers had to wait for a fresh generation schooled in computers. Their elders stuck with the decryption methods they learned in their own youth. That is still true today. Medical doctors especially are infamous for using only what they learned in medical school for their whole careers.

 

[pbuk]

BUT the plugboard combinations are just simple substitution ciphers, and that is vulnerable to a frequency analysis. So it's actually just 60 rotor choices. You could break this by hand.

Agree?

No, I don't agree. What are you going to do a frequency analysis on?

 

[Vanadium 50]

The output, trying all rotor positions.

With the rotors in the incorrect positions, the output text is random.
With the rotors in the correct positions, the output text has a non uniform frequency distribution.

Now you have a simple substitution cipher.

 

[Baluncore]

With the rotors in the correct positions, the output text has a non uniform frequency distribution.

I don't see how that follows.
The rotor internal wiring was not orderly. The order of the rotors in the stack, and the starting position, meant the scrambled output changed, which thwarted frequency analysis.

It was well known by the cryptanalysts that the stecker plug-board did not increase security by the factor assumed by the Germans. Most cryptanalytic techniques for Enigma looked straight through, and could ignore the stecker settings for the day.

Are you suggesting that there was a bigger hole in Enigma security, but that it was not seen because the cryptanalysts were blinded by the fundamental certainty with Enigma, that no letter could be enciphered as itself ?

Having an idea like that is quite common during familiarisation with any new encryption technique. While it is possible for there to be a hole in security, I suspect many experienced cryptanalysts and mathematicians have looked there before you, and realized that an attack from that approach was covered.

I would suggest you obtain, or write, an Enigma machine emulator. Then you can demonstrate the difference in frequency distribution that you expect.

 

[Vanadium 50]

I suspect many experienced cryptanalysts and mathematicians have looked there before you, and realized that an attack from that approach was covered.

I'm not sure that I buy this argument. What makes this different? I have 75 years of hindsight. Also, some of the modern descriptions (like the 2nd video) don't exactly match the real device, at least the common ones. They also emphasize the number of permutations, which is driven by the plugboard.

I would suggest you obtain, or write, an Enigma machine emulator

Looked at a few. They give different answers from each other, which doesn't exactly inspire confidence. Many do not distinguish between "rotor" and "ring", and at least as I understand it, these are separate.

Using the Wikipedia notation, the encryption transform is E=PRMLUL^{-1}M^{-1}R^{-1}P^{-1}. Let me group them together as such, and have it operate on a message x: E(x)=P(RMLUL^{-1}M^{-1}R^{-1})P^{-1}(x). Let me rewrite as E(x)=(P)(Q)(P^{-1})(x). So P is the plugboard, and Q is the effect of everything else.

If x has a non-uniform distribiution, P^{-1}x must as well. It's a simple substitution cipher, and easily translatable. The same argument applies to P operating on the output of Q. So the problem breaks into two pieces - figuring out what Q does and then inverting it, and then taking the output, a simple substitution cipher and solving that like people have done for a thousand years.

But Q has relatively few states, and is therefore a brute force attack is plausible. You have the rotor selection and order, the position of the ring on the rotor, and the initial position - which is given in plaintext. For using 3 out of 5 rotors, this is just over a million. Probably impractical for electromechanical calculators, but not for all-electronic ones.

 

[Baluncore]

They also emphasize the number of permutations, which is driven by the plugboard.

The plugboard steckers were there to make finding the correct wheel order, and the correct starting position, more difficult. If the total number of possible stecker permutations is emphasized, then the victim is being distracted by something irrelevant to the breaking of the cipher. That was a perpetual German security evaluation mistake. I think twice, an investigation into whether Enigma was being read by the allies, argued wrongly that the number of stecker permutations was so great that Enigma must be secure. The Germans preferred to believe that they had a traitor, or leaks from the organisational structure, external to Enigma. I read those allied reports on the German internal review about 5 years ago, but cannot now remember the reference. Maybe it will come to me.

 

[Drakkith]

I still find it remarkable that at a time when electronic computers were emerging - the ABC machine was in 1942 - nobody thought to adapt them to decryption.

Is this not exactly what Colossus was?
If you're asking why it didn't happen earlier or why it wasn't more widespread, I'd guess that it's a product of them being an emerging technology that very, very few people understood.

 

[pbuk]

With the rotors in the incorrect positions, the output text is random.
With the rotors in the correct positions, the output text has a non uniform frequency distribution.

No, that's not correct. Let's look at an example.

The plaintext is BALL and the secret settings yield the (partial) multiple substitution cipher:

A | B L Z G
B | A J D C
D | P E B L
J | S B L Z
L | M A J D

The ciphertext is therefore ALJD:

B | A
A |   L
L |     J
L |       D
--|--------
  | A L J D

Let's say we correctly guess the secret rotors, but do not know that in the secret plugboard the letters D and L are swapped. Our configuration therefore yields the cipher:

A | B D Z G
B | A J L C
D | M A J L
J | S B D Z
L | P E B D

and our candidate solution is BEDL:

A | B
L |   E
J |     D
D |       L
--|--------
  | B E D L

How does frequency analysis help us here? It doesn't of course, so how can we decipher this message?

The path to the answer starts with noticing that the ciphertext D has been correctly decrypted to L. Assuming the rotor settings are correct this can only happen if the plugboard settings for D and L are correct, or if they are transposed. The incorrect decryption of the third letter as a D instead of an L gives further information, so we connect D and L on our trial plugboard and the full plaintext is revealed!

You can try this out on a simulator e.g. https://www.101computing.net/enigma-machine-emulator/ with the default initial rotor setting AAA.

 

[Vanadium 50]

Using the emulator your link provided, I did the following:

1. Set everything to its defaults. Set the plugboard at QW+LM.
2. Emcrypted LLLLL LLLLL anbd got DYKOH CONOV. Multiple letters are obfuscated, good. A letter doesn't encrypt to itself. Good.
3. Decrypted DYKOH CONOV and got LLLLL LLLLL. Good. Double-encrypted DYKOH CONOV and got LLLLL LLLL. Good.
4. Undid the plugboard, and decrypted DYKOH CONOV.

I get MMMMM MMMMM, So this supports my contention - if you get the rotors and rings right - what I called Q above - and the plugboard wrong, you arr left with a simple substitution cipher.

Sure, I have no idea that M stands for L in this case, but if I had a real message, I could work it out with frequency analysis.

 

[Baluncore]

- if you get the rotors and rings right - what I called Q above - and the plugboard wrong, you arr left with a simple substitution cipher.

And that is exactly what happened at Bletchley. Once possible rotor settings had been found by the electromechanical search for probable words. The elimination of the limited number of steckers used on that day was a final trivial step, done by eye on the plain text. It was not necessary to search all possible permutations, yet the number of permutations was used in the German assessment of Enigma security.

 

[pbuk]

I get MMMMM MMMMM, So this supports my contention - if you get the rotors and rings right - what I called Q above - and the plugboard wrong, you arr left with a simple substitution cipher.

Sure, I have no idea that M stands for L in this case, but if I had a real message, I could work it out with frequency analysis.

No that's cheating - there's only one letter set on the plugboard that's doing anything. Here's something that's less contrived to support your fallacy:

• Set the plugboard to PE BD UC ON
• Encrypt LLLLL MMMMM -> EPDBC UNONV
• Clear the plugboard and you get
• EPDBC UNONV -> FHJCN PRQVM
• Unique letters - analyse that!

 

[pbuk]

Or if think that example is contrived in the other direction choose instead

• Set the plugboard to PB UK VA ND IM
• Encrypt LLLLL MMMMM -> BEPNK LBPJK
• Clear the plugboard and you get
• BEPNK LBPJK -> ALSSV IJWIB

 

[Vanadium 50]

Well, I can only say now I am complete;y confused. @Baluncore and @pbuk seem to be saying different things. Did it happen? Or is it impossible?

I will say there is a thin line between "contrived" and "the simplest example that shows the effect".

 

[pbuk]

Well, I can only say now I am complete;y confused. @Baluncore and @pbuk seem to be saying different things. Did it happen? Or is it impossible?

I don't think I am contradicting anything @Baluncore has said. In particular I completely agree with this:

It was well known by the cryptanalysts that the stecker plug-board did not increase security by the factor assumed by the Germans. Most cryptanalytic techniques for Enigma looked straight through, and could ignore the stecker settings for the day.

The article at https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma gives some reasonable indications of why this is the case.

So we can see that the methods that were actually used got around the variation introduced by the plugboard. That has no bearing on whether you can ignore the plugboard if you are try to brute force a solution: as we have seen above, you can't, and we find that brute force requires testing upwards of 150 trillion settings.

 

[Baluncore]

One problem with using electronics to emulate electromechanical rotor machines was the complexity of an electronic crossbar switch, capable of cyclically indexing an array of scrambled connections. That structure requires two electronic barrel rotators connected by the rotor internal wiring. The circuit would need to be duplicated, because the current passed through each rotor twice, in different directions. Vacuum tube electronics could not then run forwards and backwards at the same time. It could be done in the 1960s using FET analogue gates, or diode bridge sampler circuits. It is usually done by indexing an array in RAM with a counter.

Stephen Budiansky; Battle of Wits. The Complete Story of Codebreaking in World War II; Free Press (2000) Reports OP-20-G evaluating electronic Bombes in 1942.
“The U.S. Navy's all-electronic design would avoid all of these mechanical and electrical problems by using twenty thousand vacuum tubes in place of the rotating wheels and relays. But no one had ever tried anything like that before, and it was not even clear that so many tubes could be purchased or that a power supply could be built to handle such a huge load, so the Navy quickly shelved that plan and decided to blend the best of the two British designs, combining a complete four-wheel bombe with an electronic sensing device.”

 

[Baluncore]

That has no bearing on whether you can ignore the plugboard if you are try to brute force a solution: as we have seen above, you can't, and we find that brute force requires testing upwards of 150 trillion settings.

A cryptanalyst would not succeed with such a defeatist attitude. Cryptanalysts are not brutes, they are curious, cunning, and expert at the factorisation of complexity. They have a fixative "yes, can do" attitude to any problem. Cryptanalysts never fail, they just keep working until they find a solution.

It was the ability to factorise the composite Enigma, while ignoring the magnitude, that was essential to the design of the tools needed to break it down, to minimise the solution.

 

[pbuk]

A cryptanalyst would not succeed with such a defeatist attitude. Cryptanalysts are not brutes, they are curious, cunning, and expert at the factorisation of complexity. They have a fixative "yes, can do" attitude to any problem. Cryptanalysts never fail, they just keep working until they find a solution.

It was the ability to factorise the composite Enigma, while ignoring the magnitude, that was essential to the design of the tools needed to break it down, to minimise the solution.

Yes, that was my point, in contrast to @Vanadium 50's suggestion of brute forcing.

 

[Drakkith]

One problem with using electronics to emulate electromechanical rotor machines...

Baluncore's post here is an example of exactly what I was thinking. I tried typing up a whole post last night about the logistics and procurement of parts and knowledgeable people, but it was 3 am and I was too tired for my mind to work. With such new technology, acquiring the parts and people isn't a simple matter. It probably wasn't even immediately clear to the decoders themselves how to use this technology effectively. I mean, you can't even brute force decode a message unless you actually know a fair bit about how it was encrypted, which means you can't build a machine to do the brute forcing until after you've spent a significant amount of time and effort already. And being so new, everything had to be constructed from scratch or very nearly so. The machines themselves, the instructions on how to use them, the more general instructions on how computing machines work, how to apply them to code breaking, etc.

Asking why things happened at the pace that they did and not some other pace isn't an easy question to answer in a short forum post. The same question can be asked about any emerging technology, and the answers usually involve things like reliability, cost, potential applications, profitability, time and resources to build the required infrastructure that is itself needed to build, support, and expand the technology, scalability, ease of use, education and training of personnel, and many more.

Sometimes these technologies expand quickly, sometimes they don't. Although, perhaps ironically for this thread, I would guess that the codebreaking effort of WW2 sped the development and adoption of fully electronic digital computers by about a decade. Colossus was literally the first fully programmable, electronic, digital computer ever built, and it was built specifically because of the challenges codebreaking imposed. Whose to say how long it would have been had WW2 not happened?

 

[Vanadium 50]

One problem with using electronics to emulate electromechanical rotor machines was the complexity of an electronic crossbar switch, capable of cyclically indexing an array of scrambled connections

Sure, and that's why they went electromechanical.

The more modern solution would be to go binary: 26 letters is 5 bits, Toss enough NAND can be implemented in a single tube, so a big enough box of tubes can emulate a rotor. Big enough would be a hundred or hundfreds, not the tens of thousands in the upcoming general purpose computers. However, we're programmed to think in binary, They had DeMorgan's Laws, but were these generally known? Or some bit of obscure and useless mathematics.

An alternative might be purpose-built tubes with 26 states, like Nixie tubes have ten. (26 and 10? Sounds like string theory) I understand why that didn't take off - one reason is that Nixie tubes, while invented in the 1930's weren't common until the 1950's. The other is that if you need one new piece of technology, it's easy to make the mental leap and you have a fair probability of success. If you need multiple new developments, this is not the case.

Finally, memory would definitely have helped, but at the time people were using tubes and aciustic delay limes. Obviously semiconductor memory was decades away, but why not switched capacitor arrays? I think the issue isn't capacitor technology, it was the interface to the ScA. Vacuum tubes have high impedance, so you need a lot of charhe, and that makes them big, slow, and likely unreliable. I'm imagining these big electrolytics like you see in 1930's vintage radios. One per bit.

 

[Baluncore]

An alternative might be purpose-built tubes with 26 states, like Nixie tubes have ten.

You may be confusing Nixie tubes with thyratron ring counters. Nixie tubes were single decimal numerical displays, later used with the 7445 decoder. Thyratron rings could be chained to make a 26 element ring, but that would not really help you unless you wanted 26 decoded outputs. The thyratron ring counter was the early plasma version of the later CD4017. The plasma version featured one of 10 neon dots, that made it possible to read the state of the counter.

The more modern solution would be to go binary: 26 letters is 5 bits, Toss enough NAND can be implemented in a single tube, so a big enough box of tubes can emulate a rotor.

26 letters is 5 bits input, scrambled by the 5 bit wheel position, gives a 10 bit input, and there will be 5 bits output. So you need a 1k x 5 bit logic table for each Enigma rotor, except you will need to duplicate that, as there is also the reflected letter signal returning to the display. That logic table could have been minimised, but I don't know by what percentage. I think the 5 wheel position inputs and their inverts would have been the only common decoder logic.

Finally, memory would definitely have helped, but at the time people were using tubes and aciustic delay limes. Obviously semiconductor memory was decades away, but why not switched capacitor arrays?

Memory in the form of an RS F/F could be implemented with a dual-triode vacuum tube. No capacitor was needed.

Capacitors are dynamic memory, so must be refreshed. The high input and output impedance of VTs worked well for that. By sensing the voltage with the high impedance grid, invert and amplify with another, to boost the voltage a little. So it required one dual-triode tube to refresh each column of a dynamic rotating capacitor bank. Unfortunately, the mechanical switch contacts needed for a rotating capacitor bank, brought back the same problems as the Enigma rotor electrical contacts.

 

[Vanadium 50]

thyratron ring counters

Never heard of them.

Nixie tubes were just an example of a tube with multiple discrete states. I'd say "common example" but it's like talking about buggy whips.

 

[Baluncore]

Nixie tubes were just an example of a tube with multiple discrete states. I'd say "common example" but it's like talking about buggy whips.

A Nixie tube was a simple display tube, not a multi-state counter. It contained 10 anodes in the shape of the decimal digits 0 to 9. The digit shown in the neon discharge was selected by controlling the voltage on the 10 inputs.

Never heard of them.

Thyratron ring counters were used in Colossus to count coincidences. They had 10 discrete states, and could be advanced by a pulse input, like a counter. They could also be cascaded to count several decades.

 

[Vanadium 50]

A Nixie tube was a simple display tube, not a multi-state counter.

That is true. (Well, "simple" is in the eye of the beholder - is 7-segment simpler?)

But it is not a binary device either. It has 10 states, not 1.

 

[N1206]

But one method was not "brute force with electronics". I'm still curious was to why not.

As Balancore has said, Colossus had bigger fish to fry, as it were <grin> It was used to attack the more complex 'Fish' cyphers. So the reason that electronics weren't used to brute-force Engima is that the scarce resources (Colussus) were used to break things that could NOT be broken expeditiously by dint of other methods. A helpful Nazi officer in the Qattara Depression sent 'Nothing to report Heil Hitler' every day via Enigma. With a crib like that, breaking Enigma could be done by more conventional methods.

A vastly under-appreciated fact of warfare is that it many times depends upon successful deployment of logistics (ask Putin about that.) In wartime, you spend ONLY the resources you HAVE TO in order to get the task done. The big machines used to purify uranium to Oak Ridge needed a pile of low impedance wiring. That much very pure copper was nixed as being detrimental to the war effort so SILVER, tons of it, was sent from Fort Knox to make the wiring.

Wartime logistics. It sometimes results in what looks like odd choices in peacetime hindsight.

 

[Baluncore]

That is true. (Well, "simple" is in the eye of the beholder - is 7-segment simpler?)

But it is not a binary device either. It has 10 states, not 1.

Both display styles required a 'Binary Coded Decimal' converter to display decimal digits. For wider binary words, the displays were operated in three bit groups, to display octal. 8 bit maximum = 377, 16 bit maximum = 177777.

A 7 segment display has separately illuminated segments, several of which needed to be turned on at one time to show a recognisable decimal digit. There are 2^7 = 128 symbols possible, only 10 of which were needed. The 4 bit BCD to 7 segment converter was the TTL 7447. All signal currents were either on or off, it was digital.

A Nixie tube has ten different shaped electrodes, only one of which needs to be turned on to display the digit. The 4 bit, BCD to one-of-ten converter was the TTL 7445 (or the 7442). All signal currents were either on or off, it was digital.

Neither display device had internal state registers that could store or advance the number displayed. That state information flowed from some earlier digital device.

 

[Baluncore]

As Balancore has said, Colossus had bigger fish to fry, as it were <grin> It was used to attack the more complex 'Fish' cyphers. So the reason that electronics weren't used to brute-force Engima is that the scarce resources (Colussus) were used to break things that could NOT be broken expeditiously by dint of other methods.

On why high level rotor machines, such as Fish, could be emulated by electronics in Colussus, while Enigma could not be emulated so easily without physical rotors.

The higher level rotor systems generated a parallel PRBS from mutually-prime-length rotors. That was then used to conditionally invert (EXOR) the five bits of the teletype character. The same rotor settings generated the same PRBS, which reversed the encryption process. The non-linearity that gave security to the prime rotor machines came from the combination of the EXOR function with the hard to extrapolate PRBS. It was the binary state of signals that changed. The fixed circuitry was not changed during the process.

Enigma employed rotors with a fixed length of 26. That formed a dynamically changing braided path. One of 26 letters flowed forwards, up the braided path through three or four rotors, then was reflected, back down a different braided path through the same rotors. The resulting braided circuit wiring, was step changed for every character. The non-linearity that gave security to Enigma was generated by the dynamically changing braided circuit. It was difficult to emulate the changing circuit path by changing the state of fixed nodes using electronics.

If the electrical path through Enigma rotors had been emulated optically, using mirrors or optic guides in the rotors), then a Bombe could have run significantly faster without contact bounce.

Enigma would have been more secure if the steckers had been part of the reflector, so the sparse stecker letter exchange would have been inconsistent in the plain text. That could have defeated the use of Welchman's diagonal board, which instead defeated a stecker, while searching for a crib.

 

[Vanadium 50]

So the reason that electronics weren't used to brute-force Engima is that the scarce resources (Colussus) were used to break things that could NOT be broken expeditiously by dint of other methods

That is a most excellent answer.

A helpful Nazi officer

The Allies should have given him a medal.

 

[Swamp Thing]

I know very little about this stuff, so quick question: what is repeated substitution? Does it mean, "apply the first sub. cypher to the entire message, then apply the next cypher to the entire result, and so on" ... ?