PUBLIC-KEY ENCRYPTION AND DIGITAL SIGNATURES

PUBLIC-KEY ENCRYPTION AND DIGITAL SIGNATURES

Of equal importance to conventional encryption is public-key encryption, which

finds use in message authentication and key distribution. This section looks first

at the basic concept of public-key encryption, followed by a discussion of the

most widely used public-key algorithm: RSA. We then look at the problem of key

distribution.

Public-Key Encryption

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. For one thing, public-key algorithms are based on mathematical

functions rather than on substitution and permutation. But more importantly, publickey

cryptography is asymmetric, involving the use of two separate keys, in contrast

to the conventional 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 mention several common misconceptions concerning

public-key encryption. One such misconception is that public-key encryption

is more secure from cryptanalysis than conventional encryption. In fact, the

security of any encryption scheme depends on the length of the key and the computational

work involved in breaking a cipher. There is nothing in principle about

either conventional 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 conventional

encryption obsolete. On the contrary, because of the computational overhead of

current public-key encryption schemes, there seems no foreseeable likelihood that

conventional 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 conventional

encryption. In fact, some form of protocol is needed, often involving a central agent,

and the procedures involved are no simpler nor any more efficient than those

required for conventional encryption.

A public-key cryptographic algorithm relies on one key for encryption and a

different but related key for decryption. Furthermore, these algorithms have the

following important characteristic:

* It is computationally infeasible to determine the decryption key given only

knowledge of the cryptographic algorithm and the encryption key.

In addition, some algorithms, such as RSA, also exhibit the following characteristic:

Either of the two related keys can be used for encryption, with the other used

for decryption.

The essential steps are the following:

Each end system in a network generates a pair of keys to be used for encryption

and decryption of messages that it will receive.

Each system publishes its encryption key by placing it in a public register or

file. This is the public key. The companion key is kept private.

If A wishes to send a message to B, it encrypts the message using B's public

key.

When B receives the message, it decrypts it using B's private key. No other

recipient can decrypt the message because only B knows B'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 system controls its private key, its incoming communication is

secure. At any time, a system can change its private key and publish the companion

public key to replace its old public key.

Figure 18.16 illustrates the process (compare Figure 18.3). There is some

source A for a message, which produces a message in plaintext, X = [XI, X2, . . .,

XM] The M elements of X are letters in some finite alphabet. The message is

intended for destination B, which generates a related pair of keys: a public key KUb,

and a private key, KRb. KRb is secret, known only to B, whereas KUb is publicly

available, and therefore accessible by A.

With the message X and the encryption key KUb as input, A forms the ciphertext

Y = [Y,, Y2, . . ., YN]:

The intended receiver, in possession of the matching private key, is able to

invert the transformation:

An opponent, observing Y and having access to KUb, but not having access to

KRb or X, must attempt to recover X and/or KRb. It is assumed that the opponent

does have knowledge of the encryption (E) and decryption (D) algorithms.

We mentioned earlier that either of the two related keys can be used for

encryption, with the other being used for decryption. This enables a rather different

cryptographic scheme to be implemented. Whereas the scheme illustrated in Figure

18.16 provides privacy, Figure 18.17 shows the use of public-key encryption to provide

authentication:

In this case, A prepares a message to B and encrypts it using A's private key

before transmitting it. B can decrypt the message using A's public key. Because the

message was encrypted using A's private key, only A could have prepared the message.

Therefore, the entire encrypted message serves as a digital signature. In addition,

it is impossible to alter the message without access to A's private key, so the

message is authenticated both in terms of source and in terms of data integrity.

In the preceding scheme, the entire message is encrypted, and, although it

validates both author and contents, the encryption requires a great deal of storage;

each document must be kept in plaintext to be used for practical purposes, and a

copy also must be stored in ciphertext so that the origin and contents can be verified

in case of a dispute. A more efficient way of achieving the same results is to

encrypt a small block of bits that is a function of the document. Such a block, called

an authenticator, must have the property that it is infeasible to change the document

without changing the authenticator. If the authenticator is encrypted with the

sender's private key, it serves as a signature that verifies origin, content, and

sequencing. A secure hash code can serve this function.

