Cryptography and

Network Security
Overview
Fifth Edition
by William Stallings

Lecture slides by Lawrie Brown

Editied by R. Newman
The art of war teaches us to rely 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
 Roadmap
 Cryptographic Algorithms
 Symmetric ciphers
 Asymmetric encryption
 Hash functions/MAC/Digital Signatures

 Mutual Trust
• Key Management
• Digital Certificates/User Authentication
 Network Security
• Transport and IP level Security
• Wireless Security
 Why Do I Need Security?

Unauthorized/inappropriate access and use

Disclosure
Disruption
Deletion/destruction
Corruption
Modification
Inspection
Recording or devaluation.
 Yahoo
2013-14
Affected 3 billion user accounts
The attack compromised the real names,
email addresses, dates of birth and
telephone numbers of 500 million
users. Later on revised to all 3 billion user
accounts.
Damage: $350 million.
 Marriott International
2014-18
Impacted 500 million customers.

For some of the victims, only name and contact

information were compromised. For others
combination of contact info, passport number,
Starwood Preferred Guest numbers, travel
information, and other personal information. Credit
card numbers and expiration dates of more than
100 million customers were stolen.

Can cost $12.5 billion in damages.

 Uber
2016
Impacted 57 million Uber users and
600,000 drivers.
Names, email addresses, and mobile
phone numbers of 57 users of the Uber
app stolen. Driver license numbers of
600,000 Uber drivers also stolen.
Paid the hackers $100,000 to destroy the
data with no way to verify that they did.
Drop in valuation of $48 billion.
 HBO
2017
Hackers allegedly obtained 1.5 terabytes of
data from the company which included
episodes of Ballers and Room 104 as well as
a script from one of the episodes of “Game of
Thrones”.

https://en.wikipedia.org/wiki/List_of_cyberattacks
https://en.wikipedia.org/wiki/List_of_data_breaches
Average economic cost of cyber attacks -
$10.4 million
Direct cost - $0.9 million
Indirect loss due to job losses and loss
of reputation - $3.1 million
Macroeconomic impact such as reduced
customer and enterprise spending - $6.3
million.
Source: ‘Understanding the Cyber security threat landscape in Asia Pacific:
securing modern enterprise in the digital world’ by Microsoft and Frost and
Sullivan
 Computer Security
 The protection afforded to an automated
information system in order to attain the
applicable objectives of preserving the
integrity, availability and confidentiality of
information system resources (includes
hardware, software, firmware,
information/data, and telecommunications)
Confidentiality:
 Data confidentiality: Assures that private or confidential
information is not made available or disclosed to
unauthorized individuals.

 Privacy: Assures that individuals control or influence what

information related to them may be collected and stored
and by whom and to whom that information may be
disclosed.

Integrity:
 Data integrity: Assures that information and programs are
changed only in a specified and authorized manner.

 System integrity: Assures that a system performs its

intended function in an unimpaired manner, free from
deliberate or inadvertent unauthorized manipulation of the
system.


Key Security Concepts

CIA Triad (NIST Computer Security

Handbook)
Confidentiality:
Preserving authorized restrictions on information access
and disclosure, including means for protecting personal
privacy and proprietary information. A loss of
confidentiality is the unauthorized disclosure of
information.
Integrity:
Guarding against improper information modification or
destruction, including ensuring information
nonrepudiation and authenticity. A loss of integrity is
the unauthorized modification or destruction of
Information.
Availability:
Ensuring timely and reliable access to and use of
information. A loss of availability is the disruption of
access to or use of information or information system.

(NIST – FIPS 99 Standard For Security Categorization of

Authenticity:
The property of being genuine and being able to be
verified and trusted; confidence in validity of the
transmission , a message, or message originator. This
means verifying that the user are who they say they are
and that each input arriving at the system came from
trusted source.

Accountability:
The security goal that generates the requirement for
actions of an entity to be traced uniquely to that entity.
This supports nonrepudiation, deterrence, fault
isolation, intrusion detection and prevention, and after
action recovery and legal action.

Because truly secure systems are not yet an achievable

goal, we must be able to trace a security breach to a
responsible party. System must keep records of their
 Levels of Impact
 There 3 levels of impact from a security
breach ( i.e. Resulting from loss of CIA+AA)
possible

Low
Moderate
High
 Low Impact
 The loss could be expected to have a limited adverse
effect on organizational operations, organizational
assets, or individuals.
 A limited adverse effect means that, for example, the
loss of confidentiality, integrity, or availability might
Cause a degradation in mission capability to an
extent and duration that the organization is able to
perform its primary functions, but the effectiveness of
the functions is noticeably reduced;
Result in minor damage to organizational assets;
Result in minor financial loss; or
Result in minor harm to individuals.
 Moderate Impact
 The loss could be expected to have a serious adverse
effect on organizational operations, organizational
assets, or individuals.
 A serious adverse effect means that, for example, the
loss might
Cause a significant degradation in mission capability
to an extent and duration that the organization is able
to perform its primary functions, but the effectiveness
of the functions is significantly reduced.
Result in significant damage to organizational assets.
Result in significant financial loss.
Result in significant harm to individuals that does not
involve loss of life or serious, life-threatening injuries.
 High Impact
 The loss could be expected to have a severe or
catastrophic adverse effect on organizational operations,
organizational assets, or individuals.
 A severe or catastrophic adverse effect means that, for
example, the loss might
Cause a severe degradation in or loss of mission
capability to an extent and duration that the
organization is not able to perform one or more of its
primary functions.
Result in major damage to organizational assets.
Result in major financial loss.
Result in severe or catastrophic harm to individuals
involving loss of life or serious life threatening injuries.
 Examples of Security
Requirements: Confidentiality
Student grade information is an asset whose
confidentiality is considered to be very high
The US FERPA Act: grades should only be
available to students, their parents, and their
employers (when required for the job)
Student enrollment information: May have
moderate confidentiality rating; less damage if
disclosed
Directory information: Low confidentiality rating;
often available publicly
 Examples of Security
Requirements: Integrity
A hospital patient’s allergy information (high integrity
data): a doctor should be able to trust that the info is
correct and current
If anyone deliberately falsifies the data, the database
should be restored to a trusted basis and the falsified
information traced back to the person who did it
An online newsgroup registration data: moderate level
of integrity
An example of low integrity requirement: anonymous
online poll (inaccuracy is well understood)
 Examples of Security
Requirements: Availability
A system that provides authentication: high
availability requirement
If customers cannot access resources, the loss of
services could result in financial loss
A public website for a university: a moderate
availably requirement; not critical but causes
embarrassment
An online telephone directory lookup: a low
availability requirement because unavailability is
mostly annoyance (there are alternative sources)
 Examples of Security
Requirements
 Confidentiality – student grades
 Integrity – patient information
 Availability – authentication service
 Authenticity – admission ticket
 Non-repudiation – stock sell order
Computer Security Challenges
1. Not simple – easy to get it wrong
• Mechanism required to implement CIA are
complex.
2. Must consider potential attacks
• Successful attack exploit an unexpected
weakness.
3. Procedures used counter-intuitive
• Proper evaluation of any threat to evolve
security mechanism.
4. Involve algorithms and secret info
• i.e. encryption keys. How to create, distribute
and protect secret information. Protocol
design challenges.
Computer Security Challenges
5. Must decide where to deploy mechanisms
• Physical placement. Implement in which
protocol layer?
6. Battle of wits between attacker / security admin
• Attacker at advantage. Single weakness
necessary to mount an attack.
7. Not perceived on benefit until fails
8. Requires regular monitoring
• Difficult in short term, overloaded environment
9. Security is a process, not an event
Computer Security Challenges
9. Too often an after-thought
10. Needs to be integral part of system design.
• Most old Internet Protocol had no build in
security mechanism.
11. Regarded as impediment to using system in
user friendly and efficient manner.
“Security verses Convenience”
“Security and Moral issues”
“Security and Privacy issues”
 Computer
Security
Terminology
Security Concepts and
Relationships
 OSI Security Architecture
Software architecture refers to the
fundamental structures of a software system
and the discipline of creating such structures
and systems.

ITU-T X.800 “Security Architecture for OSI”

Defines a systematic way of defining and
providing security requirements
For us it provides a useful, if abstract,
overview of concepts we will study
 Aspects of Security
 Consider 3 aspects of information security:
Security attack
Any action that can compromise
security of Information Systems.
Security mechanism (control)
A process (device incorporating
such process) designed to detect,
prevent and recover from security
attack.
Security service
Processing or communication
service that enhances security . Use
 Aspects of Security
 Terms used
Threat – a potential for violation of security,
which exists when there is a circumstance,
capability, action or event that could breach
security and cause harm.
Vulnerability – a way by which loss can
happen. A weakness that can be exploited.
Attack – an assault on system security, a
deliberate attempt to evade security services
and violate security policy of a system.
Passive Attack – Interception
Release of Message Contents
Passive Attack: Traffic Analysis

Observe traffic pattern

Active Attack: Interruption

Block delivery of message

Active Attack: Modification

Modify message
Active Attack: Masquerade
Active Attack: Replay
 Handling Attacks
Passive attacks – focus on Prevention
• Easy to stop
• Hard to detect
Active attacks – focus on Detection and
Recovery
• Hard to stop
• Easy to detect
• Attack surface – Reachable and exploitable
vulnerabilities in system.
• Network attack surface, Software attack surface,
Human attack surface
 Threat Consequences
• Unauthorized disclosure: Threat to confidentiality
• Exposure (release data), interception, inference, intrusion
• Deception: Threat to integrity
• Masquerade, falsification (alter data), repudiation
• Disruption: Threat to integrity and availability
• Incapacitation (destruction), corruption (backdoor logic),
obstruction (infer with communication, overload a line)
• Usurpation: Threat to integrity
• Misappropriation (theft of service), misuse (hacker
gaining unauthorized access)
 Security Service
Enhance security of data processing systems
and information transfers of an organization
Intended to counter security attacks
Using one or more security mechanisms
Often replicates functions normally
associated with physical documents
• For example, have signatures, dates; need
protection from disclosure, tampering, or
destruction; be notarized or witnessed; be
recorded or licensed
 Security Services
 X.800:
“A service provided by a protocol layer of
communicating open systems, which ensures
adequate security of the systems or of data
transfers”

 RFC 2828:
“A processing or communication service
provided by a system to give a specific kind of
protection to system resources”
 Security Services (X.800)
 Authentication - assurance that communicating
entity is the one claimed
have both peer-entity & data origin authentication
 Access Control - prevention of the
unauthorized use of a resource
 Data Confidentiality –protection of data from
unauthorized disclosure.
• Connectionless confidentiality
• Connection confidentiality
• Selective-Field confidentiality
• Traffic flow confidentiality
 Security Services (X.800)
 Data Integrity - assurance that data received is
as sent by an authorized entity
• Connection integrity with recovery
• Connection integrity without recovery
• Selective-Field Connection integrity
• Connectionless integrity
• Selective-Field Connectionless integrity.
 Non-Repudiation - protection against denial by
one of the parties in a communication
• Nonrepudiation, Origin
• Nonrepudiation, Destination
 Availability – resource accessible/usable
 Security Mechanism

Feature designed to detect, prevent, or

recover from a security attack
No single mechanism that will support all
services required
However one particular element underlies
many of the security mechanisms in use:
Cryptographic techniques
Security Mechanisms (X.800)
Specific Security Mechanisms:
Encipherment ( Confidentiality)
Digital signatures (Nonrepudiation)
Access controls ( Privacy)
Data integrity ( Hashes/MAC )
Authentication exchange (Establish identity of
the entity)
Traffic padding ( Traffic analysis )
Routing control (Confidentiality, Privacy)
Notarization (Trusted Third Party)
Security Mechanisms (X.800)
Pervasive Security Mechanisms:
Trusted functionality ( What is correct
behavior? Established by security policy)
Security labels ( Names or designates the
security attribute of the resource)
Event detection ( Security breaches,
Intrusion)
Security audit trails (Maintain record of
system events and user activities)
Security recovery ( Mechanism and
processes to be implemented to perform
recovery)
Service Mechanisms
Relation
Model for Network Security
 Model for Network Security
 Using this model requires us to:
1. Design a suitable algorithm for the security
transformation
2. Generate the secret information (keys) used
by the algorithm
3. Develop methods to distribute and share the
secret information
4. Specify a protocol enabling the principals to
use the transformation and secret
information for a security service
Model for Network Access
Security
 Model for Network Access
Security
 Using this model requires us to:
1. Select appropriate gatekeeper functions to
identify users
2. Implement security controls to ensure only
authorised users access designated
information or resources
 Note that model does not include:
1. Monitoring of system for successful
penetration
2. Monitoring of authorized users for misuse
3. Audit logging for forensic uses, etc.
Security Trends
Computer Security Losses
Security Technologies Used
 Standards Organizations
 National Institute of Standards & Technology
(NIST)
 Internet Society (ISOC)
 International Telecommunication Union
Telecommunication Standardization Sector (ITU-
T)
 International Organization for Standardization
(ISO)
 Internet Engineering Task Force (IETF)
 Summary
 Topic roadmap & standards organizations
 Security concepts:
confidentiality, integrity, availability
 X.800 security architecture
 Security attacks, services, mechanisms
 models for network (access) security
Cryptography and
Network Security
Chapter 2
Fifth Edition
by William Stallings
 Classical Encryption
Techniques

 "I am fairly familiar with all the forms of secret

writings, and am myself the author of a trifling
monograph upon the subject, in which I analyze
one hundred and sixty separate ciphers," said
Holmes..
—The Adventure of the Dancing Men, Sir Arthur
Conan Doyle
 Symmetric Encryption
 or conventional / private-key / single-key
 sender and recipient share a common key
 all classical encryption algorithms are
private-key
 was only type prior to invention of public-
key in 1970’s
 and by far most widely used (still)
 is significantly faster than public-key crypto
 Some Basic Terminology
 plaintext - original message
 ciphertext - coded message
 cipher - algorithm for transforming plaintext to ciphertext
 key - info used in cipher known only to sender/receiver
 encipher (encrypt) - converting plaintext to ciphertext
 decipher (decrypt) - recovering plaintext from ciphertext
 cryptography - study of encryption principles/methods
 cryptanalysis (codebreaking) - study of principles/
methods of deciphering ciphertext without knowing key
 cryptology - field of both cryptography and cryptanalysis
Symmetric Cipher Model
 Requirements
 two requirements for secure use of symmetric
encryption:
a strong encryption algorithm
a secret key known only to sender / receiver
 mathematically have:
Y = E(K, X) = EK(X) = {X}K
X = D(K, Y) = DK(Y)
 assume encryption algorithm is known
Kerckhoff’s Principle: security in secrecy of key alone,
not in obscurity of the encryption algorithm
 implies a secure channel to distribute key
Central problem in symmetric cryptography
 Cryptography
 can characterize cryptographic system by:
type of encryption operations used
• substitution
• transposition
• product
number of keys used
• single-key or private
• two-key or public
way in which plaintext is processed
• block
• stream
 Cryptanalysis
 objective to recover key not just message
 general approaches:
cryptanalytic attack
brute-force attack
 if either succeed all key use compromised
 Cryptanalytic Attacks
ciphertext only
only know algorithm & ciphertext, is
statistical, can identify plaintext
known plaintext
know/suspect plaintext & ciphertext
chosen plaintext
select plaintext and obtain ciphertext
chosen ciphertext
select ciphertext and obtain plaintext
chosen text
select plaintext or ciphertext to en/decrypt
 Cipher Strength
 unconditional security
no matter how much computer power or time
is available, the cipher cannot be broken since
the ciphertext provides insufficient information
to uniquely determine the corresponding
plaintext
 computational security
given limited computing resources (e.g. time
needed for calculations is greater than age of
universe), the cipher cannot be broken
 Brute Force Search
 always possible to simply try every key
 most basic attack, exponential in key length
 assume either know / recognise plaintext

Key Size (bits) Number of Alternative Time required at 1 Time required at 106
Keys decryption/µs decryptions/µs

32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds

56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours

128 2128 = 3.4  1038 2127 µs = 5.4  1024 years 5.4  1018 years

168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years

26 characters 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years
(permutation)
 Classical Substitution
Ciphers
 where letters of plaintext are replaced by
other letters or by numbers or symbols
 or if plaintext is viewed as a sequence of
bits, then substitution involves replacing
plaintext bit patterns with ciphertext bit
patterns
 Caesar Cipher
 earliest known substitution cipher
 by Julius Caesar
 first attested use in military affairs
 replaces each letter by 3rd letter on
 example:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
 Caesar Cipher
 can define transformation as:
a b c d e f g h i j k l m n o p q r s t u v w x y z =
IN
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C =
OUT

 mathematically give each letter a number

a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

 then have Caesar (rotation) cipher as:

c = E(k, p) = (p + k) mod (26)
p = D(k, c) = (c – k) mod (26)
 Cryptanalysis of Caesar
Cipher
 only have 26 possible ciphers
A maps to A,B,..Z
 could simply try each in turn
 a brute force search
 given ciphertext, just try all shifts of letters
 do need to recognize when have plaintext
 eg. break ciphertext "GCUA VQ DTGCM"
 Affine Cipher
broaden to include multiplication
can define affine transformation as:
c = E(k, p) = (ap + b) mod (26)
p = D(k, c) = (a-1(c – b)) mod (26)
key k=(a,b)
a must be relatively prime to 26
so there exists unique inverse a-1
 Affine Cipher - Example
 example k=(17,3):
a b c d e f g h i j k l m n o p q r s t u v w x y
z = IN
D U L C T K B S J A R I Z Q H Y P G X O F W N E V
M = OUT
 example:
meet me after the toga party
ZTTO ZT DKOTG OST OHBD YDGOV
 Now how many keys are there?
12 x 26 = 312
 Still can be brute force attacked!
 Monoalphabetic Cipher
 rather than just shifting the alphabet
 could shuffle (permute) the letters arbitrarily
 each plaintext letter maps to a different random
ciphertext letter
 hence key is 26 letters long

Plain: abcdefghijklmnopqrstuvwxyz
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
 Monoalphabetic Cipher
Security
 key size is now 25 characters…
 now have a total of 26! = 4 x 1026 keys
 with so many keys, might think is secure
 but would be !!!WRONG!!!
 problem is language characteristics
 Language Redundancy and
Cryptanalysis
 human languages are redundant
 e.g., "th lrd s m shphrd shll nt wnt"
 letters are not equally commonly used
 in English E is by far the most common letter
followed by T,R,N,I,O,A,S
 other letters like Z,J,K,Q,X are fairly rare
 have tables of single, double & triple letter
frequencies for various languages
English Letter Frequencies
 Use in Cryptanalysis
 key concept - monoalphabetic substitution
ciphers do not change relative letter frequencies
 discovered by Arabian scientists in 9th century
 calculate letter frequencies for ciphertext
 compare counts/plots against known values
 if caesar cipher look for common peaks/troughs
peaks at: A-E-I triple, N-O pair, R-S-T triple
troughs at: J-K, U-V-W-X-Y-Z
 for monoalphabetic must identify each letter
tables of common double/triple letters help
(digrams and trigrams)
 amount of ciphertext is important – statistics!
 Example Cryptanalysis
 given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
 count relative letter frequencies (see text)
 Example Cryptanalysis
 given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
 guess P & Z are e and t
 guess ZW is th and hence ZWP is “the”
 proceeding with trial and error finally get:
it was disclosed yesterday that several informal
but
direct contacts have been made with political
representatives of the viet cong in moscow
 Playfair Cipher
 not even the large number of keys in a
monoalphabetic cipher provides security
 one approach to improving security was to
encrypt multiple letters
 the Playfair Cipher is an example
 invented by Charles Wheatstone in 1854,
but named after his friend Baron Playfair
 Playfair Key Matrix
 a 5X5 matrix of letters based on a keyword
 fill in letters of keyword (sans duplicates)
 fill rest of matrix with other letters
 eg. using the keyword MONARCHY

M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
 Encrypting and Decrypting
 plaintext is encrypted two letters at a time
1. if a pair is a repeated letter, insert filler like 'X’
2. if both letters fall in the same row, replace
each with letter to right (wrapping back to start
from end)
3. if both letters fall in the same column, replace
each with the letter below it (wrapping to top
from bottom)
4. otherwise each letter is replaced by the letter
in the same row and in the column of the other
letter of the pair
 Playfair Example
 Message = Move forward
 Plaintext = mo ve fo rw ar dx
 Here x is just a filler, message is padded and segmented
mo -> ON; ve -> UF; fo -> PH, etc.
 Ciphertext = ON UF PH NZ RM BZ
M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
 Security of Playfair Cipher
 security much improved over monoalphabetic
 since have 26 x 26 = 676 digrams
 would need a 676 entry frequency table to
analyse (versus 26 for a monoalphabetic)
 and correspondingly more ciphertext
 was widely used for many years
eg. by US & British military in WW1
 it can be broken, given a few hundred letters
 since still has much of plaintext structure
 Polyalphabetic Ciphers
 polyalphabetic substitution ciphers
 improve security using multiple cipher alphabets
 make cryptanalysis harder with more alphabets
to guess and flatter frequency distribution
 use a key to select which alphabet is used for
each letter of the message
 use each alphabet in turn
 repeat from start after end of key is reached
 Vigenère Cipher
 simplest polyalphabetic substitution cipher
 effectively multiple caesar ciphers
 key is multiple letters long K = k1 k2 ... kd
 ith letter specifies ith alphabet to use
 use each alphabet in turn
 repeat from start after d letters in message
 decryption simply works in reverse
 Example of Vigenère Cipher
 write the plaintext out
 write the keyword repeated above it
 use each key letter as a caesar cipher key
 encrypt the corresponding plaintext letter
 eg using keyword deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
 Aids
 simple aids can assist with en/decryption
 a Saint-Cyr Slide is a simple manual aid
a slide with repeated alphabet
line up plaintext 'A' with key letter, eg 'C'
then read off any mapping for key letter
 can bend round into a cipher disk
 or expand into a Vigenère Tableau
Cipher Disk
Vigenère Tableau
 Security of Vigenère Ciphers
 have multiple ciphertext letters for each
plaintext letter
 hence letter frequencies are obscured
 but not totally lost
 start with letter frequencies
see if it looks monoalphabetic or not
 if not, then need to determine number of
alphabets, since then can attack each
 Kasiski Method
 method developed by Babbage / Kasiski
 repetitions in ciphertext give clues to period
 so find same plaintext a multiple of key length
apart
 which results in the same ciphertext
 of course, could also be random fluke
 e.g. repeated “VTW” in previous example
 distance of 9 suggests key size of 3 or 9
 then attack each monoalphabetic cipher
individually using same techniques as before
 Example of Kasiski Attack
 Find repeated ciphertext trigrams (e.g., VTW)
 May be result of same key sequence and same
plaintext sequence (or not)
 Find distance(s)
 Common factors are likely key lengths

key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
 Autokey Cipher
 ideally want a key as long as the message
 Vigenère proposed the autokey cipher
 with keyword is prefixed to message as key
 knowing keyword can recover the first few letters
 use these in turn on the rest of the message
 but still have frequency characteristics to attack
 eg. given key deceptive
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA
 Vernam Cipher
 ultimate defense is to use a key as long as the
plaintext
 with no statistical relationship to it
 invented by AT&T engineer Gilbert Vernam in
1918
 specified in U.S. Patent 1,310,719, issued July
22, 1919
 originally proposed using a very long but
eventually repeating key
 used electromechanical relays
 One-Time Pad
 if a truly random key as long as the message is
used, the cipher will be secure
 called a One-Time pad (OTP)
 is unbreakable since ciphertext bears no
statistical relationship to the plaintext
 since for any plaintext & any ciphertext there
exists a key mapping one to other
 can only use the key once though
 problems in generation & safe distribution of key
Ciphertext:ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERF
PLUYTS

key: pxlmvmsydofuyrvzwctnlebnecvgdupahfzzl
mnyih
plaintext: mr mustard wit the candlestick in
the hall

key: mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyo
vuhwt
plaintext: miss scarlet with the knife in the li
brary
 Transposition Ciphers
 now consider classical transposition or
permutation ciphers
 these hide the message by rearranging
the letter order
 without altering the actual letters used
 can recognise these since have the same
frequency distribution as the original text
 Rail Fence cipher
 write message letters out diagonally over a
number of rows
 then read off cipher row by row
 Message: meetmeafterthetogaparty
 eg. write message out as:
m e m a t r h t g p r y
e t e f e t e o a a t
 giving ciphertext
MEMATRHTGPRYETEFETEOAAT
 Row Transposition Ciphers
 is a more complex transposition
 write letters of message out in rows over a
specified number of columns
 then reorder the columns according to
some key before reading off the rows
Key: 4312567
Column Out 4 3 1 2 5 6 7
Plaintext: a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
 Block Transposition Ciphers
arbitrary block transposition may be used
specify permutation on block
repeat for each block of plaintext
Key: 4931285607
Plaintext: attackpost poneduntil twoamxyzab

Ciphertext: CTATTSKPAO DLEONIDUPT MBAWOAXYTZ

 Product Ciphers
 ciphers using substitutions or transpositions are
not secure because of language characteristics
 hence consider using several ciphers in
succession to make harder, but:
two substitutions make a more complex substitution
two transpositions make more complex transposition
but a substitution followed by a transposition makes a
new much harder cipher
 this is bridge from classical to modern ciphers
 Rotor Machines
 before modern ciphers, rotor machines were
most common complex ciphers in use
 widely used in WW2
German Enigma, Allied Hagelin, Japanese Purple
 implemented a very complex, varying
substitution cipher
 used a series of cylinders, each giving one
substitution, which rotated and changed after
each letter was encrypted
 with 3 cylinders have 263=17576 alphabets
Hagelin Rotor Machine
Rotor Machine Principles
 Rotor Ciphers
 Each rotor implements some permutation
between its input and output contacts
 Rotors turn like an odometer on each key
stroke (rotating input and output contacts)
 Key is the sequence of rotors and their
initial positions
 Steganography
 an alternative to encryption
 hides existence of message
using only a subset of letters/words in a longer
message marked in some way
using invisible ink
hiding in LSB in graphic image or sound file
hide in “noise”
 has drawbacks
high overhead to hide relatively few info bits
 advantage is can obscure encryption use
 Summary
 have considered:
classical cipher techniques and terminology
monoalphabetic substitution ciphers
cryptanalysis using letter frequencies
Playfair cipher
polyalphabetic ciphers
transposition ciphers
product ciphers and rotor machines
steganography
 Encryption Mappings
M1 C1  A given key (k)
 Maps any message Mi to
M2 K1 C2
some ciphertext E(k,Mi)
 Ciphertext image of Mi is
unique to Mi under k

K1
K1

M3 C3  Plaintext pre-image of Ci is
K1

unique to Ci under k
 Notation
A A
K1
 key k and Mi in M, Ǝ! Cj
Mi Ci
in C such that E(k,Mi) = Cj
A A
 key k and ciphertext Ci
K1
in C, Ǝ! Mj in M such that
E(k,Mj) = Ci
Mn
Cn  Ek(.) is “one-to-one” (injective)
M=set of all C=set of all
 If |M|=|C| it is also “onto”
plaintexts ciphertexts (surjective), and hence
bijective.
 Encryption Mappings (2)
 A given plaintext (Mi)
M1 C1
 Mi is mapped to some ciphertext
E(K,Mi) by every key k
 Different keys may map Mi to the
M2 Kj C2
same ciphertext
 There may be some ciphertexts to
M3 K2,K89,... C3
which Mi is never mapped by any
K3,K
key
j’,.
Km ..  Notation
A A
 key k and Mi in M, Ǝ!
K1
, K7 ciphertext Cj in C such that
Mi 57 Ci E(k,Mi) = Cj
,..
.  It is possible that there are keys k
and k’ such that E(k,Mi) = E(k’,Mi)
 There may be some ciphertext Cj
Mn for which Ǝ key k such that
Cn E(k,Mi) = Cj
 Encryption Mappings (3)
M1 C1  A ciphertext (Ci)
 Has a unique plaintext pre-
K1
,K 1
image under each k
M2 7,. C2  May have two keys that map
..
the same plaintext to it
 There may be some plaintext
M3 K2,K89,... C3 Mj such that no key maps Mj
Km to Ci
,...
4  Notation
...

...
... Kj , K9
K3
A A
 key k and ciphertext Ci
Mi ... Ci in C, Ǝ! Mj in M such that
E(k,Mj) = Ci
 There may exist keys k, k’
...

...

and plaintext Mj such that

E(k,Mj) = E(k’,Mj) = Ci
Mn  There may exist plaintext Mj
Cn
such that Ǝ key k such that
E(k,Mj) = Ci
 Encryption Mappings (4)
Under what conditions will there always be
some key that maps some plaintext to a
given ciphertext?
If for an intercepted ciphertext cj, there is
some plaintext mi for which there does not
exist any key k that maps mi to cj, then the
attacker has learned something
If the attacker has ciphertext cj and known
plaintext mi, then many keys may be
eliminated
 Homophone Cipher
 rather than combine multiple monoalphabetic
ciphers, can assign multiple ciphertext
characters to same plaintext character
 assign number of homophones according to
frequency of plaintext character
 Gauss believed he made unbreakable cipher
using homophones
 but still have digram/trigram frequency
characteristics to attack
 e.g., have 58 ciphertext characters, with each
plaintext character assigned to ceil(freq/2)
ciphertext characters – so e has 7 homophones,
t has 5, a has 4, j has 1, q has 1, etc.
Cryptography and
Network Security
Chapter 3
Fifth Edition
by William Stallings
 Chapter 3 – Block Ciphers and
the Data Encryption Standard

All the afternoon Mungo had been working on

Stern's code, principally with the aid of the latest
messages which he had copied down at the
Nevin Square drop. Stern was very confident.
He must be well aware London Central knew
about that drop. It was obvious that they didn't
care how often Mungo read their messages, so
confident were they in the impenetrability of the
code.
—Talking to Strange Men, Ruth Rendell
 Modern Block Ciphers
 Now look at modern block ciphers
 One of the most widely used types of
cryptographic algorithms
 Provide secrecy /authentication services
 Focus on DES (Data Encryption Standard)
 To illustrate block cipher design principles
 Block vs Stream Ciphers
 Block ciphers process messages in
blocks, each of which is then en/decrypted
 Like a substitution on very big characters

64-bits or more
 Stream ciphers process messages a bit or
byte at a time when en/decrypting
 Many current ciphers are block ciphers

better analysed

broader range of applications
Block vs Stream Ciphers
 Block Cipher Principles
 Most symmetric block ciphers are based on a
Feistel Cipher Structure
 Needed since must be able to decrypt
ciphertext to recover messages efficiently
 Block ciphers look like an extremely large
substitution
 Would need table of 264 entries for a 64-bit block
 Instead create from smaller building blocks
 Using idea of a product cipher
Ideal Block Cipher

permutation
Claude Shannon and Substitution-
Permutation Ciphers
 Claude Shannon introduced idea of substitution-
permutation (S-P) networks in 1949 paper
 Form basis of modern block ciphers
 S-P nets are based on the two primitive
cryptographic operations seen before:

substitution (S-box)

permutation (P-box)
 Provide confusion & diffusion of message & key
 Confusion and Diffusion
 Cipher needs to completely obscure
statistical properties of original message
 A one-time pad does this
 More practically Shannon suggested
combining S & P elements to obtain:
 Diffusion – dissipates statistical structure
of plaintext over bulk of ciphertext
 Confusion – makes relationship between
ciphertext and key as complex as possible
 Feistel Cipher Structure
 Horst Feistel devised the feistel cipher

based on concept of invertible product cipher
 Partitions input block into two halves

process through multiple rounds which

perform a substitution on left data half

based on round function of right half & subkey

then have permutation swapping halves
 Implements Shannon’s S-P net concept
Feistel Cipher Structure
Feistel Cipher Design Elements
 Block size
 Key size
 Number of rounds
 Subkey generation algorithm
 Round function
 Fast software en/decryption
 Ease of analysis
Data Encryption Standard (DES)
 Most widely used block cipher in world
 Adopted in 1977 by NBS (now NIST)

as FIPS PUB 46
 Encrypts 64-bit data using 56-bit key
 Has widespread use
 Has been considerable controversy over
its security
 DES History
 IBM developed Lucifer cipher

by team led by Feistel in late 60’s

used 64-bit data blocks with 128-bit key
 Then redeveloped as a commercial cipher
with input from NSA and others
 In 1973 NBS issued request for proposals
for a national cipher standard
 IBM submitted their revised Lucifer which
was eventually accepted as the DES
 DES Design Controversy
 Although DES standard is public
 Was considerable controversy over design

in choice of 56-bit key (vs Lucifer 128-bit)

and because design criteria were classified
 Subsequent events and public analysis
show in fact design was appropriate
 Use of DES has flourished

especially in financial applications

still standardised for legacy application use
DES Encryption Overview
 Initial Permutation IP
 First step of the data computation
 IP reorders the input data bits
 Even bits to LH half, odd bits to RH half
 Quite regular in structure (easy in h/w)
 No cryptographic value
 example:
IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)
 Initial Permutation

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

