Autoscritcher

from Wikipedia, the free encyclopedia

The Autoscritcher was an electromechanically operated cryptanalytic machine that was developed and used by the US towards the end of the Second World War to decipher the communications of the German Wehrmacht, which was encrypted with the help of the Enigma key machine . From the beginning of 1945, an electronic version was developed, called the Superscritcher , but it was not completed until after the end of the war, in 1946.

The name Autoscritcher comes from the Greek word αὐτό ~ (German: "self") and the English verb to scritch , which, especially in the field of cryptanalysis , describes the systematic processing of hypotheses taking into account other boundary conditions, perhaps somewhat freely in German To translate "durchnudeln".

background

ENIGMA roller set with three rotating rollers and on the far left here the reversing roller B. The task of the autoscritcher was to develop the unknown and frequently changing wiring of the reversing roller D.

During the Second World War, the backbone of German cryptography was formed by ENIGMA, which was used by all three parts of the Wehrmacht, the army , the air force and the navy , to encrypt their secret communications. Long before the war, in 1932, Polish cryptanalysts working with the young Marian Rejewski succeeded in breaking into the ENIGMA system for the first time . Building on this, British code breakers in Bletchley Park, England , succeeded in intercepting German radio messages at the beginning of the war and, from January 1940, first of all to decipher messages encrypted by the Air Force and later by the Army with the ENIGMA I. Contrary to the German hopes and assumptions, the radio messages encrypted by the German Navy with the help of the ENIGMA M3 and - particularly important for the war effort - the radio messages encrypted with the ENIGMA M4 machine used by the German submarines remained no secret for the British. Rather, they succeeded in breaking the Wehrmacht's encrypted communications with the aid of special cryptanalytic devices such as the Turing bomb for almost the entire duration of World War II and using the information obtained from it profitably under the code name " Ultra ".

Towards the end of the war, more precisely on January 1, 1944, the Luftwaffe began to use an innovative roller in part of its key networks, namely the reversing roller D (photo see Pröse p. 40), which, in contrast to all other ENIGMA rollers, is characterized by this that their wiring could be changed by the user depending on the key . The German cryptographers eliminated a major weakness of ENIGMA, which was based on the fact that, as with the "old" reversing rollers (VHF A, B and C), the wiring of the ENIGMA rollers was rigid and never changed (see also: Enigma rollers ). So they denied their British and American "opponents" the possibility of breaking into the secret German radio traffic, which was used there on an industrial scale, but without the Germans knowing or even suspecting it.

The VHF D could have had fatal consequences due to the significant increase in the combinatorial complexity of the ENIGMA machine on the Allied side, and could have caused the ENIGMA to completely lose its ability to decipher if this cylinder had been introduced suddenly and across the board. This is confirmed by a quote from an American investigation report written shortly after the war:

“ How close the Anglo-Americans came to losing out in their solution of the German Army Enigma is a matter to give cryptanalysts pause. British and American cryptanalysts recall with a shudder how drastic an increase in difficulty resulted from the introduction by the German Air Force ot the pluggable reflector (" Umkehrwalze D," called "Uncle Dick" by the British) in the Spring of 1945. It made Completely obsolete the "bomb" machinery which had been designed and installed at so great an expense for standard, plugboard-Enigma solution. It necessitated the development by the US Navy of a new, more complex machine called the "duenna," and by the US Army of a radically new electrical solver called the "autoscritcher." Each of these had to make millions of tests to establish simultaneously the unknown (end-plate) plugboard and the unknown reflector plugging. Only a trickle of solutions would have resulted if the pluggable reflector had been adopted universally; and this trickle of solutions would not have contained enough intelligence to furnish the data for cribs needed in subsequent solutions. Thus even the trickle would have eventually vanished. ”

