NETWORK SECURITY

NETWORK SECURITY

T he requirements of information security within an organization have undergone

two major changes in the last several decades. Before the widespread

use of data processing equipment, the security of information felt to be

valuable to an organization was provided primarily by physical and administrative

means; an example of the former is the use of rugged filing cabinets with a combination

lock for storing sensitive documents; an example of the latter is personnel

screening procedures used during the hiring process.

With the introduction of the computer, the need for automated tools for protecting

files and other information stored on the computer became evident; this is

especially the case for a shared system, such as a time-sharing system, and the need

is even more acute for systems that can be accessed over a public telephone or data

network. The generic name for the collection of tools designed to protect data and

to thwart hackers is computer security. Although this is an important topic, it is

beyond the scope of this lesson and will be dealt with only briefly.

The second major change that affected security is the introduction of distributed

systems and the use of networks and communications facilities for carrying

data between terminal user and computer and between computer and computer.

Network security measures are needed to protect data during their transmission,

and to guarantee that data transmissions are authentic.

The essential technology underlying virtually all automated network and computer

security applications is encryption. Two fundamental approaches are in use:

conventional encryption, also known as symmetric encryption, and public-key

encryption, also known as asymmetric encryption. As we look at the various

approaches to network security, these two types of encryption will be explored.

The lesson begins with an overview of the requirements for network security.

Next, we look at conventional encryption and its use in providing privacy; this is followed

by a discussion of message authentication. We then look at the use of publickey

encryption and digital signatures. The lesson closes with an examination of

security features in IPv4 and IPv6.

SECURITY REQUIREMENTS AND ATTACKS

In order to be able to understand the types of threats that exist to security, we need

to have a definition of security requirements. Computer and network security

address three requirements:

* Secrecy. Requires that the information in a computer system only be accessible

for reading by authorized parties. This type of access includes printing, displaying,

and other forms of disclosure, including simply revealing the existence

of an object.

Integrity. Requires that computer system assets can be modified only by

authorized parties. Modification includes writing, changing, changing status,

deleting, and creating.

Availability. Requires that computer system assets are available to authorized

parties.

The types of attacks on the security of a computer system or network are best characterized

by viewing the function of the computer system as providing information.

In general, there is a flow of information from a source, such as a file or a region of

main memory, to a destination, such as another file or a user. This normal flow is

depicted in Figure 18.la. The remaining parts of the figure show the following four

general categories of attack:

c Interruption. An asset of the system is destroyed or becomes unavailable or

unusable. This is an attack on availability. Examples include destruction of a

piece of hardware, such as a hard disk, the cutting of a communication line, or

the disabling of the file management system.

e Interception. An unauthorized party gains access to an asset. This is an attack

on confidentiality. The unauthorized party could be a person, a program, or a

computer. Examples include wiretapping to capture data in a network, and

the illicit copying of files or programs.

c Modification. An unauthorized party not only gains access to but tampers

with an asset. This is an attack on integrity. Examples include changing values

in a data file, altering a program so that it performs differently, and modifying

the content of messages being transmitted in a network.

Fabrication. An unauthorized party inserts counterfeit objects into the system.

This is an attack on authenticity. Examples include the insertion of spurious

messages in a network or the addition of records to a file.

A useful categorization of these attacks is in terms of passive attacks and

active attacks (Figure 18.2)

Passive Attacks

Passive attacks mean the eavesdropping on, or monitoring of, transmissions. The

goal of the opponent is to obtain information that is being transmitted. Two types

of attacks are involved here: release-of-message contents and traffic analysis.

The release-of-message contents is easily understood. A telephone conversation,

an electronic mail message, a transferred file may contain sensitive or confidential

information. We would like to prevent the opponent from learning the

contents of these transmissions.

The second passive attack, tralffic analysis, is more subtle. Suppose that we had

a way of masking the contents of messages or other information traffic so that opponents,

even if they captured the message, could not extract the information from the

message. The common technique for masking contents is encryption. If we had

encryption protection in place, an opponent might still be able to observe the pattern

of these messages. The opponent could determine the location and identity of