Final Permutation reverses the above operation

Feistel Cipher Round
 DES Round Structure
 Uses two 32-bit L & R halves
 as for any Feistel cipher can describe as:
Li = Ri–1
Ri = Li–1  F(Ri–1, Ki)
 F takes 32-bit R half and 48-bit subkey:

expands R to 48-bits using perm E

adds to subkey using XOR

passes through 8 S-boxes to get 32-bit result

finally permutes using 32-bit perm P
DES Round Structure
 DES Expansion Permutation
Right Half i-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

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

 R half expanded to same length as 48-bit

subkey
 consider R as 8 nybbles (4 bits each)
 expansion permutation

copies each nybble into the middle of a 6-bit
block

copies the end bits of the two adjacent
nybbles into the two end bits of the 6-bit block
Expansion Permutation (E)

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
 Substitution Boxes S
 Have eight S-boxes which map 6 to 4 bits
 Each S-box is actually 4 little 4 bit boxes

outer bits 1 & 6 (row bits) select one row of 4

inner bits 2-5 (col bits) are substituted

result is 8 lots of 4 bits, or 32 bits
 Row selection depends on both data & key

feature known as autoclaving (autokeying)
 example:

S(18 09 12 3d 11 17 38 39) = 5fd25e03
 Substitution Boxes S
 Each of the eight s-
boxes is different
input symbol  Each s-box reduces
6 bits to 4 bits
control

Si  So the 8 s-boxes
implement the 48-bit
output symbol to 32-bit contraction
substitution
 101101

Middle 4 bits of input

S5 00 00 00 00 01 01 01 01 10 10 10 10 11 11 11
1111
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10
00 11 01 00 01 10 10 01 10 01 00 11 11 00 11
00 1001
10 00 00 01 11 10 11 10 00 01 11 11 01 00 10
11 10 00 11 01 01 11 00 01 00 11 10 00 10 10
01 0110
Outer 10 11 10 00 00 11 01 01 01 00 11 10 11 01 00
bits 01 00 00 10 10 11 01 10 11 10 11 01 01 00 00
10 1110
00 10 01 11 10 01 11 00 11 01 00 01 10 11 00
10 10 11 01 00 11 00 11 01 11 00 10 10 01 01
11 0011
11 00 00 11 01 10 10 01 10 11 00 01 10 00 01

0010
 Permutation Box P
S1 S2 S3 S4 S5 S6 S7 S8

 P-box at end of each round

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

 Increases diffusion/avalanche effect

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
Permutation Function (P)

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
 DES Round in Full
Right Half i-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

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

Round Key i

+
O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

input symbol input symbol input symbol input symbol input symbol input symbol input symbol input symbol
control

control

control

control

control

control

control

control
S1 S2 S3 S4 S5 S6 S7 S8

output symbol output symbol output symbol output symbol output symbol output symbol output symbol output symbol

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

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

Left Half i-1

+
O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Right Half i

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 DES Key Schedule
 Forms subkeys used in each round

initial permutation of the key (PC1) which
selects 56-bits in two 28-bit halves

16 stages consisting of:
• rotating each half separately either 1 or 2 places
depending on the key rotation schedule K
• selecting 24-bits from each half & permuting them
by PC2 for use in round function F
 Note practical use issues in h/w vs s/w
 Key

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Discarded bits
 Initial permutation - PC1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36

63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

Left Rotation per round

Round number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Bits rotated 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Final permutation per round - PC2

14 17 11 24 1 5 3 28
15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40
51 45 33 48 44 49 39 56
34 53 46 42 50 36 29 32
 DES Key Schedule
64-bit key with parity bits
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

permuted
choice 1
57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4

56-bit key 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
Left
Shift
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 29

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

permuted
choice 2
14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

48-bit subkey 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
 DES Decryption
 decrypt must unwind steps of data computation
 with Feistel design, do encryption steps again
using subkeys in reverse order (SK16 … SK1)

IP undoes final FP step of encryption

1st round with SK16 undoes 16th encrypt round

….

16th round with SK1 undoes 1st encrypt round

then final FP undoes initial encryption IP

thus recovering original data value
 DES Round Decryption
Left half i-1 Right half i-1

Mangler
Function Round key i
F

+
O

Left half i Right half i

Decryption
DES Example
Avalanche in DES
 Avalanche Effect
 Key desirable property of encryption alg
 Where a change of one input or key bit
results in changing approx half output bits
 Making attempts to “home-in” by guessing
keys impossible
 DES exhibits strong avalanche
Change in Plaintext Change in Key

Round Number of bits that differ Round Number of bits that differ

0 1 0 0
1 6 1 2
2 21 2 14
3 35 3 28
4 39 4 32
5 34 5 30
6 32 6 32
7 31 7 35
8 29 8 34
9 42 9 40
10 44 10 38
11 32 11 31
12 30 12 33
13 30 13 28
14 26 14 26
15 29 15 34
16 34 16 35
 DES Design Criteria
 As reported by Coppersmith in [COPP94]
 7 criteria for S-boxes provide for

non-linearity

resistance to differential cryptanalysis

good confusion
 3 criteria for permutation P provide for

increased diffusion
(S-1)
Each S-box has six bits of input and four bits of output. (This was the largest
size that we could accommodate and still fit all of DES onto a single chip in
1974 technology.)

(S-2)
No output bit of an S-box should be too close to a linear function of the input
bits. (That is, if we select any output bit position and any subset of the six
input bit positions, the fraction of inputs for which this output bit equals the
XOR of these input bits should not be close to 0 or 1, but rather should be
near 1/2.)

(S-3)
If we fix the leftmost and rightmost input bits of the S-box and vary the four
middle bits, each possible 4-bit output is attained exactly once as the middle
four input bits range over their 16 possibilities.

(S-4)
If two inputs to an S-box differ in exactly one bit, the outputs must differ in at
least two bits.
(S-5)
If two inputs to an S-box differ in the two middle bits exactly, the outputs must
differ in at least two bits.

(S-6)
If two inputs to an S-box differ in their first two bits and are identical in their
last two bits, the two outputs must not be the same.

(S-7)
For any nonzero 6-bit difference between inputs, ΔIij no more than 8 of the
32 pairs of inputs exhibiting ΔIij may result in the same output difference
ΔOij

(S-8)
Similar to (S-7), but with stronger restrictions in the case ΔOij = 0, for the
case of three active S-boxes on round i
(P-1)
The four output bits from each S-box at round i are distributed so that two of
them affect (provide input for) “middle bits” of S-boxes at round i + 1 (the two
middle bits of input to an S-box, not shared with adjacent S-boxes), and the
other two affect “end bits” (the two left-hand bits or the two righthand bits,
which are shared with adjacent S-boxes).

(P-2)
The four output bits from each S-box affect six different S-boxes; no two affect
the same S-box. (Remember that each “end bit” affects two adjacent S-boxes.)