“How close the Anglo-Americans were about to lose the ability to decipher the German Army ENIGMA is a matter that makes cryptanalysts breathless. British and American code breakers remember with a shudder what a drastically increased complication from the introduction of the plug-in reversing roller ("Reversing roller D", called "Uncle Dick" by the British) by the German Air Force in the spring of 1945 [actually: in the spring of 1944] resulted. This made the " bomb fleet " completely useless, which had been designed and built with so much effort to solve the normal plug board ENIGMA. Inevitably, the US Navy had to develop a new, much more complicated machine called the “ Duenna ”, and the US Army had to develop a completely new electrical solution machine called the “Autoscritcher”. Each of these machines had to carry out millions of tests in order to simultaneously fathom the unknown (front panel) connector board and the unknown wiring of the reversing roller [D]. There would only have been a trickle of solutions if the plug-in reversing roller had been used in general; and these droplets of solution would not have contained sufficient information to provide indications for cribs needed for further solutions. In the end, even the trickling would have dried up. "

In fact, the reversing roller D was not introduced suddenly and across the board, but, presumably due to production bottlenecks caused by the war and also, as has since been done by the German cryptologist Dr. Erich Hüttenhain known, because of its arduous and error-prone handling only occasionally and in a few key circles, for example by the Air Force in Norway, while mostly the well-known VHF B was still used - a fatal cryptographic error.

This mistake allowed the Allies to understand the functionality and use of the VHF D and to develop special cryptanalytic "cracking machines", the main task of which was to change the wiring of the VHF three to four times a month at intervals of about seven to twelve days D to stay on the trail and thus maintain the ability to decipher German communications, which is essential for the war effort.

The autoscritcher

In the war year 1944, the Autoscritcher was developed and built by the US Army's Signal Security Agency (SSA) as one of the most cryptanalytically powerful electromechanical machines . The relay technology that was tried and tested at the time was used, which was known and available from telephone switching technology .

For the exhaustive (complete) cryptanalytic attack on the key area of the ENIGMA, in principle 5 · 4 · 3 = 60 roller positions and 26 · 26 · 26 = 17,576 roller positions would have to be examined. However, the basic cryptanalytic principle of the autoscritcher exploited a fundamental weakness of ENIGMA, which consisted in the fact that the roller position of the left roller in the roller set only changed every 650 letters, which, due to the prescribed maximum length of the radio messages of 250 letters, rarely happened once in a message . The allied cryptanalysts were therefore able to limit themselves to the 5 · 4 = 20 possible combinations of the middle and right rollers with the so-called “ two-wheel attack” and did not have to “noodle through all 60 combinations of the roller set ". In addition, they used the “ general plug approach ” method and were thus able to further reduce the number of roller positions to be checked for two rollers from 26 · 26 = 676 possibilities to only 26 possible relative positions. In this way they succeeded in reducing the search area from originally 60 roller positions by 17,576 roller positions, i.e. 1,054,560 (more than a million) possibilities of ENIGMA to only 20 · 26 = 520 cases to be examined.

The core of the investigation for each of these 520 cases were individual processing steps. For this purpose, a connector partner for the secret letter and a connector partner for the plain letter was exhaustively assumed for the respective letter of the plain text and the ciphertext for a certain text position, designated by the cryptanalysts in English as "Constatation" . In contrast to the practically unmanageable task of trying out all the options for the entire ENIGMA plug board (there are more than 150 trillion plug-in options for this, see also: Key space in the ENIGMA main article ), the task of trying out all connector partners for a single given letter is very easy, because there are only 26 options. These were switched electromechanically and it was determined which wiring this leads to in the case of the unknown “virtual, thick” reversing roller. The composition of the unknown VHF D and the equally unknown left-hand rotating roller, which were initially not considered to be separate, was considered as a virtual, thick reversing roller. The examination described was carried out automatically for up to twenty different text positions and their results compared.

The comparison could produce three different results. First, a so-called "Confirmation" (German: confirmation). This meant that a possible consistent (partial) solution had been found and it was worthwhile to continue the investigation until the complete solution was found. Second, it was possible that the result was no confirmation but also no contradiction. This was called "non-contradiction" (German: non-contradiction). In this case you were just as smart as before and had to investigate further text positions or, at the risk of overlooking the real solution, interrupt the investigation here. The third result was a contradiction ( "contradiction" ). Basically, this was a very welcome result, because according to the basic principle of Reductio ad absurdum ( German,  return to contradiction ) one of the many possibilities could be safely rejected. As soon as this proof of contradiction was successful for all but one possible solution, the correct solution had been found.

