Bài giảng Cryptography - TS. Lê Nhật Duy

(cid:61591) (cid:61590) TS. Lê Nhật Duy

(cid:61558) Lê Nhật Duy, PhD. (cid:61558) Blog: https://Lnduy.wordpress.com (cid:61558) Email: Ln.duy@mail.ru

2

(cid:61558) Reference books (cid:61558) Reference books (cid:61558) Subject introduction (cid:61558) Subject introduction (cid:61558) Examination (cid:61558) Examination (cid:61558) Rules (cid:61558) Rules

(cid:51)

(cid:61592) Giáo trình chính: (cid:61592) Giáo trình chính: (cid:61592) Stallings W., Cryptography and Network Security. (cid:61592) Stallings W., Cryptography and Network Security.

Principles and Practice, 5th edition, Prentice Hall, 2010 Principles and Practice, 5th edition, Prentice Hall, 2010

(cid:61592) Tài liệu tham khảo: (cid:61592) Tài liệu tham khảo: (cid:61592) Rick Lehtinen, Computer Security Basics, 2006, (cid:61592) Rick Lehtinen, Computer Security Basics, 2006,

O'Reilly Publishing O'Reilly Publishing

(cid:61558) Emmett Dulaney, CompTIA Security+ Deluxe Study (cid:61558) Emmett Dulaney, CompTIA Security+ Deluxe Study

Guide, Wiley Publishing, 2009 Guide, Wiley Publishing, 2009

(cid:52)

1. OVERVIEW 1. OVERVIEW 2. SYMMETRIC CIPHERS 2. SYMMETRIC CIPHERS

2.1. Classical Encryption Techniques 2.1. Classical Encryption Techniques 2.2. Block Ciphers And The Data Encryption Standard 2.2. Block Ciphers And The Data Encryption Standard 2.3. Basic Concepts In Number Theory And Finite Fields 2.3. Basic Concepts In Number Theory And Finite Fields 2.4. Advanced Encryption Standard 2.4. Advanced Encryption Standard 2.5. Block Cipher Operation 2.5. Block Cipher Operation 2.6. Pseudorandom number generation and stream 2.6. Pseudorandom number generation and stream

ciphers ciphers

(cid:53)

3. ASYMMETRIC CIPHERS 3. ASYMMETRIC CIPHERS

3.1. Introduction To Number Theory 3.1. Introduction To Number Theory 3.2. Public-key Cryptography and RSA 3.2. Public-key Cryptography and RSA 3.3. Other Public-key Cryptosystems 3.3. Other Public-key Cryptosystems

4. CRYPTOGRAPHIC DATA INTEGRITY ALGORITHMS 4. CRYPTOGRAPHIC DATA INTEGRITY ALGORITHMS

4.1. Cryptographic Hash Functions 4.1. Cryptographic Hash Functions 4.2. Message Authentication Codes 4.2. Message Authentication Codes 4.3. Digital Signatures 4.3. Digital Signatures

5. MUTUAL TRUST 5. MUTUAL TRUST

5.1. Key Management And Distribution 5.1. Key Management And Distribution 5.2. User Authentication 5.2. User Authentication

(cid:54)

(cid:61558) Mid-term (cid:61558) Assignments (cid:61558) Final test

(cid:55)

(cid:61592) (cid:8230)

(cid:56)

(cid:61591) (cid:61590)

1. Computer Security Concepts 1. Computer Security Concepts 2. The OSI Security Architecture 2. The OSI Security Architecture 3. Security Attacks 3. Security Attacks 4. Security Services 4. Security Services 5. Security Mechanisms 5. Security Mechanisms 6. A Model for Network Security 6. A Model for Network Security

(cid:50)

(cid:61558) The Open Systems Interconnection (OSI) security architecture (cid:61558) The Open Systems Interconnection (OSI) security architecture provides a systematic framework for defining security attacks, provides a systematic framework for defining security attacks, mechanisms, and services. mechanisms, and services.

(cid:61558) Security attacks are classified as either passive attacks, which (cid:61558) Security attacks are classified as either passive attacks, which include unauthorized reading of a message of file and traffic include unauthorized reading of a message of file and traffic analysis or active attacks, such as modification of messages or analysis or active attacks, such as modification of messages or files, and denial of service. files, and denial of service.

(cid:61558) A security mechanism is any process (or a device incorporating (cid:61558) A security mechanism is any process (or a device incorporating such a process) that is designed to detect, prevent, or recover such a process) that is designed to detect, prevent, or recover from a security attack. Examples of mechanisms are encryption from a security attack. Examples of mechanisms are encryption algorithms, digital signatures, and authentication protocols. algorithms, digital signatures, and authentication protocols.

(cid:61558) Security services include authentication, access control, data (cid:61558) Security services include authentication, access control, data confidentiality, data integrity, nonrepudiation, and availability. confidentiality, data integrity, nonrepudiation, and availability.

(cid:51)

preserving preserving

objectives objectives

the the

of of

software, software,

(includes (includes

(cid:61558) COMPUTER SECURITY: The protection afforded to an (cid:61558) COMPUTER SECURITY: The protection afforded to an automated information system in order to attain the automated information system in order to attain the integrity, integrity, applicable applicable availability, and confidentiality of information system availability, and confidentiality of information system firmware, firmware, hardware, hardware, resources resources information/data, and telecommunications). information/data, and telecommunications).

(cid:61558) This definition introduces three key objectives that are at (cid:61558) This definition introduces three key objectives that are at

the heart of computer security: the heart of computer security:

(cid:61558) Confidentiality (cid:61558) Confidentiality (cid:61558) Integrity (cid:61558) Integrity (cid:61558) Availability (cid:61558) Availability

(cid:52)

(cid:61592) Confidentiality: Data (cid:61592) Confidentiality: Data confidentiality, Privacy confidentiality, Privacy

(cid:61592) Integrity: Data (cid:61592) Integrity: Data

integrity, System integrity, System integrity integrity (cid:61592) Availability. (cid:61592) Availability.

CIA triad (Figure 1.1) CIA triad (Figure 1.1)

5

(cid:61558) Although the use of the CIA triad to define security (cid:61558) Although the use of the CIA triad to define security objectives is well established, some in the security field objectives is well established, some in the security field that additional concepts are needed to present a that additional concepts are needed to present a feel feel complete picture. Two of the most commonly mentioned complete picture. Two of the most commonly mentioned are as follows: are as follows:

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

(cid:54)

(cid:61558) Accountability: The security goal (cid:61558) Accountability: The security goal

that generates the that generates the requirement for actions of an entity to be traced uniquely requirement for actions of an entity to be traced uniquely to that entity. This supports nonrepudiation, deterrence, to that entity. This supports nonrepudiation, deterrence, fault isolation, intrusion detection and prevention, and fault isolation, intrusion detection and prevention, and after-action recovery and legal action. Because truly after-action recovery and legal action. Because truly secure systems are not yet an achievable goal, we must be secure systems are not yet an achievable goal, we must be able to trace a security breach to a responsible party. able to trace a security breach to a responsible party. Systems must keep records of their activities to permit Systems must keep records of their activities to permit later forensic analysis to trace security breaches or to aid later forensic analysis to trace security breaches or to aid in transaction disputes. in transaction disputes.

(cid:55)

is a possible danger is a possible danger

(cid:61558) Threats and Attacks (RFC 2828) (cid:61558) Threats and Attacks (RFC 2828) (cid:61558) Threat: A potential for violation of security, which exists (cid:61558) Threat: A potential for violation of security, which exists when there is a circumstance, capability, action, or event when there is a circumstance, capability, action, or event that could breach security and cause harm. That is, a that could breach security and cause harm. That is, a that might exploit a that might exploit a threat threat vulnerability. vulnerability.

(cid:61558) Attack: An assault on system security that derives from (cid:61558) Attack: An assault on system security that derives from an intelligent threat; that is, an intelligent act that is a an intelligent threat; that is, an intelligent act that is a deliberate attempt (especially in the sense of a method or deliberate attempt (especially in the sense of a method or technique) to evade security services and violate the technique) to evade security services and violate the security policy of a system. security policy of a system.

(cid:56)

(cid:61558) Security attack: Any action that compromises the (cid:61558) Security attack: Any action that compromises the

(cid:61558) Security mechanism: A process (cid:61558) Security mechanism: A process

security of information owned by an organization. security of information owned by an organization. a a

(or (or

device device incorporating such a process) that is designed to detect, incorporating such a process) that is designed to detect, prevent, or recover from a security attack. prevent, or recover from a security attack.

(cid:61558) Security service: A processing or communication service (cid:61558) Security service: A processing or communication service that enhances the security of the data processing systems that enhances the security of the data processing systems and the information transfers of an organization. The and the information transfers of an organization. The services are intended to counter security attacks, and they services are intended to counter security attacks, and they make use of one or more security mechanisms to provide make use of one or more security mechanisms to provide the service. the service.

(cid:57)

(cid:61558) Passive Attacks: Passive attacks are in the nature of (cid:61558) Passive Attacks: Passive attacks are in the nature of eavesdropping on, or monitoring of, transmissions. The eavesdropping on, or monitoring of, transmissions. The goal of the opponent is to obtain information that is being goal of the opponent is to obtain information that is being transmitted. Two types of passive attacks are the release transmitted. Two types of passive attacks are the release of message contents and traffic analysis. of message contents and traffic analysis.

(cid:49)(cid:48)

(cid:49)(cid:49)

12

(cid:61558) Active attacks involve some modification of the data (cid:61558) Active attacks involve some modification of the data stream or the creation of a false stream and can be stream or the creation of a false stream and can be subdivided into four categories: masquerade, replay, subdivided into four categories: masquerade, replay, modification of messages, and denial of service. modification of messages, and denial of service.

(cid:61558) Masquerade (Figure 1.3a) (cid:61558) Masquerade (Figure 1.3a) (cid:61558) Replay (Figure 1.3b) (cid:61558) Replay (Figure 1.3b) (cid:61558) Modification of messages (Figure 1.3c) (cid:61558) Modification of messages (Figure 1.3c) (cid:61558) Denial of service (Figure 1.3d) (cid:61558) Denial of service (Figure 1.3d)

(cid:49)(cid:51)

(cid:49)(cid:52)

(cid:49)(cid:53)

(cid:49)(cid:54)

(cid:49)(cid:55)

(cid:49)(cid:56)

(cid:49)(cid:57)

20

(cid:50)(cid:49)

22

23

24

25

(cid:61591) (cid:61590)

1. Classical encryption techniques 1. Classical encryption techniques 2. Block ciphers and the data encryption standard 2. Block ciphers and the data encryption standard 3. Basic concepts in number theory and finite fields 3. Basic concepts in number theory and finite fields 4. Advanced encryption standard 4. Advanced encryption standard 5. Block cipher operation 5. Block cipher operation 6. Pseudorandom number generation and stream ciphers 6. Pseudorandom number generation and stream ciphers

2

(cid:61558) Symmetric Cipher Model (cid:61558) Symmetric Cipher Model (cid:61558) Substitution Techniques (cid:61558) Substitution Techniques (cid:61558) Transposition Techniques (cid:61558) Transposition Techniques (cid:61558) Rotor Machines (cid:61558) Rotor Machines (cid:61558) Steganography (cid:61558) Steganography

3

(cid:61592) Symmetric encryption is a form of cryptosystem in (cid:61592) Symmetric encryption is a form of cryptosystem in which encryption and decryption are performed using the which encryption and decryption are performed using the same key. It is also known as conventional encryption. same key. It is also known as conventional encryption.

(cid:61592) Symmetric (cid:61592) Symmetric

encryption encryption

transforms transforms

plaintext plaintext

into into ciphertext using a secret key and an encryption algorithm. ciphertext using a secret key and an encryption algorithm. Using the same key and a decryption algorithm, the the Using the same key and a decryption algorithm, plaintext is recovered from the ciphertext. plaintext is recovered from the ciphertext.

(cid:61592) The two types of attack on an encryption algorithm are (cid:61592) The two types of attack on an encryption algorithm are the encryption the encryption cryptanalysis, based on properties of cryptanalysis, based on properties of algorithm, and brute-force, which involves trying all algorithm, and brute-force, which involves trying all possible keys. possible keys.

4

(cid:61592) Traditional (cid:61592) Traditional

symmetric symmetric

(precomputer) (precomputer)

ciphers ciphers

elements. elements.

use use substitution and/or transposition techniques. Substitution substitution and/or transposition techniques. Substitution techniques map plaintext elements (characters, bits) into techniques map plaintext elements (characters, bits) into techniques techniques Transposition Transposition ciphertext ciphertext systematically transpose the positions of plaintext the positions of plaintext systematically transpose elements. elements.

(cid:61592) Rotor machines are sophisticated precomputer hardware (cid:61592) Rotor machines are sophisticated precomputer hardware

devices that use substitution techniques. devices that use substitution techniques.

(cid:61592) Steganography is a technique for hiding a secret message (cid:61592) Steganography is a technique for hiding a secret message within a larger one in such a way that others cannot within a larger one in such a way that others cannot discern the presence or contents of the hidden message. discern the presence or contents of the hidden message.

5

6

(cid:61592) Plaintext: This is the original intelligible message or data (cid:61592) Plaintext: This is the original intelligible message or data

that is fed into the algorithm as input that is fed into the algorithm as input

(cid:61592) Encryption algorithm: The encryption algorithm performs (cid:61592) Encryption algorithm: The encryption algorithm performs various substitutions and transformations on the plaintext. various substitutions and transformations on the plaintext. (cid:61592) Secret key: The secret key is also input to the encryption (cid:61592) Secret key: The secret key is also input to the encryption algorithm. The key is a value independent of the plaintext algorithm. The key is a value independent of the plaintext and of the algorithm and of the algorithm

(cid:61592) Ciphertext: This is the scrambled message produced as (cid:61592) Ciphertext: This is the scrambled message produced as

output. It depends on the plaintext and the secret key. output. It depends on the plaintext and the secret key.

(cid:61592) Decryption algorithm: This is essentially the encryption (cid:61592) Decryption algorithm: This is essentially the encryption algorithm run in reverse. It takes the ciphertext and the algorithm run in reverse. It takes the ciphertext and the secret key and produces the original plaintext. secret key and produces the original plaintext.

7

8

(cid:61592) Cryptographic systems are characterized along three (cid:61592) Cryptographic systems are characterized along three

independent dimensions: independent dimensions:

1. The type of operations used for transforming 1. The type of operations used for transforming plaintext to ciphertext. (substitution, transposition). plaintext to ciphertext. (substitution, transposition). 2. The number of keys used (symmetric, public-key 2. The number of keys used (symmetric, public-key

encryption) encryption)

3. The way in which the plaintext is processed (block 3. The way in which the plaintext is processed (block

cipher, stream cipher) cipher, stream cipher)

9

(cid:61592) Cryptanalysis: Cryptanalytic attacks rely on the nature of (cid:61592) Cryptanalysis: Cryptanalytic attacks rely on the nature of the the the algorithm plus perhaps some knowledge of the algorithm plus perhaps some knowledge of general characteristics of the plaintext or even some general characteristics of the plaintext or even some sample plaintext–ciphertext pairs. This type of attack sample plaintext–ciphertext pairs. This type of attack exploits the characteristics of the algorithm to attempt to exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being deduce a specific plaintext or to deduce the key being used. used.

(cid:61592) Brute-force attack: The attacker tries every possible key (cid:61592) Brute-force attack: The attacker tries every possible key on a piece of cipher-text until an intelligible translation on a piece of cipher-text until an intelligible translation into plaintext is obtained. On average, half of all possible into plaintext is obtained. On average, half of all possible keys must be tried to achieve success. keys must be tried to achieve success.

10

11

(cid:61592) A brute-force attack involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained. On average, half of all possible keys must be tried to achieve success.

12

(cid:61592) A substitution technique is one in which the letters of (cid:61592) A substitution technique is one in which the letters of plaintext are replaced by other letters or by numbers or plaintext are replaced by other letters or by numbers or symbols.1 If the plaintext is viewed as a sequence of bits, symbols.1 If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns then substitution involves replacing plaintext bit patterns with ciphertext bit patterns. with ciphertext bit patterns.

(cid:61592) Caesar Cipher (cid:61592) Caesar Cipher (cid:61592) For example, (cid:61592) For example, (cid:61592) plain: meet me after the toga party (cid:61592) plain: meet me after the toga party (cid:61592) cipher: PHHW PH DIWHU WKH WRJD SDUWB (cid:61592) cipher: PHHW PH DIWHU WKH WRJD SDUWB

13

14

(cid:61592) Monoalphabetic Ciphers (cid:61592) Monoalphabetic Ciphers (cid:61592) Playfair Cipher (cid:61592) Playfair Cipher (cid:61592) Hill Cipher (cid:61592) Hill Cipher (cid:61592) Polyalphabetic Ciphers (cid:61592) Polyalphabetic Ciphers

15

16

relationship to the plaintext. Because relationship to the plaintext. Because

(cid:61592) An Army Signal Corp officer, Joseph Mauborgne, proposed (cid:61592) An Army Signal Corp officer, Joseph Mauborgne, proposed to the Vernam cipher that yields the to the Vernam cipher that yields the an improvement an improvement ultimate in security. Mauborgne suggested using a random ultimate in security. Mauborgne suggested using a random key that is as long as the message, so that the key need not key that is as long as the message, so that the key need not be repeated. In addition, the key is to be used to encrypt and be repeated. In addition, the key is to be used to encrypt and decrypt a single message, and then is discarded. Each new decrypt a single message, and then is discarded. Each new message requires a new key of the same length as the message requires a new key of the same length as the new message. Such a scheme, known as a one-time pad, is new message. Such a scheme, known as a one-time pad, is that bears no unbreakable. It produces random output that bears no unbreakable. It produces random output the the statistical statistical ciphertext contains no information whatsoever about the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code. plaintext, there is simply no way to break the code.

