use of cryptographic algorithms

An important element in many computer security services and applications is the
use of cryptographic algorithms. This chapter provides an overview of the various types of algorithms, together with a discussion of their applicability. For each type of algorithm, we introduce the most important standardized algorithms in common use. For the technical details of the algorithms themselves, see Part Four. We begin with symmetric encryption, which is used in the widest variety of contexts, primarily to provide confidentiality. Next, we examine secure hash functions and discuss their use in message authentication. The next section examines public-key encryption, also known as asymmetric encryption. We then discuss the two most important applications of public-key encryption, namely digital signatures and key management. In the case of digital signatures, asymmetric encryption and secure hash functions are combined to produce an extremely useful tool. Finally, in this chapter we provide an example of an application area for cryptographic algorithms by looking at the encryption of stored data. Cryptography

Crypto as Black Box A generic view plaintext encrypt decrypt plaintext
key key plaintext encrypt decrypt plaintext ciphertext A generic view Part 1  Cryptography

Basic Terminology plaintext - the original message
ciphertext - the coded message cipher - algorithm for transforming plaintext to ciphertext key - info used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - converting ciphertext to plaintext  (knowing the key) cryptography - study of encryption principles/methods cryptanalysis (code breaking) - the study of principles/ methods of deciphering ciphertext without knowing key cryptology - the field of both cryptography and cryptanalysis Briefly review some terminology used throughout the course. In other words: Cryptology  The art and science of making and breaking “secret codes” Cryptography  making “secret codes” Cryptanalysis  breaking “secret codes” Crypto  all of the above (and more)

Crypto Basic assumptions This is known as Kerckhoffs’ Principle
The system is completely known to the attacker Only the key is secret That is, crypto algorithms are not secret  This is known as Kerckhoffs’ Principle Why do we make such an assumption? Experience has shown that secret algorithms tend to be weak when exposed Secret algorithms never remain secret Better to find weaknesses beforehand Part 1  Cryptography

Encryption/Decryption Process
The basic process of encrypting and then decrypting data. From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: ). Copyright 2015 by Pearson Education, Inc. All rights reserved.

Symmetric vs. Asymmetric
Same Key Different Keys The critical difference between symmetric and asymmetric is that symmetric uses a single key for both encryption and decryption, whereas asymmetric uses complementary keys. From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: ). Copyright 2015 by Pearson Education, Inc. All rights reserved.

Stream Ciphers In stream ciphers, each byte of the data stream is encrypted separately. This is as opposed to block ciphers, which are shown on the next slide. From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: ). Copyright 2015 by Pearson Education, Inc. All rights reserved.

Block Ciphers Unlike a stream cipher, a block cipher encrypts a group of plaintext symbols as a single block. The pros and cons of each model are discussed on the next slide. From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: ). Copyright 2015 by Pearson Education, Inc. All rights reserved.

Block & Stream Ciphers Block Cipher Stream Cipher
Processes the input one block of elements at a time Produces an output block for each input block Can reuse keys More common Block Cipher Processes the input elements continuously Produces output one element at a time Primary advantage is that they are almost always faster and use far less code Encrypts plaintext one byte at a time Pseudorandom stream is one that is unpredictable without knowledge of the input key Stream Cipher A block cipher processes the input one block of elements at a time, producing an output block for each input block. A stream cipher processes the input elements continuously, producing output one element at a time, as it goes along. Although block ciphers are far more common, there are certain applications in which a stream cipher is more appropriate. Examples are given subsequently in this book. A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time. With a properly designed pseudorandom number generator, a stream cipher can be as secure as block cipher of comparable key length. The primary advantage of a stream cipher is that stream ciphers are almost always faster and use far less code than do block ciphers. The advantage of a block cipher is that you can reuse keys. For applications that require encryption/decryption of a stream of data, such as over a data communications channel or a browser/Web link, a stream cipher might be the better alternative. For applications that deal with blocks of data, such as file transfer, , and database, block ciphers may be more appropriate. However, either type of cipher can be used in virtually any application.

Cryptographic Primitives
Substitution One set of bits is exchanged for another Transposition Rearranging the order of the ciphertext to break any repeating patterns in the underlying plaintext Confusion An algorithm providing good confusion has a complex functional relationship between the plaintext/key pair and the ciphertext, so that changing one character in the plaintext causes unpredictable changes to the resulting ciphertext Diffusion Distributes the information from single plaintext characters over the entire ciphertext output, so that even small changes to the plaintext result in broad changes to the ciphertext These are the basic techniques that make up cryptographic algorithms. As we study some algorithms in depth later in the chapter, we’ll see these again and again. The first two—substitution and transposition—are simple mathematical operations used within complex cryptosystems. The latter two—confusion and diffusion—are more conceptual and may be accomplished in a number of different ways depending on the cryptographic algorithm. From Security in Computing, Fifth Edition, by Charles P. Pfleeger, et al. (ISBN: ). Copyright 2015 by Pearson Education, Inc. All rights reserved.

Classification of Cryptography
Number of keys used Secret key cryptography: one key Public key cryptography: two keys – (public, private) Type of encryption operations used substitution / transposition / product Way in which plaintext is processed block / stream

Cryptanalysis Scheme Ciphertext only – only know algorithm / ciphertext, statistical, can identify plaintext Known plaintext – know/suspect/guess 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

Unconditional vs. Computational Security
Unconditional security No matter how much computer power is available  the cipher cannot be broken The ciphertext provides insufficient information to uniquely determine the corresponding plaintext Only one-time pad scheme qualifies (one-time pre-shared key) Computational security Cost of breaking the cipher exceeds the value of the encrypted info Time required to break the cipher exceeds the useful lifetime of the info (either takes too long, or is too expensive) Unconditional security would be nice, but the only known such cipher is the one-time pad (later). For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher.

Brute Force Search Always possible to simply try every key !!!
Most basic attack, proportional to key size Assume either know / recognise plaintext

Classical Substitution Ciphers
Letters of plaintext are replaced by other letters or by numbers or symbols Plaintext is viewed as a sequence of bits, then substitution replaces plaintext bit patterns with ciphertext bit patterns In this section and the next, we examine a sampling of what might be called classical encryption techniques. A study of these techniques enables us to illustrate the basic approaches to symmetric encryption used today and the types of cryptanalytic attacks that must be anticipated. The two basic building blocks of all encryption techniques: substitution and transposition. We examine these in the next two sections. Finally, we discuss a system that combine both substitution and transposition.

Caesar Cipher Simplest and earliest known use of a substitution cipher
Used by Julius Caesar Involves replacing each letter of the alphabet with the letter standing three places further down the alphabet For example, when key=3 Replaces each letter by 3rd letter on Alphabet is wrapped around so that the letter following Z is A Example: plain: meet me after the toga party cipher: PHHW PH DIWHU WKH WRJD SDUWB Substitution ciphers form the first of the fundamental building blocks. The core idea is to replace one basic unit (letter/byte) with another. Whilst the early Greeks described several substitution ciphers, the first attested use in military affairs of one was by Julius Caesar, described by him in Gallic Wars (cf. Kahn pp83-84). Still call any cipher using a simple letter shift a caesar cipher, not just those with shift 3. Note: when letters are involved, the following conventions are used in this course: Plaintext is always in lowercase; ciphertext is in uppercase; key values are in italicized lowercase.

Caesar Cipher Define transformation as:
a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Mathematically give each letter a number a b c d e f g h i j k l m n o p q r s t u v w x y Z Then have Caesar cipher as: C = E(p) = (p + k) mod (26) p = D(C) = (C – k) mod (26) This mathematical description uses modulo arithmetic (ie clock arithmetic). Here, when you reach Z you go back to A and start again. Mod 26 implies that when you reach 26, you use 0 instead (ie the letter after Z, or goes to A or 0). Example: howdy (7,14,22,3,24) encrypted using key f (5) is MTBID

