1
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.12
Overview
2
A,J,Menezes,P,C,van Oorschot and S,A,Vanstone,
Handbook of Applied Cryptography,CRC Press,1997,
Bruce Schneier,Applied Cryptography,Second Edition,
Protocols,Algorthms,and Source Code in C (cloth) John
Wiley & Sons,Inc.) 1996
Douglas R,Stinson,Cryptography (Theory and Practice),
CRC Press 1995
Resources
3
?Overview, Secure communication,Attacks to
cryptosystems,One time pad,randomness and pseudo-
randomness
?Secret-Key Cryptography,Block ciphers,DES,AES
(Rijndael),Modes of operation,Linear and Differential
cryptanalysis,
?Public-Key Cryptography,Mathematical Foundations,
One-way functions,Trapdoor one-way functions,Public-key
cryptosystems,RSA,Diffie-Hellman,ElGamal,and elliptic
curve cryptosystems,
?Design and Analysis of Cryptographic Protocols,
Authentication protocols,Digital cash,Sharing and partial
disclosure of secrets,Zero-knowledge proof systems,
Identification protocols,Key management architectures
Course Outline
4
Some Security Properties
? Integrity,no improper modification
– Authenticity,integrity of source
– Non-repudiation,integrity of commitments
– Accountability,integrity of responsibility
? Secrecy,no improper disclosure
– Privacy,secrecy of personal data
– Anonymity,unlinkable secrecy of identity
– Pseudonymity,linkable secrecy of identity
? Availability,no improper denial of service
5
Correctness vs,Security
? Correctness,satisfy specifications
– For reasonable inputs,
get reasonable output
? Security,resist attacks
– For unreasonable inputs,
output not completely disastrous
? Main difference
– Active interference from the environment
6
Attack Goals
? Publicity
? Fraud
? Disruption
? Invasion
of privacy
–,
? Terrorism
? Landing in Red Square
? Bank robbery
? Scams
? Plagiarism
? Vandalism
? Obstruction of justice
? Collection of personal
data
? Espionage
in the physical world
? Highly contagious viruses
? Defacing web pages
? Credit card number theft
? On-line scams
? Intellectual property theft
? Wiping out data
? Denial of service
? Reading private files
? Surveillance
in the electronic world
7
Vulnerable Systems,a Trend
? The Internet
– World-Wide connection
– Distributed,no central design and control
– Open infrastructures,modems,wireless,DHCP
– Untrusted software,applets,downloads
– Unsophisticated users
? Security costs
– Market now,fix bugs later
– Customers want it,
but won’t pay for it
? Homogeneity
– Hardware,x86
– OS,Windows
– Applications,
Vulnerability,a weakness that
can be exploited to cause damage
Attack, a method to exploit a
vulnerability
8
Attacks,Services,and Mechanisms
* Security Attack,Any action that compromises the security
of information,
* Security Mechanism,A mechanism that is designed to
detect,prevent,or recover from a security attack,
* Security Service,A service that enhances the security of
data processing systems and information transfers,A
security service makes use of one or more security
mechanisms,
9
Some Attacks
? Unintended blunders
? Hackers driven by technical challenge
? Disgruntled employees or customers
? Petty criminals
? Organized crime
? Organized terror groups
? Foreign espionage agents
? Information warfare
10
- confidentiality,only authorized parties have read
access to information
- integrity,only authorized parties have write access
to information
- availability,authorized access to information when
needed
- authenticity,identity claims (user,message source)
can be verified
- non-repudiation,message exchange can be proved
by sender and receiver
- authorization,information / system / resource
access control
Security services
11
Authentication
? Peer Entity Authentication – in a connection based
environment; provide confidence in the identity of a
connecting entity
– Logging in with a password
– Gaining access via biological identity verification
? DNA identification,retinal scan,finger/hand print
identification
– Access via audio voice identification
? Data Origin Authentication – in a connectionless
environment; provide assurance that the source of received
data is as claimed
– Corroborates the source of the data
– Does not proved assurance against duplicate or
modified data
12
Access Control
? This service provides protection against unauthorized use
of resources accessible via OSI,These may be OSI or non-
OSI resources accessed via OSI protocols,This protection
service may be applied to various types of access to a
resource or to all accesses to a resource
– e.g.,the use of a communications resource; the reading,
the writing,or the deletion of an information resource;
the execution of a processing resource
13
Data Confidentiality
? Connection Confidentiality
– Protection of all user data on a connection
? Connectionless Confidentiality
– Protection of all data within a single data block
? Selective-Field Confidentiality
– Insure confidentiality of selected fields with within the
user data on a connection or in a single data block
connection
? Traffic-Flow Confidentiality
– Protection of information that might be derived by
observing the traffic flow patterns
14
Data Integrity
? Connection Integrity with Recovery
– Detect any modification of stream data or replay of data and
retry;
? Connection Integrity without Recovery
– Detect any modification and report it,no retry…continue on
? Selective-Field Connection Integrity
– Same except for selected fields
? Connectionless Integrity
– Detect modifications in fixed block connectionless data,may
provide replay detection and protection
? Selective-Field Connectionless Integrity
– Same,except for selected fields
? Total stream protection would encompass all of the above and is
probably the best strategy
15
Nonrepudiation
? Nonrepudiation,Origin
– Proof that the message was sent by the specified party
? Nonrepudiation,Destination
– Proof that the message was received by the specified
party
16
Security Mechanisms (X.800)
? Encipherment – algorithmic/mathematical conversion
? Digital Signature – appending a secret signature
? Access Control -
? Data Integrity
? Authentication Exchange
? Traffic Padding – appending extra chars to foil traffic
analysis techniques
? Routing Control – selection of secure routeds through the
network
? Notarization – use a trused 3rd party (like a notary public)
17
Other Security Mechanisms(non X.800)
? Trusted Functionality
– That which is perceived to be true by some criteria
(policy)
? Security Label
– The marking of (bound to) a resource that names or
designates the security attributes of the resource
? Event Detection
– Intrusion detection
– Detection of specific hacks (detector hardware)
– Too many log in attempts
? Security Audit Trail
– Logging of all system events
? Security Recovery
– Recovery based on requests from security mechanisms
and/or event handling,
18
The Compromises of Security
? There is no absolute security!
? Race between attackers and defenders
? Constant innovation
? Well-funded,capable,determined attacker succeed
? Costs
? Relative to target’s value
? Users’ inconvenience
? Users’ acceptance
? Detection
? Rarely possible in real time
? Works mostly for
old threats
? Punishment
? Hard at a distance
? No international
legislation
? Poor domestic
legislation
? Perceived,unethical”
? Freedom of expression
? Intangibility
19
Information security and cryptography
? Cryptography is the study of mathematical
techniques related to aspects of information
security
? Cryptographic goals
– Confidentiality
– Data integrity
– Authentication
– Non-repudiation
– ……………
20
Cryptographical Building Blocks
Block
Ciphers
Stream
Ciphers
Symmetric Key
Cryptography
Authentication Privacy
Encryption
Hash
Functions
Challenge
Response
IVs
MACs
MICs
Message
Digests Nonces
Pseudo
Random
Random
Sources
Secret
Keys
Smart
Cards
DH
RSA
Public Key
Cryptography
Elliptic
Curves
Digital
Signatures
Data
Integrity
Secure Network Protocols
Non-
Repudiation
21
Is Cryptography the Solution?
Cryptography is not the same as security
– 85% of all CERT advisories cannot be fixed by crypto
– 30-50% of recent security holes from buffer overflow
Computer Security
Cryptography
Law
Operating
systems
Mathematics
Networking
Programming
languages
Economics
Psychology
Human
computer
interaction
22
Is Cryptography the Solution?
? The real world offers the attacker a richer menu of
options than mere cryptanalysis,
? Often more worrisome are protocol attacks,Trojan
horses,viruses,electromagnetic monitoring,
physical compromise,blackmail and intimidation
of key holders,operating system bugs,application
program bugs,hardware bugs,user errors,
physical eavesdropping,social engineering,and
dumpster diving,to name just a few,
23
Security Standards
Internet - Internet Engineering Task Force (IETF)
De Facto (PGP email security system,Kerberos-MIT)
ITU (X.509 Certificates)
National Institute of Standards and Technology (SHA)
IEEE
Department of Defense,Nat,Computer Security Center
- Tempest (radiation limits)
- Orange Book,Class A1,B3,C1,C2,..,
Export Controls
- High Performance Computers
- Systems with,Hard” Encryption
24
A Brief History of Cryptography
? ~2000 years ago,Substitution ciphers
? A few centuries later,Permutation ciphers
? Renaissance,Polyalphabetic ciphers
? Jefferson Cylinder (1790)
? Wheatstone disc (1870)
25
A Brief History of Cryptography
? The Enigma Rotor Machine (WW2)
? 1975,DES
? 1976,Public-key cryptography
? 1996-2000 AES
26
Cryptosystem
? A cryptosystem is a five -tuple (P,C,K,E,D),
where the following conditions are satisfied,
? 1,P is a finite set of possible plain texts
? 2,C is a finite set of possible ciphertexts
? 3,K,the keyspace,is a finite set of possible
keys
? 4,For each k?K,there is an encryption rule
eK ? E,and a corresponding decryption rule
dK ? D),Each eK, P ? C and dK, C ? P are
functions such that dK(eK(x)) = x for every
plaintext x ? P,
27
Taxonomy of cryptographic
primitives,
Arbitrary length hash functions
One-way permutations
Random sequences
Symmetric-key ciphers
Arbitrary length hash functions(MACs)
Signatures
Pseudorandom sequences
Identification primitives
Public-key ciphers
Signatures
Identification primitives
Unkeyed
Primitives
Symmetric-key
Primitives
Public-key
Primitives
Security
Primitives
Block
ciphers
Stream
ciphers
28
Cryptography - Terminology I
Cryptology is a branch of mathematics
Cryptology
Cryptography
?Art and science of
keeping messages secure,
Cryptanalysis
?Art and science of
breaking ciphertext,
29
Cipher
Cryptography - Terminology II
Encryption
EK(P) = C
plaintext
we
attack
at dawn
P
sorqjz
plvnwk
ghanqd
C
ciphertext
we
attack
at dawn
P
sorqjz
plvnwk
ghanqd
C
Decryption
DK(C) = P
key K
key K
30
Crypto tools
? one-way function
? Encryption/decryption – to hide info
? Key exchange - to establish shared key
? Authentication – to establish shared key with
the party you really meant to
– public
– private
? Signatures
? Hashing
? Certificates,PKI
31
Background on Functions
? Function
– f, X ? Y is called a function f from set X to set Y,
? X,domain; Y,codomain,
– for y = f(x) where x ? X and y ? Y
? y,image of x
? x,preimage of y
– Im(f),image of f
? the set that all y ? Y have at least one preimage
? 1 ? 1 function if
– each element in Y is the image of at most one element in X,
? onto function if
– Im(f) =Y
? bijection function if
– f is 1?1 and onto,
32
Background on Functions (ctd)
? one-way function if
– f(x) is easy to compute for all x ? X,but
– it is computationally infeasible to find any x ? X
such that f(x) =y,
? trapdoor one-way function if
– given trapdoor information,it becomes feasible to
find an x ? X such that f(x) =y,
33
Encryption / Decryption
encoder
decoder
(plaintext in -
ciphertext out)
ciphertext
msg
(ciphertext in
- plaintext out)
(should understand
nothing about the msg)
eavesdropper
bla-bla
cmb-cmb bla-bla
Shared Key
34
Key exchange
? Alice and Bob want to establish a shared
secret (key) when other people
(eavesdroppers) are listening
– Passive – just looking
– Active – may change msgs
Alice
Bob
35
Key exchange,man-in-the-middle
? Key exchange without Authentication
– Subject to Man-in-the-Middle attack
– Attacker translates between the keys,reading and/or
modifying the messages
– Authentication afterwards will not help!
Alice Bob
Shared
w/Alice Shared
w/Bob
36
Authentication
M
Alice Bob
Alice sends a msg to Bob
Bob wants to be sure the msg is really from
Alice
?the problem of proving that a user is who he
says he is
37
Signatures
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,… )
38
Authentication:,public”
Alice
Bob
? checks
? contracts
39
Public Key Signatures
PAlice
Alice Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,PAlice )
? Public Key
? Secret Key
40
Certificates
?,This public key PAlice really belongs to Alice,
Signed by Charlie,Certification Authority”
? Certificates can be public!
? Who’s Charlie?!?
Alice Charlie,
CA
SAlice
? Public Key
? Secret Key
PAlice
PAlice
CA
41
Public Key Infrastructures (PKI)
? Root CA public key
– Obtained out-of-band
– Certifies other Public Keys
(of CAs,or users)
? Certification Chains
? Grain of salt,so,you have a certificate…
? To be continued…
42
Signatures
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,… )
43
Authentication:,private”
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
SAlice
Verify(M,SigM,SAlice ),
Check SigM= Sign(M,SAlice )
Message Authentication Code (MAC)
Sign(M,SAlice )=Hash(M,SAlice )
MAC =,Shared Secret Sig” =
Symmetric Sig (Sign=Verify)
45
Cryptanalysis - Fundamental
Assumptions
? Attacker knows every detail of the cryptographical
algorithm
? Attacker is in possession of encryption / decryption
equipment (HW machine or SW implementation)
? Attacker has access to an arbitrary number of
plaintext / ciphertext pairs generated with the same
(unknown) key,
? Strong cipher,Best attack should be brute force key
search!
The security of a cipher should rely
on the secrecy of the key only!
Auguste Kerckhoffs,?La Cryptographie militaire“,1883
46
Cryptanalysis - Types of Attacks
? Ciphertext-Only Attack
– Attacker knows ciphertext of several messages encrypted with
the same key and/or several keys
– Recover the plaintext of as many messages as possible or even
better deduce the key (or keys)
– Given,C1 = Ek(P1),C2 = Ek(P2),...Ci = Ek(Pi)
Deduce,Either P1,P2,...Pi; k; or an algorithm to
infer Pi+1 from Ci+1 = Ek(Pi+1)
? Known-Plaintext Attack
– Known ciphertext / plaintext pair of several messages
– Deduce the key or an algorithm to decrypt further messages
– Given,P1,C1 = Ek(P1),P2,C2 = Ek(P2),...Pi,Ci = Ek(Pi)
– Deduce,Either k,or an algorithm to infer Pi+1 from
Ci+1 = Ek(Pi+1)
47
Cryptanalysis - Types of Attacks
? Chosen-Plaintext Attack
– Attacker can choose the plaintext that gets encrypted thereby
potentially getting more information about the key
– Given,P1,C1 = Ek(P1),P2,C2 = Ek(P2),...Pi,Ci = Ek(Pi),
where the cryptanalyst gets to choose P1,P2,...Pi
Deduce,Either k,or an algorithm to infer Pi+1 from
Ci+1 = Ek(Pi+1)
? Adaptive Chosen-Plaintext Attack
– Attacker can choose a series of plaintexts,basing choice on the
result of previous encryption ? differential cryptanalysis!
? Chosen-ciphertext attack
– Given,C1,P1 = Dk(C1),C2,P2 = Dk(C2),...Ci,Pi = Dk(Ci)
– Deduce,k
48
Models for evaluating security
? Unconditional security (perfect secrecy)
– Adversaries have unlimited computational resources
– Observation of the ciphertext provides no information to an
adversary
– One time pad
? Complexity-theoretic security
– Adversaries have polynomial computational power,
– Asymptotic analysis and usually also worst-case analysis is
used
? Provable security
– provably secure if the difficulty of defeating crypto system
can be shown to be as difficult as solving a well-known
number-theoretic problem
49
Models for evaluating security (ctd)
? Computational security (Practical security)
– We might define a cryptosystem to be computationally secure
if the best algorithm for breaking it requires at least N
operations,where N is some specified,very large number,
– The problem is that no known practical cryptosystem can be
proved to be secure under this definition,
– neither the Shift Cipher,the Substitution Cipher nor the
Vigenke Cipher is computationally secure against a
ciphertext-only attack (given a sufficient amount of
ciphertext),
? Ad hoc security (heuristic security)
– any variety of convincing computational security
– unforeseen attacks may remain
50
Cipher = Encoder; or Encryption/Decryption scheme
Stream cipher encodes/decodes char by char
Block cipher encodes/decodes block by block
Stream cipher ~ Block cipher with block size of 1 char
(+state)
Chaining (Modes of Operation) –
– make block encryption depend on the past blocks
–,make block ciphers more like stream ciphers”
Block vs,Stream Ciphers
51
Symmetric & Asymmetric schemes
? Symmetric,
– decryption as easy as encryption (and vice versa)
i.e,if you can encrypt then you can decrypt
(and vice versa)
(DES,AES/Rijndael are symmetric block ciphers)
? Asymmetric,
– may not be able to decrypt even if can encrypt
(and vice versa)
e.g,RSA
52
Classical Cryptography
? Simple Methods
– Transposition
? Arrange the,plaintext” in a special permutation
– Substitution
? Replace letters of the,plaintext” with other letters or
symbols in a certain way
? Caesar’s Cipher,
A ? C
B ? E
D ? F
…
X ? A
Y ? B
Z ? C
53
Classical Cryptography
? Problem with simple methods
– Security depends on the secrecy of the entire
encrypting/decrypting process
– Need a way to ensure secrecy even if the
encryption process is compromised
54
Classical Cryptography
? Key-based Cryptography
– Private Key
? Secret key locks and unlocks data
? Encrypt – EPri(P) = C
? Decrypt – DPri(C) = P
– Public Key
? Separate keys to lock and unlock data
? Encrypt – EPub(P) = C
? Decrypt – DPri(C) = P
55
Classical Cryptography
? Problem with private-key encryption
– Depends entirely on the secrecy of the key
– Requires two parties who initially share no
secret information to exchange a secret key
– An eavesdropper can passively snoop secret
key as it’s being exchanged
56
Classical Cryptography
? Problems with Public-key encryption
– No key distribution problem
– However,security relies on unproven
mathematical assumptions such as the difficulty
of factoring large integers
– Shor has already shown that the assumption
wont hold up against quantum computation
57
Summary of comparison
? public-key cryptography
– signatures (particularly,non-repudiation) and key
management
? symmetric-key cryptography
– encryption and some data integrity applications
? Key sizes
– Private keys must be larger (e.g.,1024 bits for RSA) than
secret keys (e.g.,64 or 128 bits)
? most attack on symmetric-key systems is an exhaustive key search
? public-key systems are subject to,short-cut” attacks (e.g.,factoring)
58
open channel
Symmetric or Secret-Key
Algorithms
? Same key used for encryption and decryption
? Key must be kept absolutely secret
? Same key can be used for several messages,but
should be changed periodically ? secure key
distribution problem!
Encryption
EK(P) = C
plaintext
P
Decryption
DK(C) = P
ciphertext plaintext
P C
key K key K
distribution of secret-key over secure channel
59
Symmetric Algorithms,Block
Ciphers
ciphertext blocks n bits
n bits plaintext blocks n bits
n bits
Common Block Sizes,
n = 64,128,256 bits
Common Key Sizes,
k = 40,56,64,80,128,
168,192,256 bits
k bits
Key
Block Cipher
60
Some Popular Block Ciphers
Block Size Name of Algorithm Key Size
DES (Digital Encryption Standard,IBM) 64 56
3DES (Triple DES) 64 168
IDEA (Lai / Massey,ETH Zürich) 64 128
RC2 (Ron Rivest,RSA) 64 40,.,1024
CAST (Canada) 64 128
Blowfish (Bruce Schneier) 64 128,.,448
Skipjack (NSA,clipper chip,was classified) 64 80
RC5 (Ron Rivest,RSA) 64,.,256 64,.,256
61
Claude Shannon *1916
? Information Theory
– Worked at MIT / Bell Labs
– ?The Mathematical Theory of
Communication,(1948)
– Maximum capacity of a noisy
transmission channel
– Definition of the ?binary digit,(bit)
as a unit of information
– Definition of ?entropy,as a
measure of information
? Cryptography
– Model of a secrecy system
– Definition of perfect secrecy
– Principles of ?confusion,and
?diffusion,The Father of Information Theory
62
Cryptoanalytic Attacks
E
21
T
18
A
16
O
16
N
14
I
13
R
13
S
12
H
12
D
8
L
7
U
6
C
6
M
6
P
4
F
4
Y
4
W
3
G
3
B
3
V
2
J
1
K
1
X
1 ?
Q Z
?
high frequency group medium frequency group
low frequency group rare group
Frequency table of 200 English letters
63
Shannon‘s Definition of Perfect
Secrecy
m ciphertext C
One-Time Pad
k bits of random key K
1 0 0 1 1 0 1 0 1 0
0 1 1 1 0 1 1 0 1 1
1 1 0 1 0 0 0 1 1 1
use random key sequence
only once and then discard it !
The One-Time Pad
Ek(m) = m ? k
k
64
One-time random pad (cont.)
? Symmetric
? Pad is selected at random
? perfectly secure,but..,
? One time only
so sending the pad is just as hard as
sending the msg
65
Pseudo-random bit string (PRBS) generator,
PRBS = Hard to guess a bit (after seeing many others)
Pseudo-random pad
seed
(short)
PRBS
(long)
01101 1010010110...,
66
Complexity,what is,hard”?
measure hardness in terms of size of input
easy = polynomial; hard = exponential
? Easy problems,
? Finding max of n numbers - O(n)
? Sorting n elements - O(n lg n)
? Hard problems,
? Factoring N=pq (n bits long) -
current best (?)
2 O n n( lg )?
67
Other hard problems
Let N=p?q,where p,q are large primes
? Square root mod N
– given x,N find y= mod N,i.e,y2=x mod N
(equivalent to factoring N)
? Discrete log
– given b,N and x,find y =
How hard are these problems really?
? One-way functions,easy to compute hard to invert
? Trap-door,a secret making inverting a owf easy
x
l o g,m o db x b y x N i, e,?
68
Pseudo-Random Bit Generators
? Deterministic functions
– RNG, {0,1}n ? {0,1}?
? Stretch fixed-size seed
to an unbounded sequence
that looks random
? Computable approximation
of one-time pad
? Example,RC4
Example,
i,= 0
i,= 0
do forever
i,= i+1 mod 256
j,= j+s[I] mod 256
swap s[i],s[j]
t,= s[i]+s[j] mod 256
output s[t]
Seed,initial value of s
Size of state,(2256)256
69
Symmetric Algorithms,Stream
Ciphers
Pseudo-Random
Sequence Generator
Plaintext Bitstream Ciphertext Bitstream
Key
1 1 1 1 1 1 1 1 0 0 0 0 0 0 …
1 0 0 1 1 0 1 0 1 1 0 1 0 0 …
0 1 1 0 0 1 0 1 1 1 0 1 0 0 …
Plaintext Stream
Pseudo-Random Stream
Ciphertext Stream
One-time pad using a
RNG
Ek(m) = m ? RNG(k)
70
Stream Ciphers
Linear Feedback Shift Registers
(LFSRs)
? Maximum possible sequence length is 2n - 1 with n
registers
? LFSRs are often used as building blocks for stream ciphers
? GSM A5 is a cipher with 3 LFSRs of lengths 19,22,and
23
Key
1 1 0 1 0
Load Key
R0 R1 R2 Rn-2 Rn-1
71
Integrity of Documents and
Messages
? Detection of corrupted documents and messages
– Detection of bit errors caused by unreliable transmission links
or faulty storage media,
– Solution,Message Digest acting as a unique fingerprint for
the document (similar function as CRC),
? Protection against unauthorized modification
– Without protection a forger could create both an alternative
document and its corresponding correct message digest,
– Symmetric Key Solution,Message Authentication Code
(MAC) formed by using a keyed message digest function,
– Asymmetric Key Solution,Digital Signature formed by
encrypting the message digest with the document author‘s
private key,
72
Message Digests based on
One-Way Hash Functions
? A single bit change in a document should cause
about 50% of the bits in the digest to change their
value !
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Document
or
message
of arbitrary size
1 0 1 1 0 1 Message Digest of fixed size
Hash Function One-Way Function
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Hash Function
1 0 1 1 0 1 0 0 0
1
73
Popular Hash Functions
? SHA - Secure Hash Algorithm,NIST / NSA
Document
or
Message
Message Digest or
Hash or Fingerprint
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
128 bits
MD5 Hash Function
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
160 bits
SHA
? MD5 - Message Digest #5,Ron Rivest,RSA
74
Basic Structure of the
MD5 / SHA One-Way Hash
Functions
N x 512 bits
IV 128/160 bit Initialization Vector
Hash 128/160 bit Hash Value
Document Pad L
Pad Padding
L 64 bit Document Length
MD5/SHA
Hash
Function
H
a
s
h
I
V
MD5/SHA
Hash
Function
H
a
s
h
MD5/SHA
Hash
Function
H
a
s
h
Block N
512 bits
Block 2
512 bits
Block 1
512 bits
75
Message Authentication Codes
based on
Keyed One-Way Hash Functions
Genuine
if equal MAC
Key
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Author
Keyed
Hash Function
Recipient 1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
MAC
Transmission
Channel
MAC
Key
Keyed
Hash Function
76
Inner Key
512 bits
Basic Structure of a
Keyed One-Way Hash Function
MD5 / SHA Hash Function
Hash
MD5 / SHA Hash Function
Hash
Document
Key
0x36..0x36
XOR
Outer Key
512 bits
0x5C..0x5C
XOR
Pad 512 bits
? Key Length ? Hash
Length
MAC Truncate to 96 bits
RFC 2104
77
Digital Signatures based on
Public Key Cryptosystems
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Author
Decryption with
Public Key
Hash Value
Hash Value Genuine
if equal Transmission Channel
Recipient 1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Signature
Hash Value
Hash Function
Encryption with
Private Key
Signature
78
Forging Documents
? On average 2m trials are required to find a
document having the same hash value as a given
one !
Original
Document
0 1 0 0 1 1 Hash Value of m bits
Hash Function
Pay 100 $
to the bearer
AQ - 1545323
Hash Function
1 0 1 1 0 1 0 0 1 0 0 1 1
Pay 100‘000 $
to the bearer
XX - XXXXXXX
Forged
Document
Random
Text
79
The Birthday Paradox
? What is the probability of another person having
the same birthday as you?
Probability p = 1/365
? How many people must be a in a room so that the
probability of at least another person having the
same birthday as you is greater than 0.5?
? n = 253 people
364
365 0 5
FHG IKJ ?n,
? How many people must be in a room so that the probability
of at least two of them having the same birthday is greater
than 0.5?
364
365
1 2
0 5FHG IKJ
? ?
?
n n( ) /
.
? n = 23 people
80
Birthday Attacks against Hash
Functions
? Only about 2m/2 trials are required to find two
documents having the same hash value ? MD5
might be insecure !
Original
Document
Z Z Z Z Z Z Hash Value of m bits
Hash Function
Pay 100 $
to the bearer
YY - YYYYYYY
Hash Function
1 0 1 1 0 1 0 Z Z Z Z Z Z
Pay 100‘000 $
to the bearer
XX - XXXXXXX
Forged
Document
Random
Text
Random
Text
Looking for Collisions !
81
Trust Models I
PGP Web of Trust
Alice Bob
Carol Dave
Signed by Dave
Signed by Bob
Signed by Dave
Signed by Carol
Signed by Alice
Signed by Bob
Can Carol trust Alice?
Trust
Trust
Trust
Certificate
Certificate
82
Trust Models II
Trust Hierarchy with
Certification Authorities
Verisign Swisskey
Amazon
Carol
Self Signed
Verisign
Self Signed
Swisskey
Alice
Amazon
Bob
Amazon
Root CA
Intermediate CA
Client
Certificates
Trust
83
General Structure of an X.509
Certificate
* specifies algorithm used to sign certificate,e.g,md5RSA
signatureAlgorithm*
Hash Function*
Hash / Fingerprint
Encryption with
Issuer‘s Private Key*
signature
version
serialNumber
signature*
issuer
validity
subject
subjectPublicKeyInfo
issuerUniqueID OPTIONAL
subjectUniqueID OPTIONAL
extensions OPTIONAL
84
General Structure of an X.509
Certificate
TBSCertificate,:= SEQUENCE {
version [0] Version DEFAULT v1(0),
serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier,
issuer Name,
validity Validity,
subject Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueID [1] Unique Identifier OPTIONAL,
subjectUniqueID [2] Unique Identifier OPTIONAL,
extensions [3] Extensions OPTIONAL
}
Certificate,:= SEQUENCE {
tbsCertificate TBSCertificate,
signatureAlgorithm AlgorithmIdentifier,
signature BIT STRING
}
85
X.509 Certificate Handling
Microsoft Internet Explorer 5.0
Explorer Menu,
Tools / Internet Options
86
X.509 Certificate Handling –
Internet Explorer
Certification Path
87
X.509 Certificate Structure
V1 Fields and V3 Extensions
88
Public Key Infrastructure (PKI)
? Certification Authority
– Governed by a Certificate Practice Statement (CPS)
– Issues and signs Client and Server Certificates
– Maintains a Certificate Revocation List (CRL)
– Offers LDAP / WWW based Directory Services
? Private Key Management
– Secure Generation and/or Distribution of Private Keys
? Browser or Java Applet generated Keys
? Hardware generated Keys (Intel 810/820 Chipset,Smart Cards)
– Secure Storage of Private Keys
? Smart Cards,USB Modules,SIM Cards (Sonera)
– Key Recovery of lost private keys
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.5.12
Overview
2
A,J,Menezes,P,C,van Oorschot and S,A,Vanstone,
Handbook of Applied Cryptography,CRC Press,1997,
Bruce Schneier,Applied Cryptography,Second Edition,
Protocols,Algorthms,and Source Code in C (cloth) John
Wiley & Sons,Inc.) 1996
Douglas R,Stinson,Cryptography (Theory and Practice),
CRC Press 1995
Resources
3
?Overview, Secure communication,Attacks to
cryptosystems,One time pad,randomness and pseudo-
randomness
?Secret-Key Cryptography,Block ciphers,DES,AES
(Rijndael),Modes of operation,Linear and Differential
cryptanalysis,
?Public-Key Cryptography,Mathematical Foundations,
One-way functions,Trapdoor one-way functions,Public-key
cryptosystems,RSA,Diffie-Hellman,ElGamal,and elliptic
curve cryptosystems,
?Design and Analysis of Cryptographic Protocols,
Authentication protocols,Digital cash,Sharing and partial
disclosure of secrets,Zero-knowledge proof systems,
Identification protocols,Key management architectures
Course Outline
4
Some Security Properties
? Integrity,no improper modification
– Authenticity,integrity of source
– Non-repudiation,integrity of commitments
– Accountability,integrity of responsibility
? Secrecy,no improper disclosure
– Privacy,secrecy of personal data
– Anonymity,unlinkable secrecy of identity
– Pseudonymity,linkable secrecy of identity
? Availability,no improper denial of service
5
Correctness vs,Security
? Correctness,satisfy specifications
– For reasonable inputs,
get reasonable output
? Security,resist attacks
– For unreasonable inputs,
output not completely disastrous
? Main difference
– Active interference from the environment
6
Attack Goals
? Publicity
? Fraud
? Disruption
? Invasion
of privacy
–,
? Terrorism
? Landing in Red Square
? Bank robbery
? Scams
? Plagiarism
? Vandalism
? Obstruction of justice
? Collection of personal
data
? Espionage
in the physical world
? Highly contagious viruses
? Defacing web pages
? Credit card number theft
? On-line scams
? Intellectual property theft
? Wiping out data
? Denial of service
? Reading private files
? Surveillance
in the electronic world
7
Vulnerable Systems,a Trend
? The Internet
– World-Wide connection
– Distributed,no central design and control
– Open infrastructures,modems,wireless,DHCP
– Untrusted software,applets,downloads
– Unsophisticated users
? Security costs
– Market now,fix bugs later
– Customers want it,
but won’t pay for it
? Homogeneity
– Hardware,x86
– OS,Windows
– Applications,
Vulnerability,a weakness that
can be exploited to cause damage
Attack, a method to exploit a
vulnerability
8
Attacks,Services,and Mechanisms
* Security Attack,Any action that compromises the security
of information,
* Security Mechanism,A mechanism that is designed to
detect,prevent,or recover from a security attack,
* Security Service,A service that enhances the security of
data processing systems and information transfers,A
security service makes use of one or more security
mechanisms,
9
Some Attacks
? Unintended blunders
? Hackers driven by technical challenge
? Disgruntled employees or customers
? Petty criminals
? Organized crime
? Organized terror groups
? Foreign espionage agents
? Information warfare
10
- confidentiality,only authorized parties have read
access to information
- integrity,only authorized parties have write access
to information
- availability,authorized access to information when
needed
- authenticity,identity claims (user,message source)
can be verified
- non-repudiation,message exchange can be proved
by sender and receiver
- authorization,information / system / resource
access control
Security services
11
Authentication
? Peer Entity Authentication – in a connection based
environment; provide confidence in the identity of a
connecting entity
– Logging in with a password
– Gaining access via biological identity verification
? DNA identification,retinal scan,finger/hand print
identification
– Access via audio voice identification
? Data Origin Authentication – in a connectionless
environment; provide assurance that the source of received
data is as claimed
– Corroborates the source of the data
– Does not proved assurance against duplicate or
modified data
12
Access Control
? This service provides protection against unauthorized use
of resources accessible via OSI,These may be OSI or non-
OSI resources accessed via OSI protocols,This protection
service may be applied to various types of access to a
resource or to all accesses to a resource
– e.g.,the use of a communications resource; the reading,
the writing,or the deletion of an information resource;
the execution of a processing resource
13
Data Confidentiality
? Connection Confidentiality
– Protection of all user data on a connection
? Connectionless Confidentiality
– Protection of all data within a single data block
? Selective-Field Confidentiality
– Insure confidentiality of selected fields with within the
user data on a connection or in a single data block
connection
? Traffic-Flow Confidentiality
– Protection of information that might be derived by
observing the traffic flow patterns
14
Data Integrity
? Connection Integrity with Recovery
– Detect any modification of stream data or replay of data and
retry;
? Connection Integrity without Recovery
– Detect any modification and report it,no retry…continue on
? Selective-Field Connection Integrity
– Same except for selected fields
? Connectionless Integrity
– Detect modifications in fixed block connectionless data,may
provide replay detection and protection
? Selective-Field Connectionless Integrity
– Same,except for selected fields
? Total stream protection would encompass all of the above and is
probably the best strategy
15
Nonrepudiation
? Nonrepudiation,Origin
– Proof that the message was sent by the specified party
? Nonrepudiation,Destination
– Proof that the message was received by the specified
party
16
Security Mechanisms (X.800)
? Encipherment – algorithmic/mathematical conversion
? Digital Signature – appending a secret signature
? Access Control -
? Data Integrity
? Authentication Exchange
? Traffic Padding – appending extra chars to foil traffic
analysis techniques
? Routing Control – selection of secure routeds through the
network
? Notarization – use a trused 3rd party (like a notary public)
17
Other Security Mechanisms(non X.800)
? Trusted Functionality
– That which is perceived to be true by some criteria
(policy)
? Security Label
– The marking of (bound to) a resource that names or
designates the security attributes of the resource
? Event Detection
– Intrusion detection
– Detection of specific hacks (detector hardware)
– Too many log in attempts
? Security Audit Trail
– Logging of all system events
? Security Recovery
– Recovery based on requests from security mechanisms
and/or event handling,
18
The Compromises of Security
? There is no absolute security!
? Race between attackers and defenders
? Constant innovation
? Well-funded,capable,determined attacker succeed
? Costs
? Relative to target’s value
? Users’ inconvenience
? Users’ acceptance
? Detection
? Rarely possible in real time
? Works mostly for
old threats
? Punishment
? Hard at a distance
? No international
legislation
? Poor domestic
legislation
? Perceived,unethical”
? Freedom of expression
? Intangibility
19
Information security and cryptography
? Cryptography is the study of mathematical
techniques related to aspects of information
security
? Cryptographic goals
– Confidentiality
– Data integrity
– Authentication
– Non-repudiation
– ……………
20
Cryptographical Building Blocks
Block
Ciphers
Stream
Ciphers
Symmetric Key
Cryptography
Authentication Privacy
Encryption
Hash
Functions
Challenge
Response
IVs
MACs
MICs
Message
Digests Nonces
Pseudo
Random
Random
Sources
Secret
Keys
Smart
Cards
DH
RSA
Public Key
Cryptography
Elliptic
Curves
Digital
Signatures
Data
Integrity
Secure Network Protocols
Non-
Repudiation
21
Is Cryptography the Solution?
Cryptography is not the same as security
– 85% of all CERT advisories cannot be fixed by crypto
– 30-50% of recent security holes from buffer overflow
Computer Security
Cryptography
Law
Operating
systems
Mathematics
Networking
Programming
languages
Economics
Psychology
Human
computer
interaction
22
Is Cryptography the Solution?
? The real world offers the attacker a richer menu of
options than mere cryptanalysis,
? Often more worrisome are protocol attacks,Trojan
horses,viruses,electromagnetic monitoring,
physical compromise,blackmail and intimidation
of key holders,operating system bugs,application
program bugs,hardware bugs,user errors,
physical eavesdropping,social engineering,and
dumpster diving,to name just a few,
23
Security Standards
Internet - Internet Engineering Task Force (IETF)
De Facto (PGP email security system,Kerberos-MIT)
ITU (X.509 Certificates)
National Institute of Standards and Technology (SHA)
IEEE
Department of Defense,Nat,Computer Security Center
- Tempest (radiation limits)
- Orange Book,Class A1,B3,C1,C2,..,
Export Controls
- High Performance Computers
- Systems with,Hard” Encryption
24
A Brief History of Cryptography
? ~2000 years ago,Substitution ciphers
? A few centuries later,Permutation ciphers
? Renaissance,Polyalphabetic ciphers
? Jefferson Cylinder (1790)
? Wheatstone disc (1870)
25
A Brief History of Cryptography
? The Enigma Rotor Machine (WW2)
? 1975,DES
? 1976,Public-key cryptography
? 1996-2000 AES
26
Cryptosystem
? A cryptosystem is a five -tuple (P,C,K,E,D),
where the following conditions are satisfied,
? 1,P is a finite set of possible plain texts
? 2,C is a finite set of possible ciphertexts
? 3,K,the keyspace,is a finite set of possible
keys
? 4,For each k?K,there is an encryption rule
eK ? E,and a corresponding decryption rule
dK ? D),Each eK, P ? C and dK, C ? P are
functions such that dK(eK(x)) = x for every
plaintext x ? P,
27
Taxonomy of cryptographic
primitives,
Arbitrary length hash functions
One-way permutations
Random sequences
Symmetric-key ciphers
Arbitrary length hash functions(MACs)
Signatures
Pseudorandom sequences
Identification primitives
Public-key ciphers
Signatures
Identification primitives
Unkeyed
Primitives
Symmetric-key
Primitives
Public-key
Primitives
Security
Primitives
Block
ciphers
Stream
ciphers
28
Cryptography - Terminology I
Cryptology is a branch of mathematics
Cryptology
Cryptography
?Art and science of
keeping messages secure,
Cryptanalysis
?Art and science of
breaking ciphertext,
29
Cipher
Cryptography - Terminology II
Encryption
EK(P) = C
plaintext
we
attack
at dawn
P
sorqjz
plvnwk
ghanqd
C
ciphertext
we
attack
at dawn
P
sorqjz
plvnwk
ghanqd
C
Decryption
DK(C) = P
key K
key K
30
Crypto tools
? one-way function
? Encryption/decryption – to hide info
? Key exchange - to establish shared key
? Authentication – to establish shared key with
the party you really meant to
– public
– private
? Signatures
? Hashing
? Certificates,PKI
31
Background on Functions
? Function
– f, X ? Y is called a function f from set X to set Y,
? X,domain; Y,codomain,
– for y = f(x) where x ? X and y ? Y
? y,image of x
? x,preimage of y
– Im(f),image of f
? the set that all y ? Y have at least one preimage
? 1 ? 1 function if
– each element in Y is the image of at most one element in X,
? onto function if
– Im(f) =Y
? bijection function if
– f is 1?1 and onto,
32
Background on Functions (ctd)
? one-way function if
– f(x) is easy to compute for all x ? X,but
– it is computationally infeasible to find any x ? X
such that f(x) =y,
? trapdoor one-way function if
– given trapdoor information,it becomes feasible to
find an x ? X such that f(x) =y,
33
Encryption / Decryption
encoder
decoder
(plaintext in -
ciphertext out)
ciphertext
msg
(ciphertext in
- plaintext out)
(should understand
nothing about the msg)
eavesdropper
bla-bla
cmb-cmb bla-bla
Shared Key
34
Key exchange
? Alice and Bob want to establish a shared
secret (key) when other people
(eavesdroppers) are listening
– Passive – just looking
– Active – may change msgs
Alice
Bob
35
Key exchange,man-in-the-middle
? Key exchange without Authentication
– Subject to Man-in-the-Middle attack
– Attacker translates between the keys,reading and/or
modifying the messages
– Authentication afterwards will not help!
Alice Bob
Shared
w/Alice Shared
w/Bob
36
Authentication
M
Alice Bob
Alice sends a msg to Bob
Bob wants to be sure the msg is really from
Alice
?the problem of proving that a user is who he
says he is
37
Signatures
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,… )
38
Authentication:,public”
Alice
Bob
? checks
? contracts
39
Public Key Signatures
PAlice
Alice Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,PAlice )
? Public Key
? Secret Key
40
Certificates
?,This public key PAlice really belongs to Alice,
Signed by Charlie,Certification Authority”
? Certificates can be public!
? Who’s Charlie?!?
Alice Charlie,
CA
SAlice
? Public Key
? Secret Key
PAlice
PAlice
CA
41
Public Key Infrastructures (PKI)
? Root CA public key
– Obtained out-of-band
– Certifies other Public Keys
(of CAs,or users)
? Certification Chains
? Grain of salt,so,you have a certificate…
? To be continued…
42
Signatures
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
Verify(M,SigM,… )
43
Authentication:,private”
Alice
Bob
SAlice
SigM= Sign(M,SAlice )
= (M,SigM)
SAlice
Verify(M,SigM,SAlice ),
Check SigM= Sign(M,SAlice )
Message Authentication Code (MAC)
Sign(M,SAlice )=Hash(M,SAlice )
MAC =,Shared Secret Sig” =
Symmetric Sig (Sign=Verify)
45
Cryptanalysis - Fundamental
Assumptions
? Attacker knows every detail of the cryptographical
algorithm
? Attacker is in possession of encryption / decryption
equipment (HW machine or SW implementation)
? Attacker has access to an arbitrary number of
plaintext / ciphertext pairs generated with the same
(unknown) key,
? Strong cipher,Best attack should be brute force key
search!
The security of a cipher should rely
on the secrecy of the key only!
Auguste Kerckhoffs,?La Cryptographie militaire“,1883
46
Cryptanalysis - Types of Attacks
? Ciphertext-Only Attack
– Attacker knows ciphertext of several messages encrypted with
the same key and/or several keys
– Recover the plaintext of as many messages as possible or even
better deduce the key (or keys)
– Given,C1 = Ek(P1),C2 = Ek(P2),...Ci = Ek(Pi)
Deduce,Either P1,P2,...Pi; k; or an algorithm to
infer Pi+1 from Ci+1 = Ek(Pi+1)
? Known-Plaintext Attack
– Known ciphertext / plaintext pair of several messages
– Deduce the key or an algorithm to decrypt further messages
– Given,P1,C1 = Ek(P1),P2,C2 = Ek(P2),...Pi,Ci = Ek(Pi)
– Deduce,Either k,or an algorithm to infer Pi+1 from
Ci+1 = Ek(Pi+1)
47
Cryptanalysis - Types of Attacks
? Chosen-Plaintext Attack
– Attacker can choose the plaintext that gets encrypted thereby
potentially getting more information about the key
– Given,P1,C1 = Ek(P1),P2,C2 = Ek(P2),...Pi,Ci = Ek(Pi),
where the cryptanalyst gets to choose P1,P2,...Pi
Deduce,Either k,or an algorithm to infer Pi+1 from
Ci+1 = Ek(Pi+1)
? Adaptive Chosen-Plaintext Attack
– Attacker can choose a series of plaintexts,basing choice on the
result of previous encryption ? differential cryptanalysis!
? Chosen-ciphertext attack
– Given,C1,P1 = Dk(C1),C2,P2 = Dk(C2),...Ci,Pi = Dk(Ci)
– Deduce,k
48
Models for evaluating security
? Unconditional security (perfect secrecy)
– Adversaries have unlimited computational resources
– Observation of the ciphertext provides no information to an
adversary
– One time pad
? Complexity-theoretic security
– Adversaries have polynomial computational power,
– Asymptotic analysis and usually also worst-case analysis is
used
? Provable security
– provably secure if the difficulty of defeating crypto system
can be shown to be as difficult as solving a well-known
number-theoretic problem
49
Models for evaluating security (ctd)
? Computational security (Practical security)
– We might define a cryptosystem to be computationally secure
if the best algorithm for breaking it requires at least N
operations,where N is some specified,very large number,
– The problem is that no known practical cryptosystem can be
proved to be secure under this definition,
– neither the Shift Cipher,the Substitution Cipher nor the
Vigenke Cipher is computationally secure against a
ciphertext-only attack (given a sufficient amount of
ciphertext),
? Ad hoc security (heuristic security)
– any variety of convincing computational security
– unforeseen attacks may remain
50
Cipher = Encoder; or Encryption/Decryption scheme
Stream cipher encodes/decodes char by char
Block cipher encodes/decodes block by block
Stream cipher ~ Block cipher with block size of 1 char
(+state)
Chaining (Modes of Operation) –
– make block encryption depend on the past blocks
–,make block ciphers more like stream ciphers”
Block vs,Stream Ciphers
51
Symmetric & Asymmetric schemes
? Symmetric,
– decryption as easy as encryption (and vice versa)
i.e,if you can encrypt then you can decrypt
(and vice versa)
(DES,AES/Rijndael are symmetric block ciphers)
? Asymmetric,
– may not be able to decrypt even if can encrypt
(and vice versa)
e.g,RSA
52
Classical Cryptography
? Simple Methods
– Transposition
? Arrange the,plaintext” in a special permutation
– Substitution
? Replace letters of the,plaintext” with other letters or
symbols in a certain way
? Caesar’s Cipher,
A ? C
B ? E
D ? F
…
X ? A
Y ? B
Z ? C
53
Classical Cryptography
? Problem with simple methods
– Security depends on the secrecy of the entire
encrypting/decrypting process
– Need a way to ensure secrecy even if the
encryption process is compromised
54
Classical Cryptography
? Key-based Cryptography
– Private Key
? Secret key locks and unlocks data
? Encrypt – EPri(P) = C
? Decrypt – DPri(C) = P
– Public Key
? Separate keys to lock and unlock data
? Encrypt – EPub(P) = C
? Decrypt – DPri(C) = P
55
Classical Cryptography
? Problem with private-key encryption
– Depends entirely on the secrecy of the key
– Requires two parties who initially share no
secret information to exchange a secret key
– An eavesdropper can passively snoop secret
key as it’s being exchanged
56
Classical Cryptography
? Problems with Public-key encryption
– No key distribution problem
– However,security relies on unproven
mathematical assumptions such as the difficulty
of factoring large integers
– Shor has already shown that the assumption
wont hold up against quantum computation
57
Summary of comparison
? public-key cryptography
– signatures (particularly,non-repudiation) and key
management
? symmetric-key cryptography
– encryption and some data integrity applications
? Key sizes
– Private keys must be larger (e.g.,1024 bits for RSA) than
secret keys (e.g.,64 or 128 bits)
? most attack on symmetric-key systems is an exhaustive key search
? public-key systems are subject to,short-cut” attacks (e.g.,factoring)
58
open channel
Symmetric or Secret-Key
Algorithms
? Same key used for encryption and decryption
? Key must be kept absolutely secret
? Same key can be used for several messages,but
should be changed periodically ? secure key
distribution problem!
Encryption
EK(P) = C
plaintext
P
Decryption
DK(C) = P
ciphertext plaintext
P C
key K key K
distribution of secret-key over secure channel
59
Symmetric Algorithms,Block
Ciphers
ciphertext blocks n bits
n bits plaintext blocks n bits
n bits
Common Block Sizes,
n = 64,128,256 bits
Common Key Sizes,
k = 40,56,64,80,128,
168,192,256 bits
k bits
Key
Block Cipher
60
Some Popular Block Ciphers
Block Size Name of Algorithm Key Size
DES (Digital Encryption Standard,IBM) 64 56
3DES (Triple DES) 64 168
IDEA (Lai / Massey,ETH Zürich) 64 128
RC2 (Ron Rivest,RSA) 64 40,.,1024
CAST (Canada) 64 128
Blowfish (Bruce Schneier) 64 128,.,448
Skipjack (NSA,clipper chip,was classified) 64 80
RC5 (Ron Rivest,RSA) 64,.,256 64,.,256
61
Claude Shannon *1916
? Information Theory
– Worked at MIT / Bell Labs
– ?The Mathematical Theory of
Communication,(1948)
– Maximum capacity of a noisy
transmission channel
– Definition of the ?binary digit,(bit)
as a unit of information
– Definition of ?entropy,as a
measure of information
? Cryptography
– Model of a secrecy system
– Definition of perfect secrecy
– Principles of ?confusion,and
?diffusion,The Father of Information Theory
62
Cryptoanalytic Attacks
E
21
T
18
A
16
O
16
N
14
I
13
R
13
S
12
H
12
D
8
L
7
U
6
C
6
M
6
P
4
F
4
Y
4
W
3
G
3
B
3
V
2
J
1
K
1
X
1 ?
Q Z
?
high frequency group medium frequency group
low frequency group rare group
Frequency table of 200 English letters
63
Shannon‘s Definition of Perfect
Secrecy
m ciphertext C
One-Time Pad
k bits of random key K
1 0 0 1 1 0 1 0 1 0
0 1 1 1 0 1 1 0 1 1
1 1 0 1 0 0 0 1 1 1
use random key sequence
only once and then discard it !
The One-Time Pad
Ek(m) = m ? k
k
64
One-time random pad (cont.)
? Symmetric
? Pad is selected at random
? perfectly secure,but..,
? One time only
so sending the pad is just as hard as
sending the msg
65
Pseudo-random bit string (PRBS) generator,
PRBS = Hard to guess a bit (after seeing many others)
Pseudo-random pad
seed
(short)
PRBS
(long)
01101 1010010110...,
66
Complexity,what is,hard”?
measure hardness in terms of size of input
easy = polynomial; hard = exponential
? Easy problems,
? Finding max of n numbers - O(n)
? Sorting n elements - O(n lg n)
? Hard problems,
? Factoring N=pq (n bits long) -
current best (?)
2 O n n( lg )?
67
Other hard problems
Let N=p?q,where p,q are large primes
? Square root mod N
– given x,N find y= mod N,i.e,y2=x mod N
(equivalent to factoring N)
? Discrete log
– given b,N and x,find y =
How hard are these problems really?
? One-way functions,easy to compute hard to invert
? Trap-door,a secret making inverting a owf easy
x
l o g,m o db x b y x N i, e,?
68
Pseudo-Random Bit Generators
? Deterministic functions
– RNG, {0,1}n ? {0,1}?
? Stretch fixed-size seed
to an unbounded sequence
that looks random
? Computable approximation
of one-time pad
? Example,RC4
Example,
i,= 0
i,= 0
do forever
i,= i+1 mod 256
j,= j+s[I] mod 256
swap s[i],s[j]
t,= s[i]+s[j] mod 256
output s[t]
Seed,initial value of s
Size of state,(2256)256
69
Symmetric Algorithms,Stream
Ciphers
Pseudo-Random
Sequence Generator
Plaintext Bitstream Ciphertext Bitstream
Key
1 1 1 1 1 1 1 1 0 0 0 0 0 0 …
1 0 0 1 1 0 1 0 1 1 0 1 0 0 …
0 1 1 0 0 1 0 1 1 1 0 1 0 0 …
Plaintext Stream
Pseudo-Random Stream
Ciphertext Stream
One-time pad using a
RNG
Ek(m) = m ? RNG(k)
70
Stream Ciphers
Linear Feedback Shift Registers
(LFSRs)
? Maximum possible sequence length is 2n - 1 with n
registers
? LFSRs are often used as building blocks for stream ciphers
? GSM A5 is a cipher with 3 LFSRs of lengths 19,22,and
23
Key
1 1 0 1 0
Load Key
R0 R1 R2 Rn-2 Rn-1
71
Integrity of Documents and
Messages
? Detection of corrupted documents and messages
– Detection of bit errors caused by unreliable transmission links
or faulty storage media,
– Solution,Message Digest acting as a unique fingerprint for
the document (similar function as CRC),
? Protection against unauthorized modification
– Without protection a forger could create both an alternative
document and its corresponding correct message digest,
– Symmetric Key Solution,Message Authentication Code
(MAC) formed by using a keyed message digest function,
– Asymmetric Key Solution,Digital Signature formed by
encrypting the message digest with the document author‘s
private key,
72
Message Digests based on
One-Way Hash Functions
? A single bit change in a document should cause
about 50% of the bits in the digest to change their
value !
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Document
or
message
of arbitrary size
1 0 1 1 0 1 Message Digest of fixed size
Hash Function One-Way Function
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Hash Function
1 0 1 1 0 1 0 0 0
1
73
Popular Hash Functions
? SHA - Secure Hash Algorithm,NIST / NSA
Document
or
Message
Message Digest or
Hash or Fingerprint
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
128 bits
MD5 Hash Function
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
160 bits
SHA
? MD5 - Message Digest #5,Ron Rivest,RSA
74
Basic Structure of the
MD5 / SHA One-Way Hash
Functions
N x 512 bits
IV 128/160 bit Initialization Vector
Hash 128/160 bit Hash Value
Document Pad L
Pad Padding
L 64 bit Document Length
MD5/SHA
Hash
Function
H
a
s
h
I
V
MD5/SHA
Hash
Function
H
a
s
h
MD5/SHA
Hash
Function
H
a
s
h
Block N
512 bits
Block 2
512 bits
Block 1
512 bits
75
Message Authentication Codes
based on
Keyed One-Way Hash Functions
Genuine
if equal MAC
Key
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Author
Keyed
Hash Function
Recipient 1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
MAC
Transmission
Channel
MAC
Key
Keyed
Hash Function
76
Inner Key
512 bits
Basic Structure of a
Keyed One-Way Hash Function
MD5 / SHA Hash Function
Hash
MD5 / SHA Hash Function
Hash
Document
Key
0x36..0x36
XOR
Outer Key
512 bits
0x5C..0x5C
XOR
Pad 512 bits
? Key Length ? Hash
Length
MAC Truncate to 96 bits
RFC 2104
77
Digital Signatures based on
Public Key Cryptosystems
1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Author
Decryption with
Public Key
Hash Value
Hash Value Genuine
if equal Transmission Channel
Recipient 1 0 1 0 1 1 1
0 0 1 0 1 0 0
1 1 0 1 1 1 0 1
0 0 0 1 0 1 0 1
Signature
Hash Value
Hash Function
Encryption with
Private Key
Signature
78
Forging Documents
? On average 2m trials are required to find a
document having the same hash value as a given
one !
Original
Document
0 1 0 0 1 1 Hash Value of m bits
Hash Function
Pay 100 $
to the bearer
AQ - 1545323
Hash Function
1 0 1 1 0 1 0 0 1 0 0 1 1
Pay 100‘000 $
to the bearer
XX - XXXXXXX
Forged
Document
Random
Text
79
The Birthday Paradox
? What is the probability of another person having
the same birthday as you?
Probability p = 1/365
? How many people must be a in a room so that the
probability of at least another person having the
same birthday as you is greater than 0.5?
? n = 253 people
364
365 0 5
FHG IKJ ?n,
? How many people must be in a room so that the probability
of at least two of them having the same birthday is greater
than 0.5?
364
365
1 2
0 5FHG IKJ
? ?
?
n n( ) /
.
? n = 23 people
80
Birthday Attacks against Hash
Functions
? Only about 2m/2 trials are required to find two
documents having the same hash value ? MD5
might be insecure !
Original
Document
Z Z Z Z Z Z Hash Value of m bits
Hash Function
Pay 100 $
to the bearer
YY - YYYYYYY
Hash Function
1 0 1 1 0 1 0 Z Z Z Z Z Z
Pay 100‘000 $
to the bearer
XX - XXXXXXX
Forged
Document
Random
Text
Random
Text
Looking for Collisions !
81
Trust Models I
PGP Web of Trust
Alice Bob
Carol Dave
Signed by Dave
Signed by Bob
Signed by Dave
Signed by Carol
Signed by Alice
Signed by Bob
Can Carol trust Alice?
Trust
Trust
Trust
Certificate
Certificate
82
Trust Models II
Trust Hierarchy with
Certification Authorities
Verisign Swisskey
Amazon
Carol
Self Signed
Verisign
Self Signed
Swisskey
Alice
Amazon
Bob
Amazon
Root CA
Intermediate CA
Client
Certificates
Trust
83
General Structure of an X.509
Certificate
* specifies algorithm used to sign certificate,e.g,md5RSA
signatureAlgorithm*
Hash Function*
Hash / Fingerprint
Encryption with
Issuer‘s Private Key*
signature
version
serialNumber
signature*
issuer
validity
subject
subjectPublicKeyInfo
issuerUniqueID OPTIONAL
subjectUniqueID OPTIONAL
extensions OPTIONAL
84
General Structure of an X.509
Certificate
TBSCertificate,:= SEQUENCE {
version [0] Version DEFAULT v1(0),
serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier,
issuer Name,
validity Validity,
subject Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueID [1] Unique Identifier OPTIONAL,
subjectUniqueID [2] Unique Identifier OPTIONAL,
extensions [3] Extensions OPTIONAL
}
Certificate,:= SEQUENCE {
tbsCertificate TBSCertificate,
signatureAlgorithm AlgorithmIdentifier,
signature BIT STRING
}
85
X.509 Certificate Handling
Microsoft Internet Explorer 5.0
Explorer Menu,
Tools / Internet Options
86
X.509 Certificate Handling –
Internet Explorer
Certification Path
87
X.509 Certificate Structure
V1 Fields and V3 Extensions
88
Public Key Infrastructure (PKI)
? Certification Authority
– Governed by a Certificate Practice Statement (CPS)
– Issues and signs Client and Server Certificates
– Maintains a Certificate Revocation List (CRL)
– Offers LDAP / WWW based Directory Services
? Private Key Management
– Secure Generation and/or Distribution of Private Keys
? Browser or Java Applet generated Keys
? Hardware generated Keys (Intel 810/820 Chipset,Smart Cards)
– Secure Storage of Private Keys
? Smart Cards,USB Modules,SIM Cards (Sonera)
– Key Recovery of lost private keys