17

(cid:61592) The simplest such cipher is the rail fence technique, in (cid:61592) The simplest such cipher is the rail fence technique, in which the plaintext is written down as a sequence of which the plaintext is written down as a sequence of diagonals and then read off as a sequence of rows. For diagonals and then read off as a sequence of rows. For example, to encipher the message “meet me after the example, to encipher the message “meet me after the toga party” with a rail fence of depth 2, we write the toga party” with a rail fence of depth 2, we write the following: following:

m e m a t r h t g p r y m e m a t r h t g p r y e t e f e t e o a a t e t e f e t e o a a t

(cid:61592) The encrypted message is (cid:61592) The encrypted message is

MEMATRHTGPRYETEFETEOAAT MEMATRHTGPRYETEFETEOAAT

18

19

(cid:61592) A plaintext message may be hidden in one of two ways. (cid:61592) A plaintext message may be hidden in one of two ways. The methods of steganography conceal the existence of The methods of steganography conceal the existence of the message, whereas the methods of cryptography render the message, whereas the methods of cryptography render the message unintelligible to outsiders by various the message unintelligible to outsiders by various transformations of the text. transformations of the text.

(cid:61592) Character marking: Selected letters of printed or (cid:61592) Character marking: Selected letters of printed or typewritten text are over-written in pencil. The marks are typewritten text are over-written in pencil. The marks are ordinarily not visible unless the paper is held at an angle ordinarily not visible unless the paper is held at an angle to bright light. to bright light.

(cid:61592) Invisible ink: A number of substances can be used for (cid:61592) Invisible ink: A number of substances can be used for writing but leave no visible trace until heat or some writing but leave no visible trace until heat or some chemical is applied to the paper. chemical is applied to the paper.

20

(cid:61592) Pin punctures: Small pin punctures on selected letters (cid:61592) Pin punctures: Small pin punctures on selected letters are ordinarily not visible unless the paper is held up in are ordinarily not visible unless the paper is held up in front of a light. front of a light.

(cid:61592) Typewriter correction ribbon: Used between lines typed (cid:61592) Typewriter correction ribbon: Used between lines typed the results of typing with the the results of typing with the

with a black ribbon, with a black ribbon, correction tape are visible only under a strong light. correction tape are visible only under a strong light.

The advantage of steganography is that it can be employed The advantage of steganography is that it can be employed by parties who have something to lose should the fact of by parties who have something to lose should the fact of their secret communication (not necessarily the content) their secret communication (not necessarily the content) be discovered. Encryption flags traffic as important or be discovered. Encryption flags traffic as important or secret or may identify the sender or receiver as someone secret or may identify the sender or receiver as someone with something to hide. with something to hide.

21

(cid:61592) Block Cipher Principles (cid:61592) The Data Encryption Standard

22

(cid:61592) A block cipher is an encryption/decryption scheme in (cid:61592) A block cipher is an encryption/decryption scheme in which a block of plaintext is treated as a whole and used which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length. to produce a ciphertext block of equal length.

(cid:61592) Many block ciphers have a Feistel structure. Such a (cid:61592) Many block ciphers have a Feistel structure. Such a structure consists of a number of identical rounds of structure consists of a number of identical rounds of processing. In each round, a substitution is performed on processing. In each round, a substitution is performed on one half of the data being processed, followed by a one half of the data being processed, followed by a permutation that interchanges the two halves. The original permutation that interchanges the two halves. The original key is expanded so that a different key is used for each key is expanded so that a different key is used for each round. round.

23

recently. recently.

(cid:61592) The Data Encryption Standard (DES) has been the most (cid:61592) The Data Encryption Standard (DES) has been the most It It widely used encryption algorithm until widely used encryption algorithm until exhibits the classic Feistel structure. DES uses a 64-bit exhibits the classic Feistel structure. DES uses a 64-bit block and a 56-bit key. block and a 56-bit key.

(cid:61592) Two important methods of cryptanalysis are differential (cid:61592) Two important methods of cryptanalysis are differential cryptanalysis and linear cryptanalysis. DES has been cryptanalysis and linear cryptanalysis. DES has been shown to be highly resistant to these two types of attack. shown to be highly resistant to these two types of attack.

24

(cid:61592) Stream Ciphers and Block Ciphers (cid:61592) Stream Ciphers and Block Ciphers (cid:61592) A stream cipher is one that encrypts a digital data stream (cid:61592) A stream cipher is one that encrypts a digital data stream

one bit or one byte at a time. one bit or one byte at a time.

(cid:61592) A block cipher is one in which a block of plaintext is (cid:61592) A block cipher is one in which a block of plaintext is treated as a whole and used to produce a ciphertext block treated as a whole and used to produce a ciphertext block of equal length. Typically, a block size of 64 or 128 bits is of equal length. Typically, a block size of 64 or 128 bits is used. used.

25

26

(cid:61592) In the late 1960s, IBM set up a research project (cid:61592) In the late 1960s, IBM set up a research project

in in computer cryptography led by Horst Feistel. The project computer cryptography led by Horst Feistel. The project concluded in 1971 with the development of an algorithm concluded in 1971 with the development of an algorithm with the designation LUCIFER [FEIS73], which was sold with the designation LUCIFER [FEIS73], which was sold to Lloyd’s of London for use in a cash-dispensing system, to Lloyd’s of London for use in a cash-dispensing system, also developed by IBM. also developed by IBM.

(cid:61592) In 1973, the National Bureau of Standards (NBS) issued a (cid:61592) In 1973, the National Bureau of Standards (NBS) issued a request for proposals for a national cipher standard. IBM request for proposals for a national cipher standard. IBM submitted the results of its Tuchman–Meyer project. This submitted the results of its Tuchman–Meyer project. This was by far the best algorithm proposed and was adopted was by far the best algorithm proposed and was adopted in 1977 as the Data Encryption Standard. in 1977 as the Data Encryption Standard.

27

(cid:61592) As with any encryption scheme, there are two inputs to (cid:61592) As with any encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the encryption function: the plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in the key. In this case, the plaintext must be 64 bits in length and the key is 56 bits in length (Actually, the length and the key is 56 bits in length (Actually, the function expects a 64-bit key as input. However, only 56 function expects a 64-bit key as input. However, only 56 of these bits are ever used; the other 8 bits can be used as of these bits are ever used; the other 8 bits can be used as parity bits or simply set arbitrarily). parity bits or simply set arbitrarily).

28

29

30

31

(cid:61592) Divisibility and The Division Algorithm (cid:61592) Divisibility and The Division Algorithm (cid:61592) The Euclidean Algorithm (cid:61592) The Euclidean Algorithm (cid:61592) Modular Arithmetic (cid:61592) Modular Arithmetic (cid:61592) Groups, Rings, and Fields (cid:61592) Groups, Rings, and Fields (cid:61592) Finite Fields of the Form GF(p) (cid:61592) Finite Fields of the Form GF(p) (cid:61592) Polynomial Arithmetic (cid:61592) Polynomial Arithmetic (cid:61592) Finite Fields of the Form GF(2^n) (cid:61592) Finite Fields of the Form GF(2^n)

32

(cid:61592) Modular arithmetic is a kind of integer arithmetic that (cid:61592) Modular arithmetic is a kind of integer arithmetic that reduces all numbers to one of a fixed set [0,...,n-1] for reduces all numbers to one of a fixed set [0,...,n-1] for some number n. Any integer outside this range is reduced some number n. Any integer outside this range is reduced to one in this range by taking the remainder after division to one in this range by taking the remainder after division by n. by n.

(cid:61592) The greatest common divisor of two integers is the largest (cid:61592) The greatest common divisor of two integers is the largest

positive integer that exactly divides both integers. positive integer that exactly divides both integers.

(cid:61592) A field is a set of elements on which two arithmetic (cid:61592) A field is a set of elements on which two arithmetic operations (addition and multiplication) have been defined operations (addition and multiplication) have been defined and which has the properties of ordinary arithmetic, such and which has the properties of ordinary arithmetic, such as closure, associativity, commutativity, distributivity, and as closure, associativity, commutativity, distributivity, and having both additive and multiplicative inverses. having both additive and multiplicative inverses.

33

(cid:61592) Finite (cid:61592) Finite

in in

are are

fields fields

important important

several several

areas areas

of of cryptography. A finite field is simply a field with a finite cryptography. A finite field is simply a field with a finite number of elements. It can be shown that the order of a number of elements. It can be shown that the order of a finite field (number of elements in the field) must be a finite field (number of elements in the field) must be a power of a prime p^n, where n is a positive integer. power of a prime p^n, where n is a positive integer.

(cid:61592) Finite fields of order p can be defined using arithmetic (cid:61592) Finite fields of order p can be defined using arithmetic

