Demystifying Encryption: Symmetric Encryption, Public-key Encryption, and Hybrid Encryption

Introduction

In this blog I provide a technical overview of encryption, primarily focusing on two of the most widely used encryption algorithms today - AES and RSA.

What is Encryption

Encryption is the process of encoding information, which converts the original representation of the information known as plaintext into an alternative form known as ciphertext. The goal of encryption is to ensure confidentiality of information.

There are two essential components to encryption - the encryption algorithm called a cipher and a secret value called the key. The algorithm describes the step by step process of how data is encrypted, and the key is a randomly generated value. Because generating truly random values is actually very difficult, an encryption scheme usually uses a pseudo-random encryption key.

Encryption itself does not prevent interference, instead it denies the intelligible content to a would-be interceptor. The key used for decrypting encrypted information is shared only with authorized parties; therefore only authorized parties can decipher a ciphertext back to plaintext and access the original information. The security of encryption can be evaluated by assessing how likely it is that unauthorized parties would be able to guess/reconstruct the decryption key. Cracking the encryption by guessing the decryption key is practically impossible in modern encryption techniques, because they use algorithms for generating encryption/decryption keys that ensure that guessing the key is so computationally expensive to an extent that it is impossible.

Two of the most widely used encryption algorithms today are AES (Advanced Encryption Standard) and RSA (Rivest-Shamir-Adleman), which represent two different encryption schemes. AES uses a symmetric key scheme, where the encryption and decryption keys are the same. RSA uses an asymmetric scheme (also known as public-key scheme), where the encryption and decryption keys are different and the encryption key is public, while the decryption key is kept private.

The primary security challenge of AES encryption is the distribution of the encryption key that can both encrypt and decrypt information; and therefore, needs to remain secret. With RSA encryption having two separate keys, this challenge is alleviated. However, compared to AES, RSA encryption is computationally expensive. Therefore, it is common to combine RSA and AES encryption into a hybrid encryption scheme, e.g: TLS or SSH that are further described below.

Symmetric Encryption

Symmetric encryption relies on only one key that is used for both encryption and decryption. Some examples of symmetric encryption algorithms are: DES, GOST 28147-89, AES, or One-Time Pad. DES (Data Encryption Standard) was a predecessor of AES, which is the most commonly used symmetric encryption today.

AES

AES (Advanced Encryption System) is an encryption algorithm, or a cipher, that falls under the category of block ciphers, which process data in blocks.

Block ciphers encrypt and decrypt data in blocks as opposed to bit by bit and are characterized by two attributes: block size and key size. Their algorithms are based on a repetition of rounds that represent a sequence of transformations to the input data that is being encrypted. Each round of transformations is parameterized by a key, called a round key, which must be unique for each round to ensure security of the encryption. Performing the same data transformations, but with different round keys yields different results and the keys are derived using a key schedule prescribed by the specific algorithm. There are two main techniques that can be used in block ciphers: (1) the substitution-permutation (e.g.: AES), or (2) the Feisel scheme (e.g.: DES).

In addition to using a different key for each round, to ensure the security of encryption, the block cipher must add enough confusion and diffusion to the input that is being encrypted. Confusion means that the input undergoes complex transformations and diffusion means that the transformations depend on all bits of the input equally. These two concepts can be viewed as the depth and breadth of the transformations performed.

AES is a variant of the Rijndael block cipher with a fixed block size of 128 bits, and a key size of 128, 192, or 256 bits. The key size used for an AES cipher specifies the number of transformation rounds that convert the input (plaintext) into the final output (ciphertext). For a 128 bit key, the algorithm performs 10 rounds of transformations, for 192 bit key 12 rounds, and for 256 bit key it is 14 rounds.

The AES algorithm can be described as follows:

1. Divide plaintext into blocks
   Each of the blocks contains a column of 16 bytes in a layout of four-by-four. Since one byte contains 8 bits, we get 128-bit block size (16x8=128)

2. Key expansion
   Produce a key with Rijindael’s key schedule represented as a block

3. Add key
   Add the blocks of text and the key

4. Repeat 9, 11, or 13 rounds:
   Step 1: Byte substitution
   Substitute every byte in the blocks produced with a code based on the Rijndael S-box
   Step 2: Row shifting
   Shift bytes in the 1st row to the left by 0 bytes, by 1 byte in the 2nd row, by 2 bytes in the 3rd row, by 3 bytes in the 4th row
   Step 3: Mix columns
   Multiply each column by a matrix
   Step 4: Add key
   Add the key to the cipher blocks

5. Final round
   Step 1: Byte substitution
   Step 2: Row shifting
   Step 3: Add key

In practice AES encryption is implemented with special techniques called table based implementations and native instructions, which make it very fast.

AES encryption is very safe. Even cracking the smallest key of 128 bits is impossible, because it would require checking 2 to the 128 possibilities, which would take more than 100 trillion years on a supercomputer.

