Cipher Cracking: When Computer Bugs Were Real and Bits Were Cogs
Introduction
Being a Prof, I'm so lucky to be invited to meet some amazing people, and see places where some of the great cryptographers of the past once practiced their art. One of my favouriates is seeing the ancient cipher machines, so I'm pleased to say I finished my Enigma Machine [here]:
and my Lorenz machine [here]:
A few basics
Imagine that Bob and Alice wish to secretly communicate, and Eve, who wishes to listen in. Here “plain text” refers to the original message, and “cipher text” as the coded message.
There are two ways of creating the cipher text:
-
Having an algorithm (a cipher) that only Bob and Alice know, so that one applies the cipher to encode the text and the other applies the cipher in reverse to decode.
-
Using a well-defined algorithm, but adding something that changes the way it operates which is easy for Bob and Alice to convert, but difficult for Eve to find.
In the first case, to read their messages Eve will have to crack the cipher – to work out what method it uses to change plain text to cipher text. For example, the famous Julius Caesar cipher is a form of substitution cipher that shifts letters in the alphabet a number of places, for example a shift of 13 means A becomes N, B becomes O, C becomes P and so on. This is an easy code to crack, as there are only 25 unique shifts.
A substitution cipher with the alphabet shifted 13 times (ROT13).Matt Crypto
Far harder would be a scrambled alphabet, in which any letter can be mapped to any other letter without the same substitution shift applying to all, as with the Caesar cipher. This leads to a colossal number of permutations – 403 million billion billion – that, even with a supercomputer with which to try a billion mappings per second, would still take an average 6.3 billion years to crack.
However, these ciphers' fundamental weakness is the occurrence of the letters: in English, the letter with the most occurrences is likely to represent an E, the most common in the language. Performing a frequency analysis with this in mind makes much shorter work of it – about five minutes.
In the early days it was the ciphers' text scrambling method that was kept secret. But if Eve manages to crack the cipher, neither Bob nor Alice will know – just as the Nazis didn’t know the Allies had cracked Enigma. So modern cryptography uses a different approach: a public method to create the cipher, but a private key to use the cipher that Eve will find difficult to find. This is public key encryption.
Try my new Caeser shifter:
https://asecuritysite.com/encryption/caesar
The Birth of Computers
One of the first appearances of computer technology occurred in the USA in the 1880s, and was due to the American Constitution demanding that a survey be undertaken every 10 years. As the population of the USA increased, it took an increasing amount of time to produce the statistics. In fact it got so bad, that by the 1880s, it looked likely that the 1880 survey would not be complete until 1890.
To overcome this, a government employee named Herman Hollerith devised a machine that accepted punch cards with information on them. These cards allowed an electrical current to pass through a hole when there was a hole present (a ‘true’), and did not conduct a current when it a hole was not present (a ‘false’). This was one of the first uses of binary information, which represents data in a collection of one of two states (such as true or false, or, 0 or 1). Thus, Hollerith used a system which stored the census information with a sequence of binary information.
Hollerith’s electromechanical machine was extremely successful and was used in the 1890 and 1900 censuses. He then went on to found the company that would later become International Business Machines (IBM): CTR (Computer Tabulating Recording). Unfortunately, his business fell into financial difficulties and was saved by Tom Watson, a young salesman at CTR, who recognized the potential of selling punch card-based calculating machines to American businesses.
He eventually took over the company, and, in the 1920s, he renamed it International Business Machines Corporation (IBM). IBM would eventually control much of the computer market, and it was only their own creation, the IBM PC, which would reduce this domination. For the next 50 years the electromechanical machines were speeded up and improved, but electronic computers, using valves, would eventually supercede these.
The first generation of electronic computers started in 1943.
These electronic computers used the flow of electrons within an electronic valve to represent the binary states, and not on magnetic fields stored in electromagnetics, which were used in previous computers. This had the advantage that they did not rely as much on the movement of mechanical components and or magnetic fields. These led to the first generation of computers that used electronic valves and punched cards for their main, non-volatile storage (non-volatile allows for long-term storage, even when the power is taken away).
The first electronic computers developed were the ‘Harvard Mk I’, which was developed at Harvard University and was a general-purpose electromechanical programmable computer, and Colossus, which was developed in the UK and was used to crack the German coding system (Lorenz cipher).
Codebreaking Enigma
In the days before computers, ciphers were mechanically generated – the Enigma cipher rotor machine is a good example. It used a polyalphabetic substitution cipher – with three rotors to generate three alphabetic substitution shifts – and a secret key. The challenge was to determine both the algorithm used and the key.
Enigma’s weakness was that the machine prevented a plain text letter from being ciphered as itself (that is, from A ending up after three substitutions as A). This made the challenge easier as the codebreakers could dismiss any code that mapped to the same letter, bu this still left many alternatives – too many for a human to crack.
Figure 3: An Enigma… wrapped in a box. Dominic Lipinski/PA
The mathematical prowess of the Polish Cypher Bureau had secretly first broken Enigma codes in 1932, with the aid of French intelligence. At the eve of the war they handed their work to the Allies, who were amazed. But by now the German military were using more advanced versions of the Enigma machine, with extra rotors and other features adding complexity to the cipher. Dilly Knox, the British chief codebreaker, had some success but better equipment was required.
Developing the work of the Polish Cipher Bureau, Turing and Gordon Welchman designed the electro-mechanical Bombe, a device designed to imitate Enigma machines wired back-to-back, which given certain information could narrow down the possible permutations of the Enigma machines' settings from 150 million million to a more manageable number.
Figure 4: Former operator Jean Valentine, 82, explains the ‘Bombe’ cryptoanalysis machine behind her. Rui Vieira/PA
But the true father of code cracking is Colossus, the world’s first programmable electronic digital computer, which was created by engineer Tommy Flowers in order to crack the Lorenz cipher, the more sophisticated successor to Enigma.
Figure 5: The rebuilt Colossos, the world’s first computerised codebreaking machine with Tony Sale, it’s creator. Ru
Conclusion
We have always been been intrigued by keeping secrets and uncovering the secrets of others, whether that’s childhood secret messages, or secrets and codebreaking of national importance. For us at Edinburgh Napier, we love cracking ciphers, and the challenge of breaking them increases by the day. While some throw lots of computing power at breaking them, others still look to analyse them for their flaws.
For us the demand for cryptography increases by the day, and we are amazed by the number of companies who are looking to collaborate with us, and aim to improve security. For us, we just love the subject, and it is a privilege to do anything in this area, and make a small difference.
If you're interested there are more here: