The Story of Cryptography Part 2: 20th Century Cryptography

In the first post of this series, we described the early history of cryptography.  This included the development and use of Caesar’s Box and the Vigenere cipher, encryption algorithms that pioneered the use of encryption and the encryption key.

It wasn’t until the 20th century that cryptography came into widespread use.  Notable encryption milestones from the 20th century include the development and use of the Enigma machine, the creation of the US Data Encryption Standard (DES), and the development of asymmetric encryption.

The Enigma Machine

The Enigma machine is the most famous mechanical encryption machine in existence.  Developed by Arthur Scherbius in 1918, it was a machine that implemented a substitution cipher.  The use of several different rotors and reconfigurable wiring allowed the machine to operate in many different configurations and acted as the secret key.

When used, the Enigma operator would type a letter on the keyboard and the next letter of the ciphertext would light up.  Decryption was accomplished via the same process, allowing the use of Enigma for encrypting radio communications (which was necessary for the rapid troop movement that was a vital part of their strategy).  The Enigma machines were famously used by the Germans in WWII, but versions were also employed by the Japanese and Italians as well.

Cracking the German Code

Breaking the encryption of the Enigma machine was a multistage process.  The model in use by the Germans had cryptographic vulnerabilities, allowing a Polish cryptanalysis, Marian Rejewski, to crack the encryption keys in use.  However, he did not have knowledge of the internal wiring of the machines, so he was not able to use this knowledge to break the codes.

This information was obtained by French spy Hans-Thilo Schmidt, along with the codes used for encryption in September and October 1932.  Using captured ciphertexts from this period, the Polish were able to build a working Enigma machine and decrypt German communications starting the following January.  This began a cat and mouse game between the Germans and the Poles until 1938, when German improvements made decryption too resource-intensive for the Poles to maintain.

In July of the following year, the Poles disclosed their Enigma decryption efforts to French and British military intelligence.  This partnership allowed the British to develop their Enigma decryption efforts at Bletchley Park and continue decryption of German communications for the rest of the war.  In the end, one of the deciding factors in their ability to decrypt Enigma communications was procedural errors like failure to update encryption keys regularly 

Lucifer: The Data Encryption Standard

Before the early 1970s, the use of cryptography was primarily restricted to the military.  However, in 1971, the first encryption algorithms for private use were published. Companies had seen the effectiveness of encryption and were interested in applying to the protection of their intellectual property.

The first set of civilian encryption algorithms were developed by IBM under the name Lucifer.  Several different variants were developed internal to IBM, and one of the variants was submitted to the US National Bureau of standards (the precursor of NIST) in response to a call for proposals for the national Data Encryption Standard.

The submitted version of Lucifer was vulnerable to differential cryptanalysis, an attack only known to the NSA at the time.  However, after some modifications by the NSA, IBM’s Lucifer submission was accepted as the Data Encryption Standard (DES).

The accepted version of DES was a Feistel network, a multi-round encryption algorithm whose structure is shown in the images above, where the right image shows the operations performed in the boxes labeled F (for Feistel function) in the left image.  As shown, the message undergoes a permutation at the beginning and the end of the encryption process (IP and FP) and in each round of the Feistel function (labeled P). The E box in the right image represents an expansion of the half block from 32 to 48 bits, and each of the S-Boxes represents a substitution table that reduces 6 input bits to 4 output bits.  The cipher also has a key schedule, which generates 16 48-bit round keys from the original 56-bit secret key.

Brute-Forcing the Data Encryption Standard

The NSA made several different modifications to the Lucifer cipher before it was accepted as the DES.  Some modifications, like changing the S-Boxes to protect against differential cryptanalysis, were designed to improve the security of the cipher.

Others, like changing the key length from 128 bits to 56 bits, may have been designed to ensure that the NSA still had the ability to break the cipher at need.  In the end, DES wasn’t broken based upon cryptographic vulnerabilities (though some have been identified), but by a brute force attack taking advantage of the limited keyspace.  DES was first broken in 1997, paving the way for the Advanced Encryption Standard.

DH and RSA: Asymmetric Encryption

The original encryption algorithms are all symmetric encryption algorithms.  These systems require both the sender and recipient of a message to both have access to the same encryption key.  This requires that the users have the ability to set up a secure channel to transmit this key before encryption can begin.

However, in the 1970s, the invention of asymmetric cryptography changed this.  A series of encryption algorithms developed by the UK’s GCHQ made use of mathematical one-way functions to implement asymmetric encryption.  These algorithms allowed two parties to create a shared private key over a public channel or let a user generate a private/public keypair where the public key can be used for encryption of messages that can only be read using the private key.

The one way functions used in most asymmetric cryptography are the factorization and discrete logarithm problem.  The security of these schemes relies on the fact that operations like multiplication and exponentiation are “easy” (with polynomial difficulty) and the inverse operations, factoring and logarithms, are “hard” (with exponential difficulty).  Asymmetric encryption algorithms are designed to allow legitimate users to perform “easy” operations while forcing attackers to solve “hard” problems. The asymmetric relationship between the attacker and the defender means that it’s possible to create algorithms that are usable but have an arbitrary level of security against brute-force attacks.

While GCHQ cryptographers originally developed asymmetric cryptography in the early 1970s, their results and algorithms remained classified until 1997.  As a result, the algorithms were independently discovered by private researchers and are named after these parties.

The original key exchange protocol was invented by Malcolm J. Williamson of GCHQ in 1974 and is named after Whitfield Diffie and Martin Hellman, who discovered it in 1976.  The RSA algorithm for asymmetric encryption and decryption was discovered by Clifford Cocks in 1973 and a more general version was invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1976.  Since then, several different asymmetric encryption algorithms have been invented.

Coming Up: Modern Cryptography

The encryption algorithms presented in this article are largely broken, with the exception of the asymmetric algorithms Diffie-Hellman and RSA.  However, even the security of these algorithms are threatened by advances in computers. The final post in this series describes some of the modern encryption algorithms currently in use or development that are designed to replace these algorithms as they are broken.