mod p. mod p.

(cid:61592) Finite fields of order p^n, for n>1, can be defined using (cid:61592) Finite fields of order p^n, for n>1, can be defined using

arithmetic over polynomials. arithmetic over polynomials.

34

35

36

common common

(cid:61592) Definition: Two integers (cid:61592) Definition: Two integers are relatively primeif their are relatively primeif their only positive positive only integer factor is 1. integer factor is 1.

(cid:61592) Finding (cid:61592) Finding

the Greatest the Greatest

Common Divisor Common Divisor

37

(cid:61592) Properties of Congruences

38

39

40

41

42

43

44

45

46

47

48

(cid:61592) Finite Field Arithmetic (cid:61592) Finite Field Arithmetic (cid:61592) AES Structure (cid:61592) AES Structure (cid:61592) AES Transformation Functions (cid:61592) AES Transformation Functions (cid:61592) AES Key Expansion (cid:61592) AES Key Expansion (cid:61592) An AES Example (cid:61592) An AES Example (cid:61592) AES Implementation (cid:61592) AES Implementation

49

(cid:61592) AES is a block cipher intended to replace DES for (cid:61592) AES is a block cipher intended to replace DES for commercial applica-tions. It uses a 128-bit block size and commercial applica-tions. It uses a 128-bit block size and a key size of 128, 192, or 256 bits. a key size of 128, 192, or 256 bits.

functions: functions:

separate separate

consists consists

four four

of of

(cid:61592) AES does not use a Feistel structure. Instead, each full (cid:61592) AES does not use a Feistel structure. Instead, each full byte byte round round substitution, permutation, arithmetic opera-tions over a substitution, permutation, arithmetic opera-tions over a finite field, and XOR with a key. finite field, and XOR with a key.

50

51

52

(cid:61592) Multiple Encryption and Triple DES (cid:61592) Multiple Encryption and Triple DES (cid:61592) Electronic Code Book (cid:61592) Electronic Code Book (cid:61592) Cipher Block Chaining Mode (cid:61592) Cipher Block Chaining Mode (cid:61592) Cipher Feedback Mode (cid:61592) Cipher Feedback Mode (cid:61592) Output Feedback Mode (cid:61592) Output Feedback Mode (cid:61592) Counter Mode (cid:61592) Counter Mode (cid:61592) XTS-AES Mode for Block-Oriented Storage Devices (cid:61592) XTS-AES Mode for Block-Oriented Storage Devices

53

(cid:61592) Multiple encryption is a technique in which an encryption (cid:61592) Multiple encryption is a technique in which an encryption algorithm is used multiple times. In the first instance, algorithm is used multiple times. In the first instance, plaintext is converted to ciphertext using the encryption plaintext is converted to ciphertext using the encryption algorithm. This ciphertext is then used as input and the algorithm. This ciphertext is then used as input and the algorithm is applied again. This process may be repeated algorithm is applied again. This process may be repeated through any number of stages. through any number of stages.

(cid:61592) Triple DES makes use of three stages of the DES (cid:61592) Triple DES makes use of three stages of the DES

algorithm, using a total of two or three distinct keys. algorithm, using a total of two or three distinct keys.

(cid:61592) A mode of operation is a technique for enhancing the (cid:61592) A mode of operation is a technique for enhancing the effect of a crypto-graphic algorithm or adapting the effect of a crypto-graphic algorithm or adapting the algorithm for an application, such as applying a block algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream. cipher to a sequence of data blocks or a data stream.

54

(cid:61592) Five modes of operation have been standardized by NIST (cid:61592) Five modes of operation have been standardized by NIST for use with symmetric block ciphers such as DES and for use with symmetric block ciphers such as DES and AES: electronic codebook mode, cipher block chaining AES: electronic codebook mode, cipher block chaining mode, cipher feedback mode, output feed-back mode, and mode, cipher feedback mode, output feed-back mode, and counter mode. counter mode.

(cid:61592) Another (cid:61592) Another

important mode, XTS-AES, important mode, XTS-AES,

has has

been been standardized by the IEEE Security in Storage Working standardized by the IEEE Security in Storage Working Group (P1619). The standard describes a method of Group (P1619). The standard describes a method of encryption for data stored in sector-based devices where encryption for data stored in sector-based devices where the threat model includes possible access to stored data by the threat model includes possible access to stored data by the adversary. the adversary.

55

56

Triple DES with Two Keys

of

Triple DES with Three Keys: A number Internet-based applications have adopted three- key 3DES, including PGP and S/MIME

(cid:53)(cid:55)

58

59

60

61

62

63

64

65

66

67

(cid:61592) Principles of Pseudorandom Number Generation (cid:61592) Principles of Pseudorandom Number Generation (cid:61592) Pseudorandom Number Generators (cid:61592) Pseudorandom Number Generators (cid:61592) Pseudorandom Number Generation Using a Block Cipher (cid:61592) Pseudorandom Number Generation Using a Block Cipher (cid:61592) Stream Ciphers (cid:61592) Stream Ciphers (cid:61592) RC4 (cid:61592) RC4 (cid:61592) True Random Number Generators (cid:61592) True Random Number Generators

68

(cid:61592) A capability with (cid:61592) A capability with

number number

to to

a a

of application of application cryptographic functions is random or pseudorandom cryptographic functions is random or pseudorandom number generation. The principle requirement for this number generation. The principle requirement for this the generated number stream be capability is that the generated number stream be capability is that unpredictable. unpredictable.

(cid:61592) A stream cipher is a symmetric encryption algorithm in (cid:61592) A stream cipher is a symmetric encryption algorithm in which ciphertext output is produced bit-by-bit or byte-by- which ciphertext output is produced bit-by-bit or byte-by- byte from a stream of plaintext input. The most widely byte from a stream of plaintext input. The most widely used such cipher is RC4. used such cipher is RC4.

69

(cid:61592) Traditionally, the concern in the generation of a sequence (cid:61592) Traditionally, the concern in the generation of a sequence of allegedly random numbers has been that the sequence of allegedly random numbers has been that the sequence of numbers be random in some well-defined statistical of numbers be random in some well-defined statistical sense. The following two criteria are used to validate that sense. The following two criteria are used to validate that a sequence of numbers is random: a sequence of numbers is random:

(cid:61592) Uniform distribution:The distribution of bits in the (cid:61592) Uniform distribution:The distribution of bits in the sequence should be uniform; that is, the frequency of sequence should be uniform; that is, the frequency of occurrence of ones and zeros should be approximately occurrence of ones and zeros should be approximately equal. equal.

(cid:61592) Independence:No one subsequence in the sequence can (cid:61592) Independence:No one subsequence in the sequence can

be inferred from the others. be inferred from the others.

70

71

72

(cid:61592) RC4 is used in the Secure Sockets Layer/Transport Layer (cid:61592) RC4 is used in the Secure Sockets Layer/Transport Layer Security (SSL/TLS) standards that have been defined for Security (SSL/TLS) standards that have been defined for communication between Web browsers and servers. It is communication between Web browsers and servers. It is also used in the Wired Equivalent Privacy (WEP) also used in the Wired Equivalent Privacy (WEP) protocol and the newer WiFi Protected Access (WPA) protocol and the newer WiFi Protected Access (WPA) protocol that are part of the IEEE 802.11 wireless LAN protocol that are part of the IEEE 802.11 wireless LAN standard. RC4 was kept as a trade secret by RSA Security. standard. RC4 was kept as a trade secret by RSA Security.

73

(cid:61591) (cid:61590)

1.

INTRODUCTION TO NUMBER THEORY 2. PUBLIC-KEYCRYPTOGRAPHY AND RSA 3. OTHER PUBLIC-KEY CRYPTOSYSTEMS

(cid:50)

(cid:61592) Prime Numbers (cid:61592) Prime Numbers (cid:61592) Fermat’s and Euler’s Theorems (cid:61592) Fermat’s and Euler’s Theorems (cid:61592) Testing for Primality (cid:61592) Testing for Primality (cid:61592) The Chinese Remainder Theorem (cid:61592) The Chinese Remainder Theorem (cid:61592) Discrete Logarithms (cid:61592) Discrete Logarithms

(cid:51)

(cid:61592) A prime number is an integer that can only be divided (cid:61592) A prime number is an integer that can only be divided without remainder by positive and negative values of without remainder by positive and negative values of itself and 1. Prime numbers play a critical role both in itself and 1. Prime numbers play a critical role both in number theory and in cryptography. number theory and in cryptography.

(cid:61592) Two theorems that play important roles in public-key (cid:61592) Two theorems that play important roles in public-key theorem and Euler’s theorem and Euler’s

cryptography are Fermat’s cryptography are Fermat’s theorem. theorem.

(cid:52)