(P-3)
For two S-boxes j , k, if an output bit from S, affects a middle bit of Sk, then an
output bit from Sk cannot affect a middle bit of Sj. This implies that in the case j =
k, an output bit from Sj must not affect a middle bit of Sj.
 Strength of DES – Key Size
 56-bit keys have 256 = 7.2 x 1016 values
 Brute force search looks hard
 Recent advances have shown is possible

in 1997 on Internet in a few months

in 1998 on dedicated h/w (EFF) in a few days

in 1999 above combined in 22hrs!
 Still must be able to recognize plaintext
 Must now consider alternatives to DES
 Strength of DES – Analytic
Attacks
 Now have several analytic attacks on DES
 These utilise some deep structure of the cipher

by gathering information about encryptions

can eventually recover some/all of the sub-key bits

if necessary then exhaustively search for the rest
 Generally these are statistical attacks

differential cryptanalysis

linear cryptanalysis

related key attacks
 Strength of DES – Timing
Attacks
 Attacks actual implementation of cipher
 Use knowledge of consequences of
implementation to derive information about
some/all subkey bits
 Specifically use fact that calculations can
take varying times depending on the value
of the inputs to it
 Particularly problematic on smartcards
 Differential Cryptanalysis
 One of the most significant recent (public)
advances in cryptanalysis
 Known by NSA in 70's cf DES design
 Murphy, Biham & Shamir published in 90’s
 Powerful method to analyse block ciphers
 Used to analyse most current block
ciphers with varying degrees of success
 DES reasonably resistant to it, cf Lucifer
 Differential Cryptanalysis
 A statistical attack against Feistel ciphers
 Uses cipher structure not previously used
 Design of S-P networks has output of
function f influenced by both input & key
 Hence cannot trace values back through
cipher without knowing value of the key
 Differential cryptanalysis compares two
related pairs of encryptions
 Linear Cryptanalysis
 Another recent development
 Also a statistical method
 Must be iterated over rounds, with
decreasing probabilities
 Developed by Matsui et al in early 90's
 Based on finding linear approximations
 Can attack DES with 243 known plaintexts,
easier but still in practise infeasible
 DES Design Criteria
 As reported by Coppersmith in [COPP94]
 7 criteria for S-boxes provide for

non-linearity

resistance to differential cryptanalysis

good confusion
 3 criteria for permutation P provide for

increased diffusion
 Block Cipher Design
 Basic principles still like Feistel’s in 1970’s
 Number of rounds

more is better, exhaustive search best attack
 function f:

provides “confusion”, is nonlinear, avalanche

have issues of how S-boxes are selected
 Key schedule

complex subkey creation, key avalanche
 Design Of Function F
 Function F provides confusion.
 Should be nonlinear
 Achieved by Avalanche effect

Strict Avalanche Criterion (SAC)
• Any output bit j of substitution box should change
with probability ½ when any single input bit i is
inverted for all i, j.

Bit Independence Criterion (BIC)
• Output bit j and k should change independently
when input bit i is inverted for all i,j,k.
 Summary
 have considered:

block vs stream ciphers

Feistel cipher design & structure

DES
• details
• strength

Differential & Linear Cryptanalysis

block cipher design principles
Cryptography and
Network Security
Chapter 4
Fifth Edition
by William Stallings
Chapter 4 – Basic Concepts in
Number Theory and Finite
Fields
The next morning at daybreak, Star flew indoors, seemingly keen for
a lesson. I said, "Tap eight." She did a brilliant exhibition, first
tapping it in 4, 4, then giving me a hasty glance and doing it in 2, 2,
2, 2, before coming for her nut. It is astonishing that Star learned to
count up to 8 with no difficulty, and of her own accord discovered
that each number could be given with various different divisions, this
leaving no doubt that she was consciously thinking each number. In
fact, she did mental arithmetic, although unable, like humans, to
name the numbers. But she learned to recognize their spoken
names almost immediately and was able to remember the sounds of
the names. Star is unique as a wild bird, who of her own free will
pursued the science of numbers with keen interest and astonishing
intelligence.
— Living with Birds, Len Howard
 Introduction
 will now introduce finite fields
 of increasing importance in cryptography

AES, Elliptic Curve, IDEA, Public Key
 concern operations on “numbers”

where what constitutes a “number” and the
type of operations varies considerably
 start with basic number theory concepts
 Divisors
 say a non-zero number b divides a if for
some m have a=mb (a,b,m all integers)
 that is b divides into a with no remainder
 denote this b|a
 and say that b is a divisor of a
 eg. all of 1,2,3,4,6,8,12,24 divide 24
 eg. 13 | 182; –5 | 30; 17 | 289; –3 | 33; 17 | 0
 Properties of Divisibility
 If a|1, then a = ±1.
 If a|b and b|a, then a = ±b.
 Any b /= 0 divides 0.
 If a | b and b | c, then a | c

e.g. 11 | 66 and 66 | 198 so 11 | 198
 If b|g and b|h, then b|(mg + nh)
for arbitrary integers m and n
e.g. b = 7; g = 14; h = 63; m = 3; n = 2
7|14 and 7|63 hence 7 | 42+126 = 168
 Division Algorithm
 if divide a by n get integer quotient q and
integer remainder r such that:

a = qn + r where 0 <= r < n; q = floor(a/n)
 remainder r often referred to as a residue
Greatest Common Divisor (GCD)
 a common problem in number theory
 GCD (a,b) of a and b is the largest integer
that divides evenly into both a and b

eg GCD(60,24) = 12
 define gcd(0, 0) = 0
 often want no common factors (except 1)
define such numbers as relatively prime

eg GCD(8,15) = 1

hence 8 & 15 are relatively prime
 Example GCD(1970,1066)
1970 = 1 x 1066 + 904 gcd(1066, 904)
1066 = 1 x 904 + 162 gcd(904, 162)
904 = 5 x 162 + 94 gcd(162, 94)
162 = 1 x 94 + 68 gcd(94, 68)
94 = 1 x 68 + 26 gcd(68, 26)
68 = 2 x 26 + 16 gcd(26, 16)
26 = 1 x 16 + 10 gcd(16, 10)
16 = 1 x 10 + 6 gcd(10, 6)
10 = 1 x 6 + 4 gcd(6, 4)
6 = 1 x 4 + 2 gcd(4, 2)
4 = 2 x 2 + 0 gcd(2, 0)
 GCD(1160718174, 316258250)
Dividend Divisor Quotient Remainder
a = 1160718174 b = 316258250 q1 = 3 r1 = 211943424
b = 316258250 r1 = 211943424 q2 = 1 r2 = 104314826
r1 = 211943424 r2 = 104314826 q3 = 2 r3 = 3313772
r2 = 104314826 r3 = 3313772 q4 = 31 r4 = 1587894
r3 = 3313772 r4 = 1587894 q5 = 2 r5 = 137984
r4 = 1587894 r5 = 137984 q6 = 11 r6 = 70070
r5 = 137984 r6 = 70070 q7 = 1 r7 = 67914
r6 = 70070 r7 = 67914 q8 = 1 r8 = 2156
r7 = 67914 r8 = 2156 q9 = 31 r9 = 1078
r8 = 2156 r9 = 1078 q10 = 2 r10 = 0
 Modular Arithmetic
 define modulo operator “a mod n” to be
remainder when a is divided by n

where integer n is called the modulus
 b is called a residue of a mod n

since with integers can always write: a = qn + b

usually chose smallest positive remainder as residue
• ie. 0 <= b <= n-1

process is known as modulo reduction
• eg. -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7
 a & b are congruent if: a mod n = b mod n

when divided by n, a & b have same remainder

eg. 100 mod 11 = 34 mod 11
so 100 is congruent to 34 mod 11
Modular Arithmetic Operations
 can perform arithmetic with residues
 uses a finite number of values, and loops
back from either end
Zn = {0, 1, . . . , (n – 1)}
 modular arithmetic is when do addition &
multiplication and modulo reduce answer
 can do reduction at any point, ie

a+b mod n = [a mod n + b mod n] mod n
Modular Arithmetic Operations
1. [(a mod n) + (b mod n)] mod n
= (a + b) mod n
2. [(a mod n) – (b mod n)] mod n
= (a – b) mod n
3. [(a mod n) x (b mod n)] mod n
= (a x b) mod n
e.g.
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) – (15 mod 8)] mod 8 = –4 mod 8 = 4 (11 – 15) mod 8 = –4 mod 8 = 4
[(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 x 15) mod 8 = 165 mod 8 = 5
Modulo 8 Addition Example
+ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 0
2 2 3 4 5 6 7 0 1
3 3 4 5 6 7 0 1 2
4 4 5 6 7 0 1 2 3
5 5 6 7 0 1 2 3 4
6 6 7 0 1 2 3 4 5
7 7 0 1 2 3 4 5 6
Modulo 8 Multiplication
+ 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
Modular Arithmetic Properties
 Euclidean Algorithm
 an efficient way to find the GCD(a,b)
 uses theorem that:

GCD(a,b) = GCD(b, a mod b)
 Euclidean Algorithm to compute GCD(a,b) is:
Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);
Extended Euclidean Algorithm
 calculates not only GCD but x & y:

ax + by = d = gcd(a, b)
 useful for later crypto computations
 follow sequence of divisions for GCD but
assume at each step i, can find x &y:
r = ax + by
 at end find GCD value and also x & y
 if GCD(a,b)=1 these values are inverses
 Finding Inverses
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
Inverse of 550 in GF(1759)
Q A1 A2 A3 B1 B2 B3
— 1 0 1759 0 1 550
3 0 1 550 1 –3 109
5 1 –3 109 –5 16 5
21 –5 16 5 106 –339 4
1 106 –339 4 –111 355 1
 Group
 a set S of elements or “numbers”

may be finite or infinite
 with some operation ‘.’ so G=(S,.)
 Obeys CAIN:

Closure: a,b in S, then a.b in S

Associative law: (a.b).c = a.(b.c)

has Identity e: e.a = a.e = a

has iNverses a-1: a.a-1 = e
 if commutative a.b = b.a

then forms an abelian group
 Cyclic Group
 define exponentiation as repeated
application of operator

example: a3 = a.a.a
 and let identity be: e=a0
 a group is cyclic if every element is a
power of some fixed element a

i.e., b = ak for some a and every b in group
 a is said to be a generator of the group
 Ring
 a set of “numbers”
 with two operations (addition and multiplication)
which form:
 an abelian group with addition operation
 and multiplication:

has closure

is associative

distributive over addition: a(b+c) = ab + ac
 if multiplication operation is commutative, it
forms a commutative ring
 if multiplication operation has an identity and no
zero divisors, it forms an integral domain
 Field
 a set of numbers
 with two operations which form:

abelian group for addition

abelian group for multiplication (ignoring 0)

ring
 have hierarchy with more axioms/laws

group -> ring -> field
Group, Ring, Field
 Finite (Galois) Fields
 finite fields play a key role in cryptography
 can show number of elements in a finite
field must be a power of a prime pn
 known as Galois fields
 denoted GF(pn)
 in particular often use the fields:

GF(p)

GF(2n)
 Galois Fields GF(p)
 GF(p) is the set of integers {0,1, … , p-1}
with arithmetic operations modulo prime p
 these form a finite field

since have multiplicative inverses

find inverse with Extended Euclidean algorithm
 hence arithmetic is “well-behaved” and can
do addition, subtraction, multiplication, and
division without leaving the field GF(p)
GF(7) Multiplication Example
 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
 Polynomial Arithmetic
 can compute using polynomials
f(x) = anxn + an-1xn-1 + … + a1x + a0 = ∑ aixi
• n.b. not interested in any specific value of x
• which is known as the indeterminate
 several alternatives available

ordinary polynomial arithmetic

poly arithmetic with coefs mod p

poly arithmetic with coefs mod p and
polynomials mod m(x)
Ordinary Polynomial Arithmetic
 add or subtract corresponding coefficients
 multiply all terms by each other
 eg
let f(x) = x3 + x2 + 2 and g(x) = x2 – x + 1
f(x) + g(x) = x3 + 2x2 – x + 3
f(x) – g(x) = x3 + x + 1
f(x) x g(x) = x5 + 3x2 – 2x + 2
 Polynomial Arithmetic with
Modulo Coefficients
 when computing value of each coefficient
do calculation modulo some value

forms a polynomial ring
 could be modulo any prime
 but we are most interested in mod 2

ie all coefficients are 0 or 1

eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1
f(x) + g(x) = x3 + x + 1
f(x) x g(x) = x5 + x2
 Polynomial Division
 can write any polynomial in the form:

f(x) = q(x) g(x) + r(x)

can interpret r(x) as being a remainder

r(x) = f(x) mod g(x)
 if have no remainder say g(x) divides f(x)
 if g(x) has no divisors other than itself & 1
say it is irreducible (or prime) polynomial
 arithmetic modulo an irreducible
polynomial forms a field
 Polynomial GCD
 can find greatest common divisor for polys

c(x) = GCD(a(x), b(x)) if c(x) is the poly of greatest
degree which divides both a(x), b(x)
 can adapt Euclid’s Algorithm to find it:
Euclid(a(x), b(x))
if (b(x)=0) then return a(x);
else return
Euclid(b(x), a(x) mod b(x));
 all foundation for polynomial fields as see next
 Modular Polynomial
Arithmetic
 can compute in field GF(2n)

polynomials with coefficients modulo 2

whose degree is less than n

hence must reduce modulo an irreducible poly
of degree n (for multiplication only)
 form a finite field
 can always find an inverse

can extend Euclid’s Inverse algorithm to find
Example GF(23)
 Computational
Considerations
 since coefficients are 0 or 1, can represent
any such polynomial as a bit string
 addition becomes XOR of these bit strings
 multiplication is shift & XOR

cf long-hand multiplication
 modulo reduction done by repeatedly
substituting highest power with remainder
of irreducible poly (also shift & XOR)
 Computational Example
 in GF(23) have (x2+1) is 1012 & (x2+x+1) is 1112
 so addition is

(x2+1) + (x2+x+1) = x

101 XOR 111 = 0102
 and multiplication is

(x+1).(x2+1) = x.(x2+1) + 1.(x2+1)
= x3+x+x2+1 = x3+x2+x+1

011.101 = (101)<<1 XOR (101)<<0 =
1010 XOR 101 = 11112
 polynomial modulo reduction (get q(x) & r(x)) is

(x3+x2+x+1 ) mod (x3+x+1) = 1.(x3+x+1) + (x2) = x2

1111 mod 1011 = 1111 XOR 1011 = 01002
 Using a Generator
 equivalent definition of a finite field
 a generator g is an element whose
powers generate all non-zero elements

in F have 0, g0, g1, …, gq-2
 can create generator from root of the
irreducible polynomial
 then implement multiplication by adding
exponents of generator
 Summary
 have considered:

divisibility & GCD

modular arithmetic with integers

concept of groups, rings, fields

Euclid’s algorithm for GCD & Inverse

finite fields GF(p)

polynomial arithmetic in general and in GF(2n)
Cryptography and
Network Security
Chapter 5
Fifth Edition
by William Stallings
Chapter 5 –Advanced Encryption
Standard

"It seems very simple."

"It is very simple. But if you don't know what
the key is it's virtually indecipherable."
—Talking to Strange Men, Ruth Rendell
 AES Origins
 clear a replacement for DES was needed

have theoretical attacks that can break it

have demonstrated exhaustive key search attacks
 can use Triple-DES – but slow, has small blocks
 US NIST issued call for ciphers in 1997
 15 candidates accepted in Jun 98
 5 were shortlisted in Aug-99
 Rijndael was selected as the AES in Oct-2000
 issued as FIPS PUB 197 standard in Nov-2001
 AES Requirements
 Private key symmetric block cipher
 128-bit data, 128/192/256-bit keys
 Stronger & faster than Triple-DES
 Active life of 20-30 years (+ archival use)
 Provide full specification & design details
 NIST have released all submissions &
unclassified analyses
 Evaluation Criteria
 Initial criteria:

security – effort for practical cryptanalysis

cost – in terms of computational efficiency

algorithm & implementation characteristics
 Final criteria

general security

ease of software & hardware implementation

implementation attacks

flexibility (in en/decrypt, keying, other factors)
SECURITY

•Actual security: compared to other submitted

algorithms (at the same key and block size).

•Randomness: the extent to which the algorithm

output is indistinguishable from a random permutation
on the input block.

•Soundness: of the mathematical basis for the

algorithm's security.

•Other security factors: raised by the public during

the evaluation process, including any attacks which
demonstrate that the actual security of the algorithm is
less than the strength claimed by the submitter.
COST

•Licensing requirements: NIST intends that when the AES

is issued, the algorithm(s) specified in the AES shall be
available on a worldwide, non-exclusive, royalty-free basis.

•Computational efficiency: The evaluation of computational

efficiency will be applicable to both hardware and software
implementations. Round 1 analysis by NIST will focus
primarily on software implementations and specifically on
one key-block size combination (128-128); more attention
will be paid to hardware implementations and other
supported key-block size combinations during Round 2
analysis.
Computational efficiency essentially refers to the speed of the
algorithm. Public comments on each algorithm's efficiency
(particularly for various platforms and applications) will also
be taken into consideration by NIST.
COST

•Memory requirements: The memory required to implement

a candidate algorithm—for both hardware and software
implementations of the algorithm--will also be considered
during the evaluation process.

Round 1 analysis by NIST will focus primarily on software

implementations; more attention will be paid to hardware
implementations during Round 2.
Memory requirements will include such factors as gate
counts for hardware implementations, and code size and
RAM requirements for software implementations.
ALGORITHM AND IMPLEMENTATION CHARACTERISTICS

•Flexibility: Candidate algorithms with greater flexibility will meet

the needs of more users than less flexible ones, and therefore,
inter alia, are preferable. However, some extremes of functionality
are of little practical application (e.g., extremely short key lengths);
for those cases, preference will not be given. Some examples of
flexibility may include (but are not limited to) the following:
a. The algorithm can accommodate additional key- and block-
sizes (e.g., 64-bit block sizes, key sizes other than those
specified in the Minimum Acceptability Requirements section,
[e.g., keys between 128 and 256 that are multiples of 32 bits,
etc.])
b. The algorithm can be implemented securely and efficiently in
a wide variety of platforms and applications (e.g., 8-bit
processors, ATM networks, voice & satellite communications,
HDTV, B-ISDN, etc.).
c. The algorithm can be implemented as a stream cipher,
message authentication code (MAC) generator,
pseudorandom number generator, hashing algorithm, etc.
ALGORITHM AND IMPLEMENTATION CHARACTERISTICS

•Hardware and software suitability: A candidate algorithm shall

not be restrictive in the sense that it can only be implemented in
hardware. If one can also implement the algorithm efficiently in
firmware, then this will be an advantage in the area of flexibility.

•Simplicity: A candidate algorithm shall be judged according to

relative simplicity of design.
 AES Shortlist
 After testing and evaluation, shortlist in Aug-99:

MARS (IBM) - complex, fast, high security margin

RC6 (USA) - v. simple, v. fast, low security margin

Rijndael (Belgium) - clean, fast, good security margin

Serpent (Euro) - slow, clean, v. high security margin

Twofish (USA) - complex, v. fast, high security margin
 then subject to further analysis & comment
 Contrast between algorithms with

few complex rounds verses many simple rounds

which refined existing ciphers verses new proposals
 The AES Cipher - Rijndael
 designed by Rijmen-Daemen in Belgium
 has 128/192/256 bit keys, 128 bit data
 an iterative rather than Feistel cipher

processes data as block of 4 columns of 4 bytes

operates on entire data block in every round
 designed to have:

resistance against known attacks

speed and code compactness on many CPUs

design simplicity
 AES Parameters

Key Size ( word/byte/bits) 4/16/128 6/24/192 8/32/256

Plaintext Block Size ( word/byte/bits) 4/16/128 4/16/128 4/16/128

