CPSC 253 - Week 3: Cryptography and Cryptanalysis

Threats to messages

• Interception: Confidentiality is compromised

• Interruption (blocking messages): Availability is compromised

• Modification and Fabrication: Integrity

Cryptology

Cryptography and Cryptanalysis

Cryptography

Science/art of securing messages

Cryptanalysis

Art/science of breaking Ciphertext

Basic Cryptographic scheme

• 𝑃 = 𝑝1, 𝑝2, … , 𝑝𝑛

– Where 𝑝𝑖 = i th char of 𝑃

– 𝑃 = “DO NOT TELL ANYBODY” (e.g., 𝑝1=“D”, 𝑝2=“O”, etc.)

– By convention, cleartext in uppercase

• IS what gets encrypted

• 𝐶 = 𝑐1, 𝑐2, … , 𝑐𝑛

– Where 𝑐𝑖 = i th char of 𝐶

– 𝐶 = “ep opu ufmm bozcpez” (e.g., 𝑐1=“e”, 𝑐2=“p”, etc.)

– By convention, ciphertext in lowercase

Each letter in P has a corresponding letter in C.

Benefits of Cryptography

• Improvement, not solution for security

• Minimizes some problems

• Adds an envelope(encoding) to a postcard(plain/cleartext)

Formal Notation(Important)

• E: Encryption rule/algorithm

• D: Decryption rule/algorithm

• P: Plaintext

• C: Ciphertext

• C = E(P)

• P = D(C)

• You need a cryptosystem where P = D(C) = D(E(P)), allows you to get back original message

Cryptography in practice

• Can happen through wired or wireless networks

• Compromised confidentiality

  • 
    

Crypto System with Keys

• 𝐶 = 𝐸(𝐾_𝐸,𝑃)

  • 𝐸 = set of encryption algorithms/𝐾𝐸 selects 𝐸_𝑖 ∈ 𝐸

• 𝑃 = 𝐷(𝐾_𝐷, 𝐶)

• 𝐷 = set of decryption algorithms/𝐾_𝐷 selects 𝐷_𝑗 ∈ 𝐷

• Crypto algorithms and keys are like door locks and keys

• We need: 𝑃 = 𝐷(𝐾_𝐷, 𝐸 (𝐾_𝐸, 𝑃) )

• Plaintext must equal a set of decryption algorithms with the decryption key and the set of encryption algorithms which is a function of the encryption key and Plaintext

  • Each needs a key

Classification of Cryptosystem w.r.t Keys

• Keyless

• Symmetric

• Asymmetric

Keyless cryptosystem

• EX: Caesar cypher

• Less secure

Symmetric cryptosystem

• Encipher and decipher w/ same key, easy to derive from each other

• K_E = K_D

• K_E: Encryption key

• K_D: Decryption key

Asymmetric Cryptosystem

• Private key must always stay with user, one for each user

• Public key system

• Encipher and decipher with diff keys

• Difficult to derive keys from each other

• K_E ≠ K_D

Cryptanalysis goals

• Breaking the messages

• Find patterns in encryption to break them

  • Infer meanings without actually breaking encryption

  • EX: Enemy troops sending a lot of messages may be an attack, busy node may be headquarters

• Deduce key to break subsequent messages

• Find general weaknesses and vulnerabilities in implementation or environment in an encryption algorithm

Cryptanalysis

How to start off

• Intercepted encrypted messages and plain text

• Known encryption algorithms

• Data suspected to be ciphertext

• Math/statistical tools

• Properties of natural language

  • EX: Adversary natural language like Americans using Navajo language in WW2

• Properties of computer systems

• Most important is ingenuity/luck?

• No rules

Breakable Encryption

• Based on Shannon’s theory of information

• Practical cryptosystems should be breakable with enough time and computing power, but it should be possible to devise an unbreakable system.

  • Must be hard enough for the intruder to not break it

• It is possible to make unbreakable ones theoretically

Requirements for Crypto protocols

• Messages should get to destination(Availability)

• Only the recipient should see and get it(confidentiality)

• Message shouldn’t be corrupted in transit(Integrity)

• Message should be sent/received once(availability)

• Proof of sender’s id(non-repudiation)

Representing characters