(cid:61592) An important requirement in a number of cryptographic (cid:61592) An important requirement in a number of cryptographic algorithms is the ability to choose a large prime number. algorithms is the ability to choose a large prime number. An area of ongoing research is the development of An area of ongoing research is the development of efficient algorithms for determining if a randomly chosen efficient algorithms for determining if a randomly chosen large integer is a prime number. large integer is a prime number.

(cid:61592) Discrete logarithms are fundamental (cid:61592) Discrete logarithms are fundamental

to a number of to a number of public-key algorithms. Discrete logarithms are analogous public-key algorithms. Discrete logarithms are analogous to ordinary logarithms but are defined using modular to ordinary logarithms but are defined using modular arithmetic. arithmetic.

(cid:53)

(cid:61592) Principles Of Public-Key Cryptosystems (cid:61592) The RSA Algorithm

(cid:54)

(cid:61592) Asymmetric encryption is a form of cryptosystem in (cid:61592) Asymmetric encryption is a form of cryptosystem in which encryption and decryption are performed using the which encryption and decryption are performed using the different keys—one a public key and one a private key. It different keys—one a public key and one a private key. It is also known as public-key encryption. is also known as public-key encryption. transforms transforms encryption encryption

(cid:61592) Asymmetric (cid:61592) Asymmetric

plaintext plaintext

into into ciphertext using a one of two keys and an encryption ciphertext using a one of two keys and an encryption algorithm. Using the paired key and a decryption algorithm. Using the paired key and a decryption algorithm, the plaintext is recovered from the ciphertext. algorithm, the plaintext is recovered from the ciphertext.

(cid:55)

(cid:61592) Asymmetric encryption can be used for confidentiality, (cid:61592) Asymmetric encryption can be used for confidentiality,

authentication, or both. authentication, or both.

(cid:61592) The most widely used public-key cryptosystem is RSA. (cid:61592) The most widely used public-key cryptosystem is RSA. The difficulty of attacking RSA is based on the difficulty The difficulty of attacking RSA is based on the difficulty of finding the prime factors of a composite number. of finding the prime factors of a composite number.

(cid:56)

(cid:61592) Asymmetric Keys (cid:61592) Asymmetric Keys (cid:61592) Two related keys, a public key and a private key, that are (cid:61592) Two related keys, a public key and a private key, that are used to perform complementary operations, such as used to perform complementary operations, such as encryption and decryption or signature generation and encryption and decryption or signature generation and signature verification. signature verification. (cid:61592) Public Key Certificate (cid:61592) Public Key Certificate (cid:61592) A digital document issued and digitally signed by the (cid:61592) A digital document issued and digitally signed by the private key of a Certification Authority that binds the private key of a Certification Authority that binds the name of a subscriber to a public key. The certificate name of a subscriber to a public key. The certificate indicates that the subscriber identified in the certificate has indicates that the subscriber identified in the certificate has sole control and access to the corresponding private key. sole control and access to the corresponding private key.

(cid:57)

(cid:61592) Public Key (Asymmetric) Cryptographic Algorithm (cid:61592) Public Key (Asymmetric) Cryptographic Algorithm (cid:61592) A cryptographic algorithm that uses two related keys, a (cid:61592) A cryptographic algorithm that uses two related keys, a public key and a private key. The two keys have the public key and a private key. The two keys have the property that deriving the private key from the public key property that deriving the private key from the public key is computationally infeasible. is computationally infeasible. (cid:61592) Public Key Infrastructure (PKI) (cid:61592) Public Key Infrastructure (PKI) (cid:61592) A set of policies, processes, server platforms, software (cid:61592) A set of policies, processes, server platforms, software and workstations used for the purpose of administering and workstations used for the purpose of administering certificates and public-private key pairs, including the certificates and public-private key pairs, including the ability to issue, maintain, and revoke public key ability to issue, maintain, and revoke public key certificates. certificates.

(cid:49)(cid:48)

11

(cid:49)(cid:50)

(cid:61592) Plaintext (cid:61592) Plaintext (cid:61592) Encryption algorithm (cid:61592) Encryption algorithm (cid:61592) Public key (cid:61592) Public key (cid:61592) Private key (cid:61592) Private key (cid:61592) Ciphertext (cid:61592) Ciphertext (cid:61592) Decryption algorithm (cid:61592) Decryption algorithm

(cid:49)(cid:51)

(cid:49)(cid:52)

(cid:49)(cid:53)

(cid:49)(cid:54)

(cid:49)(cid:55)

(cid:49)(cid:56)

(cid:61592) Brute-force attack (cid:61592) compute the private key given the public key (cid:61592) probable-message attack

(cid:49)(cid:57)

(cid:50)(cid:48)

(cid:50)(cid:49)

(cid:50)(cid:50)

Four possible approaches to attacking the RSA algorithm are Four possible approaches to attacking the RSA algorithm are (cid:61592) Brute force: This involves trying all possible private (cid:61592) Brute force: This involves trying all possible private

keys. keys.

(cid:61592) Mathematical attacks: There are several approaches, all (cid:61592) Mathematical attacks: There are several approaches, all to factoring the product of two to factoring the product of two

in effort in effort

equivalent equivalent primes. primes.

(cid:61592) Timing attacks: These depend on the running time of the (cid:61592) Timing attacks: These depend on the running time of the

decryption algorithm. decryption algorithm.

(cid:61592) Chosen ciphertext attacks: This type of attack exploits (cid:61592) Chosen ciphertext attacks: This type of attack exploits

properties of the RSA algorithm. properties of the RSA algorithm.

(cid:50)(cid:51)

(cid:50)(cid:52)

(cid:50)(cid:53)

(cid:61592) Diffie-Hellman Key Exchange (cid:61592) Diffie-Hellman Key Exchange (cid:61592) Elgamal Cryptographic System (cid:61592) Elgamal Cryptographic System (cid:61592) Elliptic Curve Arithmetic (cid:61592) Elliptic Curve Arithmetic (cid:61592) Elliptic Curve Cryptography (cid:61592) Elliptic Curve Cryptography (cid:61592) Pseudorandom Number Generation Based on an (cid:61592) Pseudorandom Number Generation Based on an

Asymmetric Cipher Asymmetric Cipher

(cid:50)(cid:57)

(cid:61592) A simple public-key algorithm is Diffie-Hellman key exchange. (cid:61592) A simple public-key algorithm is Diffie-Hellman key exchange. This protocol enables two users to establish a secret key using a This protocol enables two users to establish a secret key using a public-key scheme based on discrete logarithms. The protocol is public-key scheme based on discrete logarithms. The protocol is secure only if the authenticity of the two participants can be secure only if the authenticity of the two participants can be established. established.

(cid:61592) Elliptic curve arithmetic can be used to develop a variety of (cid:61592) Elliptic curve arithmetic can be used to develop a variety of including key including key

elliptic curve cryptography (ECC) schemes, elliptic curve cryptography (ECC) schemes, exchange, encryption, and digital signature. exchange, encryption, and digital signature.

(cid:61592) For purposes of ECC, elliptic curve arithmetic involves the use (cid:61592) For purposes of ECC, elliptic curve arithmetic involves the use of an elliptic curve equation defined over a finite field. The of an elliptic curve equation defined over a finite field. The coefficients and variables in the equation are elements of a finite coefficients and variables in the equation are elements of a finite field. Schemes using Zp and GF(2^m) have been developed. field. Schemes using Zp and GF(2^m) have been developed.

(cid:51)(cid:48)

(cid:51)(cid:49)

(cid:51)(cid:50)

(cid:51)(cid:51)

(cid:51)(cid:52)

(cid:61591) (cid:61590)

1. CRYPTOGRAPHIC HASH FUNCTIONS 2. MESSAGE AUTHENTICATION CODES 3. DIGITAL SIGNATURES

2

(cid:61592) Applications of Cryptographic Hash Functions (cid:61592) Applications of Cryptographic Hash Functions (cid:61592) Two Simple Hash Functions (cid:61592) Two Simple Hash Functions (cid:61592) Requirements and Security (cid:61592) Requirements and Security (cid:61592) Hash Functions Based on Cipher Block Chaining (cid:61592) Hash Functions Based on Cipher Block Chaining (cid:61592) Secure Hash Algorithm (SHA) (cid:61592) Secure Hash Algorithm (SHA) (cid:61592) SHA-3 (cid:61592) SHA-3

(cid:51)

(cid:61592) A hash function maps a variable-length message into a (cid:61592) A hash function maps a variable-length message into a

fixed-length hash value, or message digest. fixed-length hash value, or message digest.

(cid:61592) Virtually all cryptographic hash functions involve the (cid:61592) Virtually all cryptographic hash functions involve the

iterative use of a compression function. iterative use of a compression function.

(cid:61592) The compression function used in secure hash algorithms (cid:61592) The compression function used in secure hash algorithms falls into one of two categories: a function specifically falls into one of two categories: a function specifically designed for the hash function or an algorithm based on a designed for the hash function or an algorithm based on a are are symmetric block cipher. SHA and Whirlpool symmetric block cipher. SHA and Whirlpool examples of these two approaches, respectively. examples of these two approaches, respectively.

