Today

Introduction to cryptography and information hiding
- Termonology
- Simple encryption schemes
- Cryptoanalysis

History

One of the earliest examples of secret hiding:
- Herodotus describing the war between Greece and Persia
- Message hiding - steganography
  - A weakness: someone discoveres the message
Cryptography was developed in parallell
Early encryption
- Substitution and transposition

Encryption Terminology

Encryption: encoding a message so that its meaning is not obvious
Decryption: the reverse
Encipher, decipher: the same
Cryptography: the art of keeping messages secure
Cryptoanalysis: the art of breaking cipher-text
Cryptology: the mathematics field that cryptography and cryptoanalysis belong to

Encryption Terminology

Plain-text (M or P)
Cipher-text (C)
E(M) = C
D(C) = M
The following must be true: D(E(M)) = M

Encryption

Some cryptographic methods rely on the secrecy of the algorithms
- Only historical interest
- Not adequate for real-world applications
Generally, no algorithm that depends on its secrecy is secure
All modern algorithms
- Use keys to control encryption and decryption
- Cannot really be executed by humans
In theory, any cryptographic method with a key can be broken by trying all possible keys in sequence
- Except One-time Pad systems...

Other uses of cryptography

Authentication
Integrity
Non-repudiation
More specialized uses:
- Digital signatures
- Undeniable digital signatures
- All-or-nothing disclosure of secrets
- Zero-knowledge proofs
- Oblivious transfer
- Simultaneous exchange of secrets
- Secure elections
- Digital cash
- Etc.

Algorithms and Keys

A cryptographic algorithm, a cipher, is the mathematical function used for encryption and decryption.
Modern algorithms use a key (K).
The set of possible keys are called the key-space
E_K(M) = C
D_K(C) = M
D_K(E_K(M)) = M
Some algorithms uses two keys:
- E_K1(M) = C
- D_K2(C) = M
- D_K2(E_K1(M)) = M

Encryption

One-time Pad

A Perfect Secrecy System
Bitwise Exclusive OR operation
- 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 1 XOR 1 = 0
- M XOR K = C
- C XOR K = (M XOR K) XOR K = M
Pad = The Key
The Pad must be of the same length as the plain-text message

One-time Pad

One-time pad is unbreakable provided:
- Pad is never reused
- Unpredictable random numbers (i.e. pad) are used

Then there is no way of knowing which key is correct:

  M:  a   t    t    a   c   k    a   t    d    a   w    n
      97  116  116  97  99  107  97  116  100  97  119  110
  K1: 119 99   115  110 111 105  115 111  98   96  119  101
  C:  22  23   7    15  12  2    18  27   6    1   0    11

Try to decode with another key:

  C:  22  23   7    15  12  2    18  27   6    1   0    11
  K2: 98  127  98   107 99  101  123 104  100  109 117  110
  M2: 116 104  101  100 111 103  105 115  98   108 117  101
      t   h    e    d   o   g    i   s    b    l   u    e

Perfect encryption

All theoretically unbreakable encryption (except possibly quantum encryption) schemes requires:
- A random key that is at least as long as the message
- That the key is never used more than once

Substitution Cipher

Each letter of the alphabet is represented by some other letter.
The correspondence may be random or systematic
26! possible substitution ciphers
Example: Ceaser cipher:
- C = E(M) = M + 3
- E(a) = d, E(b) = e, ..., E(y) = b, E(z) = c
- E(computer) = frpsxwhu
More general: C = E(M) = M + k

Cryptoanalysis of Ceaser cipher

Cipher-text:

        wklv phvvdjh lv qrw kdug wr euhdn

Method 1: try all 26 different "keys", values of k.

Cryptoanalysis of Ceaser cipher

Cipher-text:

        wklv phvvdjh lv qrw wrr kdug wr euhdn

Look for small words: a, an, am, is, to be, he, we, and, the, you, ...
Strong clues: wrr and wr
Consider: D(wrr) = too, see, add, odd, off, woo, gee
D(wrr) = see implies D(wr) = se
- Not likely

D(wrr) = too implies D(wr) = to

