Programming Colossus (Cracking Enigma)

[keeper0]

I suspect most of you are familiar with the efforts of Bletchley Park in cracking the Enigma codes during WWII. One of the keys to this process was the first digital computer, called Colossus, to help sort through the myriad possibilities.

What I would like to know is, "What was the algorithm programmed into the Colossus?" I realize that it was programmed by connecting wires and such, not with a computer language as we think about today. What would it look like as a computer language program?

Did it just cycle through all the possible permutations and leave it up to humans to read through the millions of possibilities to determine likely solutions, or was there some "intelligence" to the computer that it could recognize "good" solutions?
(The former doesn't seem that efficient, but the latter seems unlikely given the computer's capabilities.)

Thank you.

[gotpasswords]

I've not seen (nor looked for!) the information online, but the National Security Agency's Center for Cryptologic History has a handful of booklets on Enigma, its mathematics and the Bombe computers that were used in cracking Enigma.

The booklets are free for the asking - they all say to send a request to:

Center for Cryptologic History
National Security Agency
9800 SavageRoad, Suite 6886
Fort George G. Meade, MD 20755-6886


The titles I have here are:
The Cryptographic Mathematics of Enigma
Sharing the Burden: Women in Cryptology during World War II
Solving the Enigma: History of the Cryptanalyic Bombe

Utterly fascinating stuff. I picked them up at a recent computer security trade show where the NSA was passing them out, but the real attraction was that they had the Holy Grail itself on the table - a real live 4-rotor Enigma!

[gotpasswords]

After some Googling, it appears the NSA's not exactly embracing the concept of publishing stuff on the web.

