Cryptography – A Gentle Overview (Part 2: Encryption)

Previous Entry

This post is part 2 of a series. Click here to read the first entry in this series.

Symmetric Encryption

In symmetric encryption, the same key is used to encrypt and decrypt. Plaintext is converted into ciphertext using a key and the ciphertext can be converted back to plaintext with the same key.

Symmetric encryption has been used for thousands of years. A famous example of symmetric encryption is a Caesar cipher. A Caesar cipher works by shifting characters in a text by a fixed number of positions. When the shift exceeds the bounds of the alphabet, it wraps back around to the start of the alphabet.

For example, this is an example of a Caesar cipher with a shift of 2.

For example, this is an example of a Caesar decipher with a shift of 2.

While this form of encryption is relatively simple, it is also quite easy to break. By mapping the frequency of commonly used letters (frequency analysis), it is possible to derive a shift value and keep updating the shift until the ciphertext converts into a readable plaintext.

Fortunately, other symmetric encryption schemes exist that are much more secure than the Caesar cipher. Some of the first modern symmetric encryption schemes were DES and 3DES, developed in the late 70s / early 80s (they have since been deprecated by NIST). As of this publishing, Advanced Encryption Scheme (AES) remains one of the most popular, widely-used symmetric encryption schemes still used today.

The challenge of utilizing symmetric encryption to securely communicate with other parties – especially over the internet – is how the key is shared. If Alice creates a key, how can she share the key with Bob without exposing it to a malicious actor, Eve? Another type of cryptographic algorithm is required: asymmetric encryption.

Asymmetric Encryption

In asymmetric encryption (also known as public key cryptography), different keys are required to encrypt and decrypt:

• Public key - used to encrypt
• Private key - used to decrypt

Therefore, if Alice wants to securely send a message to Bob:

• Alice will use Bob's public key to encrypt a message and send it to Bob
• Bob will use his private key to decrypt Alice's message

Since a message encrypted by a public key cannot be decrypted without the private key, it is extremely important that the private key is never shared with anyone.

Examples of asymmetric encryption algorithms in use today are RSA and Elliptic Curve Cryptography (ECC). While this blog will not dive into it, these schemes rely on mathematics to create difficult problems to solve, such as prime number factorization or difficulty finding a discrete logarithm for a curve, respectively.

While asymmetric encryption enables secure communication between two or more parties, it has its limitations. In terms of performance, asymmetric encryption is typically slower than symmetric encryption. This is largely due to the mathematics involved in their implementation as mentioned in the previous paragraph. Additionally, asymmetric encryption is bound on its input size; it cannot operate on large inputs.

In practical applications, a hybrid approach of using both symmetric and asymmetric encryption is utilized:

• Encrypt a plaintext T with symmetric encryption to produce a ciphertext C₁. Encrypt C₁ with asymmetric encryption to produce ciphertext C₂.
• Decrypt ciphertext C₂ with asymmetric encryption to produce ciphertext C₁. Decrypt C₁ with symmetric encryption to produce plaintext T.

A famous example of hybrid encryption is the Diffie-Hellman key exchange protocol, which describes how two parties can establish a shared symmetric key using their public and private keys. This video gives a good explanation of how the key exchange protocol works.

Encryption So Far

So far, we've established that symmetric and asymmetric encryption both offer confidentiality:

• In symmetric encryption, only those with the shared secret key can read an encrypted message.
• In asymmetric encryption, only the person with the private key can read a message encrypted by the public key.

In the previous post, I described a CIA triad cryptography can fulfill (confidentiality / integrity / authenticity). What about integrity and authenticity?

In the next couple of sections, I will describe how hashing could be used to fulfill these missing pillars.

Hashing

Hashing is the one-way conversion of a plaintext to a ciphertext (also known as a backdoor function):

• A plaintext T₁ can be converted to hash H₁. H₁ cannot be converted back to T₁.
• Given a constant plaintext T₁, it will always produce hash H₁.

A property of hashing is that it is one-to-one, which means:

• Given two unique plaintexts T₁ and T₂, hash(T₁) != hash(T₂).

Some notable hashing algorithms include MD5, SHA (1/256/512) and Bcrypt.

You may have come across a scenario where you've downloaded a file from the internet and the site you've downloaded the file from provides an MD5 hash of the file. This is to ensure the integrity of the download: the file was downloaded completely and is the correct version of the file you're expecting.

Another application of hashing is to obscure sensitive information that shouldn't be recovered, such as a password. When a user's password is set, a hash of the password is stored in the database. Then, next time the user logs in, their supplied password is hashed and compared against the stored password hash. This is an example of using hashing to achieve confidentiality.

• It is beyond the scope of this post, but hashes can utilize salting to achieve unique hashes given a constant input. This is primarily used to produce different password hashes given the same password.

Hashing + Encryption

Since anyone can send Bob a message by using his public key, how can Bob validate who sent him a message? If Bob receives a message saying "Send Eve 5 dollars", how can he ensure this message came from Alice and not Eve?

This is where HMAC (Hash-based Message Authenticator Code) can be used to validate the authenticity of the sender.

HMAC offers two main functions:

• Signing - sign a hash using the private key of the sender to produce a signature
• Verifying - verify the signature using the public key of the sender

For example, if Alice wants to send Bob the message "Send Eve 5 dollars":

• Alice encrypts "Send Eve 5 dollars" with Bob's public key to produce ciphertext C₁.
• "Send Eve 5 dollars" is hashed by Alice to produce hash H₁
• Alice will then sign H₁ with Alice's private key to produce signature S₁.
• Bob receives ciphertext C₁ and signature S₁.
• Bob decrypts ciphertext C₁ with his private key to produce plaintext "Send Eve 5 dollars".
• Bob hashes "Send Eve 5 dollars" to produce hash H₂.
• Bob verifies hash H₂ was used to produce signature S₁ by using Alice's public key.

If validation passes, Bob can verify that the message he received from Alice was what was intended (integrity) and that Alice was the one who sent it (authenticity).

Conclusion

Although it is necessary for secure communication, cryptography has a lot of elements at play and can be a complex field. Through the course of this article, we explored the different encryption schemes and how, when combined with hashing, all of these components can be used to verify the confidentiality, integrity and authenticity of our communications.

As a final note, cryptography is not a perfect field. It relies on mathematics and computational complexity. As computer hardware becomes more efficient and can compute quicker, cryptographic functions that were once considered secure have since become insecure. When deciding on an encryption scheme to use in your application, verify it is appropriate for your scenario and whether the scheme is still considered secure.

Thank you for reading!

Good Literature

If you're interested in learning more about cryptography and want to learn more about the subject as a whole:

• Foundations of Cryptography by George Kudrayvtsev (link )
• Introduction to Modern Cryptography by M. Ballare, P. Rogaway

If you're interested in learning about the history behind cryptography and the historical figures behind our modern-day cryptographic landscape:

• Crypto by Steven Levy