Symmetric key cryptography

Introduction

In this lesson we will look at symmetric key cryptography which secures much of the data at rest and in transit by virtue of its efficiency.

By the end of the lesson we will have covered:

• What symmetric key cryptography is
• Python code examples demonstrating the use of symmetric key cryptography
• A look at applications of symmetric key cryptography
• Symmetric key cryptography applications
• The security of symmetric key cryptography
• Threats to these algorithms from both classical and quantum computers

Introduction to symmetric key cryptography

Symmetric key cryptography (SKC) is the oldest and most intuitive form of cryptography. With SKC, confidential information is secured through symmetric key encryption (SKE), that is, by using a single secret key for both encryption and decryption.

SKC involves:

• An encryption function that converts a given plain text instance to ciphertext while utilizing a secret key
• A decryption function that inverts the operation by converting the ciphertext back to plain text using the same secret key

Plain text can mean any kind of unencrypted data such as natural language text or binary code whose information content is in principle directly accessible, while ciphertext refers to encrypted data whose information content is intended to be inaccessible prior to decryption.

An algorithm that describes the encryption and decryption operations using a shared secret key is also called a symmetric cipher.

Figure 1. Symmetric key encryption of a given plain text to ciphertext and decryption back to plain text using the same key.

Properties of symmetric key cryptosystems

A symmetric key cryptosystem should ensure the following properties to secure messages-both statically stored data and/or communications over some transmission channel:

• Confidentiality: Refers to the property that the information content of encrypted messages is protected from unauthorized access.
• Integrity: Refers to the property that any tampering of encrypted messages during storage or transmission can be detected.
• Authenticity: Refers to the property that the receiver of a message can verify the identity of the sender and detect impersonation by an unauthorized party.

Furthermore, these properties should be realized in a setting where the algorithms or ciphers used for encryption and decryption may be public and where access to the information content of encrypted messages is controlled exclusively through access to the secret key.

Implementing a secure symmetric key cryptosystem therefore involves two main tasks:

1. Employing a robust symmetric key encryption algorithm resistant to cryptographic attacks.
2. Ensuring confidentiality in the distribution and management of secret keys.

In this lesson, we will discuss aspects related to the first task, which forms the primary concern of SKC technology. The second task, however, needs solutions that fall outside of SKC itself and will be introduced later.

Illustration of symmetric key encryption using python

We show a simple example of the encrypt and decrypt operations using the classical Caesar shift cipher and the modern Advanced Encryption System (AES), which has been the standard for symmetric key encryption since 2001.

First we set up some Python libraries that provide the needed symmetric key encryption ciphers, and then define the plain text we wish to encrypt.

Requirement already satisfied: secretpy in /home/travis/virtualenv/python3.11.0/lib/python3.11/site-packages (0.12.0)

Note: you may need to restart the kernel to use updated packages.

Given plaintext: this is a strict top secret message for intended recipients only

We will see how to encrypt and decrypt it using two different symmetric key encryption methods:

1. The classic Caesar shift cipher
2. The modern Advanced Encryption Standard AES-256 protocol

Caesar shift cipher:

Caesar shift encryption involves defining

• An alphabet of possible characters to encode
• A shift value which can be between 0 (unencrypted) and the length of the alphabet. We consider this the key.

It is known as a monoalphabetic substitution cipher since each letter of the plain text is substituted with another in the ciphertext.

In this example we will use lowercase letters of the alphabet.

Let's start by setting things up.

Caesar shift secret key: 5
alphabet: ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ')

Encrypt the plain text to get ciphertext for the Caesar cipher.

Encrypted caeser shift ciphertext: ymnxenxefexywnhyeytuexjhwjyerjxxfljektwensyjsijiewjhnunjsyxetsqc

Decrypt the ciphertext back to the original plain text using the same key used for encryption.

Decrypted caeser shift plaintext: this is a strict top secret message for intended recipients only

Advanced encryption standard (AES) cipher

We now encrypt the plain text using AES, a popular symmetric key encryption algorithm.