communicating hosts and could observe the frequency and length of messages being

exchanged. This information might be useful in guessing the nature of the cornrnunication

that was taking place.

Passive attacks are very difficult to detect because they do not involve any

alteration of the data. However, it is feasible to prevent the success of these attacks.

Thus, the emphasis in dealing with passive attacks is on prevention rather than

detection.

Active Attacks

The second major category of attack is active attacks. These attacks involve some

modification of the data stream or the creation of a false stream and can be subdivided

into four categories: masquerade, replay, modification of messages, and

denial of service.

A masquerade takes place when one entity pretends to be a different entity. A

masquerade attack usually includes one of the other forms of active attack. For

example, authentication sequences can be captured and replayed after a valid

authentication sequence has taken place, thus enabling an authorized entity with

few privileges to obtain extra privileges by impersonating an entity that has those

privileges.

Replay involves the passive capture of a data unit and its subsequent retransmission

to produce an unauthorized effect.

Modification of messages simply means that some portion of a legitimate message

is altered, or that messages are delayed or reordered, to produce an unauthorized

effect. For example, a message meaning "Allow John Smith to read confidential

file accounts" is modified to mean "Allow Fred Brown to read confidential file

accounts."

The denial of service prevents or inhibits the normal use or management of

communications facilities. This attack may have a specific target; for example, an

entity may suppress all messages directed to a particular destination (e.g., the security

audit service). Another form of service denial is the disruption of an entire network,

either by disabling the network or by overloading it with messages so as to

degrade performance.

Active attacks present the opposite characteristics of passive attacks. Whereas

passive attacks are difficult to detect, measures are available to prevent their success.

On the other hand, it is quite difficult to prevent active attacks absolutely, as

to do so would require physical protection of all communications facilities and paths

at all times. Instead, the goal is to detect them and to recover from any disruption

or delays caused by them. Because the detection has a deterrent effect, it may also

contribute to prevention.

PRIVACY WITH CONVENTIONAL ENCRYPTION

The universal technique for providing privacy for transmitted data is conventional

encryption. This section looks first at the basic concept of conventional encryption,

followed by a discussion of the two most popular conventional encryption techniques:

DES and triple DES. We then examine the application of these techniques

to achieve privacy.

Conventional Encryption

Figure 18.3 illustrates the conventional encryption process. The original intelligible

message, referred to as plaintext, is converted into apparently random nonsense,

referred to as ciphertext. The encryption process consists of an algorithm and a key.

The key is a value independent of the plaintext that controls the algorithm. The

algorithm will produce a different output depending on the specific key being used

at the time. Changing the key changes the output of the algorithm.

Once the ciphertext is produced, it is transmitted. Upon reception, the ciphertext

can be transformed back to the original plaintext by using a decryption algorithm

and the same key that was used for encryption.

The security of conventional encryption depends on several factors. First, the

encryption algorithm must be powerful enough so that it is impractical to decrypt a

message on the basis of the ciphertext alone. Beyond that, the security of conventional

encryption depends on the secrecy of the key, not on the secrecy of the algorithm.

That is, it is assumed that it is impractical to decrypt a message on the basis

of the ciphertext pl~rs knowledge of the encryptionldecryption algorithm. In other

words, we don't need to keep the algorithm secret; we only need to keep the key

secret.

This feature of conventional encryption is what makes it feasible for widespread

use. The fact that the algorithm need not be kept secret means that manufacturers

can and have developed low-cost chip implementations of data encryption

algorithms. These chips are widely available and incorporated into a number of

products. With the use of conventional encryption, the principal security problem is

maintaining the secrecy of the key.

Let us take a closer look at the essential elements of a conventional encryption

scheme, again using Figure 18.3. There is some source for a message, which

Encryption Algorithms

The most commonly used conventional 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 two most important conventional

algorithms, both of which are block ciphers, are DES and Triple DES.

The Data Encryption Standard (DES)

The most widely used encryption scheme is defined in 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). In 1994, NIST "reaffirmed" DES for federal use for

another five years [NIST94]; NIST recommends the use of DES for applications

other than the protection of classified information.