Brute-Force Cryptanalysis of Caesar Cipher
Figure 3.3 Brute-Force Cryptanalysis of Caesar Cipher (This chart can be found on page 75 in the textbook) If it is known that a given ciphertext is a Caesar cipher, then a brute-force cryptanalysis is easily performed: simply try all the 25 possible keys. Figure 3.3 shows the results of applying this strategy to the example ciphertext. In this case, the plaintext leaps out as occupying the third line. Three important characteristics of this problem enabled us to use a brute-force cryptanalysis: 1. The encryption and decryption algorithms are known. 2. There are only 25 keys to try. 3. The language of the plaintext is known and easily recognizable. © 2017 Pearson Education, Ltd., All rights reserved.

English Letter Frequencies
This graph is based on counts done at ADFA in the late 1980's, and used to develop the tables published in Seberry & Pieprzyk [SEBE89]. Note that all human languages have varying letter frequencies, though the number of letters and their frequencies varies. Seberry & Pieprzyk [SEBE89] Appendix A has graphs for 20 languages (most European & Japanese & Malay).

Example Cryptanalysis
Given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ Count relative letter frequencies (see text) Guess P & Z are e and t Guess ZW is th and hence ZWP is the Proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

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 Transposition Ciphers form the second basic building block of ciphers. The core idea is to rearrange the order of basic units (letters/bytes/bits) without altering their actual values.

Rail Fence cipher (zigzag cipher)
Write message letters out diagonally over a number of rows Then read off cipher row by row E.g., write message out as: m e m a t r h t g p r y e t e f e t e o a a t Giving ciphertext: (key=2) MEMATRHTGPRYETEFETEOAAT Example message is: "meet me after the toga party" with a rail fence of depth 2.

Product Ciphers Ciphers using substitutions or transpositions are not secure because of language characteristics Hence consider using several ciphers in succession to make it harder, but: Two substitutions make a more complex substitution Two transpositions make more complex transposition But a substitution followed by a transposition makes a new much harder cipher This is the bridge from classical to modern ciphers

Symmetric Encryption The universal technique for providing confidentiality for transmitted or stored data Also referred to as conventional encryption or single-key encryption Two requirements for secure use: Need a strong encryption algorithm Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure The universal technique for providing confidentiality for transmitted or stored data is symmetric encryption. This section introduces the basic concept of symmetric encryption. This is followed by an overview of the two most important symmetric encryption algorithms: the Data Encryption Standard (DES) and the Advanced Encryption Standard (AES), which are block encryption algorithms. Finally, this section introduces the concept of symmetric stream encryption algorithms. Symmetric encryption, also referred to as conventional encryption or single-key encryption, was the only type of encryption in use prior to the introduction of public-key encryption in the late 1970s. Countless individuals and groups, from Julius Caesar to the German U-boat force to present-day diplomatic, military, and commercial users, have used symmetric encryption for secret communication. It remains the more widely used of the two types of encryption. There are two requirements for secure use of symmetric encryption: 1. We need a strong encryption algorithm. At a minimum, we would like the algorithm to be such that an opponent who knows the algorithm and has access to one or more ciphertexts would be unable to decipher the ciphertext or figure out the key. This requirement is usually stated in a stronger form: The opponent should be unable to decrypt ciphertext or discover the key even if he or she is in possession of a number of ciphertexts together with the plaintext that produced each ciphertext. 2. Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable.

A symmetric encryption scheme has five ingredients (Figure 2.1):
• Plaintext: This is the original message or data that is fed into the algorithm as input. • Encryption algorithm: The encryption algorithm performs various substitutions and transformations on the plaintext. • Secret key: The secret key is also input to the encryption algorithm. The exact substitutions and transformations performed by the algorithm depend on the key. • Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the secret key. For a given message, two different keys will produce two different ciphertexts. • Decryption algorithm: This is essentially the encryption algorithm run in reverse. It takes the ciphertext and the secret key and produces the original plaintext.

Attacking Symmetric Encryption Two Different Approaches
1) Cryptanalytic Attacks 2) Brute-Force Attack Rely on: Nature of the algorithm Some knowledge of the general characteristics of the plaintext Some sample plaintext- ciphertext pairs Exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or the key being used If successful all future and past messages encrypted with that key are compromised Try all possible keys on some ciphertext until an intelligible translation into plaintext is obtained On average half of all possible keys must be tried to achieve success There are two general approaches to attacking a symmetric encryption scheme. The first attack is known as cryptanalysis. Cryptanalytic attacks rely on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext-ciphertext pairs. This type of attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used. If the attack succeeds in deducing the key, the effect is catastrophic: All future and past messages encrypted with that key are compromised. The second method, known as the brute-force attack, is to try every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average, half of all possible keys must be tried to achieve success.

Comparison of Three Popular Symmetric Encryption Algorithms
The most commonly used symmetric encryption algorithms are block ciphers. A block cipher processes the plaintext input in fixed-size blocks and produces a block of ciphertext of equal size for each plaintext block. The algorithm processes longer plaintext amounts as a series of fixed-size blocks. The most important symmetric algorithms, all of which are block ciphers, are the Data Encryption Standard (DES), triple DES, and the Advanced Encryption Standard (AES); see Table This subsection provides an overview of these algorithms. Chapter 20 presents the technical details. Table 2.1

Data Encryption Standard (DES)
The most widely used encryption scheme FIPS PUB 46 (Federal Information Processing Standards) Referred to as the Data Encryption Algorithm (DEA) Uses 64 bit plaintext block and 56 bit key to produce a 64 bit ciphertext block Strength concerns: Concerns about algorithm DES is the most studied encryption algorithm in existence Use of 56-bit key (serious concern ) Electronic Frontier Foundation (EFF) announced in July 1998 that it had broken a DES encryption The most widely used encryption scheme is based on the Data Encryption Standard (DES) adopted in 1977 by the National Bureau of Standards, now the National Institute of Standards and Technology (NIST), as Federal Information Processing Standard 46 (FIPS PUB 46). The algorithm itself is referred to as the Data Encryption Algorithm (DEA). DES takes a plaintext block of 64 bits and a key of 56 bits, to produce a ciphertext block of 64 bits. Concerns about the strength of DES fall into two categories: concerns about the algorithm itself and concerns about the use of a 56-bit key. The first concern refers to the possibility that cryptanalysis is possible by exploiting the characteristics of the DES algorithm. Over the years, there have been numerous attempts to find and exploit weaknesses in the algorithm, making DES the most-studied encryption algorithm in existence. Despite numerous approaches, no one has so far reported a fatal weakness in DES. A more serious concern is key length. With a key length of 56 bits, there are 256 possible keys, which is approximately 7.2 * 1016 keys. Thus, on the face of it, a brute-force attack appears impractical. Assuming that, on average, half the key space has to be searched, a single machine performing one DES encryption per micro second would take more than a thousand years (see Table 2.1) to break the cipher. However, the assumption of one encryption per microsecond is overly conservative. DES finally and definitively proved insecure in July 1998, when the Electronic Frontier Foundation (EFF) announced that it had broken a DES encryption using a special-purpose “DES cracker” machine that was built for less than $250,000. The attack took less than three days. The EFF has published a detailed description of the machine, enabling others to build their own cracker [EFF98]. And, of course, hardware prices will continue to drop as speeds increase, making DES virtually worthless. It is important to note that there is more to a key-search attack than simply running through all possible keys. Unless known plaintext is provided, the analyst must be able to recognize plaintext as plaintext. If the message is just plain text in English, then the result pops out easily, although the task of recognizing English would have to be automated. If the text message has been compressed before encryption, then recognition is more difficult. And if the message is some more general type of data, such as a numerical file, and this has been compressed, the problem becomes even more difficult to automate. Thus, to supplement the brute-force approach, some degree of knowledge about the expected plaintext is needed, and some means of automatically distinguishing plaintext from garble is also needed. The EFF approach addresses this issue as well and introduces some automated techniques that would be effective in many contexts. A final point: If the only form of attack that could be made on an encryption algorithm is brute force, then the way to counter such attacks is obvious: Use longer keys. To get some idea of the size of key required, let us use the EFF cracker as a basis for our estimates. The EFF cracker was a prototype and we can assume that with today’s technology, a faster machine is cost effective. If we assume that a cracker can perform 1 million decryptions per μs, which is the rate used in Table 2.1, then a DES code would take about 10 hours to crack. This is a speed-up of approximately a factor of 7 compared to the EFF result