It is important to emphasize that the encryption process just described 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, as 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.

The RSA Public-Key Encryption Algorithm

One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi

Shamir, and Len Adleman at MIT, and first published in 1978 [RIVE78]. The RSA

scheme has since reigned supreme as the only widely accepted and implemented

approach to public-key encryption. RSA is a block cipher in which the plaintext and

ciphertext are integers between 0 and n-1 for some n.

Encryption and decryption are of the following form, for some plaintext block

M and ciphertext block C:

There are two possible approaches to defeating the RSA algorithm. The first

is the brute force approach: Try all possible private keys. Thus, the larger the number

of bits in e and d, the more secure the algorithm. However, because the calculations

involved, both in key generation and in encryptionldecryption, are complex,

the larger the size of the key, the slower the system will run.

Most discussions of the cryptanalysis of RSA have focused on the task of factoring

n into its two prime factors. Until recently, this was felt to be infeasible for

numbers in the range of 100 decimal digits or so, which is about 300 or more bits.

To demonstrate the strength of RSA, its three developers issued a challenge to

decrypt a message that was encrypted using a 129-decimal-digit number as their

public modulus. The authors predicted that it would take 40 quadrillion years with

current technology to crack the code. Recently the code was cracked by a worldwide

team cooperating over the Internet and using over 1600 computers after

only eight months of work [LEUT94]. This result does not invalidate the use of

RSA; it simply means that larger key sizes must be used. Currently, a 1024-bit

key size (about 300 decimal digits) is considered strong enough for virtually all

applications.

Key Management

With conventional encryption, a fundamental requirement for two parties to communicate

securely is that they share a secret key. Suppose Bob wants to create a

messaging application that will enable him to exchange e-mail securely with anyone

who has access either to the Internet or to some other network that the two of them

share (e.g., an on-line service such as Compuserve). Suppose Bob wants to do this

using only conventional encryption. With conventional encryption, Bob and his correspondent,

say, Alice, must come up with a way to share a unique secret key that

no one else knows. How are they going to do that? If Alice is in the next room from

Bob, Bob could generate a key and write it down on a piece of paper or store it on

a diskette and hand it to Alice. But if Alice is on the other side of the continent, or

maybe the world, what can Bob do? Well, he could encrypt this key using conventional

encryption and e-mail it to Alice, but this means that Bob and Alice must

share a secret key in order to encrypt this new secret key. Furthermore, Bob

and everyone else who use this new e-mail package face the same problem with

every potential correspondent: Each pair of correspondents must share a unique

secret key.

How to distribute secret keys securely is the most difficult problem for conventional

encryption. This problem is wiped away with public-key encryption by the

simple fact that the private key is never distributed. If Bob wants to correspond with

Alice and other people, he generates a single pair of keys, one private and one public.

He keeps the private key secure and broadcasts the public key to all and sundry;

if Alice does the same, then Bob has Alice's public key, Alice has Bob's public key,

and they can now communicate securely. When Bob wishes to communicate with

Alice, Bob can do the following:

I. Prepare a message.

2. Encrypt that message using conventional encryption with a one-time conventional

session key.

3. Encrypt the session key using public-key encryption with Alice's public key.

4. Attach the encrypted session key to the message and send it to Alice.

Only Alice is capable of decrypting the session key and therefore recovering

the original message.

It is only fair to point out, however, that we have replaced one problem with

another. Bob's private key is secure as he need never reveal it; however, Alice must

be sure that the public key with Bob's name written all over it is in fact Bob's public

key. Someone else could have broadcast a public key and said it was Bob's. The

common way to overcome this problem is ingenious: Use public-key encryption to

authenticate the public key. This encryption assumes the existence of some trusted

signing authority or individual, and works as follows:

I. A public key is generated by Bob and submitted to Agency X for certification.

2. X determines by some procedure, such as a face-to-face meeting, that this is,

authentically, Bob's public key.

3. X appends a timestamp to the public key, generates the hash code of the

result, and encrypts that result with its private key forming the signature.

4. The signature is attached to the public key.

Anyone equipped with a copy of X's public key can now verify that Bob's public