The autoscritcher could be put into operation early in 1945, that is, during the time of the Second World War, and was able to perform around ten processing steps per second. After each partial examination, a human operator had to set the machine to a new one of the 26 possible different relative roller positions of the middle and right roller and then exchange the roller set. A total of twenty different sets of rollers were to be examined. The running time was about three and a half hours per roller layer, so a maximum of 70 hours in total.

The autoscritcher was successfully used to determine the wiring of the VHF D. The first " break " occurred on February 18, 1945, two more on March 6 of the same year. Overall, the completed Autoscritcher 21 runs, of which four were successful and eight others were stopped prematurely because the key in other ways had been identified or a better Crib was available. Only one example of the Autoscritcher was ever made, as the intention from the beginning was to develop the Superscritcher as a successor .

The superscritcher

The electronic refinement of the autoscritcher was the superscritcher , which, unlike its predecessor, did not use relays, but rather the highly modern electron tubes of the time. (The transistor was not invented until 1947.) In the case of the Superscritcher completed by the SSA in 1946, i.e. after the end of World War II, around 3500 electron tubes were used. The double triode of the type 6J6 was mainly used, the reliability of which initially caused great problems for the engineers . As it later turned out, the cause was a design defect in the triode, which was due to the insufficient distance between the cathode and control grid , between which short circuits could easily form due to dirt particles, especially when the tube was installed horizontally. The problem was finally solved by selecting good specimens.

After development of the Superscritcher had started in the last quarter of 1944 and the concept was in place early in 1945, construction and finally commissioning of the prototype began in autumn 1945. Commissioning was successfully completed in the first half of 1946.

The Superscritcher was originally designed in such a way that it should be able to carry out around a thousand processing steps per second instead of the approximately ten processing steps per second of its electromechanical predecessor. In fact, after successfully completing their project, the engineers were happy that the speed could be exceeded by a factor of 20. In addition, the 26 relative roller positions on the Superscritcher, in contrast to the Autoscritcher, were set automatically and not manually. Only the twenty different roller positions still had to be switched manually. Instead of around 70 hours that the Autoscritcher needed for a full cycle, the Superscritcher took barely three minutes.

glossary

  • Confirmation - English word for "confirmation"
  • Constatation - Special English term for a pair of letters made up of a ciphertext letter at a certain text position and the associated assumed or assumed plaintext letter
  • Contradiction - English word for "contradiction"
  • Crib - (German: Eselsbrücke, more aptly: Probable word) English term for a text fragment which is expected to appear in plain text
  • Cup - (German literally: mug, bowl, mug) Special English term for a processing unit, of which the autoscritcher had six, each of which could process up to five pairs of letters (English: constatations )
  • Ciphertext - Text generated from plaintext by encryption
  • Non-contradiction - a special English term for a so-called “non-contradiction”, ie a result that does not lead to confirmation, but also not to contradiction
  • Key - Secret setting of the key machine
  • Key space - set of all possible keys
  • Spruch - ciphertext that is usually transmitted by radio
  • Plug - cable connections between the front panel sockets
  • Plug board - socket plate attached to the front of the ENIGMA
  • Reversing roller - (mostly) fixed roller at the end of the roller set (abbreviation: UKW)
  • Uncle Dick - (German: Onkel Dick) English nickname for the reversing roller D
  • Roller - rotor that turns during the keying process (English: wheel )
  • Roll position - key-dependent placement of the rolls in the roll set
  • Roller set - a summary term for all rollers
  • Roller position - manually adjustable and changing rotation position of the rollers during the keying process

See also