(cid:52)

(cid:61592) A hash function H accepts a variable-length block of data (cid:61592) A hash function H accepts a variable-length block of data as input and produces a fixed-size hash value h=H(M). A as input and produces a fixed-size hash value h=H(M). A “good” hash function has the property that the results of “good” hash function has the property that the results of applying the function to a large set of inputs will produce applying the function to a large set of inputs will produce outputs that are evenly distributed and apparently random. outputs that are evenly distributed and apparently random. (cid:61592) A cryptographic hash function is an algorithm for which it (cid:61592) A cryptographic hash function is an algorithm for which it is computationally infeasible (because no attack is is computationally infeasible (because no attack is significantly more efficient than brute force) to find either significantly more efficient than brute force) to find either (a) a data object that maps to a pre-specified hash result (a) a data object that maps to a pre-specified hash result (the one-way property) or (b) two data objects that map to (the one-way property) or (b) two data objects that map to the same hash result (the collision-free property). the same hash result (the collision-free property).

(cid:53)

(cid:54)

Message Authentication

(cid:61592) The message plus concatenated hash code is encrypted (cid:61592) The message plus concatenated hash code is encrypted using symmetric encryption. Because only A and B share using symmetric encryption. Because only A and B share the secret key, the message must have come from A and the secret key, the message must have come from A and has not been altered. The hash code provides the structure has not been altered. The hash code provides the structure or redundancy required to achieve authentication. Because or redundancy required to achieve authentication. Because encryption is applied to the entire message plus hash encryption is applied to the entire message plus hash code, confidentiality is also provided code, confidentiality is also provided

(cid:55)

(cid:61592) Only the hash code is encrypted, using symmetric encryption. This reduces the processing burden for those applications that do not require confidentiality.

(cid:56)

(cid:61592) It is possible to use a hash function but no encryption for (cid:61592) It is possible to use a hash function but no encryption for message authentication. The technique assumes that the two message authentication. The technique assumes that the two communicating parties share a common secret value S. A communicating parties share a common secret value S. A computes the hash value over the concatenation of M and S computes the hash value over the concatenation of M and S and appends the resulting hash value to M. Because B and appends the resulting hash value to M. Because B possesses S, it can recompute the hash value to verify. Because possesses S, it can recompute the hash value to verify. Because the secret value itself is not sent, an opponent cannot modify an the secret value itself is not sent, an opponent cannot modify an intercepted message and cannot generate a false message. intercepted message and cannot generate a false message.

(cid:57)

(cid:61592) Confidentiality can be added to the approach of method (c) by encrypting the entire message plus the hash code.

(cid:49)(cid:48)

(cid:49)(cid:49)

(cid:49)(cid:50)

(cid:61592) Message Authentication Requirements (cid:61592) Message Authentication Requirements (cid:61592) Message Authentication Functions (cid:61592) Message Authentication Functions (cid:61592) Requirements for Message Authentication Codes (cid:61592) Requirements for Message Authentication Codes (cid:61592) Security of MACs (cid:61592) Security of MACs (cid:61592) MACs Based on Hash Functions: HMAC (cid:61592) MACs Based on Hash Functions: HMAC (cid:61592) MACs Based on Block Ciphers: DAA and CMAC (cid:61592) MACs Based on Block Ciphers: DAA and CMAC (cid:61592) Authenticated Encryption: CCM and GCM (cid:61592) Authenticated Encryption: CCM and GCM (cid:61592) Pseudorandom Number Generation Using Hash Functions (cid:61592) Pseudorandom Number Generation Using Hash Functions

and Macs and Macs

(cid:49)(cid:51)

(cid:61592) Message authentication is a mechanism or service used to (cid:61592) Message authentication is a mechanism or service used to verify the integrity of a message. Message authentication verify the integrity of a message. Message authentication assures that data received are exactly as sent by (i.e., assures that data received are exactly as sent by (i.e., contain no modification, insertion, deletion, or replay) contain no modification, insertion, deletion, or replay) and that the purported identity of the sender is valid. and that the purported identity of the sender is valid.

(cid:61592) Symmetric encryption provides authentication among (cid:61592) Symmetric encryption provides authentication among

those who share the secret key. those who share the secret key.

(cid:49)(cid:52)

(cid:61592) A message authentication code (MAC) is an algorithm (cid:61592) A message authentication code (MAC) is an algorithm that requires the use of a secret key. A MAC takes a that requires the use of a secret key. A MAC takes a variable-length message and a secret key as input and variable-length message and a secret key as input and produces an authentication code. A recipient in possession produces an authentication code. A recipient in possession of the secret key can generate an authentication code to of the secret key can generate an authentication code to verify the integrity of the message. verify the integrity of the message.

(cid:61592) One means of (cid:61592) One means of

to combine a forming a MAC is to combine a forming a MAC is cryptographic hash function in some fashion with a secret cryptographic hash function in some fashion with a secret key. key.

(cid:61592) Another approach to constructing a MAC is to use a (cid:61592) Another approach to constructing a MAC is to use a symmetric block cipher in such a way that it produces a symmetric block cipher in such a way that it produces a fixed-length output for a variable-length input. fixed-length output for a variable-length input.

(cid:49)(cid:53)

1. Disclosure: Release of message contents to any person or 1. Disclosure: Release of message contents to any person or process not possessing the appropriate cryptographic process not possessing the appropriate cryptographic key. key.

2. Traffic analysis: Discovery of the pattern of traffic 2. Traffic analysis: Discovery of the pattern of traffic

between parties… between parties…

3. Masquerade: Insertion of messages into the network 3. Masquerade: Insertion of messages into the network

from a fraudulent source … from a fraudulent source …

4. Content modification: Changes to the contents of a 4. Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and message, including insertion, deletion, transposition, and modification. modification.

(cid:49)(cid:54)

5. Sequence modification: Any modification to a sequence 5. Sequence modification: Any modification to a sequence including insertion, including insertion,

of messages between parties, of messages between parties, deletion, and reordering. deletion, and reordering.

6. Timing modification: Delay or replay of messages. 6. Timing modification: Delay or replay of messages. 7. Source repudiation: Denial of transmission of message 7. Source repudiation: Denial of transmission of message

by source. by source.

8. Destination repudiation: Denial of receipt of message by 8. Destination repudiation: Denial of receipt of message by

destination. destination.

(cid:49)(cid:55)

(cid:61592) Hash function: A function that maps a message of any (cid:61592) Hash function: A function that maps a message of any length into a fixed-length hash value, which serves as the length into a fixed-length hash value, which serves as the authenticator. authenticator.

(cid:61592) Message encryption: The ciphertext of (cid:61592) Message encryption: The ciphertext of

the entire the entire

message serves as its authenticator. message serves as its authenticator.

(cid:61592) Message authentication code (MAC): A function of the (cid:61592) Message authentication code (MAC): A function of the message and a secret key that produces a fixed-length message and a secret key that produces a fixed-length value that serves as the authenticator. value that serves as the authenticator.

(cid:49)(cid:56)

(cid:49)(cid:57)

(cid:50)(cid:48)

(cid:50)(cid:49)

(cid:50)(cid:50)

(cid:61592) Brute-Force Attacks (cid:61592) Cryptanalysis

(cid:50)(cid:51)

(cid:50)(cid:52)

(cid:50)(cid:53)

(cid:50)(cid:54)

(cid:50)(cid:55)

(cid:50)(cid:56)

(cid:50)(cid:57)

(cid:61592) Digital Signatures (cid:61592) Digital Signatures (cid:61592) ElGamal Digital Signature Scheme (cid:61592) ElGamal Digital Signature Scheme (cid:61592) Schnorr Digital Signature Scheme (cid:61592) Schnorr Digital Signature Scheme (cid:61592) Digital Signature Standard (cid:61592) Digital Signature Standard

(cid:51)(cid:48)

(cid:61592) A digital signature is an authentication mechanism that (cid:61592) A digital signature is an authentication mechanism that enables the creator of a message to attach a code that acts enables the creator of a message to attach a code that acts as a signature. Typically the signature is formed by taking as a signature. Typically the signature is formed by taking the hash of the message and encrypting the message with the hash of the message and encrypting the message with the creator’s private key. The signature guarantees the the creator’s private key. The signature guarantees the source and integrity of the message. source and integrity of the message.

(cid:61592) The digital signature standard (DSS) is an NIST standard (cid:61592) The digital signature standard (DSS) is an NIST standard

that uses the secure hash algorithm (SHA). that uses the secure hash algorithm (SHA).

(cid:51)(cid:49)

(cid:51)(cid:50)

(cid:51)(cid:51)

(cid:51)(cid:52)

(cid:51)(cid:53)

(cid:51)(cid:54)

(cid:51)(cid:55)

(cid:51)(cid:56)

(cid:51)(cid:57)

(cid:52)(cid:48)

(cid:61591) (cid:61590)

