CSEC - 7 - M

Symmetric cryptography

Same key used for both encryption and decryption

AES

Advanced Encryption Standard - symmetric algorithm recommended by NIST - replaced DES

DES

Data Encryption Standard - legacy algorithm replaced by AES

NIST

U.S. National Institute of Standards and Technology

Cryptography

Techniques for secure and trustworthy communication and computation

Alice Bob and Eve

Alice and Bob want to communicate securely - Eve is the eavesdropper who may read their messages

Cryptanalysis

The science of attacking cryptosystems

Cryptanalyst

A practitioner of cryptanalysis

Open design principle

Assume the attacker knows the algorithms but knows nothing about the keys

Security by obscurity

Relying on hiding the algorithm - likely to fail as it can leak (stolen documents or bribed programmer or reverse engineering)

Ciphertext-only attack

Eve has ciphertexts of one or more messages encrypted with the same key K - goal is to find the plaintext or better still K

Known-plaintext attack

Eve has one or more plaintext-ciphertext pairs using the same key K - goal is to determine K

Chosen-plaintext attack

Eve chooses plaintexts and gets the matching ciphertexts (same key K)

Chosen-ciphertext attack

Eve chooses ciphertexts and gets the matching plaintexts (same key K)

Offline (chosen-text attacks)

Eve must choose all her texts in advance

Adaptive (chosen-text attacks)

Eve chooses texts iteratively - each choice can be based on what she learned from previous ones

Order of the four attacks

Listed by amount of information Eve has: ciphertext-only then known-plaintext then chosen-plaintext then chosen-ciphertext

Why attacks are feasible

It is usually easy to recognise a valid plaintext (gibberish = wrong key and intelligible text = right key)

Unicity distance

Minimum number of ciphertext characters needed so that there is a single intelligible plaintext associated with it

Why unicity distance exists

Built-in redundancy of natural languages

Caesar cipher

Each letter replaced by the letter three positions away in a cyclic alphabet (modulo the alphabet size)

Generalised substitution cipher

Each letter gets an arbitrary substitution as long as all substitutions are unique

Number of English substitution ciphers

26! = more than 4.03 × 10^26

Main weakness of simple substitution ciphers

They do not hide the underlying frequencies of characters (frequency analysis)

English letter frequencies

E is just over 12% - T is next at under 10% - the most frequent ciphertext letter probably stands for E

A Christmas Story example

Ralphie uses a decoder pin (substitution cipher) to decode "BE SURE TO DRINK YOUR OVALTINE"

Polygraphic substitution cipher

Groups of letters are encrypted together

Digram

A pair of letters

Digram substitution keys

26^2 = 676 digrams so 676! possible keys - but the key is long as all 676 substitutions must be written down

Substitution box (S-box)

2D table where the first letter or bits pick the row - the second pick the column - the entry is the unique substitute

S-box dimensions for a b-bit word

Split x into c bits and d bits (b = c + d) - S-box is 2^c × 2^d

Inverse S-box

Exists if all S-box substitutions are unique - reverses the substitutions (used to decrypt)

4-bit S-box example

4×4 S-box from Figure 3 - used in the Serpent cryptosystem

Why single-character or digram substitution is insecure

Single-letter and digram frequencies are easy to compute from a large enough corpus

Vigenère cipher

Polygraphic substitution cipher from 1586 - blocks of length m - m shift ciphers in parallel - key is (k1 to km) modulo 26

Vigenère weakness

Can be broken with statistical techniques if the ciphertext is long enough relative to m

One-time pad

Absolutely unbreakable substitution cipher invented in 1917 by Joseph Mauborgne and Gilbert Vernam

Two rules of the one-time pad

1) Key length m must equal plaintext length n 2) Each shift amount ki must be chosen completely at random

Why the one-time pad is unbreakable

Each letter is equally likely at any ciphertext position so no statistical analysis is possible

Pad reuse

Quickly reduces security - allows statistical methods to discover parts of the plaintext

Venona Project

US effort to analyse intercepted Soviet-spy traffic - very successful because pads were reused

Why the one-time pad is impractical

Pad must be as long as the message - what do you do when you run out of pad

Cold War hotline

Moscow-Washington hotline reportedly encrypted with a one-time pad

XOR (exclusive-or)

Gives 1 if the two bits are different and 0 if they are the same

Binary one-time pad encryption

C = M ⊕ P (M = plaintext bit string of length n and P = completely random pad of length n)

Binary one-time pad decryption

M = C ⊕ P (same pad used for both)

Why XOR decryption works

XOR is associative so C ⊕ P = (M ⊕ P) ⊕ P = M ⊕ (P ⊕ P) = M ⊕ 0 = M

Why the binary one-time pad is unbreakable

Each ciphertext bit is equally likely to be 0 or 1 independent of the plaintext and the other ciphertext bits