Types of Attacks

Passive: Eavesdropping or monitoring transmissions (harder to detect)

Active: manipulating data

Data confidentiality

Cipher Basics

Kerckhoff's Principle

Kerchoff's principle asserted that the security of a given scheme should not rely on the secrecy of the algorithm employed

Computationally Secure

• The cost of breaking the cipher exceeds the value of the encrypted information
• The time required to break the cipher exceeds the useful lifespan of the information

Overview

Mono alphabetic means that it uses the same substitution over the entire message

• Issues
  • Key space is too small -- only 25
    • Takes an avg of 13 tries to break an alpha shift cipher
  • Easy to guess the key by performing statistical analysis. Eg, the letter 'e'occurs most frequently in English
• Solutions
  • Encrypt a block at a time rather than a character at a time
  • Use a different shift for each character

Playfair cipher

Hill cipher

Uses an invertible square matrix as the key

• Matrix multiplication
  • Multiply the key matrix with each character

Polyalphabetic ciphers

• Vernam cipher
  • Encrypts each bit by XOR-ing
  • Key has to be as long as the plaintext!
• Vigenere cipher
  • Choose a key phrase and line it up under the plaintext (repeatedly if necessary), use the corresponding character from the key phrase as the key to the shift cipher

One-time pads

• Random key as long as PT. Key can never be reused
• Can never reuse a key

Transposition

• Arrange as blocks,then rearrange the PT characters within the blocks

Product ciphers

• Multiple use of shift cipher... Just looks like a single cipher anyway

Enigma machine

Shift and substitution cipher

Issues

Cipher's leak statistical information

• So encrypt 1 block at a time
  • Usually from n bits to n bits

Some block cipher designs

Code book

• Still, patterns can be found. Code book is very large and hard to share
• All plain text had to be anticipated

Random substitution block cipher

• Problem is that the key size is too large

Non random substitution block-cipher

• Key size is more manageable
• Uses matrices
  • Problem is that they key can be solved using system of linear equationsLinear systems are easy to solve
    • Possible solution:substitution-permutation network (SPN)
      • Diffuses the statistical distribution of the cipher text... No longer 1:1between plaintext and cipher text characters

Feistel cipher

DES

• 64 bit blocks
• Symmetrical encrypt and decrypt
• Initial placement
• 16 rounds results in about half the numbers being changed
• Substitution portion (s boxes) is hard coded
• See key creation section -- shifting left

Gauging Effectiveness

Finite fields necessity

If we have 3 bits to work with and we try to add five and four we will not have enough bits to store the answer of 9. This is the problem of finite fields. We use modular arithmetic to deal with this.

Groups

Group (G, $\cdot$) - a set of elements with a binary operation denoted by $\cdot$ that associates to each ordered pair (a, b) of elements in G an element (a $\cdot$ b) in G, such that:

Properties

• Closure - if a and b belong to G then $a \cdot b$ is also in G
• Associative - $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c$ in $G$
• Identity element - there is an element $e$ in $G$ such that $a \cdot e = e \cdot a = a$ for all $a$ in $G$
  • Ie, keep the same value
• Inverse element - for each $a$ in $G$, there is an element $a'$ in $G$ such that $a \cdot a' = a' \cdot a = e$
  • Ie, produce a 1
• Commutative = $a \cdot b = b \cdot a$ for all $a, b$ in $G$

Examples of groups

• Integer addition is a group (ie, the set of all integers satisfies the above properties)
• Rational number multiplication

Finite Fields

• Integers ${\mathbb{Z}_n}$ where n is prime
• See ${\mathbb{Z}_4}$ that doesn't work
• We can fix the problem of ${\mathbb{Z}_4}$

Irreducible Polynomials (aka, prime polynomials)

• $x$
• $x + 1$
• $x^2 + x + 1$
• $x^3 + x + 1$

Useful property of these polynomials for $GF(2^n)$ which makes the 'overflow' arithmetic much easier:

• Given $x^3 + x + 1$
• $x^3 \equiv - x - 1 \ (mod x^3 + x + 1)$
• $x^3 \equiv x + 1 \ (mod x^3 + x + 1)$ [because with $2^n$ fields, addition and subtraction are interchangeable]
• So, we can use the $x + 1$ part to simply XOR with the result of the arithmetic in the event of an overflow

Sample Problem

Overview

• All operations are 8 bit bytes; arithmetic operations are over $GF(2^8)$ finite field
• Decryption is not symmetrical with encryption -- it can use two different algorithms, though both are functionally the same
• Plaintext block size 16 bytes (128b)
• Key length 16, 24, or 32 bytes
• Number of rounds is 10, 12, or 14 for key length of 16, 24, or 32 bytes
• PT is transformed into a 4x4 square matrix referred to as the State array, which is modified at each stage

Four Transformations

1. SubBytes - byte by byte S-Box substitution
2. ShiftRows - simple permutation, just rotate the bottom row
3. MixColumns - substitution that makes use of matrix multiplication over $GF(2^8)$
4. AddRoundKey - simple bitwise XOR

Key Expansion

Polynomials w/ $GF(2^8)$

Multiple Encryption & Triple-DES

2DES

Vulnerable to time-memory tradeoff attack

Triple-DES

• c = E(k1, D(k2, E(k1, P))
• The D in the middle allows decryption of old-style single DES
• 2^112

ECB (electronic code book)

• Same speed as block
• Has serious issues as the the same key is used for each block - so the pattern of the content is still there (eg, encrypt an image with ECB and you can still see it)
• Can run on parallel processors
• Random access is nice

CBC (Cipher Block Chaining)

• Before the Encrypt stage, the PT is XOR'd with IV (input vector) which is the output of the previous Encrypt stage (except the first, which needs an IV to be supplied)
• Last block must be padded to a full b bits if it is a partial block

Handling IV (input vector)

• Fixed: not secure
• Counter: not so secure, as an increment of 1 sometimes changes only 1 bit
• Random: Better, but... How to generate, how to share?
• Nonce-generated: Pre-generated

Padding

A padding strategy is required for block ciphers whose last block is not full. Two possible strategies are:

• Add a '1' followed by all '0's
• Ciphertext stealing

CTR (CounTeR)

Encrypt counter and XOR with plain text

Xts aes

Output feedback mode

Can be preprocessed

Similar to ctr