Ryerson Computer Science CPS713 Applied Cryptography

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

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

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

Key Expansion

Polynomials w/ $GF(2^8)$

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

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

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

8 - Number Theory

9 - Public Key & RSA

10 - Other Public Key Systems