The overall scheme for DES encryption is illustrated in Figure 18.4. As with

any encryption scheme, there are two inputs to the encryption function: the plaintext

to be encrypted and the key. In this case, the plaintext must be 64 bits in length,

and the key is 56 bits in length.

The processing of the plaintext proceeds in three phases. First, the 64-bit

plaintext passes through an initial permutation (IP) that rearranges the bits to produce

the permuted input. This IP is followed by a phase consisting of 16 iterations

of the same function. The output of the last (16th) iteration consists of 64 bits that

are a function of the plaintext input and the key. The left and right halves of the output

are swapped to produce the preoutput. Finally, the preoutput is passed through

a permutation (IP-l) that is the inverse of the initial permutation function, in order

to produce the 64-bit ciphertext.

The right-hand portion of Figure 18.4 shows the way in which the 56-bit key is

used. Initially, the key is passed through a permutation function. Then, for each of

the 16 iterations, a subkey (K;) is produced by the combination of a left circular shift

and a permutation. The permutation function is the same for each iteration, but a

different subkey is produced because of the repeated shifting of the key bits

Figure 18.5 examines more closely the algorithm for a single iteration. The

64-bit permuted input passes through 16 iterations, producing an intermediate

64-bit value at the conclusion of each iteration. The left- and right-half of each 64-bit

intermediate value are treated as separate 32-bit quantities, labeled L (left) and R

(right). The overall processing at each iteration can be summarized in the following

formulas:

The Strength of DES

Since its adoption as a federal standard, there have been lingering concerns about

the level of security provided by DES. These concerns, by and large, fall into two

areas: the nature of the algorithm and key size.

For many years, the more important concern was the possibility of exploiting

the characteristics of the DES algorithm to perform cryptanalysis. The focus of concern

has been on the eight substitution tables, or S-boxes, that are used in each iteration.

Because the design criteria for these boxes, and indeed for the entire algorithm,

have never been made public, there is a suspicion that the boxes were

constructed in such a way that cryptanalysis is possible for an opponent who knows

the weaknesses in the S-boxes. This assertion is tantalizing, and over the years a

number of regularities and unexpected behaviors of the S-boxes have been discovered.

Despite this problem, no one has so far succeeded in discovering the supposed

fatal weaknesses in the S-boxes. Indeed, as advances in cryptanalytic techniques

have occurred, the underlying strength of the DES algorithm has become more

apparent. As of this writing, no practical attack method for DES has been published.

Given that the algorithm has survived years of intensive scrutiny unscathed,

it is probably safe to say that DES is one of the strongest encryption algorithms ever

devised.

The more serious concern, today, is the key size. With a key length of 56 bits,

there are 2j6 possible keys, which is approximately 7.6 X 10^16 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 microsecond would take more than a thousand years to break the cipher.

However, the assumption of one encryption per microsecond is overly conservative.

As far back as 1977, Diffie and Hellman, the inventors of public-key

encryption, postulated that the technology existed to build a parallel machine with

1 million encryption devices, each of which could perform one encryption per

microsecond. The authors estimated that the cost would be about $20 million in

1977 dollars.

The most rigorous recent analysis of the problem was done by Wiener

[WIEN93] and is based on a known plaintext attack. That is, it is assumed that the

attacker has at least one (plaintext, ciphertext) pair. Wiener takes care to provide

the details of his design. To quote his paper,

There have been numerous unverifiable claims about how fast the DES key

space can be searched. To avoid adding to this list of questionable claims, a great

deal of detail in the design of a key search machine is included in the appendices.

This detailed work was done to obtain an accurate assessment of the cost of the

machine and the time required to find a DES key. There are no plans to actually

build such a machine.

Wiener reports on the design of a chip that uses pipelined techniques to

achieve a key search rate of 50 million keys per second. llsing 1993 costs, he

designed a module that costs $100,000 and contains 5,760 key search chips. With this

In addition, Wiener estimates a one-time development cost of about $500,000.

The Wiener design represents the culmination of years of concern about the

security of DES and may in retrospect have been a turning point. As of the time of

this writing, it still seems reasonable to rely on DES for personal and commercial