Number of Rounds 10 12 14
Round Key Size ( word/byte/bits) 4/16/128 4/16/128 4/16/128
Expanded Key Size ( word/byte) 44/176 52/208 60/240
 AES
Encryption
Process
 AES Structure
 data block of 4 columns of 4 bytes is state
 key is expanded to array of words
 has 9/11/13 rounds in which state undergoes:

byte substitution (1 S-box used on every byte)

shift rows (permute bytes between groups/columns)

mix columns (subs using matrix multiply of groups)

add round key (XOR state with key material)

view as alternating XOR key & scramble data bytes
 initial XOR key material & incomplete last round
 with fast XOR & table lookup implementation
AES Structure
 Some Comments on AES
1. an iterative rather than Feistel cipher
2. key expanded into array of 32-bit words
1. four words form round key in each round
3. 4 different stages are used as shown
4. has a simple structure
5. only AddRoundKey uses key
6. AddRoundKey a form of Vernam cipher
7. each stage is easily reversible
8. decryption uses keys in reverse order
9. decryption does recover plaintext
10. final round has only 3 stages
 Substitute Bytes
 a simple substitution of each byte
 uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
 each byte of state is replaced by byte indexed
by row (left 4-bits) & column (right 4-bits)

eg. byte {95} is replaced by byte in row 9 column 5

which has value {2A}
 S-box constructed using defined transformation
of values in GF(28)
 designed to be resistant to all known attacks
Substitute Bytes
Substitute Bytes Example
 Shift Rows
 a circular byte shift in each each

1st row is unchanged

2nd row does 1 byte circular shift to left

3rd row does 2 byte circular shift to left

4th row does 3 byte circular shift to left
 decrypt inverts using shifts to right
 since state is processed by columns, this step
permutes bytes between the columns
Shift Rows
 Mix Columns
 each column is processed separately
 each byte is replaced by a value
dependent on all 4 bytes in the column
 effectively a matrix multiplication in GF(28)
using prime poly m(x) =x8+x4+x3+x+1
Mix Columns
Mix Columns Example
 AES Arithmetic
 uses arithmetic in the finite field GF(28)
 with irreducible polynomial
m(x) = x8 + x4 + x3 + x + 1
which is (100011011) or {11b}
 e.g.
{02} • {87} mod {11b} = (1 0000 1110) mod {11b}
= (1 0000 1110) xor (1 0001 1011) = (0001 0101)
 Mix Columns
 can express each col as 4 equations

to derive each new byte in col
 decryption requires use of inverse matrix

with larger coefficients, hence a little harder
 have an alternate characterisation

each column a 4-term polynomial

with coefficients in GF(28)

and polynomials multiplied modulo (x4+1)
 coefficients based on linear code with
maximal distance between codewords
Mix Columns - Decryption
 Add Round Key
 XOR state with 128-bits of the round key
 again processed by column (though
effectively a series of byte operations)
 inverse for decryption identical

since XOR own inverse, with reversed keys
 designed to be as simple as possible

a form of Vernam cipher on expanded key

requires other stages for complexity / security
Add Round Key
AES Round
 AES Key Expansion
 takes 128-bit (16-byte) key and expands
into array of 44/52/60 32-bit words
 start by copying key into first 4 words
 then loop creating words that depend on
values in previous & 4 places back

in 3 of 4 cases just XOR these together

1st word in 4 has rotate + S-box + XOR round
constant on previous, before XOR 4th back
AES Key Expansion
 Key Expansion Rationale
 designed to resist known attacks
 design criteria included

knowing part key insufficient to find many more

invertible transformation

fast on wide range of CPU’s

use round constants to break symmetry

diffuse key bits into round keys

enough non-linearity to hinder analysis

simplicity of description
 AES
Example
Key
Expansion
 AES
Example
Encryption
 AES
Example
Avalanche
 AES Decryption
 AES decryption is not identical to
encryption since steps done in reverse
 but can define an equivalent inverse
cipher with steps as for encryption

but using inverses of each step

with a different key schedule
 works since result is unchanged when

swap byte substitution & shift rows

swap mix columns & add (tweaked) round key
AES Decryption
 Implementation Aspects
 can efficiently implement on 8-bit CPU

byte substitution works on bytes using a table
of 256 entries

shift rows is simple byte shift

add round key works on byte XOR’s

mix columns requires matrix multiply in GF(28)
which works on byte values, can be simplified
to use table lookups & byte XOR’s
 Implementation Aspects
 can efficiently implement on 32-bit CPU

redefine steps to use 32-bit words

can precompute 4 tables of 256-words

then each column in each round can be
computed using 4 table lookups + 4 XORs

at a cost of 4Kb to store tables
 designers believe this very efficient
implementation was a key factor in its
selection as the AES cipher
General Security
Rijndael has no known security attacks. Rijndael uses S-boxes as nonlinear
components. Rijndael appears to have an adequate security margin, but
has received some criticism suggesting that its mathematical structure may
lead to attacks. On the other hand, the simple structure may have facilitated
its security analysis during the timeframe of the AES development process.

Software Implementations
Rijndael performs encryption and decryption very well across a variety of
platforms,
including 8-bit and 64-bit platforms, and DSPs. However, there is a
decrease in performance with the higher key sizes because of the increased
number of rounds that are performed. Rijndael’s high inherent parallelism
facilitates the efficient use of processor resources, resulting in very good
software performance even when implemented in a mode not capable of
interleaving. Rijndael’s key setup time is fast.
Restricted-Space Environments
In general, Rijndael is very well suited for restricted-space environments
where either
encryption or decryption is implemented (but not both). It has very low RAM
and ROM requirements. A drawback is that ROM requirements will increase
if both encryption and decryption are implemented simultaneously, although
it appears to remain suitable for these environments. The key schedule for
decryption is separate from encryption.

Hardware Implementations
Rijndael has the highest throughput of any of the finalists for feedback
modes and second highest for non-feedback modes. For the 192 and 256-
bit key sizes, throughput falls in standard and unrolled implementations
because of the additional number of rounds. For fully pipelined
implementations, the area requirement increases, but the throughput is
unaffected.
Attacks on Implementations
The operations used by Rijndael are among the easiest to defend against
power and timing attacks. The use of masking techniques to provide
Rijndael with some defense against these attacks does not cause significant
performance degradation relative to the other finalists, and its RAM
requirement remains reasonable. Rijndael appears to gain a major speed
advantage over its competitors when such protections are considered.

Encryption vs. Decryption

The encryption and decryption functions in Rijndael differ. One FPGA study
reports that the implementation of both encryption and decryption takes
about 60% more space than the implementation of encryption alone.
Rijndael’s speed does not vary significantly between encryption and
decryption, although the key setup performance is slower for decryption
than for encryption.
Key Agility
Rijndael supports on-the-fly subkey computation for encryption. Rijndael
requires a one-time execution of the key schedule to generate all subkeys
prior to the first decryption with a specific key. This places a slight resource
burden on the key agility of Rijndael.

Other Versatility and Flexibility

Rijndael fully supports block sizes and key sizes of 128 bits, 192 bits and
256 bits, in any combination. In principle, the Rijndael structure can
accommodate any block sizes and key sizes that are multiples of 32, as well
as changes in the number of rounds that are specified.

Potential for Instruction-Level Parallelism

Rijndael has an excellent potential for parallelism for a single block
encryption.
 Summary
 have considered:

the AES selection process

the details of Rijndael – the AES cipher

looked at the steps in each round

the key expansion

implementation aspects
Cryptography and
Network Security
Chapter 6
Fifth Edition
by William Stallings
 Chapter 6 – Block Cipher
Operation
Many savages at the present day regard
their names as vital parts of themselves,
and therefore take great pains to conceal
their real names, lest these should give to
evil-disposed persons a handle by which
to injure their owners.
— The Golden Bough, Sir James George
Frazer
 Multiple Encryption & DES
 Clear a replacement for DES was needed

theoretical attacks that can break it

demonstrated exhaustive key search attacks
 AES is a new cipher alternative
 Prior to this alternative was to use multiple
encryption with DES implementations
 Triple-DES is the chosen form
 Why not Double-DES?
 Could use 2 DES encrypts on each block
 C = EK2(EK1(P))
 Concern at time of reduction to single stage
 “meet-in-the-middle” attack

works whenever use a cipher twice
 since X = EK1(P) = DK2(C)

attack by encrypting P with all keys and store

then decrypt C with keys and match X value

can show takes O(256) steps

Requires…
known plaintext
 Triple-DES with Two-Keys
 Hence must use 3 encryptions

would seem to need 3 distinct keys
 But can use 2 keys with E-D-E sequence

C = EK1(DK2(EK1(P)))

n.b. encrypt & decrypt equivalent in security

if K1=K2 then can work with single DES
 standardized in ANSI X9.17 & ISO8732
 No current known practical attacks

several proposed impractical attacks might
become basis of future attacks
 Triple-DES with Three-Keys
 Although are no practical attacks on two-
key Triple-DES have some indications
 Can use Triple-DES with Three-Keys to
avoid even these
 C = EK3(DK2(EK1(P)))
 Has been adopted by some Internet
applications, e.g., PGP, S/MIME
 Modes of Operation
 block ciphers encrypt fixed size blocks

e.g., DES encrypts 64-bit blocks
 Need some way to en/decrypt arbitrary
amounts of data in practice
 NIST SP 800-38A defines 5 modes
 Have block and stream modes
 To cover a wide variety of applications
 Can be used with any block cipher
Electronic Codebook Book (ECB)
 Message is broken into independent
blocks that are encrypted
 Each block is a value which is substituted,
like a codebook, hence name
 Each block is encoded independently of
the other blocks
Ci = EK(Pi)
 uses: secure transmission of single values
Electronic
Codebook
Book
(ECB)
 Advantages and Limitations of
ECB
 Message repetitions may show in ciphertext

if aligned with message block

particularly with data such graphics

or with messages that change very little, which
become a code-book analysis problem
 Weakness is due to the encrypted message
blocks being independent
 Vulnerable to cut-and-paste attacks
 Main use is sending a few blocks of data
Cipher Block Chaining (CBC)
 Message is broken into blocks
 Linked together in encryption operation
 Each previous cipher blocks is chained with
current plaintext block, hence name
 Use Initial Vector (IV) to start process
Ci = EK(Pi XOR Ci-1)
C-1 = IV
 IV prevents same P from making same C
 uses: bulk data encryption, authentication
 Cipher
Block
Chaining
(CBC)
 Message Padding
 Atend of message must handle a possible
last short block

which is not as large as blocksize of cipher

pad either with known non-data value (eg nulls)

or pad last block along with count of pad size
• eg. [ b1 b2 b3 0 0 0 0 5]
• means have 3 data bytes, then 5 bytes pad+count

this may require an extra entire block over
those in message
 There are other, more esoteric modes,
which avoid the need for an extra block
 Ciphertext Stealing

 Use to make ciphertext length same as

plaintext length
 Requires more than one block of plaintext
Pn-1 Pn

En-1

Head n T
Pn T

En-1 Head n
 Advantages and Limitations of
CBC
A ciphertext block depends on all blocks
before it
 Any change to a block affects all following
ciphertext blocks... avalanche effect
 need Initialization Vector (IV)

which must be known to sender & receiver

if sent in clear, attacker can change bits of first block, by
changing corresponding bits of IV

hence IV must either be a fixed value (as in EFTPOS)

or derived in way hard to manipulate

or sent encrypted in ECB mode before rest of message

or message integrity must be checked otherwise
 Stream Modes of Operation
 Block modes encrypt entire block
 May need to operate on smaller units

real time data
 Convert block cipher into stream cipher

cipher feedback (CFB) mode

output feedback (OFB) mode

counter (CTR) mode
 Use block cipher as some form of
pseudo-random number generator...
Vernam cipher
 Cipher FeedBack (CFB)
 Message is treated as a stream of bits
 Added to the output of the block cipher
 Result is feed back for next stage (hence
name)
 Standard allows any number of bits (1,8, 64 or
128 etc) to be feed back

denoted CFB-1, CFB-8, CFB-64, CFB-128, etc.
 Most efficient to use all bits in block (64 or 128)
Ci = Pi XOR EK(Ci-1)
C-1 = IV

 s-bit
Cipher
FeedBack
(CFB-s)
 Advantages and Limitations of
CFB
 Most common stream mode
 Appropriate when data arrives in bits/bytes
 Limitation is need to stall while do block
encryption after every s-bits
 Note that the block cipher is used in
encryption mode at both ends (XOR)
 Errors propagate for several blocks after
the error ... how many?
 Output FeedBack (OFB)
 Message is treated as a stream of bits
 Output of cipher is added to message
 Output is then feed back (hence name)
Oi = EK(Oi-1)
Ci = Pi XOR Oi
O-1 = IV
 Feedback is independent of message
 Can be computed in advance
 uses: stream encryption on noisy channels
Why noisy channels?
 Output
FeedBack
(OFB)
 Advantages and Limitations of
OFB
 Needs an IV which is unique for each use

if ever reuse attacker can recover outputs...

OTP
 Can pre-compute
 Bit errors do not propagate
 More vulnerable to message stream modification...

change arbitrary bits by changing ciphertext
 Sender & receiver must remain in sync
 Only use with full block feedback

subsequent research has shown that only full block feedback
(ie CFB-64 or CFB-128) should ever be used
 Counter (CTR)
 A “new” mode, though proposed early on
 Similar to OFB but encrypts counter value rather
than any feedback value
Oi = EK(i)
Ci = Pi XOR Oi
 Must have a different key & counter value for
every plaintext block (never reused)

again, OTP issue
 uses: high-speed network encryptions
Counter
(CTR)
 Advantages and Limitations of
CTR
 Efficiency

can do parallel encryptions in h/w or s/w

can preprocess in advance of need

good for bursty high speed links
 Random access to encrypted data blocks
 Provable security (good as other modes)
 Never have cycle less than 2 b
 But must ensure never reuse key/counter
values, otherwise could break (cf OFB)
Feedback
Character-
istics
 XTS-AES Mode
 New mode, for block oriented storage use

in IEEE Std 1619-2007
 Concept of tweakable block cipher
 Different requirements to transmitted data
 Uses AES twice for each block
Tj = EK2(i) XOR αj
Cj = EK1(Pj XOR Tj) XOR Tj
where i is tweak & j is sector no
 Each sector may have multiple blocks
XTS-AES
Mode
per block
XTS-AES
Mode
Overview
 Advantages and Limitations of
XTS-AES
 Eiciency

can do parallel encryptions in h/w or s/w

random access to encrypted data blocks
 Has both nonce & counter
 Addresses security concerns related to
stored data
 Criteria For Comparison
 Can a random block be encrypted or
decrypted?
 How much does a error in transmission
affect the receiver?
 Is parallel encryption/decryption possible?
 Can the keystream be pre computed?
 Summary
 Multiple Encryption & Triple-DES
 Modes of Operation

ECB, CBC, CFB, OFB, CTR, XTS-AES
 Next – Stream ciphers (Ch 7), then hash
functions (Ch 11)
Cryptography and
Network Security
Chapter 8
Fifth Edition
by William Stallings
 Chapter 8 – Introduction to
Number Theory
The Devil said to Daniel Webster: "Set me a task I can't carry out, and
I'll give you anything in the world you ask for."
Daniel Webster: "Fair enough. Prove that for n greater than 2, the
equation an + bn = cn has no non-trivial solution in the integers."
They agreed on a three-day period for the labor, and the Devil
disappeared.
At the end of three days, the Devil presented himself, haggard, jumpy,
biting his lip. Daniel Webster said to him, "Well, how did you do at
my task? Did you prove the theorem?'
"Eh? No . . . no, I haven't proved it."
"Then I can have whatever I ask for? Money? The Presidency?'
"What? Oh, that—of course. But listen! If we could just prove the
following two lemmas—"
—The Mathematical Magpie, Clifton Fadiman
 Prime Numbers
 prime numbers only have divisors of 1 and self

they cannot be written as a product of other numbers

note: 1 is prime, but is generally not of interest
 eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
 prime numbers are central to number theory
 list of prime number less than 200 is:
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
 Prime Factorisation
 to factor a number n is to write it as a
product of other numbers: n=a x b x c
 note that factoring a number is relatively
hard compared to multiplying the factors
together to generate the number
 the prime factorisation of a number n is
when its written as a product of primes

eg. 91=7x13 ; 3600=24x32x52
Relatively Prime Numbers & GCD
 two numbers a, b are relatively prime if have
no common divisors apart from 1

eg. 8 & 15 are relatively prime since factors of 8 are
1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only
common factor
 conversely can determine the greatest common
divisor by comparing their prime factorizations
and using least powers

eg. 300=21x31x52 18=21x32 hence
GCD(18,300)=21x31x50=6
 Fermat's Theorem
 ap-1 ≡ 1 (mod p)

where p is prime and gcd(a,p)=1
 also known as Fermat’s Little Theorem
 also have: ap ≡ a (mod p)
 useful in public key and primality testing
 Euler Totient Function ø(n)
 when doing arithmetic modulo n
 complete set of residues is: 0..n-1
 reduced set of residues is those numbers
(residues) which are relatively prime to n

eg for n=10,

complete set of residues is {0,1,2,3,4,5,6,7,8,9}

reduced set of residues is {1,3,7,9}
 number of elements in reduced set of residues is
called the Euler Totient Function ø(n)
 Euler Totient Function ø(n)
 to compute ø(n) need to count number of
residues to be excluded
 in general need prime factorization, but

for p (p prime) ø(p)=p-1

for p.q (p,q prime) ø(p.q)=(p-1)x(q-1)
 eg.
ø(37) = 36
ø(21) = (3–1)x(7–1) = 2x6 = 12
 Euler's Theorem
 a generalisation of Fermat's Theorem
 aø(n) ≡ 1 (mod n)

for any a,n where gcd(a,n)=1
 eg.
a=3;n=10; ø(10)=4;
hence 34 = 81 = 1 mod 10
a=2;n=11; ø(11)=10;
hence 210 = 1024 = 1 mod 11
 also have: aø(n)+1 ≡ a (mod n)
 Primality Testing
 often need to find large prime numbers
 traditionally sieve using trial division

ie. divide by all numbers (primes) in turn less than the
square root of the number

only works for small numbers
 alternatively can use statistical primality tests
based on properties of primes

for which all primes numbers satisfy property

but some composite numbers, called pseudo-primes,
also satisfy the property
 can use a slower deterministic primality test
 Miller Rabin Algorithm
 a test based on prime properties that result from
Fermat’s Theorem
 algorithm is:
