A historical look at decrypting the Enigma

[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" ... ?

 

[Baluncore]

what is repeated substitution?

It depends on context, and what happens between the two substitutions.
Where was the term used?

 

[Swamp Thing]

It depends on context, and what happens between the two substitutions.
Where was the term used?

The last two posts in these results: https://www.physicsforums.com/search/7184615/?q="repeated+substitution"&t=post&c[thread]=1046742&o=date

Edit: I asked because it seemed that Vanadium considered Enigma to be a form of rep. subs. Whereas to me, it seems like a very long one-time pad that you recycle through each time you reach the end?

Edit: Plus, the enemy has copies of all the pads you will ever use (like millions of them) but doesn't know which is the current one.

 

[Baluncore]

Each rotor contained 26 wires that connected the 26 contacts on the left face, to 26 different contacts on the right face. That was in effect a (cyclically changing) letter substitution. With three rotors, and a reflector, there were a total of 7 substitutions. The plugboard was another sparse substitution, since only a few steckers were used to exchange the letters.

I don't think the concept of a long "One Time Pad" is a good model of Enigma. The messages were very much shorter than the rotor sequence length. Enigma was broken by the successive preclusion of possible known rotors, based on each assumed crib. An OTP should be truly random, and so could not possibly be factored into the different rotor combination and order employed that day.