applications. But the time has come to investigate alternatives for conventional

encryption. One of the most promising and widely used candidates for replacing

DES is triple DES.

design, the following results are obtained:

In addition, Wiener estimates a one-time development cost of about $500,000.

The Wiener design represents the culmination of years of concern about the

security of DES and may in retrospect have been a turning point. As of the time of

this writing, it still seems reasonable to rely on DES for personal and commercial

applications. But the time has come to investigate alternatives for conventional

encryption. One of the most promising and widely used candidates for replacing

DES is triple DES.

design, the following results are obtained:

Triple DES

Triple DES

Key Search Machine Unit Cost

Triple DES was first proposed by Tuchman [TUCH79], and first standardized for

use in financial applications [ANSI85]. Triple DES uses two keys and three executions

of the DES algorithm (Figure 18.6). The function follows an encrypt-decryptencrypt

(EDE) sequence:

middle attack, that would reduce a double DES system with two keys to the relative

strength of ordinary single DES. With three iterations of the DES function, the

effective key length is 112 bits.

Location of Encryption Devices

The most powerful, and most common, approach to countering the threats to network

security is encryption. In using encryption we need to decide what to encrypt

and where the encryption gear should be located. As Figure 18.7 indicates, there are

two fundamental alternatives: link encryption and end-to-end encryption.

With link encryption, each vulnerable communications link is equipped on

both ends with an encryption device. Thus, all traffic over all communications links

is secured. Although this requires many encryption devices in a large network, the

value of this approach is clear. However, one disadvantage of this approach is that

the message must be decrypted each time it enters a packet switch; this is necessary

because the switch must read the address (virtual circuit number) in the packet

header in order to route the packet. Thus. the message is vulnerable at each switch.

If this is a public packet-switching network, the user has no control over the security

of the nodes.

With end-to-end encryption, the encryption process is carried out at the two

end systems. The source host, or terminal, encrypts the data, which, in encrypted

form, is then transmitted unaltered across the network to the destination terminal

or host. The destination shares a key with the source and so is able to decrypt the

data. This approach would seem to secure the transmission against attacks on the

network links or switches. There is, however, still a weak spot.

Consider the following situation. A host connects to an X.25 packet-switching

network, sets up a virtual circuit to another host, and is prepared to transfer data to

that other host using end-to-end encryption. Data are transmitted over such a network

in the form of packets, consisting of a header and some user data. What part

of each packet will the host encrypt? Suppose that the host encrypts the entire

packet, including the header. This will not work because, remember, only the other

host can perform the decryption. The packet-switching node will receive an

encrypted packet and be unable to read the header. Therefore, it will not be able to

route the packet! It follows that the host may only encrypt the user data portion

of the packet and must leave the header in the clear, so that it can be read by the

network.

Thus, with end-to-end encryption, the user data are secure; however, the traffic

pattern is not, as packet headers are transmitted in the clear. To achieve greater

security, both link and end-to-end encryption are needed, as is shown in Figure 18.7.

To summarize, when both forms are employed, the host encrypts the user data

portion of a packet using an end-to-end encryption key. The entire packet is then

encrypted using a link-encryption key. As the packet traverses the network, each

switch decrypts the packet using a link-encryption key in order to read the header

and then encrypts the entire packet again so as to send it out on the next link. Now

the entire packet is secure, except for the time that the packet is actually in the

memory of a packet switch, at which time the packet header is in the clear.

Key Distribution

For conventional encryption to work, the two parties in an exchange must have the

same key, and that key must be protected from access by others. Furthermore, frequent

key changes are usually desirable to limit the amount of data compromised if

an attacker learns the key. Therefore, the strength of any cryptographic system rests

with the key distribution technique, a term that refers to the means of delivering a

key to two parties who wish to exchange data without allowing others to see the key.

Key distribution can be achieved in a number of ways. For two parties A and B

1. A key could be selected by A and physically delivered to B.

2. A third party could select the key and physically deliver it to A and B.

3. If A and B have previously and recently used a key, one party could transmit

the new key to the other, encrypted using the old key.