TEST (n) is:
1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq
2. Select a random integer a, 1<a<n–1
3. if aq mod n = 1 then return (“inconclusive");
4. for j = 0 to k – 1 do
j
5. if (a2 q mod n = n-1)
then return(“inconclusive")
6. return (“composite")
 Probabilistic Considerations
 ifMiller-Rabin returns “composite” the number
is definitely not prime
 otherwise is a prime or a pseudo-prime
 chance it detects a pseudo-prime is < 1/4
 hence if repeat test with different random a
then chance n is prime after t tests is:

Pr(n prime after t tests) = 1-4-t

eg. for t=10 this probability is > 0.99999
 could then use the deterministic AKS
(Agrawal–Kayal–Saxena) test
 Prime Distribution
 prime number theorem states that primes
occur roughly every (ln n) integers
 but can immediately ignore evens
 so in practice need only test 0.5 ln(n)
numbers of size n to locate a prime

note this is only the “average”

sometimes primes are close together

other times are quite far apart
Chinese Remainder Theorem
 used to speed up modulo computations
 if working modulo a product of numbers
 eg. mod M = m1m2..mk
 Chinese Remainder theorem lets us work
in each moduli mi separately
 since computational cost is proportional to
size, this is faster than working in the full
modulus M
Chinese Remainder Theorem
 can implement CRT in several ways
 to compute A(mod M)

first compute all ai = A mod mi separately

determine constants ci below, where Mi = M/mi

then combine results to get answer using:
 CRT Example – Addition 1/2
Given 973 mod 1813

Now 1813 = 37 x 49

Therefore m1 = 37, m2 = 49, M = 1813, A = 937

M1 = M/m1 = M/37 = 49, M2 = M/m2 = M/ 49 = 37

Calculate inverses of M1 and M2 using Extended Euclidian Algorithm

M1-1 = 34 mod m1 = 34, M2-1 = 4 mod m2 = 4

A = (a1, a2) where a1 = 973 mod 37 = 11, a2 = 973 mod 49 = 42

= ( 11, 42)
 CRT Example – Addition 2/2
We wish to add 678 to 973 i.e. calculate S = ( 678 + 973 ) mod 1813

Let B = 678

B = (b1, b2) where b1 = 678 mod 37 = 12, b2 = 678 mod 49 = 41

= ( 12, 41)

S = (s1, s2), s1 = (a1 + b1) mod 37 = 23, s2 = (a2 + b2) mod 49 = 34

= (23, 34)

S = [ s1 x M1 x M1-1 + s2 x M2 x M2-1 ] mod 1813

= [ 23 x 49 x 34 + 34 x 37 x 4 ] mod 1813 = 43350 mod 1813 = 1651

 Primitive Roots
 from Euler’s theorem have aø(n)mod n≡1
 consider am≡1 (mod n), GCD(a,n)=1

must exist for m = ø(n) but may be smaller

once powers reach m, cycle will repeat
 if smallest is m = ø(n) then a is called a
primitive root
 if p is prime, then successive powers of a
"generate" the group mod p
 these are useful but relatively hard to find
Powers mod 19
 Discrete Logarithms
 the inverse problem to exponentiation is to find
the discrete logarithm of a number modulo p
 that is to find i such that b = ai (mod p)
 this is written as i = dloga b (mod p)
 if a is a primitive root then it always exists,
otherwise it may not, eg.
x = log3 4 mod 13 has no answer
x = log2 3 mod 13 = 4 by trying successive powers
 whilst exponentiation is relatively easy, finding
discrete logarithms is generally a hard problem
Discrete Logarithms mod 19
 Summary
 have considered:

prime numbers

Fermat’s and Euler’s Theorems & ø(n)

Primality Testing

Chinese Remainder Theorem

Primitive Roots & Discrete Logarithms
Cryptography and
Network Security
Chapter 9
Fifth Edition
by William Stallings
 Chapter 9 – Public Key
Cryptography and RSA

Every Egyptian received two names, which were

known respectively as the true name and the
good name, or the great name and the little
name; and while the good or little name was
made public, the true or great name appears to
have been carefully concealed.
—The Golden Bough, Sir James George Frazer
 Private-Key Cryptography
 traditional private/secret/single key
cryptography uses one key
 shared by both sender and receiver
 if this key is disclosed communications are
compromised
 also is symmetric, parties are equal
 hence does not protect sender from
receiver forging a message & claiming is
sent by sender
 Public-Key Cryptography
 probably most significant advance in the
3000 year history of cryptography
 uses two keys – a public & a private key
 asymmetric since parties are not equal
 uses clever application of number
theoretic concepts to function
 complements rather than replaces private
key crypto
 Why Public-Key
Cryptography?
 developed to address two key issues:

key distribution – how to have secure
communications in general without having to
trust a KDC with your key

digital signatures – how to verify a message
comes intact from the claimed sender
 publicinvention due to Whitfield Diffie &
Martin Hellman at Stanford Uni in 1976

known earlier in classified community
 Public-Key Cryptography
 public-key/two-key/asymmetric cryptography
involves the use of two keys:

a public-key, which may be known by anybody, and can
be used to encrypt messages, and verify signatures

a related private-key, known only to the recipient, used
to decrypt messages, and sign (create) signatures
 infeasible to determine private key from public
 is asymmetric because

those who encrypt messages or verify signatures cannot
decrypt messages or create signatures
Public-Key Cryptography
Symmetric vs Public-Key
Public-Key Cryptosystems
 Public-Key Applications
 can classify uses into 3 categories:

encryption/decryption (provide secrecy)

digital signatures (provide authentication)

key exchange (of session keys)
 some algorithms are suitable for all uses,
others are specific to one
 Public-Key Requirements
 Public-Key algorithms rely on two keys where:

it is computationally infeasible to find decryption key
knowing only algorithm & encryption key

it is computationally easy to en/decrypt messages
when the relevant (en/decrypt) key is known

either of the two related keys can be used for
encryption, with the other used for decryption (for
some algorithms)
 these are formidable requirements which
only a few algorithms have satisfied
 Public-Key Requirements
 need a trapdoor one-way function
 one-way function has

Y = f(X) easy

X = f–1(Y) infeasible
 a trap-door one-way function has
 Y = fk(X) easy, if k and X are known
 X = fk–1(Y) easy, if k and Y are known
 X = fk–1(Y) infeasible, if Y known but k not known
 a practical public-key scheme depends on
a suitable trap-door one-way function
Security of Public Key Schemes

 like private key schemes brute force exhaustive

search attack is always theoretically possible
 but keys used are too large (>512bits)
 security relies on a large enough difference in
difficulty between easy (en/decrypt) and hard
(cryptanalyse) problems
 more generally the hard problem is known, but
is made hard enough to be impractical to break
 requires the use of very large numbers
 hence is slow compared to private key schemes
 RSA
 by Rivest, Shamir & Adleman of MIT in 1977
 best known & widely used public-key scheme
 based on exponentiation in a finite (Galois) field
over integers modulo a prime

nb. exponentiation takes O((log n)3) operations (easy)
 uses large integers (eg. 1024 bits)
 security due to cost of factoring large numbers

nb. factorization takes O(e log n log log n) operations (hard)
 RSA En/decryption
 to encrypt a message M the sender:

obtains public key of recipient PU={e,n}

computes: C = Me mod n, where 0≤M<n
 to decrypt the ciphertext C the owner:

uses their private key PR={d,n}

computes: M = Cd mod n
 notethat the message M must be smaller
than the modulus n (block if needed)
 RSA Key Setup
 each user generates a public/private key pair by:
 selecting two large primes at random: p, q
 computing their system modulus n=p.q

note ø(n)=(p-1)(q-1)
 selecting at random the encryption key e

where 1<e<ø(n), gcd(e,ø(n))=1
 solve following equation to find decryption key d

e.d=1 mod ø(n) and 0≤d≤n
 publish their public encryption key: PU={e,n}
 keep secret private decryption key: PR={d,n}
 Why RSA Works
 because of Euler's Theorem:

aø(n)mod n = 1 where gcd(a,n)=1

 in RSA have:

n=p.q

ø(n)=(p-1)(q-1)

carefully chose e & d to be inverses mod ø(n)

hence e.d=1+k.ø(n) for some k

 hence :
Cd = Me.d = M1+k.ø(n) = M1.(Mø(n))k
= M1.(1)k = M1 = M mod n
 RSA Example - Key Setup
1. Select primes: p=17 & q=11
2. Calculate n = pq =17 x 11=187
3. Calculate ø(n)=(p–1)(q-1)=16x10=160
4. Select e: gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160
Value is d=23 since 23x7=161= 10x160+1
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}
RSA Example - En/Decryption
 sample RSA encryption/decryption is:
 given message M = 88 (nb. 88<187)
 encryption:
C = 887 mod 187 = 11
 decryption:
M = 1123 mod 187 = 88
 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
 Exponentiation
c = 0; f = 1
for i = k downto 0
do c = 2 x c
f = (f x f) mod n
if bi == 1 then
c = c + 1
f = (f x a) mod n
return f
 Efficient Encryption
 encryption uses exponentiation to power e
 hence if e small, this will be faster

often choose e=65537 (216-1)

also see choices of e=3 or e=17
 but if e too small (eg e=3) can attack

using Chinese remainder theorem & 3
messages with different modulii
 if e fixed must ensure gcd(e,ø(n))=1

ie reject any p or q not relatively prime to e
 Efficient Decryption
 decryption uses exponentiation to power d

this is likely large, insecure if not
 canuse the Chinese Remainder Theorem
(CRT) to compute mod p & q separately.
then combine to get desired answer

approx 4 times faster than doing directly
 onlyowner of private key who knows
values of p & q can use this technique
 RSA Key Generation
 users of RSA must:

determine two primes at random - p, q

select either e or d and compute the other
 primesp,q must not be easily derived
from modulus n=p.q

means must be sufficiently large

typically guess and use probabilistic test
 exponents e, d are inverses, so use
Inverse algorithm to compute the other
 RSA Security
 possible approaches to attacking RSA are:

brute force key search - infeasible given size
of numbers

mathematical attacks - based on difficulty of
computing ø(n), by factoring modulus n

timing attacks - on running of decryption

chosen ciphertext attacks - given properties of
RSA
 Factoring Problem
 mathematical approach takes 3 forms:

factor n=p.q, hence compute ø(n) and then d

determine ø(n) directly and compute d

find d directly

 currently believe all equivalent to factoring


have seen slow improvements over the years
• as of May-05 best is 200 decimal digits (663) bit with LS

biggest improvement comes from improved algorithm
• cf QS to GNFS to LS

currently assume 1024-2048 bit RSA is secure
• ensure p, q of similar size and matching other constraints
Progress in Factoring
Progress
in
Factoring
 Timing Attacks
 developed by Paul Kocher in mid-1990’s
 exploit timing variations in operations

eg. multiplying by small vs large number

or IF's varying which instructions executed
 infer operand size based on time taken
 RSA exploits time taken in exponentiation
 countermeasures

use constant exponentiation time

add random delays

blind values used in calculations
 Chosen Ciphertext Attacks
• RSA is vulnerable to a Chosen Ciphertext
Attack (CCA)
• attackers chooses ciphertexts & gets
decrypted plaintext back
• choose ciphertext to exploit properties of
RSA to provide info to help cryptanalysis
• can counter with random pad of plaintext
• or use Optimal Asymmetric Encryption
Padding (OASP)
 Optimal
Asymmetric
Encryption
Padding
(OASP)
 Summary
 have considered:

principles of public-key cryptography

RSA algorithm, implementation, security
Cryptography and
Network Security
Chapter 10
Fifth Edition
by William Stallings
 Chapter 10 – Other Public Key
Cryptosystems
Amongst the tribes of Central Australia every man, woman,
and child has a secret or sacred name which is bestowed
by the older men upon him or her soon after birth, and
which is known to none but the fully initiated members of
the group. This secret name is never mentioned except
upon the most solemn occasions; to utter it in the hearing of
men of another group would be a most serious breach of
tribal custom. When mentioned at all, the name is spoken
only in a whisper, and not until the most elaborate
precautions have been taken that it shall be heard by no
one but members of the group. The native thinks that a
stranger knowing his secret name would have special
power to work him ill by means of magic.
—The Golden Bough, Sir James George Frazer
Diffie-Hellman Key Exchange
 first public-key type scheme proposed
 by Diffie & Hellman in 1976 along with the
exposition of public key concepts

note: now know that Williamson (UK CESG)
secretly proposed the concept in 1970
 is a practical method for public exchange
of a secret key
 used in a number of commercial products
Diffie-Hellman Key Exchange
 a public-key distribution scheme

cannot be used to exchange an arbitrary message

rather it can establish a common key

known only to the two participants
 value of key depends on the participants (and
their private and public key information)
 based on exponentiation in a finite (Galois) field
(modulo a prime or a polynomial) - easy
 security relies on the difficulty of computing
discrete logarithms (similar to factoring) – hard
 Diffie-Hellman Setup
 all users agree on global parameters:

large prime integer or polynomial q

a being a primitive root mod q
 each user (eg. A) generates their key
 chooses a secret key (number): xA < q
xA

compute their public key: yA = a mod q
 each user makes public that key yA
Diffie-Hellman Key Exchange
 shared session key for users A & B is KAB:
xA.xB
KAB = a mod q
xB
= y A mod q (which B can compute)
xA
= y B mod q (which A can compute)
 KAB is used as session key in private-key
encryption scheme between Alice and Bob
 if Alice and Bob subsequently communicate, they
will have the same key as before, unless they
choose new public-keys
 attacker needs an x, must solve discrete log
 Diffie-Hellman Example
 users Alice & Bob who wish to swap keys:
 agree on prime q=353 and a=3
 select random secret keys:

A chooses xA=97, B chooses xB=233
 compute respective public keys:
97

yA=3 mod 353 = 40 (Alice)
233

yB=3 mod 353 = 248 (Bob)
 compute shared session key as:
xA 97

KAB= yB mod 353 = 248 = 160 (Alice)
xB 233

KAB= yA mod 353 = 40 = 160 (Bob)
 Key Exchange Protocols
 users could create random private/public
D-H keys each time they communicate
 users could create a known private/public
D-H key and publish in a directory, then
consulted and used to securely
communicate with them
 both of these are vulnerable to a man-in-
the-Middle Attack
 authentication of the keys is needed
 Man-in-the-Middle Attack
1. Darth prepares by creating two private / public keys
2. Alice transmits her public key to Bob
3. Darth intercepts this and transmits his first public key to Bob.
Darth also calculates a shared key with Alice
4. Bob receives the public key and calculates the shared key
(with Darth instead of Alice)
5. Bob transmits his public key to Alice
6. Darth intercepts this and transmits his second public key to
Alice. Darth calculates a shared key with Bob
7. Alice receives the key and calculates the shared key (with
Darth instead of Bob)
 Darth can then intercept, decrypt, re-encrypt, forward all
messages between Alice & Bob
 ElGamal Cryptography
 public-key cryptosystem related to D-H
 so uses exponentiation in a finite (Galois)
 with security based difficulty of computing
discrete logarithms, as in D-H
 each user (eg. A) generates their key
 chooses a secret key (number): 1 < xA < q-1
xA

compute their public key: yA = a mod q
 ElGamal Message Exchange
 Bob encrypt a message to send to A computing

represent message M in range 0 <= M <= q-1
• longer messages must be sent as blocks

chose random integer k with 1 <= k <= q-1
compute one-time key K = yA mod q
 k


encrypt M as a pair of integers (C1,C2) where
• C1 = ak mod q ; C2 = KM mod q
 A then recovers message by

recovering key K as K = C1xA mod q

computing M as M = C2 K-1 mod q
 a unique k must be used each time

otherwise result is insecure
 ElGamal Example
 use field GF(19) q=19 and a=10
 Alice computes her key:
5

A chooses xA=5 & computes yA=10 mod 19 = 3
 Bob send message m=17 as (11,5) by

chosing random k=6

computing K = yAk mod q = 36 mod 19 = 7

computing C1 = ak mod q = 106 mod 19 = 11;
C2 = KM mod q = 7.17 mod 19 = 5
 Alice recovers original message by computing:
5

recover K = C1
xA
mod q = 11 mod 19 = 7

compute inverse K-1 = 7-1 = 11

recover M = C2 K-1 mod q = 5.11 mod 19 = 17
 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
 newer, but not as well analysed
 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
 consider set of points E(a,b) that satisfy
 have addition operation for elliptic curve

geometrically sum of P+Q is reflection of the
intersection R
Real Elliptic Curve Example
 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
• best in software
• y2 = (x3 + ax + b) mod p
 binary curves E2m(a,b) defined over GF(2n)
• use polynomials with binary coefficients
• best in hardware
 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
 Example: E (1,1)
23
Point of E23(1,1)
 ECC Diffie-Hellman
 can do key exchange analogous to D-H
 users select a suitable curve Eq(a,b)
 select base point G=(x1,y1)

with large order n s.t. nG=O
 A & B select private keys
nA<n, nB<n
 compute public keys: P =n G, P =n G
A A B B
 compute shared key: K=n P , K=n P
A B B A

same since K=nAnBG
 attacker would need to find k, hard
 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, nB<n
 and computes public key PA=nAG, PB=nBG
 When A send data to B
 to encrypt Pm : Cm={kG, Pm+kPB}, k random
 decrypt Cm compute:
Pm+kPb–nB(kG) = Pm+k(nBG)–nB(kG) = Pm
 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
 Comparable Key Sizes for
Equivalent Security
Symmetric ECC-based RSA/DSA
scheme scheme (modulus size in
(key size in bits) (size of n in bits) bits)
56 112 512
80 160 1024
112 224 2048
128 256 3072
192 384 7680
256 512 15360
 Summary
 have considered:

Diffie-Hellman key exchange

ElGamal cryptography

Elliptic Curve cryptography
Cryptography and
Network Security
Chapter 11
Fifth Edition
by William Stallings
 Chapter 11 – Cryptographic
Hash Functions
Each of the messages, like each one he had ever
read of Stern's commands, began with a number
and ended with a number or row of numbers. No
efforts on the part of Mungo or any of his experts
had been able to break Stern's code, nor was
there any clue as to what the preliminary number
and those ultimate numbers signified.
—Talking to Strange Men, Ruth Rendell
 Hash Functions
 condenses arbitrary message to fixed size
h = H(M)
 usually assume hash function is public
 hash used to detect changes to message
 want a cryptographic hash function

computationally infeasible to find data mapping
to specific hash (one-way property)

computationally infeasible to find two data to
same hash (collision-free property)
Cryptographic Hash Function
 Hash Function Uses
 Message Integrity Check (MIC)

send hash of message (digest)

MIC always encrypted, message optionally
 Message Authentication Code (MAC)

send keyed hash of message

MAC, message optionally encrypted
 Digital Signature (non-repudiation)

Encrypt hash with private (signing) key

Verify with public (verification) key
 Hash Functions & Message
Authentication
ymmetric Key
nkeyed Hash

) Message
encrypted

) Message
unencrypted
 Hash Functions & Message
Authentication
ymmetric Key
Keyed Hash

Message
unencrypted

) Message
encrypted
Hash Functions & Digital
Signatures
 Other Hash Function Uses
 pseudorandom function (PRF)

Generate session keys, nonces

Produce key from password

Derive keys from master key cooperatively
 pseudorandom number generator
(PRNG)

Vernam Cipher/OTP

S/Key, proof of “what you have” via messages
 More Hash Function Uses
 to create a one-way password file

store hash of password not actual password

e.g., Unix, Windows NT, etc.

salt to deter precomputation attacks

Rainbow tables
 for intrusion detection and virus detection

keep & check hash of files on system

e.g., Tripwire
Lamport One-time Passwords
 Password safety in distributed system

server compromise does not compromise P

interception of authentication exchange does
not compromise password either
 Alice picks Password PA
A
 Hashes password N times, HN(PA)
 Server stores (Alice, N, HN(PA))
 Attacker can’t get PA from HN(PA)
Lamport One-time Passwords
 Protocol

Alice sends “I’m Alice”

Server sends “N-1”
 Alice sends “X” where X=HN-1(PA)
 Server verifies H(X) = HN(PA)

Server updates to (Alice, N-1, X)
 Attacker still can’t get PA or authenticate as
Alice
 Two Simple Insecure Hash
Functions
 consider two simple insecure hash functions
 bit-by-bit exclusive-OR (XOR) of every block
 Ci = bi1 xor bi2 xor . . . xor bim

a longitudinal redundancy check

reasonably effective as data integrity check
 one-bit circular shift on hash value

for each successive n-bit block
• rotate current hash value to left by1bit and XOR block

good for data integrity but useless for security
 What If We Hash and Encrypt
 Hash h = XN+1 = X1 xor X2 xor ... xor XN
 Encrypt the message along with hash
 Y1, Y2, … , YN+1 where
 Y1 = IV xor E(K, X1)]
 Y2 = Y1 xor E(K, X2)] ….
 YN+1 = YN xor E(K, XN+1)] = Encrypted h
 XN+1 = X1 xor X2 xor ... xor XN

= [ IV xor D(K, Y1)] xor [Y1 xor D(K, Y2)]
xor … xor [YN-1 xor D(K, YN)]
Hash Function Requirements
 Hash Function Resistance
Properties Required

Preimage Second Collision

Resistance Preimage Resistance
Resistance
Hash+ digital signature yes yes Yes*

Intrusion and Virus yes

detection
One way password file yes