literature

  • Friedrich L. Bauer : Deciphered Secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, ISBN 3-540-67931-6 .
  • David J. Crawford, Philip E. Fox (Eds.): The Autoscritcher and the Superscritcher: Aids to Cryptanalysis of the German Enigma Cipher Machine . IEEE Annals of the History of Computing, Volume 14, Number 3, 1992, pp. 9-22.
  • Philip Marks : Reversing roller D: Enigma's rewirable reflector - Part 1 . Cryptologia , Volume XXV, Number 2, April 2001, pp. 101-141.
  • Philip Marks: Reversing roller D: Enigma's rewirable reflector - Part 2 . Cryptologia, Volume XXV, Number 3, July 2001, pp. 177-212.
  • Philip Marks: Reversing roller D: Enigma's rewirable reflector - Part 3 . Cryptologia, Volume XXV, Number 4, Oct. 2001, pp. 296-310.
  • Michael Pröse: Encryption machines and deciphering devices in World War II - history of technology and aspects of IT history . Dissertation at Chemnitz University of Technology, Leipzig 2004. PDF; 7.9 MB
  • Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001, p. 22. Retrieved January 16, 2012. PDF; 0.4 MB
  • Heinz Ulbricht: The Enigma cipher machine - deceptive security . A contribution to the history of the intelligence services. Dissertation Braunschweig 2005. PDF; 4.7 MB

Web links

Individual evidence

  1. ↑ Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001, p. 72. Retrieved January 16, 2012. PDF; 0.4 MB
  2. ^ Gordon Welchman: The Hut Six Story - Breaking the Enigma Codes . Allen Lane, London 1982; Cleobury Mortimer M&M, Baldwin Shropshire 2000, p. 230. ISBN 0-947712-34-8
  3. ↑ Michael Pröse: Encryption machines and deciphering devices in the Second World War - the history of technology and aspects of the history of IT . Dissertation at Chemnitz University of Technology, Leipzig 2004, p. 40. PDF; 7.9 MB ( Memento of the original from September 4, 2009 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / archiv.tu-chemnitz.de
  4. ↑ Philip Marks : Umkehrwalze D: Enigma's rewirable reflector - Part 1 . Cryptologia , Volume XXV, Number 2, April 2001, p. 107
  5. ^ A b Army Security Agency: Notes on German High Level Cryptography and Cryptanalysis . European Axis Signal Intelligence in World War II, Vol 2, Washington (DC), 1946 (May), p. 13. Accessed: Jan 16, 2012. PDF; 7.5 MB ( memento of the original from June 11, 2014 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / www.nsa.gov
  6. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 118.
  7. ^ A b David J. Crawford, Philip E. Fox (eds.): The Autoscritcher and the Superscritcher: Aids to Cryptanalysis of the German Enigma Cipher Machine . IEEE Annals of the History of Computing, Volume 14, Number 3, 1992, p. 9.
  8. ^ Hugh Sebag-Montefiore: ENIGMA - The battle for the code . Cassell Military Paperbacks, London 2004, p. 404 ISBN 0-304-36662-5
  9. ↑ Philip Marks: Umkehrwalze D: Enigma's rewirable reflector - Part 3 . Cryptologia, Volume XXV, Number 4, Oct. 2001, p. 296.
  10. ^ A b David J. Crawford, Philip E. Fox (eds.): The Autoscritcher and the Superscritcher: Aids to Cryptanalysis of the German Enigma Cipher Machine . IEEE Annals of the History of Computing, Volume 14, Number 3, 1992, p. 15.
  11. ↑ a b c Philip Marks: Umkehrwalze D: Enigma's rewirable reflector - Part 3 . Cryptologia, Volume XXV, Number 4, Oct. 2001, p. 297.
  12. ↑ Philip Marks: Umkehrwalze D: Enigma's rewirable reflector - Part 3 . Cryptologia, Volume XXV, Number 4, Oct. 2001, p. 303.
  13. ↑ David J. Crawford, Philip E. Fox (Eds.): The Autoscritcher and the Superscritcher: Aids to Cryptanalysis of the German Enigma Cipher Machine . IEEE Annals of the History of Computing, Volume 14, Number 3, 1992, pp. 20-21.
  14. ^ A b David J. Crawford, Philip E. Fox (eds.): The Autoscritcher and the Superscritcher: Aids to Cryptanalysis of the German Enigma Cipher Machine . IEEE Annals of the History of Computing, Volume 14, Number 3, 1992, p. 21.
  15. ↑ Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001, p. 22. Retrieved January 16, 2012. PDF; 0.4 MB