Heath Robinson (codebreaking machine)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The rebuilding of a Heath Robinson on show at the National Museum of Computing. Prominent in the foreground is the paper tape transport mechanism that was dubbed the "bedstead" because of a resemblance to an upended metal bed frame.

Heath Robinson was a machine used by British codebreakers at the Government Code and Cypher School (GC&CS) at Bletchley Park during World War II in Cryptanalysis of the Lorenz cipher. This achieved the decryption of messages in the German teleprinter cipher produced by the Lorenz SZ40/42 in-line cipher machine. Both the cipher and the machines were called "Tunny" by the codebreakers, who named different German teleprinter ciphers after fish. It was mainly an electro-mechanical machine, containing no more than a couple of dozen valves (vacuum tubes),[1] and was the predecessor to the electronic Colossus computer. It was dubbed "Heath Robinson" by the Wrens who operated it, after cartoonist William Heath Robinson, who drew immensely complicated mechanical devices for simple tasks, similar to Rube Goldberg in the USA.

The functional specification of the machine was produced by Max Newman. The main engineering design was the work of Frank Morrell[2] at the Post Office Research Station at Dollis Hill in North London, with his colleague Tommy Flowers designing the "Combining Unit".[3] Dr C. E. Wynn-Williams from the Telecommunications Research Establishment at Malvern produced the high-speed electronic valve and relay counters.[3] Construction started in January 1943,[4] the prototype machine was delivered to Bletchley Park in June and was first used to help read current encrypted traffic soon afterwards.[5]

Tutte's statistical method[edit]

The basis of the method that the Heath Robinson machine implemented was Bill Tutte's "1+2 technique".[6] This involved examining the first two of the five impulses[7] of the characters of the message on the ciphertext tape and combining them with the first two impulses of part of the key as generated by the chi wheels of the Lorenz machine. This involved reading two long loops of paper tape, one containing the ciphertext and the other the chi component of the key. By making the key tape one character longer than the message tape, each of the 1271 starting position of the chi1 chi2 sequence was tried against the message.[8] A count was amassed for each start position and, if it exceeded a pre-defined "set total", was printed out. The highest count was the most likely one to be the one with the correct values of chi1 and chi2. With these values, settings of the other chi wheels could be tried to break all five chi wheel starting positions for this message. This then allowed the effect of the chi component of the key to be removed and the resulting modified message attacked by manual methods in the Testery.

Tape transport[edit]

The "bedstead" was a system of pulleys around which two continuous loops of tape were driven in synchrony. Initially this was by means of a pair of sprocket wheels on a common axle. This was changed to drive by friction pulleys with the sprocket wheels maintaining the synchrony when it was found that this caused less damage to the tapes. Speeds of up to 2000 characters per second were achieved for shorter tapes, but only 1000 for longer tapes. The tapes were guided past an array of photo-electric cells where the characters and other signals were read.[9] Possible tape lengths on the bedstead were from 2000 to 11,000 characters.[10]

Tape reading[edit]

The perforated tapes were read photo-electrically at a "gate" which was placed as near as possible to the sprocket to reduce the effect of stretched tapes. Successive characters on the tape were read by a battery of ten photocells, an eleventh for the sprocket holes and two additional ones for the "stop" and "start" signals that were hand-punched between the third and fourth and fourth and fifth channels.[9]

Combining Unit[edit]

This was designed by Tommy Flowers of the Post Office Research Station at Dollis Hill in North London.[3] It used thermionic valves (vacuum tubes) to implement the logic. This involved the Boolean "exclusive or" (XOR) function in combining the various bit-streams. In the following "truth table", 1 represents "true" and 0 represents "false". (At Bletchley Park these were known as x and respectively.)

INPUT OUTPUT
A B A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