MAC yes yes Yes*

 Attacks on Hash Functions
 have brute-force attacks and cryptanalysis
 a preimage or second preimage attack

find y s.t. H(y) equals a given hash value
 collision resistance

find two messages x & y with same hash so
H(x) = H(y)
 hence value 2m/2 determines strength of
hash code against brute-force attacks

128-bits inadequate, 160-bits suspect
 Birthday Attacks
 might think a 64-bit hash is secure
 but by Birthday Paradox is not
 birthday attack works thus:

given user prepared to sign a valid message x
m

opponent generates 2 /2 variations x’ of x, all with
essentially the same meaning, and saves them
m/

opponent generates 2 2 variations y’ of a desired
fraudulent message y

two sets of messages are compared to find pair with
same hash (probability > 0.5 by birthday paradox)

have user sign the valid message, then substitute the
forgery which will have a valid signature
 conclusion is that need to use larger MAC/hash
 Birthday Attacks
Find i and j
such that y y’1 y’2 … y’j … y’N
H(y’j)=H(x’i)
x ≠ ≠ ≠ ≠ ≠
x’1 ≠ ≠ ≠ ≠ ≠
x’2 ≠ ≠ ≠ ≠ ≠
…
x’i ≠ ≠ ≠ = ≠
…
x’N ≠ ≠ ≠ ≠ ≠
 Birthday Attacks
 What are chances we get a match?
 N distinct values, k randomly chosen ones
 P(N,k) = prob(k randomly selected values
from 1..N have at least one match)
 For P(N,k)>0.5, need k ≈ N1/2
 Need double # bits in hash value
 Hash Function Cryptanalysis
 cryptanalytic attacks exploit some property
of alg so faster than exhaustive search
 hash functions use iterative structure

process message in blocks (incl length)
 attacks focus on collisions in function f
 Block Ciphers as Hash
Functions
 can use block ciphers as hash functions
 using H0=0 and zero-pad of final block
 compute: Hi = EMi [Hi-1]

and use final block as the hash value

similar to CBC but without a key
 resulting hash is too small (64-bit)

both due to direct birthday attack

and to “meet-in-the-middle” attack
 other variants also susceptible to attack
 Block Ciphers as Hash
Functions H
0

Block cipher key length B

Pad Message M to multiple of B M1 E
Break padded M into L blocks
L = |M|/B M2 E
M = M1 M2 … ML
Use blocks of M as keys in block
cipher, iteratively encrypt state value
starting with constant H0 resulting in ML E
hash value
HL
H = HL = E(ML,….E(M2,E(M1,H0))…)
 Secure Hash Algorithm
 SHA originally designed by NIST & NSA in 1993
 was revised in 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
 based on design of MD4 with key differences
 produces 160-bit hash values
 recent 2005 results on security of SHA-1 have
raised concerns on its use in future applications
 Revised Secure Hash
Standard
 NIST issued revision FIPS 180-2 in 2002
 adds 3 additional versions of SHA

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
 but security levels are rather higher
SHA Versions
SHA-512 Overview
 SHA-512 Compression
Function
 heart of the algorithm
 processing message in 1024-bit blocks
 consists of 80 rounds

updating a 512-bit buffer

using a 64-bit value Wt derived from the
current message block

and a round constant based on cube root of
first 80 prime numbers
SHA-512 Round Function
 Ch(e,f,g) = (e AND f) XOR (NOT e AND g)
 Maj(a,b,c) = (a AND b) XOR (a AND c) XOR (b AND c)
 ∑(a) = ROTR(a,28) XOR ROTR(a,34) XOR ROTR(a,39)
 ∑(e) = ROTR(e,14) XOR ROTR(e,18) XOR ROTR(e,41)
 + = addition modulo 2^64
 Kt = a 64-bit additive constant
 Wt = a 64-bit word derived from the current 1024-bit
input block.
SHA-512 Round Function
 ∂0(x) = ROTR(x,1) XOR ROTR(x,8) XOR
SHR(x,7)

 ∂1(x) = ROTR(x,19) XOR ROTR(x,61)

XOR SHR(x,6)
 SHA-3
 SHA-1 not yet "broken”

but similar to broken MD5 & SHA-0

so considered insecure
 SHA-2 (esp. SHA-512) seems secure

shares same structure and mathematical
operations as predecessors so have concern
 NIST announced in 2007 a competition for
the SHA-3 next gen NIST hash function

goal to have in place by 2012 but not fixed
 SHA-3 Requirements
 replace SHA-2 with SHA-3 in any use

so use same hash sizes
 preserve the online nature of SHA-2

so must process small blocks (512 / 1024 bits)
 evaluation criteria

security close to theoretical max for hash sizes

cost in time & memory

characteristics: such as flexibility & simplicity
 Summary
 have considered:

hash functions
• uses, requirements, security

hash functions based on block ciphers

SHA-1, SHA-2, SHA-3
Cryptography and
Network Security
Chapter 12
Fifth Edition
by William Stallings
 Chapter 12 – Message
Authentication Codes
 At cats' green on the Sunday he took the message from
the inside of the pillar and added Peter Moran's name to
the two names already printed there in the "Brontosaur"
code. The message now read: “Leviathan to Dragon:
Martin Hillman, Trevor Allan, Peter Moran: observe and
tail.” What was the good of it John hardly knew. He felt
better, he felt that at last he had made an attack on Peter
Moran instead of waiting passively and effecting no
retaliation. Besides, what was the use of being in
possession of the key to the codes if he never took
advantage of it?
 —Talking to Strange Men, Ruth Rendell
 Message Authentication
 Message authentication is concerned with:

Protecting the integrity of a message

Validating identity of originator

Non-repudiation of origin (dispute
resolution)

 Will consider the security requirements

Message Security Requirements
 Disclosure
 Traffic analysis
 Masquerade
 Content modification
 Sequence modification
 Timing modification
 Source repudiation
 Destination repudiation
Symmetric Message Encryption
 Encryption can also provides authentication
 If symmetric encryption is used then:

Receiver know sender must have created it

Since only sender and receiver now key used

Know content cannot have been altered

If message has suitable structure, redundancy
or a checksum to detect any changes
Public-Key Message Encryption
 If public-key encryption is used:

Encryption provides no confidence of sender
• since anyone potentially knows public-key

However if
• sender signs message using their private-key
• then encrypts with recipients public key
• have both secrecy and authentication

Again need to recognize corrupted messages

But at cost of two public-key uses on
message
Internal & External Error
Control
 With internal error control, authentication is
provided because an opponent would have
difficulty generating ciphertext that, when
decrypted, would have valid error control
bits.

 With external error control, an opponent

can construct messages with valid error-
control codes. Although the opponent
cannot know what the decrypted plaintext
will be, he or she can still hope to create
confusion and disrupt operations.
 Message Authentication Code
(MAC)
 Generated by an algorithm that creates a small
fixed-sized block

Depending on both message and some key

Like encryption though need not be reversible
 Appended to message as a cryptographic
checksum.
 Receiver performs same computation on
message and checks it matches the MAC
 Provides assurance that message is unaltered
and comes from sender
Message Authentication Code
 A small fixed-sized block of data
 Generated from message + secret key
 MAC = C(K,M)
 Appended to message when sent
Basic Use of MAC
 When MAC Matched
 The receiver is assured that the message has not
been altered. If an attacker alters the message but
does not alter the MAC, then the receiver’s calculation
of the MAC will differ from the received MAC.
 The receiver is assured that the message is from the
alleged sender. Because no one else knows the
secret key to generate MAC.
 If the message includes a sequence number then the
receiver can be assured of the proper sequence
because an attacker cannot successfully alter the
sequence number.
 Message Authentication
Codes
 Can also use encryption for secrecy

generally use separate keys for each

can compute MAC either before or after encryption

is generally regarded as better done before

 Why use a MAC?


sometimes only authentication is needed

sometimes need authentication to persist longer than
the encryption (eg. archival use)

 Note that a MAC is not a digital signature

 MAC Properties
 A MAC is a cryptographic checksum
MAC = CK(M)

Condenses a variable-length message M

Using a secret key K

To a fixed-sized authenticator
 MAC Properties
 Is a many-to-one function

Potentially many messages have same MAC

But finding these needs to be very difficult


If an m-bit MAC is used, then there are 2m
possible MACs.

N possible messages with N >> 2m

With a k-bit key, there are 2k possible keys.
 Security of MACs
 Like block ciphers have:
 Brute-force attacks exploiting
m/

Strong collision resistance hash have cost 2 2

• 128-bit hash looks vulnerable, 160-bits better


MACs with known message-MAC pairs
• can either attack keyspace (cf key search) or MAC
• Brute force attack effort ~ min(2k,2n)
• at least 128-bit MAC is needed for security
 Requirements for MACs
 If k > m; key size is greater than MAC
size.
 Given message M1 and T1 where T1
=MAC(k,M1), we can compute
Ti=MAC(ki, M1) for all values of ki.
 At least one key ki will produce Ti = T1.
 But 2k > 2m; So 2k/2m = 2k-m key values will
produce T1 and create confusion in the
mind of attacker.
 Round 1
 Given:M1, T1 = MAC(K,M1)
 Compute Ti = MAC(Ki,M1) for all 2k keys

Number of matches ≈ 2(k-n)
 Round 2
 Given:M2, T2 = MAC(K,M2)
 Compute Ti = MAC(Ki,M2) for the 2(k-n) keys
resulting from Round 1

Number of matches ≈ 2(k-2xn)

 On average, α rounds will be needed if k= α x n.

 Security of MACs
 Cryptanalytic attacks exploit structure

like block ciphers want brute-force attacks to
be the best alternative
 More variety of MACs so harder to
generalize about cryptanalysis
 Requirements for MACs
 Taking into account the types of attacks
 Need the MAC to satisfy the following:
1. Knowing a message and MAC, is infeasible to
find another message with same MAC
2. MACs should be uniformly distributed. Probability
that two different messages have the same hash
must be 2-n where n is number of bits in the hash.
3. MAC should depend equally on all bits of the
message
Keyed Hash Functions as MACs
 Want a MAC based on a hash function

because hash functions are generally faster

crypto hash function code is widely available
 Hash includes a key along with message
 Original proposal:
KeyedHash = Hash(Key|Message)

some weaknesses were found with this
 Eventually led to development of HMAC
 Problem with Keyed Hash
 KeyedHash = Hash(Key|Message)
 Recall hash function works on blocks
 Let M = Key | Message | Padding and M

M=M1 M2 … ML, where |Mi| = Blocksize

Hash=H(H(…H(H(IV,M1),M2),…,ML)
 But can add extra block(s) M
L+1 by

Hash’=H(Hash,ML+1)
 Unless formatting prevents it…
… but still best to use HMAC!
 HMAC Design Objectives
 Use, without modifications, hash functions
 Allow for easy replaceability of embedded
hash function
 Preserve original performance of hash
function without significant degradation
 Use and handle keys in a simple way.
 Have well understood cryptographic analysis
of authentication mechanism strength
 HMAC
 Specified as Internet standard RFC2104
 Uses hash function on the message:
HMACK(M)= Hash[(K+ XOR opad) ||
Hash[(K+ XOR ipad) || M)] ]

where K+ is the key padded out to block size

opad, ipad are specified padding constants
 Overhead is just 3 more hash block calculations
than the message needs alone
 Any hash function can be used

eg. MD5, SHA-1, RIPEMD-160, Whirlpool
 HMAC
Overview
 HMAC Security
 Proved 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
 Summary
 Have considered:

Message authentication requirements

Message authentication using encryption

MACs

HMAC authentication using a hash function
Cryptography and
Network Security
Chapter 13
Fifth Edition
by William Stallings
 Chapter 13 – Digital Signatures

To guard against the baneful influence exerted by strangers

is therefore an elementary dictate of savage prudence.
Hence before strangers are allowed to enter a district, or
at least before they are permitted to mingle freely with
the inhabitants, certain ceremonies are often performed
by the natives of the country for the purpose of disarming
the strangers of their magical powers, or of disinfecting,
so to speak, the tainted atmosphere by which they are
supposed to be surrounded.
—The Golden Bough, Sir James George Frazer
 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
Digital Signature Model
 Digital
Signature
Model
 Attacks and Forgeries
 attacks

key-only attack

known message attack

generic chosen message attack

directed chosen message attack

adaptive chosen message attack
 break success levels

total break

Universal forgery

selective forgery

existential forgery
Digital Signature Requirements
 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
 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
 ElGamal Digital Signatures
 signature variant of ElGamal, related to D-H

so uses exponentiation in a finite (Galois)

with security based difficulty of computing
discrete logarithms, as in D-H
 use private key for encryption (signing)
 uses public key for decryption (verification)
 each user (eg. A) generates their key
 chooses a secret key (number): 1 < xA < q-1
xA

compute their public key: yA = a mod q
 ElGamal Digital Signature
 Alice signs a message M to Bob by computing

the hash m = H(M), 0 <= m <= (q-1)

chose random integer K with 1 <= K <= (q-1) and
gcd(K,q-1)=1
k

compute temporary key: S1 = a mod q

compute K-1 the inverse of K mod (q-1)

compute the value: S2 = K-1(m-xAS1) mod (q-1)

signature is:(S1,S2)
 any user B can verify the signature by computing
m

V1 = a mod q

V2 = yAS1 S1S2 mod q

signature is valid if V1 = V2
 ElGamal Signature Example
 use field GF(19) q=19 and a=10
 Alice computes her key:
16

A chooses xA=16 & computes yA=10 mod 19 = 4
 Alice signs message with hash m=14 as (3,4):

choosing random K=5 which has gcd(18,5)=1
5

computing S1 = 10 mod 19 = 3

finding K-1 mod (q-1) = 5-1 mod 18 = 11

computing S2 = 11(14-16.3) mod 18 = 4
 any user B can verify the signature by computing
14

V1 = 10 mod 19 = 16

V2 = 43.34 = 5184 = 16 mod 19

since 16 = 16 signature is valid
Digital Signature Standard (DSS)
 US Govt approved signature scheme
 designed by NIST & NSA in early 90's
 published as FIPS-186 in 1991
 revised in 1993, 1996 & then 2000
 uses the SHA hash algorithm
 DSS is the standard, DSA is the algorithm
 FIPS 186-2 (2000) includes alternative RSA &
elliptic curve signature variants
 DSA is digital signature only unlike RSA is a
public-key technique
DSS vs RSA Signatures
 Digital Signature Algorithm
(DSA)
 creates a 320 bit signature
 with 512-1024 bit security
 smaller and faster than RSA
 a digital signature scheme only
 security depends on difficulty of computing
discrete logarithms
 variant of ElGamal & Schnorr schemes
 DSA Key Generation
 have shared global public key values (p,q,g):

choose 160-bit prime number q

choose a large prime p with 2L-1 < p < 2L
• where L= 512 to 1024 bits and is a multiple of 64
• such that q is a 160 bit prime divisor of (p-1)

choose g = h(p-1)/q
• where 1<h<p-1 and h(p-1)/q mod p > 1
 users choose private & compute public key:

choose random private key: x<q

compute public key: y = gx mod p
 DSA Signature Creation
 to sign a message M the sender:

generates a random signature key k, k<q

nb. k must be random, be destroyed after
use, and never be reused
 then computes signature pair:
r = (gk mod p)mod q
s = [k-1(H(M)+ xr)] mod q
 sends signature (r,s) with message M
 DSA Signature Verification
 having received M & signature (r,s)
 to verify a signature, recipient computes:
w = s-1 mod q
u1= [H(M)w ]mod q
u2= (rw)mod q
v = [(gu1 yu2)mod p ]mod q
 if v=r then signature is verified
DSS Overview
 Summary
 have discussed:

digital signatures

ElGamal signature scheme

digital signature algorithm and standard
Cryptography and
Network Security
Chapter 14
Fifth Edition
by William Stallings
 Chapter 14 – Key Management
and Distribution
No Singhalese, whether man or woman,
would venture out of the house without a
bunch of keys in his hand, for without such
a talisman he would fear that some devil
might take advantage of his weak state to
slip into his body.
—The Golden Bough, Sir James George
Frazer
 Key Management and
Distribution
 Topics of cryptographic key management /
key distribution are complex

cryptographic, protocol, & management issues
 Symmetric schemes require both parties to
share a common secret key
 Public key schemes require parties to
acquire valid public keys
 Have concerns with doing both
 Key Distribution
 Symmetric schemes require both parties
to share a common secret key
 Issue is how to securely distribute this key
 Whilst protecting it from others
 Frequent key changes can be desirable
 Often secure system failure due to a break
in the key distribution scheme
 Key Distribution
 Given parties A and B have various key
distribution alternatives:
1. A can select key and physically deliver to B
2. Third party can select & deliver key to A & B
3. If A & B have communicated previously can
use previous key to encrypt a new key
4. If A & B have secure communications with a
third party C, C can relay key between A & B
Key Distribution Task
 Key Hierarchy
 Typically have a hierarchy of keys
 Session key

temporary key

used for encryption of data between users

for one logical session then discarded
 Master key

used to encrypt session keys

shared by user & key distribution center
Key Hierarchy
Key Distribution Scenario
 Key Distribution Issues
 Hierarchies of KDC’s required for large
networks, but must trust each other
 Session key lifetimes should be limited for
greater security
 Use of automatic key distribution on behalf
of users, but must trust system
 Use of decentralized key distribution
 Controlling key usage
 Symmetric Key Distribution
Using Public Keys
 Public key cryptosystems are inefficient

So almost never use for direct data encryption

Rather use to encrypt secret keys for
distribution
Simple Secret Key Distribution
 Merkle proposed this very simple scheme

Allows secure communications

No keys before/after exist
 Man-in-the-Middle Attack
 This very simple scheme is vulnerable to
an active man-in-the-middle attack
Secret Key Distribution with
Confidentiality and
Authentication
 Hybrid Key Distribution
 Retain use of private-key KDC
 Shares secret master key with each user
 Distributes session key using master key
 Public-key used to distribute master keys

especially useful with widely distributed users
 Rationale

performance

backward compatibility
 Distribution of Public Keys
 Can be considered as using one of:

Public announcement

Publicly available directory

Public-key authority

Public-key certificates
 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
 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
 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

May be vulnerable to tampering
Public-Key Authority
 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
Public-Key Certificates
X.509 Authentication Service
 Part of CCITT X.500 directory service standards

distributed servers maintaining user 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
 X.509 certificates are widely used

have 3 versions
 X.509
Certificate
Use
 X.509 Certificates
 Issued by a Certification Authority (CA), containing:

version V (1, 2, or 3)

serial number SN (unique within CA) identifying certificate

signature algorithm identifier AI

issuer X.500 name CA)

period of validity TA (from - to dates)

subject X.500 name A (name of owner)

subject public-key info Ap (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
X.509 Certificates
 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
 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
CA Hierarchy Use
 Certificate Revocation
 Certificates have a period of validity
 May need to revoke before expiry, eg:
1. user's private key is compromised
2. user is no longer certified by this CA
3. CA's certificate is compromised
 CA’s maintain list of revoked certificates

the Certificate Revocation List (CRL)
 Users should check certificates with CA’s CRL
 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
 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
Public Key Infrastructure
 PKIX Management
 Functions:

Registration

Initialization

Certification

Key pair recovery

Key pair update

Revocation request

Cross certification
 Protocols: CMP, CMC
 Summary
 Have considered:

Symmetric key distribution using symmetric
encryption

Symmetric key distribution using public-key
encryption

Distribution of public keys
• announcement, directory, authrority, CA

X.509 authentication and certificates

Public key infrastructure (PKIX)
Cryptography and
Network Security
Chapter 15
Fifth Edition
by William Stallings
Chapter 15 – User Authentication
We cannot enter into alliance with
neighboring princes until we are
acquainted with their designs.
—The Art of War, Sun Tzu
 User Authentication
 Fundamental security building block
basis of access control & user accountability
 Is the process of verifying an identity
claimed by or for a system entity
 Has two steps:
identification - specify identifier
verification - bind entity (person) and identifier
 Distinct from message authentication
Means of User Authentication
 Four means of authenticating user's
identity
 Based one something the individual
knows - e.g. password, PIN
possesses - e.g. key, token, smartcard
is (static biometrics) - e.g. fingerprint, retina
does (dynamic biometrics) - e.g. voice, sign
 Can use alone or combined (multi factor)
 All can provide user authentication
 All have issues
 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
 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)
 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
 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
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: E(Ka,[Ks||IDB||N1|| E(Kb,[Ks||IDA])])
3. A -> B: E(Kb, [Ks||IDA])
4. B -> A: E(Ks, [N2])
5. A -> B: E(Ks, [f(N2)])
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 in steps 2 & 3 (Denning 81)
using an extra nonce (Neuman 93)
 Denning Modification to N-S
 Needs clocks to be syncrhronised.
 Suppress-Replay attack (senders clock
ahead)
 |Clock – T| < Δt1 + Δt2