key is authentic.

 IPv4 AND IPv6 SECURITY

In August 1995, the IETF published five security-related Proposed Standards that

define a security capability at the internet level. The documents are

RFC 1825: An overview of a security architecture

RFC 1826: Description of a packet authentication extension to IP

RFC 1828: A specific authentication mechanism

e RFC 1827: Description of a packet encryption extension to IP

0 RFC 1829: A specific encryption mechanism

Support for these features is mandatory for IPv6 and optional for IPv4. In both

cases, the security features are implemented as extension headers that follow the

main IP header. The extension header for authentication is known as the Authentication

header; the one designated for privacy is known as the Encapsulating Security

Payload (ESP) header.

Security Associations

A key concept that appears in both the authentication and privacy mechanisms for

IP is the security association. An association is a one-way relationship between a

sender and a receiver. If a peer relationship is needed, for two-way secure exchange,

then two security associations are required.

A security association is uniquely identified by an internet address and a security

parameter index (SPI). Hence, in any IP packet,"he security association is

uniquely identified by the Destination Address in the IPv4 or IPv6 header and the

SPI in the enclosed extension header (Authentication header or Encapsulating

Security Payload header).

A security association is normally defined by the following parameters:

Authentication algorithm and algorithm mode being used with the IP Authentication

Header (required for AH implementations).

Key(s) used with the authentication algorithm in use with the Authentication

Header (required for AH implementations).

Encryption algorithm, algorithm mode, and transform being used with the IP

Encapsulating Security Payload (required for ESP implementations).

Key(s) used with the encryption algorithm in use with the Encapsulating

Security Payload (required for ESP implementations).

Presencelabsence and size of a cryptographic synchronization or initialization

vector field for the encryption algorithm (required for ESP implementations).

Authentication algorithm and mode used with the ESP transform, if any is in

use (recommended for ESP implementations).

Authentication key(s) used with the authentication algorithm that is part of

the ESP transform, if any (recommended for ESP implementations).

Lifetime of the key or time when key change should occur (recommended for

all implementations).

Lifetime of this Security Association (recommended for all implementations).

Source Address(es) of the Security Association, might be a wildcard address

if more than one sending system shares the same Security Association with

the destination (recommended for all implementations).

Sensitivity level (for example, Secret or Unclassified) of the protected data

(required for all systems claiming to provide multi-level security, recommended

for all other systems).

The key management mechanism that is used to distribute keys is coupled to

the authentication and privacy mechanisms only by way of the Security Parameters

Index. Hence, authentication and privacy have been specified independently of any

specific key-management mechanism.

Authentication

The Authentication header provides support for data integrity and authentication

of IP packets. The Authentication Header consists of the following fields (Figure

18.20):

Next Header (8 bits). Identifies the type of header immediately following this

header.

Length (8 bits). Length of Authentication Data field in 32-bit words.

Reserved (16 bits). For future use.

Security Parameters Index (32 bits). Identifies a security association.

e Authentication Data (variable). An integral number of 32-bit words.

The authentication data field contents will depend on the authentication algorithm

specified. In any case, the authentication data is calculated over the entire IP

packet, excluding any fields that may change in transit. Such fields are set to zero

for purposes of calculation at both source and destination. The authentication calculation

is performed prior to fragmentation at the source and after reassembly

at the destination. Hence, fragmentation-related fields can be included in the

calculation.

For IPv4, the Time-to-Live and Header Checksum fields are subject to change

and are therefore set to zero for the authentication calculation. IPv4 options must

be handled in accordance with the rule that any option whose value might change

during transit must not be included in the calculation.

For IPv6, the Hop Limit field is the only field in the base IPv6 header subject

to change; it is therefore set to zero for the calculation. For the Hop-by-Hop

Options and Destination Options headers, the Option Type field for each option

contains a bit that indicates whether the Option Data field for this option

may change during transit; if so, this option is excluded from the authentication

calculation.

Authentication Using Keyed MD5

RFC 1828 specifies the use of MD5 for authentication. The MD5 algorithm is performed

over the IP packet plus a secret key by the source and then inserted into the

IP packet. At the destination, the same calculation is performed on the IP packet