Average Time Required for Exhaustive Key Search (brute force approach)
Table 2.2 shows how much time is required for a brute-force attack for various key sizes. As can be seen, a single PC can break DES in about a year; if multiple PCs work in parallel, the time is drastically shortened. And today’s supercomputers should be able to find a key in about an hour. Key sizes of 128 bits or greater are effectively unbreakable using simply a brute-force approach. Even if we managed to speed up the attacking system by a factor of 1 trillion (1012 ), it would still take over 100,000 years to break a code using a 128-bit key. Table 2.2

Triple DES (3DES) Repeats basic DES algorithm three times using either two or three unique keys First standardized for use in financial applications in ANSI standard X9.17 in 1985 Attractions: 168-bit key length overcomes the vulnerability to brute-force attack of DES 3DES requires three times as many calculations as DES Underlying encryption algorithm is the same as in DES Drawbacks: Algorithm is sluggish in software Uses a 64-bit block size The life of DES was extended by the use of triple DES (3DES), which involves repeating the basic DES algorithm three times, using either two or three unique keys, for a key size of 112 or 168 bits. Triple DES (3DES) was first standardized for use in financial applications in ANSI standard X9.17 in 1985. 3DES was incorporated as part of the Data Encryption Standard in 1999, with the publication of FIPS PUB 46-3. 3DES has two attractions that assure its widespread use over the next few years. First, with its 168-bit key length, it overcomes the vulnerability to brute-force attack of DES. Second, the underlying encryption algorithm in 3DES is the same as in DES. This algorithm has been subjected to more scrutiny than any other encryption algorithm over a longer period of time, and no effective cryptanalytic attack based on the algorithm rather than brute force has been found. Accordingly, there is a high level of confidence that 3DES is very resistant to cryptanalysis. If security were the only consideration, then 3DES would be an appropriate choice for a standardized encryption algorithm for decades to come. The principal drawback of 3DES is that the algorithm is relatively sluggish in software. The original DES was designed for mid-1970s hardware implementation and does not produce efficient software code. 3DES, which requires three times as many calculations as DES, is correspondingly slower. A secondary drawback is that both DES and 3DES use a 64-bit block size. For reasons of both efficiency and security, a larger block size is desirable.

DES vs. Double DES vs. 3DES K P C E DES Key Space: 256 K1 P X E
Double DES or 2DES K2 C Key Space: 256 * 256 K1 P X1 E Triple DES or 3DES K2 X2 K3 C Key Space: 256 * 256 * 256 K1 P X1 E Triple DES or 3DES, also K2 X2 D C Key Space: 256 * 256

Meet In The Middle (MITM) Attack
Double DES (2DES) is supposed to give 112-bit key length. E( E(P,K1), K2 ) and D( D(P,K1), K2 ) 256 * 256 = 2112,key space (possible keys) Instead, attackers may end up trying 257, how come? Thus, double encryption is not that significant in terms of added security, but why? K1 P X E Double DES: Encryption K2 C K2 C X D Double DES: Decryption K1 P

Advanced Encryption Standard (AES)
Needed a replacement for 3DES 3DES was not reasonable for long term use NIST called for proposals for a new AES in 1997 Should have a security strength equal to or better than 3DES Significantly improved efficiency Symmetric block cipher 128 bit data and 128/192/256 bit keys Selected Rijndael in November 2001 Published as FIPS 197 Because of its drawbacks, 3DES is not a reasonable candidate for long-term use. As a replacement, NIST in 1997 issued a call for proposals for a new Advanced Encryption Standard (AES), which should have a security strength equal to or better than 3DES and significantly improved efficiency. In addition to these general requirements, NIST specified that AES must be a symmetric block cipher with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits. Evaluation criteria included security, computational efficiency, memory requirements, hardware and software suitability, and flexibility. In a first round of evaluation, 15 proposed algorithms were accepted. A second round narrowed the field to 5 algorithms. NIST completed its evaluation process and published a final standard (FIPS PUB 197) in November of NIST selected Rijndael as the proposed AES algorithm. AES is now widely available in commercial products. AES is described in detail in Chapter 20.

Practical Security Issues
Typically symmetric encryption is applied to a unit of data larger than a single 64-bit or 128-bit block Electronic CodeBook (ECB) mode is the simplest approach to multiple-block encryption Each block of plaintext is encrypted using the same key Cryptanalysts may be able to exploit regularities in the plaintext, but how can we prevent such an attack? Modes of operation Alternative techniques developed to increase the security of symmetric block encryption for large sequences Overcomes the weaknesses of ECB Typically, symmetric encryption is applied to a unit of data larger than a single 64-bit or 128-bit block. messages, network packets, database records, and other plaintext sources must be broken up into a series of fixed-length block for encryption by a symmetric block cipher. The simplest approach to multiple-block encryption is known as electronic codebook (ECB) mode, in which plaintext is handled b bits at a time and each block of plaintext is encrypted using the same key. Typically b =64 or b =128 For lengthy messages, the ECB mode may not be secure. A cryptanalyst may be able to exploit regularities in the plaintext to ease the task of decryption. For example, if it is known that the message always starts out with certain predefined fields, then the cryptanalyst may have a number of known plaintext-ciphertext pairs to work with. To increase the security of symmetric block encryption for large sequences of data, a number of alternative techniques have been developed, called modes of operation. These modes overcome the weaknesses of ECB; each mode has its own particular advantages. This topic is explored in Chapter 20.

Block Cipher Modes Using a stream cipher is easy—you generate a keystream that is the same length as the plaintext (or ciphertext) and XOR. Using a block cipher is also easy, provided that you have exactly one block to encrypt. But how should multiple blocks be encrypted with a block cipher? It turns out that the answer is not as straightforward as it might seem. How to encrypt multiple blocks? Do we need a new key for each block? If so, as impractical as a One-Time Pad! Encrypt each block independently? Part 1  Cryptography

Block Cipher: Modes of Operation
Many modes  we discuss 3 most popular Electronic Codebook (ECB) mode Encrypt each block independently Most obvious approach, but a bad idea, (we will see why ?) Cipher Block Chaining (CBC) mode Chain the blocks together More secure than ECB, virtually no extra work Counter Mode (CTR) mode Block ciphers acts like a stream cipher Popular for random access Part 1  Cryptography

ECB: Electronic Codebook
the same key is used for all blocks Figure 2.2a shows the ECB mode. A plaintext of length nb is divided into n b-bit blocks (P1, P2,….,Pn). Each block is encrypted using the same algorithm and the same encryption key, to produce a sequence of n b-bit blocks of ciphertext (C1, C2,….,Cn). For lengthy messages, the ECB mode may not be secure. A cryptanalyst may be able to exploit regularities in the plaintext to ease the task of decryption. For example, if it is known that the message always starts out with certain predefined fields, then the cryptanalyst may have a number of known plaintext-ciphertext pairs with which to work. To increase the security of symmetric block encryption for large sequences of data, a number of alternative techniques have been developed, called modes of operation . These modes overcome the weaknesses of ECB; each mode has its own particular advantages. In a stream cipher structure, the key is input to a pseudorandom bit generator that produces a stream of 8-bit numbers that are apparently random. A pseudorandom stream is one that is unpredictable without knowledge of the input key and which has an apparently random character (see Section 2.5). The output of the generator, called a keystream, is combined one byte at a time with the plaintext stream using the bitwise exclusive- OR (XOR) operation.

