Introducing Symmetric Ciphers

This blog post by Polymesh software developer Eric Richardson is the first in a series covering applied cryptography. The goal is for readers to be comfortable with, and know the advantages and disadvantages between the common algorithms.

Used in blockchain technology, cryptography is a method of securing and protecting data during communication.

This blog post gives an introduction to symmetric ciphers, which use symmetric algorithms to encrypt and decrypt data.

Encryption and Decryption

The two basic cryptographic functions are encrypt and decrypt.

Encryption turns plain text into something that appears random and meaningless. This output of the encrypt function is known as cipher text. 

Decryption is the inverse. The decrypt function takes cipher text as its input, returning the original plain text message.

For cryptography to properly secure and protect data, the cipher text should reveal nothing about the original message without the “secret” for decrypt. There are a handful of methods capable of this, broadly classifiable between symmetric and asymmetric.

Symmetric cryptography

The simplest method to encrypt and decrypt —and also the most secure— is known as the one-time pad. The pad is a shared secret used for both encrypting and decrypting.

Pad management places significant burden on its users because the secret needs to be shared with every recipient a user wishes to communicate with. Additionally, the collection of letters for the pad will be equal to the number of letters in the message, so the file can end up quite large.

In order for the one-time pad to encrypt communication, this large file needs to be shared between each party ahead of time. Also, if any part of it is reused, security will be weakened.

This makes the one-time pad unusable for many use cases. In practice, the use of a one-time pad is relatively niche and most commonly reserved for securing sensitive diplomatic channels between nations.

Because both parties need to share a secret ahead of time, the one-time pad can be classified as a symmetric cipher. This means that there is only one key which can both encrypt and decrypt messages. 

Asymmetric cryptography

In contrast, asymmetric cryptography has two keys, referred to as a  public and private key, based on how they are shared. In asymmetric cryptography, encrypt and decrypt may accept different values, but they maintain their inverse relationship with the key pair. On distributed ledgers the public key is encoded and referred to as an address.

Asymmetric cryptography involves great mathematical complexity and has heavy performance penalties. In practice, asymmetric cryptography is used to either sign a message, or encrypt a symmetric key, which can then efficiently encrypt the communication.

While asymmetric cryptography enables many use cases not possible with symmetric, it is almost always preferable to encrypt using a symmetric cipher. Many modern systems combine both types to provide the best of both for users.

For now in this blog, the focus is on symmetric cryptography.

Setting up our example: Alice, Bob, and Eve

To illustrate examples, we will use Alice, Bob, and Eve.

Alice and Bob wish to communicate over some channel controlled by Eve—perhaps they are friends playing a game, or perhaps Alice and Bob are undercover and Eve is a counterintelligence agent, or perhaps they are ancient generals communicating via unreliable messengers. Whatever imaginative flavor you desire, there are a few points to keep in mind: these characters are ideal and always perform their duties perfectly. Additionally, they lack corporeal bodies. In real systems, however, there are effective but crude attacks through other means.

Whatever communication channel Alice and Bob intend to use to exchange messages over, they will be unable to use it to share the one-time pad. Instead they will need to share it in another manner. This out of protocol communication takes place over a side channel. We will ignore any inconvenience it places on Alice and Bob to securely exchange the pad, but practically, the exchanging of pads not using the internet, is a major limitation preventing broad adoption of the one time pad.

Giving context: the one-time pad

The one-time pad was introduced in 1882 by Frank Miller, a banker by trade, who used the telegraphs for his work. Miller published his code so other bankers would be able to conduct their business, authorize payments and settlement over telegraphs, without placing their reputations and careers in the hands of unknown, and untrusted telegraph operators.

The patent for the one-time pad was awarded to a reinvention by Gilbert Vernam in 1919. The patent and name recognition being rewarded to a later inventor is a common occurrence in cryptography, especially as many leading experts are bound by strict non–disclosure agreements.

To this day, the one-time pad serves as the security standard that all other ciphers are compared to. A message properly encrypted with the one time pad cannot be decrypted without knowledge of the secret stored on the pad.

The one-time pad today

Traditionally, a pad was a paper encoded with random words. In the era of modern computers, it’s now a file consisting of random bits, represented as 1 and 0 or true and false, depending on your preference. This one-time pad can be any length, but each bit can only be used once, as implied by “one time”. 

The pad length is the maximum amount of data that can be encoded before a new pad will need to be exchanged. Ideally the bits originate from a device reading from some kind of physical phenomena. Flipping a coin could work, but would be very tedious. Unix machines provide /dev/random as a source based on mouse movements and the like. Cloudflare famously uses a camera feed of a wall of lava lamps.

Entropy in viewing a binary file

Viewing a binary file will usually result in an unintelligible display most commonly represented by hex digits (base 16, 0-F), which allows a single character to represent four binary bits. However, this secret can also take less compressed forms, like a wordlist or code book. The word entropy is used as a formal measure of randomness or uncertainty and can be thought of as the opposite of information. Cryptography is only concerned with the ideal “compressed” representations of bits. However, the application layer still retains flexibility in how entropy is represented. Each bit of entropy is equal to the unknown outcome of a coin flip.

The popular BIP-39 wordlists (mnemonic code used by many crypto wallets) contain 2048 words. This means there are 11 bits of entropy per word as 2^11 = 2048 possibilities (or 1 << 11). For every additional word, there are 2048 times more possibilities added, or eleven doublings. Another way of thinking about it, is if your only source of randomness is a coin, it would take 11 flips to select one random word for a mnemonic phrase.

