Symmetric Encryption

Ungraded Quiz

• What is the difference between information-theoretic security and computational security?

• What is the key space? Why does it need to be large?

• What is the cryptographic key in a Caeasar cipher? How big is the key space?

• What is the difference between a block cipher and a stream cipher?

• Why does a block cipher need modes?

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”

Key Concepts

Be familiar with diagrams like Figure 2.1, page 31

These diagrams use cryptographic notation.

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.

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 meanst he attacker can choose ciphertext and see the corresponding decrypted plaintext.

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 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: see Figure 2.2, page 33

• 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 — see Figure 2.3, page 34
• 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

  • ECB
  • CBC
  • CTR

• Wikipedia article on block cipher modes

• 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

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