1. A->KDC: IDA || IDB

2. KDC -> A: E(Ka,[Ks||IDB||T || E(Kb,[Ks||IDA||T])])
3. A -> B: E(Kb, [Ks||IDA||T ])
4. B -> A: E(Ks, [N1])
Neuman Modification to N-S

1. A->B: IDA || Na
2. B -> KDC: IDB||Nb|| E(Kb,[IDA||Na|| Tb])
3. KDC -> A: E(Ka, [IDB||Na||Ks||Tb]) ||
E(Kb, [IDA||Ks||Tb])||Nb
4. A -> B: E(Kb, [IDA||Ks||Tb]) || E(Ks, Nb)
 One-Way Authentication
 Use refinement of KDC to secure email
since B no online, drop steps 4 & 5
 Protocol becomes:
1. A->KDC: IDA || IDB || N1
2. KDC -> A: E(Ka, [Ks||IDB||N1 || E(Kb,[Ks||IDA])])
3. A -> B: E(Kb, [Ks||IDA]) || E(Ks, M)
 Provides encryption & some authentication
 Does not protect from replay attack
 Kerberos
 Trusted key server system from MIT
 Provides centralised private-key third-party
authentication in a distributed network
allows users access to services distributed
through network
without needing to trust all workstations
rather all trust a central authentication server
 Two versions in use: 4 & 5
 Threats
 A user may gain access to a particular
workstation and pretend to be another user
operating from that workstation.
 A user may alter the network address of a
workstation so that the requests sent from
the altered workstation appear to come
from the impersonated workstation.
 A user may eavesdrop on exchanges and
use a replay attack to gain entrance to a
server or to disrupt operations.
 Kerberos Requirements
 Its first report identified requirements as:
Secure - eavesdropping/impersanation.
Reliable – availability/distributed architecture.
Transparent – one time password.
Scalable – large number of servers and
clients.
 Implemented using an authentication
protocol based on Needham-Schroeder
 Sample Dialogue 1
1. C -> AS : IDC || PC || IDV
2. AS -> C : Ticket
3. C -> V : IDC || Ticket
Ticket = E(Kv, [IDC || ADC || IDV])

where
C = client
Issues:
AS = authentication server
Password sent in plaintext.
V = server
Password needs to be entered each
IDV = server identifier
time for new session or different
IDC = identifier of user on C
service.
PC = client password
ADC = network address of C
KV = secret encryption key shared between AS and V
 Sample Dialogue 2
Once per user logon session:

C -> AS : IDC || IDtgs

AS -> C : E(KC, Tickettgs)

Once per type of service:

3. C -> TGS : IDC || IDV || Tickettgs