1. KEY MANAGEMENT AND DISTRIBUTION 2. USER AUTHENTICATION

(cid:50)

(cid:61592) Symmetric Key Distribution Using Symmetric (cid:61592) Symmetric Key Distribution Using Symmetric

Encryption Encryption

(cid:61592) Symmetric Key Distribution Using Asymmetric (cid:61592) Symmetric Key Distribution Using Asymmetric

Encryption Encryption

(cid:61592) Distribution Of Public Keys (cid:61592) Distribution Of Public Keys (cid:61592) X.509 Certificates (cid:61592) X.509 Certificates (cid:61592) Public-Key Infrastructure (cid:61592) Public-Key Infrastructure

(cid:51)

(cid:61592) Key distribution is the function that delivers a key to two (cid:61592) Key distribution is the function that delivers a key to two parties who wish to exchange secure encrypted data. parties who wish to exchange secure encrypted data. Some sort of mechanism or protocol is needed to provide Some sort of mechanism or protocol is needed to provide for the secure distribution of keys. for the secure distribution of keys.

(cid:61592) Key distribution often involves the use of master keys, (cid:61592) Key distribution often involves the use of master keys, which are infrequently used and are long lasting, and which are infrequently used and are long lasting, and session keys, which are generated and distributed for session keys, which are generated and distributed for temporary use between two parties. temporary use between two parties.

(cid:61592) Public-key encryption schemes are secure only if the (cid:61592) Public-key encryption schemes are secure only if the authenticity of the public key is assured. A public-key authenticity of the public key is assured. A public-key certificate scheme provides the necessary security. certificate scheme provides the necessary security.

(cid:52)

(cid:61592) X.509 defines the format for public-key certificates. This (cid:61592) X.509 defines the format for public-key certificates. This

format is widely used in a variety of applications. format is widely used in a variety of applications.

(cid:61592) A public-key infrastructure (PKI) is defined as the set of (cid:61592) A public-key infrastructure (PKI) is defined as the set of hardware, software, people, policies, and procedures hardware, software, people, policies, and procedures needed to create, manage, store, distribute, and revoke needed to create, manage, store, distribute, and revoke digital certificates based on asymmetric cryptography. digital certificates based on asymmetric cryptography.

implementations make use of X.509 implementations make use of X.509

(cid:61592) Typically, PKI (cid:61592) Typically, PKI certificates. certificates.

(cid:53)

(cid:54)

(cid:55)

8

9

(cid:49)(cid:48)

(cid:49)(cid:49)

(cid:49)(cid:50)

(cid:61592) Several (cid:61592) Several

for for

been been

have have

proposed proposed

techniques techniques

the the distribution of public keys. Virtually all these proposals distribution of public keys. Virtually all these proposals can be grouped into the following general schemes: can be grouped into the following general schemes: o Public announcement o Public announcement o Publicly available directory o Publicly available directory o Public-key authority o Public-key authority o Public-key certificates o Public-key certificates

(cid:49)(cid:51)

(cid:49)(cid:52)

(cid:49)(cid:53)

(cid:49)(cid:54)

(cid:49)(cid:55)

(cid:61592) ITU-T recommendation X.509 is part of the X.500 series of (cid:61592) ITU-T recommendation X.509 is part of the X.500 series of recommendations that define a directory service. The directory recommendations that define a directory service. The directory is, in effect, a server or distributed set of servers that maintains is, in effect, a server or distributed set of servers that maintains information about users. The information a database of information about users. The information a database of includes a mapping from user name to network address, as includes a mapping from user name to network address, as well as other attributes and information about the users. well as other attributes and information about the users.

(cid:61592) X.509 defines a framework for the provision of authentication (cid:61592) X.509 defines a framework for the provision of authentication services by the X.500 directory to its users. Each certificate services by the X.500 directory to its users. Each certificate contains the public key of a user and is signed with the private contains the public key of a user and is signed with the private key of a trusted certification authority. In addition, X.509 key of a trusted certification authority. In addition, X.509 defines alternative authentication protocols based on the use of defines alternative authentication protocols based on the use of public-key certificates. public-key certificates.

(cid:49)(cid:56)

(cid:61592) X.509 is an important standard because the certificate structure (cid:61592) X.509 is an important standard because the certificate structure and authentication protocols defined in X.509 are used in a variety and authentication protocols defined in X.509 are used in a variety of contexts. For example, the X.509 certificate format is used in of contexts. For example, the X.509 certificate format is used in S/MIME, IP Security and SSL/TLS. X.509 was initially issued in S/MIME, IP Security and SSL/TLS. X.509 was initially issued in 1988. 1988.

a a

(cid:61592) X.509 is based on the use of public-key cryptography and digital (cid:61592) X.509 is based on the use of public-key cryptography and digital signatures. The standard does not dictate the use of a specific signatures. The standard does not dictate the use of a specific algorithm but recommends RSA. The dig-ital signature scheme is algorithm but recommends RSA. The dig-ital signature scheme is assumed to require the use of a hash function. Again, the standard assumed to require the use of a hash function. Again, the standard does not dictate specific hash algorithm. The 1988 specific hash algorithm. The 1988 does not dictate recommendation included the description of a recommended hash recommendation included the description of a recommended hash algorithm; this algorithm has since been shown to be insecure and algorithm; this algorithm has since been shown to be insecure and was dropped from the 1993 recommendation. was dropped from the 1993 recommendation.

(cid:49)(cid:57)

(cid:50)(cid:48)

(cid:50)(cid:49)

(cid:61592) Version: Differentiates among successive versions of the (cid:61592) Version: Differentiates among successive versions of the certificate format; the default is version 1. If the issuer certificate format; the default is version 1. If the issuer unique identifier or subject unique identifier are present, unique identifier or subject unique identifier are present, the value must be version 2. If one or more extensions are the value must be version 2. If one or more extensions are present, the version must be version 3. present, the version must be version 3.

together with together with

certificate certificate

any any

the the

(cid:61592) Serial number: An integer value unique within the issuing (cid:61592) Serial number: An integer value unique within the issuing CA that is unambiguously associated with this certificate. CA that is unambiguously associated with this certificate. (cid:61592) Signature algorithm identifier: The algorithm used to (cid:61592) Signature algorithm identifier: The algorithm used to sign associated associated sign parameters. Because this information is repeated in the parameters. Because this information is repeated in the signature field at the end of the certificate, this field has signature field at the end of the certificate, this field has little, if any, utility. little, if any, utility.

(cid:50)(cid:50)

(cid:61592) Issuer name: X.500 is the name of the CA that created (cid:61592) Issuer name: X.500 is the name of the CA that created

and signed this certificate. and signed this certificate.

(cid:61592) Period of validity: Consists of two dates: the first and (cid:61592) Period of validity: Consists of two dates: the first and

last on which the certificate is valid. last on which the certificate is valid.

is, is,

(cid:61592) Subject name: The name of the user to whom this (cid:61592) Subject name: The name of the user to whom this this certificate certifies the this certificate certifies the certificate refers. That certificate refers. That public key of the subject who holds the corresponding public key of the subject who holds the corresponding private key. private key.

to be used, to be used,

(cid:61592) Subject’s public-key information: The public key of the (cid:61592) Subject’s public-key information: The public key of the subject, plus an identifier of the algorithm for which this subject, plus an identifier of the algorithm for which this together with any associated together with any associated key is key is parameters. parameters.

(cid:50)(cid:51)

(cid:61592) Issuer unique identifier: An optional-bit string field used to (cid:61592) Issuer unique identifier: An optional-bit string field used to identify uniquely the issuing CA in the event the X.500 name identify uniquely the issuing CA in the event the X.500 name has been reused for different entities. has been reused for different entities.

(cid:61592) Subject unique identifier: An optional-bit string field used to (cid:61592) Subject unique identifier: An optional-bit string field used to identify uniquely the subject in the event the X.500 name has identify uniquely the subject in the event the X.500 name has been reused for different entities. been reused for different entities.

(cid:61592) Extensions: A set of one or more extension fields. Extensions (cid:61592) Extensions: A set of one or more extension fields. Extensions were added in version 3 and are discussed later in this section. were added in version 3 and are discussed later in this section. (cid:61592) Signature: Covers all of the other fields of the certificate; it (cid:61592) Signature: Covers all of the other fields of the certificate; it contains the hash code of the other fields encrypted with the contains the hash code of the other fields encrypted with the CA’s private key. This field includes the signature algorithm CA’s private key. This field includes the signature algorithm identifier. identifier.

(cid:50)(cid:52)

