**Security Mechanisms** are used to...

- Detect
- Prevent
- and Recover from...

... security attacks

- what services do we need (what to protect?)
- What is the cost of a loss

- what type of attacks do we expect?
- which security mechanism to use

- Confidentiality
- Data confidentiality
- Privacy

- Integrity
- Availability

**Classical def**: the art of writing or solving codes

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

**Passive:** Eavesdropping or monitoring transmissions (harder to detect)

**Active:** manipulating data

- 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

- Solution 1 send a courier

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

- Easy to use for encryption/decryption by both parties
- Difficult to break
- Reusable

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

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

- 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

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

- Key space is too small -- only 25
- Solutions
- Encrypt a block at a time rather than a character at a time
- Use a different shift for each character

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

- Encipher groups of two letters at a time

- Enciphering rules

Uses an invertible square matrix as the key

- Matrix multiplication
- Multiply the key matrix with each character

- 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

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

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

Shift and substitution cipher

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

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

- Problem is that the key size is too large

- 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

- Possible solution:substitution-permutation network (SPN)

- Problem is that they key can be solved using system of linear equationsLinear systems are easy to solve

- 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

- 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

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

**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 AlgorithmAnother Sample Extended Euclidian Algorithm

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

**Division Algorithm**: a = qn + r

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

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

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

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.

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:

*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$

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

- 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}$

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

- 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

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

Vulnerable to time-memory tradeoff attack

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

- 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

- 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

- 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

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

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

- True Random Number Generators
- uses a non-deterministic source ("entropy")
- eg: radioactive decay, keystrokes, capacitor discharge, etc

- Pseudo Random Number Generators
- takes input seed, feeds it into a deterministic algorithm