Possible:

        wklv phvvdjh lv qrw wrr kdug wr euhdn
        t                ot too      to

_ot = dot, got, hot, lot, not?
Notice w = t + 3, r = o + 3

More simple ciphers

The Ceaser cipher is a monoalphabetic substitution cipher.
Plain text letter X is always mapped to the same cipher text letter.

Slightly more advanced: define a permutation.

Examples:

Plain-text:      abcdefghijklmnopqrstuvwxyz
Cipher-text:     qwertyuioplkjhgfdsazxcvbnm

C = E(M) = 25 - M

Cryptoanalysis of Monoalphabetic ciphers

Substitute short words at appropriate places in the cipher-text
Utilizing the frequency distribution
Guessing, using clues

Frequency distribution

Frequency distribution for "Hamlet" in english:

Frequency distribution

Frequency distribution for a short part "Hamlet" encrypted with a ceaser cipher:

Frequency distribution

Frequency distribution for a short part "Hamlet" encrypted with a substitution cipher:

Polyalphabetic substitution ciphers

The frequency distribution of monoalphabetic ciphers reflects the distribution of the underlying alphabet
If we use more than one permutation, the frequency distribution of the cipher-text will not match that of e.g. English.

Example:
For odd positions:

M: a b c d e f g h i j k l m n o p q r s t u v w x y z
C: a d g j m o s v y b e h k n q t w z c f i l o r u x

For even positions:

M: a b c d e f g h i j k l m n o p q r s t u v w x y z
C: n s x c h m r w b g l q v a f k p u z e j o t y d i

Example encryption:

M: TREATYIMPOSSIBLE
C: fumnfdyvtfczyshh

Note that e.g. s encrypts to both c and z

Vigenere cipher

Polyalphabetic substitution cipher
Developed in the 16:th century
- Knowledge about cryptoanalysis of monoalphabetic was widespread
"The indecipherable cipher"

Vigenere table

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B   B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 
C   C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 
E   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 
F   F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 
G   G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 
H   H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 
I   I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 
J   J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 
K   K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 
L   L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 
M   M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 
N   N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 
O   O P Q R S T U V W X Y Z A B C D E F G H I J K L M N 
P   P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 
Q   Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 
R   R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 
S   S T U V W X Y Z A B C D E F G H I J K L M N O P Q R  
T   T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 
U   U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 
V   V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W   W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 
X   X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 
Y   Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 
Z   Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Vigenere cipher

Considered unbreakable
First broken by Charles Babbage, about 1854
- Never published
- The technique independetly discovered by Friedrich Wilhelm Kasiski, 1863

Cryptoanalysis of polyalphabetic substitutions

If we can decide the number of alphabets, we can use the frequency distribution of each alphabet the deduce the substitutions
Kasiski method
Index of coincidence

Kasiski method

Relies on the regularity of English
Examples
- -th, -ing, -ed, -ion, -tion, etc. are often repeated
- of, and, to, with, are, etc. are often repeated
If a message is encoded with n alphabets in cyclic rotation, and if a word or letter group appears k times in the plain-text, it should be encoded approximately k/n times to the same cipher-text

Kasiski method

12345 67123 45671 23456 71234 56712 34567 12345
itwas thebe stoft imesi twast hewor stoft imesi

67123 45671 23456 71234 56712 34567 12345 67123
twast heage ofwis domit wasth eageo ffool ishne

45671 23456 71234 56712 34567 12345 67123 45671
ssitw asthe epoch ofbel iefit wasth eepoc hofin

itwasthe is enciphered using the 67123456 alphabets once in the first row and twice in the second row.
The distance between these occurances must be a multiple of the key-length (the number of alphabets)

Distances:

          Starting  Distance Factors
          position
             20
                       63     3,7,9,21,63
             83
                       21     3,7,21
            104

The number of alphabets is probably 3 or 7
Then use e.g. frequence analysis on each alphabet

Kasiski method

Identify repeated patterns of three or more characters
Compute the distances between the starting points of successive instances of a pattern
Determine all factors of each distance
The key length will probably be one of the factors that appears often in step 3.

Index of coincidence

