Symmetric Encryption

Introductions

• introductions of two students

Questions on the readings

The readings today are from Computer Security and the Internet, Chapter 2, sections 2.0 - 2.2

Cryptography basics

Important note

• You should not design your own cryptographic algorithms and protocols (unless you are doing PhD-level research or have become a cryptography expert)

• Kerckhoffs’s principle, as restated by Steven Bellovin — “design your system assuming that your opponents know it in detail”

Cryptographic notation

You should become accustomed to cryptographic notation such as is used below.

The importance of notation is that it cleary expresses a set of cryptographic operations. As you read academic papers or cryptography websites, you will find that there is no standard notation — instead, an author will often define their terms before using them.

Attacks on cryptography

For any given encryption key, you can try to guess it by exhaustively trying all possible keys — this is called an exhaustive key search or a brute force search.

• Example: DES keys, 56 bits
• A keyspace of 56 bits provides 2 56 ≈ 7.2×10¹⁶ possible keys. At a rate of 10¹² keys per second it would take approximately 7.2×10⁴ seconds or about 20 hours to try every key.
• In January 1999, distributed.net and the Electronic Frontier Foundation collaborated to publicly break a DES key in 22 hours and 15 minutes.

Some common attacks:

• A ciphertext-only attack requires the attacker to guess the plaintext (or the key) using only the ciphertext.
• A known-plaintext attack means the attacker has access to examples of both plaintext and ciphertext.
• A chosen-plaintext attack means the attacker can choose a plaintext and see the corresponding encrypted ciphertext.
• A chosen-chiphertext attack means the attacker can choose ciphertext and see the corresponding decrypted plaintext.

Some common adversaries:

• A passive adversary can only observe messages.
• An active adversary can inject or alter messages.

Symmetric Encryption

Symmetric encryption allows one party to send encrypted data to another party, provided they have a shared key. It is called symmetric encryption because the same key is used for decryption and encryption.

Caesar Cipher

Caesar cipher with a shift of 23:

• Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
• Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Vernam cipher

• If using a random stream of bits for the key, and never reuse the same key, this is a one-time pad.
• A one-time pad is information-theoretically secure for confidentiality: “even given unlimited computing power and time, an attacker without the key cannot recover plaintext from ciphertext”.
• Useful in theory! Try to approach its level of security.
• In practice, we try to have computational security, meaning protection against an attacker with fixed resources, unable to brute force keys chosen from a large space.
• Has no integrity.

Types of ciphers

• stream cipher — encrypt one bit or one character at a time
• block cipher — encrypt chunks of fixed size, e.g. 128 bits, pad smaller blocks with a 1 and then zeroes.

AES

AES is the most common block cipher.

• 128-bit block
• 128, 192, or 256 bit key

Block cipher modes

Block cipher modes are used to encrypt variable-size pieces of data using a block cipher. Remember, AES can only encrypt 128 bits! Block cipher modes are what you use to encrypt larger sizes of data.

Everywhere you see “block cipher encryption” in the below diagrams, that is where AES fits in

ECB Mode

• Electronic Code Book
• Not recommended due to its weaknesses

CBC mode

• Cipher Block Chaining
• blocks are chained together
• uses an Initialization Vector to make sure each message is unique, should be random
• encryption must be done sequentially by block
• message must be padded to a multiple of the block size

CTR mode

• CounTeR
• uses a non-repeating counter
• nonce is an initialization vectore
• for a given AES key, do not re-use the same nonce
• the counter is encrypted and then XORed with the plaintext to produce ciphertext
• turns a block cipher into a stream cipher, since each bit of the plaintext is individually XORed with the encrypted counter
• encryption and decryption can be done in parallel

Padding

Block ciphers require that the plaintext be a multiple of the block size (ECB and CBC modes). Padding is used to make sure that all blocks are “full”. Both sides need to know the padding scheme. PKCS #7 is a common scheme.

AES with GCM

Symmetric encryption offers confidentiality, but not integrity and authenticity. Securely combining separate confidentiality and authentication block cipher operation modes can be error prone and difficult. To solve this problem, we have Authenticated Encryption with Associated Data (AEAD) algorithms, which provide confidentiality, integrity, and authentication with associated (unencrypted) data (e.g. message header). Integrity covers the associated data as well.

AES-GCM (Galois Counter Mode) is used in TLS, SSH, IPSec, OpenVPN.

• notice that this is identical to CTR mode, with the Associated Data (called Auth Data here) added in later
• to add in the associated data, GCM uses a combination of XOR and mult_H, which is finite field multiplication using a Galois Field
• fast, patent-free, on-line (don’t need to know message length in advance), can be parallelized
• security depends on choosing a unique initialization vector for every encryption performed with the same key

The strength of cryptography

• Relies on the size of the key space. AES typically uses a key space of 256 bits = 2²⁵⁶ possible keys
• For comparison:
  • 1 in 2⁶¹ odds of winning the lottery and being hit by lightning in the same day
  • 2⁹² atoms in the average human body
• Thermodynamic limits
  • physics: To set or clear a bit requires no less than 𝑘𝑇 “erg”
    • 𝑘 is the Boltzman constant — 1.38×10⁻¹⁶ erg⁄°𝐾
    • 𝑇 is the absolute temperature of the system
  • assuming 𝑇=3.2°𝐾 (ambient temperature of universe)
    • 𝑘𝑇=4.4×10⁻¹⁶ ergs
  • annual energy output of the sun is 1.21×10⁴¹ ergs
    • enough to cycle through a 187-bit counter in a year
    • enough to cycle through a 192-bit counter after 32 years
  • a supernova produces about 10⁵¹ ergs
    • enough to cycle through a 219-bit counter

Class exercises

We are going to be using the Rust Crypto crates.

See the Rust Cryptography repo for an AES-GCM code example.