ECB: Electronic Codebook Mode
Notation: C = E(P, K) Given plaintext P0, P1, …, Pm, … Most obvious way to use a ECB block cipher: Encrypt Decrypt C0 = E(P0, K) P0 = D(C0, K) C1 = E(P1, K) P1 = D(C1, K) C2 = E(P2, K) … P2 = D(C2, K) … An attacker might observes that Ci = Cj. Then the attacker knows that Pi = Pj. This gives some information, even if Pi or Pj are unknown, and if Pi is known then now is Pj Although this may seem innocent enough, there are cases where the attacker will know part of the plaintext, and any match with a known block reveals another block. This approach works, but there are serious security issues with ECB mode and, as a result, it should never be used in practice. Suppose ECB mode is used, and an attacker observes that Ci = Cj. Then the attacker knows that Pi = Pj. Although this may seem innocent enough, there are cases where the attacker will know part of the plaintext, and any match with a known block reveals another block. But even if the attacker does not know Pi or Pj, some information has been revealed, namely, that these two plaintext blocks are the same, and we don't want to give the cryptanalyst anything for free—especially if there is an easy way to avoid it. Part 1  Cryptography

ECB: Electronic Codebook
Simplest mode Plaintext is handled b-bit (block) at a time and each block is encrypted using the same key “Codebook” is used because there is a unique ciphertext for every b-bit block of plaintext Not secure for long messages since repeated plaintext is seen in repeated ciphertext this is a serious security issues and it should never be used in practice. To overcome security deficiencies: you need a technique where the same plaintext block, if repeated, produces different ciphertext blocks ?? The simplest way to proceed is what is known as electronic codebook (ECB) mode, in which plaintext is handled b bits at a time and each block of plaintext is encrypted using the same key ( Figure 2.3a ). The term codebook is used because, for a given key, there is a unique ciphertext for every b -bit block of plaintext. Therefore, one can imagine a gigantic codebook in which there is an entry for every possible b -bit plaintext pattern showing its corresponding ciphertext. With ECB, if the same b -bit block of plaintext appears more than once in the message, it always produces the same ciphertext. Because of this, for lengthy messages, the ECB mode may not be secure. If the message is highly structured, it may be possible for a cryptanalyst to exploit these regularities. For example, if it is known that the message always starts out with certain predefined fields, then the cryptanalyst may have a number of known plaintext-ciphertext pairs to work with. If the message has repetitive elements, with a period of repetition a multiple of b bits, then these elements can be identified by the analyst. This may help in the analysis or may provide an opportunity for substituting or rearranging blocks. To overcome the security deficiencies of ECB, we would like a technique in which the same plaintext block, if repeated, produces different ciphertext blocks.

Alice Hates ECB Mode Alice’s uncompressed image, and ECB encrypted
Why does this happen? Same plaintext yields same ciphertext! Part 1  Cryptography

CBC: Cipher Block Chaining Mode
Blocks are “chained” together A random Initialization Vector (IV) is required to start with the CBC mode IV is random, but not secret Encryption Decryption C0 = E(IV  P0, K), P0 = IV  D(C0, K), C1 = E(C0  P1, K), P1 = C0  D(C1, K), C2 = E(C1  P2, K),… P2 = C1  D(C2, K),… Analogous to classic codebook with additive Part 1  Cryptography

In the cipher block chaining (CBC) mode (Figure 20
In the cipher block chaining (CBC) mode (Figure 20.7), the input to the encryption algorithm is the XOR of the current plaintext block and the preceding ciphertext block; the same key is used for each block. In effect, we have chained together the processing of the sequence of plaintext blocks. The input to the encryption function for each plaintext block bears no fixed relationship to the plaintext block. Therefore, repeating patterns of b bits are not exposed. For decryption, each cipher block is passed through the decryption algorithm. The result is XORed with the preceding ciphertext block to produce the plaintext block. To see that this works, we can write: Cj = E(K, [Cj–1  Pj]) where E[K, X] is the encryption of plaintext X using key K, and  is the exclusive-OR operation. To produce the first block of ciphertext, an initialization vector (IV) is XORed with the first block of plaintext. On decryption, the IV is XORed with the output of the decryption algorithm to recover the first block of plaintext. The IV must be known to both the sender and receiver. For maximum security, the IV should be protected as well as the key. This could be done by sending the IV using ECB encryption. One reason for protecting the IV is as follows: If an opponent is able to fool the receiver into using a different value for IV, then the opponent is able to invert selected bits in the first block of plaintext.

CBC: Cipher Block Chaining Mode
Pros: Using the CBC, identical plaintext blocks yield different ciphertext blocks  this is very good! But what about errors in transmission (error propagation)? Suppose the ciphertext block Ci is garbled to, say, G  Ci . Then Pi  D(G, K) Ci-1 and Pi+1  D(Ci+1, K) G But Pi+2 = D(Ci+2,K)  Ci+1, … However, all subsequent blocks are decrypted correctly. That is, each plaintext block only depends on two consecutive ciphertext blocks, so errors do not propagate beyond two blocks. But, the fact that a single-bit error can cause two entire blocks to be garbled is a serious concern in high error-rate environments such as wireless. Stream ciphers do not have this problem—a single garbled ciphertext bit results in a single garbled plaintext bit—and that is one reason why stream ciphers are often preferred in wireless applications Garbled: a 0 bit could become 1 or vice versa Part 1  Cryptography

Alice Likes CBC Mode Alice’s uncompressed image, Alice CBC encrypted
Why does this happen? Same plaintext yields different ciphertext! Part 1  Cryptography

CTR: Counter Mode CTR is popular for random access
Use block cipher like a stream cipher Encryption Decryption C0 = P0  E(IV, K), P0 = C0  E(IV, K), C1 = P1  E(IV+1, K), P1 = C1  E(IV+1, K), C2 = P2  E(IV+2, K),… P2 = C2  E(IV+2, K),… Part 1  Cryptography

Although interest in the counter mode (CTR) has increased recently, with applications
to ATM (asynchronous transfer mode) network security and IPSec (IP security), this mode was proposed early on (e.g., [DIFF79]). Figure 20.9 depicts the CTR mode. A counter, equal to the plaintext block size is used. The only requirement stated in SP A is that the counter value must be different for each plaintext block that is encrypted. Typically, the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo 2b, where b is the block size). For encryption, the counter is encrypted and then XORed with the plaintext block to produce the ciphertext block; there is no chaining. For decryption, the same sequence of counter values is used, with each encrypted counter XORed with a ciphertext block to recover the corresponding plaintext block. [LIPM00] lists the following advantages of CTR mode: • Hardware efficiency: Unlike the three chaining modes, encryption (or decryption) in CTR mode can be done in parallel on multiple blocks of plaintext or ciphertext. For the chaining modes, the algorithm must complete the computation on one block before beginning on the next block. This limits the maximum throughput of the algorithm to the reciprocal of the time for one execution of block encryption or decryption. In CTR mode, the throughput is only limited by the amount of parallelism that is achieved. • Software efficiency: Similarly, because of the opportunities for parallel execution in CTR mode, processors that support parallel features, such as aggressive pipelining, multiple instruction dispatch per clock cycle, a large number of registers, and SIMD instructions, can be effectively utilized. • Preprocessing: The execution of the underlying encryption algorithm does not depend on input of the plaintext or ciphertext. Therefore, if sufficient memory is available and security is maintained, preprocessing can be used to prepare the output of the encryption boxes that feed into the XOR functions in Figure When the plaintext or ciphertext input is presented, then the only computation is a series of XORs. Such a strategy greatly enhances throughput. • Random access: The i th block of plaintext or ciphertext can be processed in random access fashion. With the chaining modes, block Ci cannot be computed until the i - 1 prior block are computed. There may be applications in which a ciphertext is stored and it is desired to decrypt just one block; for such applications, the random access feature is attractive. • Provable security: It can be shown that CTR is at least as secure as the other modes discussed in this section. • Simplicity: Unlike ECB and CBC modes, CTR mode requires only the implementation of the encryption algorithm and not the decryption algorithm. This matters most when the decryption algorithm differs substantially from the encryption algorithm, as it does for AES. In addition, the decryption key scheduling need not be implemented.