• Mapping input to 0 or 1 can be done with modulo 26(Uppercase letters rep with 0-25)

• Letter operations

  • A + 2 = C → 0+2=2%26 = 2

  • X + 4 = B → 23+4= 27%26 = 1

Basic Ciphers

• Substitution cipher

  • Letters of P replaced with other letters by E

• Transposition(permutation) ciphers

  • Order of P’s letters rearranged by E

• Product Cipher

  • E = E_1+E_2, a combo of 2 cipher

Caesar Cipher

• Has a numeric key, which shifts the characters

• Add the key to each character and use %26

• One key, 1 letter is used to sub each letter in Plaintext(P)

• A monoalphabetic substiution cipher

• EX:

  • 𝑃 (plaintext): HELLO WORLD

    𝐶 (ciphertext): khoor zruog

Exhaustive Search

• If there’s a small number for the possibility of keys try all of them

• For caesar ciphers there are 26 possible ones from 0-25

• Used to attack substitution ciphers

Breakable Encryption example

• With a message consisting of 25 characters there are 26^ 25 possible decryptions

  • A brute force approach to find the right one could take 10^ 10(10 billion) decryption/sec 10^35/10^10=10^25 sec or 317 quadrillion years

• Using ingenuity could reduce it to 10^15 decryptions to check at 10^10 decryptions/s → 10^15/10^10= 10^5 sec or 1 day

Frequency Table

Polyalphabetic Substitution

• Flatten(diffuse) some of the letter dist. by combining high and low dist.

  • Ex 1

• Key 1: Skip 2, take next letter

• Key 2 in example: Skip 4, keep next letter

Ciphertext to plaintext example

• Substitution or

Caesar substitution example and equation

• Key = 3 or Key = “D” as D represents 3

• 𝑐𝑖 = 𝐸 𝑝𝑖 = (𝑝𝑖 + 𝑘ey) %26

  – 26 letters in the English alphabet

  – Change each letter to the third letter following it (circularly)

  – If key=3: 𝐴 → 𝐷, 𝐵 → 𝐸, … , 𝑋 → 𝐴, 𝑌 → 𝐵, 𝑍 → 𝐶

• Can also be represented through 𝜋

Caesar Cipher as a permutation

• Represented as a 𝜋 symbol

• 𝜋(𝑖) = (𝑖 + 𝑘ey) 𝑚od 26

  – For key=3: 𝜋 (0) = 3, 𝜋 (1) = 4, …, 𝜋 (23) = 26 𝑚od 26 = 0, 𝜋 (24) = 1, 𝜋( 25) = 2

Statistical Analysis

• Used to attack substitution ciphers

• Compare to so called 1-gram (unigram) model of

English

• Shows frequency of (single) characters in English

• The longer the C, the more effective statistical analysis

would be necessary

Statistical Attack - Step 1

• Compute frequency f(c) of each letter in ciphertext

• Example: c = ‘khoor zruog’

  • 10 characters: 3 * ‘o‘, 2 * ‘r’, 1 * {k, h, z, u, g}

  • f(c) (whitespace ignored):

    • f(g)=0.1 f(h)=0.1 f(k)=0.1 f(o)=0.3 f(r)= 0.2

    • f(u)=0.1 f(z)=0.1 f(ci ) = 0 for any other ci

• Apply 1-gram model of English

  • Frequency of (single) characters in English

  • 1-grams on previous slide

Statistical Attack - Step 2

• phi 𝜑(𝑖) - correlation of frequency of letters in ciphertext

with frequency of corresponding letters in English - for key i

• For key i: 𝜑(𝑖) = ∑0≤𝑐𝑐≤25 𝑓 (𝑐) ∗ 𝑝(𝑐 − 𝑖)

  • c is representation of character (a-0, ..., z-25)

  • f(c) is frequency of letter c in ciphertext C

  • p(x) is frequency of character x in English

  • Intuition: sum of probabilities for words in P, if i were the key