Other names for this function are: "not equal" (NEQ), "modulo 2 addition" (without carry) and "modulo 2 subtraction" (without 'borrow'). Note that modulo 2 addition and subtraction are identical. Some descriptions of Tunny decryption refer to addition and some to differencing, i.e. subtraction, but they mean the same thing.

The combining unit implemented the logic of Tutte's statistical method. This required that the paper tape containing the ciphertext was tried against a tape that contained the component of the Lorenz cipher machine generated by the relevant two chi wheels at all possible starting positions. A count was then made of the total number of 0s generated, with a high count indicating a greater probability of the starting position of the chi key sequence being correct.

Counting[edit]

Wynn-Williams had obtained his PhD at Cambridge University for his work at the Cavendish Laboratory with Sir Ernest Rutherford.[11] In 1926 he had constructed an amplifier using thermionic valves (vacuum tubes) for the very small electrical currents arising from detectors in their nuclear disintegration experiments. Rutherford had got him to devote his attention to the construction of a reliable valve amplifier and methods of registering and counting these particles. The counter used gas-filled Thyratron tubes which are bi-stable devices.

The counters that Wynn-Williams designed for Heath Robinson, and subsequently for the Colossus computers used thyratrons to count units of 1, 2, 4, 8; high speed relays to count units of 16, 32, 48, 64; and slower relays to count 80, 160, 240, 320, 400, 800, 1200, 1600, 2000, 4000, 6000, and 8000.[10] The count obtained for each run-through of the message tape was compared with a pre-set value, and if it exceeded it, was displayed along with a count that indicated the position of the key tape in relation to the message tape. The Wren operators initially had to write down these numbers before the next count that exceeded the threshold was displayed – which was "a fruitful source of error",[12] so a printer was soon introduced.

Robinson developments[edit]

The original Heath Robinson was a prototype and was effective despite a number of serious shortcomings.[12] All but one of these, the lack of "spanning"[13] ability, were progressively overcome in the development of what became known as "Old Robinson".[14] However, Tommy Flowers realised that he could produce a machine that generated the key stream electronically so that the main problem of keeping two tapes synchronised with each other would be eliminated. This was the genesis of the Colossus computer.

Despite the success of Colossus, the Robinson approach was still valuable for certain problems. A further development of the ideas was a machine called "Super Robinson" or "Super Rob".[15] This had four bedsteads,[16] could run four tapes and was used for "crib" or Known-plaintext attack runs.[17]

References and notes[edit]

  1. ^ Copeland 2006, p. 74
  2. ^ Bletchley Park National Code Centre: November 1943, retrieved 21 November 2012 
  3. ^ a b c Good, Michie & Timms 1945, p. 33 in 1. Introduction: Some historical notes
  4. ^ Copeland 2006, p. 65
  5. ^ Good, Michie & Timms 1945, p. 290 in 3. Organisation: Machine Setting Organisation
  6. ^ Budianskiy 2006, pp. 58,59
  7. ^ "Impulse" is the term used at Bletchley Park. Today one would say "the first two bits".
  8. ^ Sale, Tony (2001), The Rebuild of Heath Robinson: Heath Robinson at Bletchley Park, retrieved 2 April 2013 
  9. ^ a b Good, Michie & Timms 1945, p. 355 in 54. Robinson: Bedsteads and Position Counting
  10. ^ a b Small 1944
  11. ^ Copeland 2006, p. 64
  12. ^ a b Good, Michie & Timms 1945, p. 328 in 52. Development of Robinson and Colossus
  13. ^ Spanning was the ability to limit consideration of the message tape to a defined section (or "span") in a situation in which it was known or suspected that there was an error in a particular part of the tape.
  14. ^ Good, Michie & Timms 1945, p. 354 in 54. Robinson: Introduction
  15. ^ Good, Michie & Timms 1945, pp. 354–362 in 54. Robinson
  16. ^ Good, Michie & Timms 1945, p. 26 in 13. Machines.
  17. ^ Randell 2006, p. 149

Bibliography[edit]