A Tool for Information Warfare Becomes a Field of Science

Five Essays on Cryptography (2/5)

Cryptography is one of the core disciplines that we use to protect digital information today. It is part of the larger area of Information Security which has become recently one of the most discussed topics across industries. This series of five articles is aimed at those who would like to have an overview of the domain of cryptography, a bit of its history, and a grasp on important concepts and recent developments.

All articles in this series

• 1 Cryptography is Interwoven in our Daily Life
• 2 A Tool for Information Warfare Becomes a Field of Science
• 3 Asymmetric and Symmetric Encryption
• 4 Cryptographic Hashes and Credentials Management
• 5 The Use of Cryptography in our Economy (to appear)

Special thanks to my friend Philipp Jovanovic (Twitter @Daeinar) for sharing his expert opinion on this series of articles.

Comments, Feedback: Laurent Balmelli (Twitter Laurent Balmelli)

The Historical Reasons for Encryption

It is commonly agreed that the first usage of encryption for military purposes dates back to the Romans and in particular at the time of Caesar. This was reported by the Roman historian Gaius Suetonius Tranquillus, who wrote during the early imperial era of the Roman empire. However, earlier traces of cryptography can even be found in ancient India and Greece. In the Kamasutra, it has been documented that some form of cipher was used for the purpose of secret communication between lovers.

The method described below is today referred to as a Caesar cipher. A cipher refers to an algorithm used to encrypt data. Encryption in these days was applied directly to characters, as opposed to today where it is applied to bit representations as used by computers.

Messages were encrypted by simply shifting each letter composing a word in a sentence by a fixed number of positions in the alphabet, while preserving the spaces between words unchanged. For example the word “help” becomes “khos” when each letter is shifted by 3 positions in the alphabet. When the end of the alphabet is reached, the shift was simply wrapped around and restarted from the first letter.

In this setting, the number of shifts necessary to retrieve the original message would be a shared secret between the two parties willing to communicate in confidentiality. Since in some cases, it might have been difficult to share this secret, for simplicity it is reported that the shift was always three characters.

This method would provide some confidentiality, although whatever the shift used, it is easy to retrieve the message by trying all the possible shifts. Regarding integrity, i.e. that the message had not been modified while in transit, and authenticity, i.e. the message was indeed coming from the person who claimed to be the sender, these two properties would be guaranteed with an envelope and a seal of wax, respectively.

The Evolution of Encryption Methods

The Caesar cipher got improved in the 16th century with the Vigenere cipher, by an Italian named Bellaso, but the name was misattributed to a Frenchman called De Virginère. The Vigenere cipher is similar to the one used by Caesar except that characters in words are shifted according to a series of subsequent shifts, represented by a word (which represents a key).

Note that the same encryption scheme was used during the Confederate War in the US, and also during the Spanish-American War in 1898. During the former, militaries in charge of secret communications would use a Confederate cipher disk to decode the messages.

For example, a key will be typically a secret word, e.g. “enemy”, whose letters in the alphabet reveal the different shifts that we need to apply to the text that we wish to encrypt. And this case, “e” would require to apply a shift of four, “n” will require to apply a shift of 13, the next “e” a shift of four as well, etc. Hence, trying to encode again “help” gives us:

• h is shifted by four, i.e. l
• e is shifted by 13, i.e. i
• l is shifted by four, i.e. p
• p is shifted by 14, i.e. t

Hence, the resulting ciphertext is ‘lipt’. To decode the ciphertext into plaintext again, just revert the shifts. Note that spaces between words are ignored and there is no differentiation between small and capital letters. Finally, note that if the key is shorter than the word to encode, it is simply repeated.

Still today, keys used to encrypt the communication during the Confederate War, i.e. the shared secrets between allies, are subject of discussion by historians and amateurs on-line. In particular, not all messages of this era have been apparently decoded and volunteers are still working today on decrypting them. Note also that it was reported that the Swiss army used the Vigenere cipher for communication during World War 1.

Interestingly such a basic encryption method was actually sufficient to provide a fair amount of confidentiality during early wars. This is because messages were short, and as a result it was difficult to deduct the key for the lack of data. In contrast, access to data allows for a so-called frequency analysis based on frequencies of letter appearances in a given language, which permits to an attacker estimate the value of the key. The method also provided a large number of possibilities for key combinations, and trying many of these combinations by hand was difficult. Finally the secrets only need to be kept for short periods of time, typically it is believed that, during most war activities the need for confidentiality was only a few hours.