We start by creating the key, in this case, a random 16-letter string.

AES secret key: xooyapiszrhovbmm

AES supports multiple operating modes and requires we specify which to use.

We choose the Cipher Block Chaining (CBC) mode provided by the modes.CBC class of the cryptography library. The CBC mode of AES uses randomness for additional security. This requires specifying a random Initialization Vector (IV), also called a nonce. We will use a random string for this as well, just like we did for the key.

AES initialization vector: vygqlyihkolhmyzo

We can now instantiate an AES cipher on behalf of the sender of the secret message. Note that the initialization vector is passed to the modes.CBC class to set up the CBC mode of operation.

We will then encrypt the plain text to send.

Encrypted AES ciphertext: b'&\xf7X?\x88\xdd\xd3kQD\xda\x04(\x9b\xa7\x00\xc9)\xfc=@6\x065\n\xbe\xec%\xa1\x9dM)zR$\x9fed\x0c\x15\x88N$\xa9U\xd7\x13\x02\xcb\xd6\x0c\xcf-\xeb\xd8s3I\xed\xc5H\xf5p\xe9'

To decrypt it, let us instantiate an AES cipher on behalf of the receiver. Note that the intended receiver has access to both the secret key and the initialization vector, but the latter is not required to be secret.

Decrypted AES plaintext: this is a strict top secret message for intended recipients only

Applications of symmetric key cryptography

While classical ciphers such as the Caesar cipher fell out of use a long time ago, modern symmetric cryptosystems such as AES are deployed in a wide range of applications, including:

1. Data encryption and decryption: SKC is widely used to protect sensitive data, whether statically stored on a device or transmitted over a network. Examples include protecting user credentials, encrypting email messages, and securing financial transactions, among others.

2. Secure communication: Common communication protocols such as SSL/TLS use a combination of symmetric and asymmetric key encryption to ensure the confidentiality and integrity of data exchanged between two parties. These messages are encrypted and decrypted using symmetric key encryption which uses a shared key. The key used in symmetric key encryption is securely exchanged using asymmetric key encryption which uses a public-private key pair. Symmetric key encryption is much faster and hence can be used for encryption of messages of large size.

3. Authenticity verification: In some settings, SKC is employed through techniques like message authentication codes (MACs) and keyed-hash MACs (HMAC) to verify the authenticity and integrity of messages, ensuring tamper-resistant communication.

4. File and disk encryption: Full-disk encryption software and file encryption tools employ SKC to protect sensitive data stored on hard disks or portable storage devices.

5. Virtual private networks: VPN technologies, which aim to provide confidential communication channels free from eavesdropping, can use symmetric or asymmetric key encryption to connect remote users as well as corporate networks.

The diverse array of applications in which SKC is deployed in turn require that symmetric cryptosystems satisfy a certain set of criteria.

Principles of symmetric key encryption

In this section, we will discuss some of the basic principles underlying the security of symmetric key encryption algorithms.

Resistance to brute force attack: The most basic requirement for the security of an encryption cipher is that the key space size — in other words, the number of possible distinct keys from which someone using the algorithm could have chosen — is very large.

Resistance to cryptanalytic attack: The second basic requirement for a cipher, symmetric or otherwise, is that it can generate ciphertexts that are informationally inscrutable. To this end, a necessary but not sufficient condition from an information theory perspective is that ciphertexts should be characterized by high entropy, making them indistinguishable from random text with no discernible patterns or correlations. This way, an attacker can gain no information about the plain text or secret key by trying to analyze the ciphertext using frequency analysis or other statistical techniques.

Resistance to general forms of cryptanalytic attacks sufficient to ensure semantic security is formalized via the notion of indistiguishability . While there are several variants of indistiguishability with distinct requirements, a symmetric cryptosystem is considered to be semantically secure if it satisfies the criterion of Indistinguishability under Chosen Plain Text Attack (IND-CPA). This means that an attacker cannot distinguish between the encryptions of two different messages even if allowed to send multiple plain texts of their choosing to the algorithm and view the corresponding ciphertexts.

