Crash (cryptology)
As Crash ( / kræʃ / ; plural crashes ; German collision, crash crash ; German technical term: collision ) is in the cryptology the coincidence of an identical character at the same position in both the plaintext and the ciphertext referred to in the jargon then with the Verb to crash ( German "crash" ) called. The opposite is Admit ( German to allow; freely translated: “fits” ).
Crash should not be confused with clash (the repeated occurrence of the same Enigma roller on two consecutive days).
meaning
Crashes in classical cryptology with polyalphabetic ciphers , which meet the condition “in every alphabet , no character is encrypted by the same character ” are of great importance . This includes involutive ciphers . A prominent example is the Enigma rotor key machine , which was used by the German Wehrmacht during the Second World War . If, for example, a U is encoded into an X there, then an X would conversely be encoded into a U in this position.
This special property of the Involution simplified the operation and construction of the machine, because there is no need to differentiate between encryption and decryption . At the same time, this also causes a cryptographic weakness , namely that a letter is never encrypted in itself ( fixed point-free permutation ). The British code breakers in Bletchley Park ( BP ), England, knew this weakness and used it to their advantage if the machine broke . The electromechanical "cracking machine" they successfully used to decipher the German Enigma radio messages , the Turing bomb (also: Turing-Welchman bomb or Welchman-Turing bomb ; bomb for short ), requires clear text passages, their occurrence and precise details for their function Position in the text had to be guessed by the code breakers. The observation of crashes helped them .
As Admit , loosely translated "fits" the opposite of was crashing called, so an appropriate Crib at a certain position within the text, to no crashes leads. Exactly such matching crib layers were the coveted passages that were subsequently examined more closely with the help of the Turing bomb and which often led to the solution of the ciphertext.
example
A deciphering method that has been known and proven for centuries is the " Probable Word Method ". The attacker guesses, suspects or knows that a certain phrase ( Crib in English , Mot probable in French ) appears in the text , for example "OBERKOMMANDODERWEHRMACHT". If, for example, the attacker has a ciphertext fragment encrypted with the Enigma like the following, he can easily determine at which point in the text the suspected probable word can not be by checking for each possible position whether there is a character in it itself would be encrypted, which, as he knows from the Enigma, is impossible. To do this, he writes the probable word in the various positions under the ciphertext and checks for collisions , which are highlighted in red and underlined in the example below:
BHNCXSEQKOBIIODWFBTZGCYEHQQJEWOYNBDXHQBALHTSSDPWGW 1 OBERKOMMANDODERWEHRMACHT 2 OBERKOMMANDODERWEHRMACHT 3 OBERKOMMANDODERWEHRMACHT 4 OBERKOMMANDODERWEHRMACHT 5 OBERKOMMANDODERWEHRMACHT 6 OBERKOMMANDODERWEHRMACHT 7 OBERKOMMANDODERWEHRMACHT 8 OBERKOMMANDODERWEHRMACHT 9 OBERKOMMANDODERWEHRMACHT 10 OBERKOMMANDODERWEHRMACHT 11 OBERKOMMANDODERWEHRMACHT 12 OBERKOMMANDODERWEHRMACHT 13 OBERKOMMANDODERWEHRMACHT 14 OBERKOMMANDODERWEHRMACHT 15 OBERKOMMANDODERWEHRMACHT 16 OBERKOMMANDODERWEHRMACHT 17 OBERKOMMANDODERWEHRMACHT 18 OBERKOMMANDODERWEHRMACHT 19 OBERKOMMANDODERWEHRMACHT 20 OBERKOMMANDODERWEHRMACHT 21 OBERKOMMANDODERWEHRMACHT 22 OBERKOMMANDODERWEHRMACHT 23 OBERKOMMANDODERWEHRMACHT 24 OBERKOMMANDODERWEHRMACHT 25 OBERKOMMANDODERWEHRMACHT 26 OBERKOMMANDODERWEHRMACHT 27 OBERKOMMANDODERWEHRMACHT BHNCXSEQKOBIIODWFBTZGCYEHQQJEWOYNBDXHQBALHTSSDPWGW |
The number of situations to be ruled out by crashes can be estimated based on the following consideration: With a probable word of length 1 (i.e. only a single probable letter) the probability of a collision is 1/26. Hence the probability of no crash is 1−1 / 26. With a probable word as above with length 24, the probability of no collision (1−1 / 26) is 24 , which is about 39%. This means that in the case of 27 examined locations, no crashes are expected on average for 27 · (1−1 / 26) 24 of the cases . The expression gives a value of about 10.5 and agrees quite well with the eight collision-free crib layers observed in the example (and marked in green). With the help of this extremely simple cryptanalytic attack method, 19 of the 27 possible positions of the probable word, i.e. more than two thirds, can be eliminated as impossible - a considerable simplification of work for the attacker.
literature
- Friedrich L. Bauer : Deciphered Secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, ISBN 3-540-67931-6 .
- Tony Sale : The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001. PDF; 0.4 MB , accessed August 27, 2018.
Web links
Individual evidence
- ↑ Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001, p. 22. PDF; 0.4 MB , accessed August 27, 2018.
- ↑ Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary . Publication, Bletchley Park, 2001, p. 1. PDF; 0.4 MB , accessed August 27, 2018.
- ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 270.
- ^ Gordon Welchman: The Hut Six Story - Breaking the Enigma Codes . Allen Lane, London 1982; Cleobury Mortimer M&M, Baldwin Shropshire 2000, p. 11. ISBN 0-947712-34-8
- ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 276.
- ^ Claude Shannon: Communication Theory of Secrecy Systems . Bell System Technical Journal, Vol. 28, 1949 (October), pp. 710f. PDF; 0.6 MB , accessed: August 27, 2018.
- ↑ David Kahn: Seizing the Enigma - The Race to Break the German U-Boat codes 1939 -1943 . Naval Institute Press, Annapolis, MD, USA, 2012, p. 131. ISBN 978-1-59114-807-4 .