18-03-2011, 02:18 PM
presented by:
Dr. Bill Figg
Cryptography & Network Security.ppt (Size: 1.03 MB / Downloads: 392)
Cryptography & Network Security
Introduction
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
Security Services
• X.800 defines it as: a service provided by a protocol layer of communicating open systems, which ensures adequate security of the systems or of data transfers
• RFC 2828 defines it as: a processing or communication service provided by a system to give a specific kind of protection to system resources
• X.800 defines it in 5 major categories
Security Services (X.800)
• Authentication - assurance that the communicating entity is the one claimed
• Access Control - prevention of the unauthorized use of a resource
• Data Confidentiality –protection of data from unauthorized disclosure
• Data Integrity - assurance that data received is as sent by an authorized entity
• Non-Repudiation - protection against denial by one of the parties in a communication
Security Mechanisms (X.800)
• specific security mechanisms:
– encipherment, digital signatures, access controls, data integrity, authentication exchange, traffic padding, routing control, notarization
• pervasive security mechanisms:
– trusted functionality, security labels, event detection, security audit trails, security recovery
– Classify Security Attacks
• passive attacks - eavesdropping on, or monitoring of, transmissions to:
– obtain message contents, or
– monitor traffic flows
• active attacks – modification of data stream to:
– masquerade of one entity as some other
– replay previous messages
– modify messages in transit
– denial of service
Types of Attacks
Classical Encryption Techniques
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
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
• Symmetric Cipher Model
Cryptography
• can be characterized 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
Types of Cryptanalytic Attacks
• ciphertext only
– only know algorithm / ciphertext, statistical, can identify plaintext
• known plaintext
– know/suspect plaintext & ciphertext to attack cipher
• chosen plaintext
– select plaintext and obtain ciphertext to attack cipher
• chosen ciphertext
– select ciphertext and obtain plaintext to attack cipher
• chosen text
– select either plaintext or ciphertext to en/decrypt to attack cipher
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
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"
• Language Redundancy and Cryptanalysis
• human languages are redundant
• eg "th lrd s m shphrd shll nt wnt"
• letters are not equally commonly used
• in English e is by far the most common letter
• then T,R,N,I,O,A,S
• other letters are fairly rare
• cf. Z,J,K,Q,X
• have tables of single, double & triple letter frequencies
Encrypting and Decrypting
• plaintext encrypted two letters at a time:
– if a pair is a repeated letter, insert a filler like 'X', eg. "balloon" encrypts as "ba lx lo on"
– if both letters fall in the same row, replace each with letter to right (wrapping back to start from end), eg. “ar" encrypts as "RM"
– if both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), eg. “mu" encrypts to "CM"
– otherwise each letter is replaced by the one in its row in the column of the other letter of the pair, eg. “hs" encrypts to "BP", and “ea" to "IM" or "JM" (as desired)
Polyalphabetic Ciphers
• another approach to improving security is to use multiple cipher alphabets
• called polyalphabetic substitution ciphers
• makes 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
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
• 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
• have problem of safe distribution of key
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
Row Transposition Ciphers
• a more complex scheme
• 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: 3 4 2 1 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
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
• has drawbacks
– high overhead to hide relatively few info bits
• Block vs Stream Ciphers
• block ciphers process messages in into 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
• hence are focus of course
Confusion and Diffusion
• cipher needs to completely obscure statistical properties of original message
• a one-time pad does this
• more practically Shannon suggested combining 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 substitution-permutation network concept
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 1990
• 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
Dr. Bill Figg
Cryptography & Network Security.ppt (Size: 1.03 MB / Downloads: 392)
Cryptography & Network Security
Introduction
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
Security Services
• X.800 defines it as: a service provided by a protocol layer of communicating open systems, which ensures adequate security of the systems or of data transfers
• RFC 2828 defines it as: a processing or communication service provided by a system to give a specific kind of protection to system resources
• X.800 defines it in 5 major categories
Security Services (X.800)
• Authentication - assurance that the communicating entity is the one claimed
• Access Control - prevention of the unauthorized use of a resource
• Data Confidentiality –protection of data from unauthorized disclosure
• Data Integrity - assurance that data received is as sent by an authorized entity
• Non-Repudiation - protection against denial by one of the parties in a communication
Security Mechanisms (X.800)
• specific security mechanisms:
– encipherment, digital signatures, access controls, data integrity, authentication exchange, traffic padding, routing control, notarization
• pervasive security mechanisms:
– trusted functionality, security labels, event detection, security audit trails, security recovery
– Classify Security Attacks
• passive attacks - eavesdropping on, or monitoring of, transmissions to:
– obtain message contents, or
– monitor traffic flows
• active attacks – modification of data stream to:
– masquerade of one entity as some other
– replay previous messages
– modify messages in transit
– denial of service
Types of Attacks
Classical Encryption Techniques
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
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
• Symmetric Cipher Model
Cryptography
• can be characterized 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
Types of Cryptanalytic Attacks
• ciphertext only
– only know algorithm / ciphertext, statistical, can identify plaintext
• known plaintext
– know/suspect plaintext & ciphertext to attack cipher
• chosen plaintext
– select plaintext and obtain ciphertext to attack cipher
• chosen ciphertext
– select ciphertext and obtain plaintext to attack cipher
• chosen text
– select either plaintext or ciphertext to en/decrypt to attack cipher
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
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"
• Language Redundancy and Cryptanalysis
• human languages are redundant
• eg "th lrd s m shphrd shll nt wnt"
• letters are not equally commonly used
• in English e is by far the most common letter
• then T,R,N,I,O,A,S
• other letters are fairly rare
• cf. Z,J,K,Q,X
• have tables of single, double & triple letter frequencies
Encrypting and Decrypting
• plaintext encrypted two letters at a time:
– if a pair is a repeated letter, insert a filler like 'X', eg. "balloon" encrypts as "ba lx lo on"
– if both letters fall in the same row, replace each with letter to right (wrapping back to start from end), eg. “ar" encrypts as "RM"
– if both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), eg. “mu" encrypts to "CM"
– otherwise each letter is replaced by the one in its row in the column of the other letter of the pair, eg. “hs" encrypts to "BP", and “ea" to "IM" or "JM" (as desired)
Polyalphabetic Ciphers
• another approach to improving security is to use multiple cipher alphabets
• called polyalphabetic substitution ciphers
• makes 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
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
• 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
• have problem of safe distribution of key
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
Row Transposition Ciphers
• a more complex scheme
• 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: 3 4 2 1 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
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
• has drawbacks
– high overhead to hide relatively few info bits
• Block vs Stream Ciphers
• block ciphers process messages in into 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
• hence are focus of course
Confusion and Diffusion
• cipher needs to completely obscure statistical properties of original message
• a one-time pad does this
• more practically Shannon suggested combining 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 substitution-permutation network concept
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 1990
• 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