4. If A and B each have an encrypted connection to a third party C, C could

deliver a key on the encrypted links to A and B.

Options 1 and 2 call for manual delivery of a key; for link encryption, this is a

reasonable requirement, as each link encryption device is only going to be exchanging

data with its partner on the other end of the link. However, for end-to-end

encryption, manual delivery is awkward. In a distributed system, any given host or

terminal may need to engage in exchanges with many other hosts and terminals

over time. Thus, each device needs a number of keys, supplied dynamically. The

problem is especially difficult in a wide-area distributed system.

Option 3 is a possibility for either link encryption or end-to-end encryption,

but if an attacker ever succeeds in gaining access to one key, then all subsequent

keys are revealed. Even if frequent changes are made to the link-encryption keys,

these should be done manually. To provide keys for end-to-end encryption, option

4 is preferable.

Figure 18.8 illustrates an implementation that satisfies option 4 for end-to-end

encryption. In the figure, link encryption is ignored. This can be added, or not, as

required. For this scheme, two kinds of keys are identified:

Session key. When two end systems (hosts, terminals, etc.) wish to communicate,

they establish a logical connection (e.g., virtual circuit). For the duration

of that logical connection, all user data are encrypted with a one-time session

key. At the conclusion of the session, or connection, the session key is

destroyed.

Permanent key. A permanent key is one used between entities for the purpose

of distributing session keys.

The configuration consists of the following elements:

Key distribution center. The key distribution center determines which systems

are allowed to communicate with each other. When permission is granted for

two systems to establish a connection, the key distribution center provides a

one-time session key for that connection.

Front-end processor. The front-end processor performs end-to-end encryption

and obtains session keys on behalf of its host or terminal.

The steps involved in establishing a connection are shown in the figure. When

one host wishes to set up a connection to another host, it transmits a connectionrequest

packet (step 1). The front-end processor saves that packet and applies to

the KDC for permission to establish the connection (step 2). The communication

between the FEP and the KDC is encrypted using a master key shared only by the

FEP and the KDC. If the KDC approves the connection request, it generates the

session key and delivers it to the two appropriate front-end processors, using a

unique permanent key for each front end (step 3). The requesting front-end processor

can now release the connection-request packet, and a connection is set up

between the two end systems (step 4). All user data exchanged between the two end

systems are encrypted by their respective front-end processors using the one-time

session key.

The automated key distribution approach provides the flexibility and dynamic

characteristics needed both to allow a number of terminal users to access a number

of hosts and for the hosts to exchange data with each other.

Of course, another approach to key distribution uses public-key encryption,

which is discussed in Section 18.4.

Traffic Padding

We mentioned that, in some cases, users are concerned about security from traffic

analysis. With the use of link encryption, packet headers are encrypted, reducing

the opportunity for traffic analysis. However, it is still possible in those circumstances

for an attacker to assess the amount of traffic on a network and to observe

the amount of traffic entering and leaving each end system. An effective countermeasure

to this attack is traffic padding, illustrated in Figure 18.9.

Traffic padding is a function that produces ciphertext output continuously,

even in the absence of plaintext. A continuous random data stream is generated.

When plaintext is available, it is encrypted and transmitted. When input plaintext is

not present, the random data are encrypted and transmitted. This makes it impossible

for an attacker to distinguish between true data flow and noise, and it is therefore

impossible for the intruder to deduce the amount of traffic.

MESSAGE AUTHENTICATION AND HASH FUNCTION

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 authentication.

Approaches to Message Authentication

A message, file, document, or other collection of data is said to be authentic when

it is genuine and actually coming from its alleged source. Message authentication is

a procedure that allows communicating parties to verify that received 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.

Authentication Using Conventional Encryption

It is possible to perform authentication simply by the use of conventional 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 successfully encrypt a

message for the other participant. Furthermore, if the message includes an errordetection

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

time normally expected for network transit.

Message Authentication Without Message Encryption

In this section, we examine several approaches to message authentication that do

not rely on encryption but on a related family of functions. In all of these

approaches, an authentication tag is generated and appended to each message for

transmission. The message itself is not encrypted and can be read at the destination