I did manage to find [iSolving the Enigma[/i] online at http://www.ehistory.com/world/librar...s/wwii/enigma/ This is the largest of the three booklets I listed previously. The others are worth requesting, even if it is by snail mail.

[sailor]

I also recommend The Code Book by Simon Singh

[gotpasswords]

After some Googling, it appears the NSA's not exactly embracing the concept of publishing stuff on the web.

I did manage to find [iSolving the Enigma[/i] online at http://www.ehistory.com/world/librar...s/wwii/enigma/ This is the largest of the three booklets I listed previously. The others are worth requesting, even if it is by snail mail.

[gotpasswords]

<straightening out the LAN cable> Anything else stuck in there??

[Bill H.]

gotpasswords wrote

I picked them up at a recent computer security trade show where the NSA was passing them out, but the real attraction was that they had the Holy Grail itself on the table - a real live 4-rotor Enigma!

Yes! Wasn't that the coolest thing ever? I would love to own one of those bad boys.

[Bill H.]

from http://www.codesandciphers.org.uk/lorenz/rebuild.htm

The performance of Colossus
Colossus is not a stored-programme computer. It is hard-wired and switch-programmed, just like ENIAC. Because of its parallel nature it is very fast, even by today's standards. The intercepted message, punched on to ordinary teleprinter paper tape, is read at 5,000 characters per second. The sprocket holes down the middle of the tape are read to form the clock for the whole machine. This avoids any synchronisation problems: whatever the speed of the tape, that's the speed of Colossus. Tommy Flowers once wound up the paper tape drive motor to see what happened. At 9,600 characters per second the tape burst and flew all over the room at 60 mph! It was decided that 5,000 cps was a safe speed.

At 5,000 cps the interval between sprocket holes is 200 microsecs. In this time Colossus will do up to 100 Boolean calculations simultaneously on each of the five tape channels and across a five character matrix. The gate delay time is 1.2 microsecs which is quite remarkable for very ordinary valves. It demonstrates the design skills of Tommy Flowers and Allen Coombs who re-engineered most of the Mark 2 Colossus.

Colossus is so fast and parallel that a modern PC programmed to do the same code-breaking task takes as long as Colossus to achieve a result!

[sailor]

Originally posted by gotpasswords
After some Googling, it appears the NSA's not exactly embracing the concept of publishing stuff on the web.

I did manage to find [iSolving the Enigma[/i] online at http://www.ehistory.com/world/librar...s/wwii/enigma/ This is the largest of the three booklets I listed previously. The others are worth requesting, even if it is by snail mail.

i read that with interest and it is *very* interesting but a very big mistake has crept in: in page http://www.ehistory.com/world/librar...nigma/0006.cfm it says:

Since the German cipher clerk determined the initial rotor settings, they had to be sent to the intended recipient in the clear, that is, unenciphered. The first three letters of the code group, sent unenciphered, told the receiver where to set the rotors. The following six letters were the ciphered letters (repeated) of the settings for the rest of the message. They were sent twice in order to avoid garbles in transmission. For example, the clerk might send HIT in the clear.

NO!. This makes no sense. The three first letter (the key) were NOT transmitted in the clear. This would give the enemy the key for decription and made the system useless! The key was taken from the key books which the receiver had and which changed daily. With the daily key set the receiver would decode the first six characters which were the key for that message twice. having set the rotors for that message key he would then decode the message. I am surprised such a blatant error crept in. Other than that it is very interesting.

[astro]

Direct precursor of Colossus and the machine on which Colossus was based. Would imagine Colossus wired algorithm was similar.


The Rebuild of Heath Robinson

Finding the Chi wheel pattern start positions.

At Bletchley Park, Bill Tutte had proposed the "Double Delta" method for finding the Lorenz machine wheel start positions to which the German operator had set his Lorenz machine. (different wheel start positions for each message).

The Tutte algorithm required adding modulo two (XORing) the current and previous character bits on both the cipher text (Z) and the Chi wheel patterns (X) being tested to get the Deltas and then XORing these together for two of the five channels (tracks) on the paper tape. Then counting, down the whole length of the tape the number of times that this result equated to zero, trying various pattern start positions to find the maximum score.
i.e. if channels 1 and 2 are being used then count when;

DeltaZ1 + DeltaX1 + DeltaZ2 +DeltaX2 = 0
---------------------------------

The Wynn-Williams proposal.

The Logic Circuits

When Wynn-Williams was asked to produce electronic circuits to implement the double delta algorithm he chose to use a phase modulated carrier from a master oscillator at 25kc/s to perform the XOR logic.

He decided to use 0 and 180 degrees of phase to represent 0 and 1. The elegance of this is that if a "1" causes 180 degrees phase shift, then another 1 returns the phase to zero and thus this implements an XOR function (0 + 0 = 0, 1 + 1 = 0, 0 + 1 = 1, 1 + 0 = 1). ....

and on and on with circuit logic diagrams etc etc

[bernse]

Colossus is so fast and parallel that a modern PC programmed to do the same code-breaking task takes as long as Colossus to achieve a result!

I find that a little hard to believe. What is (was?) their defintion of a modern PC I wonder?

[sailor]

Lorenz ciphers and the Colossus

The Principle of the Enigma

Virtual 3 wheel Naval Enigma

ENIGMA 2.0 A Windows-based emulator of the 3 rotor service machine

[gotpasswords]

Sailor - Transmitting the key in plaintext makes sense. Think of it as the public key you might use for PGP encryption. Doesn't do any good without the private key, or in this case, the physical Enigma device.

Besides, they can't very well run the day's key through Enigma and expect the field units to know how to decode it without a key. In that HIT example, the message header was HIT KOSRLB. The receiver had to have an Enigma, had to know to set the rotors to HIT initially, then enter KOSRLB and successfully decode LERLER, and know to then re-set the rotors to LER to decode the rest of the message.

[Peter Morris]

I dont quite follow that. Couldn't any spy intercepting the message use HIT to decode KOSRLB?

I've seen a documentary on it, and I've heard that the spies seeing HIT at the start would guess that the code was LER, and also BER + LIN, TOM + MIX and others. But from your description, there would be no need to guess, if the key was given.

[sailor]

Originally posted by gotpasswords
Sailor - Transmitting the key in plaintext makes sense. Think of it as the public key you might use for PGP encryption. Doesn't do any good without the private key, or in this case, the physical Enigma device.

Besides, they can't very well run the day's key through Enigma and expect the field units to know how to decode it without a key. In that HIT example, the message header was HIT KOSRLB. The receiver had to have an Enigma, had to know to set the rotors to HIT initially, then enter KOSRLB and successfully decode LERLER, and know to then re-set the rotors to LER to decode the rest of the message.

Um no. That is not how it was done. To begin with public key encryption did not exist yet and this was a simmetrical key. The daily keys were distrubuted in books for periods of 1 2 or 3 months.

the daily key changed at midnight every day and every key consisted of: the order of the rotors, the position of the rotors (three letters in question) and the jumpers of the plugboard. With this key a received message was begun to decode and the six first characters were the new positions of the three rotors duplicated. It is explained in every text where Enigma is discussed and you can see it here: http://www.codesandciphers.org.uk/enigma/enigma3.htm

Even that page which I mentioned is in error, a couple pages before gets it correctly. It is obviously an oversight.

[Little Nemo]

Three factors were key in breaking the enigma codes. First was the fact that unknown to the Germans, the Allies had succeeded in virtually duplicating the physical design of the enigma. Second was a pecularity of the machine; due to its design, it never substituted a letter for itself. Third was the habit of some Axis transmitters of using certain stock phrases (for example there was one weather station that always started its transmission with the exact identical opening).

So the British would intercept a transmission from a source like the above mentioned weather station. They already knew part of the message because of the repitition. The colossus would then try various combinations of enigma settings to see if this message would encode as the received transmission. Numerous combinations could be eliminated right away because of the letter for letter substitution mentioned above. But eventually a combination of settings would be found that duplicated the known message. These settings could then be used to decode other transmissions with new messages.

[Spiny Norman]

The importance of having a physical Enigma machine available is somewhat overstated - the Wehrmacht set up their procedures assuming that a machine would eventually fall into enemy hands. (Even so, the military Enigma was only a modest improvement on a commercially available model. The inner workings were not secret.)

sailor is right, no key was ever transmitted in plaintext.

One of the weaknesses was that the operator had to select a 3-letter key per message. Humans are bad at generating random sequences, especially tired humans. Operators would select sequences next to each other on the keyboard, for instance - having some sequences being more likely than other is the sort of thing that lends itself to statistical analysis.

[sailor]

Maybe it is because I am a geek for these things but owning a replica of an Enigma machine would be cool and I have not seen them for sale anywhere. I wonder if they can be found. It would make a cool toy to play with and a neat thing for display.

[sailor]

The Colossus Rebuild Project

[sailor]

I have been looking some more into how the Enigma machine was used and it turns out I was mistaken in a way because there is another layer I was not aware of until now.

The rotors were composed of two parts which could rotate with respect to each other so that the catch which made the next rotor advance one step was not always in the same place with respect to the rotor. This way the catch which made the next wheel advance could be placed in any position arount the rotor. These were called the "ring settings".

So, the key necessary for decryption was composed of:

1. Rotor Order (Walzenlage), e.g.: II, I, III
2. Ring settings (Ringstellung), e.g.: Z, W, D
3. Starting Rotor Positions, (Grundstellung), e.g.: C, R, D
4. Plugboard connections (Steckerverbindungen): EZ, BL, XP, WR, IU, VM, JO

Of these 1, 2 and 4 were part of the secret daily code books of which both sender and receiver had copies BUT #3, the starting rotor positions, were chosen randomly by the sender for each message and were transmitted in clear at the beginning of the message.

That explains my earlier confusion in this thread. I hope I got it right this time.

[sailor]

I forgot to include the link where you can see a facsimile of a code book and an explanation of how it was used. The first column is the day of the month. The second column is the rotor order. The third column is the ring settings. The fourth column is the plugboard settings. There is a fifth column called Kenngruppe which was not necessarily used as that page explains.

In this page you can also see an example of how the Enigma was used in practice.

[KidCharlemagne]

My understanding is that Colossus wasn't pure brute force but was set to start with likely combinations based on cribs, link chains (which was the first undoing of the Enigma - I think we have those two Polish mathematicians to thank for that one), and other intelligence.

I have to second "The Code Book" by Simon Singh. That's the best non-fiction read I've had in years.