曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.16
Outline
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,
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,
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
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,
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)
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
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
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
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
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,
Block cipher
Definition An n-bit block cipher is a function
E, Vn?K?Vn,such that for each key K ?K,
E(P;K) is an invertible mapping (the encryption
function for K) from Vn to Vn,written EK(P),
The inverse mapping is the decryption function,
denoted DK(C),P denotes that ciphertext
results from encrypting plaintext P under K,
Iterating Block ciphers
Definition A product cipher combines two or more
transformations in a manner intending that the resulting
cipher is more secure than the individual components,
Definition An iterated block cipher is a block cipher
involving the sequential repetition of an internal
function called a round function,Parameters include the
number of rounds Nr,the block bitsize n,and the bitsize
k of the input key K from which Nr subkeys Ki (round
keys) are derived,For invertibility (allowing unique
decryption),for each value Ki the round function is a
bijection on the round input,
Substitution-Permutation Networks,SPN
? Substitution pS,{0,1}l ? {0,1}l
? Permutation pP,{1,…,lm} ? {1,…,lm}
The plaintext has lm bits,x = x(1)||,,, ||x(m)
where,x(i)= (x(i-1)l+1,.,,,xil)
The SPN has Nr rounds,in which we perform on x
m substitutions pS followed by one permutation pP,
to get the ciphertext y,
Definition A substitution-permutation (SP) network is a
product cipher composed of a number of stages each
involving substitutions and permutations
Linear Cryptanalysis
? Linear cryptanalysis tries to take advantage of
high probability occurrences of linear
expressions involving plaintext bits,
"ciphertext" bits (actually we shall use bits
from the 2nd last round output),and subkey
bits,
? It is a known plaintext attack,
Differential Cryptanalysis
? Differential cryptanalysis exploits the high
probability of certain occurrences of plaintext
differences and differences into the last round of
the cipher,
? Differential cryptanalysis is a chosen plaintext
attack,meaning that the attacker is able to select
inputs and examine outputs in an attempt to
derive the key,
Feistel Networks
f1,…,fk, {0,1}n ? {0,1}n
? Arbitrary functions
? Not necessarily invertible
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
n bits n bits
Ro
un
d 1
Ro
un
d 2
Ro
un
d k
-1
Ro
un
d k
…
Li = Ri-1
Ri = Li-1 ? fi(Ri-1)
Inverting a Feistel Network
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
… Li-1 = Ri ? fi(Li)
Ri-1 = Li
Theorem
For any f1,…,fk, {0,1}n ? {0,1}n,
a Feistel network computes a
permutation p, {0,1}n ? {0,1}n
Inverse,
Inside DES
? x0 = IP(m) = L0R0,
? 16 Rounds,i = 1,2,…,16,
Li,= Ri-1,
Ri,= Li-1 ? f (Ri-1,Ki),where
f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki)),
with operations E (expansion),
S (S-box lookup),and P some
(permutation),
? c = IP-1(L16R16),
One Round of DES
Expansion Permutation
48
P-Box Permutation
S-Box Substitution
32
Shift Shift
48
Compression
Permutation
Feistel
Network
56
32
32
Keyi-1 Ri-1 Li-1
Keyi Ri Li
32
32 56
Avoiding Exhaustive Search–3DES
3DESk1,k2(m) = Ek1(Dk2(Ek1(m)))
? Key length,112 bits
? Very popular
DES
encryption
DES
decryption
1,TDEA encryption operation
O = EK3(DK2(EK1(m))),
2,TDEA decryption operation
O = DK1(EK2(DK3(c)))
1,K1,K2 and K3 are
independent keys;
2,K1 and K2 are independent
keys and K3 = K1;
3,K1 = K2 = K3,
Theory of Block Cipher Design ? Choosing good S-boxes,
? They should not be linear or affine,nor even close to
linear or affine,There should be a balance of zeros and
ones,and no correlations between different
combinations of bits,
? One property that seems very important is the
avalanche effect,The strict avalanche criteria (SAC)
guarantees that exactly half of the output bits change
when one input bit changes,
? 1,Choose randomly,
? 2,Choose and test,
? 3,Man-made,
? 4,Math-made,
Modes of operation
Five basic modes of operation are available for
block ciphers,
? Electronic codebook mode,ECB
? Cipher block chaining mode,CBC
? Cipher feedback mode,CFB
? Output feedback mode,OFB
? Counter Mode:CTR
? Rounds, depend on block size and key length
Block size
Key size
128 bits
(Nb=4)
192 bits
(Nb=6)
256 bits
(Nb=8)
128 bits (Nk=4) 10 12 14
192 bits (Nk=6) 12 12 14
256 bits (Nk=8) 14 14 14
The AES Cipher
Add Round Key
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Mix Columns
Shift Rows
Add Round Key
Inverse sub bytes
Inverse shift rows
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Substitute Bytes
Add round key
Shift Rows
Substitute Bytes
Add round key
Substitute Bytes
Shift Rows
Mix Columns
Expand Key
.,
,
.,
,
w[0,3]
w[4,7]
w[36,39]
w[40,43]
Plaintext Plaintext
Ciphertext Ciphertext
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Keyed hash functions
(X,Y,K,H) is a keyed hash family,where
? X is a set of possible messages
? Y is the set of possible message digests,or
authentication tags
? K is the keyspace
? H is a set of hash functions
? For each key K there is a hash function hK,X ? Y
in H
? Assume |X| >= |Y| (even better,2|X| >= |Y|)
Unkeyed hash functions
An unkeyed hash function is a mapping h,X ? Y,
where
? X is a set of possible messages
? Y is the set of possible message digests
?Unkeyed hash function
–|K| = 1
–Ex,SHA-1 (successor of MD4)
Ideal hash functions
? it is a simple matter to compute the probability
that k random elements z1,.,,,zk ? Z are
distinct,
? The first choice z1 is arbitrary; the probability that
z2 != z1 is 1 - l/n; the probability that z3 is distinct
from z1 and z2 is 1 - 2/n,etc,
? we estimate the probability of no collisions to be
Message Authentication codes (MACs)
Source (K) Destination (K)
Message m
y = hk(m)
Check
y = hk(m)
m,tag y
HMAC
? nested MAC algorithm (proposed standard)
– based on SHA-1
– uses 512-bit key k
– 2 512-bit constants,ipad and opad
? 160-bit MAC
– HMACk(x) = SHA-1((k ? opad) || SHA-1((K
? ipad) || x))
? ipad component resistant against unknown-key
collision attack
CBC MAC
x1
+ + + +
IV
x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
Public-Key Applications
? can classify uses into 3 categories,
– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
– key exchange (of session keys)
? some algorithms are suitable for all uses,
others are specific to one,Only three
algorithms work well for both encryption
and digital signatures,RSA,ElGamal,and
Rabin,All of these algorithms are slow,
Security of Public-Key
Algorithms
? Since a cryptanalyst has access to the public key,
he can always choose any message to encrypt,
? Eve can generate a database of all possible session
keys encrypted with Bob’s public key,
? most public-key algorithms are particularly
susceptible to a chosen-ciphertext attack
? In systems where the digital signature operation is
the inverse of the encryption operation,this attack
is impossible to prevent unless different keys are
used for encryption and signatures,
Public Key,
n product of two primes,p and q (p and q must remain secret)
e relatively prime to (p - 1)(q - 1)
Private Key,
d e-1 mod ((p - 1)(q - 1))
Encrypting,
c = me mod n
Decrypting,
m = cd mod n
RSA Encryption
RSA Signature
p,q,primes,n = pq,ed = 1 mod (n),
e,n,public key,d,secret key,(factoring,n,1024 bits)
M,message,M in {0,1,..,n-1},
Signing,S = Md mod n
Verification,M = Se mod n
Key generation,p = 3,q = 5,n = 15,e = 3 => d = 3
Signing,M = 13,S = 13d mod n,=> S = 7
Verification,Checking M = Se mod n
?
Semantic security
? Total break
– The adversary can determine the private key of a
public key cryptosystem,or the secret key of a
symmetric key encryption system,
? Partial break
– The adversary is able with non-negligible probability
to
? decrypt a previously unseen ciphertext (without knowing
the private/secret key),or
? determine some specific information about the plaintext
given
the ciphertext,
Semantic security
? Distinguishability of ciphertexts
– The adversary is able to distinguish with probability greater
than ?,
? encryptions of different plaintexts,or
? encryptions of a given plaintext and a random string,
A public key cryptosystem in which the adversary cannot
(in polynomial time) distinguish ciphertexts,under certain
computational assumptions hold,is said to achieve
semantical security,
Perfect vs,Semantic security
? perfect secrecy,
– a passive adversary,even with infinite computational
resources
– can learn nothing about plaintext from ciphertext,
except its length
– Limitation,cannot be achieved unless key is as long as
message
? semantic security,polynomially bounded perfect
secrecy
– a passive adversary with poly,bounded resources can
learn nothing
Alice ga mod p Bob
gb mod p
The private key is,gab mod p
where p is a prime and g is a generator of Zp
Diffie-Hellman
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + Q
Group set,
All points P(x,y) lying
on an elliptic curve
Group operation,
Point addition
R'
R P
Q
Points P(x,y) on an Elliptic Curve
form a Group
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
Inverse element,
P'(x,-y) = P(x,y)
is mirrored on x-axis
Point addition with
inverse element,
P + P' = O
results in a neutral
element O(x,?) at
infinity P'
O
Neutral element,
P + O = P
P
Neutral and Inverse Elements
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + P
Point Doubling,
Form the tangent in
Point P(x,y)
R'
R P
Point Doubling – Adding a point
to itself
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
kP = P + P +,.,+ P
Point Iteration,
3P
2P P
Point Iteration – Adding a point
k-1 times to itself
Definition of an Elliptic Curve
Cryptosystem
? version is currently v1
? fieldID identifies the finite field over which curve is defined
? curve coefficients a and b of the elliptic curve
? base specifies the base point P,a point P in the elliptic
curve group defined over GF(p)
? order the order n of the base point
Public Key Cryptography
Signature schemes
Let
? P be the set of all messages
? A be the set of signatures
? K be the set of all keys
Basic Mechanism of Signature
Schemes
? K,A key generation algorithm to randomly select
a public key pair,
? Sig K, A signature algorithm that takes message +
private key as input and generates a signature for
the message as output
? Ver K, A signature verification algorithm that
takes signature + public key as input and generates
information bit according to whether signature is
consistent as output,
Attack models
? Total Breaking Attack
- The attacker knows the public key,He tries to recover the
corresponding secret key,
? Forgery Attack
- The attacker knows the public key,He tries to find the signature
for a given message,
? Existential Forgery Attack
- The attacker knows the public key,He tries to find a pair of
a message and its signature,
? Chosen Message Attack (CMA)
- The attacker is able to sign messages but does not know the key
used,He tries to perform the (existential) forgery or to obtain the
secret key,
definitions
? A protocol is said to have perfect forward secrecy if compromise
of long term keys does not compromise past (short term)
session keys,
? A protocol is vulnerable to a known-key attack if compromise of
past session keys allows an attacker to compromise of future
session keys (including actively impersonating)
Needham Schroeder
Symmetric Key
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,
A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
A B
S
Freshness Attacks(3)
Needham Schroeder Symmetric Key
? i.1,A -> S, A,B,Na
? i.2,S -> A, {Na,B,Kab,{Kab,A}Kbs }Kas
? i.3,A -> I(B), {Kab,A}Kbs
? assume that Kab is compromised
? ii.3,I(A) -> B, {Kab,A}Kbs
? ii.4,B -> I(A), {Nb}Kab
? ii.5,I(A) -> B, {dec(Nb)}Kab
A B
S
Needham-Schroeder Public
Key (1)
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb}KPa
? 3,A -> B, {Nb}KPb
A B
Needham-Schroeder Public
Key (2)
? i.1,A -> I, {Na,A}KPi
? ii.1,I(A) -> B, {Na,A}KPb
? ii.2,B -> I(A), {Na,Nb}KPa
? i.2,I -> A, {Na,Nb}KPa
? i.3,A -> I, {Nb}KPi
? ii.3,I(A) -> B, {Nb}KPb
A I B
secret splitting
Algorithm,
Assume Trent wishes to protect the message m,
Trent generates a random bit string r,the same
length m,
Trent computes m ? r = s
Trent gives Alice r
Trent gives Bob s
? Each of the pieces is called a shadow,
? To reconstruct m,Alice and Bob XOR their
shadows together,
? If r is truly random,the system is perfectly
secure (OTP),
? To extend the scheme to n people,generate n
random bit strings e.g,m ? r ? s ? t = u
Adi Shamir (N,d)-Scheme
? Pick a prime p
? and a random polynomial
f (x) = ad-1xd-1 + ad-2xd-2 +…+ a0 mod p
a0 = f (0) = s
? User i receive si = f (i) mod p
? Any d users can interpolate to obtain f and
hence s
? Any d-1 users can not obtain any information
about s
Graph Isomorphism
? Assume that Peggy knows the isomorphism between the two graphs,G1
and G2,The following protocol will convince Victor of Peggy’s knowledge,
? (1) Peggy randomly permutes G1 to produce another graph,H,that is
isomorphic to G1,Because Peggy knows the isomorphism between H
and G1,she also knows the isomorphism between H and G2,
? (2) Peggy sends H to Victor,
? (3) Victor asks Peggy either to,
? (a) prove that H and G1 are isomorphic,or
? (b) prove that H and G2 are isomorphic,
? (4) Peggy complies,She either,
? (a) proves that H and G1 are isomorphic,without proving that H
and G2 are isomorphic,or
? (b) proves that H and G2 are isomorphic,without proving that H
and G1 are isomorphic,
? (5) Peggy and Victor repeat steps (1) through (4) n times,
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.16
Outline
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,
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,
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
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,
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)
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
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
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
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
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,
Block cipher
Definition An n-bit block cipher is a function
E, Vn?K?Vn,such that for each key K ?K,
E(P;K) is an invertible mapping (the encryption
function for K) from Vn to Vn,written EK(P),
The inverse mapping is the decryption function,
denoted DK(C),P denotes that ciphertext
results from encrypting plaintext P under K,
Iterating Block ciphers
Definition A product cipher combines two or more
transformations in a manner intending that the resulting
cipher is more secure than the individual components,
Definition An iterated block cipher is a block cipher
involving the sequential repetition of an internal
function called a round function,Parameters include the
number of rounds Nr,the block bitsize n,and the bitsize
k of the input key K from which Nr subkeys Ki (round
keys) are derived,For invertibility (allowing unique
decryption),for each value Ki the round function is a
bijection on the round input,
Substitution-Permutation Networks,SPN
? Substitution pS,{0,1}l ? {0,1}l
? Permutation pP,{1,…,lm} ? {1,…,lm}
The plaintext has lm bits,x = x(1)||,,, ||x(m)
where,x(i)= (x(i-1)l+1,.,,,xil)
The SPN has Nr rounds,in which we perform on x
m substitutions pS followed by one permutation pP,
to get the ciphertext y,
Definition A substitution-permutation (SP) network is a
product cipher composed of a number of stages each
involving substitutions and permutations
Linear Cryptanalysis
? Linear cryptanalysis tries to take advantage of
high probability occurrences of linear
expressions involving plaintext bits,
"ciphertext" bits (actually we shall use bits
from the 2nd last round output),and subkey
bits,
? It is a known plaintext attack,
Differential Cryptanalysis
? Differential cryptanalysis exploits the high
probability of certain occurrences of plaintext
differences and differences into the last round of
the cipher,
? Differential cryptanalysis is a chosen plaintext
attack,meaning that the attacker is able to select
inputs and examine outputs in an attempt to
derive the key,
Feistel Networks
f1,…,fk, {0,1}n ? {0,1}n
? Arbitrary functions
? Not necessarily invertible
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
n bits n bits
Ro
un
d 1
Ro
un
d 2
Ro
un
d k
-1
Ro
un
d k
…
Li = Ri-1
Ri = Li-1 ? fi(Ri-1)
Inverting a Feistel Network
f1 ?
f2 ?
fk-1 ?
fk ?
L0, R0,
L1, R1,
Lk-2, Rk-2,
Lk-1, Rk-1,
Lk, Rk,
… Li-1 = Ri ? fi(Li)
Ri-1 = Li
Theorem
For any f1,…,fk, {0,1}n ? {0,1}n,
a Feistel network computes a
permutation p, {0,1}n ? {0,1}n
Inverse,
Inside DES
? x0 = IP(m) = L0R0,
? 16 Rounds,i = 1,2,…,16,
Li,= Ri-1,
Ri,= Li-1 ? f (Ri-1,Ki),where
f (Ri-1,Ki) = P(S(E(Ri-1) ? Ki)),
with operations E (expansion),
S (S-box lookup),and P some
(permutation),
? c = IP-1(L16R16),
One Round of DES
Expansion Permutation
48
P-Box Permutation
S-Box Substitution
32
Shift Shift
48
Compression
Permutation
Feistel
Network
56
32
32
Keyi-1 Ri-1 Li-1
Keyi Ri Li
32
32 56
Avoiding Exhaustive Search–3DES
3DESk1,k2(m) = Ek1(Dk2(Ek1(m)))
? Key length,112 bits
? Very popular
DES
encryption
DES
decryption
1,TDEA encryption operation
O = EK3(DK2(EK1(m))),
2,TDEA decryption operation
O = DK1(EK2(DK3(c)))
1,K1,K2 and K3 are
independent keys;
2,K1 and K2 are independent
keys and K3 = K1;
3,K1 = K2 = K3,
Theory of Block Cipher Design ? Choosing good S-boxes,
? They should not be linear or affine,nor even close to
linear or affine,There should be a balance of zeros and
ones,and no correlations between different
combinations of bits,
? One property that seems very important is the
avalanche effect,The strict avalanche criteria (SAC)
guarantees that exactly half of the output bits change
when one input bit changes,
? 1,Choose randomly,
? 2,Choose and test,
? 3,Man-made,
? 4,Math-made,
Modes of operation
Five basic modes of operation are available for
block ciphers,
? Electronic codebook mode,ECB
? Cipher block chaining mode,CBC
? Cipher feedback mode,CFB
? Output feedback mode,OFB
? Counter Mode:CTR
? Rounds, depend on block size and key length
Block size
Key size
128 bits
(Nb=4)
192 bits
(Nb=6)
256 bits
(Nb=8)
128 bits (Nk=4) 10 12 14
192 bits (Nk=6) 12 12 14
256 bits (Nk=8) 14 14 14
The AES Cipher
Add Round Key
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Mix Columns
Shift Rows
Add Round Key
Inverse sub bytes
Inverse shift rows
Inverse mix cols
Add round key
Inverse sub bytes
Inverse shift rows
Add round key
Substitute Bytes
Add round key
Shift Rows
Substitute Bytes
Add round key
Substitute Bytes
Shift Rows
Mix Columns
Expand Key
.,
,
.,
,
w[0,3]
w[4,7]
w[36,39]
w[40,43]
Plaintext Plaintext
Ciphertext Ciphertext
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Ro
un
d 1
Ro
un
d 9
Ro
un
d 1
0
Keyed hash functions
(X,Y,K,H) is a keyed hash family,where
? X is a set of possible messages
? Y is the set of possible message digests,or
authentication tags
? K is the keyspace
? H is a set of hash functions
? For each key K there is a hash function hK,X ? Y
in H
? Assume |X| >= |Y| (even better,2|X| >= |Y|)
Unkeyed hash functions
An unkeyed hash function is a mapping h,X ? Y,
where
? X is a set of possible messages
? Y is the set of possible message digests
?Unkeyed hash function
–|K| = 1
–Ex,SHA-1 (successor of MD4)
Ideal hash functions
? it is a simple matter to compute the probability
that k random elements z1,.,,,zk ? Z are
distinct,
? The first choice z1 is arbitrary; the probability that
z2 != z1 is 1 - l/n; the probability that z3 is distinct
from z1 and z2 is 1 - 2/n,etc,
? we estimate the probability of no collisions to be
Message Authentication codes (MACs)
Source (K) Destination (K)
Message m
y = hk(m)
Check
y = hk(m)
m,tag y
HMAC
? nested MAC algorithm (proposed standard)
– based on SHA-1
– uses 512-bit key k
– 2 512-bit constants,ipad and opad
? 160-bit MAC
– HMACk(x) = SHA-1((k ? opad) || SHA-1((K
? ipad) || x))
? ipad component resistant against unknown-key
collision attack
CBC MAC
x1
+ + + +
IV
x2 x3 x4
y4 y3 y2 y1
DES DES DES DES
Public-Key Applications
? can classify uses into 3 categories,
– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
– key exchange (of session keys)
? some algorithms are suitable for all uses,
others are specific to one,Only three
algorithms work well for both encryption
and digital signatures,RSA,ElGamal,and
Rabin,All of these algorithms are slow,
Security of Public-Key
Algorithms
? Since a cryptanalyst has access to the public key,
he can always choose any message to encrypt,
? Eve can generate a database of all possible session
keys encrypted with Bob’s public key,
? most public-key algorithms are particularly
susceptible to a chosen-ciphertext attack
? In systems where the digital signature operation is
the inverse of the encryption operation,this attack
is impossible to prevent unless different keys are
used for encryption and signatures,
Public Key,
n product of two primes,p and q (p and q must remain secret)
e relatively prime to (p - 1)(q - 1)
Private Key,
d e-1 mod ((p - 1)(q - 1))
Encrypting,
c = me mod n
Decrypting,
m = cd mod n
RSA Encryption
RSA Signature
p,q,primes,n = pq,ed = 1 mod (n),
e,n,public key,d,secret key,(factoring,n,1024 bits)
M,message,M in {0,1,..,n-1},
Signing,S = Md mod n
Verification,M = Se mod n
Key generation,p = 3,q = 5,n = 15,e = 3 => d = 3
Signing,M = 13,S = 13d mod n,=> S = 7
Verification,Checking M = Se mod n
?
Semantic security
? Total break
– The adversary can determine the private key of a
public key cryptosystem,or the secret key of a
symmetric key encryption system,
? Partial break
– The adversary is able with non-negligible probability
to
? decrypt a previously unseen ciphertext (without knowing
the private/secret key),or
? determine some specific information about the plaintext
given
the ciphertext,
Semantic security
? Distinguishability of ciphertexts
– The adversary is able to distinguish with probability greater
than ?,
? encryptions of different plaintexts,or
? encryptions of a given plaintext and a random string,
A public key cryptosystem in which the adversary cannot
(in polynomial time) distinguish ciphertexts,under certain
computational assumptions hold,is said to achieve
semantical security,
Perfect vs,Semantic security
? perfect secrecy,
– a passive adversary,even with infinite computational
resources
– can learn nothing about plaintext from ciphertext,
except its length
– Limitation,cannot be achieved unless key is as long as
message
? semantic security,polynomially bounded perfect
secrecy
– a passive adversary with poly,bounded resources can
learn nothing
Alice ga mod p Bob
gb mod p
The private key is,gab mod p
where p is a prime and g is a generator of Zp
Diffie-Hellman
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + Q
Group set,
All points P(x,y) lying
on an elliptic curve
Group operation,
Point addition
R'
R P
Q
Points P(x,y) on an Elliptic Curve
form a Group
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
Inverse element,
P'(x,-y) = P(x,y)
is mirrored on x-axis
Point addition with
inverse element,
P + P' = O
results in a neutral
element O(x,?) at
infinity P'
O
Neutral element,
P + O = P
P
Neutral and Inverse Elements
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
R = P + P
Point Doubling,
Form the tangent in
Point P(x,y)
R'
R P
Point Doubling – Adding a point
to itself
-3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4
kP = P + P +,.,+ P
Point Iteration,
3P
2P P
Point Iteration – Adding a point
k-1 times to itself
Definition of an Elliptic Curve
Cryptosystem
? version is currently v1
? fieldID identifies the finite field over which curve is defined
? curve coefficients a and b of the elliptic curve
? base specifies the base point P,a point P in the elliptic
curve group defined over GF(p)
? order the order n of the base point
Public Key Cryptography
Signature schemes
Let
? P be the set of all messages
? A be the set of signatures
? K be the set of all keys
Basic Mechanism of Signature
Schemes
? K,A key generation algorithm to randomly select
a public key pair,
? Sig K, A signature algorithm that takes message +
private key as input and generates a signature for
the message as output
? Ver K, A signature verification algorithm that
takes signature + public key as input and generates
information bit according to whether signature is
consistent as output,
Attack models
? Total Breaking Attack
- The attacker knows the public key,He tries to recover the
corresponding secret key,
? Forgery Attack
- The attacker knows the public key,He tries to find the signature
for a given message,
? Existential Forgery Attack
- The attacker knows the public key,He tries to find a pair of
a message and its signature,
? Chosen Message Attack (CMA)
- The attacker is able to sign messages but does not know the key
used,He tries to perform the (existential) forgery or to obtain the
secret key,
definitions
? A protocol is said to have perfect forward secrecy if compromise
of long term keys does not compromise past (short term)
session keys,
? A protocol is vulnerable to a known-key attack if compromise of
past session keys allows an attacker to compromise of future
session keys (including actively impersonating)
Needham Schroeder
Symmetric Key
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,
A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
A B
S
Freshness Attacks(3)
Needham Schroeder Symmetric Key
? i.1,A -> S, A,B,Na
? i.2,S -> A, {Na,B,Kab,{Kab,A}Kbs }Kas
? i.3,A -> I(B), {Kab,A}Kbs
? assume that Kab is compromised
? ii.3,I(A) -> B, {Kab,A}Kbs
? ii.4,B -> I(A), {Nb}Kab
? ii.5,I(A) -> B, {dec(Nb)}Kab
A B
S
Needham-Schroeder Public
Key (1)
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb}KPa
? 3,A -> B, {Nb}KPb
A B
Needham-Schroeder Public
Key (2)
? i.1,A -> I, {Na,A}KPi
? ii.1,I(A) -> B, {Na,A}KPb
? ii.2,B -> I(A), {Na,Nb}KPa
? i.2,I -> A, {Na,Nb}KPa
? i.3,A -> I, {Nb}KPi
? ii.3,I(A) -> B, {Nb}KPb
A I B
secret splitting
Algorithm,
Assume Trent wishes to protect the message m,
Trent generates a random bit string r,the same
length m,
Trent computes m ? r = s
Trent gives Alice r
Trent gives Bob s
? Each of the pieces is called a shadow,
? To reconstruct m,Alice and Bob XOR their
shadows together,
? If r is truly random,the system is perfectly
secure (OTP),
? To extend the scheme to n people,generate n
random bit strings e.g,m ? r ? s ? t = u
Adi Shamir (N,d)-Scheme
? Pick a prime p
? and a random polynomial
f (x) = ad-1xd-1 + ad-2xd-2 +…+ a0 mod p
a0 = f (0) = s
? User i receive si = f (i) mod p
? Any d users can interpolate to obtain f and
hence s
? Any d-1 users can not obtain any information
about s
Graph Isomorphism
? Assume that Peggy knows the isomorphism between the two graphs,G1
and G2,The following protocol will convince Victor of Peggy’s knowledge,
? (1) Peggy randomly permutes G1 to produce another graph,H,that is
isomorphic to G1,Because Peggy knows the isomorphism between H
and G1,she also knows the isomorphism between H and G2,
? (2) Peggy sends H to Victor,
? (3) Victor asks Peggy either to,
? (a) prove that H and G1 are isomorphic,or
? (b) prove that H and G2 are isomorphic,
? (4) Peggy complies,She either,
? (a) proves that H and G1 are isomorphic,without proving that H
and G2 are isomorphic,or
? (b) proves that H and G2 are isomorphic,without proving that H
and G1 are isomorphic,
? (5) Peggy and Victor repeat steps (1) through (4) n times,