Message Authentication
Encryption protects against passive attack (eavesdropping). A different requirement is needed to protect against active attack (falsification of data and transactions). This protection is known as message or data authentication. Protects against active attacks Verifies received message is authentic Can use conventional encryption Contents have not been altered From authentic source Timely and in correct sequence Only sender & receiver share a key Encryption protects against passive attack (eavesdropping). A different requirement is to protect against active attack (falsification of data and transactions). Protection against such attacks is known as message or data authentication. A message, file, document, or other collection of data is said to be authentic when it is genuine and came from its alleged source. Message or data authentication is a procedure that allows communicating parties to verify that received or stored messages are authentic. The two important aspects are to verify that the contents of the message have not been altered and that the source is authentic. We may also wish to verify a message’s timeliness (it has not been artificially delayed and replayed) and sequence relative to other messages flowing between two parties. All of these concerns come under the category of data integrity as described in Chapter 1. It would seem possible to perform authentication simply by the use of symmetric encryption. If we assume that only the sender and receiver share a key (which is as it should be), then only the genuine sender would be able to encrypt a message successfully for the other participant, provided the receiver can recognize a valid message. Furthermore, if the message includes an error-detection code and a sequence number, the receiver is assured that no alterations have been made and that sequencing is proper. If the message also includes a timestamp, the receiver is assured that the message has not been delayed beyond that normally expected for network transit. In fact, symmetric encryption alone is not a suitable tool for data authentication. To give one simple example, in the ECB mode of encryption, if an attacker reorders the blocks of ciphertext, then each block will still decrypt successfully. However, the reordering may alter the meaning of the overall data sequence. Although sequence numbers may be used at some level (e.g., each IP packet), it is typically not the case that a separate sequence number will be associated with each b-bit block of plaintext. Thus, block reordering is a threat.

MAC: Message Authentication Code
One authentication technique involves the use of a secret key to generate a small block of data, known as a Message Authentication Code, that is appended to the message. This technique assumes that two communicating parties, say A and B, share a common secret key KAB. When A has a message to send to B, it calculates the message authentication code as a complex function of the message and the key: MACM F(KAB, M). The message plus code are transmitted to the intended recipient. The recipient performs the same calculation on the received message, using the same secret key, to generate a new message authentication code. The received code is compared to the calculated code (Figure 2.3). If we assume that only the receiver and the sender know the identity of the secret key, and if the received code matches the calculated code, then 1. The receiver is assured that the message has not been altered. If an attacker alters the message but does not alter the code, then the receiver’s calculation of the code will differ from the received code. Because the attacker is assumed not to know the secret key, the attacker cannot alter the code to correspond to the alterations in the message. 2. The receiver is assured that the message is from the alleged sender. Because no one else knows the secret key, no one else could prepare a message with a proper code. 3. If the message includes a sequence number (such as is used with X.25, HDLC, and TCP), then the receiver can be assured of the proper sequence, because an attacker cannot successfully alter the sequence number. A number of algorithms could be used to generate the code. The NIST specification, FIPS PUB 113, recommends the use of DES. DES is used to generate an encrypted version of the message, and the last number of bits of ciphertext are used as the code. A 16- or 32-bit code is typical. The process just described is similar to encryption. One difference is that the authentication algorithm need not be reversible, as it must for decryption. It turns out that because of the mathematical properties of the authentication function, it is less vulnerable to being broken than encryption. Assumes that two parties, say A and B, share a common secret key KAB A calculates a MAC as a function MACM = F(KAB, M). Then, both M & MACM are sent to B. Then, B recalculates MACM and compares them

MAC: Message Authentication Code
The receiver is assured that the message has not been altered. If an attacker alters the message but does not alter the code, then the receiver’s calculation of the code will differ from the received code. Because the attacker is assumed not to know the secret key, the attacker cannot alter the code to correspond to the alterations in the message. 2. The receiver is assured that the message is from the alleged sender. Because no one else knows the secret key, no one else could prepare a message with a proper code. 3. If the message includes a sequence number, then the receiver can be assured of the proper sequence, because an attacker cannot successfully alter the sequence number. An alternative to the message authentication code is the one-way hash function. As with the message authentication code, a hash function accepts a variable-size message M as input and produces a fixed-size message digest H(M) as output (Figure 2.4). Typically, the message is padded out to an integer multiple of some fixed length (e.g., 1024 bits) and the padding includes the value of the length of the original message in bits. The length field is a security measure to increase the difficulty for an attacker to produce an alternative message with the same hash value. An alternative to the MAC is the one-way hash function. (i.e. SHA-1, SHA-2, SHA-256, SHA-384) As with the MAC, a hash function accepts a variable-size message M as input and produces a fixed-size value (message digest) H(M) as output

1 2 Unlike the MAC, a hash function does not also take a secret key as input. To authenticate a message, the message digest is sent with the message in such a way that the message digest is authentic. Figure 2.5 illustrates three ways in which the message can be authenticated using a hash code. The message digest can be encrypted using symmetric encryption (part a); if it is assumed that only the sender and receiver share the encryption key, then authenticity is assured. The message digest can also be encrypted using public-key encryption (part b); this is explained in Section 2.3. The public-key approach has two advantages: It provides a digital signature as well as message authentication; and it does not require the distribution of keys to communicating parties. These two approaches have an advantage over approaches that encrypt the entire message in that less computation is required. But an even more common approach is the use of a technique that avoids encryption altogether. Several reasons for this interest are pointed out in [TSUD92]: • Encryption software is quite slow. Even though the amount of data to be encrypted per message is small, there may be a steady stream of messages into and out of a system. • Encryption hardware costs are non-negligible. Low-cost chip implementations of DES are available, but the cost adds up if all nodes in a network must have this capability. • Encryption hardware is optimized toward large data sizes. For small blocks of data, a high proportion of the time is spent in initialization/invocation overhead. • An encryption algorithm may be protected by a patent. Figure 2.5c shows a technique that uses a hash function but no encryption for message authentication. This technique, known as a keyed hash MAC, assumes that two communicating parties, say A and B, share a common secret key K. This secret key is incorporated into the process of generating a hash code. In the approach illustrated in Figure 2.5c, when A has a message to send to B, it calculates the hash function over the concatenation of the secret key and the message: MDM = H(K ll M ll K). It then sends [ M ii MDM] to B. Because B possesses K, it can recompute H(K ll M ll K) and verify MDM. Because the secret key itself is not sent, it should not be possible for an attacker to modify an intercepted message. As long as the secret key remains secret, it should not be possible for an attacker to generate a false message. Note that the secret key is used as both a prefix and a suffix to the message. If the secret key is used as either only a prefix or only a suffix, the scheme is less secure. This topic is discussed in Chapter 21. Chapter 21 also describes a scheme known as HMAC, which is somewhat more complex than the approach of Figure 2.5c and which has become the standard approach for a keyed hash MAC. 3 keyed hash MAC