Measures the variation between frequencies in a distribution
Monoalphabetic substitution of English text has a index of coincidence of about 0.068
- 2 alphabets: 0.52, 3: 0.47, etc.
We can use this to validate the predictions from the Kasiski method

Transpositions

The goal of substitution is confusion
The goal of transpositions is diffusion

Columnar transpositions:

    t h i s i
    s a m e s 
    s a g e t
    o s h o w

Ciphertext: t s s o h a a s i m g h s e e o i s t w

Cryptoanalysis

Find the column length
Compare blocks of ciphertext with each other
If common digrams occur, we might know the column length
Digrams: ie, ae, vq, wf, etc.

Transposition algorithms

Use two columnar transpositions

Different number of columns

Table 1:

             t h i s i
             s a m e s 
             s a g e t
             o s h o w

Ciphertext: t s s o h a a s i m g h s e e o i s t w

Table 2:

	     t s s
	     o h a
	     a s i
	     m g h
	     s e e
	     o i s
	     t w X

Final ciphertext: t o a m s o t s h s g e i w s a i h e s X

Generalized transposition:
- Any permutation can be used, as long as it is reversible

ADFGVX

German ADFGVX cipher, introduced in 5 March 1918
Combines substitution and transposition
Quite advanced for its time
Broken by French cryptoanalyst Georges Painvin 2 June 1918

ADFGVX

	A	D	F	G	V	X
A	8	p	3	d	1	n
D	l	t	4	o	a	h
F	7	k	b	c	5	z
G	j	u	6	w	g	m
V	x	s	v	i	r	2
X	9	e	y	0	f	q

Stage 1, substitution
- "8" - AA (position in grid)
- "u" - GD
- "attack at 10pm" - DV DD DD DV FG FD DV DD AV XG AD GX

ADFGVX - Stage 2

Stage 2, Transposition
Add stage 1 text into a table, with a key at the top:

M	A	R	K
D	V	D	D
D	D	D	V
F	G	F	D
D	V	D	D
A	V	X	G
A	D	G	X

Rearrange the columns according to the alphabetical order of the key:

A	K	M	R
V	D	D	D
D	V	D	D
G	D	F	F
V	D	D	D
V	G	A	X
D	X	A	G

Final cipher text: V D G V V D D V D D G X D D F D A A D D F D X G

Cryptoanalysis

Four general types of cryptoanalytic attacks:
1. Cipher-text-only attack
2. Known-plain-text attack
3. Chosen-plain-text attack
4. Chosen-cipher-text attack
Other types of attacks

Cipher-text-only attack

The cryptoanalyst has the cipher-text of one or several messages. We want to recover the plain-text or (better) the key.
Given: C₁ = E(P₁), C₂ = E(P₂), ..., C_i = E(P_i)
Deduce: Either P₁, P₂, ..., P_i, K; or an algorithm to infer P_i+1 from C_i+1 = E(P_i+1).

Known-plain-text attack

We have not only the cipher-text, but also the plain-text of several messages. We want to recover the key.
Given: P₁, P₂, ..., P_i, C₁ = E(P₁), C₂ = E(P₂), ..., C_i = E(P_i)
Deduce: Either K or an algorithm to infer P_i+1 from C_i+1 = E(P_i+1).

Chosen-plain-text attack

We get to select the plain-text that gets encrypted. We want to recover the key.
Given: P₁, P₂, ..., P_i, C₁ = E(P₁), C₂ = E(P₂), ..., C_i = E(P_i)
where we can select P₁, P₂, ..., P_i.
Deduce: Either K or an algorithm to infer P_i+1 from C_i+1 = E(P_i+1).

Chosen-cipher-text attack

We can chose what cipher-texts get decrypted.
Given: C₁, C₂, ..., C_i, P₁ = D(C₁), P₂ = D(C₂), ..., P_i = D(C_i)
Deduce: K

Other attacks

Rubber hose attack:
- We blackmail, threatens or tortures someone until they give us the key
- Sometimes known as purchase-key attack
We can steal the key or bribe someone to give it away
Often the easiest way to break an algorithm

Next time

More secure algorithms