independent of the authentication function at the destination.

Because the approaches discussed in this section do not encrypt the message,

message secrecy is not provided. Because conventional encryption will provide

authentication, and because it is widely used with readily available products, why

not simply use such an approach, which provides both secrecy and authentication?

[DAVI90] suggests three situations in which message authentication without

secrecy is preferable:

1. There are a number of applications in which the same message is broadcast to

a number of destinations-for example, notification to users that the network

is now unavailable or an alarm signal in a control center. It is cheaper and

more reliable to have only one destination responsible for monitoring authenticity.

Thus, the message must be broadcast in plaintext with an associated

message authentication tag. The responsible system performs authentication.

If a violation occurs, the other destination systems are alerted by a general

alarm.

2. Another possible scenario is an exchange in which one side has a heavy load

and cannot afford the time to decrypt all incoming messages. Authentication

is carried out on a selective basis, with the messages being chosen at random

for checking.

3. Authentication of a computer program in plaintext is an attractive service. The

computer program can be executed without having to decrypt it every time,

which would be wasteful of processor resources. However, if a message authentication

tag were attached to the program, it could be checked whenever

assurance is required of the integrity of the program.

Thus, there is a place for both authentication and encryption in meeting security

requirements.

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 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 18.10). 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,

TCP, and the IS0 transport protocol), then the receiver can be assured of

the proper sequence, as an attacker cannot successfully alter the sequence

number.

A number of algorithms could be used to generate the code. The National

Bureau of Standards, in its publication DES Modes of Operation, recommends the

use of the DES algorithm. The DES algorithm 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 is encryption.

One-way Hash Function.

A variation on the message authentication code that has received much attention

recently 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

tag H(M), sometimes called a message digest, as output. To authenticate a message,

the message digest is sent with the message in such a way that the message digest is

authentic.

Figure 18.11 illustrates three ways in which the message digest can be authenticated.

The message digest can be encrypted using conventional encryption (part

(a)); if it is assumed that only the sender and receiver share the encryption key, then

authenticity is assured. The message can also be encrypted using public-key encryption

(part (b)). 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. Nevertheless, there has been

an interest in developing 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.

Encryption algorithms may be covered by patents. Some encryption algorithms,

such as the RSA public-key algorithm, are patented and must be licensed,

adding a cost.

a Encryption algorithms may be subject to export control. This is true of DES.

Figure 1 8 . 1 1s~h ows a technique that uses a hash function but no encryption

for message authentication. This technique assumes that two communicating parties,

say A and B, share a common secret value SAB. When A has a message to send

to B, it calculates the hash function over the concatenation of the secret value and

the message: MDM = H ( s ~ ~ I IMI)t .th' en sends [MIIMDM]t o B. Because B possesses

SAB, it can recompute H(SABIIM) and verify MDM, and, because the secret

value itself is not sent, it is not possible for an attacker to modify an intercepted

message. As long as the secret value remains secret, it is also not possible for an

attacker to generate a false message.

This third technique, using a shared secret value, is the one adopted for IP

security (described in Lesson 19); it has also been tentatively specified for

SNMPV~.~

Secure Hash Functions

The one-way hash function, or secure hash function, is important not only in message

authentication but in digital signatures. In this section, we begin with a discussion

of requirements for a secure hash function. Then we look at two very simple

hash functions that are not secure, to gain an appreciation of the structure of such

functions. Finally, we examine one of the most important hash functions, MD5.

Hash Function Requirements

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, adapted from a list in [NECH91]:

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 m, it is computationally infeasible to find x such that

H(x) = m.

5. For any given block x, it is computationally infeasible to find y r x with

H(Y) = H(x).

6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y).

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 18.11c), which is not itself 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, he or she obtains the message M and the hash

code MDM = H(SABIIM). The attacker then inverts the hash function to obtain

SABllM = H-'(MD~). Because the attacker now has both M and SABIIM, it is a trivial

matter to recover SAW

The fifth property guarantees that an alternative message hashing to the same

value as a given message cannot be found; this prevents forgery when an encrypted