Hash Function Requirements
A hash function can be used to produce a “fingerprint” of a file, message, or block of data. To be useful for message authentication, a hash function H must have the following properties: Can be applied to a block of data of any size Produces a fixed-length output H(x) is relatively easy to compute for any given x One-way or pre-image resistant Computationally infeasible to find x such that H(x) = h Computationally infeasible to find y ≠ x such that H(y) = H(x) Collision resistant or strong collision resistance Computationally infeasible to find any pair (x,y) such that H(x) = H(y) The purpose of a hash function is to produce a “fingerprint” of a file, message, or other block of data. To be useful for message authentication, a hash function H must have the following properties: 1. H can be applied to a block of data of any size. 2. H produces a fixed-length output. 3. H(x) is relatively easy to compute for any given x, making both hardware and software implementations practical. 4. For any given code h, it is computationally infeasible to find x such that H(x) h. A hash function with this property is referred to as one-way or preimage resistant. 5. For any given block x, it is computationally infeasible to find y ≠ x with H(y) H(x). A hash function with this property is referred to as second preimage resistant. This is sometimes referred to as weak collision resistant. 6. It is computationally infeasible to find any pair (x, y) such that H(x) H(y). A hash function with this property is referred to as collision resistant. This is sometimes referred to as strong collision resistant. The first three properties are requirements for the practical application of a hash function to message authentication. The fourth property is the one-way property: It is easy to generate a code given a message, but virtually impossible to generate a message given a code. This property is important if the authentication technique involves the use of a secret value (Figure 2.5c). The secret value itself is not sent; however, if the hash function is not one way, an attacker can easily discover the secret value: If the attacker can observe or intercept a transmission, the attacker obtains the message M and the hash code MDM H(SAB || M). The attacker then inverts the hash function to obtain SAB || M H-1(MDM). Because the attacker now has both M and SAB || M, it is a trivial matter to recover SAB. The fifth property guarantees that it is impossible to find an alternative message with the same hash value as a given message. This prevents forgery when an encrypted hash code is used (Figures 2.5a and b). If this property were not true, an attacker would be capable of the following sequence: First, observe or intercept a message plus its encrypted hash code; second, generate an unencrypted hash code from the message; third, generate an alternate message with the same hash code. A hash function that satisfies the first five properties in the preceding list is referred to as a weak hash function. If the sixth property is also satisfied, then it is referred to as a strong hash function. A strong hash function protects against an attack in which one party generates a message for another party to sign. For example, suppose Bob gets to write an IOU message, send it to Alice, and she signs it. Bob finds two messages with the same hash, one of which requires Alice to pay a small amount and one that requires a large payment. Alice signs the first message and Bob is then able to claim that the second message is authentic.

Security of Hash Functions
There are two approaches to attacking a secure hash function: Cryptanalysis Exploit logical weaknesses in the algorithm Brute-force attack Strength of hash function depends solely on the length of the hash code produced by the algorithm SHA most widely used hash algorithm * SHA-1 (Secure Hash Algorithm 1) (160-bit); Not secure any more * SHA-2 family consists of six hash functions ( SHA-256,  256 bits SHA-384 384 bits SHA-512 512 bits ) *SHA-3 is the latest member of the Secure Hash Algorithm family of standards (released by NIST on August 2015) Additional secure hash function applications: Passwords Hash of a password is stored by an operating system Intrusion detection Store H(F) for each file on a system and secure the hash values As with symmetric encryption, there are two approaches to attacking a secure hash function: cryptanalysis and brute-force attack. As with symmetric encryption algorithms, cryptanalysis of a hash function involves exploiting logical weaknesses in the algorithm. The strength of a hash function against brute-force attacks depends solely on the length of the hash code produced by the algorithm. For a hash code of length n, the level of effort required is proportional to the following: Preimage resistant 2n Second preimage resistant 2n Collision resistant 2n/2 If collision resistance is required (and this is desirable for a general-purpose secure hash code), then the value 2n/2 determines the strength of the hash code against brute-force attacks. Van Oorschot and Wiener [VANO94] pre sented a design for a $10 million collision search machine for MD5, which has a 128-bit hash length, that could find a collision in 24 days. Thus a 128-bit code may be viewed as inadequate. The next step up, if a hash code is treated as a sequence of 32 bits, is a 160-bit hash length. With a hash length of 160 bits, the same search machine would require over four thousand years to find a collision. With today’s technology, the time would be much shorter, so that 160 bits now appears suspect. In recent years, the most widely used hash function has been the Secure Hash Algorithm (SHA). SHA was developed by the National Institute of Standards and Technology (NIST) and published as a federal information processing standard (FIPS 180) in When weaknesses were discovered in SHA, a revised version was issued as FIPS in 1995 and is generally referred to as SHA-1. SHA-1 produces a hash value of 160 bits. In 2002, NIST produced a revised version of the standard, FIPS 180–2, that defined three new versions of SHA, with hash value lengths of 256, 384, and 512 bits, known as SHA-256, SHA-384, and SHA-512. These new versions have the same underlying structure and use the same types of modular arithmetic and logical binary operations as SHA-1. In 2005, NIST announced the intention to phase out approval of SHA-1 and move to a reliance on the other SHA versions by As discussed in Chapter 21, researchers have demonstrated that SHA-1 is far weaker than its 160-bit hash length suggests, necessitating the move to the newer versions of SHA. We have discussed the use of hash functions for message authentication and for the creation of digital signatures (the latter is discussed in more detail later in this chapter). Here are two other examples of secure hash function applications: • Passwords: Chapter 3 explains a scheme in which a hash of a password is stored by an operating system rather than the password itself. Thus, the actual password is not retrievable by a hacker who gains access to the password file. In simple terms, when a user enters a password, the hash of that password is compared to the stored hash value for verification. This application requires preimage resistance and perhaps second preimage resistance. • Intrusion detection: Store H(F) for each file on a system and secure the hash values (e.g., on a CD-R that is kept secure). One can later determine if a file has been modified by recomputing H(F). An intruder would need to change F without changing H(F). This application requires weak second preimage resistance

Public-Key Encryption Structure
Publicly proposed by Diffie and Hellman in 1976 Based on mathematical functions Asymmetric Uses two separate keys Public key and private key Public key is made public for others to use Some form of protocol is needed for distribution Public-key encryption, first publicly proposed by Diffie and Hellman in 1976 [DIFF76], is the first truly revolutionary advance in encryption in literally thousands of years. Public-key algorithms are based on mathematical functions rather than on simple operations on bit patterns, such as are used in symmetric encryption algorithms. More important, public-key cryptography is asymmetric, involving the use of two separate keys, in contrast to symmetric encryption, which uses only one key. The use of two keys has profound consequences in the areas of confidentiality, key distribution, and authentication. Before proceeding, we should first mention several common misconceptions concerning public-key encryption. One is that public-key encryption is more secure from cryptanalysis than symmetric encryption. In fact, the security of any encryption scheme depends on (1) the length of the key and (2) the computational work involved in breaking a cipher. There is nothing in principle about either symmetric or public-key encryption that makes one superior to another from the point of view of resisting cryptanalysis. A second misconception is that public-key encryption is a general- purpose technique that has made symmetric encryption obsolete. On the contrary, because of the computational overhead of current public-key encryption schemes, there seems no foreseeable likelihood that symmetric encryption will be abandoned. Finally, there is a feeling that key distribution is trivial when using public-key encryption, compared to the rather cumbersome handshaking involved with key distribution centers for symmetric encryption. For public-key key distribution, some form of protocol is needed, often involving a central agent, and the procedures involved are no simpler or any more efficient than those required for symmetric encryption. As the names suggest, the public key of the pair is made public for others to use, while the private key is known only to its owner. A general-purpose public-key cryptographic algorithm relies on one key for encryption and a different but related key for decryption.

A public-key encryption scheme has six ingredients Plaintext
Readable message or data that is fed into the algorithm as input Encryption algorithm Performs transformations on the plaintext Public and private key Pair of keys, one for encryption, one for decryption Ciphertext Scrambled message produced as output Decryption algorithm Produces the original plaintext A public-key encryption scheme has six ingredients (Figure 2.6a): • Plaintext: This is the readable message or data that is fed into the algorithm as input. • Encryption algorithm: The encryption algorithm performs various transformations on the plaintext. • Public and private key: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transformations performed by the encryption algorithm depend on the public or private key that is provided as input. Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts. • Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext. As the names suggest, the public key of the pair is made public for others to use, while the private key is known only to its owner. A general-purpose public-key cryptographic algorithm relies on one key for encryption and a different but related key for decryption. The essential steps are the following: 1. Each user generates a pair of keys to be used for the encryption and decryption of messages. 2. Each user places one of the two keys in a public register or other accessible file. This is the public key. The companion key is kept private. As Figure 2.6a suggests, each user maintains a collection of public keys obtained from others. 3. If Bob wishes to send a private message to Alice, Bob encrypts the message using Alice’s public key. 4. When Alice receives the message, she decrypts it using her private key. No other recipient can decrypt the message because only Alice knows Alice’s private key. With this approach, all participants have access to public keys, and private keys are generated locally by each participant and therefore need never be distributed. As long as a user protects his or her private key, incoming communication is secure. At any time, a user can change the private key and publish the companion public key to replace the old public key. Note that the scheme of Figure 2.6a is directed toward providing confidentiality: Only the intended recipient should be able to decrypt the ciphertext because only the intended recipient is in possession of the required private key. Whether in fact confidentiality is provided depends on a number of factors, including the security of the algorithm, whether the private key is kept secure, and the security of any protocol of which the encryption function is a part.