4. TGS -> C : Ticketv Issues:
What if ticket lifetime is too short or
Once per service session: too long?
Only client authentication, server is
5. C -> V : IDC || Ticketv
not authenticated.
Tickettgs = E(Ktgs, [IDC || ADC || IDtgs || TS1 || Lifetime1])
Ticketv = E(Kv, [IDC || ADC || IDv || TS2 || Lifetime2]
Kerberos v4 Dialogue
 Kerberos v4 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
 Using a complex protocol using DES
Kerberos 4 Overview
 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
Kerberos Realms
 Kerberos Version 5
 Developed in mid 1990’s
 Specified as Internet standard RFC 1510
 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
Kerberos v5 Dialogue
 Summary
 have considered:
remote user authentication issues
authentication using symmetric encryption
the Kerberos trusted key server system
Cryptography and
Network Security
Chapter 16
Fifth Edition
by William Stallings
 Chapter 16 –
Transport-Level Security
Use your mentality
Wake up to reality
—From the song, "I've Got You under My
Skin“ by Cole Porter
 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
Threats on the Web
Web Traffic Security
Approaches
 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
 SSL Connection Properties
 Confidentiality

Transmitted data is encrypted. A handshake
procedure is used to agree upon the
parameters of symmetric encryption to be
use, including the encryption key.
 Authetication

Identity of the communicating parties can be
established using public key cryptography.
 Integrity

Uses MAC to detect loss or alteration of data.
SSL Architecture
 SSL Architecture
 SSL connection

A transient, peer-to-peer, communications link

Associated with 1 SSL session
 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
 Session State
 Session Identifier
 Peer certificate
 Compression Method
 Cipher Specs

Encryption Algorithm, Hash Algorithm
 Master Secret (48 byte shared secret
between client and server)
 Is resumable (can be used to initiate new
connection)?
 Connection State
 Server and Client random
 Server write MAC secret
 Client write MAC secret
 Server write key (server encryption key)
 Client write key (client encryption key)
 Initialization vectors
 Sequence numbers
 SSL Record Protocol
Services
 Confidentiality

Using symmetric encryption with a shared
secret key defined by Handshake Protocol

AES, IDEA, RC2-40, DES-40, DES, 3DES,
Fortezza

RC4-40, RC4-128

Message is compressed before encryption
 Message integrity

Using a MAC with shared secret key

Similar to HMAC but with different padding
SSL Record Protocol
Operation
 SSL Record Protocol Header
 Content type ( 8 bits)

The higher-layer protocol used to
process the enclosed fragment. (SSL
Handshake, SSL Change Cipher Spec,
SSL Alert, Application data)
 Major version number (8 bits)
 Minor version number (8 bits)
 Compressed length (16 bits)
 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 (10 different types of messages)
1. Establish Security Capabilities
2. Server Authentication and Key Exchange
3. Client Authentication and Key Exchange
4. Finish
TLS Handshake Message Type
 SSL
Handshake
Protocol
 client_hello Message
 Version:

The highest SSL version understood by the
client.
 Random:

A client-generated random structure
consisting of a 32-bit timestamp and 28 bytes
generated by a secure random number
generator.

These values serve as nonces and are used
during key exchange to prevent replay
 client_hello Message
 Session ID:

A variable-length session identifier. A nonzero
value indicates that the client wishes to
update the parameters of an existing
connection or to create a new connection on
this session.

A zero value indicates that the client wishes to
establish a new connection on a new session.
 client_hello Message
 Cipher Suit Parameters

A list that contains the combinations of
cryptographic algorithms supported by the
client, in decreasing order of preference.

Each element of the list (each cipher suite)
defines both a key exchange algorithm and a
CipherSpec.

TLS_RSA_WITH_NULL_MD5

TLS_RSA_WITH_RC4_128_SHA

TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA

TLS_RSA_WITH_NULL_MD5

TLS_NULL_WITH_NULL_NULL
 Key Exchange Methods
 RSA

Secret key is encrypted with RSA public key (in server certificate)
 Fixed Diffie-Hellman

DH public key parameters in certificate signed by CA.Fixed secret key
 Ephemeral Diffie-Hellman

Temporary, one time DH public key parameters exchanged using
senders private RSA, DSS key. Can be verified by using certified
public keys ( in CA issued certificate). Most secure.
 Anonymous Diffie-Hellman

DH public key exchange with no authentication

Not secure due to man in the middle attack
 Fortezza
 CipherSpec
 CipherAlgorithm

Any of the algorithms mentioned earlier: RC4,
RC2, DES, 3DES, DES40, IDEA, or Fortezza
 MACAlgorithm

MD5 or SHA-1
 CipherType

Stream or Block
 IsExportable

True or False
 CipherSpec
 HashSize

0, 16 (for MD5), or 20 (for SHA-1) bytes
 Key Material

A sequence of bytes that contain data used in
generating the write keys
 IV Size

The size of the Initialization Value for Cipher
Block Chaining (CBC) encryption
 Server certificate Message
 Required when using

Fixed DH - certificate contains servers public
DH parameters.

Ephemeral DH – certificate must have
signature capability.

RSA – certificate should have secret key
encryption capability.
 Contains a single or chain of X.509
certificates.
 server_key_exchange
Message
 Required when using

Anonymous DH (contains prime number,
primitive root, public DH key)

Ephemeral DH (same as above with
signature)

RSA key exchange (When server cannot
send encrypted secret key as it has signature
only RSA key). Creates a temporary RSA
public private key pair and send the public key
along with signature
 server_key_exchange
Message
 Not required for

RSA (client will later on send the secret key
encrypted using the server public key in the
certificate exchanged in earlier certificate
message)

Fixed DH – ( DH public parameters already
exchanged in earlier certificate message)
 Hash (required for signature) is computed
using

Hash(ClientHello.random||ServerHello.random||
Server params)
 certificate _request Message
 Required when using

Ephemeral DH

Fixed DH

RSA key exchange (signature only)
 Not required for

Anonymous DH
 Contains information about kind of
certificate requested and accepted CAs.
 client_key_exchange
Message
 Required for

RSA
• 48 byte pre-master secret sent encrypted using RSA public
key

Ephemeral and Anonymous DH
• Client public DH parameters

Fixed DH
• This message not required.
 Incase of DH pre-master secret is
computed using public parameters
exchanged
 Finished message
 Contains pseudo random value generated
over (PRF function used)

Master secret

Finished label

All handshake messages exchanged so far.
 Both MD5 and SHA-1 hashes are used

PRF( master secret, finished label,

MD5(handshake messages )||SHA1(handshake messages))
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

te
certifica Phase 2
e
k e y _ e xchang Server may send certificate, key exchange
server_ and request certificate.
est
rt if ic a te_requ
ce
ne
r v e r_ h ello_do
se
Time
certific
a te Phase 3
client_k Client sends certificate if requested. Client
e y_exch
a n ge sends key exchange.
certific
a te_verif
y

change
_ cipher_
specs Phase 4
finished Change cipher suit and finish handshake
protocol.

r_ specs
_ciphe
change
d
finishe
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

te
certifica
Phase 2
certificate_request message is optional.
Required only if client is to be authenticated
est
r t if ic a te_requ using a certificate.
ce
ne
rv e r_ h ello_do
se
Time
certific Phase 3
a te
client_k certificate message is optional. Required
e y_exch only if certificate_request message was sent
a n ge
earlier by server.
certific
a te_verif client_key_exchange message will contain
y
48 byte pre-master-secret encrypted using
public key of server (taken from server
certificate).
change
_ cipher_
specs Phase 4
finished Change cipher suit and finish handshake
protocol.

r_ specs Key Exchange Protocol – RSA

_ciphe
change
d
finishe
Server certificate containing RSA public key
meant for encryption/decryption of data/key.
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

te Phase 2
certifica Server certificate can only be used for
e
k e y _ e xchang signature verification.
server_ Server creates temporary RSA public-
est
rt if ic a te_requ private key pair for the purpose of
ce encryption/decryption and signs this
ne
r v e r_ h ello_do temporary public key using his private key
se and sends it to client inside
Time server_key_exchange message.

certific
a te Phase 3
client_k client_key_exchange message will contain
e y_exch
a n ge 48 byte pre-master-secret encrypted using
certific temporary RSA public key sent by server.
a te_verif
y Temporary RSA public key is verified by
using RSA key contained in Server certificate
message.
change
_ cipher_
specs Phase 4
finished Change cipher suit and finish handshake
protocol.

r_ specs Key Exchange Protocol – RSA*

_ciphe
change
d
finishe
* Server certificate containing RSA public key
meant for verifying signatures.
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

te
certifica Phase 2
Server certificate message contains
certificate containing servers DH public
parameters (a, p, Y).

hello_ done
server_
Time
certific
a te Phase 3
Client certificate message contains certificate
containing clients DH public parameters.

Shared DH public parameters are used to

compute pre-master-secret.

change
_ cipher_
specs Phase 4
finished Change cipher suit and finish handshake
protocol.

r_ specs Key Exchange Protocol – Fixed DH

_ciphe
change
d
finishe
Server and Clients have certificate containing
their DH public parameters (a, p,Y).
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

te
certifica Phase 2
e
k e y _ e xchang Server certificate can only be used for
server_ signature verification.
est Server creates temporary DH public-private
rt if ic a te_requ
ce key pair signs this temporary public key
ne
r v e r_ h ello_do using his private key and sends all public
se parameters (a, p, Y) to client inside
Time server_key_exchange message.

certific Phase 3
a te
Clients creates temporary DH public-private
client_k
e y_exch key pair and sends public key to server
a n ge
inside client_key_exchange message.
certific
a te_verif
y
Shared temparory DH public parameters are
used to compute pre-master-secret.
change
_ cipher_
specs Phase 4
finished Change cipher suit and finish handshake
protocol.

r_ specs Key Exchange Protocol –Ephemeral DH

_ciphe
change
d
finishe
Server certificate containing RSA/DSS public key
meant for verifying signatures.
 client_h
Client e llo Server
Phase 1
hello Protocol version, session ID, cipher
server_ suit,compression method, initial random
numbers.

Phase 2
e
ke y _ e xchang Server creates temporary DH public-private
server_ key pair and sends all public parameters (a,
p, Y) to client inside server_key_exchange
message. (not encrypted, not signed)
hello_ done
server_
Time
Phase 3
client_k Client creates temporary DH public-private
e y_exch key pair and sends public key to server
a n ge
inside client_key_exchange message. (not
encrypted, not signed).

Shared temparory DH public parameters are

change used to compute pre-master-secret.
_ cipher_
specs
finished Phase 4
Change cipher suit and finish handshake
protocol.
r_ specs
_ciphe Key Exchange Protocol – Anonymous DH
change
d
finishe
Not Secure. Susceptible to man-in-the-middle
attack.
Cryptographic Computations
 Master secret creation from pre-master
secret

A one-time 48-byte value generated using 48
byte secret value exchanged using secure
key exchange (RSA / Diffie-Hellman).
 Generation of cryptographic parameters

client write MAC secret, a server write MAC
secret, a client write key, a server write key, a
client write IV, and a server write IV

Generated by hashing master secret
 Master secret =
PRF( pre-master secret, “master secret”,
ClientHello.random||ServerHello.random )
 Key Block =
PRF( master secret, “key expansion”,
ClientHello.random||ServerHello.random )
 PRF is used on master secret till enough
bits are generated to cover, MAC secrets,
encryption keys and IVs
 Pseudo Random Function
PRF
 SSL
MD5(master_secret || SHA('A' || master_secret ||
ServerHello.random || ClientHello.random)) ||
MD5(master_secret || SHA('BB' || master_secret ||
ServerHello.random || ClientHello.random)) ||
MD5(master_secret || SHA('CCC' || master_secret ||
ServerHello.random || ClientHello.random)) ||...
 TLS
HMAC(master secret, A(1) || seed ) ||
HMAC(master secret, A(2) || seed ) ||
HMAC(master secret, A(3) || seed ) || …
Where A(0) = seed ( “master secret” ||
ServerHello.random||ClientHello.random)
A(i) = HMAC(master secret, A(i-1))
 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
 SSL Alert Protocol
 Conveys SSL-related alerts to peer entity
 Severity
• warning or fatal
 Specific alert
• fatal: unexpected message, bad record mac,
decompression failure, handshake failure, illegal
parameter
• warning: close notify, no certificate, bad certificate,
unsupported certificate, certificate revoked,
certificate expired, certificate unknown
 Compressed & encrypted like all SSL data
 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
• based on HMAC using SHA-1 or MD5

has additional alert codes

some changes in supported ciphers

changes in certificate types & negotiations

changes in crypto computations & padding
 HTTPS
 HTTPS (HTTP over SSL)

combination of HTTP & SSL/TLS to secure
communications between browser & server
• documented in RFC2818
• no fundamental change using either SSL or TLS
 use https:// URL rather than http://

and port 443 rather than 80
 encrypts

URL, document contents, form data, cookies,
HTTP headers
 HTTPS Use
 Connection initiation

TLS handshake then HTTP request(s)
 Connection closure

have “Connection: close” in HTTP record

TLS level exchange close_notify alerts

can then close TCP connection

must handle TCP close before alert exchange
sent or completed
 Secure Shell (SSH)
 Protocol for secure network communications

Designed to be simple & inexpensive
 SSH1 provided secure remote logon facility

Replace TELNET & other insecure schemes

Also has more general client/server capability
 SSH2 fixes a number of security flaws
 Documented in RFCs 4250 through 4254
 SSH clients & servers are widely available
 Method of choice for remote login/ X tunnels
 Summary
 have considered:

need for web security

SSL/TLS transport layer security protocols

HTTPS
Cryptography and
Network Security
Chapter 17
Fifth Edition
by William Stallings
Chapter 17 – Wireless Network
Security
Investigators have published numerous reports of birds
taking turns vocalizing; the bird spoken to gave its full
attention to the speaker and never vocalized at the
same time, as if the two were holding a conversation
Researchers and scholars who have studied the data on
avian communication carefully write the (a) the
communication code of birds such has crows has not
been broken by any means; (b) probably all birds have
wider vocabularies than anyone realizes; and (c)
greater complexity and depth are recognized in avian
communication as research progresses.
—The Human Nature of Birds, Theodore Barber
 IEEE 802.11
 IEEE 802 committee for LAN standards
 IEEE 802.11 formed in 1990’s

charter to develop a protocol & transmission
specifications for wireless LANs (WLANs)
 Since then demand for WLANs, at
different frequencies and data rates, has
exploded
 Hence seen ever-expanding list of
standards issued
 IEEE 802 Terminology
Access point (AP) Any entity that has station functionality and provides
access to the distribution system via the wireless
medium for associated stations
Basic service set A set of stations controlled by a single coordination
(BSS) function
Coordination function The logical function that determines when a station
operating within a BSS is permitted to transmit and
may be able to receive PDUs
Distribution system A system used to interconnect a set of BSSs and
(DS) integrated LANs to create an ESS
Extended service set A set of one or more interconnected BSSs and
(ESS) integrated LANs that appear as a single BSS to the LLC
layer at any station associated with one of these BSSs
MAC protocol data The unit of data exchanged between two peer MAC
unit (MPDU) entites using the services of the physical layer
MAC service data unit Information that is delivered as a unit between MAC
(MSDU) users
Station Any device that contains an IEEE 802.11 conformant MAC
and physical layer
 Wi-Fi Alliance
 802.11b first broadly accepted standard
 WirelessEthernet Compatibility Alliance
(WECA) industry consortium formed 1999

To assist interoperability of products

Renamed Wi-Fi (Wireless Fidelity) Alliance

Created a test suite to certify interoperability

Initially for 802.11b, later extended to
802.11g/n/ac/ax

Concerned with a range of WLANs markets,
including enterprise, home, and hot spots
Network Components &
Architecture
IEEE 802.11 Services
802.11 Wireless LAN Security
 Inherently insecure as wireless traffic can
be monitored by any radio in range.
 Original 802.11 spec had security features

Wired Equivalent Privacy (WEP) algorithm

But found this contained major weaknesses
 802.11itask group developed capabilities
to address WLAN security issues

Wi-Fi Alliance Wi-Fi Protected Access (WPA)

Final 802.11i Robust Security Network (RSN)
 Wire Equivalent Privacy
 Confidentiality (RC 4 using single shared key)

WEP-40 : 40 bit + 24 bit IV = 64 bit encryption key.

WEP-104: 104 bit key + 24 bit IV = 128 bit key encryption key.

152 bit and 256 bit WEP were also available from some vendors.

Each WEP key should be 10 hex or 5 ASCII characters in length
for WEP-40 encryption and 26 hex or 13 ASCII characters in
length for WEP-104 encryption.
– WEP-104 was broken by 2004
 Integrity (CRC-32)

32 bit CRC.
 Authentication

Open System Authentication (null authentication)

Shared Key Authentication using four step challenge response
 802.11i Standards
 802.11i task group developed capabilities to
address WEP weaknesses

Wi-Fi Protected Access (WPA) in 2003
• Intended as an intermediate measure in anticipation
of the availability of the more secure and complex
RSN/WPA2

Final 802.11i Robust Security Network
(RSN/WPA 2) in 2004
• Also referred to as WPA 2

WPA 3 announced in 2018

WPA/WPA 2 has two generations named Enterprise
and Personal.
 Target Users
 WPA-Personal: Also referred to as WPA-PSK (pre-shared
key) mode, Designed for home and small office networks.
Doesn't require an authentication server. PSK should be 8-36
characters in length.
 WPA-Enterprise: Also referred to as WPA-802.1X mode,
and sometimes just WPA (as opposed to WPA-PSK).
Designed for enterprise networks and requires a RADIUS
authentication server. The AP uses Extensible Authentication
Protocol (EAP) to negotiate pair-wise master key with each
STA.
 Wi-Fi Protected Setup (WPS): An alternative
authentication key distribution method intended to simplify
and strengthen the process. Unfortunately creates a major
security hole via WPS PIN recovery.
 IEEE 802.11i Services
 Authentication

Allows user and authentication server to perform
mutual authentication and generate temporary keys to
be used between STA and AP.
 Access Control

Enforces use of authentication function, routes
messages properly and facilitates key exchange.
 Privacy with message integrity

MAC level data is encrypted along with message
integrity code to protect against data alteration.
Wi-Fi Protected Access (WPA)
 Implements subset of IEEE802.11i draft.

Temporal Key Integrity Protocol (TKIP)
• Combines the secret root key with the initialization
vector before passing it to the RC4.
• Employs a per-packet key, meaning that it
dynamically generates a new 128-bit key for each
packet .
• Implements a sequence counter to protect against
replay attacks.

Message Integrity Check (64 bit MIC)
• This replaces the cyclic redundancy check (CRC)
• Generated using algorithm Michael. Computed
using source and destination MAC addresses + key.
 802.11i RSN/WPA 2
 RSN provides two new protocols: the four-way
handshake and the group key handshake.
 These utilize the authentication services and port
access control described in IEEE 802.1X to
establish and change the appropriate
cryptographic keys
 Provides two RSNA data confidentiality and
integrity protocols, TKIP and CCMP.

Counter Mode CBC-MAC Protocol (CCMP): CCM
Mode Protocol of the Advanced Encryption Standard
(AES) standard combines AES-CTR mode for data
confidentiality and AES-CBC-MAC for authentication
and integrity.
802.11i RSN Services and
Protocols
802.11i RSN Cryptographic
Algorithms
802.11i Phases of Operation
(WPA/WPA 2)
 Authentication Phase
 Uses pre-shared key (PSK), or following an EAP
exchange through 802.1X (known as EAPOL,
which requires the presence of an authentication
server).
 This process ensures that the client station
(STA) is authenticated with the access point
(AP)
 After the PSK or 802.1X authentication, a shared
secret key is generated, called the Pairwise
Master Key (PMK).
 Discovery

802.11i
Discovery and
Authentication
Phases Authentication
IEEE 802.1X Access Control
Approach
 Extensible Authentication
Protocol
 EAP is an authentication framework frequently
used in network and internet connections.
• EAP-TLS
• EAP-TTLS/MSCHAPv2
• PEAPv0/EAP-MSCHAPv2
• PEAPv1/EAP-GTC
• PEAP-TLS
• EAP-SIM
• EAP-AKA
• EAP-FAST
 Pairwise Master Key
 In PSK authentication, the PMK is actually the
PSK.
 If an 802.1X EAP exchange was carried out, the
PMK is derived from the EAP parameters
provided by the authentication server.
 The four-way handshake is performed so that
the access point (or authenticator) and wireless
client (or supplicant) can independently prove to
each other that they know the PSK/PMK, without
ever disclosing the key
 Pairwise Transient Key
 The PMK is designed to last the entire session and
should be exposed as little as possible; therefore,
keys to encrypt the traffic need to be derived.
 A four-way handshake is used to establish another
key called the Pairwise Transient Key (PTK).
 The PTK is generated by concatenating the
following attributes: PMK, AP nonce (ANonce), STA
nonce (SNonce), AP MAC address, and STA MAC
address.
 The handshake also yields the GTK (Group
Temporal Key), used to decrypt multicast and
broadcast traffic
 Four Way Handshake

802.11i
Key
Management
Phase
 The Pairwise Transient Key (64 bytes) is divided
into five separate keys:
1. 16 bytes of EAPOL-Key Confirmation Key (KCK) –
Used to compute MIC on WPA EAPOL Key message
2. 16 bytes of EAPOL-Key Encryption Key (KEK) – AP
uses this key to encrypt additional data sent to the
client (for example, the GTK)
3. 16 bytes of Temporal Key (TK) – Used to
encrypt/decrypt Unicast data packets
4. 8 bytes of Michael MIC Authenticator Tx Key – Used
to compute MIC on unicast data packets transmitted
by the AP
5. 8 bytes of Michael MIC Authenticator Rx Key – Used
to compute MIC on unicast data packets transmitted
by the station
 The Group Temporal Key (32 bytes) is divided
into three separate keys:
1. 16 bytes of Group Temporal Encryption Key – used to
encrypt/decrypt Multicast and Broadcast data packets
2. 8 bytes of Michael MIC Authenticator Tx Key – used
to compute MIC on Multicast and Broadcast packets
transmitted by AP
3. 8 bytes of Michael MIC Authenticator Rx Key –
currently unused as stations do not send multicast
traffic
The Michael MIC Authenticator Tx/Rx Keys in both the
PTK and GTK are only used if the network is using
TKIP to encrypt the data.
Four-way handshake has been shown to be vulnerable
to KRACK attack in 2017.
802.11i
Key
Manage-
ment
Phase
 WPA/WPA2 Attack
Offline Dictionary Attack Overview:

- Master key is generated using:

• Passphrase and SSID

- Session keys (KCK, KEK, TK) are generated using:

• Master key, MAC address of client, MAC address of
access point, nonce from client, and nonce from
access point

- Attacker’s goal is to reproduce the key hierarchy to access

the network

- Attacker needs to capture SSID, MAC addresses, and

 WPA/WPA2 Attack Cont.
Offline Dictionary Attack Capture:

- Listen for access point broadcasts

• Recovers SSID

- Passively sniff the network for the 4-way handshake

• Recovers MAC address of client, MAC address of
access point, nonce from client, nonce from access
point, and a MIC (derived from session key (KCK)
and handshake messages)

- Attacker has captured all necessary values and is ready to

perform dictionary attack offline
 WPA/WPA2 Attack Cont.
Offline Dictionary Attack Method:

- Perform dictionary attack on passphrase to generate

master key using:
• Dictionary file (passphrase) and captured SSID

- Generate session keys using:

• Master key, captured MAC addresses, and
captured nonces

- Generate MIC using:

• Session key (KCK) and captured handshake
messages
 How to Defend When Using
WPA/WPA 2
Passphrases: The most popular way to crack WPA is to
sniff the password associated with the handshake
authentication process, and if this password is extremely
complicated it will be almost impossible to crack.

Passphrase Complexity: Select a random passphrase that

is not made up of dictionary words. Select a complex
passphrase of a minimum of 20 characters in length and
change it at regular intervals
 802.11i Protected Data
Transfer Phase
 Have two schemes for protecting data
 Temporal Key Integrity Protocol (TKIP)

S/W changes only to older WEP

Adds 64-bit Michael message integrity code
(MIC)

Encrypts MPDU plus MIC value using RC4
 Counter Mode-CBC MAC Protocol (CCMP)

Uses the cipher block chaining message
authentication code (CBC-MAC) for integrity

Uses the CRT block cipher mode of operation
 Summary
 Have considered:

IEEE 802.11 Wireless LANs
• protocol overview and security
Cryptography and
Network Security
Chapter 19
Fifth Edition
by William Stallings
 Chapter 19 – 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
 IP Security
 Have a range of 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
 IP Security
 General IP Security mechanisms
 Provides

authentication

confidentiality

key management
 Applicable to use over LANs, across public
& private WANs, & for the Internet
 Need identified in 1994 report

Need authentication, encryption in IPv4 &
IPv6
 Benefits of IPSec
 In a firewall/router provides strong security
to all traffic crossing the perimeter
 In a firewall/router is resistant to bypass
 Is below transport layer, hence transparent
to applications
 Can be transparent to end users
 Can provide security for individual users
 Secures routing architecture
 IPSec Services
 Access control
 Connectionless integrity
 Data origin authentication
 Rejection of replayed packets

A form of partial sequence integrity
 Confidentiality (encryption)(only by ESP)
 Limited traffic flow confidentiality
 IP Security Architecture
 Specification is quite complex, with groups:

Architecture
• RFC4301 Security Architecture for Internet Protocol

Authentication Header (AH)
• RFC4302 IP Authentication Header

Encapsulating Security Payload (ESP)
• RFC4303 IP Encapsulating Security Payload (ESP)

Internet Key Exchange (IKE)
• RFC4306 Internet Key Exchange (IKEv2) Protocol

Cryptographic algorithms

Other
IP Security Uses
 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 MAC key
Authentication Header
Encapsulating Security Payload
(ESP)
 Provides message content confidentiality, data
origin authentication, connectionless integrity, an
anti-replay service, limited traffic flow
confidentiality

 Services depend on options selected when

establish Security Association (SA), net location

 Can use a variety of encryption & authentication

algorithms
Encapsulating Security
Payload
 Encryption & Authentication
Algorithms & Padding
 ESP can encrypt payload data, padding,
pad length, and next header fields

if needed have IV at start of payload data
 ESP can have optional ICV for integrity

is computed after encryption is performed
 ESP uses padding

to expand plaintext to required length

to align pad length and next header fields

to provide partial traffic flow confidentiality
 Anti-Replay Service
 Replay is when attacker resends a copy of
an authenticated packet
 Use sequence number to thwart this attack
 Sender initializes sequence number to 0
when a new SA is established

increment for each packet

must not exceed limit of 232 – 1
 Receiver then accepts packets with seq no
within window of (N –W+1)
 Cryptographic Suites
 Variety of cryptographic algorithm types
 To promote interoperability have

RFC4308 defines VPN cryptographic suites
• VPN-A matches common corporate VPN security
using 3DES & HMAC
• VPN-B has stronger security for new VPNs
implementing IPsecv3 and IKEv2 using AES

RFC4869 defines four cryptographic suites
compatible with US NSA specs
• provide choices for ESP & IKE
• AES-GCM, AES-CBC, HMAC-SHA, ECP, ECDSA
 Transport and Tunnel Modes
 Transport Mode

To encrypt & optionally authenticate IP data

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

No routers on way can examine inner IP
header

Good for VPNs, gateway to gateway security
Transport
and
Tunnel
Modes
Transport
and
Tunnel
Mode
Protocols
Transport and Tunnel Mode
Protocols
 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
 Security Policy Database
 Relates IP traffic to specific SAs

Match subset of IP traffic to relevant SA

Use selectors to filter outgoing traffic to map

Based on: local & remote IP addresses, next
layer protocol, name, local & remote ports
 Combining Security
Associations
 SA’s can implement either AH or ESP
 To implement both need to combine SA’s

Form a security association bundle

May terminate at different or same endpoints

Combined by
• transport adjacency
• iterated tunneling
 Combining authentication & encryption

ESP with authentication, bundled inner ESP &
outer AH, bundled inner transport & outer
ESP
Combining Security
Associations
 IPSec 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
 Oakley
 A key exchange protocol
 Based on Diffie-Hellman key exchange
 Adds features to address weaknesses

No info on parties, man-in-middle attack, cost

So adds cookies, groups (global params),
nonces, DH key exchange with authentication
 Can use arithmetic in prime fields or
elliptic curve fields
 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
 IKEv2 no longer uses Oakley & ISAKMP
terms, but basic functionality is same
 Summary
 Have considered:

IPSec security framework

AH & ESP

Cryptographic suites used

IPSec security policy

Combining security associations

Internet key exchange
Cryptography and
Network Security
Chapter 20
Fifth Edition
by William Stallings

Lecture slides by Lawrie Brown

 Chapter 20– 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
 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
 Intruders
 clearly a growing publicized problem

from “Wily Hacker” in 1986/87

to clearly escalating CERT stats
 range

benign: explore, still costs resources

serious: access/modify data, disrupt system
 led to the development of CERTs
 intruder techniques & behavior patterns
constantly shifting, have common features
 Examples of Intrusion
 remote root compromise
 web server defacement
 guessing / cracking passwords
 copying viewing sensitive data / databases
 running a packet sniffer
 distributing pirated software
 using an unsecured modem to access net
 impersonating a user to reset password
 using an unattended workstation
 Hackers
 motivated by thrill of access and status

hacking community a strong meritocracy

status is determined by level of competence
 benign intruders might be tolerable

do consume resources and may slow performance

can’t know in advance whether benign or malign
 IDS / IPS / VPNs can help counter
 awareness led to establishment of CERTs

collect / disseminate vulnerability info / responses
 Hacker Behavior Example
1. select target using IP lookup tools
2. map network for accessible services
3. identify potentially vulnerable services
4. brute force (guess) passwords
5. install remote administration tool
6. wait for admin to log on and capture
password
7. use password to access remainder of
network
 Criminal Enterprise
 organized groups of hackers now a threat

corporation / government / loosely affiliated gangs

typically young

often Eastern European or Russian hackers

often target credit cards on e-commerce server
 criminal hackers usually have specific targets
 once penetrated act quickly and get out
 IDS / IPS help but less effective
 sensitive data needs strong protection
 Criminal Enterprise Behavior
1. act quickly and precisely to make their
activities harder to detect
2. exploit perimeter via vulnerable ports
3. use trojan horses (hidden software) to
leave back doors for re-entry
4. use sniffers to capture passwords
5. do not stick around until noticed
6. make few or no mistakes.
 Insider Attacks
 among most difficult to detect and prevent
 employees have access & systems knowledge
 may be motivated by revenge / entitlement

when employment terminated

taking customer data when move to competitor
 IDS / IPS may help but also need:

least privilege, monitor logs, strong authentication,
termination process to block access & mirror data
 Insider Behavior Example
1. create network accounts for themselves and
their friends
2. access accounts and applications they wouldn't
normally use for their daily jobs
3. e-mail former and prospective employers
4. conduct furtive instant-messaging chats
5. visit web sites that cater to disgruntled
employees, such as f'dcompany.com
6. perform large downloads and file copying
7. access the network during off hours.
 Intrusion Techniques
 aim to gain access and/or increase
privileges on a system
 often use system / software vulnerabilities
 key goal often is to acquire passwords

so then exercise access rights of owner
 basic attack methodology

target acquisition and information gathering

initial access

privilege escalation

covering tracks
 Password Guessing
 one of the most common attacks
 attacker knows a login (from email/web page etc)
 then attempts to guess password for it

defaults, short passwords, common word searches

user info (variations on names, birthday, phone,
common words/interests)

exhaustively searching all possible passwords
 check by login or against stolen password file
 success depends on password chosen by user
 surveys show many users choose poorly
 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
 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
Intrusion Detection
 Approaches to Intrusion
Detection
 statistical anomaly detection

attempts to define normal/expected behavior

threshold

profile based
 rule-based detection

attempts to define proper behavior

anomaly

penetration identification
 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
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
 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
 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
 Rule-Based Intrusion
Detection
 rule-based penetration identification

uses expert systems technology

with rules identifying known penetration,
weakness patterns, or suspicious behavior

compare audit records or states against rules

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
 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
 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
Distributed Intrusion Detection -
Architecture
Distributed Intrusion Detection –
Agent Implementation
 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
 single or multiple networked systems
 cf IETF Intrusion Detection WG standards
 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
 should protect password file on system
 Password Studies
 Purdue 1992 - many short passwords
 Klein 1990 - many guessable passwords
 conclusion is that users choose poor
passwords too often
 need some approach to counter this
 Managing Passwords -
Education
 can use policies and good user education
 educate on importance of good passwords
 give guidelines for good passwords

minimum length (>6)

require a mix of upper & lower case letters,
numbers, punctuation

not dictionary words
 but likely to be ignored by many users
 Managing Passwords -
Computer Generated
 let computer create passwords
 if random likely not memorisable, so will be
written down (sticky label syndrome)
 even pronounceable not remembered
 have history of poor user acceptance
 FIPS PUB 181 one of best generators

has both description & sample code

generates words from concatenating random
pronounceable syllables
 Managing Passwords -
Reactive Checking
 reactively run password guessing tools

note that good dictionaries exist for almost
any language/interest group
 cracked passwords are disabled
 but is resource intensive
 bad passwords are vulnerable till found
 Managing Passwords -
Proactive 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 earlier slide)

compare against dictionary of bad passwords

use algorithmic (markov model or bloom filter)
to detect poor choices
 Summary
 have considered:

problem of intrusion, behavior and techniques

intrusion detection (statistical & rule-based)

password management
Cryptography and
Network Security
Chapter 22
Fifth Edition
by William Stallings
 Chapter 20 – Firewalls

The function of a strong position is to make

the forces holding it practically
unassailable
—On War, Carl Von Clausewitz
 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
 typically use a Firewall
 to provide perimeter defence
 as part of comprehensive security strategy
 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
 provide NAT & usage monitoring
 implement VPNs using IPSec
 must be immune to penetration
What is a Firewall?
 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 or colluding employees
 cannot protect against access via WLAN

if improperly secured against external use
 cannot protect against malware imported
via laptop, PDA, storage infected outside
 Firewalls – Packet Filters
 simplest, fastest firewall component
 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
Firewalls – Packet Filters
Firewalls – Packet Filters
 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
Firewalls – Stateful Packet Filters
 traditional packet filters do not examine
higher layer context

ie matching return packets with outgoing flow
 stateful packet filters address this need
 they examine each IP packet in context

keep track of client-server sessions

check each packet validly belongs to one
 hence are better able to detect bogus
packets out of context
 may even inspect limited application data
 Firewalls - Application Level
Gateway (or Proxy)
 have 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

can log / audit traffic at application level
 need separate proxies for each service

some services naturally support proxying

others are more problematic
Firewalls - Application Level
Gateway (or Proxy)
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 is commonly used
Firewalls - Circuit Level Gateway
 Bastion Host
 highly secure host system
 runs circuit / application level gateways
 or provides externally accessible services
 potentially exposed to "hostile" elements
 hence is secured to withstand this

hardened O/S, essential services, extra auth

proxies small, secure, independent, non-privileged
 may support 2 or more net connections
 may be trusted to enforce policy of trusted
separation between these net connections
 Host-Based Firewalls
 s/w module used to secure individual host

available in many operating systems

or can be provided as an add-on package
 often used on servers
 advantages:

can tailor filtering rules to host environment

protection is provided independent of topology

provides an additional layer of protection
 Personal Firewalls
 controls traffic between PC/workstation
and Internet or enterprise network
 a software module on personal computer
 or in home/office DSL/cable/ISP router
 typically much less complex than other
firewall types
 primary role to deny unauthorized remote
access to the computer
 and monitor outgoing activity for malware
Personal Firewalls
Firewall Configurations
Firewall Configurations
Firewall Configurations
 DMZ
Networks
Virtual Private Networks
Distributed
Firewalls
 Summary of Firewall
Locations and Topologies
 host-resident firewall
 screening router
 single bastion inline
 single bastion T
 double bastion inline
 double bastion T
 distributed firewall configuration
 Summary
 have considered:

firewalls

types of firewalls
• packet-filter, stateful inspection, application proxy,
circuit-level

basing
• bastion, host, personal

location and configurations
• DMZ, VPN, distributed, topologies