plus the secret key and compared to the received value. This procedure provides

both authentication and data integrity.

Specifically, the MD5 calculation is performed over the following sequence:

key, keyfill, IP packet, key, MD5fill

where

key = the secret key for this security association

keyfill = padding so that key + keyfill is an integer multiple of 512 bits

IP packet = with the appropriate fields set to zero

MD5fill = padding supplied by MD5 so that the entire block is an integer

multiple of 512 bits

Figure 18.21 shows two ways in which the IP authentication service can be

used. In one case, authentication is provided directly between a server and client

workstations; the workstation can be either on the same network as the server or on

an external network. So long as the workstation and the server share a protected

secret key, the authentication process is secure. In the other case, a remote workstation

authenticates itself to the corporate firewall, either for access to the entire

internal network or because the requested server does not support the authentication

feature.

Encapsulating Security Payload

The use of the Encapsulating Security Payload provides support for privacy and

data integrity for IP packets. Depending on the user's requirements, this mechanism

can be used to encrypt either a transport-layer segment (e.g., TCP, UDP,

ICMP), known as transport-mode ESP, or an entire IP packet, known as tunnelmode

ESP.

The ESP header begins with a 32-bit Security Parameters Index (SPI), which

identifies a security association. The remainder of the header, if any, may contain

parameters dependent on the encryption algorithm being used. In general, the first

part of the header, including the SPI and possibly some parameters, is transmitted

in unencrypted (plaintext) form, while the remainder of the header, if any, is transmitted

in encrypted (ciphertext) form.

Transport-Mode ESP

Transport-mode ESP is used to encrypt the data carried by IP. Typically, these data

are a transport-layer segment, such as a TCP or UDP segment, which in turn contains

application-level data. For this mode, the ESP header is inserted into the IP

packet immediately prior to the transport-layer header (e.g., TCP, UDP, ICMP). In

the case of IPv6, if a Destination Options header is present, the ESP header is

inserted immediately prior to that header (see Figure 16.16).

Transport-mode operation may be summarized as follows:

1. At the source, the block of data consisting of a trailing portion of the ESP

header, plus the entire transport-layer segment, is encrypted, and the plaintext

of this block is replaced with its ciphertext to form the IP packet for transmission

(Figure 18.22a).

2. This IP packet is then routed to the destination. Each intermediate router

needs to examine and process the IP header plus any plaintext IP extension

headers, but does not need to examine the ciphertext.

3. The destination node examines and processes the IP header plus any plaintext

IP extension headers. Then, on the basis of the SPI in the ESP header, the destination

node decrypts the remainder of the packet to recover the plaintext

transport-layer segment.

Transport-mode operation provides privacy for any application that uses it,

thus avoiding the need to implement privacy in every individual application. This

mode of operation is also reasonably efficient. adding little to the total length of the

IP packet. One drawback to this mode is that it is possible to do traffic analysis on

the transmitted packets. Figure 18.23a illustrates the protection provided by transport-

mode operation.

Tunnel-Mode ESP

Tunnel-mode ESP is used to encrypt an entire IP packet. For this mode, the ESP is

prefixed to the packet, and then the packet plus a trailing portion of the ESP header

is encrypted. This method can be used to counter traffic analysis.

Because the IP header contains the destination address and possibly source

routing directives and hop-by-hop option information, it is not possible to simply

transmit the encrypted IP packet prefixed by the ESP header. Intermediate routes

would be unable to process such a packet. Therefore, it is necessary to encapsulate

the entire block (ESP header plus encrypted IP packet) with a new IP header that

will contain sufficient information for routing but not for traffic analysis.

Whereas the transport-mode is suitable for protecting connections between

hosts that support the ESP feature, the tunnel-mode is useful in a configuration that

includes a firewall or other sort of security gateway that protects a trusted network

from external networks. In this latter case, encryption occurs only between an external

host and the security gateway, or between two security gateways; this relieves

hosts on the internal network of the processing burden of encryption and also simplifies

the key distribution task by reducing the number of needed keys; further, it

thwarts traffic analysis based on ultimate destination.

Consider a case in which an external host wishes to communicate with a host