User encrypts data using his or her own private key
Figure 2.6b illustrates another mode of operation of public-key cryptography. In this scheme, a user encrypts data using his or her own private key. Anyone who knows the corresponding public key will then be able to decrypt the message. The scheme of Figure 2.6b is directed toward providing authentication and/or data integrity. If a user is able to successfully recover the plaintext from Bob’s ciphertext using Bob’s public key, this indicates that only Bob could have encrypted the plaintext, thus providing authentication. Further, no one but Bob would be able to modify the plaintext because only Bob could encrypt the plaintext with Bob’s private key. Once again, the actual provision of authentication or data integrity depends on a variety of factors. This issue is addressed primarily in Chapter 21, but other references are made to it where appropriate in this text. User encrypts data using his or her own private key Anyone who knows the corresponding public key will be able to decrypt the message

Applications for Public-Key Cryptosystems
Table 2.3 Applications for Public-Key Cryptosystems Before proceeding, we need to clarify one aspect of public-key cryptosystems that is otherwise likely to lead to confusion. Public-key systems are characterized by the use of a cryptographic type of algorithm with two keys, one held private and one available publicly. Depending on the application, the sender uses either the sender’s private key or the receiver’s public key, or both, to perform some type of cryptographic function. In broad terms, we can classify the use of public-key cryptosystems into three categories: digital signature, symmetric key distribution, and encryption of secret keys. These applications are discussed in Section 2.4. Some algorithms are suitable for all three applications, whereas others can be used only for one or two of these applications. Table 2.3 indicates the applications supported by the algorithms discussed in this section.

Requirements for Public-Key Cryptosystems
Computationally easy to create key pairs Computationally easy for sender knowing public key to encrypt messages Computationally easy for receiver knowing private key to decrypt ciphertext Computationally infeasible for opponent to determine private key from public key Computationally infeasible for opponent to otherwise recover original message Useful if either key can be used for each role The cryptosystem illustrated in Figure 2.6 depends on a cryptographic algorithm based on two related keys. Diffie and Hellman postulated this system without demonstrating that such algorithms exist. However, they did lay out the conditions that such algorithms must fulfill [DIFF76]:

Digital Signatures Used for authenticating both source and data integrity Created by encrypting hash code with private key Does not provide confidentiality Even in the case of complete encryption Message is safe from alteration but not eavesdropping because the rest of the message is transmitted in the clear Even in the case of complete encryption, there is no protection of confidentiality because any observer can decrypt the message by using the sender’s public key. Public-key encryption can be used for authentication, as suggested by Figure 2.6b. Suppose that Bob wants to send a message to Alice. Although it is not important that the message be kept secret, he wants Alice to be certain that the message is indeed from him. For this purpose, Bob uses a secure hash function, such as SHA-512, to generate a hash value for the message and then encrypts the hash code with his private key, creating a digital signature. Bob sends the message with the signature attached. When Alice receives the message plus signature, she (1) calculates a hash value for the message; (2) decrypts the signature using Bob’s public key; and (3) compares the calculated hash value to the decrypted hash value. If the two hash values match, Alice is assured that the message must have been signed by Bob. No one else has Bob’s private key and therefore no one else could have created a ciphertext that could be decrypted with Bob’s public key. In addition, it is impossible to alter the message without access to Bob’s private key, so the message is authenticated both in terms of source and in terms of data integrity. It is important to emphasize that the digital signature does not provide confidentiality. That is, the message being sent is safe from alteration but not safe from eavesdropping. This is obvious in the case of a signature based on a portion of the message, because the rest of the message is transmitted in the clear. Even in the case of complete encryption, there is no protection of confidentiality because any observer can decrypt the message by using the sender’s public key.

Digital Signatures NIST FIPS PUB defines a digital signature as: (link) “The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity and signatory non- repudiation.” Thus, a digital signature is a data-dependent bit pattern, generated by an agent as a function of a file, message, or other form of data block FIPS specifies the use of one of three digital signature algorithms: Digital Signature Algorithm (DSA) RSA Digital Signature Algorithm Elliptic Curve Digital Signature Algorithm (ECDSA) Public-key encryption can be used for authentication with a technique known as the digital signature. NIST FIPS PUB [Digital Signature Standard (DSS) , July 2013] defines a digital signature as follows: The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity and signatory non-repudiation. Thus, a digital signature is a data-dependent bit pattern, generated by an agent as a function of a file, message, or other form of data block. Another agent can access the data block and its associated signature and verify (1) the data block has been signed by the alleged signer, and (2) the data block has not been altered since the signing. Further, the signer cannot repudiate the signature. FIPS specifies the use of one of three digital signature algorithms: • Digital Signature Algorithm (DSA): The original NIST-approved algorithm, which is based on the difficulty of computing discrete logarithms. • RSA Digital Signature Algorithm: Based on the RSA public-key algorithm. • Elliptic Curve Digital Signature Algorithm (ECDSA): Based on elliptic-curve cryptography.

Properties of Digital Signatures: Example
Suppose Alice sends her bank a message authorizing it to transfer $100 to Bob. Alice’s bank must be able to verify and prove that the message really came from Alice. if she should later deny sending the message. (This property is called non-repudiation.) The bank also wants to know that the message is entirely Alice’s, that it has not been altered along the way. For her part, Alice wants to be certain that her bank cannot forge such messages. (This property is called authenticity.) Both parties want to be sure that the message is new, not a reuse of a previous message, and that it has not been altered during transmission. Thus, a digital signature is a protocol that produces the same effect as a real signature: It is a mark that only the sender can make but that other people can easily recognize as belonging to the sender. Just like a real signature, a digital signature confirms agreement to a message.

Figure 2.7 is a generic model of the process of making and using digital signatures.
All of the digital signature schemes in FIPS have this structure. Suppose Bob wants to send a message to Alice. Although it is not important that the message be kept secret, he wants Alice to be certain that the message is indeed from him. For this purpose, Bob uses a secure hash function, such as SHA-512, to generate a hash value for the message. That hash value, together with Bob’s private key, serve as input to a digital signature generation algorithm that produces a short block that functions as a digital signature. Bob sends the message with the signature attached. When Alice receives the message plus signature, she (1) calculates a hash value for the message; (2) provides the hash value and Bob’s public key as inputs to a digital signature verification algorithm. If the algorithm returns the result that the signature is valid, Alice is assured that the message must have been signed by Bob. No one else has Bob’s private key, and therefore no one else could have created a signature that could be verified for this message with Bob’s public key. In addition, it is impossible to alter the message without access to Bob’s private key, so the message is authenticated both in terms of source and in terms of data integrity. The digital signature does not provide confidentiality. That is, the message being sent is safe from alteration, but not safe from eavesdropping. This is obvious in the case of a signature based on a portion of the message, because the rest of the message is transmitted in the clear. Even in the case of complete encryption, there is no protection of confidentiality because any observer can decrypt the message by using the sender’s public key.

