Cryptography 2014
Lecture 1
Introduction
Course info
General concepts
Introductory examples
Symmetric Crypto History
November 15, 2014
1 / 51
Introduction
Cryptography
... is about communication in the presence of adversaries.
(R. Rivest)
Adversary
November 15, 2014
2 / 51
Introduction
Course Objectives
Objectives
Learn how crypto primitives work.
Learn to use them correctly and reason about security.
Be well-oriented in basic cryptographic concepts and methods.
Have a sound understanding of theory and implementation, as well as limitations
and vulnerability.
Be familiar with a number of examples of use of cryptographic tools in common
software and hardware artefacts.
November 15, 2014
3 / 51
Introduction
Why study cryptography?
Cryptography is everywhere!
Where?
Secure Communication: web traffic: HTTPS, wireless traffic 802.11i WPA2 (wifi),
GSM (cellphone), Bluetooth.
Encrypting files on disk: EFS, TrueCrypt
Content protection (DVD, Blu-ray): CSS (Content Scrambling System), AACS
User authentication
November 15, 2014
4 / 51
Introduction
Secure Communication: example
!"#$%&$'()"**+!,#
!"#-%.*$)+!,#
SSL/TLS An attacker cannot eavesdrop/tamper data.
November 15, 2014
5 / 51
Introduction
Secure Communication: Secure Socket Layer/ TLS
Two main parts
1
Handshake Protocol: Establish shared secret key using public-key cryptography
(2nd part of the course).
Record Layer: Transmit data using shared secret key
Ensure confidentiality and integrity (1st part of the course)
November 15, 2014
6 / 51
Introduction
Protected files on disk
!"#$%
+'",(%
&"'(%)%
&"'(%*%
+'",(%
-.%(/0(#12.33"45%
-.%6/73(2"45%
Files encrypted
If data are stolen Attacker (A) cannot read/tamper data
If A tries to modify Alice will detect it
Confidentiality & Integrity!!
Analogous to secure communication:
Alice Today sends a message to Alice Tomorrow
November 15, 2014
7 / 51
Introduction
Crypto Core
Secret key establishment
At the end of the protocol
Alice & Bob share a
secret key k.
*+",#-.&
/(&!"#$%&
*+",#-.&
/(&'()&
Alice will know that she is
talking to Bob.
!"#$%&
'()&
Attacker has no clue
about k.
!"!#$%&'''(
Secure Communication
Attacker A cannot
understand transmitted
messages.
A Cannot tamper
messages.
!"
12"
!"
13"
#$%&'(%)*+,-."*%'",%-(/0,-."
November 15, 2014
8 / 51
Introduction
But crypto can do much more
Digital Signatures
Physical Always the
same!!
Digital A function of
the content signed.
!"#$%&
'#()*+,-%&
Anonymous
Communication
mix-net: Communicate
via a sequence of
proxies.
Messages
encrypted/decrypted
appropriately!
'()&*#*&+&&
,-./&/0"1&/)2&
!"#$%&
November 15, 2014
9 / 51
Introduction
But crypto can do much more
Digital Signatures
Physical Always the
same!!
Digital A function of
the content signed.
!"#$%&
'#()*+,-%&
Anonymous digital cash
Can I spend a digital coin without anyone knowing who I am?
How to prevent double spending?
Anonymity in conflict with security!
If she spends the coin once Anonymous!
More than once Identity exposed!
!"#
!"#$%&
/0-%10%-&
'()&*+,&
-(+-.&
2+0)03&$)4435&
November 15, 2014
9 / 51
Introduction
Protocols
x1 x2 x3 x4 x5
Private Auctions
Auction winner =
highest bidder
pays 2nd highest bid
Other bids remain
secret.
f (x1 , x2 , x3 , x4 , x5 )
Trusted
Party
Goal: compute f (x1 , x2 , x3 , x4 )
How? Secure multi-party computation!!
Theorem:
Anything that can be done with trusted auth. can also be done without.
November 15, 2014
10 / 51
Introduction
Crypto magic
Privately outsourcing computation
.*(/&0#0&'*%&
'%()$*&12)3&
'%()$*&
+,%)-&
!"#$%&
45&+,%)-&6&
45&)%',"/'&6&
)%',"/'&
Zero knowledge (proof of knowledge)
333"
/7189"
456,)"
!"#$%&"'()"*+,'%-."%*"/"00"
1-%%*""2"
:%;"
/"
November 15, 2014
11 / 51
Introduction
A rigorous science
The three steps in cryptography:
Precisely specify threat model
Propose a construction
Prove that breaking a construction under threat model
will solve an underlying hard problem.
November 15, 2014
12 / 51
Introduction
Cryptographic goals
Cryptographic Goals
In spite of adversaries, we want to achieve (among other things)
confidentiality (keeping secret data secret).
integrity (preventing alteration).
authentication (preventing frauds).
non-repudiation (preventing denials of messages sent).
How?
Cryptography provides basic building blocks for use in building secure systems.
November 15, 2014
13 / 51
Introduction
Things to Remember
Cryptography is:
A tremendous tool
The basis for many security mechanisms
Cryptography is not
The solution to all security problems (e.g. software bugs, social engineering)
Reliable unless implemented and used properly
Something you should try to invent yourself
many many examples of broken ad-hoc designs.
November 15, 2014
14 / 51
Introduction
Course data, teachers
Course code TDA351 (Chalmers), DIT250 (GU)
Web site: http://www.cse.chalmers.se/edu/course/TDA351/
Lectures:
Katerina Mitrokotsa
Tutors (problem sessions and home assignments):
Bart van Delft
Andres M
ortberg
Hamid Ebadi Tavallaei
Nikita Frolov
November 15, 2014
15 / 51
Introduction
Teaching
Lectures
Tuesdays 810 in HC4, Wednesdays 810 in HB1, week 17.
Exception week 4 Lectures Wednesday and Friday.
Web site contains info about the topics for the lectures.
Problem-solving sessions
Fridays 1012 in HC1, from week 1.
Home assignment feedback
Comments on your solutions to the assignments.
Office hours
See course web site.
November 15, 2014
16 / 51
Introduction
Course literature and other resources
Text book:
Introduction to Modern Cryptography, Jonathan Katz & Yehuda Lindell
Previous course book also useful: Stallings: Cryptography and Network Security,
6th ed.
Lecture slides, problem sets, home assignments.
Additional useful resources, available on the web:
Handbook of Applied Cryptography, CRC Press 2001.
Selected papers, videos, standards. See course web site.
November 15, 2014
17 / 51
Introduction
Examination
Paper-and-pencil home assignments
Done individually. Available on course web site; First to be discussed in the class.
Programming assignment
One assignment; done in groups of two or individually.
Exam
Written (closed-book) exam on the 13th of January at 14:00-18:00.
November 15, 2014
18 / 51
Introduction
Course evaluation
Chalmers procedure
Victor Lindhe (lvictor@student.chalmers.se)
Oskar Montin (oskarmo@student.chalmers.se)
Brian Mwambazi (mwambazi@student.chalmers.se)
Linnea Otterlind (linott@student.chalmers.se)
Georgios Petros Sideris (sideris@student.chalmers.se)
Your input is important to improve the course!
Reimbursement for volunteers: 200 kr voucher at Cremona.
November 15, 2014
19 / 51
Introduction
Other security courses at Chalmers and GU
Informal security specialization
We offer a package of four courses in computer and network security, that complement
each other:
Cryptography (period 2)
Computer security (period 3)
Language-based security (period 4)
Network security (period 4)
More info at http://www.cse.chalmers.se/edu/master/secspec.
November 15, 2014
20 / 51
Introduction
Online crypto courses
Stanford crypto course online
Contains video lectures, quizzes, problem sets, programming assignments,. . .
We will use material from this course.
See https://www.coursera.org/course/crypto
Basic Probabilities & Math
Do a recap on math and basic probabilities:
http://en.wikibooks.org/High_School_Mathematics_Extensions/Discrete_Probabil
November 15, 2014
21 / 51
Symmetric Crypto: History
Building block: Symmetric Encryption
Alice: k
m
Bob: k
c:=E(k,m)
same key!
m
D
Symmetric ciphers
E , D: cipher, k: secret key (e.g. 128 bits)
m, c: plaintext, ciphertext
November 15, 2014
22 / 51
Symmetric Crypto: History
Building block: Symmetric Encryption
Alice: k
m
Bob: k
c:=E(k,m)
same key!
m
D
Symmetric ciphers
E , D: cipher, k: secret key (e.g. 128 bits)
m, c: plaintext, ciphertext
Attention: Encryption algorithm is publicly known Never use a proprietary cipher!
November 15, 2014
22 / 51
Symmetric Crypto: History
Building block: Symmetric Encryption
Alice: k
m
Bob: k
c:=E(k,m)
same key!
m
D
Symmetric ciphers
E , D: cipher, k: secret key (e.g. 128 bits)
m, c: plaintext, ciphertext
Attention: Encryption algorithm is publicly known Never use a proprietary cipher!
Kerckhoffs principle
Security should not rest on secrecy of the algorithms, but only on the secrecy of K .
November 15, 2014
22 / 51
Symmetric Crypto: History
Use Cases
Single use key (one time key)
Key is only used to encrypt one message
Example: encrypted email new key generated for every email.
Multi use key (many time key)
Key used to encrypt multiple messages
Encrypted files: same key used to encrypt many files
Need more machinery than for one-time key!
November 15, 2014
23 / 51
Symmetric Crypto: History
Historical development
Ancient times 1920.
Paper-and-pencil systems
Substitution, transposition, Vigen`ere, Vernam, . . .
1920 1960.
(Pre-computer) machine ciphers
Enigma, Purple, Hagelin, . . .
1960
Computer-based systems
These are the main topics of this course.
1990
Cryptography everywhere.
November 15, 2014
24 / 51
Symmetric Crypto: History
Classification of Classical Cryptosystems
Ciphers
There are two types of basic algorithms:
transposition ciphers rearrange the order of letters in plaintext.
Example: transposition 7 POISONISNTART
substitution ciphers replace characters in plaintext by others.
Example: substitution 7 TVCTUJUVUJPO where a 7 B, b 7 C, c 7 D, .
November 15, 2014
25 / 51
Symmetric Crypto: History
Notational Convention
For today (only) we will use the following conventions:
Messages are supposed to be in English.
We use the 26 letters only. Space, comma, period etc. are usually ignored.
Texts are written in groups of five characters.
Plaintexts are in lower case.
plain textl ooksl iketh is
Ciphertexts are in upper case.
SODLQ WHAWO RRNVO LNHWK LV
November 15, 2014
26 / 51
Symmetric Crypto: History
Transposition Cipher
Plaintext is divided into blocks of the same size n.
Here, for explanation, we choose n = 10.
012345 67 89 01234567 89 0 12 3456 789 0123456789
theory of re lativity ca n be used for cryptology
A key is a permutation of (0, 1, , n 1), say (9, 3, 0, 5, 2, 7, 8, 1, 4, 6)
Characters in a plaintext block are rearranged according to the key.
01234 56789 7 93052 78146
theor yofre
EOTYE FRHRO
This is repeated for each plaintext block.
EOTYE FRHRO AILIT YCAVT RUNEE FOBSD YPCOY OGRTL
November 15, 2014
27 / 51
Symmetric Crypto: History
Transposition cipher as circuit
We can illustrate (and implement in hardware) the permutation (9, 3, 0, 5, 2, 7, 8, 1, 4, 6)
as follows:
Transposition ciphers form part of many modern ciphers.
November 15, 2014
28 / 51
Symmetric Crypto: History
Transposition variants
A major problem in the old days was to remember the permutation. Some tricks used:
Route transposition: Plaintext is written in one pattern (diagonal, spiral, triangle,
) and read out in another.
5
0
0
Use of keywords, e.g. alphabetical ordering of letters in 0231 gives (0, 2, 3, 1) for
clue
n = 4.
Longer blocks means more security and more difficulty in remembering key!
November 15, 2014
29 / 51
Symmetric Crypto: History
Size of the key space
Brute force attack are infeasible
A transposition cipher with block size n has as key a permutation of (0, 1, 2, . . . , n 1)
The number of such permutations is n!, which grows very fast with n.
Examples: 20! 2.4 1018 ,
100! 9.3 10157 .
But ...
Transposition ciphers (with reasonable block sizes) are easily broken using frequency
analysis.
November 15, 2014
30 / 51
Symmetric Crypto: History
Few Historic Examples (all badly broken)
ac
bw
cn
Substitution cipher
c := E (k, bcza) = wnac
D(k, c) = bcza
k :=
...
za
November 15, 2014
31 / 51
Symmetric Crypto: History
Caesars cipher
Caesars cipher
Each letter in the plaintext is replaced by the letter three steps ahead
plain alphabet
cipher alphabet
a b c d e f g h i j k l m n o p q r s t u v w
D E F G H I J K L M N O P Q R S T U V W X Y Z
M = one one two
C = RQH RQH WZR
Decryption is done by shifting back each cipher letter three steps.
Problem
Encryption method must be kept secret from the adversary!
There is no key!
If method becomes known, all is lost.
November 15, 2014
32 / 51
Symmetric Crypto: History
Caesar Cipher
Caesar cipher
Shift by 3
ad
be
cf
...
yb
zc
November 15, 2014
33 / 51
Symmetric Crypto: History
Quiz question!
Key space of substitution ciphers
What is the size of key space in the substitution cipher assuming 26 letters?
1
|K| = 26
|K| = 26!
|K| = 226
|K| = 262
The key is a permutation of the 26 letters.
Large key space but terribly insecure via letter frequencies.
November 15, 2014
34 / 51
Symmetric Crypto: History
Quiz question!
Key space of substitution ciphers
What is the size of key space in the substitution cipher assuming 26 letters?
1
|K| = 26
|K| = 26! 26! = 288
|K| = 226
|K| = 262
November 15, 2014
34 / 51
Symmetric Crypto: History
Comparison substitution & transposition ciphers
Transposition cipher: key a permutation of positions in a block applies the key to
each block in the message, regardless of the letters in the block.
November 15, 2014
35 / 51
Symmetric Crypto: History
Comparison substitution & transposition ciphers
Transposition cipher: key a permutation of positions in a block applies the key to
each block in the message, regardless of the letters in the block.
Substitution cipher: key a permutation of the alphabet applies the key to each
letter in the message.
November 15, 2014
35 / 51
Symmetric Crypto: History
How to break a substitution cipher?
What is the most common letter in English text?
1
November 15, 2014
36 / 51
Symmetric Crypto: History
How to break a substitution cipher?
Use frequency of English letters
e: 12.7% , t: 9.1%, a:8.1%
Use frequency of pairs of letters (digrams)
he, an, in, th
Ciphertext only attacks!
November 15, 2014
37 / 51
Symmetric Crypto: History
(What types of attacks do we have?
Types of attacks
Ciphertext only attack: The Adversary has one or more ciphertexts.
Known plaintext attacks: The Adversary has one or more plaintexts and the
corresponding cipher texts.
Chosen plaintext attack: The Adversary can choose plain texts, have them
encrypted and obtain the corresponding ciphertexts.
November 15, 2014
38 / 51
Symmetric Crypto: History
English letter frequency distribution
(sorted)
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
(
%)
( 8.07)
( 1.40)
( 2.27)
( 4.71)
(12.49)
( 2.26)
( 2.08)
( 6.57)
( 6.81)
( 0.11)
( 0.79)
( 3.68)
( 2.56)
( 7.08)
( 7.74)
( 1.62)
( 0.11)
( 6.16)
( 6.30)
( 8.99)
( 2.78)
( 0.86)
( 2.37)
( 0.11)
( 2.03)
( 0.04)
e
t
a
o
n
i
h
s
r
d
l
u
m
w
c
f
g
y
p
b
v
k
q
x
j
z
November 15, 2014
39 / 51
Symmetric Crypto: History
An Example
Ciphertext
UKBYBIPOUZBCUFEEBORUKBYBHOBBRFESPVKBWFOFERVNBCVBZPRUBOFER
VNBCVBPCYYFVUFOFEIKNWFRFIKJNUPWRFIPOUNVNIPUBRNCUKBEFWWFDNC
HXCYBOHOPYXPUBNCUBOYNRVNIWNCPOJIOFHOPZRVFZIXUBORJRUBZRBCHN
CBBONCHRJZSFWNVRJRUBZRPCYZPUKBZPUNVPWPCYVFZIXUPUNFCPWRVNB
CVBRPYYNUNFCPWWJUKBYBIPOUZBCUIPOUNVNIPUBRNCHOPYXPUBNCUBOY
NRVNIWNCPOJIOFHOPZRNCRVNBCUNENVVFZIXUNCHPCYVFZIXUPUNFCPWZP
UKBZPUNVR
!" #$"
!!!"!
%" #&"
%*"
++"
!!!%&!
'.!" $"
('"
+,"
!!!$#!
/0%" $"
'" ##"
!!!#!
'!" +,"
(" #)"
!!!$!
'%"
*" )$"
-"
123"
!!!#'"!
&"
;756789:"
456789:"
November 15, 2014
40 / 51
Symmetric Crypto: History
Shift encryption example
Left diagram shows letter frequencies in ciphertext;
right shows distribution in English.
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
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
(
%)
( 8.07)
( 1.40)
( 2.27)
( 4.71)
(12.49)
( 2.26)
( 2.08)
( 6.57)
( 6.81)
( 0.11)
( 0.79)
( 3.68)
( 2.56)
( 7.08)
( 7.74)
( 1.62)
( 0.11)
( 6.16)
( 6.30)
( 8.99)
( 2.78)
( 0.86)
( 2.37)
( 0.11)
( 2.03)
( 0.04)
Slide left diagram downwards (with wrap-around) until it matches the right.
November 15, 2014
41 / 51
Symmetric Crypto: History
Shift encryption example
Left diagram shows letter frequencies in ciphertext;
right shows distribution in English.
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
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
(
%)
( 8.07)
( 1.40)
( 2.27)
( 4.71)
(12.49)
( 2.26)
( 2.08)
( 6.57)
( 6.81)
( 0.11)
( 0.79)
( 3.68)
( 2.56)
( 7.08)
( 7.74)
( 1.62)
( 0.11)
( 6.16)
( 6.30)
( 8.99)
( 2.78)
( 0.86)
( 2.37)
( 0.11)
( 2.03)
( 0.04)
Slide left diagram downwards (with wrap-around) until it matches the right.
Can we do it better than visually?
November 15, 2014
41 / 51
Symmetric Crypto: History
Correlation
25
Let {fi }25
i =0 be observed relative letter frequencies in ciphertext and {pi }i =0 letter
frequencies in English.
If (unknown) shift is k, then we should have fi p(i +k) mod 26 .
To find k, we compute
ck =
25
X
fi p(i +k) mod 26
i =0
for k = 0, 1, . . . 25. The k for which ck is maximal is likely to be the correct shift.
In fact, maximal ck is expected to be ca 0.066, while all others are around 0.038.
November 15, 2014
42 / 51
Symmetric Crypto: History
Vigener Cipher (16th century, Rome)
!""""#"""""C R Y P T O C R Y P T O C R Y P T
%&"$'(")*+"
""""$"""#"""""W H A T A N I C E D A Y T O D A Y
"""""","""#"""""Z Z Z J U C L U D T U N W G C Q S
period = key length
If we assume that most common first letter in the encrypted blocks is H
Then: first letter of the key = H - E =C
November 15, 2014
43 / 51
Symmetric Crypto: History
Vigener Cipher (16th century, Rome)
Step 1: Find the key length!
Step 2: Perform a frequency analysis of the ciphertext!
November 15, 2014
44 / 51
Symmetric Crypto: History
Vigener Cipher (16th century, Rome)
How to identify the key length?
Two occurrences of the same word
in the plaintext will get different
encryptions
. . . unless they occur in positions
that differ by a multiple of the
period.
Example
ASXER
FFSTS
DHSDF
HMHKO
CDMBV
FDLKG
DOSVW
AKEWQ
DCRWE
DBEBD
BDHFG
FHGLS
OWESS
ALQWE
RCVMG
GFROI
GNBLK
SDVKH
DGAGF
EKKEW
LERRK
OLFGL
RTYJH
FSERF
JHKFV
DSPIO
DLHMD
LSATR
FLFRL
DEFES
DRDGN
NJLDM
BEBDG
FLEKG
YLKRU
SDEYN
Easy to break the Vigenere cipher
Two occurrences of an n-gram (with n > 3) in the ciphertext is likely to be caused by
the same plaintext separated by a number of full periods.
November 15, 2014
45 / 51
Symmetric Crypto: History
Kasiskis test
Kasiskis test
Find (several) repeating n-grams in ciphertext and for each pair compute the
distance (difference in position) between the two occurrences.
The period is probably a common factor of all these numbers. So, compute the
(pairwise) gcd of the distances.
Example
CDRAWSD occurs in a ciphertext at position 37, 254 and 457.
gcd(254 37, 457 254) = 7, so probable period is 7.
Reveal the key period
For reasonably long ciphertexts, this will reveal the period.
November 15, 2014
46 / 51
Symmetric Crypto: History
Rotor Machines
!"
#"
$"
%"
%"
&"
'"
("
/01"
)"
*"
+"
%"
%"
,"
-"
."
."
)"
*"
+"
%"
%"
,"
-"
-"
."
)"
*"
+"
%"
%"
,"
November 15, 2014
47 / 51
Symmetric Crypto: History
Rotor Machines
Most famous: the Enigma (3-5 rotors)
Number of keys = 264 = 218
November 15, 2014
48 / 51
Symmetric Crypto: History
Data Encryption Standard (1974)
Data Encryption Standard
Number of keys = 256 , block size = 64 bits Broken
Current ciphers: AES (2001) (128 bit keys), Salsa20 (2008) many many others
November 15, 2014
49 / 51
Symmetric Crypto: History
Things to remember
Things to remember
Cryptography is a tremendous tool !
Not the solution to all security problems!!
Security should not rest on the secrecy of algorithm.
Historical ciphers all badly broken
Questions
How do we break a substitution cipher?
What is the difference between a substitution and a transposition cipher?
How can we break the Vigener cipher?
Tomorrow One Time Pad & Stream ciphers
November 15, 2014
50 / 51
Symmetric Crypto: History
References:
Crypto Course Stanford, Dan Boneh
Cryptography and Network Security: Principles and practice (Chapters 1.1, 2)
Introduction to Modern Cryptography, Lindell and Katz (Chapter 1)
Thank you for your attention!
November 15, 2014
51 / 51