(cid:61592) RFC 2822 (Internet Security Glossary) defines public-key (cid:61592) RFC 2822 (Internet Security Glossary) defines public-key infrastructure (PKI) as the set of hardware, software, infrastructure (PKI) as the set of hardware, software, people, policies, and procedures needed to create, people, policies, and procedures needed to create, manage, store, distribute, and revoke digital certificates manage, store, distribute, and revoke digital certificates cryptography. The principal cryptography. The principal based on asymmetric based on asymmetric objective for developing a PKI is to enable secure, objective for developing a PKI is to enable secure, convenient, and efficient acquisition of public keys. The convenient, and efficient acquisition of public keys. The Internet Engineering Task Force (IETF) Public Key Internet Engineering Task Force (IETF) Public Key Infrastructure X.509 (PKIX) working group has been the Infrastructure X.509 (PKIX) working group has been the driving force behind setting up a formal (and generic) driving force behind setting up a formal (and generic) model based on X.509 that is suitable for deploying a model based on X.509 that is suitable for deploying a certificate-based architecture on the Internet. certificate-based architecture on the Internet.

(cid:50)(cid:53)

(cid:50)(cid:54)

(cid:61592) End entity: A generic term used to denote end users, (cid:61592) End entity: A generic term used to denote end users, devices (e.g., servers, routers), or any other entity that can devices (e.g., servers, routers), or any other entity that can field of a public key field of a public key be identified in the subject be identified in the subject certificate. End entities typically consume and/or support certificate. End entities typically consume and/or support PKI-related services. PKI-related services.

(cid:61592) Certification authority (CA): The issuer of certificates (cid:61592) Certification authority (CA): The issuer of certificates and (usually) certificate revocation lists (CRLs). It may and (usually) certificate revocation lists (CRLs). It may also support a variety of administrative functions, also support a variety of administrative functions, although these are often delegated to one or more although these are often delegated to one or more Registration Authorities. Registration Authorities.

(cid:50)(cid:55)

(cid:61592) Registration authority (RA): An optional component (cid:61592) Registration authority (RA): An optional component that can assume a number of administrative functions that can assume a number of administrative functions from the CA. The RA is often associated with the end from the CA. The RA is often associated with the end entity registration process but can assist in a number of entity registration process but can assist in a number of other areas as well. other areas as well.

(cid:61592) CRL issuer: An optional component (cid:61592) CRL issuer: An optional component

that a CA can that a CA can

delegate to publish CRLs. delegate to publish CRLs.

(cid:61592) Repository: A generic term used to denote any method (cid:61592) Repository: A generic term used to denote any method for storing certificates and CRLs so that they can be for storing certificates and CRLs so that they can be retrieved by end entities. retrieved by end entities.

(cid:50)(cid:56)

(cid:61592) Remote User-Authentication Principles (cid:61592) Remote User-Authentication Principles (cid:61592) Remote User-Authentication Using Symmetric (cid:61592) Remote User-Authentication Using Symmetric

Encryption Encryption

(cid:61592) Kerberos (cid:61592) Kerberos (cid:61592) Remote User Authentication Using Asymmetric (cid:61592) Remote User Authentication Using Asymmetric

Encryption Encryption

(cid:61592) Federated Identity Management (cid:61592) Federated Identity Management

(cid:50)(cid:57)

(cid:61592) Mutual authentication protocols enable communicating (cid:61592) Mutual authentication protocols enable communicating parties to satisfy themselves mutually about each other’s parties to satisfy themselves mutually about each other’s identity and to exchange session keys. identity and to exchange session keys.

(cid:61592) Kerberos is an authentication service designed for use in a (cid:61592) Kerberos is an authentication service designed for use in a

distributed environment. distributed environment.

(cid:61592) Kerberos provides a trusted third-party authentication (cid:61592) Kerberos provides a trusted third-party authentication service that enables clients and servers to establish service that enables clients and servers to establish authenticated communication. authenticated communication.

(cid:51)(cid:48)

(cid:61592) Identity management is a centralized, automated approach (cid:61592) Identity management is a centralized, automated approach to resources by to resources by

to provide enterprise-wide access to provide enterprise-wide access employees and other authorized individuals. employees and other authorized individuals.

(cid:61592) Identity federation is, in essence, an extension of identity (cid:61592) Identity federation is, in essence, an extension of identity

management to multiple security domains. management to multiple security domains.

(cid:51)(cid:49)

(cid:61592) The process of verifying an identity claimed by or for a (cid:61592) The process of verifying an identity claimed by or for a system entity. An authentication process consists of two system entity. An authentication process consists of two steps: steps:

(cid:61592) Identification step: Presenting an identifier (cid:61592) Identification step: Presenting an identifier

to the to the security system. (Identifiers should be assigned carefully, security system. (Identifiers should be assigned carefully, because authenticated identities are the basis for other because authenticated identities are the basis for other security services, such as access control service.) security services, such as access control service.)

(cid:61592) Verification step: Presenting or generating authentication (cid:61592) Verification step: Presenting or generating authentication information that corroborates the binding between the information that corroborates the binding between the entity and the identifier. entity and the identifier.

(cid:51)(cid:50)

(cid:61592) Something the (cid:61592) Something the

individual knows: Examples include a individual knows: Examples include a (PIN), or (PIN), or

identification number identification number

password, a personal password, a personal answers to a prearranged set of questions. answers to a prearranged set of questions.

(cid:61592) Something the individual possesses: Examples include (cid:61592) Something the individual possesses: Examples include cryptographic keys, electronic keycards, smart cards, and cryptographic keys, electronic keycards, smart cards, and physical keys. This type of authenticator is referred to as a physical keys. This type of authenticator is referred to as a token. token.

(cid:61592) Something the individual is (static biometrics): Examples (cid:61592) Something the individual is (static biometrics): Examples

include recognition by fingerprint, retina, and face. include recognition by fingerprint, retina, and face.

(cid:61592) Something the individual does (dynamic biometrics): (cid:61592) Something the individual does (dynamic biometrics): Examples include recognition by voice pattern, handwriting Examples include recognition by voice pattern, handwriting characteristics, and typing rhythm. characteristics, and typing rhythm.

(cid:51)(cid:51)

are are

exchange exchange

authenticated authenticated

two two

(cid:61592) An important application area is that of mutual authentication (cid:61592) An important application area is that of mutual authentication protocols. Such protocols enable communicating parties to satisfy protocols. Such protocols enable communicating parties to satisfy themselves mutually about each other’s identity and to exchange themselves mutually about each other’s identity and to exchange session keys. There, the focus was key distribution. Central to the session keys. There, the focus was key distribution. Central to the issues: key problem of issues: key problem of confidentiality and timeliness. To prevent masquerade and to confidentiality and timeliness. To prevent masquerade and to prevent compromise of session keys, essential identification and prevent compromise of session keys, essential identification and session-key information must be communicated in encrypted form. session-key information must be communicated in encrypted form. This requires the prior existence of secret or public keys that can be This requires the prior existence of secret or public keys that can be used for this purpose. The second issue, timeliness, is important used for this purpose. The second issue, timeliness, is important because of the threat of message replays. Such replays, at worst, because of the threat of message replays. Such replays, at worst, to compromise a session key or could allow an opponent to compromise a session key or could allow an opponent successfully impersonate another party. At minimum, a successful successfully impersonate another party. At minimum, a successful replay can disrupt operations by presenting parties with messages replay can disrupt operations by presenting parties with messages that appear genuine but are not. that appear genuine but are not.

(cid:51)(cid:52)

(cid:61592) [GONG93] lists the following examples of replay attacks: (cid:61592) [GONG93] lists the following examples of replay attacks: (cid:61592) Simple replay: The opponent simply copies a message and replays it (cid:61592) Simple replay: The opponent simply copies a message and replays it

later later

(cid:61592) Repetition that can be logged: An opponent can replay a times (cid:61592) Repetition that can be logged: An opponent can replay a times

tamped message within the valid time window. tamped message within the valid time window.

(cid:61592) Repetition that cannot be detected: This situation could arise (cid:61592) Repetition that cannot be detected: This situation could arise because the original message could have been suppressed and thus because the original message could have been suppressed and thus did not arrive at its destination; only the replay message arrives. did not arrive at its destination; only the replay message arrives.

(cid:61592) Backward replay without modification: This is a replay back to the (cid:61592) Backward replay without modification: This is a replay back to the message sender. This attack is possible if symmetric encryption is message sender. This attack is possible if symmetric encryption is used and the sender cannot easily recognize the difference between used and the sender cannot easily recognize the difference between messages sent and messages received on the basis of content. messages sent and messages received on the basis of content.

(cid:51)(cid:53)

this: Assume this: Assume

open open

is is

(cid:61592) Kerberos4 is an authentication service developed as part (cid:61592) Kerberos4 is an authentication service developed as part of Project Athena at MIT. The problem that Kerberos of Project Athena at MIT. The problem that Kerberos distributed distributed an an addresses addresses in which users at workstations wish to in which users at workstations wish to environment environment access services on servers distributed access services on servers distributed throughout the network. throughout the network.

(cid:51)(cid:54)

(cid:51)(cid:55)

(cid:51)(cid:56)

(cid:51)(cid:57)

(cid:52)(cid:48)

(cid:52)(cid:49)

(cid:52)(cid:50)

(cid:52)(cid:51)