On the face of it, the point of public-key encryption is that the public key is public.
Thus, if there is some broadly accepted public-key algorithm, such as RSA, any participant can send his or her public key to any other participant or broadcast the key to the community at large. Although this approach is convenient, it has a major weakness. Anyone can forge such a public announcement. That is, some user could pretend to be Bob and send a public key to another participant or broadcast such a public key. Until such time as Bob discovers the forgery and alerts other participants, the forger is able to read all encrypted messages intended for A and can use the forged keys for authentication. The solution to this problem is the public-key certificate. In essence, a certificate consists of a public key plus a user ID of the key owner, with the whole block signed by a trusted third party. The certificate also includes some information about the third party plus an indication of the period of validity of the certificate. Typically, the third party is a certificate authority (CA) that is trusted by the user community, such as a government agency or a financial institution. A user can present his or her public key to the authority in a secure manner and obtain a signed certificate. The user can then publish the certificate. Anyone needing this user’s public key can obtain the certificate and verify that it is valid by means of the attached trusted signature. Figure 2.7 illustrates the process. One scheme has become universally accepted for formatting public-key certificates: the X.509 standard. X.509 certificates are used in most network security applications, including IP Security (IPsec), Transport Layer Security (TLS), Secure Shell (SSH), and Secure/Multipurpose Internet Mail Extension (S/MIME). We examine most of these applications in Part Five.

Digital Envelopes Protects a message without needing to first arrange for sender and receiver to have the same secret key Equates to the same thing as a sealed envelope containing an unsigned letter Another application in which public-key encryption is used to protect a symmetric key is the digital envelope, which can be used to protect a message without needing to first arrange for sender and receiver to have the same secret key. The technique is referred to as a digital envelope, which is the equivalent of a sealed envelope containing an unsigned letter. The general approach is shown in Figure 2.8. Suppose Bob wishes to send a confidential message to Alice, but they do not share a symmetric secret key. Bob does the following: 1. Prepare a message. 2. Generate a random symmetric key that will be used this one time only. 3. Encrypt that message using symmetric encryption the one-time key. 4. Encrypt the one-time key using public-key encryption with Alice’s public key. 5. Attach the encrypted one-time key to the encrypted message and send it to Alice. Only Alice is capable of decrypting the one-time key and therefore of recovering the original message. If Bob obtained Alice’s public key by means of Alice’s public-key certificate, then Bob is assured that it is a valid key.

Sender Receiver One time Key only
Another application in which public-key encryption is used to protect a symmetric key is the digital envelope, which can be used to protect a message without needing to first arrange for sender and receiver to have the same secret key. The technique is referred to as a digital envelope, which is the equivalent of a sealed envelope containing an unsigned letter. The general approach is shown in Figure 2.9. Suppose Bob wishes to send a confidential message to Alice, but they do not share a symmetric secret key. Bob does the following: 1. Prepare a message. 2. Generate a random symmetric key that will be used this one time only. 3. Encrypt that message using symmetric encryption the one-time key. 4. Encrypt the one-time key using public-key encryption with Alice’s public key. 5. Attach the encrypted one-time key to the encrypted message and send it to Alice. Only Alice is capable of decrypting the one-time key and therefore of recovering the original message. If Bob obtained Alice’s public key by means of Alice’s public-key certificate, then Bob is assured that it is a valid key.

Uses include generation of:
Keys for public-key algorithms Stream key for symmetric stream cipher Symmetric key for use as a temporary session key or in creating a digital envelope Handshaking to prevent replay attacks Session key Random Numbers A number of network security algorithms based on cryptography make use of random numbers. For example, • Generation of keys for the RSA public-key encryption algorithm (described in Chapter 21) and other public-key algorithms. • Generation of a stream key for symmetric stream cipher. • Generation of a symmetric key for use as a temporary session key or in creating a digital envelope. • In a number of key distribution scenarios, such as Kerberos (described in Chapter 23), random numbers are used for handshaking to prevent replay attacks. • Session key generation, whether done by a key distribution center or by one of the principals. These applications give rise to two distinct and not necessarily compatible requirements for a sequence of random numbers: randomness and unpredictability. Uses include generation of:

Random Number Requirements
Randomness Unpredictability Criteria: Uniform distribution Frequency of occurrence of each of the numbers should be approximately the same Independence No one value in the sequence can be inferred from the others Each number is statistically independent of other numbers in the sequence Opponent should not be able to predict future elements of the sequence on the basis of earlier elements Traditionally, the concern in the generation of a sequence of allegedly random numbers has been that the sequence of numbers be random in some well-defined statistical sense. The following two criteria are used to validate that a sequence of numbers is random: • Uniform distribution: The distribution of numbers in the sequence should be uniform; that is, the frequency of occurrence of each of the numbers should be approximately the same. • Independence: No one value in the sequence can be inferred from the others. Although there are well-defined tests for determining that a sequence of numbers matches a particular distribution, such as the uniform distribution, there is no such test to “prove” independence. Rather, a number of tests can be applied to demonstrate if a sequence does not exhibit independence. The general strategy is to apply a number of such tests until the confidence that independence exists is sufficiently strong. In the context of our discussion, the use of a sequence of numbers that appear statistically random often occurs in the design of algorithms related to cryptography. In essence, if a problem is too hard or time-consuming to solve exactly, a simpler, shorter approach based on randomization is used to provide an answer with any desired level of confidence. UNPREDICTABILITY In applications such as reciprocal authentication and session key generation, the requirement is not so much that the sequence of numbers be statistically random but that the successive members of the sequence are unpredictable. With “true” random sequences, each number is statistically independent of other numbers in the sequence and therefore unpredictable. However, as is discussed shortly, true random numbers are not always used; rather, sequences of numbers that appear to be random are generated by some algorithm. In this latter case, care must be taken that an opponent not be able to predict future elements of the sequence on the basis of earlier elements.

Random versus Pseudorandom
Cryptographic applications typically make use of algorithmic techniques for random number generation Algorithms are deterministic and therefore produce sequences of numbers that are not statistically random Pseudorandom numbers are: Sequences produced that satisfy statistical randomness tests Likely to be predictable True random number generator (TRNG): Uses a nondeterministic source to produce randomness Most operate by measuring unpredictable natural processes e.g. radiation, gas discharge, leaky capacitors Increasingly provided on modern processors Cryptographic applications typically make use of algorithmic techniques for random number generation. These algorithms are deterministic and therefore produce sequences of numbers that are not statistically random. However, if the algorithm is good, the resulting sequences will pass many reasonable tests of randomness. Such numbers are referred to as pseudorandom numbers. You may be somewhat uneasy about the concept of using numbers generated by a deterministic algorithm as if they were random numbers. Despite what might be called philosophical objections to such a practice, it generally works. As one expert on probability theory puts it [HAMM91], For practical purposes we are forced to accept the awkward concept of “relatively random” meaning that with regard to the proposed use we can see no reason why they will not perform as if they were random (as the theory usually requires). This is highly subjective and is not very palatable to purists, but it is what statisticians regularly appeal to when they take “a random sample”—they hope that any results they use will have approximately the same properties as a complete counting of the whole sample space that occurs in their theory. A true random number generator (TRNG) uses a nondeterministic source to produce randomness. Most operate by measuring unpredictable natural processes, such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capac itors. Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors [JUN99]. A group at Bell Labs has developed a technique that uses the variations in the response time of raw read requests for one disk sector of a hard disk [JAKO98]. LavaRnd is an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware. The system uses a saturated charge- coupled device (CCD) in a light-tight can as a chaotic source to produce the seed. Software processes the result into truly random numbers in a variety of formats.

Summary Public-key encryption
Confidentiality with symmetric encryption Symmetric encryption Symmetric block encryption algorithms Stream ciphers Message authentication and hash functions Authentication using symmetric encryption Message authentication without message encryption Secure hash functions Other applications of hash functions Random and pseudorandom numbers The use of random numbers Random versus pseudorandom Public-key encryption Structure Applications for public-key cryptosystems Requirements for public-key cryptography Asymmetric encryption algorithms Digital signatures and key management Digital signature Public-key certificates Symmetric key exchange using public-key encryption Digital envelopes Chapter 2 summary.

use of cryptographic algorithms

Similar presentations

Presentation on theme: "use of cryptographic algorithms"— Presentation transcript:

Similar presentations

About project

Feedback

Log in

Auth with social network:

use of cryptographic algorithms

Similar presentations

Presentation on theme: "use of cryptographic algorithms"— Presentation transcript:

Similar presentations

About project

Feedback