Note that both in the case of the Caesar and the Vigenere cipher, there is a need for the parties to share a secret key. Without sharing a key, it is not possible to decrypt the communication. This is generally the case for all encryption schemes that use the same key for encryption and decryption. Such schemes are referred to as symmetric encryption schemes.

A central problem with symmetric encryption schemes is that this method does not scale because of the need to share a secret. This is clearly infeasible if a physical distance separates end-points and there is no means for them to communicate safely otherwise.

Government-Sponsored Encryption

Evidently the need for encryption has not abated in modern times and national security agencies around the world have been researching the topic and often keeping breakthrough research results secret for some time.

In the US, starting August 1974 the NSA has been publishing its own magazine on cryptography, whose issues are usually classified. However, declassified issues (PDF documents) of this magazine can be found today online.

Up to the early 90's, the US Air Force hosted a center called the Cryptologic Support Center. Recently, with the increasing integration of cyber security operations in the military, encryption and more generally the science of cryptography has been integrated in military divisions to deal with the needs for cyberwar. Note that, if you are interested in the history of cyberwar and how cryptography has played a role, read Fred Kaplan’s Dark Territory.

Symmetric key cryptography has been heavily researched by governments for the purpose of military. The US government has created multiple standards in this area and many are still in use today. One of the most popular is the Advanced Encryption System (AES) which typically supports today encrypted communications over the internet, i.e. when using the HTTPS protocol.

More generally, today there are many standards in cryptography which are usually classified by their usage, for example encryption (as I’ve discussed so far), digital signing -a topic that we will visit in the next article of this series - and others such hashing and infrastructure. I am discussing each of these applications in this series of articles. In the US, the National institute of Standards and Technology (NIST) has been defining cryptographic standards that are used today in the US and internationally.

Differentiate the Different States for Encryption

Recall that primitive ciphers such as the Caesar and the Vigenere were working directly on letters of the alphabet. Today, modern encryption is working on bits of data, i.e. the zero and ones that are used by our computers to represent information. Moreover data is often classified as being in one of the following three states: at rest, in transit or in use.

Data-at-rest refers to data when it is stored and not used, i.e. read or modified. Storage is achieved using a physical device such as a hard or solid state drive. Data-at-rest encryption typically refers to your hard drive being encrypted using one of the products that I presented in the first article of this series, for example BitLocker, FileVault and others.

Data-in-transit refer to data as being transmitted between two receivers, for example during an online communication. Data-in-transit encryption is typically achieved with a secure protocol such as TLS, the encryption protocol used in HTTPS (that I will discuss later in this series).

Finally data-in-use refers to as data when it is being accessed and updated (for a different purpose then encryption or decryption). For example, if you would like to consult or modify the amount available on your bank account and this information is encrypted, you will first have to decrypt this information in order to access it and updated it. This is usually not done on the data in encrypted state itself.

Being able to access and process information in encrypted form is known as homomorphic encryption. This is often referred to as the holy grail to cryptographers. It allows updating information without ever decrypting it. This is an actual area of research and a first scheme was created in 2009. Recent results in this area are very promising (in particular, progress in computational efficiency) and could soon revolutionize processing of encrypted data.

Central Topics in the Field of Cryptography

Remember that I first introduced encryption as a means to guarantee data confidentiality. We will see in the next article that, asymmetric schemes also exist and are essential in modern data security, because they address the shared secret problem that I evoked several times here. In other words, these schemes allow people to agree on a key to use to securely exchange data.

Another important component in cryptography is hash functions. These functions are so-called one-way functions, in the sense that they can only be computed forward and not reversed. There are many hash functions available today (including outside cryptography) and their use is generally to guarantee the integrity of information, i.e. that it has not been tampered with.

Finally, digital signing is yet another important component in cryptography because it allows addressing the problem of message authenticity, in addition to non-repudiation, i.e. as a result of using an asymmetric scheme where no key exchange is required beforehand.

Note that message authentication is possible with symmetric schemes as well, but non-repudiation is generally not guaranteed because the same key is used to generate and verify the authenticity of the message (which assumes that parties need to agree on it). Digital signing has an important purpose in many applications across industries. Perhaps one of the most popular ones recently is the Blockchain. I will also explore all these topics in this series of articles.

This is all for now. In the next article, I will compare asymmetric and symmetric cryptography, as well as discuss their history and main usages. Thanks for your feedback and comments!

Check my other articles about security, technology and societal aspects. Feel free to send your questions on Twitter at @laurentbalmelli.