This means 12 mnemonic words encode the 128 bit entropy threshold to be considered secure as of 2023. 24 BIP-39 words can provide 256 bits of entropy which is considered very secure. Historical examples will use normal letters, but with some conversion operations can be normalized into theoretical binary equivalents for analysis.

Back to our example: sharing the one-time pad

Once the pad is made, Alice needs to share it with Bob. This sharing cannot happen over the network—otherwise Eve will see it.

This is the major drawback of one-time pads. A pad needs to be exchanged for each point to point connection in the network, and consumed with use. In practice, the side channel used to share the pad is a major vulnerability and inconvenience. In theory, however, the one-time pad is highly secure because it offloads the burden to the end users.

How the one-time pad is shared is up to Alice and Bob to figure out. For our example, assume Alice and Bob share the pad securely. Perhaps Alice records it on a USB drive and gives it to Bob next time they meet in person.

Binary and the XOR function

For Alice to encrypt a message, it needs to be represented in binary (technically, this is already the case for any data on a computer).

Let's suppose Alice wants to say:

This can be represented with two ASCII bytes:

Alice will also use the 2 bytes of the pad she’s shared offline with Bob. For this example, assume it’s:

Each bit of the message will be XOR (“exclusive or”) with the random bits. The XOR function returns "1" if and only if each input is different. It can be defined with the phrase “one or the other, but not both” or with a truth table:

‍

‍
XOR  is a fundamental cryptographic function. XOR will mix all of B’s entropy with A’s information, effectively obscuring the message. Eve can never be sure if a ciphertext bit is because of the message or the pad. XOR, with the same secret B, is also its own inverse. Anyone with the secret is able to remove the entropy added by B, recovering A. In order for Bob to decrypt the message and uncover the hidden information, he will apply the same portion of pad Alice used. Sometime XOR is represented by the symbol ⊕.

To illustrate:‍

Alice performs A ⊕ B = C

‍
To verify, Bob will do the same XOR operation with the same pad bits Alice used.

Bob performs C ⊕ B = A

‍
XOR's properties of being its own inverse make it especially useful in cryptography. Although tedious to do by hand, computers are capable of quickly XORing large volumes of data. The promise is knowing B is the only way to transform C back to A. The secret pad is needed to decrypt the message.

If Alice sends a second message while Bob sends a reply using the same section of pad, then Eve has a good chance of decrypting both messages. Eve can XOR the two cipher texts which will remove the randomness introduced by the pad. The result will be as if Alice and Bob XOR their plain text messages together. Because natural language bytes have certain statistical distributions, Eve has a shockingly good chance at inferring the original messages thanks to her cryptanalysis skills and computational resources. For Bob to encrypt his messages, he should have his own pad that was shared with Alice.

Summarizing the symmetric cipher

To summarize, a one-time pad consists of the following three steps:

1. The sender generates and shares the pad offline
2. The sender encrypts the message by XORing each bit with the pad
3. The receiver XORs the received message with the same portion of the pad, recovering the original message.

Encrypting our messages is good, but for many use cases it’s neither sufficient nor desirable to encrypt. Another application of cryptography is to ensure messages really came from Alice and weren't tampered with. Although Eve cannot extract information, she could still flip random bits in the message without  Bob detecting. If Eve flips random bytes in a sentence, it will likely decrypt to a corrupted character. However, if Eve flips a random bit in a number, then Bob might not be able to detect the mistake. Modern cryptography systems not only encrypt communication, but also authenticate that the message is true to what Alice wrote. Of course Eve, with control of the network, could always choose to not deliver Alice’s messages––but this is an issue for another post.

Overall, the idea behind symmetric ciphers is to generate a shared secret to be used to XOR with the plain text message. As long as there is no discernible pattern in B, then the cipher text produced has no information contained in A embedded into it. Symmetric ciphers use discrete math to generate a series of secret blocks which will then be used in place of the one-time pad as a source of entropy. 

‍

Symmetric encryption ciphers can be broadly categorized between block ciphers, and streaming ciphers. The primary difference being a block cipher produces random bits in batches, and a stream cipher produces a continuous stream. A notable block cipher is AES, and ChaCha20 is an exemplary stream cipher. 

These algorithms alone only ensure confidentiality of the data, but do not guarantee the messages weren’t blindly tampered with, which requires message authentication. It is common to use encryption along with authentication in a single system. The second post will cover message authentication, and the cryptographic primitives needed for it.

Further Reading

Here are some interesting links if you want to learn more about these concepts.

A historical paper on the one-time pad – The last two pages have a scan of Miller's preface to his 1882 code book. Cryptography applied to electronic payments has over a century of history!

XOR explained with academic rigor - This page covers XOR in full academic rigor. Worth a read if you really want to understand the operation and boolean logic.

Verona Project – This Wikipedia page covers the Soviet pad reuse leading to the revelation of many of their espionage activities. This gives a sense of the effort spent on cryptography and cryptanalysis, and how even seemingly small defects have been exploited in the real world.

Suggested Prompts

It can be useful to review and double check your understanding using a large language model like ChatGPT. Here are some prompts to get you started.
‍

> Given the security of the one-time pad, why isn't it more widely used?

> How different would the internet be if the only means of encryption were the one time pad? Please speculate on what kinds of services we have today that would not be possible, and what new kinds of businesses would fill the needs currently satisfied by asymmetric cryptography.

> How dangerous is reusing the one-time pad? Can you provide examples of reuse causing an information leak in the real world?

> Please ask me a series of questions that will test my knowledge of cryptography relating to the one-time pad.

The next instalment by Polymesh developer Eric Richardson will cover message authentication and cryptographic primitives, namely cryptographic hash functions like SHA256