As we will consider later, IND-CPA typically requires the use of randomness to ensure that each time a given plain text is encrypted with a given secret key, the resulting ciphertext is unpredictably different for each encryption.

Failure modes of classical ciphers: Before the advent of modern cryptography in the 1970s, most classical ciphers in practical use failed to satisfy one or both above requirements. For instance, early substitution ciphers such as the monoalphabetic Caesar shift cipher were characterized by both a small key space size (see Table 1) and low entropy ciphertext, making them insecure against a variety of cryptanalytic attacks such as brute force attacks, frequency analysis, and known-plain-text (KPT) attacks.

Subsequent polyalphabetic substitution ciphers such as the Vigenère cipher and the Enigma machine cipher featured effectively large key space sizes, making them resistant to brute force attacks, but they were susceptible to frequency analysis and KPT attacks, respectively. Similarly to substitution ciphers, classic transposition ciphers, which rearrange letters in a message instead of substituting them, are also compromised by a variety of attacks such as anagramming, statistical analysis, brute force, and KPT attacks, among others.

Theoretically, a polyalphabetic substitution cipher known as the one-time pad (OTP) is known to be cryptographically secure. An OTP features a secret key that should be (1) composed of randomly chosen letters or bits, (2) at least as long as the original plain text, and (3) used only once. An OTP is impractical for actual applications because if the secret key — which is required to be as long as the plain text and can be used only once — could be shared securely, then so could the original plain text. The OTP instead illustrates the utility of randomness in generating secure ciphertexts.

An attacker trying to implement a brute force search through the key space to find a key that decrypts the message has to perform a number of operations proportional to the key space size.

Therefore, a large key space size provides resistance against brute force attacks by rendering them computationally infeasible. Table 1 lists the key space sizes of some well-known ciphers.

Table 1: Key space sizes of some symmetric ciphers

Modern symmetric key encryption schemes largely overcome the limitations of the classical ciphers. They produce ciphertext resistant to cryptanalysis and feature large key space sizes while also being much more practically efficient than an OTP.

Block ciphers: One class of modern ciphers — such as DES and AES — achieve security by combining the principles of confusion and diffusion originally introduced by Claude Shannon. We discuss these notions in a setting where encryption schemes work with binary representations of messages:

• Confusion: Confusion is the characteristic whereby each bit in the ciphertext depends on multiple bits of the secret key. It ensures that a small change in the secret key modifies almost all the bits of the ciphertext, obscuring the relationship between the ciphertext and the secret key.

• Diffusion: Diffusion is the characteristic whereby flipping a single bit in the plain text should modify roughly half the bits in the ciphertext and vice versa. Diffusion hides statistical relationships between the plain text and ciphertext. Ciphers with adequate diffusion satisfy the so-called avalanche criterion of cryptography.

Block ciphers implement confusion and diffusion using cryptographic structures known as substitution-permutation networks (SPNs) operating on discrete blocks of data. A SPN accepts a block of plain text and the secret key as inputs and performs a specified number of rounds of transformations to yield a ciphertext block. Each round is composed of alternating mathematical structures known as substitution boxes (S-boxes) and permutation boxes (P-boxes) or equivalent operations.

These respectively implement complex nonlinear and linear transformations on the input blocks, leading to avalanche effects in the ciphertext.

SPNs are designed in such a way that increasing the number of rounds typically increases the security of the cipher. This leads to the notion of security margin.

Security margin: The security margin of a given SPN-based cryptographic cipher is the difference between the number of rounds in the complete implementation of the cipher and the maximum number of rounds that are known to be breakable using the best-known real-world attack.

For instance, currently the best-known faster-than-brute-force attacks against AES-256 can break up to 9 rounds out of the total 14 rounds in the full cipher when used in the standard mode known as Electronic Codebook (ECB) mode. Therefore, currently the security margin of AES-256 is 5 rounds