• Example: C = ‘khoor zruog’ (P = ‘HELLO WORLD’)

  • f(c): f(g)=0.1, f(h)=0.1, f(k)=0.1, f(o)=0.3, f(r)=0.2, f(u)=0.1, f(z)=0.1

  • c: g - 6, h - 7, k - 10, o - 14, r - 17, u - 20, z - 25

  • 𝜑(i) = 0.1p(6 – i) + 0.1p(7 – i) + 0.1p(10 – i) + 0.3p(14 – i) +0.2p(17 – i) + 0.1p(20 – i) + 0.1p(25 - i)

Statistical Attack - Step 3

• The result

• The phrase left is i=3 or the key, signifying the cipher was broken

Problems with Caesar Cipher

• Key is too short

  • Can be easily found with an exhaustive search

  • Can’t cover statistical frequencies due to length; too similar to regular English letters

  • 1 Char-key - monoalphabetic substitution

• Solution is making the key longer

  • Use a key of n>=2, polyalphabetic substitution

  • Will make exhaustive search and cryptanalysis harder

Polyalphabetic Subtitution Key example

• Flatten (diffuse) somewhat the frequency

distribution of letters by combining high and low

distributions

• Example: 2-key substitution

  • Key1 is defined by shifting by 3/skip 2 and take next starting from a, circular

  • Key2: Is defined starting with n, skip 4, take next, circular

Using the keys in polyalphabetic substitution

• Plaintext: TOUGH STUFF

• Ciphertext: ffirv zfjpm

  • Key 1: fiv fp

  • Key 2: fr zjm

    • Use n (=2) keys in turn for consecutive P chars in P

• Note:

  • Different chars mapped into the same one: T, O → f

  • Same char mapped into different ones: F → p, m

  • ‘f’ most frequent in C (0.30); in English: f(f) = 0.02 << f(e) = 0.13

Vigenère Tableaux

EX

• Row A - shift 0(a→a)

• Row B - shift 1(a→b)

• Row C - shift 2(a→c)

….

• Row Z - shift 25(a→z)

Vigenère Tableaux Example

• Key: exodus

• Plaintext P: YELLOW SUBMARINE FROM YELLOW RIVER

• Extended keyword(re-applied to mimic words in P):

• Ciphertext: cbzoio wlppujmks ilgq vsofhb owyyj

Solution:

• Ciphertext is created from Vigenère Tableaux

• Row corrosponds with plaintext letter

• Column with key letter

• Example:

  • [Y][e] = ‘c’

  • [E][x]= ‘b’

  • [L][o] = ‘z’

Transposition Ciphers

• Rearrange letters in plaintext to produce ciphertext

• Example 1a and 1b: Columnar transposition

  • Plaintext: HELLO WORLD

• Transposition onto:

a) 3 columns:

H E L

L O W

O R L

D X X

b) 2 Columns:

H E

L L

O W

O R

L D

• XX - Padding

• Ciphertext (read column-by column):

a) hlodeorxlwlx

b) hloolelwrd

• What is the key?

– Number of columns: a) key = 3 and b) key = 2

Transposition Cipher example

• Example 2: Rail-Fence Cipher

  • Plaintext: HELLO WORLD

  • Transposition into 2 rows (rails) column-by-

column:

HLOOL

ELWRD

• Ciphertext: hloolelwrd (Does it look familiar?)

• What is the key?

  • Number of rails: key = 2

Product/Combination Ciphers

• Built of multiple blocks, each is:

  • Substitution or transposition

• Example: two-block product cipher

  • 𝐸₂(𝐸₁ 𝑃, 𝐾_E1 , 𝐾_E2)

• Product cipher might not be stronger than its

individual components used separately!

– Might not be even as strong as individual

components

What makes a cipher good?

• Depends on type of cipher and application

• Substitution

  • C hides chars of P

  • If > 1 key, C dissipates high frequency chars

• Transposition

  • C scrambles text

• Product Ciphers

  • All of the above

• What are the priorities and facilities for sender/reciever?

  • e.g., no supercomputer on the battlefield

Commercial Principles of Sound Encryption Systems

• Another criteria for good systems

• Sound mathematics

  • Proven vs. not broken so far

• Verified by expert analysis, including outsiders

• Standing the test of time, long-term success isn’t a guarantee

Examples of popular commercial encryptions

• Data Encryption Standard (DES)

• Rivest-Shamir-Adelman (RSA)

• Advanced Encryption Standard (AES) - relatively new