Chapter 9 slides, 3rdedition
Download
Report
Transcript Chapter 9 slides, 3rdedition
CS549:
Cryptography and Network
Security
© by Xiang-Yang Li
Department of Computer Science,
IIT
Cryptography and Network Security
1
Notice©
This lecture note (Cryptography and Network Security) is prepared by
Xiang-Yang Li. This lecture note has benefited from numerous
textbooks and online materials. Especially the “Cryptography and
Network Security” 2nd edition by William Stallings and the
“Cryptography: Theory and Practice” by Douglas Stinson.
You may not modify, publish, or sell, reproduce, create derivative
works from, distribute, perform, display, or in any way exploit any
of the content, in whole or in part, except as otherwise expressly
permitted by the author.
The author has used his best efforts in preparing this lecture note.
The author makes no warranty of any kind, expressed or implied,
with regard to the programs, protocols contained in this lecture
note. The author shall not be liable in any event for incidental or
consequential damages in connection with, or arising out of, the
furnishing, performance, or use of these.
Cryptography and Network Security
2
About Instructor
Associate Professor IIT
PhD/MS UIUC 1997-2000
BS, BE Tsinghua University
Research Interests:
Algorithm design and analysis
Wireless networks
Game theory
Computational geometry
Contact Information
Phone 312-567-5207
Email: [email protected]
Cryptography and Network Security
3
Office and Office hours
Office
SB 237D
Office hours
Monday 3:10PM – 4:10PM.
Wednesday 3:10PM– 4:10PM.
Or by contact: email [email protected],
phone 312 567 5207
Cryptography and Network Security
4
About This Course
Textbook
Cryptography: Theory and Practice
by Douglas R. Stinson CRC press
Cryptography and Network Security:
Principles and Practice; By William
Stallings Prentice Hall
Handbook of Applied Cryptography by
Alfred J. Menezes, Paul C. van Oorschot
and Scott A. Vanstone, CRC Press
I have electronic version!
Cryptography and Network Security
5
Grading and Others
Grading
Homework
Mid Term
Project
30%
25%
20% (select your own topic),
15 pages report
Final exam
25% (closed book)
Policy
Do it yourself
Can use library, Internet and so on, but you have to cite the sources
when you use this information
Cryptography and Network Security
6
Homeworks
Do it independently
No discussion
No copy
Can use reference books
Write your name also,
you could discuss with
classmates then write your own
report (about 10 pages for the
topic you selected)
Staple your solution
HW1 (Due 2/14/08)
HW2 (Due 3/14/08)
HW3 (Due 4/11/08)
Report (Due 05/05/08)
For report,
For project (presentation
and programming)
You SHOULD collaborate
with your group member and
you SHOULD make enough
contributions to get credit
Type your solution!
And print it then submit
Cryptography and Network Security
7
Topics
Introduction
Number Theory
Traditional Methods: secret key system
Modern Methods: Public Key System
Digital Signature and others
Internet Security: DoS, DDoS
Other topics:
secret sharing, zero-knowledge proof, bit commitment,
oblivious transfer,…
Cryptography and Network Security
8
Organization
Chapters
Introduction
Number Theory
Conventional Encryption
Block Ciphers
Public Key System
Key Management
Hash Function and Digital Signature
Identification
Secret Sharing
Pseudo-random number Generation
Email Security
Internet Security
Others
Cryptography and Network Security
9
Cryptography and Network Security
Introduction
Xiang-Yang Li
Cryptography and Network Security
10
Introduction
The art of war teaches us not on the likelihood
of the enemy’s not coming, but on our own
readiness to receive him; not on the chance of
his not attacking, but rather on the fact that
we have made our position unassailable.
--The art of War, Sun Tzu
Cryptography and Network Security
11
Criteria for Desirable Cryptosystems
Confidence in Security established
Hard or intractable problems?
Practical Efficiency
Space, time and so on
Explicitness
About its environment assumptions, security service
offered, special cases in math assumptions,
Protection tuned to application needs
No less, no more
Openness
Cryptography and Network Security
12
Most important
Security first
Efficiency, resource utilization, and
security tradeoffs
This is especially the case for resource constrained
networks such as wireless sensor networks
Limited power supply (thus limited communication, and
computation), limited storage space
Cryptography and Network Security
13
Cryptography
Cryptography (from Greek kryptós, "hidden", and
gráphein, "to write") is, traditionally, the study of
means of converting information from its normal,
comprehensible form into an incomprehensible
format, rendering it unreadable without secret
knowledge — the art of encryption.
Past: Cryptography helped ensure secrecy in
important communications, such as those of spies,
military leaders, and diplomats.
In recent decades, cryptography has expanded its
remit in two ways
mechanisms for more than just keeping secrets: schemes like
digital signatures and digital cash, for example.
in widespread use by many civilians, and users are not aware of it.
Cryptography and Network Security
14
Crypto-graphy, -analysis, -logy
The study of how to circumvent the use of cryptography is
called cryptanalysis, or codebreaking.
Cryptography and cryptanalysis are sometimes grouped
together under the umbrella term cryptology, encompassing
the entire subject.
In practice, "cryptography" is also often used to refer to
the field as a whole; crypto is an informal abbreviation.
Cryptography is an interdisciplinary subject,
linguistics
Mathematics: number theory, information theory, computational
complexity, statistics and combinatorics
engineering
Cryptography and Network Security
15
Close, but different fields
Steganography
the study of hiding the very existence of a message, and not
necessarily the contents of the message itself (for example,
microdots, or invisible ink)
http://en.wikipedia.org/wiki/Steganography
Traffic analysis
which is the analysis of patterns of communication in order
to learn secret information
The messages could be encrypted
http://en.wikipedia.org/wiki/Traffic_analysis
Cryptography and Network Security
16
Stenography Example
Last 2 bits
Cryptography and Network Security
17
Tools for Stenography
http://www.jjtc.com/Steganography/toolm
atrix.htm
Cryptography and Network Security
18
Network Security Model
Trusted Third Party
principal
principal
Security
transformation
Security
transformation
attacker
Cryptography and Network Security
19
Attacks, Services and Mechanisms
Security Attacks
Action compromises the information security
Could be passive or active attacks
Security Services
Actions that can prevent, detect such attacks.
Such as authentication, identification, encryption, signature, secret
sharing and so on.
Security mechanism
The ways to provide such services
Detect, prevent and recover from a security attack
Cryptography and Network Security
20
Attacks
Passive attacks
Interception
Release of message contents
Traffic analysis
Active attacks
Interruption, modification, fabrication
Masquerade
Replay
Modification
Denial of service
Cryptography and Network Security
21
Information Transferring
Cryptography and Network Security
22
Attack: Interruption
Cut wire lines,
Jam wireless
signals,
Drop packets,
Cryptography and Network Security
23
Attack: Interception
Wiring,
eavesdrop
Cryptography and Network Security
24
Attack: Modification
intercept
Replaced
info
Cryptography and Network Security
25
Attack: Fabrication
Also called impersonation
Cryptography and Network Security
26
Attacks, Services and Mechanisms
Security Attacks
Action compromises the information security
Could be passive or active attacks
Security Services
Actions that can prevent, detect such attacks.
Such as authentication, identification, encryption, signature, secret
sharing and so on.
Security mechanism
The ways to provide such services
Detect, prevent and recover from a security attack
Cryptography and Network Security
27
Important Services of Security
Confidentiality, also known as secrecy:
Integrity:
the recipient should be able to determine if the message has been
altered during transmission.
Authentication:
only an authorized recipient should be able to extract the
contents of the message from its encrypted form. Otherwise, it
should not be possible to obtain any significant information
about the message contents.
the recipient should be able to identify the sender, and verify that
the purported sender actually did send the message.
Non-repudiation:
the sender should not be able to deny sending the message.
Cryptography and Network Security
28
Secure Communication
protecting data locally only solves a minor
part of the problem. The major challenge
that is introduced by the Web Service
security requirements is to secure data
transport between the different
components. Combining mechanisms at
different levels of the Web Services
protocol stack can help secure data
transport (see figure next page).
Cryptography and Network Security
29
Secure Communication
Cryptography and Network Security
30
Secure Communication
The combined protocol HTTP/TLS or SSL is often
referred to as HTTPS (see figure). SSL was
originally developed by Netscape for secure
communication on the Internet, and was built into
their browsers. SSL version 3 was then adopted
by IETF and standardized as the Transport Layer
Security (TLS) protocol.
Use of Public Key Infrastructure (PKI) for session
key exchange during the handshake phase of TLS
has been quite successful in enabling Web
commerce in recent years.
TLS also has some known vulnerabilities: it is
susceptible to man-in-the-middle attacks and
denial-of-service attacks.
Cryptography and Network Security
31
SOAP security
SOAP (Simple Object Access Protocol) is designed to pass
through firewalls as HTTP. This is disquieting from a
security point of view. Today, the only way we can recognize
a SOAP message is by parsing XML at the firewall. The
SOAP protocol makes no distinction between reads and
writes on a method level, making it impossible to filter away
potentially dangerous writes. This means that a method
either needs to be fully trusted or not trusted at all.
The SOAP specification does not address security issues
directly, but allows for them to be implemented as
extensions.
As an example, the extension SOAP-DSIG defines the syntax and
processing rules for digitally signing SOAP messages and validating
signatures. Digital signatures in SOAP messages provide integrity and
non-repudiation mechanisms.
Cryptography and Network Security
32
PKI
PKI key management provides a sophisticated framework for
securely exchanging and managing keys. The two main
technological features, which a PKI can provide to Web
Services, are:
Encryption of messages: by using the public key of the recipient
Digital signatures: non-repudiation mechanisms provided by PKI and
defined in SOAP standards may provide Web Services applications with
legal protection mechanisms
Note that the features provided by PKI address the same
basic needs as those that are recognized by the
standardization organizations as being important in a Web
Services context.
In Web Services, PKI mainly intervenes at two levels:
At the SOAP level (non-repudiation, integrity)
At the HTTPS level (TLS session negotiation, eventually assuring
authentication, integrity and privacy)
Cryptography and Network Security
33
Some basic Concepts
Cryptography and Network Security
34
Cryptography
Cryptography is the study of
Secret (crypto-) writing (-graphy)
Concerned with developing algorithms:
Conceal the context of some message from all except
the sender and recipient (privacy or secrecy), and/or
Verify the correctness of a message to the recipient
(authentication)
Form the basis of many technological solutions to
computer and communications security problems
Cryptography and Network Security
35
Basic Concepts
Cryptography
encompassing the principles and methods of transforming
an intelligible message into one that is unintelligible, and
then retransforming that message back to its original form
Plaintext
The original intelligible message
Ciphertext
The transformed message
Message
Is treated as a non-negative integer hereafter
Cryptography and Network Security
36
Basic Concepts
Cipher
An algorithm for transforming an intelligible message
into unintelligible by transposition and/or substitution,
or some other techniques
Keys
Some critical information used by the cipher, known
only to the sender and/or receiver
Encipher (encode)
The process of converting plaintext to ciphertext
Decipher (decode)
The process of converting ciphertext back into plaintext
Cryptography and Network Security
37
Basic Concepts
cipher
an algorithm for encryption and decryption. The exact
operation of ciphers is normally controlled by a key — some
secret piece of information that customizes how the
ciphertext is produced
Protocols
specify the details of how ciphers (and other cryptographic
primitives) are to be used to achieve specific tasks.
A suite of protocols, ciphers, key management, userprescribed actions implemented together as a system
constitute a cryptosystem;
this is what an end-user interacts with, e.g. PGP
Cryptography and Network Security
38
Encryption and Decryption
Decipher P = D(K2)(C)
ciphertext
Plaintext
Encipher C = E(K1)(P)
K1, K2: from keyspace
These two keys could be different;
could be difficult to get one from the other
Cryptography and Network Security
39
What is Security?
Two fundamentally different securities
Unconditional security
No matter how much computer power is available, the cipher
cannot be broken
Using Shannon’s information theory
The entropy of the message I(M) is same as the entropy of the
message I(M|C) when known the ciphertext (and possible more)
Computational security
Given limited computing resources (e.g time needed for
calculations is greater than age of universe), the cipher
cannot be broken
What do we mean “broken”?
Proved by some complexity equivalence approach
Cryptography and Network Security
40
Cryptography and Network Security
Elementary Number Theory
Xiang-Yang Li
Cryptography and Network Security
41
Number theory
Elementary number theory
Main topic of this course
divisibility, the Euclidean algorithm to compute greatest
common divisors, factorization
Fermat's little theorem and Euler's theorem, the Chinese
remainder theorem and Euler's φ function are
investigated;
Analytic number theory
Algebraic number theory
Geometric number theory
Computational number theory
Cryptography and Network Security
42
Introduction to Number Theory
Divisors
b|a if a=mb for an integer m
b|a and c|b then c|a
b|g and b|h then b|(mg+nh) for any integer m,n
Prime number
P has only positive divisors 1 and p
Relatively prime numbers
No
common divisors for p and q except 1
Cryptography and Network Security
43
Prime numbers
Upto 200
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181
191 193 197 199
Largest known so far (till 2008, Jan 22)
232582657-1 with 9808358 digits (found 2006 using proof code G9)
When 2n-1is prime it is said to be a Mersenne prime (a French monk
1588-1648, conjecture 1644). Clearly n must be odd.
How many prime numbers are there?
Infinity ---- Euclid gave simple proof
Proof by contradiction
They were also irregularly placed (arbitrary gap)
How many in the range [0,n] -- Theta( n / log n)
Approximately, the nth prime n log n
How many primes with d bits approximately? ~ Theta(2d/d)
Cryptography and Network Security
44
Determining Primes?
How to determine if a given number n is
prime?
Deterministic Brute force testing
Testing whether a number a | n, for a in certain range
Random testing
A prime number should satisfy some properties
If a number x does NOT have any of such properties,
then this x is NOT a prime
Otherwise, it may be a prime number
Properties: for any number a, a does not divide x,
• More properties will be studied and used to design
efficient methods
Cryptography and Network Security
45
Greatest Common Divisor (GCD)
Greatest common divisor gcd(a,b)
The largest number that divides both a and b
Euclid's algorithm
Find the GCD of two numbers a and b, a<b
Use fact if a and b have divisor d so does
a-b, a-2b …
d ma nb
da b
d a 2b
d a 3b
d a qb
Cryptography and Network Security
46
Cont.
GCD (a,b) is given by:
let g0=b
g1=a
gi+1 = gi-1 mod gi
when gi =0 then gcd(a,b) = gi-1
The algorithm terminates in O(log b) rounds
Why?
Every round, the total number of bits of a and b is decreased by at
least one
What is a more precise
complexity bound?
Cryptography and Network Security
47
Properties
For any two integers a and b
Exist integers m and n: gcd(a,b) =ma+bn
Example:
a=2, b=3; we choose m=-1, n=1 so –2+3=1
a=6, b=11; we choose m=2, n=-1 so 2*6-11=1
Simple proof?
Integer n can be factored as
n=p1a1 p2a2 p3a3…. pnan
where pi is prime number
Cryptography and Network Security
48
Extended Euclidean Algorithm
input are two integers a and b, computes
their greatest common divisor (gcd) as well as
integers x and y such that ax + by = gcd(a, b).
It later can also be used to compute the
inverse of an integer
1
a mod n
Cryptography and Network Security
49
Proof
Assume we compute gcd(x0,y0), x0>y0
Let Xi=(xi,yi); 0xi-qi+1yi+1<|yi|
Then Xi=MiXi-1, where Mi=(0,1; 1,-qi)
Assume the gcd algorithm terminates in n steps
We have MnMn-1…M1X0=(gcd(x0,y0), 0)T
a
b
…
Assume MnMn-1 M1=(
)
c
d
Then ax0+by0=gcd(x0,y0)
The above algorithm is to keep track of a,b,c,d, and xi,yi
values.
Cryptography and Network Security
50
Modular Arithmetic
Congruence
a b mod n says when divided by n that a and b have
the same remainder
It defines a relationship between all integers
aa
a b then b a
a b, b c then a c
Cryptography and Network Security
51
Cont.
addition
(a+b) mod n (a mod n) + (b mod n)
subtraction
a-b mod n a+(-b) mod n
multiplication
a b mod n
derived from repeated addition
Possible: a*b 0 where neither a, b 0 mod n
Example: 2*3 =0 mod 6
Cryptography and Network Security
52
Addition and Multiplication
Integers modulo n with addition and
multiplication form a commutative ring with
the laws of
Associativity
(a+b)+c a+(b+c) mod n
Commutativity
a+b b+a mod n
Distributivity
(a+b)*c (a*c)+(b*c) mod n
Cryptography and Network Security
53
Cont.
Division
b/a mod n
multiplied by inverse of a: b/a = b*a-1 mod n
a-1*a 1 mod n
3-1 7 mod 10 because 3*7 1 mod 10
Inverse does not always exist!
Only when gcd(a,n)=1
Cryptography and Network Security
54
Euclid's Extended GCD Routine
If (a,n)=1 then the inverse always exists
Can extend Euclid's algorithm to find
inverse by keeping track of gi = ui.n + vi.a
Extended Euclid's (or binary GCD)
algorithm to find inverse of a number a
mod n (where (a,n)=1) is:
Cryptography and Network Security
55
Inverse
Inverse(a,n) is given by:
X=(x1,x2,x3)=(1,0,n); Y=(y1,y2,y3)=(0,1,a)
If y3=0 return x3=gcd(a,n); no inverse
If y3=1 return y3=gcd(a,n); y2=a-1 mod n
Q=[x3/y3]
T=X-Q*Y
X=Y; Y=T
Goto 2nd step
Cryptography and Network Security
56
When inverse exists
If gcd(a,n)=1 inverse exists
We can find x, y such that ax+ny=1
Then x= a-1 mod n
If inverse exists gcd(a,n)=1
x be the inverse of a, i.e., ax=1 mod n
Then x a=1+q n for some integer q
Let gcd(a,n)=d. Then d | (x a-q n )
Obviously d=1 since x a-q n =1
Let
Cryptography and Network Security
57
Galois Field
If n is constrained to be a prime number p
then this forms a Galois field modulo p
denoted GF(p) and all the normal laws
associated with integer arithmetic work
Exponentiation
b = ae mod p
Discrete Logarithms
find x where ax = b mod p
Cryptography and Network Security
58
Relative primes
Two numbers a and n are relative primes if
gcd(a,n)=1
Consider all integers 0<a <n
How many are relative prime to n?
Equivalently, how many a such that a-1 mod n exists
Typically
Zn={0,1,2,….,n-1} : all integers 0<= a < n
Zn*={a| 0<= a < n, gcd(a,n)=1}
All integers in Zn that are co-prime with n
Also called reduced residue set mod n
Cryptography and Network Security
59
Euler Totient Function
If consider arithmetic modulo n, then a
reduced set of residues is a subset of the
complete set of residues modulo n which
are relatively prime to n
eg for n=10,
the complete set of residues is {0,1,2,3,4,5,6,7,8,9}
the reduced set of residues is {1,3,7,9}
The number of elements in the reduced set
of residues is called the Euler Totient
function (n)
Cryptography and Network Security
60
cont
Compute (n)
If factoring of n is known
(n)=n (1-1/pi) where pi is its prime factor
Otherwise
It is expensive!
But not proved yet
computing (n) when knowing fact n =pq but
not the number p and q
Conjectured
to be a hard question
But not proved yet.
Equivalent to find p and q
Cryptography and Network Security
61
cont
Equivalency: finding p,q computing (n)
Proof
If we found p and q, then (n)=(p-1)(q-1)
if we found (n), then solve p, q from equations
n pq
( n ) ( p 1)( q 1)
Cryptography and Network Security
62
Euler's Theorem
Let gcd(a,n)=1 then
a(n)
mod n = 1
Proof:
consider all reduced residues xi in
Zn*={x| 0<= x < n, gcd(x,n)=1}
Then axi,1<=i <= (n) also form reduced residues set
Using axi = xi mod n
Using Zn* and aZn* are same sets!
have a(n) xi = xi mod n
Thus, a(n) =1 mod n
We
Using the fact that xi has inverse
Cryptography and Network Security
63
Fermat's Little Theorem
Let p be a prime and gcd(a,p)=1 then
ap-1 mod p = 1
Proof: similar to the proof of Euler’s theorem
But consider all integers in Zp
Generally, for any prime number p
ap mod p = a (true for any number a)
Generally, for any number n=pq
a(n) mod n = a (true for any number a)
Need to prove for the case gcd(a,n)>1
Do it
yourself
Cryptography and Network Security
64
Efficient computing of exponential
Compute ab mod n efficiently when b, n large?
Example: compute a1024 mod 21024 +1
Simple approach: repetitively time a 1024 times?
Efficient computation:
Write number b in binary format as xkxk-1xk-2….x2x1x0
Let t1=a mod n. Then compute ti+1= ti * ti mod n for i<k
b
Then
xk xk 1xk 2 ....x2 x1x0
a
mod n a
[a
( 2i ) xi
]
mod n
mod n
0 i k
ti
xi
Time
complexity?
mod n
0 i k
Cryptography and Network Security
65
Chinese Remainder Theorem
By Qin Jiushao
Let m1,m2,….mk be pair-wise relative prime numbers
Assume integer x= ai mod mi for 1<= I <= k
Then x= ai ei mod M
Where M= mi; Mi=M/ mi
ei= Mi * (Mi-1 mod mi)
Proof
For each i, the integers mi and M/mi are coprime, and using the
extended Euclidean algorithm we can find integers r and s such
that r mi + s M/mi = 1. If we set ei = s M/mi, then we have
ei =1 mod mi and ei =1 mod mj for j<>i.
Cryptography and Network Security
66
General CRT
Sometimes, the simultaneous congruences
can be solved even if the mi's are not
pairwise coprime.
a solution x exists if and only if ai ≡ aj (mod gcd(ni, nj))
for all i and j.
All solutions x are congruent modulo the least common
multiple of the ni.
Methods: successive substitution
Cryptography and Network Security
67
Example
consider the simultaneous congruences
x ≡ 3 (mod 4)
x ≡ 5 (mod 6)
Can be transformed to
x ≡ 3 (mod 4)
x ≡ 5 (mod 2) x ≡ 1 (mod 2)
x ≡ 5 (mod 3)
Then transformed to
x ≡ 3 (mod 4)
x ≡ 2 (mod 3)
Using CRT
X=11 (mod 12)
Cryptography and Network Security
68
Primality Testing
To check if exists integer a such that a|n
Primary school method
Test a=2,3,4,5,6,….,n-1
Test a=2,3,4,5,…, n0.5
Test a=2,3,5,7,11,…., p, where prime number p<=n0.5
Two slow!
Check almost n numbers
Check n0.5 numbers
At least around (n/ln n)0.5 numbers need be checked
Example
Number n~21024, then
(n/ln n)0.5~(21024 /1024) 0.5 ~ 2507
Assume 230 numbers per second, takes about 2507-30*16 = 227 days
Any improvement?
Cryptography and Network Security
69
Classification of Testing Primes
The Quick Tests for Small Numbers and Probable
Primes
Finding Very Small Primes --- trivial division
Fermat, Probable-Primality and Pseudoprimes
Strong Probable-Primality and a Practical Test
The Classical Tests
N-1 Tests (and Pepin's Test for Fermats)
N+1 Tests (and the Lucas-Lehmer Test for Mersennes)
A Combined Test -- and more
The General Purpose Tests
Neoclassical Tests, especially APR and APR-CL
Using Elliptic Curves, especially the ECPP Test
A Polynomial Time Algorithm
Cryptography and Network Security
70
Fermat Little Theorem Based
Fermat's theorem gives us a powerful test
for compositeness:
Given n > 1, choose a > 1 and calculate an-1 modulo n
(there is a very easy way to do quickly by repeated
squaring)
If the result is not one modulo n, then n is composite.
If it is one modulo n, then n might be prime so n is
called a weak probable prime base a (or just an aPRP).
Some early articles call all numbers satisfying this test
pseudoprimes, but now the term pseudoprime is
properly reserved for composite probable-primes.
Cryptography and Network Security
71
Carmichael number
There may be relatively few pseudoprimes,
but there are still infinitely many of them
for every base a>1, so we need a tougher
test.
One way to make this test more accurate is
to use multiple bases (check base 2, then 3,
then 5,...). But still we run into an
interesting obstacle called the Carmichael
numbers.
The composite integer n is a Carmichael number if
an-1=1 (mod n) for every integer a relatively prime to n.
Cryptography and Network Security
72
Strong probable-primality and a
practical test
A better way to make the Fermat test more
accurate is to realize that if an odd number n is
prime, then the number 1 has just two square
roots modulo n: 1 and -1.
So the square root of an-1, a(n-1)/2 (since n will be odd), is either 1 or
-1.
Algorithm
Write n-1 = 2sd where d is odd and s is non-negative: n is a strong
probable-prime base a (an a-SPRP) if either ad = 1 (mod n) or
(ad)2r = -1 (mod n) for some non-negative r less than s.
It has been proven ([Monier80] and [Rabin80]) that the strong
probable primality test is wrong no more than 1/4th of the time (3
out of 4 numbers which pass it will be prime).
Cryptography and Network Security
73
Simple Fact
Equation x21 mod p has only solutions 1,-1
If p is prime number
Simple proof: (x+1)(x-1) 0 mod p
So if we find another solution, then p can
not be prime number!
Miller and Rabin 1975,1980
Randomly chosen integer a
If a21 mod p then p is not prime number
Integer a is called the witness
Otherwise p maybe, or maybe not a prime number
Cryptography and Network Security
74
Witness Algorithm
Witness(a,n)
Let bkbk-1…b1b0 be the binary code of n-1
Let d=1
For i=k downto 0
x=d; d=d*d mod n
If d=1 and x1, and x n-1
return TRUE
If bi=1 then d=d*a mod n
Endfor
If d 1 then return TRUE
Return FALSE
Cryptography and Network Security
75
Facts
Analyze the result of witness
If returns TRUE, then n is not prime number
Find other solutions for x21 mod n
Otherwise, n maybe prime number
Given odd n and random a
Witness fails with probability less than 0.5
Run witness algorithm s times
If one time, it is TRUE
Then n is not prime number
Otherwise, Pr(n is prime)>1-2-s
Cryptography and Network Security
76
Randomized Methods
Las Vegas Method
Always produces correct results
Runs in expected polynomial time
Monte Carlo Method
Runs in polynomial time
May produce incorrect results with bounded probability
No-Biased Monte Carlo Method
Answer yes is always correct, but the answer no may be
wrong
Yes-biased Monte Carlo Method
Answer no is always correct, but the answer yes may be
wrong
Cryptography and Network Security
77
Witness Algorithm
Witness Algorithm is based on Monte Carlo
Method
It actually test compositeness, not primality
When it reports yes, the number is always composite
When it reports no, input may be composite, prime
Probability Result
Pr(input=composite | ans=composite)= 1
Pr(ans=no | input=composite)<1/2
Pr(input=composite | ans=no) 1/4
Cryptography and Network Security
78
Time Complexity
Each round of witness cost O(log n)
Unit: integer multiplication and modular arithmetic
So the primality testing cost
O(s log n)
The confidence is 1-2-s if report prime
The confidence is 1 if report non-prime
Miller's Test [Miller76]: If the extended
Riemann hypothesis is true, then if n is an
a-SPRP for all integers a with 1 < a < 2(log
n)2, then n is prime.
Cryptography and Network Security
79
More on proving primes (N-1 test
Theorem 1: Let n > 1. If for every prime
factor q of n-1 there is an integer a such
that
an-1
= 1 (mod n), and
a(n-1)/q is not 1 (mod n);
then n is prime.
Cryptography and Network Security
80
N-1 test
Theorem 2: Suppose n-1 = FR, where F>R,
gcd(F,R) is one and the factorization of F
is known. If for every prime factor q of F
there is an integer a>1 such that
an-1
= 1 (mod n), and
gcd(a(n-1)/q-1,n) = 1;
then n is prime.
Cryptography and Network Security
81
N+1 test
Lucas-Lehmer Test (1930): Let n be an
odd prime. The Mersenne number M(n) =
2n-1 is prime if and only if
S(n-2) = 0 (mod M(n)) where
S(0) = 4 and S(k+1) = S(k)2-2.
Cryptography and Network Security
82
ECPP method
What is the next big leap in primality proving? To
switch from Galois groups to some other, perhaps
easier to work with groups--in this case the points
on Elliptic Curves modulo n.
An Elliptic curve is a curve of genus one, that is a curve that can be
written in the form
E(a,b) : y2 = x3 + ax + b (with 4a3 + 27b2 not zero)
http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html
for implementation
Heuristically, the best version of ECPP is
O((log n)4+eps) for some eps>0
Cryptography and Network Security
83
Deterministic Poly-Time Method
In 2002 Agrawal, Kayal and Saxena found a
relatively simple deterministic algorithm
which relies on no unproved assumptions.
There has been a long list of research efforts devoted to
find deterministic polynomial time methods for testing
primes
Cryptography and Network Security
84
Basics
Theorem: Suppose that a and p are relatively
prime integers with p > 1. p is prime if and only if
(x-a)p = (xp-a) (mod p)
Proof.
If p is prime, then p divides the binomial coefficients pCr for r = 1,
2, ... p-1. This shows that (x-a)p = (xp-ap) (mod p), and the
equation above follows via Fermat's Little Theorem.
On the other hand, if p > 1 is composite, then it has a prime divisor
q. Let qk be the greatest power of q that divides p. Then qk does
not divide pCq and is relatively prime to ap-q, so the coefficient of
the term xq on the left of the equation in the theorem is not zero,
but it is on the right.
Cryptography and Network Security
85
AKS method
Input: Integer n > 1
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;
Cryptography and Network Security
86
Time Complexity
they proved would run in at most
O((log n)12f(log log n)) time where f is a polynomial
AKS also showed that if Sophie Germain primes
have the expected distribution [HL23] (and they
certainly should!), then the exponent 12 in the
time estimate can be reduced to 6, bringing it
much closer to the (probabilistic) ECPP method.
But of course when actually finding primes it is the unlisted
constants1 that make all of the difference! We will have to wait
for efficient implementations of this algorithm (and hopefully
clever restatements of the painful for loop) to see how it compares
to the others for integers of a few thousand digits. Until then, at
least we have learned that there is a polynomial-time algorithm for
all integers that both is deterministic and relies on no unproved
conjectures!
Cryptography and Network Security
87
Primitive Root
Order of integer ordn(a)
The order of a modulo n is the smallest positive k such
that ak1 mod n
Primitive Root
Integer
a is a primitive root of n if the order of a
modulo n is (n)
Not all integers have primitive root
Example n=pq for primes p and q
Prime
p has (p-1) primitive roots
Cryptography and Network Security
88
cont
When primitive root exists
Number n in format of p, 2p, pk, 2pk for some integer k
and prime number p
Otherwise the primitive root does not exist
a1
ak
p
1
q
....
q
Find a PR for p such that
1
k
Let a=2, i=1
If i>k, a is a PR, otherwise go to step 3
( p 1)/ q
1 mod p
If a
let i=i+1 and go to step 2;
otherwise let i=1, and a=a+1 and repeat this step 3.
i
Cryptography and Network Security
89
Some “hard” questions
Some questions that are assumed to be
hard, will be used as bases for
cryptography
Integer factorization
Given n, find all its prime factors
Discrete logarithm
Given g, y, and p, find x such that gxy mod p
Square root
Given b, find x such that x2b mod n. Here n is not a
prime number
Cryptography and Network Security
90
Integer Factorization
write an integer as product of prime numbers.
For example, given the number 45, the prime factorization would be 32·5.
The factorization is always unique, according to the fundamental theorem
of arithmetic
Given two large prime numbers, it is easy to multiply them. However,
given their product, it appears to be difficult to find the factors.
This is relevant for many modern systems in cryptography. If a fast
method were found for solving the integer factorization problem, then
several important cryptographic systems would be broken.
Although fast factoring is one way to break these systems, there may be
other ways to break them that don't involve factoring. So it is possible
that the integer factorization problem is truly hard, yet these systems can
still be broken quickly.
A rare exception is the BBS generator. It has been proved to be exactly as
hard as integer factorization: if you can break the generator in polynomial
time then you can factorize integers in polynomial time, and vice versa
Cryptography and Network Security
91
Current state of the art
If a large, n-bit number is the product of
two primes that are roughly the same size,
no polynomial time factoring algorithm is known
the best known algorithms are sub-exponential, but
super-polynomial: asymptotic running time by the
general number field sieve (GNFS) algorithm, is
Polynomial methods known for quantum computer!
Cryptography and Network Security
92
Sub-exponential
There are published algorithms that are
faster than O((1+ε)b) for all positive ε, i.e.,
sub-exponential, where b is the number of
bits of the input
Cryptography and Network Security
93
Factoring algorithms
Special purpose
its running time depends on the properties of unknown factors:
size, special form, etc.
Examples
Trial division, Pollard's rho algorithm, Pollard's p-1
algorithm, Lenstra elliptic curve factorization, Congruence
of squares, Special number field sieve
General purpose
running time depends solely on the size of the integer to be
factored. This is the type of algorithm used to factor RSA numbers.
Most general-purpose algorithms are based on the congruence of
squares method.
Examples:
Quadratic sieve, General number field sieve
Cryptography and Network Security
94
Factorization for Quantum
Computers
For an ordinary computer, general number field
sieve (GNFS) is the best published algorithm for
large n (more than about 100 digits).
For a quantum computer, however, Peter Shor
discovered an algorithm in 1994 that solves it in
polynomial time. This will have significant
implications for cryptography if a large quantum
computer is ever built.
Shor's algorithm takes only O(b3) time and O(b)
space on b-bit number inputs.
In 2001, the first 7-qubit quantum computer
became the first to run Shor's algorithm. It
factored the number 15.
Cryptography and Network Security
95
List of Algorithms
Special-purpose
A special-purpose factoring algorithm's running time depends on the
properties of its unknown factors: size, special form, etc. Exactly what the
running time depends on varies between algorithms.
Trial division
Pollard's rho algorithm
Algebraic-group factorisation algorithms amongst which are Pollard's p − 1 algorithm,
Williams' p+1 algorithm and Lenstra elliptic curve factorization
Fermat's factorization method
Special number field sieve
General-purpose
A general-purpose factoring algorithm's running time depends solely on the
size of the integer to be factored. This is the type of algorithm used to
factor RSA numbers. Most general-purpose factoring algorithms are based
on the congruence of squares method.
Dixon's algorithm
Continued fraction factorization (CFRAC)
Quadratic sieve
General number field sieve
Shanks' square forms factorization (SQUFOF)
Cryptography and Network Security
96
Discrete Logarithms
Y gx mod p
Given y, g, and p, compute x as logg(y)
1/3
2/3
Time complexity O(e(ln p) (ln ln p) )
Best known until now
In other words, if p is large, then it is very hard to solve the
discrete logarithm problem
Several protocols are based on this
ElGamal discrete log cryptosystem, Diffie-Hellman key exchange
and the Digital Signature Algorithm.
Current methods:
the Pohlig-Hellman algorithm if p-1 is a product of small primes,
so this should be avoided in those applications
Cryptography and Network Security
97
Methods
More sophisticated algorithms exist, usually
inspired by similar algorithms for integer
factorization. These algorithms run faster than
the naive algorithm, but none of them runs in
polynomial time.
Baby-step giant-step (Also known as 'Little-Step Big-Step')
Pollard's rho algorithm for logarithms
Pollard's lambda algorithm (aka Pollard's kangaroo algorithm)
Pohlig-Hellman algorithm
Index calculus algorithm
Number field sieve
Cryptography and Network Security
98
Quadratic Residue
Quadratic Residue
Integer b is a quadratic residue of modulo integer n if
and only if x2 b mod n has a solution for x
Number x is called the square root of b
Otherwise b is called quadratic nonresidue
Given odd prime p,
b is quadratic residue, iff b(p-1)/2 1 mod p
b is quadratic nonresidue, iff b(p-1)/2 -1 mod p
These facts can be used to test primes with probability
Cryptography and Network Security
99
Computing Square root mod p
Given number a, find number x, x2 =a mod p
If p=3 mod 4, then x=a(p+1)/4 mod p is a solution.
If p=5 mod 8, a(p-1)/4 =1 mod p then x= a(p+3)/8 mod p
If p=5 mod 8, a(p-1)/4 =-1 mod p then x= 2a(4a)(p-5)/8 mod p
h 1
If p=1 mod 8,
xa
2
N
p 1 2k h
sk
Here h is an odd number
Cryptography and Network Security
100
Compute square-root mod p
Find a solution to x2 =a mod p if exists
Let r=0, s=p-1; while s even, {r=r+1; s=s/2;}
Choose random n such that n 1
p
Let z=ns mod p; x=a(s+1)/2 mod p; b=as mod p;
If b=1, return x as a solution
Let m=1, y=b2 mod p; while y<>1 {y= y2 mod p; m=m+1;}
If r=m then a is Quadratic non-residue; exit;
r-m-1
Let x=xz2
mod p and b=bz2r-m mod p and z=z2r-m mod p
Go to step 4
The expected running time is O(log4 p)
Cryptography and Network Security
101
Complexity Theory
The input length of a problem is the number n of
symbols used to characterize it
Complexity of a method
Function f(n) is order O(g(n)) if
f(n)<=c*|g(n)|, for all n>=N0, for some c
Function f(n) is order (g(n)) if
f(n)>=c*|g(n)|, for all n>=N0, for some c
Function f(n) is order (g(n)) if
c1*|g(n)|<=f(n)<=c2*|g(n)|, for all n>=N0, for some c1 and c2
Polynomial time algorithm (P)
solves any instance of a particular problem with input length n in time
O(p(n)), where p is a polynomial
Cryptography and Network Security
102
Cont.
Non-deterministic polynomial time algorithm
(NP)
is one for which any guess at the solution of an instance of
the problem may be checked for validity in polynomial
time.
NP-complete problems
are a subclass of NP problems for which it is known that if
any such problem has a polynomial time solution, then all
NP problems have polynomial solutions.
Co-NP: the complements of NP problems.
Cryptography and Network Security
103
Cryptography and Network Security
Conventional Methods
Xiang-Yang Li
Cryptography and Network Security
104
Roadmap of Cryptography
classical cryptography (--- 1920s)
secret writing required only pen and paper
Mostly: transposition, substitution ciphers
Easily broken by statistics analysis (e.g., frequency)
mechanical devices invented for encryption
Rotor machines (e.g. Enigma cipher) 1930s-1950s
featured in films, such as in the James Bond adventure From
Russia with Love
specification of DES and the invention of RSA
(1970s) --- modern ciphers
Public key system, most notably
Quantum Cryptography (future?)
Cryptography and Network Security
105
Quantum Cryptography
Quantum cryptography currently has two aspects.
quantum key exchange (also known as quantum key distribution), a
method for secure communications based on quantum mechanics
conjectured effect of quantum computing on cryptanalysis, although it is
currently, like quantum computing itself, only a theoretical concept.
Basic idea of quantum key exchange is to use the
"noisy" properties of light to render incoherent an
image that acts to complement a secret key.
This image can be represented in a number of ways, but the ability to
decode that image rests upon an understanding of how it was made. No
way to intercept the transmission without changing it is possible, so key
information can be exchanged with great confidence it has been
transmitted secretly.
quantum computing will considerably extend the reach of cryptanalysis,
making brute force key space searches much more effective -- if such
computers ever become possible in actual practice
Cryptography and Network Security
106
History
Ancient ciphers
Have a history of at least 4000 years
Ancient Egyptians enciphered some of their
hieroglyphic writing on monuments
Ancient Hebrews enciphered certain words in the
scriptures
2000 years ago Julius Caesar used a simple substitution
cipher, now known as the Caesar cipher
Roger bacon described several methods in 1200s
Cryptography and Network Security
107
History
Ancient ciphers
Geoffrey Chaucer included several ciphers in his works
Leon Alberti devised a cipher wheel, and described the
principles of frequency analysis in the 1460s
Blaise de Vigenère published a book on cryptology in
1585, & described the polyalphabetic substitution
cipher
Increasing use, esp in diplomacy & war over centuries
Cryptography and Network Security
108
Classical Cryptographic Techniques
Two basic components of classical ciphers:
Substitution: letters are replaced by other letters
Transposition: letters are arranged in a different order
These ciphers may be:
Monoalphabetic:
only one substitution/ transposition is
used, or
Polyalphabetic:where several substitutions/
transpositions are used
Product cipher:
several ciphers concatenated together
Cryptography and Network Security
109
Encryption and Decryption
Plaintext
Encipher C = E(K)(P)
ciphertext
Decipher P = D(K)(C)
Key source
Cryptography and Network Security
110
Key Management
Using secret channel
Encrypt the key
Third trusted party
The sender and the receiver generate key
The key must be same
We will talk more about how we can generate keys for
two parties who are “unknown” of each other before,
and want secure communication
Cryptography and Network Security
111
Attacks
Recover the message
Recover the secret key
Thus also the message
Thus the number of keys possible must be
large!
Cryptography and Network Security
112
Possible Attacks
Ciphertext only
Algorithm, ciphertext
Known plaintext
Algorithm, ciphertext, plaintext-ciphertext pair
Chosen plaintext
Algorithm, ciphertext, chosen plaintext and its ciphertext
Chosen ciphertext
Algorithm, ciphertext, chosen ciphertext and its plaintext
Chosen text
Algorithm, ciphertext, chosen plaintext and ciphertext
Cryptography and Network Security
113
Steganography
Conceal the existence of message
Character marking
Invisible ink
Pin punctures
Typewriter correction ribbon
Cryptography renders message
unintelligible!
Cryptography and Network Security
114
Contemporary Equiv.
Least significant bits of picture frames
2048x3072 pixels with 24-bits RGB info
Able to hide 2.3M message
Drawbacks
Large overhead
Virtually useless if system is known
Improvement
Using some “random” sequence of the last bit for storing the data
Challenge: produce such random sequence such that the attacker
cannot figure out the sequence!
Cryptography and Network Security
115
Caesar Cipher
Replace each letter of message
by a letter a fixed distance away
Reputedly
used by Julius Caesar
Example:
L FDPH L VDZ L FRQTXHUHG
I CAME I SAW I CONGUERED
The
mapping is
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Cryptography and Network Security
116
Mathematical Model
Description
Assume all letters are mapped to integers [0,25]
A:-0, B-1, ….., Z25
E(k) : i i + k mod 26
Decryption D(k) : i i - k mod 26
Encryption
Cryptography and Network Security
117
Cryptanalysis: Caesar Cipher
Key space: 26
Exhaustive
key search
Example
GDUCUGQFRMPCNJYACJCRRCPQ
HEVDVHRGSNQDOKZBDKDSSDQR
Plaintext:
JGXFXJTIUPSFQMBDFMFUUFSTKHYGYKUJV
GRNCEGNGVVGTU
Ciphertext:
LIZHZLVKWRUHSODFHOHWWHUVMJAIAMWX
SVITPEGIPIXXIVW
Cryptography and Network Security
118
Character Frequencies
In most languages letters are not equally
common
in English e is by far the most common letter
Have tables of single, double & triple letter
frequencies
Use these tables to compare with letter
frequencies in ciphertext,
a monoalphabetic substitution does not change relative
letter frequencies
do need a moderate amount of ciphertext (100+ letters)
Cryptography and Network Security
119
Letter Frequency Analysis
Single Letter
A,B,C,D,E,…..
Double Letter
TH,HE,IN,ER,RE,ON,AN,EN,….
Triple Letter
THE,AND,TIO,ATI,FOR,THA,TER,RES,…
Cryptography and Network Security
120
Letter Frequencies
Cryptography and Network Security
121
Letter Frequencies
Cryptography and Network Security
122
N-gram Frequencies
Digraph Frequency
th he an in er on re ed nd ha at en es of nt ea ti to io
le is ou ar as de rt ve
Trigraph Frequency
the
and tha ent ion tio for nde has nce tis oft men
For more, see http://www.letterfrequency.org
Cryptography and Network Security
123
Modular Arithmetic Cipher
Use a more complex equation to calculate
the ciphertext letter for each plaintext
letter
E(a,b) : i ai + b mod 26
Need
gcd(a,26) = 1
Otherwise, not reversible
So, a2, 13, 26
Caesar cipher: a=1, b=3
Cryptography and Network Security
124
Cryptanalysis
Key space:12*26
Brute force search
Use letter frequency counts to guess a
couple of possible letter mappings
frequency
pattern not produced just by a shift
But it is still a substitution, thus we can use
frequency analysis
use these mappings to solve 2 simultaneous equations
to derive above parameters
Cryptography and Network Security
125
Playfair Cipher
The Playfair cipher or Playfair square is a
manual symmetric encryption technique and
was the first literal digraph substitution
cipher.
The
scheme was invented in 1854 by Charles
Wheatstone, but bears the name of Lord Playfair who
promoted the use of the cipher.
Cryptography and Network Security
126
Playfair Cipher
Used in WWI and WWII
s
e
i/j
a
m
b
p
c
l
d
f
o
v
g
q
w
h
r
x
k
t
y
n
u
z
Key: simple
Cryptography and Network Security
127
Playfair Cipher
Use filler letter to separate repeated
letters
Encrypt two letters together
Same row– followed letters
ac--bd
Same column– letters under
qw--wi
Otherwise—square’s corner at same row
ar--bq
Cryptography and Network Security
128
Analysis
Size of diagrams: 25!
But the actual different diagrams are not 25!
Two diagrams are the same if they derive the same
encryption and decryption method
Then what is the number of difference diagrams in
playfair cipher?
25!/25=24!
Difficult using frequency analysis
But it still reveals the frequency information
Frequency of 2-gram (bi-gram, two-letters)
Cryptography and Network Security
129
Playfair Cryptanalysis
Like most pre-modern era ciphers, the
Playfair cipher can be easily cracked if
there is enough text.
Obtaining the key is relatively straightforward if both
plaintext and ciphertext are known.
When only the ciphertext is known, brute force
cryptanalysis of the cipher involves searching through
the key space for matches between the frequency of
occurrence of digrams (pairs of letters) and the known
frequency of occurrence of digrams in the assumed
language of the original message.
Cryptography and Network Security
130
Playfair, cont
A different approach to tackling a Playfair cipher
is the shotgun hill climbing method.
This starts with a random square of letters. Then minor changes are
introduced (i.e. switching letters, rows, or reflecting the entire
square) to see if the candidate plaintext is more like standard
plaintext than before the change (perhaps by comparing the
trigrams to a known frequency chart).
If the new square is deemed to be an improvement, then it is
adopted and then further mutated to find an even better candidate.
Eventually, the plaintext or something very close is found to
achieve a maximal score by whatever grading method is chosen.
Computers can adopt this algorithm to crack Playfair ciphers with
a relatively small amount of text.
Cryptography and Network Security
131
Hill Cipher
Hill cipher is a polygraphic substitution cipher
based on linear algebra.
Invented by Lester S. Hill in 1929, it was the first polygraphic
cipher in which it was practical (though barely) to operate on more
than three symbols at once.
Each letter is treated as a digit in base 26: A = 0, B =1, and so on. A
block of n letters is then considered as a vector of n dimensions,
and multiplied by a n × n matrix, modulo 26. The components of
the matrix are the key, and should be random provided that the
matrix is invertible in (to ensure decryption is possible).
The Hill cipher has achieved Shannon's diffusion, and an ndimensional Hill cipher can diffuse fully across n symbols at once.
Cryptography and Network Security
132
Hill Cipher Machine
Cryptography and Network Security
133
Hill Cipher Machine
With fixed Key and patented
Triple encryption was recommended for
security:
a
secret nonlinear step, followed by the wide diffusive
step from the machine, followed by a third secret
nonlinear step.
Such a combination was actually very powerful for
1929, and indicates that Hill apparently understood the
concepts of a meet-in-the-middle attack as well as
confusion and diffusion.
Unfortunately, his machine did not sell.
Cryptography and Network Security
134
Hill Cipher
Encryption
Assign each letter an index
C=KP mod 26
Matrix K is the key
Decryption
P=K-1C mod 26
Thus, we can decrypt iff gcd(det(K), 26) =1.
Cryptography and Network Security
135
How to Decrypt?
Compute K-1
Compute det(K)
Check if gcd(det(K), 26) =1
If not, then K-1 do not exist
Else K-1 is
111 K1,1
1 1n K
1, n
1
K n ,1
1
det( K )
2n
1
K
n ,n
1 n
Cryptography and Network Security
136
cont
K i, j
k1,1
k1, j 1
k1, j 1
k1,n
k i 1,1 k i 1, j 1
ki 1,1
ki 1, j 1 k i 1,n
k i 1,1
k i 1,1
k i 1,1
k n ,1
k n , j 1
k n , j 1
k n ,n
Cryptography and Network Security
137
Hill Cipher Cryptanalysis
Difficult to use frequency analysis
But vulnerable to known-plaintext attack
Give simple method to attack hill cipher under the
known-plaintext assumption?
How to attack under the chosen plaintext assumption?
The security could be greatly enhanced by combining
with some non-linear step to defeat this attack.
Cryptography and Network Security
138
Key Sizes
How may good keys?
One might naïvely think that the key size, in bits, is n2log226 or
about 4.7n2.
In fact, it is slightly less than this because not all randomly
selected matrices are usable.
A slightly less naïve view might guess that 1/2 + 1/26 of candidate
keys would be unusable, reducing the keyspace by about 54%.
In fact, determinants are not uniformly distributed, and
the key space reduction is closer to 70%.
Additionally it seems to be prudent to avoid too many zeroes in the
key matrix, since they reduce diffusion.
The net effect is that the effective keyspace of a basic
Hill cipher is about 4.64n2.
For a 5 × 5 Hill cipher, that is about 114 bits. Of course,
key search is not the most efficient known attack
Cryptography and Network Security
139
Polyalphabetic Substitution
Use more than one substitution alphabet
Makes cryptanalysis harder
since have more alphabets to guess
and flattens frequency distribution
same plaintext letter gets replaced by several
ciphertext letter, depending on which alphabet is
used
Cryptography and Network Security
140
Vigenère Cipher
Basically multiple Caesar ciphers
key is multiple letters long
K = k1 k2 ... kd
ith letter specifies ith alphabet to use
use each alphabet in turn, repeating from start after d
letters in message
Plaintext THISPROCESSCANALSOBEEXPRESSED
Keyword CIPHERCIPHERCIPHERCIPHERCIPHE
Ciphertext VPXZTIQKTZWTCVPSWFDMTETIGAHLH
Cryptography and Network Security
141
Enigma Machine
Enigma was a portable cipher machine used
to encrypt and decrypt secret messages.
a family of related electro-mechanical rotor machines
Japan commercial
German military
Cryptography and Network Security
142
Enigma Machine
Enigma encryption for two
consecutive letters —
current is passed into set of
rotors, around the reflector, and
back out through the rotors
again.
Letter A encrypts differently
with consecutive key presses,
first to G, and then to C. This is
because the right hand rotor has
stepped, sending the signal on a
completely different route.
Cryptography and Network Security
143
Enigma
the actual encipherment of a letter is performed
electrically.
When a key is pressed, the circuit is completed; current flows
through the various components and ultimately lights one of many
lamps, indicating the output letter.
Current flows from a battery through the switch controlled by the
depressed key into a fixed entry wheel. This leads into the rotor
assembly (or scrambler), where the complex internal wiring of
each rotor results in the current passing from one rotor to the next
along a convoluted path. After passing through all the rotors,
current enters the reflector, which relays the signal back out again
through the rotors and the entry wheel — this time via a different
path — and, finally, to one of the lamps (the earliest Enigma
models do not have the reflector).
Cryptography and Network Security
144
Rotors
performs a very simple type of encryption
a simple substitution cipher
Cryptography and Network Security
145
World War II Era Encryption
Devices
A few here
Sigaba (United States)
Typex (Britain)
Lorenz cipher (Germany)
Geheimfernschreiber (Germany)
For more, see
http://w1tp.com/enigma/
Cryptography and Network Security
146
One-time Pad
theoretically unbreakable (Claude Shannon)
the plaintext is combined with a random "pad" the same length as
the plaintext.
Patent by
Gilbert Vernam (AT&T) and Joseph Mauborgne
Encryption
C=PK
Decryption
P=CK
Claude Shannon's work can be interpreted as
that any information-theoretically secure cipher will be effectively
equivalent to the one-time pad algorithm. Hence one-time pads
offer the best possible mathematical security of any encryption
scheme, anywhere and anytime.
Cryptography and Network Security
147
One-time pad--cont
Drawbacks
it requires secure exchange of the one-time pad material, which
must be as long as the message
pad disposed of correctly and never reused
In practice
Generate a large number of random bits,
Exchange the key material securely between the users before
sending an one-time enciphered message,
Keep both copies of the key material for each message securely
until they are used, and
Securely dispose of the key material after use, thereby ensuring
the key material is never reused.
It requires a perfect random numbers as key
We will learn how to generate pseudo-random numbers
Cryptography and Network Security
148
Random numbers needed
If the key material is generated by a
deterministic program then it is not
actually random
should never be used in an one-time pad cipher.
If so used, the method becomes a stream cipher; these
usually employ a short key that is used to generate a
long pseudorandom stream, which is then combined
with the message using some such mechanism as those
used in one-time pads. Stream ciphers can be secure in
practice, but they cannot be absolutely secure in the
same provable sense as the one-time pad
Cryptography and Network Security
149
Stream ciphers
Stream ciphers
The most famous: Vernam cipher
Invented by Vernam, ( AT&T, in 1917)
Process the message bit by bit (as a stream)
different from the one-time pad– some call same
Simply add bits of message to random key bits
Examples
A well-known stream cipher is RC4;
others include: A5/1, A5/2, Chameleon, FISH, Helix. ISAAC,
Panama, Pike, SEAL, SOBER, SOBER-128 and WAKE.
Usage
Stream ciphers are used in applications where plaintext comes in
quantities of unknowable length - for example, a secure wireless
connection
Cryptography and Network Security
150
Simplest Stream Cipher
Key
Key
Plaintext
Ciphertext
Ciphertext
Plaintext
Cryptography and Network Security
151
Pros and Cons
Drawbacks
Need as many key bits as message, difficult in practice
(ie distribute on a mag-tape or CDROM)
Strength
Is
unconditionally secure provided key is truly random
Cryptography and Network Security
152
Key Generation
Why not to generate keystream from a
smaller (base) key?
Use some pseudo-random function to do this
Although this looks very attractive, it proves to be very
very difficult in practice to find a good pseudo-random
function that is cryptographically strong
This is still an area of much research
Cryptography and Network Security
153
Transposition Methods
Permutation of plaintext
Example
Write in a square in row, then read in column order
specified by the key
Enhance: double or triple transposition
Can reapply the encryption on ciphertext
Cryptography and Network Security
154
Cryptography and Network Security
Block Ciphers
Xiang-Yang Li
Cryptography and Network Security
155
Block Ciphers
The message is broken into blocks,
Each of which is then encrypted
(Like a substitution on very big characters - 64-bits or
more)
Cryptography and Network Security
156
Substitution and Permutation
In his 1949 paper Shannon also introduced
the idea of substitution-permutation (S-P)
networks, which now form the basis of
modern block ciphers
An
S-P network is the modern form of a substitutiontransposition product cipher
S-P networks are based on the two primitive
cryptographic operations we have seen before
Cryptography and Network Security
157
Substitution
A binary word is replaced by some other
binary word
The whole substitution function forms the
key
If use n bit words,
The key space is 2n!
Can also think of this as a large lookup
table, with n address lines (hence 2n
addresses), each n bits wide being the
output value
Will call them s-boxesCryptography and Network Security
158
Cont.
Cryptography and Network Security
159
Permutation
A binary word has its bits reordered
(permuted)
The re-ordering forms the key
If use n bit words,
The
key space is n! (Less secure than substitution)
This is equivalent to a wire-crossing in
practice
(Though is much harder to do in software)
Will call these p-boxes
Cryptography and Network Security
160
Cont.
Cryptography and Network Security
161
Substitution-permutation
Network
Shannon combined these two primitives
He called these mixing transformations
A special form of product ciphers where
S-boxes
Provide confusion of input bits
P-boxes
Provide diffusion across s-box inputs
Cryptography and Network Security
162
Confusion and Diffusion
Confusion
A technique that seeks to make the relationship between
the statistics of the ciphertext and the value of the
encryption keys as complex as possible. Cipher uses
key and plaintext.
Diffusion
A technique that seeks to obscure the statistical
structure of the plaintext by spreading out the influence
of each individual plaintext digit over many ciphertext
digits.
Cryptography and Network Security
163
Desired Effect
Avalanche effect
A characteristic of an encryption algorithm in which a
small change in the plaintext gives rise to a large
change in the ciphertext
Best: changing one input bit results in changes of
approx half the output bits
Completeness effect
where each output bit is a complex function of all the
input bits
Cryptography and Network Security
164
Practical Substitutionpermutation Networks
In practice we need to be able to decrypt
messages, as well as to encrypt them,
hence either:
Have to define inverses for each of our S & P-boxes,
but this doubles the code/hardware needed, or
Define a structure that is easy to reverse, so can use
basically the same code or hardware for both
encryption and decryption
Cryptography and Network Security
165
Feistel Cipher
Invented by Horst Feistel,
working at IBM Thomas J Watson research labs in early
70's,
The idea is to partition the input block into
two halves, l(i-1) and r(i-1),
use only r(i-1) in each round i (part) of the cipher
The function f incorporates one stage of
the S-P network, controlled by part of the
key k(i) known as the ith subkey
Cryptography and Network Security
166
Cont.
Cryptography and Network Security
167
Cont.
This can be described functionally as:
L(i) = R(i-1)
R(i) = L(i-1) f(k(i), R(i-1))
This can easily be reversed as seen in the
above diagram, working backwards through
the rounds
In practice link a number of these stages
together (typically 16 rounds) to form the
full cipher
Cryptography and Network Security
168
Data Encryption Standard
Adopted in 1977 by the National Bureau of
Standards, now the National Institute of
Standards and Technology
Data are encrypted in 64-bit blocks using a
56-bit key
The same algorithm is used for decryption.
Subject to much controversy
Cryptography and Network Security
169
History
IBM LUCIFER 60’s
Uses 128 bits key
Proposal for NBS, 1973
Adopted by NBS, 1977
Uses
only 56 bits key
Possible brute force attack
Design of S-boxes was classified
Hidden weak points in in S-Boxes?
Wiener (93) claim to be able to build a machine at
$100,00 and break DES in 1.5 days
Cryptography and Network Security
170
DES
DES encrypts 64-bit blocks of data, using
a 56-bit key
the basic process consists of:
an initial permutation (IP)
16 rounds of a complex key dependent calculation f
a final permutation, being the inverse of IP
Function f can be described as
L(i) = R(i-1)
R(i) = L(i-1) P(S( E(R(i-1)) K(i) ))
Cryptography and Network Security
171
DES
Cryptography and Network Security
172
Initial and Final Permutations
Inverse Permutations
40
8
48
16
56
24
64
32
39
7
47
15
55
23
63
31
38
6
46
14
54
22
62
30
37
5
45
13
53
21
61
29
36
4
44
12
52
20
60
28
35
3
43
11
51
19
59
27
34
2
42
10
50
18
58
26
33
1
41
9
49
17
57
25
Cryptography and Network Security
173
Function f
Cryptography and Network Security
174
Expansion Table
Expands the 32 bit data to 48 bits
Result(i)=input( array(i))
32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
Cryptography and Network Security
175
S-Boxes
S-Box is a fixed 4 by 16 array
Given 6-bits B=b1b2b3b4b5b6,
Row r=b1b6
Column c=b2b3b4b5
S(B)=S(r,c) written in binary of length 4
Cryptography and Network Security
176
Example
S-Box S1
14 4
13 1
0
15 7
4
1
2
15 11
8
3
10 6
12 5
0
7
9
5
3
8
3
10 5
0
4
14 2
13 1
10 6
14 8
13 6
2
11
15 12 9
7
4
1
7
5
14 10 0
15 12 8
2
9
11
12 11
9
3
6
Cryptography and Network Security
13
177
Permutation Table
The permutation after each round
16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25
Cryptography and Network Security
178
Subkey Generation
Given a 64 bits key (with parity-check bit)
Discard the parity-check bits
Permute the remaining bits using fixed table P1
Let C0D0 be the result (total 56 bits)
Let Ci =Shifti(Ci-1); Di =Shifti(Di-1) and Ki be
another permutation P2 of CiDi (total 56
bits)
Where cyclic shift one position left if i=1,2,9,16
Else cyclic shift two positions left
Cryptography and Network Security
179
Permutation Tables
57 49 41
33 25 17
9
14
17
11
28 15
24 1
5
6
21
10
4
26 8
1
58 50 42 34 26 18
3
10
2
59 51
23 19
12
19
11
3
16
7
27 20 13
41
52 31
37 47 55
45 33 48
43 35 27
60 52 44 36
63 55 47 39 31
23 15
2
7
62 54 47 38 30 22
30 40 51
14
6
61
53 45 37 29
44 49 39 56 34 53
21
13
5
28 20 12
46 42 50 36 29 32
4
Permutation table P1
Permutation table P2
Cryptography and Network Security
180
DES in Practice
DEC (Digital Equipment Corp. 1992) built a
chip with 50k transistors
Encrypt at the rate of 1G/second
Clock rate 250 Mhz
Cost about $300
Applications
ATM transactions (encrypting PIN and so on)
Cryptography and Network Security
181
Model
Mode of use
The way we use a block cipher
Four have been defined for the DES by ANSI in the
standard: ANSI X3.106-1983 modes of use)
Block modes
Splits messages in blocks (ECB, CBC)
Stream modes
On bit stream messages (CFB, OFB)
Cryptography and Network Security
182
Block Modes
Electronic Codebook Book (ECB)
where the message is broken into independent 64-bit
blocks which are encrypted
Ci = DESK1 (Pi)
Cipher Block Chaining (CBC)
again the message is broken into 64-bit blocks, but they
are linked together in the encryption operation with an
IV
Ci = DESK1 (PiCi-1)
C-1=IV (initial value)
Cryptography and Network Security
183
Stream Model
Cipher FeedBack (CFB)
where the message is treated as a stream of bits, added
to the output of the DES, with the result being feed
back for the next stage
Ci = Pi DESK1 (Ci-1)
C-1=IV (initial value)
Cryptography and Network Security
184
Cont.
Output FeedBack (OFB)
where the message is treated as a stream of bits, added
to the message, but with the feedback being
independent of the message
Ci = Pi Oi
Oi = DESK1 (Oi-1)
O-1=IV (initial value)
Cryptography and Network Security
185
DES Weak Keys
With many block ciphers there are some
keys that should be avoided, because of
reduced cipher complexity
These keys are such that the same sub-key
is generated in more than one round, and
they include:
Cryptography and Network Security
186
Cont.
Weak keys
The same sub-key is generated for every round
DES has 4 weak keys
Semi-weak keys
Only
two sub-keys are generated on alternate rounds
DES has 12 of these (in 6 pairs)
Demi-semi weak keys
Have four sub-keys generated
Cryptography and Network Security
187
Cont.
None of these causes a problem since they
are a tiny fraction of all available keys
However they MUST be avoided by any key
generation program
Cryptography and Network Security
188
DES Attacks
1998:
The EFF's US$250,000
DES cracking machine
contained 1,536 custom chips
and could brute force a DES key in a
matter of days —
the photo shows a DES Cracker
circuit board fitted
with several Deep Crack chips.
Cryptography and Network Security
189
DES Attacks:
The COPACOBANA
machine, built for
US$10,000 by the
Universities of Bochum and
Kiel, contains 120 low-cost
FPGAs and can perform an
exhaustive key search on
DES in 9 days on average.
The photo shows the
backplane of the machine
with the FPGAs
Cryptography and Network Security
190
Attack Faster than Brute Force
Differential cryptanalysis
was discovered in the late 1980s by Eli Biham and Adi Shamir,
although it was known earlier to both IBM and the NSA and kept
secret. To break the full 16 rounds, differential cryptanalysis
requires 247 chosen plaintexts. DES was designed to be resistant to
DC.
Linear cryptanalysis
was discovered by Mitsuru Matsui, and needs 243 known plaintexts
(Matsui, 1993); the method was implemented (Matsui, 1994), and
was the first experimental cryptanalysis of DES to be reported.
There is no evidence that DES was tailored to be resistant to this
type of attack.
Cryptography and Network Security
191
Possible Techniques for
Improving DES
Multiple enciphering with DES
Extending DES to 128-bit data paths and
112-bit keys
Extending the key expansion calculation
Cryptography and Network Security
192
Double DES?
Using two encryption stages and two keys
C=Ek2(Ek1(P))
P=Dk1(Dk2(C))
It is proved that there is no key k3 such
that
C=Ek2(Ek1(P))=Ek3(P)
But Meet-in-the-middle attack
Cryptography and Network Security
193
Meet-in-the-Middle Attack
Assume C=Ek2(Ek1(P))
Given the plaintext P and ciphertext C
Encrypt P using all possible keys k1
Decrypt C using all possible keys k2
Check the result with the encrypted plaintext lists
If found match, they test the found keys again for
another plaintext and ciphertext pair
If it turns correct, then find the keys
Otherwise keep decrypting C
Cryptography and Network Security
194
Triple DES
DES variant
Standardized in ANSI X9.17 & ISO 8732
and in PEM for key management
Proposed for general EFT standard by
ANSI X9
Backwards compatible with many DES
schemes
Uses 2 or 3 keys
Cryptography and Network Security
195
Cont.
No known practical attacks
Brute force search impossible (very hard)
Meet-in-the-middle attacks need 256
Plaintext-Ciphertext pairs per key
Popular current alternative
Cryptography and Network Security
196
IDEA:
Developed by James Massey & Xuejia Lai
at ETH originally in Zurich in 1990, then
called IPES:
X Lai, J L Massey, "A Proposal for a New Block
Encryption Standard"
in Advances in Cryptology - Eurocrypt '90, Lecture
Notes in Computer Science, vol 473, pp 389-404,
X Lai, J L Massey, S Murphy, "Markov Ciphers and
Differential Cryptanalysis"
in Advances in Cryptology - Eurocrypt '91, Lecture
Notes in Computer Science, vol 547, pp 17-38,
name changed to IDEA in 1992
Cryptography and Network Security
197
Basic Features
Encrypts 64-bit blocks using a 128-bit key
Based on mixing operations from different
(incompatible) algebraic groups
XOR, + mod 2^(16) , X mod 2^(16) +1)
On 16-bit sub-blocks, with no permutations used
IDEA is patented in Europe & US, however
non-commercial use is freely permitted
used in the public domain PGP (with agreement)
currently no attack against IDEA is known
Seem secure against differential cryptanalysis, brute
force
Cryptography and Network Security
198
Operations
Operations
XOR, Addition mod 216, multiplication mod 216 +1
Why these special mod for addition, multiplication
They do not satisfy the distributive law
They do not satisfy the associative law
Cryptography and Network Security
199
MA: multiplication/addition
Multiplication/addition
Basic block to provide diffusion
Input of MA
Two sub-blocks derived from 4 input sub-blocks, 4
sub-keys
Two other sub-keys
Output
Two sub-blocks
Needs four operations
Four operations are the minimum to provide full
diffusion
Cryptography and Network Security
200
Overview
Cryptography and Network Security
201
Cont.
IDEA encryption works as follows:
Use 8-rounds
The 64-bit data is divided into: X1 , X2 , X3 , X4
Each round
The sub-blocks are added (2,3), multiplied (1,4) with subkeys
The results are XORed [1,3] and [2,4] to 2 sub-blocks
The XOR results set as input of MA structure,
It outputs two subblocks
Results are then XORed with 2,4 and 1,3 subblocks respectively
The second and third sub-blocks are swapped
Finally new sub-keys are combined with the sub-blocks
Cryptography and Network Security
202
Sub-Keys
Total need 52=6*8+4 sub-keys
First are directly from key in order
Left shift of 25 bits, and then next 8 sub-keys
Each sub-key is a sub-block of the original key
Decryption
Much more complicated
It needs the inverse of the encryption key
For addition, multiplication
Cryptography and Network Security
203
Decryption
The process of decryption is essentially
the same as encryption
But with different selection of sub-keys
Basic Operations
K1.1^(-1 ) is the multiplicative inverse mod 2^(16) +1
-K1.2 is the additive inverse mod 2^(16)
The original operations are:
(+) bit-by-bit XOR
+ additional mod 2^(16) of 16-bit integers
* multiplication mod 2^(16) +1 (where 0 means 2^(16) )
Cryptography and Network Security
204
Decryption Sub-Keys
Round
Encryption Keys
Decryption Keys
1 K1.1 K1.2 K1.3 K1.4 K1.5 K1.6
K9.1-1 -K9.2 -K9.3 K9.4-1
K8.5 K8.6
2 K2.1 K2.2 K2.3 K2.4 K2.5 K2.6
K8.1-1 -K8.3 -K8.2 K8.4-1
K7.5 K7.6
3 K3.1 K3.2 K3.3 K3.4 K3.5 K3.6
K7.1-1 -K7.3 -K7.2 K7.4-1
K6.5 K6.6
4 K4.1 K4.2 K4.3 K4.4 K4.5 K4.6
K6.1-1 -K6.3 -K6.2 K6.4-1
K5.5 K5.6
5 K5.1 K5.2 K5.3 K5.4 K5.5 K5.6
K5.1-1 -K5.3 -K5.2 K5.4-1
K4.5 K4.6
6 K6.1 K6.2 K6.3 K6.4 K6.5 K6.6
K4.1-1 -K4.3 -K4.2 K4.4-1
K3.5 K3.6
7 K7.1 K7.2 K7.3 K7.4 K7.5 K7.6
K3.1-1 -K3.3 -K3.2 K3.4-1
K2.5 K2.6
8 K8.1 K8.2 K8.3 K8.4 K8.5 K8.6
K2.1-1 -K2.3 -K2.2 K2.4-1205
Cryptography and Network Security
K1.5 K1.6 Output K9.1 K9.2 K9.3 K9.4
K1.1-1 -K1.2 -K1.3 K1.4-1
Important Feature
The size of the sub-block
Need 216+1 be prime number
To compute the inverse for each possible subkey
So sub-block size 8 is also possible
28+1=257 is prime number
Cryptography and Network Security
206
CAST-128
By Carlisle Adams, Stafford Tavares
Defined in RFC 2144
Use key size varying from 40 to 128 bits
Structure of Feistel network
16 rounds on 64-bits data block
Four primitive operations
Addition, substration (mod 232)
Bitwise exclusive-OR
Left-circular rotation
Cryptography and Network Security
207
Skipjack and Clipper
Skipjack
used in Clipper escrowed encryption scheme(US govt)
Skipjack is a block cipher, 64-bit data
hardware only implementation
80-bit key (escrowed in 2 halves)
32 round
all design details and descriptions are classified
has been very considerable debate over its use
attack by Matt Blaze (ATT) on the LEAF component of
the Clipper protocol for secure phone communications
Cryptography and Network Security
208
Blowfish Scheme
Developed by Bruce Schneier
Fast, compact, simple and variably secure
Two basic operations: addition, XOR
Key ranges from 32 bits to 448 bits
Similar to Feistel scheme
The sub-key and s-boxes are complicated
So not suitable when key changes often
Function g is very simple, unlike DES
Cryptography and Network Security
209
RC5
Developed by R. Rivest
Suitable for hardware or software
Fast, simple, low memory, data-dependent rotations
Adaptable to processors of different word length
A family of algorithms determined by word length,
number of rounds, size of secret key
Decryption and encryption are not the same
With little variations
Primitive operations
Addition, XOR, left circular rotation
Cryptography and Network Security
210
Characteristics
Key features of advanced sym block cipher
Variable key length
Mixed operators
Data dependent rotation
Key dependent rotation
Key dependent S-boxes
Lengthy key schedule algorithm
Variable function F
Variable of number of rounds
Operation on both halved data each round
Cryptography and Network Security
211
AES
Advanced Encryption Standard (Rijndael)
key size and the block size may be chosen to be any of 128, 192, or 256
bits (later only key, block fixed 128)
Rijndael has a variable number of rounds. Not counting an extra round
performed at the end of encipherment with one step omitted, the
number of rounds in Rijndael is:
9 if both the block and the key are 128 bits long.
11 if either the block or the key is 192 bits long, and neither of
them is longer than that.
13 if either the block or the key is 256 bits long.
Three big blocks
first perform an Add Round Key step (XORing a subkey with the
block) by itself,
then regular rounds noted above,
the final round with the Mix Column step
Cryptography and Network Security
212
Advanced Encryption
Standard
Not “American”
Encryption Standard
a.k.a
Lab #1
Cryptography and Network Security
213
How was AES created?
AES competition
Started in January 1997 by NIST
4-year cooperation between
U.S. Government
Private Industry
Academia
Why?
Replace 3DES
Provide an unclassified, publicly disclosed encryption algorithm,
available royalty-free, worldwide
Cryptography and Network Security
214
The Finalists
MARS
IBM
RSA Laboratories
Joan Daemen (Proton World International) and
Vincent Rijmen (Katholieke Universiteit Leuven)
RC6
Rijndael
Serpent
Ross Anderson (University of Cambridge),
Eli Biham (Technion), and
Lars Knudsen (University of California San Diego)
Twofish
Bruce Schneier, John Kelsey, and Niels Ferguson (Counterpane, Inc.),
Doug Whiting (Hi/fn, Inc.),
David Wagner (University of California Berkeley), and
Chris Hall (Princeton University)
Wrote the book
on crypto
Cryptography and Network Security
215
Evaluation Criteria
(in order of importance)
Security
Resistance to cryptanalysis, soundness of math,
randomness of output, etc.
Cost
Computational efficiency (speed)
Memory requirements
Algorithm / Implementation Characteristics
Flexibility, hardware and software suitability, algorithm
simplicity
Cryptography and Network Security
216
Results
Cryptography and Network Security
217
Results
Cryptography and Network Security
218
The winner: Rijndael
AES adopted a subset of Rijndael
Rijndael supports more block and key sizes
Cryptography and Network Security
219
Finite Fields
AES uses the finite field GF(28)
b7x7 + b6x6 + b 5x5 + b4x4 + b3x3 + b 2x2 + b1x + b0
{b7, b6, b5, b4, b3, b2, b1, b0}
Byte notation for the element: x6 + x5 + x + 1
{01100011} – binary
{63} – hex
Has its own arithmetic operations
Addition
Multiplication
Cryptography and Network Security
220
Finite Field Arithmetic
Addition (XOR)
(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2
{01010111} {10000011} = {11010100}
{57} {83} = {d4}
Multiplication is tricky
Cryptography and Network Security
221
Finite Field Multiplication ()
(x6 + x4 + x2 + x +1) (x7 + x +1) =
x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x2 + x + x6 + x4 + x2 + x +1
These cancel
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 +1
and
x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 +1 modulo ( x8 + x4 + x3 + x +1)
= x7 + x6 +1.
Irreducible Polynomial
Cryptography and Network Security
222
Efficient Finite field Multiply
There’s a better way
xtime() – very efficiently multiplies its input by {02}
Multiplication by higher powers can be
accomplished through repeat application
of xtime()
Cryptography and Network Security
223
Efficient Finite field Multiply
Example: {57} {13}
{57} {02} = xtime({57}) = {ae}
{57} {04} = xtime({ae}) = {47}
{57} {08} = xtime({47}) = {8e}
{57} {10} = xtime({8e}) = {07}
{57} {13} = {57} ({01} {02} {10})
= ({57} {01}) ({57} {02}) ({57} {10})
= {57} {ae} {07}
= {fe}
Cryptography and Network Security
224
AES parameters
Nb – Number of columns in the State
For AES, Nb = 4
Nk – Number of 32-bit words in the Key
For AES, Nk = 4, 6, or 8
Nr – Number of rounds
(function of Nb and Nk)
For AES, Nr = 10, 12, or 14
Cryptography and Network Security
225
AES methods
Convert to state array
Transformations (and their inverses)
AddRoundKey
SubBytes
ShiftRows
MixColumns
Key Expansion
Cryptography and Network Security
226
Convert to State Array
Input block:
0
0
4
8
12
1
5
9
13
1 2 2 6 310 414 5
3
7
11 15
S0,0 S0,1 S0,2 S0,3
=
6
7
8
S1,0 S1,1 S1,2 S1,3
9 10 11 12 13 14 15
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
Cryptography and Network Security
227
AddRoundKey
XOR each byte of the round key with its
corresponding byte in the state array
XOR
S0,1
S0,0 S0,1 S0,2 S0,3
S1,0 S
S1,1
1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S2,1
S3,0 S3,1 S3,2 S3,3
S3,1
R0,1
R0,0 R0,1 R0,2 R0,3
1,1 R1,2 R1,3
R1,0 R
R1,1
R2,0 R2,1 R2,2 R2,3
R2,1
R3,0 R3,1 R3,2 R3,3
R3,1
S’0,1
S’0,0 S’0,1 S’0,2 S’0,3
S’1,0S’
S’1,1
1,1 S’1,2 S’1,3
S’2,0 S’2,1 S’2,2 S’2,3
S’2,1
S’3,0 S’3,1 S’3,2 S’3,3
S’3,1
Cryptography and Network Security
228
SubBytes
Replace each byte in the state array with
its corresponding value from the S-Box
00 44 88 CC
11
55 99 DD
55
22 66 AA EE
33 77 BB FF
Cryptography and Network Security
229
ShiftRows
Last three rows are cyclically shifted
S0,0 S0,1 S0,2 S0,3
S1,0
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2
S3,0 S3,1 S3,2 S3,3
Cryptography and Network Security
230
MixColumns
Apply MixColumn transformation to each
column
S’0,c = ({02} SMixColumns()
0,c) ({03} S1,c) S2,c S3,c
S0,0
S0,1
S’0,1
S S’S1,c =SS0,c ({02} S1,c) ({03} S2,c
S’ ) SS
’ 3,cS’
0,1
0,2
0,3
0,0
0,1
0,2
S’0,3
S1,0 S
S1,1
S’1,0S’
S’
1,1S’S1,2=SS
1,3 S
1,1 )S’1,2 S’1,3
({02}
S
)
({03}
S1,1
2,c
0,c
1,c
2,c
3,c
S2,0 S2,1 S2,2 S2,3
S’2,0 S’2,1 S’2,2 S’2,3
S3,0 S3,1 S3,2 S3,3
S’3,0 S’3,1 S’3,2 S’3,3
S2,1S’
3,c
S3,1
= ({03} S0,c) S1,c S2,c ({02} S’S2,13,c
S’3,1
Cryptography and Network Security
231
Key Expansion
Expands the key material so that each
round uses a unique round key
Generates Nb(Nr+1) words
Filled with just
the key
Filled with a combination of
the previous work and the
one Nk positions earlier
Cryptography and Network Security
232
Encryption
byte state[4,Nb]
state = in
AddRoundKey(state, keySchedule[0, Nb-1])
for round = 1 step 1 to Nr–1 {
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, keySchedule[round*Nb, (round+1)*Nb-1])
Prevents
an
attacker
from
First
and
last
operations
}
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, keySchedule[Nr*Nb, (Nr+1)*Nb-1])
even beginning
to key
encrypt or
involve the
decrypt without the key
out = state
Cryptography and Network Security
233
Decryption
byte state[4,Nb]
state = in
AddRoundKey(state, keySchedule[Nr*Nb, (Nr+1)*Nb-1])
for round = Nr-1 step -1 downto 1 {
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, keySchedule[round*Nb, (round+1)*Nb-1])
InvMixColumns(state)
}
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, keySchedule[0, Nb-1])
out = state
Cryptography and Network Security
234
Encrypt and Decrypt
Encryption
Decryption
AddRoundKey
AddRoundKey
SubBytes
ShiftRows
MixColumns
AddRoundKey
InvShiftRows
InvSubBytes
AddRoundKey
InvMixColumns
SubBytes
ShiftRows
AddRoundKey
InvShiftRows
InvSubBytes
AddRoundKey
Cryptography and Network Security
235
Cryptography and Network
Security
Public key system
Xiang-Yang Li
Cryptography and Network Security
236
Public Key Encryption
Two difficult problems
Key distribution under conventional encryption
Digital signature
Diffie and Hellman, 1976
Astonishing
breakthrough
One key for encryption and the other related key for
decryption
It is computationally infeasible to determine the
decryption key using only the encryption key and the
algorithm
Cryptography and Network Security
237
Public Key Cryptosystem
Essential steps of public key cryptosystem
Each end generates a pair of keys
One for encryption and one for decryption
Each system publishes one key, called public key, and
the companion key is kept secret
It A wants to send message to B
Encrypt it using B’s public key
When B receives the encrypted message
It decrypt it using its own private key
Cryptography and Network Security
238
Applications of PKC
Encryption/Decryption
The sender encrypts the message using the receiver’s
public key
Q: Why not use the sender’s secret key?
Digital signature
The sender signs a message by encrypt the message or a
transformation of the message using its own private key
Key exchange
Two
sides cooperate to exchange a session key,
typically for conventional encryption
Cryptography and Network Security
239
Conditions of PKC
Computationally easy
To generate public and private key pair
To encrypt the message using encryption key
To decrypt the message using decryption key
Computational infeasible
To compute the private key using public key
To recover the plaintext using ciphertext and public key
The encryption and decryption can be
applied in either order
Cryptography and Network Security
240
One Way Function
PKC boils down to one way function
Maps a domain into a range with unique inverse
The calculation of the function is easy
The calculation of the inverse is infeasible
Easy
The problem can be solved in polynomial time
Infeasible
The effort to solve it grows faster than polynomial time
For example: 2n
It requires infeasible for all inputs, not just worst case
Cryptography and Network Security
241
Trapdoor One-way Function
Trapdoor one way function
Maps a domain into a range with unique inverse
Y=fk(X)
The calculation of the function is easy
The calculation of the inverse is infeasible if the key is
not known
The calculation of the inverse is easy if the key is
known
Cryptography and Network Security
242
Possible Attacks
Brute force
Use large keys
Trade-off: speed (not linearly depend on key size)
Confined to small data encryption: signature, key
management
Compute the private key from public key
Not proven that is not feasible for most protocols!
Probable message attack
Encrypt all possible messages using encryption key
Compare with the ciphertext to find the matched one!
If data is small, feasible, regardless of key size of PKC
Cryptography and Network Security
243
History
http://www.research.att.com/~smb/nsam-
160/
British
National Security Action Memorandum
160
Kennedy Nuclear Weapon
http://www.research.att.com/~smb/nsam-160/pg1.html
Cryptography and Network Security
244
RSA Algorithm
R. Rivest, A. Shamir, L. Adleman (1977)
James Ellis came up with the idea in 1970, and proved that it was
theoretically possible. In 1973, Clifford Cocks a British
mathematician invented a variant on RSA; a few months later,
Malcom Williamson invented a Diffie-Hellman analog
Only revealed till 1997
Patent expired on September 20, 2000.
Block cipher using integers 0~n-1
Thus block size k is less than log2n
Algorithm:
Encryption: C=Me mod n
Decryption: M=Cd mod n
Both sender and the receiver know n
Cryptography and Network Security
245
RSA (public key encryption)
Alice wants Bob to send her a message. She:
selects two (large) primes p, q, TOP SECRET,
computes n = pq and (n) = (p-1)(q-1),
(n) also TOP SECRET,
selects an integer e, 1 < e < (n), such that
gcd(e, (n)) = 1,
computes d, such that de 1 (mod (n)),
d also TOP SECRET,
gives public key (e, n), keeps private key (d, n).
Cryptography and Network Security
246
Requirements
Possible to find e and d such that
M=Mde mod n for all message M
Easy to conduct encryption and decryption
Infeasible to compute d
Given n and e
Cryptography and Network Security
247
RSA Example
1.
2.
3.
4.
5.
6.
7.
Select primes: p=17 & q=11
Compute n = pq =17×11=187
Compute ø(n)=(p–1)(q1)=16×10=160
Select e : gcd(e,160)=1; choose e=7
Determine d: de=1 mod 160 and d <
160 Value is d=23 since 23×7=161=
10×160+1
Publish public key KU={7,187}
Keep secret private key KR={23,17,11}
Cryptography and Network Security
248
RSA Example cont
sample RSA encryption/decryption is:
given message M = 88 (nb. 88<187)
encryption:
C = 887 mod 187 = 11
decryption:
M = 1123 mod 187 = 88
Cryptography and Network Security
249
Key Generation
Recall Euler Theorem
a(n)+1
=a mod n for all 0<a<n and gcd(a,n)=1
Then ed=1 mod (n) is sufficient to make algorithm
correct (need more proofs)
RSA chooses the following
Integer n=pq for two primes p and q
Select e, such that gcd(e, (n))=1
Compute the inverse of e mod (n)
The result is set as d
Cryptography and Network Security
250
Key Generation
The prime numbers p and q must be
sufficiently large
They are chosen by applying primality testing of
randomly chosen large numbers
About n/ln n prime numbers less than n
Implies needs to check about 2ln n random numbers
to find 2 primes numbers around n
Compute n=pq, keep p and q secret!
Select random number e
Test gcd(e, (n))=1, and get d if equation holds
Cryptography and Network Security
251
Exponentiation
can use the Square and Multiply Algorithm
a fast, efficient algorithm for exponentiation
concept is based on repeatedly squaring base
and multiplying in the ones that are needed to
compute the result
look at binary representation of exponent
only takes O(log2 n) multiples for number n
eg. 75 = 74.71 = 3.7 = 10 mod 11
eg. 3129 = 3128.31 = 5.3 = 4 mod 11
Cryptography and Network Security
252
Exponentiation
Cryptography and Network Security
253
More on Exponention (PGP)
To compute Cd mod n, we compute
Cd mod p and
Cd mod q
Remember that the receiver could keep p,q
Then Chinese Remainder Theorem to find
Cd mod n
Cryptography and Network Security
254
Security of RSA
Brute force: try all possible private keys
Factoring integer n, then know (n)
Not proven to be NPC
Determine (n) directly without factoring
Equivalent to factoring! (1996)
Determine d directly without knowing (n)
Currently appears as hard as factoring
But not proven, so it may be easier!
Cryptography and Network Security
255
Practical Considerations
Testing p, q using probability first, then
deterministic methods
A good random number generator is needed for p,q
'random' and 'unpredictable'
Primes p and q should be in similar scale
Both p-1 and q-1 should have large prime factor
The gcd(p-1,q-1) should be small
The encryption key e = 2 should not be used
The decryption key d should larger then n1/4
RSA is much slower than symmetric cryptosystems.
In practice, typically encrypts a secret message with a symmetric
algorithm, encrypts the (comparatively short) symmetric key with
RSA, and transmits both the RSA-encrypted symmetric key and the
symmetrically-encrypted message to Alice.
Cryptography and Network Security
256
Fixed point of RSA
How many m such that
me=m mod n assume that gcd(m, n)=1
It is same as me-1=1 mod n
Thus, me-1=1 mod p and me-1=1 mod q
Solutions gcd(e-1,p-1)*gcd(e-1,q-1)
Need more proofs.
Cryptography and Network Security
257
Cyclic Attack
Compute me mod n, me2 mod n, me3 mod n…till it
reaches some message readable.
Need period large
Let r be the largest prime of p-1, L be the largest
prime of r-1
Then period is at least L with high probability
Implies that we often need find a large prime x
Based on this, find a large prime of y=kx+1 format (by trying
k=2,3,…)
Based on y, then find a large prime p=t y+1 format
Try difference values for t=2,3,4…
Cryptography and Network Security
258
How to deal with p, q
Delete them securely
Or used for speed-up calculation from CRT
Compute Me mod p and Me mod q
Then find using Me mod n based on CRT
Cryptography and Network Security
259
Timing Attacks
Keep track of how long a computer takes to
decrypt a message!
Paul Kocher, 1995, Dec-7
Stunning attack strategy and cipher only attack!
Guessing the key bit by bit
Countermeasures (Rivest 11 Dec 1995)
Constant exponentiation time
Random delay
Blinding (add a random number for encryption and
decryption)
Cryptography and Network Security
260
Chosen Ciphertext Attack
Collect ciphertext c (send to Alice), want to find m=cd
mod n
Attacker chooses random r
Compute x= re mod n; y=xc mod n; and t= r-1 mod n
Attacker gets Alice to sign y with private key using
RSA: yd mod n
That is why not use the same key for encryption and digital signature
Alice sends u= yd mod n to Attacker
Attacker then computes tu mod nm
Cryptography and Network Security
261
Other attacks on RSA
Comprised decryption key
If the private key d (for decryption of received
ciphertext) of a user is comprised, then the user has to
reselect n and e and d
It cannot use the old number n to produce the key-pairs!
Otherwise attacker already can factor n almost surely!
The number n can only be used by one
person
If two user uses the same n, even they do not know the
factoring of n, they still could figure out the factoring of
n with probability almost one.
Similar as above
Cryptography and Network Security
262
Bit security of RSA
Given ciphertext C,
We may want to find the last bit of M, denoted by
parity(C)
We may want to find if M>n/2, denoted by half(C)
We may want to find all bits of M
The above three attacks are the same!
If we can solve one, we can solve the other two!
Cryptography and Network Security
263
Other Public Key Systems
Rabin Cryptosystem
Decryption is not unique
Elgamal Cryptosystem
Expansion of the plaintext (double)
Knapsack System
Already broken
Elliptic Curve System
If
directly implement Elgamal on elliptic curve
Expansion of plaintext by 4; Restricted plaintext
Menezes-Vanston system is more efficient
Cryptography and Network Security
264
Rabin Cryptosystem
Procedure
Let n=pq and p=3 mod 4, q=3 mod 4
Publish n, and a number b<n
For message m
C=m(m+b) mod n
The receiver decrypts ciphertext C
(b2/4+C)1/2-b/2
Cryptography and Network Security
265
Analysis
For receiver, need solve equation
x2+xb=C
mod n
Let x1=x+b/2, c=b2/4+C, then need
Solve x12 =c mod n
Chinese Remainder Theorem implies that
x12 =c mod p
x12 =c mod q
When p=3 and q=3 mod 4
Solution x1=c(p+1)/4 mod p and x1=c(q+1)/4 mod q
Then Chinese Remainder Theorem again to combine
solution
Cryptography and Network Security
266
Security
Breaking it < factoring n
Secure against
Chosen plaintext attack
Not secure against
Chosen ciphertext attack
Decoding produces three false results in addition to the correct
one, so that the correct result must be guessed. This is the major
disadvantage of the Rabin cryptosystem and one of the factors
which have prevented it from finding widespread practical use.
It has been proven that decoding the Rabin cryptosystem is
equivalent to the integer factorization problem, which is rather
different than for RSA.
Cryptography and Network Security
267
Dealing with 4 solutions
By adding redundancies, for example, the
repetition of the last 64 bits, the system
can be made to produce a single root.
If this technique is applied, the proof of
the equivalence with the factorization
problem fails.
Cryptography and Network Security
268
ElGamal Cryptosystem
Based on Discrete Logarithm
Find unique integer a such that gx=y mod p
Here x is a primitive element in Zp, p is prime
Procedure
Make
p, g, y public, keep x secret
Encryption:
Ek(m)=(gk mod p, m y k mod p)
Decryption
Dk(y1,y2)=y2(y1x)-1 mod p
Cryptography and Network Security
269
Security of ElGamal
ElGamal is a simple example of a semantically
secure asymmetric key encryption algorithm
(under reasonable assumptions).
ElGamal's security rests, in part, on the difficulty
of solving the discrete logarithm problem in G.
Specifically, if the discrete logarithm problem could be solved
efficiently, then ElGamal would be broken. However, the security
of ElGamal actually relies on the so-called Decisional DiffieHellman (DDH) assumption. This assumption is often stronger
than the discrete log assumption, but is still believed to be true for
many classes of groups.
Cryptography and Network Security
270
Semantic Security
Semantic security is a widely-used definition for security
in an PKS.
For a cryptosystem to be semantically secure, it must be infeasible
for a computationally-bounded adversary to derive significant
information about a message (plaintext) when given only its
ciphertext and the corresponding public encryption key.
Semantic security considers only the case of a "passive"
attacker, i.e., one who observes ciphertexts and generates
chosen ciphertexts using the public key
Indistinguishability definition is used more
commonly than the original definition of semantic
security.
Cryptography and Network Security
271
Indistinguishability: semantic
security.
Indistinguishability under Chosen Plaintext Attack (IND-CPA) is
commonly defined by the following game:
A probabilistic polynomial time-bounded adversary is given a public key, which it
may use to generate any number of ciphertexts (within polynomial bounds).
The adversary generates two equal-length messages m0 and m1, and transmits them
to a challenge oracle along with the public key.
The challenge oracle selects one of the messages by flipping a uniformly-weighted
coin, encrypts the message under the public key, and returns the resulting ciphertext
c to the adversary.
The underlying cryptosystem is IND-CPA (and thus semantically
secure under chosen plaintext attack) if
the adversary cannot determine which of the two messages was chosen by the
oracle, with probability significantly greater than 1 / 2 (the success rate of random
guessing).
a semantically secure encryption scheme must by definition be
probabilistic, possessing a component of randomness; if this were
not the case, the adversary could simply compute the deterministic
encryption of m0 and m1 and compare these encryptions with the
returned ciphertext c to successfully guess the oracle's choice.
Cryptography and Network Security
272
Deal with deterministic PKS
RSA, can be made semantically secure
(under stronger assumptions) through the
use of random encryption padding schemes
such as Optimal Asymmetric Encryption
Padding (OAEP).
ElGamal scheme is semantically secure
Cryptography and Network Security
273
Bit security of Discrete Log
Given gx=y mod p
We may want to find the value of x
Find some bits of x
Assume that p-1 = 2st
We
can find the last s bits of x for sure
But to find the other bits of x is same as to find all bits
of x!
Example, the last bit of x is
0 y is QR iff y(p-1)/2=1 mod p
1 y is NQR iff y(p-1)/2=-1 mod p
Cryptography and Network Security
274
DH Assumption
Consider a cyclic group G of order q. The DDH
assumption states that,
given (g,ga,gb) for a randomly-chosen generator g and random ,
the value gab "looks like" a perfectly random element of G.
This intuitive notion is formally stated by saying
that the following two ensembles are
computationally indistinguishable:
(g,ga,gb,gab), where g,a,b are chosen at random as
described above (this input is called a "DDH tuple");
(g,ga,gb,gc), where g,a,b are chosen at random and c is
chosen at random.
Diffie-Hellman problem
computing gab from (g,ga,gb)
Cryptography and Network Security
275
Knapsack Cryptosystem
Based on subset sum problem
Given a set, find a subset with half summation value
It is NPC problem generally
Superincreasing set if si>j<isj
The subset problem over superincreasing
set can be solved in polynomial time!
Been broken by Shamir, 1984
Using
integer programming tech by Lenstra
Cryptography and Network Security
276
Solve Subset Problem
Let T be the half summation, t=T;
For i=n downto 1 do
If tsi then
t=t-si
Set xi=1
Else xi=0
If xisi=T then (x1, x2,… xn) is the solution
Else, there is no solution
Cryptography and Network Security
277
Knapsack System
Procedure
Select a superincreasing set s
Let p be prime larger than set summation of s,
Select integer a, keep s, a, p secret
Make t=(as1, as2,…asn) mod p public
Encryption
Ciphertext C = E(x1,x2,…xn)=xiti mod p
Decryption
Solve the subset summation problem (s, a-1C mod p)
Cryptography and Network Security
278
Elliptic Curve Cryptography
majority of public-key crypto (RSA, D-H)
use either integer or polynomial arithmetic
with very large numbers/polynomials
imposes a significant load in storing and
processing keys and messages
an alternative is to use elliptic curves
offers same security with smaller bit sizes
Cryptography and Network Security
279
Real Elliptic Curves
an elliptic curve is defined by an equation in
two variables x & y, with coefficients
consider a cubic elliptic curve of form
y2
= x3 + ax + b
where x,y,a,b are all real numbers
also define zero point O
have addition operation for elliptic curve
geometrically
sum of Q+R is reflection of intersection
R
Cryptography and Network Security
280
Real Elliptic Curve Example
Cryptography and Network Security
281
Finite Elliptic Curves
Elliptic curve cryptography uses curves
whose variables & coefficients are finite
have two families commonly used:
prime curves Ep(a,b) defined over Zp
use integers modulo a prime p
best in software
binary curves E2m(a,b) defined over GF(2n)
use polynomials with binary coefficients
best in hardware
Cryptography and Network Security
282
Elliptic Curve Cryptography
ECC addition is analog of modulo multiply
ECC repeated addition is analog of modulo
exponentiation
need “hard” problem equiv to discrete log
Q=kP, where Q,P belong to a prime curve
is “easy” to compute Q given k,P
but “hard” to find k given Q,P
known as the elliptic curve logarithm problem
Certicom example: E23(9,17)
Cryptography and Network Security
283
ECC Diffie-Hellman
can do key exchange analogous to D-H
users select a suitable curve Ep(a,b)
select base point G=(x1,y1) with large order
n s.t. n*G=O
A & B select private keys nA<n, nB<n
compute public keys: PA=nA×G, PB=nB×G
compute shared key: K=nA×PB, K=nB×PA
same since K=nA×nB×G
Cryptography and Network Security
284
ECC Encryption/Decryption
several alternatives, will consider simplest
must first encode any message M as a point
on the elliptic curve Pm
select suitable curve & point G as in D-H
each user chooses private key nA<n
and computes public key PA=nA×G
to encrypt Pm : Cm={kG, Pm+k PA}, k
random
decrypt Cm compute:
Pm+kPA–nA(kG) = Pm+k(nAG)–nA(kG) = Pm
Cryptography and Network Security
285
ECC Security
relies on elliptic curve logarithm problem
fastest method is “Pollard rho method”
compared to factoring, can use much
smaller key sizes than with RSA etc
for equivalent key lengths computations
are roughly equivalent
hence for similar security ECC offers
significant computational advantages
Cryptography and Network Security
286
Cryptography and Network
Key Management and generation
Xiang-Yang Li
Cryptography and Network Security
287
Key Exchange
Public key systems are much slower than
private key system
Public key system is then often for short data
Signature, key distribution
Key distribution
One party chooses the key and transmits it to other user
Key agreement
Protocol such two parties jointly establish secret key
over public communication channel
Key is the function of inputs of two users
Cryptography and Network Security
288
Distribution of Public Keys
can be considered as using one of:
Public announcement
Publicly available directory
Public-key authority
Public-key certificates
Cryptography and Network Security
289
Public Key Management
Simple one: publish the public key
Such as newsgroups, yellow-book, etc.
But it is not secure, although it is convenient
Anyone can forge such a announcement
Ex: user B pretends to be A, and publish a key for A
Then all messages sent to A, readable by B!
Let trusted authority maintain the keys
Need to verify the identity, when register keys
User can replace old keys, or void old keys
Cryptography and Network Security
290
Possible Attacks
Observe all messages over the channel
So assume that all plaintext messages are available to
all
Save messages for reuse later
So
have to avoid replay attack
Masquerade various users in the network
So have to be able to verify the source of the message
Cryptography and Network Security
291
Public Announcement
users distribute public keys to recipients
or broadcast to community at large
eg. append PGP keys to email messages or post to news
groups or email list
major weakness is forgery
anyone can create a key claiming to be someone else
and broadcast it
until forgery is discovered can masquerade as claimed
user
Cryptography and Network Security
292
Publicly Available Directory
can obtain greater security by registering
keys with a public directory
directory must be trusted with properties:
contains {name,public-key} entries
participants register securely with directory
participants can replace key at any time
directory is periodically published
directory can be accessed electronically
still vulnerable to tampering or forgery
Cryptography and Network Security
293
Public-Key Authority
improve security by tightening control over
distribution of keys from directory
has properties of directory
and requires users to know public key for
the directory
then users interact with directory to
obtain any desired public key securely
does
require real-time access to directory when keys are
needed
Cryptography and Network Security
294
Public-Key Authority
Cryptography and Network Security
295
Cont.
More advanced distribution
A sends request-for-key(B) to authority with timestamp, that is, Ida|Idb|Time
Authority replies with key(B) (encrypted by its private
key), that is EKTta(KUb| Ida|Idb|Time)
A initiates a message to B, including a random number
Na, its IDA
B then ask authority to get key(A)
B sends A (encrypted by A’s public key) Na and Nb
A then replies B Nb encrypted by B’s public key
Cryptography and Network Security
296
Cont.
In above scheme, the authority is
bottleneck
New approach: certificate
Any user can read certificate, determine name and
public key of the certificate’s owner
Any user can verify the authority of certificate
Only the authority can create and update certificate
Any user can verify the time-stamp of certificate
The certificate is
CA=EKRauth[T,IDA, KUA]
Time-stamp is to avoid reuse of voided key
Cryptography and Network Security
297
Public-Key Certificates
certificates allow key exchange without real-time access to
public-key authority
a certificate binds identity to public key
usually with other info such as period of validity, rights of use etc
with all contents signed by a trusted Public-Key or
Certificate Authority (CA)
can be verified by anyone who knows the public-key
authorities public-key
To validate the certificate, we need another certificate, one
that matches the Issuer (of CA) in the first certificate.
Then we take the RSA public key from the second (CA)
certificate, use it to decode the signature on the first
certificate to obtain an MD5 hash, which must match an
actual MD5 hash computed over the rest of the certificate.
Cryptography and Network Security
298
X.509
The structure of a X.509 v3 digital certificate is as follows:
Certificate
Version
Serial Number
Algorithm ID
Issuer
Validity
Not Before
Not After
Subject
Subject Public Key Info
Public Key Algorithm
Subject Public Key
Issuer Unique Identifier (Optional)
Subject Unique Identifier (Optional)
Extensions (Optional)
...
Certificate Signature Algorithm
Certificate Signature
Cryptography and Network Security
299
Sample Certificate
Certificate:
Data: Version: 1 (0x0)
Serial Number: 7829 (0x1e95)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=ZA, ST=Western Cape, L=Cape Town, O=Thawte Consulting cc, OU=Certification Services
Division, CN=Thawte Server CA/[email protected]
Validity
Not Before: Jul 9 16:04:02 1998 GMT
Not After : Jul 9 16:04:02 1999 GMT
Subject: C=US, ST=Maryland, L=Pasadena, O=Brent Baccala, OU=FreeSoft,
CN=www.freesoft.org/[email protected]
Subject Public Key Info: Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit): 00:b4:31:98:0a:c4:bc:62:c1:88:aa:dc:b0:c8:bb:
33:35:19:d5:0c:64:b9:3d:41:b2:96:fc:f3:31:e1: 66:36:d0:8e:56:12:44:ba:75:eb:e8:1c:9c:5b:66:
70:33:52:14:c9:ec:4f:91:51:70:39:de:53:85:17: 16:94:6e:ee:f4:d5:6f:d5:ca:b3:47:5e:1b:0c:7b:
c5:cc:2b:6b:c1:90:c3:16:31:0d:bf:7a:c7:47:77: 8f:a0:21:c7:4c:d0:16:65:00:c1:0f:d7:b8:80:e3:
d2:75:6b:c1:ea:9e:5c:5c:ea:7d:c1:a1:10:bc:b8: e8:35:1c:9e:27:52:7e:41:8f
Exponent: 65537 (0x10001)
Signature Algorithm: md5WithRSAEncryption
93:5f:8f:5f:c5:af:bf:0a:ab:a5:6d:fb:24:5f:b6:59:5d:9d:
92:2e:4a:1b:8b:ac:7d:99:17:5d:cd:19:f6:ad:ef:63:2f:92:
ab:2f:4b:cf:0a:13:90:ee:2c:0e:43:03:be:f6:ea:8e:9c:67:
d0:a2:40:03:f7:ef:6a:15:09:79:a9:46:ed:b7:16:1b:41:72:
0d:19:aa:ad:dd:9a:df:ab:97:50:65:f5:5e:85:a6:ef:19:d1:
5a:de:9d:ea:63:cd:cb:cc:6d:5d:01:85:b5:6d:c8:f3:d9:f7:
8f:0e:fc:ba:1f:34:e9:96:6e:6c:cf:f2:ef:9b:bf:de:b5:22: 68:9f
Cryptography and Network Security
300
Security
In 2005, Arjen Lenstra and Benne de
Weger demonstrated "how to use hash
collisions to construct two X.509
certificates that contain identical
signatures and that differ only in the
public keys," achieved using a collision
attack on the MD5 hash function
See
http://www.win.tue.nl/~bdeweger/Colliding
Certificates/ddl-full.pdf
Cryptography and Network Security
301
Public-Key Certificates
Cryptography and Network Security
302
Public-Key Distribution of Secret
Keys
use previous methods to obtain public-key
can use for secrecy or authentication
but public-key algorithms are slow
so usually want to use private-key
encryption to protect message contents
hence need a session key
have several alternatives for negotiating a
suitable session
Cryptography and Network Security
303
Simple Secret Key Distribution
proposed by Merkle in 1979
A generates a new temporary public key pair
A sends B the public key and their identity
B generates a session key K sends it to A encrypted
using the supplied public key
A decrypts the session key and both use
problem is that an opponent can intercept
and impersonate both halves of protocol
Cryptography and Network Security
304
Secret key Distribution
Simple secret key distribution
A generates KUA and KRA, sends KUA to B
B generates a secret key ks
B sends ks to A using A’s public key KUA
A decrypts the message to get the secret key ks
To get more security, the public/private
keys can be regenerated when needed
But vulnerable to the active attack!
Attacker E can compromise the communication
between A and B as follows
Cryptography and Network Security
305
Cont.
Attacking
A generates KUA and KRA, sends IDA, KUA to B
E intercepts the message, transmits IDA, KUE to B
B generates a secret key ks
B sends ks to A using A’s “public key” KUE
E intercepts the message, decrypt it and get ks
E sends A the message Ks, encrypted by KUA
A decrypts the message to get the secret key ks
Now E knows Ks, but A, B are unaware of it
Cryptography and Network Security
306
Secret Key Distribution
So need confidentiality and authentication
A and B need to use a secure method to exchange their
public keys
Schemes
A initiates
a message to B, EKUB(Na,IDa)
B replies it with EKUA(Na,Nb)
A then replies it with EKUB(Nb)
A sends B the message EKUB (EKRA(Ks))
Security
The first 3 steps are used to assure that A is A, B is B
Cryptography and Network Security
307
Public-Key Distribution of Secret
Keys
if have securely exchanged public-keys:
Cryptography and Network Security
308
Key Predistribution
Trusted Authority (TA) generates keys for
all pair of users and transmits to them
Large overhead (for TA and user)
Blom Scheme
Keys
are chosen from a finite field Zp
P is public prime number
TA transmits k+1 elements of Zp to each user over
secure channel
Secure condition: any set of at most k users (not U,V)
can not determine any information about Ku,v
Cryptography and Network Security
309
Blom Scheme
Scheme (when k=1)
Each user u has distinct element ru from Zp
TA choose a,b,c and defines
f(x,y)=a+b(x+y)+cxy mod p
For each u, TA computes
gu(x)=f(x, ru) mod p
TA transmits gu(x) to user u
Two users u and v compute the common key
f(ru, rv)= a+b(ru + rv)+c ru rv mod p
Here f(ru, rv)= gv(ru)= gu(rv)
Cryptography and Network Security
310
Security of Blom Scheme
Less than k users can not determine keys
However, more than k users can compute
any keys
Solving equations to get a,b,c for k=1
Generally
Function f(x,y)=Sum ai,jxiyj mod p
Here ai,j=aj,i
Cryptography and Network Security
311
Diffie-Hellman Key Predist.
Computationally secure
if discrete logarithm is intractable
Scheme
Assume prime number p public and an integer c public
Each user u has secret component au
User u computes bu=c au mod p
TA certifies it by computing
(ID(u), bu, sigTA(ID(u), bu))
The common key of two users u and v is
K=c au av mod p
Cryptography and Network Security
312
Diffie Hellman
Around September 1974, Diffie (Graduate student)
had been traveling USA with his wife, Mary,
discussing cryptography with anyone who was
available.
At
the time, there was very little published material about
modern methods and much was classified. Very few
people were interested in the topic and Marty Hellman
even says that many of his colleagues felt that it was
"born classified," like secrets about the atomic bomb,
because it was so important to national security.
John Gill gave the idea of exponential
Cryptography and Network Security
313
Diffie-Hellman Problem
Diffie-Hellman problem definition
Given bu=gau mod p, bv=gav mod p, how to compute
gavau mod p? Here g is a primitive element of mod p
The problem is not harder than the discrete logarithmetic problem, because the later one can always be
used to solve it
It can be proved that it has the same difficulty as the
ElGamal encryption system
Cryptography and Network Security
314
Diffie-Hellman Key Exchange
Computationally secure
if discrete logarithm is intractable
Scheme
Assume prime number p public and an integer c public
Each user u chooses a secret component au (new!)
User u computes bu=c au mod p
User v computes bv=c av mod p
The common key of two users u and v is
K=c au av mod p
Cryptography and Network Security
315
Middle Attack
Intruder w intercept the communications
Intruder w communications with u
Intruder w communications with v
The key computed by u is
K=c au av’ mod p
c au’
c au
v
w
u
c av’
c av
Cryptography and Network Security
316
Authenticated Key Agreement
Introducing the identification scheme
before key exchange does not help
The attacker remains inactive until identification done
Simplified station to station protocol
Key
agreement protocol itself authenticates the user’s
identity at the same time the key being defined
Cryptography and Network Security
317
Station-to-station Protocol
Scheme
Each user has a certificate
C(v)=(Idv,verv,sigTA(Idv,verv))
User u selects au and computes bu=c au mod p
User v selects av and computes
Value bv=c av mod p
Key K=c au av mod p
Signature yv=sigv(bu,bv)
User v sends (C(V), bv, yv) to U
User u computes K=c au av mod p, verifies yv, and C(V)
User u computes yu=sigu(bu,bv), sends (C(u),yu) to V
User v verifies yu, and C(u)
Cryptography and Network Security
318
MTI Agreement Protocol
Scheme
Assume prime number p public and an integer c public
Each user has certificate c(u)=(Idu,bu, sigTA(Idu,bu))
Here bu= c au mod p
Each
user u chooses a secret component ru (new!)
User u computes su=c ru mod p, sends (c(u),su)
User v computes sv=c rv mod p, sends (c(v),sv)
The common key of two users u and v is
K=c rvau+ ru av mod p= sv aubv ru mod p= su avbu rv mod p
Cryptography and Network Security
319
Cryptography and Network
Security
Authentication
Xiang-Yang Li
Cryptography and Network Security
320
Message Authentication
Digital Signature
Authentication
Authentication requirements
Authentication functions
Mechanisms
MAC:
message authentication code
Hash functions, security in hash functions
Hash and MAC algorithms
MD5, SHA, RIPEMD-160, HMAC
Digital signatures
Cryptography and Network Security
321
Message Attacks
Possible attacks
Disclosure
Traffic analysis
Masquerade
Content modification
Sequence modification
Time modification
Repudiation
Denial of the receipt of message by the destination
or
Denial of the transmitting by the source
Cryptography and Network Security
322
Authentication
Enables receiver to verify message
authenticity
Using some lower level functions as primitive
Three types of functions
Message
encryption
Message authentication code (MAC)
Hash function
Cryptography and Network Security
323
Authentication
Goal: Bob wants Alice to “prove” her identity
to him
Protocol ap1.0: Alice says “I am Alice”
“I am Alice”
Failure scenario??
Cryptography and Network Security
324
Authentication
Goal: Bob wants Alice to “prove” her identity
to him
Protocol ap1.0: Alice says “I am Alice”
“I am Alice”
in a network,
Bob can not “see”
Alice, so Trudy simply
declares
herself to be Alice
Cryptography and Network Security
325
Authentication: another try
Protocol ap2.0: Alice says “I am Alice” in an IP packet
containing her source IP address
Alice’s
IP address “I am Alice”
Failure scenario??
Cryptography and Network Security
326
Authentication: another try
Protocol ap2.0: Alice says “I am Alice” in an IP packet
containing her source IP address
Trudy can create
a packet
“spoofing”
Alice’s
Alice’s address
IP address “I am Alice”
Cryptography and Network Security
327
Authentication: another try
Protocol ap3.0: Alice says “I am Alice” and sends her
secret password to “prove” it.
Alice’s
Alice’s
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
Failure scenario??
Cryptography and Network Security
328
Authentication: another try
Protocol ap3.0: Alice says “I am Alice” and sends her
secret password to “prove” it.
Alice’s
Alice’s
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
playback attack: Trudy
records Alice’s packet
and later
plays it back to Bob
Alice’s
Alice’s
“I’m Alice”
IP addr password
Cryptography and Network Security
329
Authentication: yet another try
Protocol ap3.1: Alice says “I am Alice” and sends her
encrypted secret password to “prove” it.
Alice’s encrypted
“I’m Alice”
IP addr password
Alice’s
IP addr
OK
Failure scenario??
Cryptography and Network Security
330
Authentication: another try
Protocol ap3.1: Alice says “I am Alice” and sends her
encrypted secret password to “prove” it.
Alice’s encrypted
“I’m Alice”
IP addr password
Alice’s
IP addr
record
and
playback
still works!
OK
Alice’s encrypted
“I’m Alice”
IP addr password
Cryptography and Network Security
331
Authentication: yet another try
Goal: avoid playback attack
Nonce: number (R) used only once –in-a-lifetime
ap4.0: to prove Alice “live”, Bob sends Alice nonce, R. Alice
must return R, encrypted with shared secret key
“I am Alice”
R
KA-B(R)
drawbacks?
Alice is live, and
only Alice knows
key to encrypt
nonce, so it must
be Alice!
Cryptography and Network Security
332
Authentication: ap5.0
ap4.0 requires shared symmetric key
can we authenticate using public key techniques?
ap5.0: use nonce, public key cryptography
“I am Alice”
R
Bob computes
+ -
-
K A (R)
“send me your public key”
+
KA
KA(KA (R)) = R
and knows only Alice
could have the private
key, that encrypted R
such that
+ K (K (R)) = R
A A
Cryptography and Network Security
333
ap5.0: security hole
Man (woman) in the middle attack: Trudy poses as
Alice (to Bob) and as Bob (to Alice)
I am Alice
R
I am Alice
R
K (R)
T
K (R)
A
Send me your public key
+
K
T
Send me your public key
+
K
A
- +
m = K (K (m))
A A
+
K (m)
A
Trudy gets
- +
m = K (K (m))
T Alice
sends T
m to
+
K (m)
T
encrypted with
Alice’s public key
Cryptography and Network Security
334
ap5.0: security hole
Man (woman) in the middle attack: Trudy poses as
Alice (to Bob) and as Bob (to Alice)
Difficult to detect:
Bob receives everything that Alice sends, and vice
versa. (e.g., so Bob, Alice can meet one week later and
recall conversation)
problem is that Trudy receives all messages as well!
Cryptography and Network Security
335
Message Encryption
Conventional Encryption
Authentication provided due to the secret key
But the message need to be meaningful
What happened it message is not readable?
How to determine intelligible automatically?
Approach
Checksum or frame check sequence(FCS) to message
Encrypt the message and the appending FCS
Receiver decrypt the ciphertext
Computes FCS of message, compare with received one
Cryptography and Network Security
336
Public Key Encryption
Direct encryption by receiver’s public key
Only confidentiality, no authentication
For authentication
Encrypt using sender’s private key
Assume the message is intelligible
No confidentiality: everyone can decrypt
Confidentiality and authentication
Encrypt by sender’s, then receiver’s public key
But too time-consuming: 4 rounds RSA on large data
Cryptography and Network Security
337
Message Authentication Code
Assume both uses share secret key k
Procedure
Sender computes MAC=Ck(M) for M
Sent M and MAC of it to receiver
Receiver computes the MAC on received M
Compare it with received MAC
If match, then accepts the message
MAC is similar to encryption, but not need
be reversible!
Cryptography and Network Security
338
MAC with Confidentiality
Two options
Using another key to encrypt M and MAC
Using another key to encrypt M only
Requirements of MAC
Size
of MAC: n
Size of key: k
Need 2n computations of MAC and n/k pairs of Mi and
MACi
Cryptography and Network Security
339
Why not Conventional Encrypt
Possible situations
Broadcast a message (one destination can verify)
Authentication is done selectively
Authentication of computer program
Authentication may be important than secrecy
Architecture flexibility
Authentication lasts longer than secret protection
Cryptography and Network Security
340
MAC Requirements
Computationally infeasible to construct M’
such that Ck(M’)=Ck(M)
Ck(M) uniformly distributed
Cryptography and Network Security
341
Data Authentication Algorithm
ANSI standard X9.17
Based on DES
Using Cipher Block Chaining mode
Data is grouped into 64 bits blocks
Padding 0’s if necessary
Outputi=Ek(DiOutputi-1)
0<i, and Output0=0’s
The data authentication code DAC consists of the
leftmost m bits of the last output, m16
Cryptography and Network Security
342
Authentication Protocols
Central issues
Confidentiality: prevent masqueraded and
compromised
Timeliness: prevent replay attacks
Simple replay, repetition within timestamp, replay
arrives but not the true messages,backward replay
attack to the sender
Mutual authentication
One-way authentication
Cryptography and Network Security
343
Coping with Replay
Time stamps
Party A accepts a message only if has valid timestamp
within a valid time
Need synchronized clock
How to set the synchronized clock?
Network delay consideration?
Challenge/response
Party A, (receiver), sends B a nonce (challenge) and
requires the subsequent message contains it
Cryptography and Network Security
344
Challenge-Response
To ensure a password is never sent in the
clear. Given a client and a server share a
key
server sends a random challenge vector
client encrypts it with private key and returns this
server verifies response with copy of private key
can repeat protocol in other direction to authenticate
server to client (2-way authentication)
Secret key management
physically distributed before secure communications
keys are stored in a central trusted key server
Cryptography and Network Security
345
Conventional Encryption App.
Each user shares a secret master key with
KDC (Key Distribution Center)
Kerberos is an example
Needham-Schroeder protocol
Party A KDC Ida|Idb|Na
KDCA
Eka(Ks|Idb|Na|Ekb(Ks|Ida))
AB
Ekb(Ks|Ida)
BA
Eks(Nb)
AB
Eks(f(Nb))
Cryptography and Network Security
346
Analysis
Step 4 and 5 prevent the replay of step 3
Assume that Ks is not compromised
If Ks is compromised
Vulnerable to replay attack
Attacker can replay step 3
Unless B remembers all previous session keys with A,
it can not tell that it is a replay!
Cryptography and Network Security
347
Denning Protocol
Denning Protocol
Party A KDC
KDCA
AB
BA
AB
Ida|Idb
Eka(Ks|Idb|T|Ekb(Ks|Ida|T))
Ekb(Ks|Ida|T)
Eks(Nb)
Eks(f(Nb))
Here T is timestamp assures the freshness
of the key Ks
Rely on synchronized clock
Cryptography and Network Security
348
Public-key Encryption App.
The simple one proposed by Denning
AS: authentication server
AAS
Ida|Idb
ASA
Ekras(KUa|Ida|T)|Ekras(Kub|Idb|T)
AB
Ekras(KUa|Ida|T)|Ekras(Kub|Idb|T)|
Ekub(Ekra(Ks|T))
It needs clock synchronization
Cryptography and Network Security
349
Cont.
Protocol by Woo and Lam, using nonce
AKDC
KDCA
AB
BKDC
KDCB
BA
AB
Ida|Idb
EKRau(Idb|KUb)
EKUb(Na|Ida)
Idb|Ida|EKUau(Na)
EKRau(Ida|KUa)|EKUb(EkRau(Na|Ks|Ida|Idb))
EKUa(EkRau(Na|Ks|Ida|Idb) | Nb)
Eks(Nb)
Cryptography and Network Security
350
One-way Authentication
Using Public Key approach
If confidentiality is main concern
AB: EKUb(Ks) | Eks(M)
If authentication is main concern
AB: M|EKRa(H(M))
This can not avoid the interception and replay attack
Sign the message then
EKUb(M|EKRa(H(M)) )
Or EKUb(Ks) | Eks(M|EKRa(H(M)) )
Also A can sends the digital certificate
EKRau(T|Ida|KUa)
Cryptography and Network Security
351
Authentication Applications
will consider authentication functions
developed to support application-level
authentication & digital signatures
will consider Kerberos – a private-key
authentication service
then X.509 directory authentication
service
Cryptography and Network Security
352
Kerberos
Trusted key server system developed by
MIT
Provides centralized third-party authentication in a
distributed network
access control may be provided for
each computing resource
in either a local or remote network (realm)
A Key Distribution Centre (KDC), containing database:
principles (customers and services)
encryption keys
KDC provides non-corruptible authentication
credentials (tickets or tokens)
Cryptography and Network Security
353
Kerberos
Two Kerberos versions
4 : restricted to a single realm
5 : allows inter-realm authentication, in beta test
Kerberos v5 is an Internet standard specified in RFC1510
To use Kerberos
need to have a KDC on your network
need to have Kerberised applications running on all participating
systems
US export restrictions
Cannot be directly distributed outside US in source format
Crypto libraries must be re-implemented locally
Cryptography and Network Security
354
Kerberos Requirements
first published report identified its
requirements as:
security
reliability
transparency
scalability
implemented using an authentication
protocol based on Needham-Schroeder
Cryptography and Network Security
355
Kerberos 4 Overview
a basic third-party authentication scheme
have an Authentication Server (AS)
users initially negotiate with AS to identify self
AS provides a non-corruptible authentication credential
(ticket granting ticket TGT)
have a Ticket Granting server (TGS)
users subsequently request access to other services from
TGS on basis of users TGT
Cryptography and Network Security
356
Kerberos 4 Overview
Cryptography and Network Security
357
Kerberos Realms
a Kerberos environment consists of:
a Kerberos server
a number of clients, all registered with server
application servers, sharing keys with server
this is termed a realm
typically a single administrative domain
if have multiple realms, their Kerberos
servers must share keys and trust
Cryptography and Network Security
358
Kerberos Version 5
developed in mid 1990’s
provides improvements over v4
addresses environmental shortcomings
encryption alg, network protocol, byte order, ticket
lifetime, authentication forwarding, interrealm auth
and technical deficiencies
double encryption, non-std mode of use, session keys,
password attacks
specified as Internet standard RFC 1510
Cryptography and Network Security
359
Authentication Protocols
used to convince parties of each others
identity and to exchange session keys
may be one-way or mutual
key issues are
confidentiality – to protect session keys
timeliness – to prevent replay attacks
Cryptography and Network Security
360
Replay Attacks
where a valid signed message is copied and
later resent
simple replay
repetition that can be logged
repetition that cannot be detected
backward replay without modification
countermeasures include
use of sequence numbers (generally impractical)
timestamps (needs synchronized clocks)
challenge/response (using unique nonce)
Cryptography and Network Security
361
Using Symmetric Encryption
as discussed previously can use a two-level
hierarchy of keys
usually with a trusted Key Distribution
Center (KDC)
each
party shares own master key with KDC
KDC generates session keys used for connections
between parties
master keys used to distribute these to them
Cryptography and Network Security
362
Needham-Schroeder Protocol
original third-party key distribution
protocol
for session between A B mediated by KDC
protocol overview is:
1. A→KDC: IDA || IDB || N1
2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]
3. A→B: EKb[Ks||IDA]
4. B→A: EKs[N2]
5. A→B: EKs[f(N2)]
Cryptography and Network Security
363
Needham-Schroeder Protocol
used to securely distribute a new session
key for communications between A & B
but is vulnerable to a replay attack if an
old session key has been compromised
then
message 3 can be resent convincing B that is
communicating with A
modifications to address this require:
timestamps (Denning 81)
using an extra nonce (Neuman 93)
Cryptography and Network Security
364
Using Public-Key Encryption
have a range of approaches based on the
use of public-key encryption
need to ensure have correct public keys
for other parties
using a central Authentication Server (AS)
various protocols exist using timestamps or
nonces
Cryptography and Network Security
365
Denning AS Protocol
Denning 81 presented the following:
1. A→AS: IDA || IDB
2. AS→A: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T]
3. A→B: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T] ||
EKUb[EKRas[Ks||T]]
note session key is chosen by A, hence AS
need not be trusted to protect it
timestamps prevent replay but require
synchronized clocks
Cryptography and Network Security
366
One-Way Authentication
required when sender & receiver are not in
communications at same time (eg. email)
have header in clear so can be delivered by
email system
may want contents of body protected &
sender authenticated
Cryptography and Network Security
367
Using Symmetric Encryption
can refine use of KDC but can’t have final
exchange of nonces, vis:
1. A→KDC: IDA || IDB || N1
2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]
3. A→B: EKb[Ks||IDA] || EKs[M]
does not protect against replays
could rely on timestamp in message, though email
delays make this problematic
Cryptography and Network Security
368
Public-Key Approaches
have seen some public-key approaches
if confidentiality is major concern, can use:
A→B: EKUb[Ks] || EKs[M]
has encrypted session key, encrypted message
if authentication needed use a digital signature
with a digital certificate:
A→B: M || EKRa[H(M)] || EKRas[T||IDA||KUa]
with message, signature, certificate
Cryptography and Network Security
369
Differences between Authentication
and Digital Signature
Two authentications:
Data authentication is comparable to stamping a document in a way disallowing all
future modifications to it. Data authentication is usually accompanied with
data origin authentication that bounds a concrete person to this document
Digital signature is a cryptographic technique that enables to
protect digital information (represented as a bit-stream) from
undesirable modification. Since signature cannot just be appended
to a digital bitstream, more sophisticated methods (also known as
signatures schemes) for signing have been elaborated.
Signature scheme is a function Sig of a key pair (SA,VA) and a
bitstring M, such that
for anyone who knows the secret key SA, it is easy to compute for any plaintext M
the signature C=Sig(PA,M).
for anyone who knows VA (the public key), C and M, it is easy to verify if
C=Sig(SA,M).
for a randomly chosen C, it is intractable for anyone who does not know SA to find
a value M for which C=Sig(SA,M).
Cryptography and Network Security
370
Cryptography and Network
Security
Hash Algorithms
Xiang-Yang Li
Cryptography and Network Security
371
Hash Function
Map a message to a smaller value
Requirements
Be applied to a block of data of any size
Produced a fixed length output
H(x) is easy to compute (by hardware, software)
One-way: given code h, it is computationally infeasible
to find x: H(x)=h
Weak collision resistance: given x, computationally
infeasible to find y so H(x)=H(y)
Strong collision resistance: Computationally infeasible
to find x, y so H(x)=H(y)
Cryptography and Network Security
372
Hash Algorithms
see similarities in the evolution of hash
functions & block ciphers
increasing power of brute-force attacks
leading to evolution in algorithms
from DES to AES in block ciphers
from MD4 & MD5 to SHA-1 & RIPEMD-160 in hash
algorithms
likewise tend to use common iterative
structure as do block ciphers
Cryptography and Network Security
373
Basic Uses of Hash Function
Six basics usages
Ek(M||H(M))
Confidentiality and authentication
M|| Ek(H(M))
Authentication
M|| EKRa(H(M))
Authentication and digital signature
Ek(M|| EKRa(H(M)))
Authentication, digital signature and confidentiality
M||H(M||S)
Authentication (S shared by both sides)
Ek(M||H(M||S))
Confidentiality and authentication
Cryptography and Network Security
374
Birthday Attacks
If 64-bits hash code is used
On average, how many messages need to try to find one
match the intercepted hash code?
Birthday paradox
A will
sign a message appended with m-bits hash code
Attacker generates some variations of fraud message,
also variations of good message
Find pair of message each from the two sets messages
Such that they have the same hash code
Give good message to A to get signature
Replace good message with fraud message
Cryptography and Network Security
375
Analysis
Using birthday attack, given 64-bits hash
code
How many message variations needed so the success
probability is large, say 90%?
Cryptography and Network Security
376
Examples
Simple hash functions
XOR of the input message
H(M)=X1 X2 … Xm-1 Xm
But not secure
Ym=H(M) Y1 Y2 … Ym-1 has same hash value as
(X1X2 … Xm-1 Xm), where Yi is any value
Cryptography and Network Security
377
Cont.
Based on DES, block chaining technique
Rabin, 1978
Divide message M into fix-sized blocks Mi
Assume total n data blocks
H0=initial value
Hi=Emi[Hi-1]
Hn is the hash value
Birthday attack still applies
If still 64-bits code used
Cryptography and Network Security
378
More Attacks
Birthday attack applied if chosen plaintext
Meet in the middle attack if known
plaintext
Known signed hash code G
Construct n-2 desired message block Qi
Compute Hi=EQi[Hi-1]
Generate 2m/2 random blocks X
For each X, Compute Hn-1=EX[Hn-2]
Generate 2m/2 random blocks Y
For each Y, Compute H’n-1=DY[G]
Find X, Y such that Hn-1= H’n-1
Then Q1, Q2,…Qn-2, X,Y is a fraud message
Cryptography and Network Security
379
Security
The size of hash code determines security
128bits is not secure
Currently, most use 160 bits hash code
Now recommend 256 bits
Attack MAC
Objective is to find valid (x, Ck(x)) pair
Attack the key space: roughly 2k, k =key size
Attack the MAC value
Cryptography and Network Security
380
More Hash Algorithms
Algorithms
Message Digest:MD5 (was mostly widely used)
Secure Hash Algorithm: SHA-1 (from MD4)
RIPEMD-160
HMAC
Cryptography and Network Security
381
MD5
designed by Ronald Rivest (the R in RSA)
latest in a series of MD2, MD4
produces a 128-bit hash value
until recently was the most widely used
hash algorithm
in recent times have both brute-force & cryptanalytic
concerns
specified as Internet standard RFC1321
Cryptography and Network Security
382
MD5 Overview
pad message so its length is 448 mod 512
2. append a 64-bit length value to message
3. initialise 4-word (128-bit) MD buffer
(A,B,C,D)
4. process message in 16-word (512-bit)
blocks:
1.
using 4 rounds of 16 bit operations on message block
& buffer
add output to buffer input to form new buffer value
5. output hash value is the final buffer value
Cryptography and Network Security
383
MD5 Overview
Cryptography and Network Security
384
MD5 Compression Function
each round has 16 steps of the form:
a = b+((a+g(b,c,d)+X[k]+T[i])<<<s)
a,b,c,d refer to the 4 words of the buffer,
but used in varying permutations
note
this updates 1 word only of the buffer
after 16 steps each word is updated 4 times
where g(b,c,d) is a different nonlinear
function in each round (F,G,H,I)
T[i] is a constant value derived from sin
Cryptography and Network Security
385
MD5 Compression Function
Cryptography and Network Security
386
MD4
precursor to MD5
also produces a 128-bit hash of message
has 3 rounds of 16 steps vs 4 in MD5
design goals:
collision resistant (hard to find collisions)
direct security (no dependence on "hard" problems)
fast, simple, compact
favours little-endian systems (eg PCs)
Cryptography and Network Security
387
Strength of MD5
MD5 hash is dependent on all message bits
Rivest claims security is good as can be
known attacks are:
Berson 92 attacked any 1 round using differential
cryptanalysis (but can’t extend)
Boer & Bosselaers 93 found a pseudo collision (again
unable to extend)
Dobbertin 96 created collisions on MD compression
function (but initial constants prevent exploit)
conclusion is that MD5 looks vulnerable
soon
Cryptography and Network Security
388
Bad news
Chinese authors (Wang, Feng, Lai, and Yu) reported a
family of collisions in MD5
(fixing the previous bug in their analysis), and also reported
that their method can efficiently (2^40 hash steps) find a
collision in SHA-0.
August Crypto 2004,
MD5 is fatally wounded; its use will be phased out.
SHA-1 is still alive but the vultures are circling. A
gradual transition away from SHA-1 will now start.
The first stage will be a debate about alternatives,
leading to a consensus among practicing
cryptographers about what the substitute will be.
Cryptography and Network Security
389
Why collisions are bad
An example of what you might do with this.
You could request an SSL certificate (for your real identity)
from a certificate authority. After the response comes back,
you can then use that response (which is based on the MD5
of your identity+key) to "authenticate" a carefully chosen
different certificate, one which claims that you are
LargeBankOrSoftwareCorp., but which has the same MD5 as
your real identity. You can then present this to other people
in order to convince them that you are someone whom you
are not.
Another example,
core internet routers use md5 to exchange passwords. I
simply sniff the md5sum, and if I can find a string that
generates the same sum, easily, I can send my own routing
update that takes down the internet. More examples, since a
LOT of applications use md5, but you get the idea.
Cryptography and Network Security
390
Further detail
Obviously the above attack isn't quite so simple, but
this research makes it *possible*. Before, it was
believed to be sufficiently difficult to find a collision,
that nobody worried about it. Now they are saying its
feasible to do it in hours.
The question hanging around right now is that these
researchers managed to find collisions easily, but not
for an artbitrary string. The questions is how long
before someone modifies this method to find any
colllision. That is how much time the world has to
move away.
More at
http://www.freedom-to-tinker.com/archives/000664.html
Cryptography and Network Security
391
What to do next
The U.S. National Institute of Standards
and Technology is having a competition for
a new cryptographic hash function.
The phrase "one-way hash function" might
sound arcane and geeky, but hash functions
are the workhorses of modern
cryptography.
Submissions will be due in fall 2008, and a
single standard is scheduled to be chosen
by the end of 2011.
we have an interim solution in SHA-256.
Cryptography and Network Security
392
Secure Hash Algorithm (SHA-1)
SHA was designed by NIST & NSA in
1993, revised 1995 as SHA-1
US standard for use with DSA signature
scheme
standard is FIPS 180-1 1995, also Internet RFC3174
nb. the algorithm is SHA, the standard is SHS
produces 160-bit hash values
now the generally preferred hash algorithm
based on design of MD4 with key
differences
Cryptography and Network Security
393
SHA Overview
pad message so its length is 448 mod 512
2. append a 64-bit length value to message
3. initialise 5-word (160-bit) buffer (A,B,C,D,E)
to
1.
(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)
4. process message in 16-word (512-bit)
chunks:
expand 16 words into 80 words by mixing & shifting
use 4 rounds of 20 bit operations on message block &
buffer
add output to input to form new buffer value
5. output hash value is the final buffer value
Cryptography and Network Security
394
SHA-1 Compression Function
each round has 20 steps which replaces the
5 buffer words thus:
(A,B,C,D,E) <(E+f(t,B,C,D)+(A<<5)+Wt+Kt),A,(B<<30),C,D)
a,b,c,d refer to the 4 words of the buffer
t is the step number
is nonlinear function for round
Wt is derived from the message block
Kt is a constant value derived from sin
f(t,B,C,D)
Cryptography and Network Security
395
SHA-1 Compression Function
Cryptography and Network Security
396
SHA-1 verses MD5
brute force attack is harder (160 vs 128
bits for MD5)
not vulnerable to any known attacks
(compared to MD4/5)
a little slower than MD5 (80 vs 64 steps)
both designed as simple and compact
optimised for big endian CPU's (vs MD5
which is optimised for little endian CPU’s)
Cryptography and Network Security
397
Revised Secure Hash Standard
NIST have issued a revision FIPS 180-2
adds 3 additional hash algorithms
SHA-256, SHA-384, SHA-512
designed for compatibility with increased
security provided by the AES cipher
structure & detail is similar to SHA-1
hence analysis should be similar
Cryptography and Network Security
398
RIPEMD-160
RIPEMD-160 was developed in Europe as part of
RIPE project in 96
by researchers involved in attacks on MD4/5
initial proposal strengthen following analysis to
become RIPEMD-160
somewhat similar to MD5/SHA
uses 2 parallel lines of 5 rounds of 16 steps
creates a 160-bit hash value
slower, but probably more secure, than SHA
Cryptography and Network Security
399
RIPEMD-160 Overview
1.
2.
3.
pad message so its length is 448 mod 512
append a 64-bit length value to message
initialise 5-word (160-bit) buffer (A,B,C,D,E) to
(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)
4.
process message in 16-word (512-bit) chunks:
5.
use 10 rounds of 16 bit operations on message block & buffer –
in 2 parallel lines of 5
add output to input to form new buffer value
output hash value is the final buffer value
Cryptography and Network Security
400
RIPEMD-160 Round
Cryptography and Network Security
401
RIPEMD-160 Compression Function
Cryptography and Network Security
402
RIPEMD-160 Design Criteria
use 2 parallel lines of 5 rounds for
increased complexity
for simplicity the 2 lines are very similar
step operation very close to MD5
permutation varies parts of message used
circular shifts designed for best results
Cryptography and Network Security
403
RIPEMD-160 verses MD5 & SHA-1
brute force attack harder (160 like SHA-1
vs 128 bits for MD5)
not vulnerable to known attacks, like SHA-1
though stronger (compared to MD4/5)
slower than MD5 (more steps)
all designed as simple and compact
SHA-1 optimised for big endian CPU's vs
RIPEMD-160 & MD5 optimised for little
endian CPU’s
Cryptography and Network Security
404
Keyed Hash Functions as MACs
have desire to create a MAC using a hash
function rather than a block cipher
because hash functions are generally faster
not limited by export controls unlike block ciphers
hash includes a key along with the message
original proposal:
KeyedHash = Hash(Key|Message)
some
weaknesses were found with this
eventually led to development of HMAC
Cryptography and Network Security
405
HMAC
specified as Internet standard RFC2104
uses hash function on the message:
HMACK = Hash[(K+ XOR opad) ||
Hash[(K+ XOR ipad)||M)]]
where K+ is the key padded out to size
and opad, ipad are specified padding constants
overhead is just 3 more hash calculations than the
message needs alone
any of MD5, SHA-1, RIPEMD-160 can be used
Cryptography and Network Security
406
HMAC Overview
Cryptography and Network Security
407
HMAC Security
know that the security of HMAC relates to
that of the underlying hash algorithm
attacking HMAC requires either:
brute force attack on key used
birthday attack (but since keyed would need to observe
a very large number of messages)
choose hash function used based on speed
verses security constraints
Cryptography and Network Security
408
Summary
have considered:
some current hash algorithms: MD5, SHA-1, RIPEMD160
HMAC authentication using hash function
Cryptography and Network Security
409
Cryptography and Network
Security
Digital Signature
Xiang-Yang Li
Cryptography and Network Security
410
Digital Signature
Cryptography and Network Security
411
Digital Signatures
have looked at message authentication
but does not address issues of lack of trust
digital signatures provide the ability to:
verify author, date & time of signature
authenticate message contents
be verified by third parties to resolve disputes
hence include authentication function with
additional capabilities
Cryptography and Network Security
412
Digital Signature Properties
must depend on the message signed
must use information unique to sender
to prevent both forgery and denial
must be relatively easy to produce
must be relatively easy to recognize & verify
be computationally infeasible to forge
with new message for existing digital signature
with fraudulent digital signature for given message
be practical save digital signature in storage
Cryptography and Network Security
413
Securities
A total break results in the recovery of the
signing key.
A universal forgery attack results in the
ability to forge signatures for any message.
A selective forgery attack results in a
signature on a message of the adversary's
choice.
An existential forgery merely results in some
valid message/signature pair not already
known to the adversary.
Cryptography and Network Security
414
Classification of Digital Signature
Undeniable
Fail-Stop
Blind
One-time
Multi-party (group signature)
(n,k)-multi-party
Oblivious
Multi-undeniable
Cryptography and Network Security
415
Algorithm and legal concerns
several prior requirements
quality algorithms. Some public key algorithms are known to be
insecure, practicable attacks against them having been identified.
quality implementations. An implementation of a good algorithm with
mistake(s) will not work. (about 1 defect per 1,000 lines).
the private key must remain actually secret; if it becomes known to
some other party, that party can produce perfect digital signatures of
anything whatsoever.
distribution of public keys must be done in such a way that the public
key claimed to belong to Bob actually belongs to Bob, and vice versa.
This is commonly done using a public key infrastructure and the public
key user association is attested by the operator of the PKI (called a
certificate authority). For 'open' PKIs in which anyone can request such
an attestation, the possibility of mistake is non trivial.
users (and their software) must carry out the signature protocol
properly.
Legal concerns
Cryptography and Network Security
416
Direct Digital Signatures
involve only sender & receiver
assumed receiver has sender’s public-key
digital signature made by sender signing
entire message or hash with private-key
can encrypt using receivers public-key
important that sign first then encrypt
message & signature
security depends on sender’s private-key
Cryptography and Network Security
417
Arbitrated Digital Signatures
involves use of arbiter A
validates any signed message
then dated and sent to recipient
requires suitable level of trust in arbiter
can be implemented with either private or
public-key algorithms
arbiter may or may not see message
Cryptography and Network Security
418
RSA signature
N=p q,where p and q are large primes
Alice’s private key (e,n),
Alice’s public key (d,n)
Signature of message m by Alice
S=H(m)e mod n
Verification of signature by Bob
Check if h(m) = Sd mod n
Cryptography and Network Security
419
From wikipedia
Cryptography and Network Security
420
Cont.
Typically d is chosen small (3 or 216+1)
Problem:
Easy to create the signature of h(m1)h(m2)
RSA-PSS
Use some more randomization to enhance security
It was added in version 2.1 of PKCS #1 (see RFC
3447).
Cryptography and Network Security
421
ElGamal Signature
Global public components
Prime number p with 512-1024 bits
Primitive element g in Zp
Users private key
Random
integer x less than p
Users public key
Integer y=gx mod p
Cryptography and Network Security
422
Elgamal
Signature
For each message M, generates random k
Computes r=gk mod p
Computes s=k-1(H(M)-xr) mod (p-1)
Signature is (r,s)
Verifying
Computes v1=gH(M) mod p
Computes v2=yrrs mod p
Test if v1= v2
Cryptography and Network Security
423
Proof of Correctness
Computes v2=yrrs mod q
So v2=yrrs mod q =gxr gks mod p
-1
= gxr+k k (H(M)-xr) mod (p-1) mod p
=gH(M) mod p=v1
Notice that here it uses Fermat theorem to show
That g (H(M)-xr) mod (p-1) mod p = g
(H(M)-xr) mod
p
Cryptography and Network Security
424
Cont.
The main disadvantage of ElGamal is
the need for randomness (sometimes it is good), and
its slower speed (especially for signing).
Another potential disadvantage of the ElGamal system
is that message expansion by a factor of two takes place
during encryption. However, such message expansion is
negligible if the cryptosystem is used only for exchange
of secret keys.
Cryptography and Network Security
425
Digital Signature Standard
FIPS PUB 186 by NIST, 1991
Final announcement 1994
It uses
Secure Hashing Algorithm (SHA) for hashing
Digital Signature Algorithm (DSA) for signature
The hash code is set as input of DSA
The signature consists of two numbers
DSA
Based on the difficulty of discrete logarithm
Based on Elgamal and Schnorr system
Cryptography and Network Security
426
DSA
Global public components
Prime number p with 512-1024 bits
Prime divisor q of (p-1) with 160 bits
Integer g=h(p-1)/q mod p
Users private key
Random integer x less than q
Users public key
Integer
y=gx mod p
Cryptography and Network Security
427
DSA
Signature
For each message M, generates random k
Computes r=(gk mod p) mod q
Computes s=k-1(H(M)+xr) mod q
Signature is (r,s)
Verifying
Computes w=s-1 mod q, u1=H(M)w mod q
Computes u2=rw mod q,v=(gu1yu2 mod p) mod q
Test if v=r
Cryptography and Network Security
428
Proof of Correctness
Notice that v=(gu1yu2 mod p) mod q
=(gH(M)w mod q yrw mod q mod p) mod q
=(gH(M)w mod q gxrw mod q mod p) mod q
=(gH(M)w +xrw mod q mod p) mod q
=(g(H(M)+xr)w mod q mod p) mod q
-1
=(g(H(M)+xr)k(H(M)+xr) mod q mod p) mod q
=(gk mod p) mod q
=r
Cryptography and Network Security
429
In practice (Sun Java Library)
g = F7E1A085D69B3DDE CBBCAB5C36B857B9
7994AFBBFA3AEA82 F9574C0B3D078267
5159578EBAD4594F E67107108180B449
167123E84C281613 B7CF09328CC8A6E1
3C167A8B547C8D28 E0A3AE1E2BB3A675
916EA37F0BFA2135 62F1FB627A01243B
CCA4F1BEA8519089 A883DFE15AE59F06
928B665E807B5525 64014C3BFECF492A
p = FD7F53811D751229 52DF4A9C2EECE4E7
F611B7523CEF4400 C31E3F80B6512669
455D402251FB593D 8D58FABFC5F5BA30
F6CB9B556CD7813B 801D346FF26660B7
6B9950A5A49F9FE8 047B1022C24FBBA9
D7FEB7C61BF83B57 E7C6A8A6150F04FB
83F6D3C51EC30235 54135A169132F675
F3AE2B61D72AEFF2 2203199DD14801C7
q = 9760508F15230BCC B292B982A2EB840B F0581CF5
Here g and p have 1024 bits, while q has 160 bits. They fulfill the
requirement that gq = 1 mod p, Cryptography and Network Security
430
Note
Can we use the random number k twice?
What will happen if k used twice?
We have r=(gk mod p) mod q
s1=k-1(H(M1)+xr) mod q and s2=k-1(H(M2)+xr) mod q
We have s1 - s2 =k-1(H(M1)-H(M2)) mod q
Another attack (for OpenPGP)
Replace
p and g
http://www.tigertools.net/board/?topic=topic4&msg=14
http://www.orlingrabbe.com/DSAflaw_OpenPGP.htm
Cryptography and Network Security
431
Cont.
We cannot use small k
Cryptography and Network Security
432
Non-deterministic
Non-determined signatures
For each message, many valid signatures exist
DSA, Elgamal
Deterministic signatures
For
each message, one valid signature exists
RSA
Cryptography and Network Security
433
Comparisons
Speed
DSS has faster signing than verifying
RSA could have faster verifying than signing
Message be signed once, but verified many times
This prefers the faster verification
But the signer may have limited computing power
Example: smart card
This prefers the faster siging
Cryptography and Network Security
434
Blind Signature (digital cash)
first introduced by Chaum, allow a person to get a
message signed by another party without revealing any
information about the message to the other party.
Suppose Alice has a message m that she wishes to have
signed by Bob, and she does not want Bob to learn
anything about m.
Let (n,e) be Bob's public key and (n,d) be his private key.
e
Alice generates a random value r such that gcd(r, n) = 1 and sends x = (r
m) mod n to Bob. The value x is ``blinded'' by the random value r; hence
Bob can derive no useful information from it.
d
Bob returns the signed value t = x mod n to Alice.
d
e
d
d
Since x (r m) r m mod n,
Alice can obtain the true signature s of m by computing
-1
s = r t mod n.
Cryptography and Network Security
435
Security Concerns
GnuPG permits creating ElGamal keys
are usable for both encryption and signing.
It is even possible to have one key (the primary one)
used for both operations.
This is not considered good cryptographic practice, but
is permitted by the OpenPGP standard.
signature is much larger than a RSA or DSA
signature
verification and creation takes far longer and the use
of ElGamal for signing has always been problematic
due to a couple of cryptographic weaknesses when
not done properly.
Cryptography and Network Security
436
Applications of Blind Signature
In an online context the blind signature works as
follows.
Voters encrypt their ballot with a secret key and then blinds it.
Then the voter signs the encrypted vote and sends it to the
validator.
The validator checks to see if the signature is valid (the signature
acts as a I.D. tag and will have to be registered with the voter
before the voting process has started) and if it is the validator signs
it and returns it to the voter.
The voter removes the blinding encryption layer, which then leaves
behind an encrypted ballot with the validator's signature.
Cryptography and Network Security
437
Cont.
This is then sent to the tallier who checks to make
sure the validator's signature is present on the
votes.
He then waits until all votes haven been collected and
then publishes all the encrypted votes so that the
voters can verify their votes have been received.
The voters then send their keys to the tallier to
decrypt their ballots.
Once the vote has been counted the tallier publishes
the encrypted votes and the decryption keys so that
voters can then verify the results.
Next we illustrate the transfer of ballots between
the various parties.
Cryptography and Network Security
438
Cont.
Cryptography and Network Security
439
Cont,
This protocol has been implemented used in reality
and has been found that the entire voting process
can be completed in a matter of minutes despite
the complex nature of the voting procedure.
Most of the tasks can be automated with the only
user interaction needed being the actual vote
casting.
Encryption, blinding and all the verification needed
can be performed by software in the background.
Of course we'd have to trust this software to
handle the voting procedures correctly and
accurately and to assume it has not been
compromised in some way.
Cryptography and Network Security
440
Cryptography and Network Security
Certificate
Xiang-Yang Li
Cryptography and Network Security
441
Certificate
A public-key certificate is a digitally
signed statement from one entity, saying
that the public key (and some other
information) of another entity has some
specific value.
Cryptography and Network Security
442
More terms
Digitally Signed
If some data is digitally signed it has been stored with
the "identity" of an entity, and a signature that proves
that entity knows about the data. The data is rendered
unforgeable by signing with the entitys' private key.
Identity
A known way of addressing an entity. In some systems
the identity is the public key, in others it can be anything
from a Unix UID to an Email address to an X.509
Distinguished Name.
Entity
An entity is a person, organization, program, computer,
business, bank, or something else you are trusting to
some degree.
Cryptography and Network Security
443
More about CA
Why need it
In a large-scale networked environment it is impossible to
guarantee that prior relationships between communicating entities
have been established or that a trusted repository exists with all
used public keys. Certificates were invented as a solution to this
public key distribution problem. Now a Certification Authority
(CA) can act as a Trusted Third Party. CAs are entities (e.g.,
businesses) that are trusted to sign (issue) certificates for other
entities. It is assumed that CAs will only create valid and reliable
certificates as they are bound by legal agreements. There are many
public Certification Authorities, such as VeriSign, Thawte, Entrust,
and so on. You can also run your own Certification Authority using
products such as the Netscape/Microsoft Certificate Servers or the
Entrust CA product for your organization.
Cryptography and Network Security
444
Who uses Certificate?
Probably the most widely visible application of
X.509 certificates today is in web browsers (such
as Netscape Navigator and Microsoft Internet
Explorer) that support the SSL protocol.
SSL (Secure Socket Layer) is a security protocol that provides
privacy and authentication for your network traffic. These
browsers can only use this protocol with web servers that support
SSL.
Other technologies that rely on X.509 certificates
include:
Various code-signing schemes, such as signed Java Archives, and
Microsoft Authenticode.
Various secure E-Mail standards, such as PEM and S/MIME.
E-Commerce protocols, such as SET.
Cryptography and Network Security
445
How to create certificate?
There are two basic techniques used to get
certificates:
you can create one yourself (using the right tools, such as keytool)
Not everyone will accept self-signed certificates,
you can ask a Certification Authority to issue you one (either directly or
using a tool such as keytool to generate the request).
The main inputs to the certificate creation are:
Matched public and private keys, generated using some special tools
(such as keytool), or a browser.
information about the entity being certified (e.g., you). This normally
includes information such as your name and organizational address. If
you ask a CA to issue a certificate for you, you will normally need to
provide proof to show correctness of the information.
Cryptography and Network Security
446
business
Many companies sale the service of
creating the certificate (such as SSL
certificate)
Comodo
Verisign
Thawte
Entrust
Geotrust
Cryptography and Network Security
447
X.509 Authentication Service
Public key certificate associated with user
The certificates are created by Trusted Authority
Then placed in the directory by TA or user
Itself is not responsible for creating certificate
It includes
Version, serial number, signature algorithm identifier,
Issuer name, issuer identifier, validity period, the
user, user identifier, user’s public key, extensions,
signature by TA
The signature by TA guarantees the authority
Certificates can be used to certify other TAs
Y<<X>>: certificate of user X issued by TA Y
Cryptography and Network Security
448
What is inside X.509 certificate?
Version
Thus far, three versions are defined.
Serial Number
distinguish it from other certificates it issues. This
information is used in numerous ways, for example when a
certificate is revoked its serial number is placed in a
Certificate Revocation List (CRL).
Signature Algorithm Identifier
This identifies the algorithm used by the CA to sign the
certificate.
Issuer Name
The X.500 name of the entity that signed the certificate.
This is normally a CA. Using this certificate implies trusting
the entity that signed this certificate. root or top-level CA
certificates, the issuer signs its own certificate.
Cryptography and Network Security
449
cont
Validity Period
This period is described by a start date and time and an end
date and time, and can be as short as a few seconds or
almost as long as a century. It depends on a number of
factors, such as the strength of the private key used to sign
the certificate or the amount one is willing to pay for a
certificate. This is the expected period that entities can
rely on the public value, if the associated private key has not
been compromised.
Subject Name
The name of the entity whose public key the certificate
identifies. This name uses the X.500 standard, so it is
intended to be unique across the Internet.
Subject Public Key Information
together with an algorithm identifier
Cryptography and Network Security
450
Certificate Revocation
Need the private key together with the
certificate to revoke it
The revocation is recorded at the
directory
Each time a certificate is arrived, check
the directory to see if it is revoked
Cryptography and Network Security
451
X.509 Authentication Service
part of CCITT X.500 directory service standards
distributed servers maintaining some info database
defines framework for authentication services
directory may store public-key certificates
with public key of user
signed by certification authority
also defines authentication protocols
uses public-key crypto & digital signatures
algorithms not standardised, but RSA recommended
Cryptography and Network Security
452
X.509 Certificates
issued by a Certification Authority (CA), containing:
version (1, 2, or 3)
serial number (unique within CA) identifying certificate
signature algorithm identifier
issuer X.500 name (CA)
period of validity (from - to dates)
subject X.500 name (name of owner)
subject public-key info (algorithm, parameters, key)
issuer unique identifier (v2+)
subject unique identifier (v2+)
extension fields (v3)
signature (of hash of all fields in certificate)
notation CA<<A>> denotes certificate for A signed by CA
Cryptography and Network Security
453
X.509 Certificates
Cryptography and Network Security
454
Obtaining a Certificate
any user with access to CA can get any
certificate from it
only the CA can modify a certificate
because cannot be forged, certificates can
be placed in a public directory
Cryptography and Network Security
455
CA Hierarchy
if both users share a common CA then they
are assumed to know its public key
otherwise CA's must form a hierarchy
use certificates linking members of
hierarchy to validate other CA's
each CA has certificates for clients (forward) and parent
(backward)
each client trusts parents certificates
enable verification of any certificate from
one CA by users of all other CAs in
hierarchy
Cryptography and Network Security
456
CA Hierarchy Use
Cryptography and Network Security
457
Certificate Revocation
certificates have a period of validity
may need to revoke before expiry, eg:
1.
2.
3.
CA’s maintain list of revoked certificates
user's private key is compromised
user is no longer certified by this CA
CA's certificate is compromised
the Certificate Revocation List (CRL)
users should check certs with CA’s CRL
Cryptography and Network Security
458
Authentication Procedures
X.509 includes three alternative
authentication procedures:
One-Way Authentication
Two-Way Authentication
Three-Way Authentication
all use public-key signatures
Cryptography and Network Security
459
One-Way Authentication
1 message ( A->B) used to establish
the identity of A and that message is from A
message was intended for B
integrity & originality of message
message must include timestamp, nonce,
B's identity and is signed by A
Cryptography and Network Security
460
Two-Way Authentication
2 messages (A->B, B->A) which also
establishes in addition:
the identity of B and that reply is from B
that reply is intended for A
integrity & originality of reply
reply includes original nonce from A, also
timestamp and nonce from B
Cryptography and Network Security
461
Three-Way Authentication
3 messages (A->B, B->A, A->B) which
enables above authentication without
synchronized clocks
has reply from A back to B containing
signed copy of nonce from B
means that timestamps need not be
checked or relied upon
Cryptography and Network Security
462
X.509 Version 3
has been recognised that additional
information is needed in a certificate
email/URL, policy details, usage constraints
rather than explicitly naming new fields
defined a general extension method
extensions consist of:
extension identifier
criticality indicator
extension value
Cryptography and Network Security
463
Certificate Extensions
key and policy information
convey info about subject & issuer keys, plus indicators
of certificate policy
certificate subject and issuer attributes
support
alternative names, in alternative formats for
certificate subject and/or issuer
certificate path constraints
allow constraints on use of certificates by other CA’s
Cryptography and Network Security
464
Cryptography and Network Security
Identification
Xiang-Yang Li
Cryptography and Network Security
465
Identification
Identification: user authentication
convince system of your identity
before it can act on your behalf
sometimes also require that the computer verify its identity with
the user
Based on three methods
what you know
what you have
what you are
Verification
Validation of information supplied against a table of possible
values based on users claimed identity
Cryptography and Network Security
466
What you Know
Passwords or Pass-phrases
prompt user for a login name and password
verify identity by checking that password is correct
on some (older) systems, password was stored clear
more often use a one-way function, whose output
cannot easily be used to find the input value
either takes a fixed sized input (eg 8 chars)
or based on a hash function to accept a variable sized
input to create the value
important that passwords are selected with care to
reduce risk of exhaustive search
Cryptography and Network Security
467
Weakness
Traditional password scheme is vulnerable
to eavesdropping over an insecure network
Cryptography and Network Security
468
Solutions?
One-time password
these are passwords used once only
future values cannot be predicted from older values
Password generation
either generate a printed list, and keep matching list on
system to be accessed
or use an algorithm based on a one-way function f (eg
MD5) to generate previous values in series (eg SKey)
start with a secret password s, and number N , p0 =
fN(s)
ith password in series is pi = fN-i(s)
must reset password after N uses
Cryptography and Network Security
469
What you Have
Magnetic Card, Magnetic Key
possess item with required code value encoded
Smart Card or Calculator
may interact with system
may require information from user
could be used to actively calculate:
a time dependent password
a one-shot password
a challenge-response verification
public-key based verification
Cryptography and Network Security
470
What you Are
Verify identity based on your physical
characteristics, known as biometrics
Characteristics used include:
Signature (usually dynamic)
Fingerprint, hand geometry
face or body profile
Speech, retina pattern
Tradeoff between
false rejection (type I error)
false acceptance (type II error)
Cryptography and Network Security
471
Cryptography and Network Security
Secret Sharing
Xiang-Yang Li
Cryptography and Network Security
472
Threshold Scheme
A (t,w)-threshold scheme
Sharing key K among a set of w users
Any t users can recover the key
Any t-1 users can not do so
Schemes
Shamir’s scheme
Geometric techniques
Matroid theory
Cryptography and Network Security
473
Information Theory
The secret sharing is as large as the original
secret
This result is based in information theory, but can be understood
intuitively. Given t-1 shares, no information whatsoever can be
determined about the secret. Thus, the final share must contain as
much information as the secret itself.
All secret sharing schemes use random bits.
To distribute a one-bit secret among threshold t people, t-1 random
bits are necessary. The final share contains as much information as
the secret, but the other t-1 shares still provide relevant information
individually. This information cannot be the secret, so it must be
random.
Cryptography and Network Security
474
Shamir’s Scheme
Initialization phase
Dealer chooses a large prime number p
Dealer chooses w distinct xi from Zp
Gives value xi to person pi
Share distribution of key k from Zp
Dealer choose t-1 random number ai
Dealer computes yi=f(xi)
Here f(x)=k+ajxj mod p
Dealer gives share yi to person pi
Cryptography and Network Security
475
Geometry View
Cryptography and Network Security
476
Simple (t,t) Sharing
Procedure
D secretly chooses t-1 random elements yi from Zn
D computes
Value yt=K- yj mod n
D distributes yi to person pi for all i
It is secure and easy
Number n can be any number
Easy to recover the key
Only t persons together can do so, assume yi random
Cryptography and Network Security
477
Blakley's Scheme
Secret is a point in an t-dimensional space
Dealer gives each user a hyper-plane
passing the secret point
Any t users can recover the common point
Cryptography and Network Security
478
Geometry View
Cryptography and Network Security
479
Avoid Cheating
Two major distinct weaknesses
Bogus values are undetectable.
Participants need not reveal their true share.
Even if a bogus value was detected, it
would not necessarily give any information
about the true value
One participant did not reveal its true
value after get the true values from other
one
Cryptography and Network Security
480
Ben-Or/Rabin Solution
Using Checking Vectors
For any two participants A and B
Dealer gives A (SA, YAB)
Dealer gives B (BAB, CAB)
Here CAB = BAB YAB+ SA mod p
SA is the secret share of A
A and B keep their values secret
B can use (BAB, CAB) to verify the value (SA, YAB) of A
Cryptography and Network Security
481
Avoid Cheating
Participant B can send A bogus value after
receive A’s value
Solution: bit transfer
Dealer gives A (SAi, YABi)
Dealer gives B (BABi, CABi)
Here CABi = BABi YABi+ SAi mod p
SAi is the ith bit of the secret share of A
Cryptography and Network Security
482
Cont.
Protocol
Participant A gives its value (SAi, YABi) to B
B verifies: CABi = BABi YABi+ SAi mod p
B then sends its value (SBi, YBAi) to A
A verifies: CBAi = BBAi YBAi+ SBi mod p
The protocol terminates whenever
One side detects cheating, or
All values transferred
Cryptography and Network Security
483
Chinese Remainder Theorem
Given a number m<n, and n=n1n2…nk,
Numbers ni and nj are coprimes
Let ai=m mod ni
Number n is public
Dealer delivers ai and ni to the ith participant
Then all k users can recover the number m
Why it is not a good secret sharing
scheme?
Is it computationally for any k-1 users to recover the
key if n is large?
Cryptography and Network Security
484
Recover method
Each user pre-computes
Ni=n/ni
Inverse of Ni: yi=Ni mod ni
Compute the product si=aiNiyi mod n
Recover the secret m
Each user submits si
Computes s1+s2+….+sk mod n
Cryptography and Network Security
485
Access Structure
Threshold scheme allows any t users to
recover key!
Access structure allows some subsets to
recover the key!
Example:
{{p1,p2,p4},{p1,p3,p4},{p2,p3}} among
p1,p2,p3,p4,p5 able to recover the key
Assume the accessing subset is minimized
No subset of any accessing subset is able to recover
Cryptography and Network Security
486
Monotone Circuit
Assign sharing for each accessing subset
p1
a1
p2
p3
p4
c1 k-c
1
a2
b1
k-a1-a2
b2
k
k-b1-b2
k
k
k
Cryptography and Network Security
487
Cont.
Distribution
(a1,b1) to p1
(a2,c1) to p2
(k-c1,b2) to p3
(k-a1-a2,k-b1-b2) to p4
The sharer needs know
The circuit used by dealer
Which shares corresponding to which wires
The shared value is secret
Cryptography and Network Security
488
Visual Secret Sharing
There is a secret picture to be shared
among n participants.
The picture is divided into n transparencies (shares)
such that
if any m transparencies are placed together, the picture
becomes visible
but if fewer than m transparencies are placed together,
nothing can be seen.
Cryptography and Network Security
489
Visual Secret Sharing
Such a scheme is constructed by viewing
the secret picture as a set of black and
white pixels and handling each pixel
separately.
The schemes are perfectly secure and easily
implemented without any cryptographic computation.
A further improvement allows each
transparency (share) to be an innocent
picture
For example, a picture of a landscape or a picture of a
building
thus concealing the fact of secret sharing
Cryptography and Network Security
490
Interactive Proof
Interactive proof is a protocol between
two parties in which one party, called the
prover, tries to prove a certain fact to the
other party, called the verifier
Often takes the form of a challengeresponse protocol
Cryptography and Network Security
491
cont
protocol in which one or more provers try
to convince another party, called the
verifier, that the prover(s) possess certain
true knowledge, such as the membership of
a string x in a given language, often with
the goal of revealing no further details
about this knowledge. The prover(s) and
verifier are formally defined as
probabilistic Turing machines with special
"interaction tapes" for exchanging
messages.
Cryptography and Network Security
492
Desired Properties
Desired properties of interactive proofs
Completeness: The verifier always accepts the proof if
the prover knows the fact and both the prover and the
verifier follow the protocol.
Soundness: Verifier always rejects the proof if prover
doesnot know the fact, and verifier follows protocol.
Zero knowledge: The verifier learns nothing about the
fact being proved (except that it is correct) from the
prover that he could not already learn without the
prover. In a zero-knowledge proof, the verifier cannot
even later prove the fact to anyone else.
Cryptography and Network Security
493
Typical Protocol
A typical round in a zero-knowledge proof
consists of a "commitment" message from the
prover, followed by a challenge from the
verifier, and then a response to the challenge
from the prover. The protocol may be
repeated for many rounds. Based on the
prover's responses in all the rounds, the
verifier decides whether to accept or reject
the proof.
Cryptography and Network Security
494
An example
Ali Baba’s Cave
Cryptography and Network Security
495
Cont.
Alice wants to prove to Bob that
she knows the secret words to open the portal at CD
but does not wish to reveal the secret to Bob.
In this scenario, Alice’s commitment is to go to C or D.
Cryptography and Network Security
496
Proof Protocol
A typical round in the proof proceeds as
follows:
Bob goes to A, waits there while Alice goes to C or D.
Bob then asks Alice to appear from either the right side
or the left side of the tunnel.
If Alice does not know the secret words
there is only a 50 percent chance that she will come
out from the right tunnel.
Bob will repeat this round as many times as he desires
until he is certain that Alice knows the secret words.
No matter how many times that the proof repeats, Bob
does not learn the secret words.
Cryptography and Network Security
497
Graph Isomorphism
Problem Instance
Two graphs G1=(V1,E1) and G2=(V2,E2)
Question
Is there a bijection f from V1 to V2, so (u,v)E1 implies
that (f(u),f(v))E2
If such bijection exists, then graphs G1 and G2 are said
to be isomorphic
If such bijection does not exist, then graphs G1 and G2
are said to be non-isomorphic
Cryptography and Network Security
498
Graph Non-isomorphism
Input: graphs G1 and G2 over {1,2,…n}
Prover want to prove
G1 and G2 are not isomophic
Assumption
Prover has unbounded computational power
Verifier has limited computational power
Cryptography and Network Security
499
Proof Protocol
Protocol (repeated for n rounds)
Verifier
Randomly chooses i=1 or 2
Selects a random permutation f and compute H to be
the image of Gi under f, sends H to prover
Prover
Determines the value j such that Gj is isomorphic to H
Sends j to verifier
Verifier checks if j=i
If equal for n rounds, then accepts the proof
Cryptography and Network Security
500
Correctness and Soundness
Correctness
If G1 and G2 are not isomorphic, then for any round,
there is only one graph of G1, G2 that could produce H
under a permutation f
So if the verifier knows non-isomorphism, then each
round a correct j will be computed
Soundness
If the verifier does not know (G1 and G2 are
isomorphic), then each round two answers possible, and
it has half chance to get the correct i chosen by the
prover.
Cryptography and Network Security
501
Graph Isomorphism
Input: graphs G1 and G2 over {1,2,…n}
Prover want to prove
G1 and G2 are isomophic
Assumption
Prover has unbounded computational power
Verifier has limited computational power
Cryptography and Network Security
502
Proof Protocol
Protocol (repeated for n rounds)
Prover
Selects a random permutation f and compute H to be the
image of G1 under f, sends H to prover
Verifier
Randomly chooses i=1 or 2, sends it to prover
Prover
Computes the permutation g such that H is the image of Gj
under g, and sends g to verifier
Verifier
checks if H is the image of Gj under g
If yes for n rounds, then accepts the proof
Cryptography and Network Security
503
Correctness and Soundness
Correctness
If G1 and G2 are isomorphic, and the verifier knows
how to find the permutation between G1 and G2, then
each round a correct g will be computed
Soundness
If the verifier does not know (G1 and G2 are nonisomorphic or the permutation between G1 and G2),
then each round prover can deceive the verifier is to
guess the value i chosen by the verifier
Cryptography and Network Security
504
Perfect Zero-Knowledge
The graph isomorphism proof is ZKP
All information seen by the verifier is the same as
generated by a random simulator
Define transcript of the proof as
t=(G1,G2,(H1,i,g1),(H2,i,g2),….(Hn,i,gn))
Anyone can generate the transcript without knowing
which permutation carries G1 to G2
Hence the verifier gains nothing by knowing the
transcript (I.e., the proof history)
Cryptography and Network Security
505
ZKP for Verifier
Perfect Zero-knowledge for verifier
Suppose we have a poly-time interactive proof system
and a poly-time simulator S. Let T be all yes-instance
transcripts and let F be all transcripts generated by S.
For any transcript t if
Pr(t occurs in T)=Pr(t occurs in F)
We say the interactive proof system are perfect zeroknowledge for the verifier
Cryptography and Network Security
506
Isomorphism Proof: ZKP-verifier
Graph isomorphism is a perfect zero-
knowledge for verifier
A triple (H,i,g). There are 2n! valid triples.
All triples (H,i,g) occurs equiprobable in some
transcript
Here, assume that both the verifier and the prover
are honest
Both of them randomly chooses parameters that
supposed to be chosen randomly
Cryptography and Network Security
507
Cheating Verifier
What happened if verifier does not follow
the protocol (does not choose i randomly)
Transcript produced by ZKP is not same as that
produced by the random simulator anymore
The verifier may gain some information due to this
imbalance
But, there is another expected poly-time simulator to
generate the same transcript
Hence, the verifier still gains nothing
Cryptography and Network Security
508
Perfect Zero-Knowledge
Definition
Suppose we have a poly-time interactive proof system,
a poly-time algorithm V to generate random numbers
by verifier, and a poly-time simulator S. Let T be all
yes-instance transcripts (depending on V) and let F be
all transcripts generated by S and V. For any transcript t
if
Pr(t occurs in T)=Pr(t occurs in F)
We say the interactive proof system are perfect zeroknowledge
Cryptography and Network Security
509
Forging Simulator
Initial transcript t=(G1,G2), repeat n rounds
Let old-state=state(V), repeat follows
Chooses ij from {1,2} randomly
Chooses gj to be a random permutation over {1,...n}
Compute Hj to be the image of Gi under g
Call V with input Hj, obtaining a challenge ij’
If ij=ij’, then concatenate (Hj, ij, gj) onto the end of t
Else reset V by state(V)=old-state
Until ij=ij’
Cryptography and Network Security
510
Perfect Zero-knowledge
The graph isomorphism is perfect ZKP
The expected running time of simulator is 2n
For the kth round of the interactive proof system
Let pk be the probability that verifier chooses i=1
Then (H,1,g) occurs in actual transcript with pk/n!,
(H,2,g) occurs in actual transcript with (1-pk)/n!
For simulator, when it terminates the simulation for
the kth round, same probability distribution for (H,1,g)
and (H,2,g)
Therefore, all transcripts by simulator or actual has
the same probability distribution
Cryptography and Network Security
511
Quadratic Residue
Fiat-Shamir Identification
Question
Given integer n=pq, here p, q are primes.
Prover wants to prove
Integer x is a quadratic residue mod n
In other words, knows u so x=u2 mod n
Quadratic residue is hard to solve if do not knowing the
factoring of n
Cryptography and Network Security
512
Proof Protocol
Repeat the following for log2n times
Prover
Chooses random v less than n and computes y=v2 mod
n. Sends y to verifier
Verifier
Chooses a random I from {0,1}, sends it to prover
Prover
Computes z=u2v mod n, sends z to verifier
Verifier
Checks if z2=xiy mod n
Accepts the proof if equation holds all log2n rounds
Cryptography and Network Security
513
Cont
Correctness
Show that verifier will accept the prover if indeed
knows
Soundness
Show
that verifier will detect the prover if it does not
know with a good probability
Zero-knowledge
Show that verifier gets nothing from the protocol
Cryptography and Network Security
514
Guillou Quisquater Protocol
The GQ protocol is an extension of the Fiat
Shamir protocol that limits the number t of
rounds required.
One Time Set-up:
1. A trusted authority T selects two random
primes p and q and forms a modulus n = p · q.
2. T defines a public exponent v > 4 with gcd(v,
(p-1)(q -1) = 1 so that T can compute s = v-1
mod (p-1) (q-1).
3. T publishes parameters n and v.
Cryptography and Network Security
515
Cont.
Selection of per-user parameters:
1. Each entity A has a unique identification
Id(A). Everyone can calculate a value J(A)
= f(Id(A)) mod n (the redundant identity).
2. T gives to each entity A the secret data
secret(A) = J(A)-s, which it can calculate.
Cryptography and Network Security
516
Cont.
Protocol: A proves her identity to B using t rounds, each
1.
2.
3.
4.
of which consists of:
A selects a random secret r and sends her identity Id(A)
and x = rv mod n to B.
B selects a random challenge e in {1, 2, ... , v}.
A computes and sends the following response to B: y = r ·
secret(A)e mod n.
B receives y, constructs J(A) = f(Id(A)) mod n, computes
z = J(A)eyv, and accepts this round if z = x mod n.
In this protocol, v determines the security level. In Fiat
Shamir, v = 2 and there are many rounds. A fraudulent
claimant can defeat the protocol by correctly guessing
the challenge e (with a 1 in v chance.) GQ seems secure,
because we need to extract v-roots modulo n.
Cryptography and Network Security
517
Discrete Logarithm
Question:
Prover wants to prove to verifier that he knows x such
that y=gx mod p .
Here g, y, and p are public information
Prover does not want to publicize the value of x.
Cryptography and Network Security
518
Proof Protocol
Repeat the following for log2n times
Prover
Chooses random j < p-1 and computes r=gj mod p.
Sends r to verifier
Verifier
Chooses a random i from {0,1}, sends it to prover
Prover
Computes h=i x +j mod p-1, sends h to verifier
Verifier
Checks if gh=yir mod n
Accepts the proof if equation holds all log2n rounds
Cryptography and Network Security
519
Cont
Correctness
Show that verifier will accept the prover if indeed
knows
Soundness
Show
that verifier will detect the prover if it does not
know with a good probability
Zero-knowledge
Show that verifier gets nothing from the protocol
Cryptography and Network Security
520
Bit Commitments
Bit commitment
Sometimes, it is desirable to give someone a piece of
information, but not commit to it until a later date. It
may be desirable for the piece of information to be held
secret for a certain period of time.
Example: stock up and down
Cryptography and Network Security
521
Properties
Bit commitment scheme
The sender encrypts the b in some way
The encrypted form of b is called blob
Scheme f: (X,b)Y
Properties
Concealing: verifier cannot detect b from f(x,b)
Binding: sender can open the blob by revealing x
Hence, the sender must use random x to mask b
Cryptography and Network Security
522
Methods
One can choose any encryption method E
Function f((x0,k),b)=Ek((x0,b))
Need supply decryption k to reveal b
Assume the decryption method D is known
Choose any integer n=pq, p and q are large
primes
Function f(x,b)=mbx2 mod n
Goldwasser-Micali Scheme
Here n=pq, m is not quadratic residule, m,n public
mx12 mod n x22 mod n
So sender can not change mind after commitment
Cryptography and Network Security
523
Coin Flip
Even protocols
Alice has a coin flip result i or j
Bob wants to guess the result
Alice has a message M that is commitment
If bob guesses correct, Bob should have M received
Alice starts with 2 pairs of public keys (Ei,Di) and
(Ej,Dj)
Bob starts with a symmetric encryption S and a key k
Cryptography and Network Security
524
Protocol
Procedure
Alice sends Ei, Ej to Bob
Bob guess h and sends y=Eh(k) to Alice
Alice computes p=Dj(y) and sends the encryption z of
M by p using S to Bob
Bob decrypts the encryption z using S and key k
If the guess is correct, then Bob gets the commitment
Cryptography and Network Security
525
Oblivious Transfer
What is oblivious transfer
Alice wants to send Bob a secret in such a way that Bob
will know whether he gets it, but Alice won't. Another
version is where Alice has several secrets and transfers
one of them to Bob in such a way that Bob knows what
he got, but Alice doesn't. This kind of transfer is said to
be oblivious (to Alice).
Cryptography and Network Security
526
Transfer Factoring
By means of RSA, oblivious transfer of any
secret amounts to oblivious transfer of the
factorization of n=pq
Bob chooses x and sends x2 mod n to Alice
Alice (who knows p,q) computes the square roots x,x,y,-y of x2 mod n and sends one of them to Bob. Note
that Alice does not know x.
If Bob gets one of y or -y, he can factor n. This means
that with probability 1/2, Bob gets the secret. Alice
doesn't know whether Bob got one of y or -y because
she doesn't know x.
Cryptography and Network Security
527
Factoring
If one knows x and y such that
1) x2=y2 mod n
2) 0<x,y<n, xy and x+y0 mod n
Number n is the production of two primes
Then n can be factored
First gcd(x+y,n) is a factor of n
And gcd(x-y,n) is a factor of n
Cryptography and Network Security
528
Quadratic Solution
Given n=p, and a is a quadratic residue
Then there is two positive integers x less than n
Such that x2=a mod n
Given n=pq, and a is a quadratic residue
Then
there is four positive integers x less than n
Such that x2=a mod n
Cryptography and Network Security
529
Oblivious Transfer of Message
Alice has a message M, bob wants to get M
through oblivious transfer
Alice does not know if Bob get M or not
Bob knows if he gets it or not
Bob gets M with probability ½
Coin flipping can be used to achieve this
Cryptography and Network Security
530
Contract Signing
It requires two things
Commitment: after certain point, both parties are bound
by the contract, until then, neither is
Unforgeability: it must be possible for either party to
prove the signature of the other party
With Pen and Paper
Two party together, face to face
Sign simultaneously (or one character by one)
Cryptography and Network Security
531
Remote Contract Signing
Simple one
Alice generate a signature, divided into SL, SR
Alice randomly select two keys KL, KR
Encrypt the signatures SL, SR
Transfer encrypted SL,SR to Bob
Obliviously transfer KL, KR to bob
Bob gets one, but Alice does not know which one
Bob decrypts the encrypted SL or SR
Verify the decrypted signature, if invalid, stop
Alice sends the ith bits of keys KL and KR to Bob
Here i=1 to the length of the keys
Cryptography and Network Security
532
Cont.
The protocol will be conducted by Bob also
What is the chance of Alice to cheat successfully?
Alice can guess which key will be transferred
obliviously ---(1/2 chance)
Then send wrong signature for the other half or send
the wrong key of the other half
Bob can not detect it if Alice can guess which key Bob
got
How about Alice stop prematurely?
One bit advance over Bob
Enhanced protocol
Use many pair of keys and signatures instead of one
Cryptography and Network Security
533
Cryptography and Network Security
Pseudo-random Number
Xiang-Yang Li
Cryptography and Network Security
534
Random number, Pseudorandom
The outputs of pseudorandom number
generators are not truly random
they only approximate some of the properties of
random numbers.
"Anyone who considers arithmetical methods of
producing random digits is, of course, in a state of
sin.”--- John von Neumann
Truely random numbers can be generated using
hardware random number generators
Cryptography and Network Security
535
Randomness Definition
Chaitin-Kolmogorov randomness (also called
algorithmic randomness)
a string of bits is random if and only if it is shorter than
any computer program that can produce that string
this basically means that random strings are those
that cannot be compressed.
Statistical Randomness
A numeric sequence is said to be statistically random
when it contains no recognizable patterns or
regularities;
sequences such as the results of an ideal die roll, or
the digits of Pi (as far as we can tell) exhibit
statistical randomness.
Cryptography and Network Security
536
Inherent non-randomness
Because any PRNG run on a deterministic computer
(contrast quantum computer) is deterministic, its
output will inevitably have certain properties that
a true random sequence would not exhibit.
guaranteed periodicity—it is certain that if the generator uses only
a fixed amount of memory then, given a sufficient number of
iterations, the generator will revisit the same internal state twice,
after which it will repeat forever. A generator that isn't periodic can
be designed, but its memory requirements would grow as it ran. In
addition, a PRNG can be started from an arbitrary starting point, or
seed state, and will always produce an identical sequence from that
point on.
Cryptography and Network Security
537
cont
In practice, many PRNGs exhibit artifacts which can
cause them to fail statistically significant tests. These
include, but are certainly not limited to:
Shorter than expected periods for some seed states
(not full period)
Poor dimensional distribution
Successive values are not independent
Some bits may be 'more random' than others
Lack of uniformity
Cryptography and Network Security
538
Pseudo-random Bit Generator
Several applications
Key generation
Some encryption algorithms, or one-time pad
Let l>k be integers
f: Z2k Z2l computable in poly-time
Then f called (k,l)-pseudo-random bit generator
The input s0 Z2k is called the seed
Output f(s0) is called the pseudo-random string
Function
Cryptography and Network Security
539
Desired Properties
Three important properties:
Unbiased (uniform distribution):
All values of whatever sample size is collected are
equiprobable
Unpredictable (independence):
It is impossible to predict what the next output will
be, given all the previous outputs, but not the internal
"hidden" state.
Irreproducible:
Two of the same generators, given the same starting
conditions, will produce different outputs.
Cryptography and Network Security
540
Desired Properties
Usually when a person says
A "good" pseudo-random number generator
they mean it is unbiased.
A "true" PRNG
they usually mean it's irreproducible
A "cryptographically strong" PRNG
they mean it's unpredictable
Very rarely they mean it's all threes
Cryptography and Network Security
541
More Properties
Long period
The generator should be of long period
Fast computation
The generator should be reasonably fast
Security
The generator should be secure
What is security level of PRNG?
Cryptography and Network Security
542
Security
A PRNG suitable for cryptographic applications is
called a cryptographically secure PRNG (CSPRNG).
Its output should not only pass all statistical tests for randomness
but satisfy some additional cryptographic requirements.
Used in many aspects of cryptography require random numbers,
for example:
Key generation
Nonces
Salts in certain signature schemes, (ECDSA, RSASSA-PSS).
One-time pads
Cryptography and Network Security
543
CSPRNG
CSPRNG requirements fall into two groups:
their statistical properties are good (passing tests of randomness),
they hold up well in case of attack, even when (part of) their secrets are
revealed.
A CSPRNG should satisfy the 'next-bit test'.
Given the first l bits of a random sequence there is no polynomial-time
algorithm that can predict the next bit with probability of success
significantly higher than 1/2.
It has been proven that a generator passing the next-bit test will pass all
other polynomial-time statistical tests for randomness.
should withstand state compromise extensions.
That is, in the unfortunate case that part or all of the state has been
revealed (or guessed correctly), it should be impossible to reconstruct
the stream of random numbers prior to the incident. Also if there is an
input of entropy, it should be infeasible to use knowledge of the state to
predict future conditions of the state.
Cryptography and Network Security
544
Example
the CSPRNG being considered produces
output by computing some function of the
next digit of pi (ie, 3.1415...),
it may well be random as pi appears to be a random
sequence.
However, this does not satisfy the next-bit test, and
thus is not cryptographically secure.
There exists an algorithm that will predict the next bit.
Cryptography and Network Security
545
Design
divide designs of CSPRNGs into classes:
those based on block ciphers;
those based upon hard mathematical problems, and
special-purpose designs.
Cryptography and Network Security
546
Designs based on cryptographic
primitives
Designs based on cryptographic primitives
A secure block cipher can also be converted into a CSPRNG by running
it in counter mode.
This is done by choosing an arbitrary key and encrypting a zero, then
encrypting a 1, then encrypting a 2, etc. The counter can also be
started at an arbitrary number other than zero. Obviously, the period
will be 2n for an n-bit block cipher; equally obviously, the initial
values (i.e. key and 'plaintext') must not become known to an attacker
lest, however good this CSPRNG construction might be otherwise, all
security be lost.
A cryptographically secure hash of a counter might
also act as a good CSPRNG in some cases.
it is necessary that the initial value of this counter is random and secret.
If the counter is a bignum, then CSPRNG could have an infinite period.
Cryptography and Network Security
547
DES Based Generator
ANSI X9.17 PRNG (used by PGP,..)
Inputs: two pseudo-random inputs
one is a 64-bit representation of date and time
The other is 64-bit seed values
Keys: three 3DES encryptions using same keys
Output:
a 64-bit pseudorandom number and
A 64-bit seed value for next-round use
Cryptography and Network Security
548
ANSI X9.17
K1,K2
DT
EDE
EDE
Si+1
Si
EDE
Ri
Cryptography and Network Security
549
Linear Congruential Generator
Protocol
Let M be an integer and a, b less than M
Let k be number of bits of M
Integer l is between k+1 and M-1
Let s0 be a seed less than M
Define si=asi-1+b mod M
Then the ith random bit is si mod 2
It is not proved to be secure
Cryptography and Network Security
550
Parameter Setting
Not all a, b are good and m should be large
For example, m is a large prime number
For fast computation, usually m=231-1
And b is set to 0 often
For this m, there are less than 100
integers a
It generates all numbers less than m
The generated sequences appear to be random
One such a=7516807
Used in IBM 360 family of computers
Cryptography and Network Security
551
RSA Generator
Protocol
Let p, q be two k/2 bits primes and define n=pq
Integer b: gcd(b, (n))=1
Public: n, b; Private p,q
A seed s0 with k bits
Sequence si+1=sib mod n
Then the ith random bit is si mod 2
It is proved to be secure!
Cryptography and Network Security
552
BBS Generator
Blum-Blum-Shub Generator
Let p, q be two k/2 bits primes and define n=pq
Here p=q=3 mod 4
this guarantees that each quadratic residue has one
square root which is also a quadratic residue
gcd(φ(p-1),
φ(q-1)) should be small
this makes the cycle length large.
Let QR(n) be all quadratic residues modulo n
Public: n; Private p,q
A seed s0 with k bits from QR(n)
Sequence si+1=si2 mod n
Then the ith random bit is si mod 2
Cryptography and Network Security
553
Cont on BBS
Provably “secure”
When the primes are chosen appropriately,
and O(log log n) bits of each Si are output,
then in the limit as n grows large, distinguishing the
output bits from random will be at least as difficult as
factoring n.
However,
it's theoretically possible that a fast algorithm for
factoring will someday be found, so BBS is not yet
guaranteed to be secure.
Cryptography and Network Security
554
Discrete Logarithm Generator
Protocol
Let p be a k-bit prime,
Let be primitive element modulo p
A seed s0 is any non-zero integer less than p
Define si+1 = si mod p
Then the ith random bit is
1 if si is larger than p/2
0 if si is less than p/2
Cryptography and Network Security
555
Standards
A number of designs of CSPRNGs have
been standardized. They can be found in:
FIPS 186-2
ANSI X9.17-1985 Appendix C
ANSI X9.31-1998 Appendix A.2.4
ANSI X9.62-1998 Annex A.4
Cryptography and Network Security
556
Network Security
Cryptography and Network Security
557
Topics to be covered
Applications
Email security
www security
Malicious software
Networks
Wireless LAN security 802.11
IPsec
Firewall
Intrusions
Cryptography and Network Security
558
Cryptography and Network Security
Email Security
Xiang-Yang Li
Cryptography and Network Security
559
Electronic Mail Security
Despite the refusal of VADM Poindexter and LtCol North to
appear, the Board's access to other sources of information
filled much of this gap. The FBI provided documents taken from
the files of the National Security Advisor and relevant NSC
staff members, including messages from the PROF system
between VADM Poindexter and LtCol North. The PROF messages
were conversations by computer, written at the time events
occurred and presumed by the writers to be protected from
disclosure. In this sense, they provide a first-hand,
contemporaneous account of events.
—The Tower Commission Report to President Reagan on the
Iran-Contra Affair, 1987
Cryptography and Network Security
560
Email Security
email is one of the most widely used and
regarded network services
currently message contents are not secure
may be inspected either in transit
or by suitably privileged users on destination system
Cryptography and Network Security
561
Email Security Enhancements
confidentiality
protection from disclosure
authentication
of sender of message
message integrity
protection from modification
non-repudiation of origin
protection
from denial by sender
Cryptography and Network Security
562
Pretty Good Privacy (PGP)
widely used de facto secure email
developed by Phil Zimmermann
selected best available crypto algs to use
integrated into a single program
available on Unix, PC, Macintosh and Amiga
systems
originally free, now have commercial
versions available also
Cryptography and Network Security
563
PGP
Five services
Authentication, confidentiality, compression, email
compatibility, segmentation
Functions
Digital
signature
Message encryption
Compression
Email compatibility
segmentation
Cryptography and Network Security
564
PGP Operation – Authentication
1. sender creates a message
2. SHA-1 used to generate 160-bit hash code of
message
3. hash code is encrypted with RSA using the
sender's private key, and result is attached to
message
4. receiver uses RSA or DSS with sender's public
key to decrypt and recover hash code
5. receiver generates new hash code for message
and compares with decrypted hash code, if
match, message is accepted as authentic
Cryptography and Network Security
565
PGP Operation – Confidentiality
1.
2.
3.
4.
5.
sender generates message and random 128-bit
number to be used as session key for this
message only
message is encrypted, using CAST-128 /
IDEA/3DES with session key
session key is encrypted using RSA with
recipient's public key, then attached to message
receiver uses RSA with its private key to decrypt
and recover session key
session key is used to decrypt message
Cryptography and Network Security
566
PGP Operation – Confidentiality &
Authentication
uses both services on same message
create signature & attach to message
encrypt both message & signature
attach RSA encrypted session key
Cryptography and Network Security
567
PGP Operation – Compression
by default PGP compresses message after
signing but before encrypting
so can store uncompressed message & signature for
later verification
& because compression is non deterministic
uses ZIP compression algorithm
Cryptography and Network Security
568
PGP Operation – Email Compatibility
when using PGP will have binary data to
send (encrypted message etc)
however email was designed only for text
hence PGP must encode raw binary data
into printable ASCII characters
uses radix-64 algorithm
maps 3 bytes to 4 printable chars
also appends a CRC
PGP also segments messages if too big
Cryptography and Network Security
569
PGP Operation – Summary
Cryptography and Network Security
570
Segmentation & Reassembly
Email systems impose maximum length
50 Kb, for example
PGP provides automatic segmentation
Done after all other operations
Thus only one session key needed
Cryptography and Network Security
571
Key management
Generating unpredictable session keys
Identifying keys
Multiple public, private key pairs for a user
Maintain keys
Its own public, private keys of a PGP entity
Public keys of correspondents
Cryptography and Network Security
572
Session Key Generation
Algorithm used: CAST-128
Input to CAST-128
A 128-bit key
Two 64 bits plaintexts to be encrypted
Output using cipher feedback mode
Generates 2 64-bits ciphers form session key
Plaintexts are from 128-bits randomized
number
Based on key stroke of user (timing and actual keys)
Then combined with previous session key
Cryptography and Network Security
573
Key Identifiers
Receiver has multiple public keys
How to know which private key is proper?
Approach
Sending the least significant 64 bits as key ID
Need send the receiver’s public key ID used for
encrypting the session key
Need send the sender’s public key ID, whose
corresponding private key used for signature
Cryptography and Network Security
574
Key Rings
Private key rings
Timestamp, Key ID, public key, encrypted private key,
user ID
Public key rings
Timestamp,
Key ID, public key, owner trust, user ID,
key legitimacy, signature, signature trust
Cryptography and Network Security
575
Public Key Management
A public key attributed to B may belong to
C
C
can send messages to A forge B’s sig
C can read any encrypted message to B
Approach to true public key
Physically get key from B
Obtain B’s key from mutual trusted authority
Using key legitimacy field
computed from the signature trust field and number
of certificates for the key
Cryptography and Network Security
576
Revoking Public Key
Reason
It is compromised: private key is open
Simply to avoid use of same key for a period
Approach
Owner
issues key revocation certificate, signed by
owner
Using corresponding private key to sign the certificate
Disseminate the certificate as widely and as quickly as
possible
Cryptography and Network Security
577
S/MIME (Secure/Multipurpose
Internet Mail Extensions)
security enhancement to MIME email
original Internet RFC822 email was text only
MIME provided support for varying content types and
multi-part messages
with encoding of binary data to textual form
S/MIME added security enhancements
have S/MIME support in various modern
mail agents: MS Outlook, Netscape etc
Cryptography and Network Security
578
S/MIME Functions
enveloped data
encrypted content and associated keys
signed data
encoded message + signed digest
clear-signed data
cleartext message + encoded signed digest
signed & enveloped data
nesting
of signed & encrypted entities
Cryptography and Network Security
579
S/MIME Cryptographic Algorithms
hash functions: SHA-1 & MD5
digital signatures: DSS & RSA
session key encryption: ElGamal & RSA
message encryption: Triple-DES, RC2/40
and others
have a procedure to decide which
algorithms to use
Cryptography and Network Security
580
S/MIME Certificate Processing
S/MIME uses X.509 v3 certificates
managed using a hybrid of a strict X.509
CA hierarchy & PGP’s web of trust
each client has a list of trusted CA’s certs
and own public/private key pairs & certs
certificates must be signed by trusted
CA’s
Cryptography and Network Security
581
Certificate Authorities
have several well-known CA’s
Verisign one of most widely used
Verisign issues several types of Digital IDs
with increasing levels of checks & hence
trust
Class
1
2+
3+
Identity Checks
Usage
name/email check
web browsing/email
enroll/addr check
email, subs, s/w validate
ID documents e-banking/service access
Cryptography and Network Security
582
Email SPAM
Spam is flooding the Internet with many
copies of the same message, in an attempt
to force the message on people who would
not otherwise choose to receive it. Most
spam is commercial advertising, often for
dubious products, get-rich-quick schemes,
or quasi-legal services. Spam costs the
sender very little to send -- most of the
costs are paid for by the recipient or the
carriers rather than by the sender
Cryptography and Network Security
583
Email Spam
E-mail spam has existed since the beginning
of the Internet, and has grown to about 90
billion messages a day, although about 80%
is sent by fewer than 200 spammers.
Botnets, virus infected computers, account
for about 80% of spam.
E-mail addresses are collected from
chatrooms, websites, newsgroups, and
viruses which harvest users address books,
and are sold to other spammers
Cryptography and Network Security
584
Anti-Spam Techs
Some popular methods for filtering and
refusing spam include
e-mail filtering based on the content of the e-mail,
DNS-based blackhole lists (DNSBL), greylisting,
spamtraps, enforcing technical requirements,
checksumming systems to detect bulk email, and by
putting some sort of cost on the sender via a Proof-ofwork system or a micropayment.
Each method has strengths and weaknesses and each is
controversial due to its weaknesses.
Cryptography and Network Security
585
Filtering Methods
Bayesian spam filtering
CRM114
dSPAM
Markovian discrimination
POPFile
Policyd-weight Postfix policy-daemon before SMTP DATA
Procmail is an MDA (Mail Delivery Agent) for Unix systems.
Maildrop is an MDA (Mail Delivery Agent) for Unix systems.
Sendmail supports libmilter for mail filtering
Sieve (mail filtering language) is an RFC standard for
describing mail filters
SpamAssassin
Anti-Spam SMTP Proxy
information filtering
White list#E-mail whitelists
Cryptography and Network Security
586
Summary
have considered:
secure email
PGP
S/MIME
Cryptography and Network Security
587
Cryptography and Network Security
Security on WWW
Xiang-Yang Li
Cryptography and Network Security
588
Introduction
Introduction
Presentation of SSL
The inner workings of SSL
• Attacks on SSL
Presentation of S-HTTP
• Comparison with SSL/TLS
• Attacks on S-HTTP
Other aspects of Web security
• TLS
• IPSec, Kerberos, SET
Conclusion
•
Cryptography and Network Security
589
Web Security
Web now widely used by business,
government, individuals
but Internet & Web are vulnerable
have a variety of threats
integrity
confidentiality
denial of service
authentication
need added security mechanisms
Cryptography and Network Security
590
SSL (Secure Socket Layer)
transport layer security service
originally developed by Netscape
version 3 designed with public input
subsequently became Internet standard
known as TLS (Transport Layer Security)
uses TCP to provide a reliable end-to-end
service
SSL has two layers of protocols
Cryptography and Network Security
591
Location of SSL
Application Layer
Secure Socket Layer
(SSL)
Transmission Control Protocol
(TCP)
SSL is build on top of
TCP
Provides a TCP like
interface
In theory can be used
by all type of
applications in a
transparent manner
Internet Protocol
(IP)
Cryptography and Network Security
592
SSL Architecture
Cryptography and Network Security
593
SSL Architecture
SSL session
an association between client & server
created by the Handshake Protocol
define a set of cryptographic parameters
may be shared by multiple SSL connections
SSL connection
a transient, peer-to-peer, communications link
associated with 1 SSL session
Cryptography and Network Security
594
SSL Record Protocol
confidentiality
using symmetric encryption with a shared secret key
defined by Handshake Protocol
IDEA, RC2-40, DES-40, DES, 3DES, Fortezza, RC440, RC4-128
message is compressed before encryption
message integrity
using a MAC with shared secret key
similar to HMAC but with different padding
Cryptography and Network Security
595
SSL Change Cipher Spec Protocol
one of 3 SSL specific protocols which use
the SSL Record protocol
a single message
causes pending state to become current
hence updating the cipher suite in use
Cryptography and Network Security
596
SSL Alert Protocol
conveys SSL-related alerts to peer entity
severity
warning or fatal
specific alert
unexpected message, bad record mac, decompression
failure, handshake failure, illegal parameter
close notify, no certificate, bad certificate,
unsupported certificate, certificate revoked,
certificate expired, certificate unknown
compressed & encrypted like all SSL data
Cryptography and Network Security
597
SSL Handshake Protocol
allows server & client to:
authenticate each other
to negotiate encryption & MAC algorithms
to negotiate cryptographic keys to be used
comprises a series of messages in phases
Establish Security Capabilities
Server Authentication and Key Exchange
Client Authentication and Key Exchange
Finish
Cryptography and Network Security
598
General purpose
1.Handshake
`
2. Data transmission
Two step process:
• Handshake : exchange private keys using a public key encryption
algorithm
• Data transmission: exchange the required data using a private key
encryption
Cryptography and Network Security
599
SSL Handshake Protocol
Cryptography and Network Security
600
handshake
`
Client
Client Hello
Server
Server Hello
Server Certificate
Server Hello Done
Client Key Exchange
Change Cipher Specification
Handshake Finished
Change Cipher Specifications
Handshake Finished
Cryptography and Network Security
601
hello
Client “Hello”:
• List of supported private
key encryptions +
• Client random number
Server “Hello”:
• Selected encryption
algorithm
• Server Random number
• Session ID
Server Certificate:
• Verify server’s identity
`
Client
Server
Client Hello
Server Hello
Server Certificate
Server Hello Done
Client Key Exchange
Change Cipher Specification
Handshake Finished
Change Cipher Specifications
Handshake Finished
Cryptography and Network Security
602
Key exchange
Client Key Exchange:
• Client
Generate second
random: Pre Master
Key
Send Pre Master Key
Calculate Master Key
Calculate Secret Key
Calculate MAC Key
•
Server
Calculate Master Key
Calculate Secret Key
Calculate MAC Key
`
Client
Server
Client Hello
Server Hello
Server Certificate
Server Hello Done
Client Key Exchange
Change Cipher Specification
Handshake Finished
Change Cipher Specifications
Handshake Finished
Cryptography and Network Security
603
Resumed based on Session Id
`
Client
Client Hello
Server
Server Hello
Change Cipher Specification
Handshake Finished
Change Cipher Specifications
Handshake Finished
Cryptography and Network Security
604
Certificate authority
Certificate Authority (CA) is a trusted
third party that helps identify the server.
How does everything work?
•
•
•
•
Server sends ID, public key to CA
CA creates and signs the server’s Certificate
Client receives the Certificate from Server
Client verifies the Certificate using the signature and
the CA’s public key
Cryptography and Network Security
605
MAC
MAC = Message Authentication Code
The initial message is split into fragments
For each fragment a “fingerprint” is
calculated using the MAC key
The fragment, fingerprint and record
header are encrypted and sent
Receiver checks the “fingerprint” using
MAC key to detect inconsistent messages
Cryptography and Network Security
606
Attacks on SSL
Certificate Injection Attack
•
•
The list of trusted Certificate Authorities is altered
Can be avoided by upgrading the OS or switching to a safer one.
Man in the Middle
•
Cipher Spec Rollback : regresses the public key encryption algorithms
Version Rollback : regression from SSL 3.0 to weaker SSL 2.0
Algorithm rollback : modify public encryption method
Truncation attack : TCP FIN|RST used to terminate connection
•
Can be avoided by randomly delaying the computations
•
Can be used on servers that accept small key sizes: 40 bits for symmetric
encryptions and 512 for the asymmetric one.
•
•
•
Timing attack
Brute force
Cryptography and Network Security
607
TLS (Transport Layer Security)
IETF standard RFC 2246 similar to SSLv3
with minor differences
in record format version number
uses HMAC for MAC
a pseudo-random function expands secrets
has additional alert codes
some changes in supported ciphers
changes in certificate negotiations
changes in use of padding
Cryptography and Network Security
608
TLS
TLS was developed by IETF to replace SSL version 3.
• Based on SSL version 3, with some changes:
• Replaced FORTEZZA key exchange option with DSS.
• Include the hash method HMAC used by IPSec for
authentication in IP headers.
• More differentiation between sub-protocols.
• TLS has mechanisms for backwards compatibility with SSL.
Cryptography and Network Security
609
TLS
TLS has about 30 possible cipher ‘suites’, combinations of
key exchange, encryption method, and hashing method.
• Key exchange includes: RSA, DSS, Kerberos
• Encryption includes: IDEA(CBC), RC2, RC4, DES, 3DES,
and AES
• Hashing: SHA and MD5
(Note: Some of the suites are intentionally weak export
versions.)
Cryptography and Network Security
610
Secure Electronic Transactions
(SET)
open encryption & security specification
to protect Internet credit card
transactions
developed in 1996 by Mastercard, Visa etc
not a payment system
rather a set of security protocols &
formats
secure communications amongst parties
trust from use of X.509v3 certificates
privacy by restricted info to those who need it
Cryptography and Network Security
611
SET Components
Cryptography and Network Security
612
SET Transaction
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
customer opens account
customer receives a certificate
merchants have their own certificates
customer places an order
merchant is verified
order and payment are sent
merchant requests payment authorization
merchant confirms order
merchant provides goods or service
merchant requests payment
Cryptography and Network Security
613
Dual Signature
customer creates dual messages
order information (OI) for merchant
payment information (PI) for bank
neither party needs details of other
but must know they are linked
use a dual signature for this
signed concatenated hashes of OI & PI
Cryptography and Network Security
614
Purchase Request – Customer
Cryptography and Network Security
615
Purchase Request – Merchant
Cryptography and Network Security
616
Purchase Request – Merchant
1.
2.
3.
4.
verifies cardholder certificates using CA sigs
verifies dual signature using customer's public
signature key to ensure order has not been
tampered with in transit & that it was signed
using cardholder's private signature key
processes order and forwards the payment
information to the payment gateway for
authorization (described later)
sends a purchase response to cardholder
Cryptography and Network Security
617
Payment Gateway Authorization
1.
2.
3.
4.
5.
6.
7.
8.
verifies all certificates
decrypts digital envelope of authorization block to obtain
symmetric key & then decrypts authorization block
verifies merchant's signature on authorization block
decrypts digital envelope of payment block to obtain
symmetric key & then decrypts payment block
verifies dual signature on payment block
verifies that transaction ID received from merchant
matches that in PI received (indirectly) from customer
requests & receives an authorization from issuer
sends authorization response back to merchant
Cryptography and Network Security
618
Payment Capture
merchant sends payment gateway a
payment capture request
gateway checks request
then causes funds to be transferred to
merchants account
notifies merchant using capture response
Cryptography and Network Security
619
A
B
C
D
C- Secure-HTTP
Presentation of S-HTTP
Designed by E. Rescorla and A. Schiffman
of EIT to secure HTTP connections
Proposed in 1994 but never used
commercially
Not to be confused with HTTPS: encrypts
HTTP messages at the application level
Security on the WWW
Cryptography and Network Security
620
A
B
C
D
C- Secure-HTTP
Location of S-HTTP
Secure-HTTP
Message encryption and
signature
Application Layer:
HTTP message
Transmission Control Protocol
(TCP)
HTTP-specific message
encryption
Can possibly be used
over a secure channel
Designed to be
compatible with HTTP
for handling at lower
layers
Internet Protocol
(IP)
Security on the WWW
Cryptography and Network Security
621
A
B
C
D
C- Secure-HTTP
S-HTTP vs. SSL/TLS
HTTP-specific vs. general purpose SSL (IMAPS,
POPS, LDAPS…)
Burden of encryption not on
transmission/reception but rather on message
production/unpacking
Similar set of available ciphers, plus added
capabilities for signing (DSS, RSA)
Very general specifications, leaving a lot to
implement and a potential for incompatible
implementations
Only one reference implementation in NCSA
Mosaic
Security on the WWW
Cryptography and Network Security
622
A
B
C
D
C- Secure-HTTP
S-HTTP vs. SSL/TLS: functionalities
Security Service
S-HTTP
SSL
Privacy
Public or private cryptosystem
Encryption of the complete HTTP
transaction
Symmetric key cryptosystem
Complete communication encryption
Integrity
Simple MAC or signing
MAC only
Authentication
Key management on the keys used,
or digital signature
During the initial public key
exchange (server auth. mandatory,
client auth. optional)
Non-repudiation
Digital signature
Not provided
S-HTTP can make use of key management
Non-repudiation is not provided by SSL
Signing is optional, but a major attraction to S-HTTP
Security on the WWW
Cryptography and Network Security
623
A
B
C
D
C- Secure-HTTP
S-HTTP vs. SSL/TLS: proxy traversal
Proxy traversal: SSL connection
OR
cleartext
SSL tunnel
External
secure server
SSL tunnel
SSL-aware proxy
Enterprise environment
Proxy traversal: S-HTTP messaging
Encrypted data
Authentication
External
secure server
Security on the WWW
S-HTTP-aware proxy
Enterprise environment
Cryptography and Network Security
624
A
B
C
D
C- Secure-HTTP
S-HTTP inner working
Message-based encryption
Superset of HTTP: “outer” envelope
Specific headers added
S-HTTP message
S-HTTP headers
HTTP payload headers:
Security-Scheme, Encryption-Identity,
Certificate-Info… + regular HTTP headers
Request:
Secure*Secure-HTTP/1.2
Response:
Secure-HTTP/1.2 200 OK
HTTP message body
Security on the WWW
Cryptography and Network Security
625
A
B
C
D
C- Secure-HTTP
S-HTTP attacks
Basically the same as on SSL, since the ciphers are the same
Default values more secure in S-HTTP than SSL at the time
of proposal (e.g. DES vs. RC4)
S-HTTP generally stronger by design (more resilient to
proxy compromising)
More complex and wider specifications create a potential for
faulty implementations
No real-world use to field test the actual security of SHTTP
Security on the WWW
Cryptography and Network Security
626
A
B
C
D
D- Other protocols
HTTP Basic Authentication
HTTP has an authentication scheme as part of its original
protocol.
• Supported by almost all browsers and web servers.
• Password and username are sent in clear text
(base64 encoded) in the HTTP request message.
• Obviously not secure enough for sensitive information.
This scheme is being replaced by the slightly more secure
HTTP Digest Authentication, which sends a MD5 hash of the
password and other information.
Security on the WWW
Cryptography and Network Security
627
IPsec
IPSec is a security layer added to a computer’s protocol
stack in the kernel (Below TCP). It is invisible to the
application. It is implemented by adding additional
protocol numbers in the IP protocol field.
• Good for implementing a VPN.
• Packets can be either tunneled inside IPSec packets, or
Transported with only the data portion of the original
packet encrypted.
• Every IPSec end machine (which could be a LAN’s router)
must implement IPSec for it to work.
Cryptography and Network Security
628
Summary
have considered:
need for web security
SSL/TLS transport layer security protocols
de facto standard, versatile and low-level enough
to accommodate many types of payloads
SET secure credit card payment protocols
IPSec: true network-layer security for any applications
(not just the Web)
Kerberos: robust 2-way authentication framework with
emphasis on security manageability
Cryptography and Network Security
629
A
B
C
D
D- Conclusion
Web Security
• SSL/TLS: de facto standard, versatile and low-level
enough to accommodate many types of payloads
• S-HTTP: never took off, restricted to HTTP messages
• IPSec: true network-layer security for any
applications (not just the Web)
• Kerberos: robust 2-way authentication framework
with emphasis on security manageability
Security on the WWW
Cryptography and Network Security
630
Cryptography & Network Security
Malicious Software
XiangYang Li
Cryptography and Network Security
631
Malicious Software
What is the concept of defense: The parrying
of a blow. What is its characteristic feature:
Awaiting the blow.
—On War, Carl Von Clausewitz
Cryptography and Network Security
632
Viruses and Other Malicious Content
computer viruses have got a lot of publicity
one of a family of malicious software
effects usually obvious
have figured in news reports, fiction,
movies (often exaggerated)
getting more attention than deserve
are a concern though
Cryptography and Network Security
633
Malicious Software
Cryptography and Network Security
634
Trapdoors
secret entry point into a program
allows those who know access bypassing
usual security procedures
have been commonly used by developers
a threat when left in production programs
allowing exploited by attackers
very hard to block in O/S
requires good s/w development & update
Cryptography and Network Security
635
Logic Bomb
one of oldest types of malicious software
code embedded in legitimate program
activated when specified conditions met
eg presence/absence of some file
particular date/time
particular user
when triggered typically damage system
modify/delete
files/disks
Cryptography and Network Security
636
Trojan Horse
program with hidden side-effects
which is usually superficially attractive
eg game, s/w upgrade etc
when run performs some additional tasks
allows attacker to indirectly gain access they do not
have directly
often used to propagate a virus/worm or
install a backdoor
or simply to destroy data
Cryptography and Network Security
637
Zombie
program which secretly takes over another
networked computer
then uses it to indirectly launch attacks
often used to launch distributed denial of
service (DDoS) attacks
exploits known flaws in network systems
Cryptography and Network Security
638
Viruses
a piece of self-replicating code attached to
some other code
cf biological virus
both propagates itself & carries a payload
carries
code to make copies of itself
as well as code to perform some covert task
Cryptography and Network Security
639
Virus Operation
virus phases:
dormant – waiting on trigger event
propagation – replicating to programs/disks
triggering – by event to execute payload
execution – of payload
details usually machine/OS specific
exploiting features/weaknesses
Cryptography and Network Security
640
Virus Structure
program V :=
{goto main;
1234567;
subroutine infect-executable :=
{loop:
file := get-random-executable-file;
if (first-line-of-file = 1234567) then goto loop
else prepend V to file; }
subroutine do-damage :=
{whatever damage is to be done}
subroutine trigger-pulled :=
{return true if some condition holds}
main: main-program := {infect-executable;
if trigger-pulled then do-damage;
goto next;}
next:
}
Cryptography and Network Security
641
Types of Viruses
can classify on basis of how they attack
parasitic virus
memory-resident virus
boot sector virus
stealth
polymorphic virus
macro virus
Cryptography and Network Security
642
Macro Virus
macro code attached to some data file
interpreted by program using file
eg Word/Excel macros
esp. using auto command & command macros
code is now platform independent
is a major source of new viral infections
blurs distinction between data and program
files making task of detection much harder
classic trade-off: "ease of use" vs
"security"
Cryptography and Network Security
643
Email Virus
spread using email with attachment
containing a macro virus
cf Melissa
triggered when user opens attachment
or worse even when mail viewed by using
scripting features in mail agent
usually targeted at Microsoft Outlook mail
agent & Word/Excel documents
Cryptography and Network Security
644
Worms
replicating but not infecting program
typically spreads over a network
cf Morris Internet Worm in 1988
led to creation of CERTs
using users distributed privileges or by exploiting
system vulnerabilities
widely used by hackers to create zombie PC's,
subsequently used for further attacks, esp DoS
major issue is lack of security of permanently
connected systems, esp PC's
Cryptography and Network Security
645
Worm Operation
worm phases like those of viruses:
dormant
propagation
search for other systems to infect
establish connection to target remote system
replicate self onto remote system
triggering
execution
Cryptography and Network Security
646
Morris Worm
best known classic worm
released by Robert Morris in 1988
targeted Unix systems
using several propagation techniques
simple password cracking of local pw file
exploit bug in finger daemon
exploit debug trapdoor in sendmail daemon
if any attack succeeds then replicated self
Cryptography and Network Security
647
Recent Worm Attacks
new spate of attacks from mid-2001
Code Red
exploited bug in MS IIS to penetrate & spread
probes random IPs for systems running IIS
had trigger time for denial-of-service attack
2nd wave infected 360000 servers in 14 hours
Code Red 2
had backdoor installed to allow remote control
Nimda
used multiple infection mechanisms
email, shares, web client, IIS, Code Red 2 backdoor
Cryptography and Network Security
648
Virus Countermeasures
viral attacks exploit lack of integrity
control on systems
to defend need to add such controls
typically by one or more of:
prevention - block virus infection mechanism
detection - of viruses in infected system
reaction - restoring system to clean state
Cryptography and Network Security
649
Anti-Virus Software
first-generation
scanner uses virus signature to identify virus
or change in length of programs
second-generation
uses heuristic rules to spot viral infection
or uses program checksums to spot changes
third-generation
memory-resident programs identify virus by actions
fourth-generation
packages with a variety of antivirus techniques
eg scanning & activity traps, access-controls
Cryptography and Network Security
650
Advanced Anti-Virus Techniques
generic decryption
use CPU simulator to check program signature &
behavior before actually running it
digital immune system (IBM)
general
purpose emulation & virus detection
any virus entering org is captured, analyzed,
detection/shielding created for it, removed
Cryptography and Network Security
651
Behavior-Blocking Software
integrated with host O/S
monitors program behavior in real-time
eg file access, disk format, executable mods, system
settings changes, network access
for possibly malicious actions
if detected can block, terminate, or seek ok
has advantage over scanners
but malicious code runs before detection
Cryptography and Network Security
652
Summary
have considered:
various malicious programs
trapdoor, logic bomb, trojan horse, zombie
viruses
worms
countermeasures
Cryptography and Network Security
653
Cryptography & Network Security
Wireless LAN Security
Road to 802.11i
Xiangyang Li
Cryptography and Network Security
654
Contents
Introduction
Problem: 802.11b Not Secure!
Wired Equivalent Privacy – WEP
Types of Attacks
802.11b Proposed Solutions
802.1X
Wi-Fi Protected Access (WPA)
802.11i: The Solution
Conclusion
Cryptography and Network Security
655
Introduction
Popular in offices, homes and public spaces
(airport, coffee shop)
Most popular: 802.11b
Example: Yahoo! DSL Wireless Kit
Theoretical max @ 11Mbps
Operate at 2.4GHz band
DSSS/FSSS modulation – similar to CDMA phones
Cryptography and Network Security
656
Introduction
Standards: IEEE 802.11 Series
802.11b – 11Mbps @ 2.4GHz
802.11a – 54Mbps @ 5.7GHz band
802.11g – 54Mbps @ 2.4GHz band
802.1X – security add-on
802.11i – high security
Cryptography and Network Security
657
Problem: 802.11b Not Secure!
“No inherent security”
Wired Wireless media change was the objective
Wired Equivalent Privacy (WEP)
The only “security” built into 802.11
Uses RC4 Stream Cipher – in a bad way
Vulnerable to several types of attacks
Sometimes not even turned ON
Cryptography and Network Security
658
Wired Equivalent Privacy – WEP
RC4 stream cipher
Designed by Ron Rivest for RSA Security
Very simple
Initialization Vector (IV)
Shared Key
The issue is in the way RC4 is used
IV (24 bits) reuse and fixed key
Early versions used 40-bit key
128-bit mode effectively uses 104 bits
Cryptography and Network Security
659
Wired Equivalent Privacy – WEP
RC4 Key Stream Encryption (source:
http://mason.gmu.edu/~gharm/wireless.html)
Cryptography and Network Security
660
Types of Attacks
Attacks
Confidentiality
Integrity
Availability
Cryptography and Network Security
661
Types of Attacks
Attacks on Confidentiality
Traffic Analysis
Passive Eavesdropping
Very easy to do
Active
Eavesdropping
Unauthorized Access
Cryptography and Network Security
662
Types of Attacks
Attacks on Confidentiality and/or
Integrity
Man-In-The-Middle
Attacks on Integrity
Session Hijacking
Replay
Attacks on Availability
Denial
of Service
Cryptography and Network Security
663
802.11b Proposed Solutions
Virtual Private Network
Closed Network
Through the use of SSID
Ethernet MAC address control lists
Replace RC4 with block cipher
Don’t reuse IV
Automatic Key Assignment
Cryptography and Network Security
664
802.1X: Interim Solution
Port-based authentication
Not specific to wireless networks
Authentication servers
RADIUS
Client authentication
EAP
Cryptography and Network Security
665
802.1X Problems
802.1X still has problems
Extensible Authentication Protocol (EAP)
One-way authentication
Attacks
Man-in-Middle
Session Hijacking
Cryptography and Network Security
666
802.1X Proposed Solutions
Per-packet authenticity and integrity
Lots of overhead
Authenticity and integrity of EAPOL
messages
Two-way authentication
Cryptography and Network Security
667
Wi-Fi Protected Access (WPA)
Addresses issues with WEP
Key management
TKIP
Key expansion
Message Integrity Check
Software upgrade only
Compatible with 802.1X
Compatible with 802.11i
Cryptography and Network Security
668
802.11i
Finalized: June, 2004
Robust Security Network
Wi-Fi Alliance: WPA2
Improvements made
Authentication enhanced
Key Management created
Data Transfer security enhanced
Cryptography and Network Security
669
802.11i - Authentication
Authentication Server
Two-way authentication
Prevents man-in-the-middle attacks
Master Key (MK)
Pairwise Master Key (PMK)
Cryptography and Network Security
670
802.11i – Key Management
Key Types
Pairwise Transient Key
Key Confirmation Key
Key Encryption Key
Group Transient Key
Temporal Key
Cryptography and Network Security
671
802.11i – Key Management
Source: http://csrc.nist.gov/wireless/S10_802.11i%20Overview-jw1.pdf
Cryptography and Network Security
672
802.11i – Data Transfer
CCMP
Long term solution – mandatory for 802.11i
compliance
Latest AES encryption
Requires hardware upgrades
WRAP
Provided for early vendor support
TKIP
Carried over from WPA
Cryptography and Network Security
673
802.11i – Additional Enhancements
Pre-authentication
Roaming clients
Client Validation
Password-to-key mappings
Random number generation
Cryptography and Network Security
674
Conclusion
Basic 802.11b (with WEP)
Massive security holes
Easily attacked
802.1X
Good
interim solution
Allows use of existing hardware
Can still be attacked
Cryptography and Network Security
675
Conclusion
Wi-Fi Protected Access
Allows use of existing hardware
Compatible with 802.1X
Compatible with 802.11i
802.11i
May require hardware upgrades
Very secure
Nothing is ever guaranteed
Cryptography and Network Security
676
Cryptography & Network Security
IPsec
XiangYang Li
Cryptography and Network Security
677
IP Security
If a secret piece of news is divulged by a spy
before the time is ripe, he must be put to
death, together with the man to whom the
secret was told.
—The Art of War, Sun Tzu
Cryptography and Network Security
678
IP Security
have considered some application specific
security mechanisms
eg. S/MIME, PGP, Kerberos, SSL/HTTPS
however there are security concerns that
cut across protocol layers
would like security implemented by the
network for all applications
Cryptography and Network Security
679
IPSec
general IP Security mechanisms
provides
authentication
confidentiality
key management
applicable to use over LANs, across public
& private WANs, & for the Internet
Cryptography and Network Security
680
IPSec Uses
Cryptography and Network Security
681
Benefits of IPSec
in a firewall/router provides strong
security to all traffic crossing the
perimeter
is resistant to bypass
is below transport layer, hence transparent
to applications
can be transparent to end users
can provide security for individual users if
desired
Cryptography and Network Security
682
IP Security Architecture
specification is quite complex
defined in numerous RFC’s
incl. RFC 2401/2402/2406/2408
many others, grouped by category
mandatory in IPv6, optional in IPv4
Cryptography and Network Security
683
IPSec Services
Access control
Connectionless integrity
Data origin authentication
Rejection of replayed packets
a form of partial sequence integrity
Confidentiality (encryption)
Limited traffic flow confidentiality
Cryptography and Network Security
684
Security Associations
a one-way relationship between sender &
receiver that affords security for traffic
flow
defined by 3 parameters:
Security Parameters Index (SPI)
IP Destination Address
Security Protocol Identifier
has a number of other parameters
seq no, AH & EH info, lifetime etc
have a database of Security Associations
Cryptography and Network Security
685
Authentication Header (AH)
provides support for data integrity &
authentication of IP packets
end system/router can authenticate user/app
prevents address spoofing attacks by tracking sequence
numbers
based on use of a MAC
HMAC-MD5-96 or HMAC-SHA-1-96
parties must share a secret key
Cryptography and Network Security
686
Authentication Header
Cryptography and Network Security
687
Transport & Tunnel Modes
Cryptography and Network Security
688
Encapsulating Security Payload (ESP)
provides message content confidentiality &
limited traffic flow confidentiality
can optionally provide the same
authentication services as AH
supports range of ciphers, modes, padding
incl. DES, Triple-DES, RC5, IDEA, CAST etc
CBC most common
pad to meet blocksize, for traffic flow
Cryptography and Network Security
689
Encapsulating Security Payload
Cryptography and Network Security
690
Transport vs Tunnel Mode ESP
transport mode is used to encrypt &
optionally authenticate IP data
data protected but header left in clear
can do traffic analysis but is efficient
good for ESP host to host traffic
tunnel mode encrypts entire IP packet
add new header for next hop
good for VPNs, gateway to gateway security
Cryptography and Network Security
691
Combining Security Associations
SA’s can implement either AH or ESP
to implement both need to combine SA’s
form a security bundle
have 4 cases (see next)
Cryptography and Network Security
692
Combining Security Associations
Cryptography and Network Security
693
Key Management
handles key generation & distribution
typically need 2 pairs of keys
2 per direction for AH & ESP
manual key management
sysadmin manually configures every system
automated key management
automated system for on demand creation of keys for
SA’s in large systems
has Oakley & ISAKMP elements
Cryptography and Network Security
694
Oakley
a key exchange protocol
based on Diffie-Hellman key exchange
adds features to address weaknesses
cookies, groups (global params), nonces, DH key
exchange with authentication
can use arithmetic in prime fields or
elliptic curve fields
Cryptography and Network Security
695
ISAKMP
Internet Security Association and Key
Management Protocol
provides framework for key management
defines procedures and packet formats to
establish, negotiate, modify, & delete SAs
independent of key exchange protocol,
encryption alg, & authentication method
Cryptography and Network Security
696
ISAKMP
Cryptography and Network Security
697
Summary
have considered:
IPSec security framework
AH
ESP
key management & Oakley/ISAKMP
Cryptography and Network Security
698
Cryptography & Network Security
Firewalls
XiangYang Li
Cryptography and Network Security
699
Firewalls
The function of a strong position is to make the
forces holding it practically unassailable
—On War, Carl Von Clausewitz
Cryptography and Network Security
700
Introduction
seen evolution of information systems
now everyone want to be on the Internet
and to interconnect networks
has persistent security concerns
can’t easily secure every system in org
need "harm minimisation"
a Firewall usually part of this
Cryptography and Network Security
701
What is a Firewall?
a choke point of control and monitoring
interconnects networks with differing
trust
imposes restrictions on network services
only authorized traffic is allowed
auditing and controlling access
can implement alarms for abnormal behavior
is itself immune to penetration
provides perimeter defence
Cryptography and Network Security
702
Firewall Limitations
cannot protect from attacks bypassing it
eg sneaker net, utility modems, trusted organisations,
trusted services (eg SSL/SSH)
cannot protect against internal threats
eg
disgruntled employee
cannot protect against transfer of all virus
infected programs or files
because of huge range of O/S & file types
Cryptography and Network Security
703
Firewalls – Packet Filters
Cryptography and Network Security
704
Firewalls – Packet Filters
simplest of components
foundation of any firewall system
examine each IP packet (no context) and
permit or deny according to rules
hence restrict access to services (ports)
possible default policies
that not expressly permitted is prohibited
that not expressly prohibited is permitted
Cryptography and Network Security
705
Firewalls – Packet Filters
Cryptography and Network Security
706
Attacks on Packet Filters
IP address spoofing
fake source address to be trusted
add filters on router to block
source routing attacks
attacker
sets a route other than default
block source routed packets
tiny fragment attacks
split
header info over several tiny packets
either discard or reassemble before check
Cryptography and Network Security
707
Firewalls – Stateful Packet Filters
examine each IP packet in context
keeps tracks of client-server sessions
checks each packet validly belongs to one
better able to detect bogus packets out of
context
Cryptography and Network Security
708
Firewalls - Application Level Gateway
(or Proxy)
Cryptography and Network Security
709
Firewalls - Application Level Gateway
(or Proxy)
use an application specific gateway / proxy
has full access to protocol
user requests service from proxy
proxy validates request as legal
then actions request and returns result to user
need separate proxies for each service
some services naturally support proxying
others are more problematic
custom services generally not supported
Cryptography and Network Security
710
Firewalls - Circuit Level Gateway
Cryptography and Network Security
711
Firewalls - Circuit Level Gateway
relays two TCP connections
imposes security by limiting which such
connections are allowed
once created usually relays traffic without
examining contents
typically used when trust internal users by
allowing general outbound connections
SOCKS commonly used for this
Cryptography and Network Security
712
Bastion Host
highly secure host system
potentially exposed to "hostile" elements
hence is secured to withstand this
may support 2 or more net connections
may be trusted to enforce trusted
separation between network connections
runs circuit / application level gateways
or provides externally accessible services
Cryptography and Network Security
713
Firewall Configurations
Cryptography and Network Security
714
Firewall Configurations
Cryptography and Network Security
715
Firewall Configurations
Cryptography and Network Security
716
Access Control
given system has identified a user
determine what resources they can access
general model is that of access matrix with
subject - active entity (user, process)
object - passive entity (file or resource)
access right – way object can be accessed
can decompose by
columns
as access control lists
rows as capability tickets
Cryptography and Network Security
717
Access Control Matrix
Cryptography and Network Security
718
Trusted Computer Systems
information security is increasingly important
have varying degrees of sensitivity of information
cf military info classifications: confidential, secret etc
subjects (people or programs) have varying rights
of access to objects (information)
want to consider ways of increasing confidence in
systems to enforce these rights
known as multilevel security
subjects have maximum & current security level
objects have a fixed security level classification
Cryptography and Network Security
719
Bell LaPadula (BLP) Model
one of the most famous security models
implemented as mandatory policies on system
has two key policies:
no read up (simple security property)
a subject can only read/write an object if the current security level
of the subject dominates (>=) the classification of the object
no write down (*-property)
a subject can only append/write to an object if the current security
level of the subject is dominated by (<=) the classification of the
object
Cryptography and Network Security
720
Reference Monitor
Cryptography and Network Security
721
Evaluated Computer Systems
governments can evaluate IT systems
against a range of standards:
TCSEC, IPSEC and now Common Criteria
define a number of “levels” of evaluation
with increasingly stringent checking
have published lists of evaluated products
though aimed at government/defense use
can be useful in industry also
Cryptography and Network Security
722
Summary
have considered:
firewalls
types of firewalls
configurations
access control
trusted systems
Cryptography and Network Security
723
Cryptography and Network
Security
Third Edition
by William Stallings
Lecture slides by Lawrie Brown
Cryptography and Network Security
724
Intruders
They agreed that Graham should set the test
for Charles Mabledene. It was neither more
nor less than that Dragon should get Stern's
code. If he had the 'in' at Utting which he
claimed to have this should be possible, only
loyalty to Moscow Centre would prevent it. If
he got the key to the code he would prove his
loyalty to London Central beyond a doubt.
—Talking to Strange Men, Ruth Rendell
Cryptography and Network Security
725
Intruders
significant issue for networked systems is
hostile or unwanted access
either via network or local
can identify classes of intruders:
masquerader
misfeasor
clandestine user
varying levels of competence
Cryptography and Network Security
726
Intruders
clearly a growing publicized problem
from “Wily Hacker” in 1986/87
to clearly escalating CERT stats
may seem benign, but still cost resources
may use compromised system to launch
other attacks
Cryptography and Network Security
727
Intrusion Techniques
aim to increase privileges on system
basic attack methodology
target acquisition and information gathering
initial access
privilege escalation
covering tracks
key goal often is to acquire passwords
so then exercise access rights of owner
Cryptography and Network Security
728
Password Guessing
one of the most common attacks
attacker knows a login (from email/web page etc)
then attempts to guess password for it
try default passwords shipped with systems
try all short passwords
then try by searching dictionaries of common words
intelligent searches try passwords associated with the user (variations on
names, birthday, phone, common words/interests)
before exhaustively searching all possible passwords
check by login attempt or against stolen password file
success depends on password chosen by user
surveys show many users choose poorly
Cryptography and Network Security
729
Password Capture
another attack involves password capture
watching over shoulder as password is entered
using a trojan horse program to collect
monitoring an insecure network login (eg. telnet, FTP,
web, email)
extracting recorded info after successful login (web
history/cache, last number dialed etc)
using valid login/password can impersonate
user
users need to be educated to use suitable
precautions/countermeasures
Cryptography and Network Security
730
Intrusion Detection
inevitably will have security failures
so need also to detect intrusions so can
block if detected quickly
act as deterrent
collect info to improve security
assume intruder will behave differently to
a legitimate user
but
will have imperfect distinction between
Cryptography and Network Security
731
Approaches to Intrusion Detection
statistical anomaly detection
threshold
profile based
rule-based detection
anomaly
penetration identification
Cryptography and Network Security
732
Audit Records
fundamental tool for intrusion detection
native audit records
part of all common multi-user O/S
already present for use
may not have info wanted in desired form
detection-specific audit records
created specifically to collect wanted info
at cost of additional overhead on system
Cryptography and Network Security
733
Statistical Anomaly Detection
threshold detection
count occurrences of specific event over time
if exceed reasonable value assume intrusion
alone is a crude & ineffective detector
profile based
characterize past behavior of users
detect significant deviations from this
profile usually multi-parameter
Cryptography and Network Security
734
Audit Record Analysis
foundation of statistical approaches
analyze records to get metrics over time
counter, gauge, interval timer, resource use
use various tests on these to determine if
current behavior is acceptable
mean & standard deviation, multivariate, markov
process, time series, operational
key advantage is no prior knowledge used
Cryptography and Network Security
735
Rule-Based Intrusion Detection
observe events on system & apply rules to
decide if activity is suspicious or not
rule-based anomaly detection
analyze historical audit records to identify usage
patterns & auto-generate rules for them
then observe current behavior & match against rules to
see if conforms
like statistical anomaly detection does not require prior
knowledge of security flaws
Cryptography and Network Security
736
Rule-Based Intrusion Detection
rule-based penetration identification
uses expert systems technology
with rules identifying known penetration, weakness
patterns, or suspicious behavior
rules usually machine & O/S specific
rules are generated by experts who interview & codify
knowledge of security admins
quality depends on how well this is done
compare audit records or states against rules
Cryptography and Network Security
737
Base-Rate Fallacy
practically an intrusion detection system
needs to detect a substantial percentage
of intrusions with few false alarms
if too few intrusions detected -> false security
if too many false alarms -> ignore / waste time
this is very hard to do
existing systems seem not to have a good
record
Cryptography and Network Security
738
Distributed Intrusion Detection
traditional focus is on single systems
but typically have networked systems
more effective defense has these working
together to detect intrusions
issues
dealing with varying audit record formats
integrity & confidentiality of networked data
centralized or decentralized architecture
Cryptography and Network Security
739
Distributed Intrusion Detection Architecture
Cryptography and Network Security
740
Distributed Intrusion Detection –
Agent Implementation
Cryptography and Network Security
741
Honeypots
decoy systems to lure attackers
away from accessing critical systems
to collect information of their activities
to encourage attacker to stay on system so administrator
can respond
are filled with fabricated information
instrumented to collect detailed
information on attackers activities
may be single or multiple networked
systems
Cryptography and Network Security
742
Password Management
front-line defense against intruders
users supply both:
login – determines privileges of that user
password – to identify them
passwords often stored encrypted
Unix uses multiple DES (variant with salt)
more recent systems use crypto hash function
Cryptography and Network Security
743
Managing Passwords
need policies and good user education
ensure every account has a default password
ensure users change the default passwords to
something they can remember
protect password file from general access
set technical policies to enforce good passwords
minimum length (>6)
require a mix of upper & lower case letters, numbers, punctuation
block know dictionary words
Cryptography and Network Security
744
Managing Passwords
may reactively run password guessing tools
note that good dictionaries exist for almost any
language/interest group
may enforce periodic changing of passwords
have system monitor failed login attempts, &
lockout account if see too many in a short
period
do need to educate users and get support
balance requirements with user acceptance
be aware of social engineering attacks
Cryptography and Network Security
745
Proactive Password Checking
most promising approach to improving
password security
allow users to select own password
but have system verify it is acceptable
simple rule enforcement (see previous slide)
compare against dictionary of bad passwords
use algorithmic (markov model or bloom filter) to
detect poor choices
Cryptography and Network Security
746
Summary
have considered:
problem of intrusion
intrusion detection (statistical & rule-based)
password management
Cryptography and Network Security
747
Cryptography and Network Security
748