Stream ciphers: As an alternative to block ciphers, modern cryptologists have also designed practically secure stream ciphers such as Chacha20. These ciphers utilize randomness as a fundamental part of their design and operate on pseudorandom keystreams of bits instead of discrete blocks of data.

Accordingly, stream ciphers combine a secret key and an initialization vector (IV) to seed a pseudorandom random number generator (PRNG) to produce a keystream of random bits which are then combined with the given plain text to yield the ciphertext. In this sense, stream ciphers are similar to a one-time pad (OTP) but feature shorter secret key lengths and reusable keys, which makes them more practical. However, for the same reason, they do not guarantee perfect secrecy, unlike an OTP.

Semantic security: We conclude this subsection by returning to the notion of semantic security or IND-CPA level security introduced above. The basic operations implemented by block ciphers such as S-box and P-box are deterministic. This means that in standard operating modes such as ECB, a given plain-text key pair always yields the same ciphertext, a state of affairs that is susceptible to chosen-plain-text attacks.

To achieve IND-CPA level security, block ciphers need to operate in a mode that utilizes randomness introduced via a pseudorandom initialization vector (IV) with the additional requirement that no two encryption operations use the same key-IV pair. AES supports several modes of operation, such as cipher block chaining (CBC), which are IND-CPA secure. A similar requirement also holds for stream ciphers whereby the same key-IV pair should not be used to seed the PRNG more than once if IND-CPA is desired.

Popular symmetric key algorithms

Having introduced some basic principles of SKC, we now list a few popular symmetric key algorithms to illustrate a variety of the approaches pursued in modern cryptosystems. Modern block ciphers and stream ciphers are both employed in different contexts as illustrated below.

1. Advanced Encryption Standard: AES, already introduced above, is currently the de facto standard for SKC owing to its security, efficiency, and performance characteristics. AES features fixed key sizes of 128, 192, and 256 bits and uses a multiround substitution-permutation network) (SPN). AES is known to be resistant to a wide range of cryptanalytic attacks. AES was announced as a Federal Information Processing Standard (FIPS) for symmetric key encryption in the United States in 2001.

2. Data Encryption Standard (DES) and Triple Data Encryption Standard (3DES): DES was a block cipher originally invented by Horst Feistel and coworkers at IBM in the 1970s and employed a SPN with a relatively short 56-bit key. DES was adopted as a FIPS for symmetric key encryption in the United States until the late 1990s when it was shown to be breakable using brute force attacks with specialized hardware due to its small key space size. Subsequently, 3DES was introduced as a replacement and applies the DES algorithm three times with different keys, increasing the key length to 168 bits. Nevertheless, 3DES is largely superseded by AES.

3. Blowfish and Twofish: Blowfish and its successor, Twofish, are block ciphers proposed by cryptographer Bruce Schneier in the 1990s. Blowfish and Twofish allow variable key lengths of up to 448 bits and 256 bits respectively, offering some flexibility in the tradeoff between security and performance. Unlike AES, they also feature key-dependent S-boxes. Twofish was one of the finalists in the NIST competition to select the Advanced Encryption Standard but ultimately was not chosen. Both algorithms are currently considered secure.

4. Rivest Ciphers (RC2, RC4, RC5, and RC6): The Rivest Cipher (RC) family of symmetric key algorithms was designed by Ron Rivest starting in the 1980s. RC2 was an early 64-bit block cipher while RC4 was stream cipher widely-used in security protocols related to web-traffic due to its simplicity and speed. Neither is currently considered secure. RC5 and RC6 are SPN based block ciphers designed with customizable block size, key size, and number of rounds. Like Twofish above, RC6 was a finalist in the NIST AES competition and is considered secure.

5. Salsa20 and ChaCha20: Salsa20 and ChaCha20 refer to a related family of stream ciphers designed by cryptographer Daniel Bernstein in the 2000s. Salsa20 is a part of the eSTREAM European Union cryptographic validation project's profile-1 portfolio. ChaCha20, a modification of Salsa20, was designed to increase diffusion characteristics and performance. Currently, ChaCha20 is considered secure and offers better performance in the absence of dedicated AES hardware acceleration. Therefore, ChaCha20 finds use in certain settings such as network protocols like QUIC and mobile devices with ARM-based CPUs.