hash code is used (Figure 18.11b and c). 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. The sixth property protects against a sophisticated

class of attack known as the birthday a t t a ~ k . ~

In addition to providing authentication, a message digest also provides data

integrity. It performs the same function as a frame check sequence: If any bits in the

message are accidentally altered in transit, the message digest will be in error.

Simple Hash Functions

All hash functions operate using the following general principles. The input (message,

file, etc.) is viewed as a sequence of n-bit blocks. The input is processed one

block at a time in an iterative fashion to produce an n-bit hash function.

One of the simplest hash functions is to take the bit-by-bit-exclusive-or

(XOR) of every block; this can be expressed as follows:

Figure 18.12 illustrates this operation. Figure 18.13a is a C program that produces

a 128-bit hash code. This type of code produces a simple parity for each bit

position and is known as a longitudinal redundancy check. It is reasonably effective

for random data as a data integrity check. Each 128-bit hash value is equally likely.

Thus, the probability that a data error will result in an unchanged hash value is 2-12'.

With more predictably formatted data, the function is less effective. For example,

in most normal text files, the high-order bit of each octet is always zero. Therefore,

16 bits in the hash will always be zero, and the effectiveness is reduced to 2-'12.

A simple way to improve matters is to perform a one-bit circular shift, or rotation

on the hash value after each block is processed, as defined in Figure 18.13b.

This has the effect of "randomizing" the input more completely and overcoming

any regularities that appear in the input.

Although the second program provides a good measure of data integrity, it is

virtually useless for data security. Consider the following task of a potential

attacker: Given a hash code, produce a message that yields that hash code. The

attacker would simply need to prepare the desired message and then append a 128-

bit block that forces the new message, plus block, to yield the desired hash code.

Thus, we need a hash algorithm that is a much more complex function of the

input bits.

MD5 Algorithm Description

The MD5 message-digest algorithm, specified in RFC 1321, was developed by Ron

Rivest at MIT (the "R" in the RSA [Rivest-Shamir-Adelman] public-key encryption

algorithm). The algorithm takes as input a message of arbitrary length and produces

as output a 128-bit message digest. The input is processed in 512-bit blocks.

Figure 18.14 depicts the overall processing of a message to produce a digest.

The processing consists of the following steps:

Step 1: Append Padding Bits

The message is padded so that its length in bits is congruent to 448 modulo 512

(length = 448 mod 512). That is, the length of the padded message is 64 bits less

than an integer multiple of 512 bits. Padding is always added, even if the message is

already of the desired length. For example, if the message is 448 bits long, it is

padded by 512 bits to a length of 960 bits. Thus, the number of padding bits is in the

range of 1 to 512.

The padding consists of a single 1-bit followed by the necessary number of

0-bits.

* Step 2: Append Length

A 64-bit representation of the length in bits of the original message (before the

padding) is appended to the result of step 1. If the original length is greater than 264,

then only the low-order 64 bits of the length are used. Thus, the field contains the

length of the original message, modulo 264. The inclusion of a length value at the

end of the message makes more difficult a type of attack known as a padding attack

.

the four rounds are labeled fF, fG, fH, fI, to indicate that each round has the same

general functional structure, f, but depends on a different primitive function

(F, G, H, I).

Each primitive function takes three 32-bit words as input and produces a 32-

bit word output. Each function performs a set of bitwise logical operations; that is,

the nth bit of the output is a function of the nth bit of the three inputs. The functions

are

Step 5: Output

After all L 512-bit blocks have been processed, the output from the Lth stage is the

128-bit message digest.

The MD5 algorithm has the property that every bit of the hash code is a function

of every bit in the input. The complex repetition of the basic functions (F, G,

H, I) produces results that are well mixed; that is, it is unlikely that two messages

chosen at random, even if they exhibit similar regularities, will have the same hash

code. Rivest conjectures in the RFC that MD5 is as strong as possible for a 128-bit

hash code; namely, the difficulty of coming up with two messages having the same

message digest is on the order of 2^64 operations, whereas the difficulty of finding a

message with a given digest is on the order of 2128 operations. As of this writing, no

analysis has been done to disprove these conjectures.