on an internal network protected by a firewall, and in which ESP is implemented in

the external host and the firewalls. The following steps occur for transfer of a transport-

layer segment from the external host to the internal host:

1. The source prepares an inner IP packet with a destination address of the target

internal host. This packet is prefixed by an ESP header; then the packet

and a portion of the ESP header are encrypted. The resulting block is encapsulated

with a new IP header (base header plus optional extensions such as

routing and hop-by-hop options) whose destination address is the firewall; this

forms the outer IP packet (Figure 18.22b).

2. The outer packet is routed to the destination firewall. Each intermediate

router needs to examine and process the outer IP header plus any outer IP

extension headers, but does not need to examine the ciphertext.

3. The destination firewall examines and processes the outer IP header plus any

outer IP extension headers. Then, on the basis of the SPI in the ESP header,

the destination node decrypts the remainder of the packet to recover the

plaintext inner IP packet. This packet is then transmitted in the internal

network.

4. The inner packet is routed through zero or more routers in the internal network

to the destination host.

Figure 18.23b shows how tunnel-mode operation can be used to set up a virtual

private network. In this example, an organization has four private networks

interconnected across the Internet. Hosts on the internal networks use the Internet

for transport of data but don't interact with other Internet-based hosts. By terminating

the tunnels at the security gateway to each internal network, the configuration

allows the hosts to avoid implementing the security capability.

The ESP DES-CBC Transform

All implementations that claim conformance with the ESP specification must

implement the DES-CBC (Data Encryption Standard-Cipher Block Chaining)

method of encryption.

Figure 18.24 shows the format of the ESP header plus payload using DESCBC,

and indicates which portions are encrypted. The fields are

@ Security Parameters Index (32 bits). Identifies a security association.

Initialization Vector (variable). Input to the CBC algorithm, and a multiple of

32 bits.

Payload Data (variable). Prior to encryption, this field contains the block of

data to be encrypted, which may be a transport-layer segment (transport

mode) or an IP packet (tunnel mode).

Padding. Prior to encryption, filled with unspecified data to align Pad Length

and Payload Type fields at a 64-bit boundary.

@ Pad Length (8 bits). The size of the unencrypted padding field.

Payload Type (8 bits). Indicates the protocol type of the Payload Data field

(e.g., IP, TCP).

Note that the Initialization Vector is transmitted in plaintext. As was mentioned

in our description of DES-CBC, this is not the most secure approach. However,

for the purposes of this application, it should provide acceptable security.

Authentication Plus Privacy

The two IP security mechanisms can be combined in order to transmit an IP packet

that has both privacy and authentication. There are two approaches that can be

used, based on the order in which the two services are applied.

Encryption Before Authentication

Figure 18.25a illustrates the case of encryption applied before authentication. In

this case, the entire transmitted IP packet is authenticated, including both

encrypted and unencrypted parts. In this approach, the user first applies ESP to the

data to be protected, then prepends the authentication header and the plaintext IP

header(s). There are actually two subcases:

@ Transport-Mode ESP. Authentication applies to the entire IP packet delivered

to the ultimate destination, but only the transport-layer segment is protected

by the privacy mechanism (encrypted).

Tunnel-Mode ESP. Authentication applies to the entire IP packet delivered

to the outer IP destination address (e.g., a firewall), and authentication is performed

at that destination. The entire inner IP packet is protected by the privacy

mechanism, for delivery to the inner IP destination.

Authentication Before Encryption

Figure 18.25b illustrates the case of authentication applied before encryption. This

approach is only appropriate for tunnel-mode ESP. In this case, the authentication

header is placed inside the inner IP packet. This inner packet is both authenticated

and protected by the privacy mechanism.

As we have just seen, the functions of authentication and encryption can be

applied in either order for tunnel-mode ESP. The use of authentication prior to

encryption might be preferable for several reasons. First, because the AH is protected

by ESP, it is impossible for anyone to intercept the message and alter the AH

without detection. Secondly, it may be desirable to store the authentication information

with the message at the destination for later reference. It is more convenient

to perform this storage if the authentication information applies to the unencrypted

message; otherwise, the message would have to be re-encrypted to verify the

authentication information.