Advantages of symmetric key cryptography

After outlining the properties of symmetric key cryptosystems and some of the principles that underlie their development, we now list some of the main advantages of SKC relative to asymmetric key cryptography. The latter will be discussed in subsequent lessons.

1. Speed and efficiency: Symmetric key algorithms are more suitable for encrypting large volumes of data or for use in real-time communication scenarios since they are generally faster and less resource intensive than their asymmetric counterparts. SKC algorithms such as AES scale linearly with the size of the plain text and do not involve algebraically intensive mathematical operations. See Tomoiaga et al. for a detailed review of the performance characteristics of AES.

2. Scalability: Owing to their relatively low computational overhead, symmetric key algorithms scale well with the number of users and the amount of data being encrypted.

3. Simplicity: Symmetric encryption protocols are often easier to implement and understand compared to asymmetric key approaches, making them attractive for developers and users.

Challenges and limitations of symmetric key cryptography

Despite the advantages, symmetric key cryptography also has some challenges and limitations:

1. Key distribution and management: In SKC, both the sender and the receiver of a message must have access to the same key, which must be kept confidential from unauthorized parties. If the key is somehow intercepted or compromised by a third party then the security of the encrypted data is also lost. The secure distribution and management of the secret key is therefore a major challenge. However, the solution to this challenge lies outside of SKC itself.

2. Lack of non-repudiation: Non-repudiation refers to the ability to prove that a specific party has sent a message. In SKC, since the same key is used for both encryption and decryption, it is not possible to determine which party has created a particular ciphertext. In contrast, asymmetric key cryptography provides non-repudiation through the use of digital signatures.

To address these challenges, symmetric key cryptography is often used in combination with asymmetric key cryptography. For instance, one often uses asymmetric key encryption to securely transmit a relatively short shared secret key between sender and receiver. This enables the subsequent use of symmetric key encryption to transmit much larger data and messages efficiently.

Quantum computing and symmetric key encryption: Risks and mitigation

Quantum cryptography offers a promising avenue for risk mitigation in the digital age, with the adoption of quantum-safe products poised to secure our information against the looming threat of quantum computing advancements.

In what follows, we discuss the risks posed by quantum computers to symmetric key encryption schemes introduced in the previous section and outline some potential pathways to mitigating the risks.

Quantum cryptographic attacks

There are two distinct classes of quantum threats to traditional cryptographic algorithms:

1. Quantum brute force attacks: These refer to situations where the attacker uses a quantum computer to execute a specialized quantum algorithm to conduct a brute force search through the key space of a symmetric cipher. The most relevant quantum primitive for enabling this kind of attack is Grover's algorithm.

2. Quantum cryptanalytic attacks: These refer to situations where quantum computers are deployed to execute cryptanalytic attacks that aim to recover either the secret key or plain text in a more efficient manner than a brute force search. The possibility of executing successful quantum cryptanalytic attacks depends on many factors having to do with the mathematical structure of the cipher being analyzed as well as potential weaknesses in specific implementations.

Risk mitigation strategies for quantum attacks

Before we discuss risk mitigation strategies for quantum attacks, let's introduce the notion of a cryptographic cipher's security level:

Security level is a measure of the difficulty of breaking a cipher measured in terms of the number of computational operations that a successful break of the cipher would require.

Typically, the security level is expressed in bits; that is, in general, a cipher offers N-bit security if it requires $\mathcal{O}(2^{N})$ operations to break it. On classical computers, assuming a symmetric cipher is otherwise cryptographically secure, the security level is roughly synonymous with the key length.

For instance, the security level of AES-128, which features a 128-bit key, is generally considered to be 128 bits because it would require on the order of 2$^{128}$ operations for an attacker employing a classical computer to try out all possible 128-bit keys in the key space.

Brute force attacks and mitigation

