(go back)

# 1 - Overview

## The basics

Security Mechanisms are used to...

• Detect
• Prevent
• and Recover from...

... security attacks

## Must decide:

1. what services do we need (what to protect?)
• What is the cost of a loss
2. what type of attacks do we expect?
3. which security mechanism to use

## Services (CIA)

• Confidentiality
• Data confidentiality
• Privacy
• Integrity
• Availability

## What is applied cryptography

Classical def: the art of writing or solving codes

Modern def: scientific study for the digital transmission, transaction, and distribution computations

## Types of Attacks

Passive: Eavesdropping or monitoring transmissions (harder to detect)

Active: manipulating data

## Data confidentiality

### Simple case 1

• Message on an insecure channel
• Solution 1 send a courier
• Not a viable solution
• Solution 2 encrypt the message
• Should be easy for sender and receiver
• Should be hard for the listener

### Cryptanalytic attacks

• Cipher text only
• Known plain text
• Chosen cipher text
• Chosen cipher text
• Analysts may have some contextual knowledge of the original message

## Cipher Basics

### Requirements

1. Easy to use for encryption/decryption by both parties
2. Difficult to break
3. Reusable

### Components

• Random key generator
• Encryption, C = E(K, P)
• Decryption, P = E(K, C)

### 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

# 2 - Classical Ciphers

## 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

• 5x5 matrix that begins with the unique characters of a keyword,followed by the rest of the alphabet (two letters need to be grouped)
• Enciphering rules
• Encipher groups of two letters at a time
• If you come across a group of two of the same letter, swap the 2nd with another padding character
• Same column - just shift each down by one (eg, mu -> CM)
• Same row - just shift to the right by one (eg, ar -> RM)
• Otherwise, form a rectangle and use the other two corners (eg, hs -> BP)

## 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

• 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

# 3 - Block Ciphers and DES

## 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

### Diffusion

• Break down the statistical connection between plain text and cipher text
• DES does this well
• Can be tested experimentally by altering the number of rounds

### Confusion

• Relationship between cipher text and key should be as complex as possible
• Can be tested experimentally by altering the number of rounds

# 4 - The Math

## GCD

Techniques

• Prime factorization -- no good algorithm for this
• Euclidian gcd algorithm

d = gcd(a, b); then d divides a, b and r where a = qb + r

Sample Extended Euclidian Algorithm
Another Sample Extended Euclidian Algorithm

## Divisibility / Division Alg

Divisible: a | b means a divides be with zero remainder

Division Algorithm: a = qn + r

## Congruence

$a \equiv b\ (mod\ m)$ means:

$\rightarrow m\ |\ (a - b)$

$\rightarrow a = b + k\cdot m$

## 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

# 5 - AES

## 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

# 6 - Block Cipher Operations

## 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

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

# 7 - Pseudo Random & Stream Ciphers

## Where are 'random' numbers used?

• Key distribution schemes
• Generated session keys
• RSA keys
• Bit stream encryption

## Randomness

• Uniform distribution: of 1's and 0's
• Independence: no one subsequence in the sequence can be inferred from others

## Types

1. True Random Number Generators
• uses a non-deterministic source ("entropy")
• eg: radioactive decay, keystrokes, capacitor discharge, etc
2. Pseudo Random Number Generators
• takes input seed, feeds it into a deterministic algorithm