A major issue with AES is that, as a symmetric algorithm, it requires that both the encryptor and the decryptor use the same key. This gives rise to a crucial key management issue – how can that all-important secret key be distributed to perhaps hundreds of recipients around the world without running a huge risk of it being carelessly or deliberately compromised somewhere along the way? The answer is to combine the strengths of AES and RSA encryption, which is described in the section on hybrid encryption later in this article.

One-Time Pad Encryption

Another symmetric encryption scheme that is worth mentioning is One-time pad (OTP) encryption. It is a technique that guarantees perfect secrecy as long as the encryption key is at least as long as the plaintext it encrypts and the key is used only once. It is due to these two characteristics that OTP is perfect encryption, but ironically they also make OTP impractical. Generating a random key each time a message needs to be encrypted is computationally expensive, especially when the key must be the same length as the message. Imagine encrypting a 1 TB hard drive - that would require a 1TB key!

Asymmetric Encryption

Asymmetric encryption (also known as public-key encryption) uses two sets of keys - a public key that is used to encrypt and a private key that is used to decrypt information.

RSA

RSA, or Rivest-Shamir-Adleman, encryption named after its inventors is one of the most prominent asymmetric encryption schemes that consists of four steps: key generation, key distribution, encryption, and decryption.

An RSA user creates and publishes a public key based on a multiplication of two large prime numbers. The prime numbers are kept secret, only their product is made public. Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the two prime numbers. Because there is no known method of calculating the prime factors of such large numbers, only the creator of the public key can also generate the private key required for decryption.

The RSA algorithm can be summarized as follows:

1. Generate two very large prime numbers: p and q, which are kept secret
2. Compute their product, n = p * q, n is released as the public key
3. Compute λ(n), where λ is Carmichael's totient function
4. Choose an integer e such that 1 < e < λ(n) and find the greatest common denominator, or gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime (meaning that they have no positive integer factors in common, aside from 1)
5. Find d, the modular multiplicative inverse of e times modulo λ(n), which will serve as the private key

The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers. However, the downside of RSA is that it is a relatively slow algorithm. Because of this, it is not commonly used to directly encrypt user data. More often, RSA is used to transmit shared keys for symmetric-key cryptography, which are then used for bulk encryption–decryption.

Hybrid Encryption

Both AES and RSA encryption schemes have advantages and disadvantages. As we discussed above, AES encryption is fast, but the challenge of distributing the AES key without the encryption security becoming compromised is a challenge. This is less of a challenge with RSA, because it uses two sets of keys - one public and one private key. But RSA encryption is computationally expensive.

Hybrid encryption combines the best of both worlds of AES and RSA. It has the efficiency of symmetric encryption and the convenience of public-key (asymmetric) encryption. In cloud computing the commonly used term for hybrid encryption is envelope encryption.

Envelope encryption has two sets of keys: (1) Data Encryption Keys (DEK) and (2) Key Encryption Keys (KEK). The DEK are used to encrypt data using AES, while the KEK are used to encrypt the DEK using RSA. The procedure can be described as follows:

1. Generate a DEK locally
2. Encrypt your data using the DEK
3. Issue a request to encrypt the DEK with a KEK stored in a secure service called key management system (KMS)
4. Send DEK encrypted data and KEK encrypted DEK
5. The receiver decrypts the DEK with a private key stored in KMS, then uses the DEK to decrypt the data

Some of the commonly used hybrid encryption algorithms are TLS and SSH.

TLS (Transport Layer Security)

TLS is an encryption and authentication protocol designed to secure Internet communications that lies between the transport layer (e.g.: TCP) and application layer (e.g.: HTTP). It is the internet security protocol that protects the connection between servers and clients by establishing secure channels to allow for, e.g.: secure credit card transactions. If you go to a website and see that it begins with https, the s stands for “secure” and signifies that the communication between your device and the server hosting the website will be encrypted with TLS. When a server and client communicate using TLS, it ensures that no third party can eavesdrop or tamper with any message.

An integral part of TLS is the handshake protocol, during which the client and server that wish to communicate exchange messages to acknowledge each other, verify each other (authentication), establish the cryptographic algorithms they will use (cipher suite negotiation), and agree on session keys (session key exchange).

The verification step during which the server authenticates itself to the client is an important part of the TLS protocol. It relies on a public key certificate (also known as a digital or identity certificate), which contains information about the key, the owner identity, and the digital signature of the issuer that verified the certificate. Typically, the issuer that guarantees the certificate authenticity is a trusted 3rd party called the certificate authority (CA), e.g: Let’s Encrypt, Comodo, Digicert. During the verification step, the server sends its certificate to the client, who then verifies its validity with the CA to confirm that the server is who it says it is.

SSH (Secure Shell Protocol)

SSH is a network communication protocol that enables two computers to communicate and share data. SSH ensures that all user authentication, commands, output, and file transfers are encrypted to protect against attacks in the network. The most commonly used applications of SSH are remote login and command-line execution.

The SSH protocol can be summarized as follows:

1. The client contacts the server
2. The server sends its public SSH key
3. The client uses its private SSH key to authenticate the server
4. The client and server negotiate and agree upon the symmetric encryption algorithm to be used for their communication and generate the encryption key to be used
5. The client and server establish a secure connection