Quantum brute force attack risk: A quantum brute force attack changes the above assessment because Grover's algorithm enables an attacker with a suitable quantum computer to search the key space of a cipher quadratically faster than any classical computer.

For instance, the same brute force attack on AES-128 with Grover's algorithm could potentially be achieved with just 2$^{64}$ operations. Therefore the security level of AES-128 is reduced from 128 bits to 64 bits when faced with a quantum adversary running Grover search. Since computational power has traditionally grown exponentially with time, currently a security level of 64 bits is considered insecure, which means that once sufficiently capable quantum computers are realized, AES-128 will have to be abandoned.

The same kind of calculation applies to other symmetric block or stream ciphers whereby the security level for a given key length is effectively halved by Grover's algorithm.

Quantum brute force attack risk mitigation: The above considerations imply that an obvious way to resist quantum brute force attacks is to at least double the minimum key lengths used for symmetric key encryption.

Therefore, to ensure 128-bit security with regard to quantum brute force attacks, one would simply use ciphers such as AES-256 or ChaCha20 that employ 256-bit keys. This is considered secure because even with quantum computers, performing 2$^{128}$ operations to break ciphers is infeasible in the foreseeable future.

While theoretically simple, this proposed solution of doubling key sizes is not without costs, as longer key sizes imply additional computational cost for routine encryption-decryption tasks, along with slower performance, more memory requirement, and additional energy use.

Cryptanalytic attacks and mitigation

Quantum cryptanalytic attacks risk: The risk to symmetric key cryptosystems posed by quantum cryptanalytic attacks is currently being actively researched by cryptographers. The combination of classical and quantum computing potentially expands the array of tools available to attackers to probe weaknesses in the mathematical structure of ciphers, and a wide range of new quantum cryptanalytic attacks are currently being proposed. These include quantizations of known classical techniques such as linear and differential cryptanalysis as well as new attack modes with no classical counterparts.

A recent quantum cryptanalytic study of the Advanced Encryption Standard (AES) found that the cipher remained resistant to various known quantum cryptanalytic attacks and continued to exhibit an adequate post-quantum security margin. However, some studies have found that various symmetric ciphers considered classically secure are easily compromised by so-called quantum chosen plain text attack. Therefore, new primitives for symmetric key encryption designed specifically for the post-quantum era have also been proposed.

Quantum cryptanalytic attacks risk mitigation: Given that quantum cryptanalysis as a discipline is in its infancy, it may be the case that post-quantum symmetric cryptography will undergo rapid evolution as new quantum cryptanalytic attacks arise and as new ciphers resistant to them are proposed and evaluated. Therefore, the best strategy to mitigate the risk of quantum cryptanalytic attacks in the foreseeable future is cryptographic agility (or crypto-agility). Crypto-agility refers to the ability of an information system to quickly and easily adopt alternative cryptographic primitives without disruptive changes to the system infrastructure.

Crypto-agility requires the ability to replace obsolete algorithms used for encryption, decryption, digital signatures, or other cryptographic functions with minimal effort and disruption. Crypto-agile systems will be well positioned to manage the transition to post-quantum symmetric key cryptography.

Summary

Symmetric key cryptography provides robust and efficient solutions for securing digital information. The simplicity of using the same key for both encryption and decryption enables high performance and scalability, making SKC suitable for a wide range of applications.

The security of SKC relies on algorithmic resistance to cryptographic attacks as well as proper secret key management. Modern symmetric key cryptosystems combine the principles of confusion, diffusion, and randomness, in conjunction with adequate key sizes, to achieve semantic security. Secret key management, while crucial, cannot be achieved with SKC alone.

Understanding the properties and limitations of SKC will enable developers to design, implement, and deploy secure information technology solutions using approaches included longer key sizes as needed, and the use of new algorithms.

The advancement of quantum computing and quantum learning introduces a new dimension to symmetric key cryptography. Quantum computers have the potential to unravel the security provided by classical symmetric key algorithms, prompting the need for quantum-resistant cryptographic approaches to ensure data privacy and protection in the face of evolving technological landscapes.