Efficient Security Mechanisms for

Multicast and Group Communication

V. Zorkadis

Computer Science, Hellenic Open University,

Data Protection Authority

Omirou 8 (6th floor), 105 64 Athens

GREECE

Abstract: -Propertiessuchas security, performance and robustness characterize the quality of services provided by distributed systems. However, security mechanisms may degrade the system performance due to the security-related processing and the communication of security-related data. In this paper, we try to compensate the tradeoff between security and performance requirements in multicast and group communication. We present optimization concepts, which refer to authentication and integrity, digital signatures and confidentiality mechanisms. These concepts mainly base on precomputation capabilities, which become feasible due to appropriate security functions. The efficient security mecahnisms examined in this paper may lead to an elimination of the performance degradation caused by security mechanisms, which is particularly important for secure high-performance or real-time applications.

Key words: Secure Group Communication, Secure Multicast Communication, High-Performance Security Mechanisms, Quality of Service, Performance Optimization

1 Introduction

Authentication of interacting entities, data confidentiality and integrity, prevention of unauthorized transmissions and receptions and utilization of the system resources according to the security policy may be required by application management in a distributed systems environment [1]. These security services rely on mechanisms like encryption and checksum exchange that may result in degradation of the system performance due to the processing and transmission of the security-related data. This paper refers to mechanisms, that may be employed to securing the communication among processes in a distributed system environment, and aims to reduce the performance degradation. The organization of the paper is as follows. In this section we present communication mechanisms in distributed systems, and mechanisms required to securing the communication. In the second section, we discuss optimization concepts, that offer the security functionality and efficiency required in a distributed systems environment. In the third section we evaluate the performance behavior of the proposed secure communication mechanisms and assess the performance benefit we may achieve by means of the concepts presented in the second section. Finally, we summarize the paper with conclusions and future research directions.

In distributed systems may be supported various forms of communication such as group communication and remote procedure call (RPC). As an example of such a communication form we can consider the reliable broadcast or multicast protocol for group communication in the Amoeba [2]. Reliable multicast or broadcast means that when a user process sends a message to the group this message is correctly delivered to all members of the group, even though the transmission components may lose packets [2]. In Fig. 1 is shown the hardware/software configuration required for reliable group communication [2]. The elected as a sequencer machine has a special role. One of the possible methods that may be employed to achieve reliable group communication can be briefly described as follows (see [2] and the references therein). When an application, for instance in the machine C (Fig. 1), wants to send a message to the group, its kernel sends it first to the machine A which is elected as the sequencer. The sequencer, after it gets the message, it allocates for it the next available sequence number, puts the sequence number in the protocol header, and broadcasts or multicasts it to the group. By means of the sequence numbers and further parameters such as unique message identifiers can the kernels check whether they received all the messages sent to the applications the kernels act for.

Fig. 1 System structure for group communication in Amoeba [2].

Processes in a distributed systems environment may require for their communication various security services that fall according to ISO/OSI 7498-2 [3] in five classes: authentication, access control, confidentiality, integrity, and non-repudiation. Authentication services ensure entities, that their peer entities and/or the source of data received are as claimed. Access control protects against unauthorized use of system resources, e. g., files, processing nodes, communication channels, etc. Confidentiality services protect against unauthorized disclosure of application-related and/or traffic-related data. Data integrity protects against active threats like data modification. Often, in the bibliography authentication is used with the meaning of both ISO/OSI-related definitions of authentication and integrity. Finally, non-repudiation provides the recipient and/or the sender of data the proof of the origin and/or delivery and the integrity of the data.

2 Optimization Concepts

Encryption is the basic security mechanism by means of which almost all security services may be implemented by its own such as confidentiality or in combination with further mechanisms such as non-repudiation.

The key elements of the optimization concepts we propose in this paper are the encryption and decryption functions that rely, in some way, on strong (pseudo) random number sequences. For the computation of strong pseudorandom numbers, generators like ANSI X.9.17 may be used, which makes use of triple DES for encryption [4, 5, 6, 7, 8] or the output feedback mode of symmetric cryptosystems, for instance IDEA [9] or AES, in combination with an initialization value and a key.

2.1 Optimization concepts for data confidentiality mechanisms

Group communication protocols [10, 11, 12] such as the multicast or broadcast communication in AMOEBA [2] or communication that bases on the connection-oriented transport protocol (ISO 8073, [13]) are highly reliable. In a highly reliable environment the problem of resynchronization is eliminated, since data loss is handled by the underlying communication mechanisms. The communication mechanisms deliver the messages correctly to all members of the group, even though the transmission components may lose packets [2]. The communicating peers, or the members of a group, have to agree, at connection set up or the registration of a group communication, upon which strong (pseudo) random bit generator algorithm to use and how to calculate and how often to change the initialization variables. In the case of the reliable group communication in AMOEBA the elected sequencer adds to each message a sequence number and maintains a history buffer with a number of messages sent most recently and their corresponding sequence numbers. This sequence number , which is unique for each message, along with the secret key may be exploited by the security mechanism to compute the initialization variable and the random bit string required for the encipherment of the message and the decipherment of the corresponding cipher . For instance, it could be when using IDEA or AES in an OFB-like operation mode to compute the under the secret key . The sender and the receiver proceed as follows.

Since the pseudorandom bit sequences must not be dependent on the message to be enciphered, it may be generated in advance, i.e., before the ‘send message’ service is called. For instance, when we use IDEA in the OFB [9], we can calculate a random bit string by means of an initial variable and the cryptographic key. The message is then XOR-ed with this random bit string, which results to the message cipher. The receiver takes the message in clear from the cipher by XOR-ing with the same random bit string. We may formally describe the encryption and decryption functions as follows:

Encipherment: The sender generates asynchron the random bit strings. Upon arrival of a ‘send message’-request and after the corresponding was calculated, the message and the are tied by the XOR-Operation. The result of the XOR-Operation is the cipher, which is sent to the receiver.

Decipherment: The receiver generates asynchron the random bit strings. Upon arrival of a ‘receive enciphered message‘-request and after the corresponding was calculated, the cipherand the tied by the XOR-Operation. The result of the XOR-Operation is the message.

Furthermore, asymmetric algorithms may be used for confidentiality purposes, although the computation of the powers required introduces a significant delay. In this case, too, the time for encipherment and decipherment experienced by a message can be significantly reduced if we appropriately modify the cryptographic functions to only provide functionality comparable to that provided by symmetric cryptosystems. At the beginning of the communication session the sequencer sends to all members of the group (or the group members exchange), securely, a large prime, a generation primitive , an encryption and a decryption key and the identifier of a strong random bit generator . The decryption key is calculated as follows: . Now, an effective confidentiality scheme by using asymmetric algorithms is as follows:

Encipherment: The sender calculates in advance and . Upon arrival of a ‘send message block ’-request he computes and sends it to the group members.

Decipherment: The receiver, upon arrival of a ‘receive enciphered message block ‘-request, calculates , which is the quantity . The reciever obtains mi, somputing, since and thus, .

According to this confidentiality scheme, only one modular multiplication and one XOR- operation is required for encipherment and decipherment of each message block.

The above cryptographic functions for encipherment and decipherment allow exploiting the stochastic nature of ‘send and receive message’ requests in distributed systems. Therefore, the precomputation of the random sequences required for encipherment and decipherment of messages becomes possible, so that the messages experience as delay only the time required for the xor-operation and/or the time for the modular multiplication operation.

Also, data origin authentication or integrity mechanisms can be constructed that base on similar cryptographic functions, in order to improve the performance behavior of secure group communication. In the following we describe such security mechanisms for data authentication and integrity.

2.2 Concept for data integrity and data origin authentication

We refer to data authentication or integrity mechanisms that employ hash functions to compute a message digest [15, 16], what is signed by the sender to protect against relevant attacks. The computation of the signature is time-consuming comparing with the computation of the hash value, which can be performed very fast. In the reliable group communication, the sender can compute in advance the signature, , of the sequence number or the unique message identifier, concatenated with a random number and a timestamp, that may be valid for the whole duration of the session if the sequence numbers are monotonically increased. When the application process passes the message to be send to the group communication mechanism, the communication mechanism can compute, by means of a hash function, , a digest, , of the message concatenated by the sequence number, the timestamp and the random number.

1The sender precomputes:

, is the encipherment function with the secret key of the sender. Combining timestamps and random numbers we may strengthen the mechanism and prevent future replay attacks.

2When the message to be sent is ready, the sender computes:

and and sends to the receiver, the message , maybe enciphered, appended by and by the, if it is not negotiated at the beginning of the session. The must be sent enciphered at least the first time if it is used for the communication of several messages, unless there is a rule negotiated between the communicating entities for their generation.

3The receiver upon receipt of the message , , and and the enciphered , computes the , derives and deciphers it with the public key of the sender , . If , and the receiver accepts the message as authentic, since only the member who possesses the secret key can compute the .

The digest of the message is tied up with a sequence number, a timestamp and a random number, that are possibly unique for each message, so replacement of the message by a bogus one is not possible without detection. We think, the uniqueness of the timestamps and the random numbers may not be required for each message. In this case, each sender needs to send only once the enciphered value of the random number. The use only of random numbers does not help detect replay attacks in a future session, since an attacker could store und try to use them in future group sessions by impersonating himself as the group member who possesses the secret key with which the was computed. Therefore, timestamps should be used along with random numbers, unless the use of random numbers is combined with challenge/response mechanisms.

In the case of data origin authentication and integrity, the time for encipherment experienced by a message can be significantly reduced, too, if we exploit Schnorr’s preprocessing technique for digital signatures [9] taking into consideration of enabled attacks [10]. In the following we describe first this technique and then modify it to adapt for data authentication and signature mechanisms.

The communicating users have exchanged a large prime and a prime that devides . Also, a primitive qth root of unity , and a security parameter[10]. It is suggested that and are in the order of 512 and 140 bits, respectively, and [9]. Each user has a secret and a public key, and , respectively. The identification protocol is as follows: The sender computes and sends it to the receiver, where is a random number. The receiver returns a random number . Next, the sender computes and sends to the receiver . Finally, the receiver calculates and accepts if [10]. This mechanism is extended to a message authentication mechanism. If denotes a hash function, as above, and , then the signature consists of . The message will be accepted as authentic by the receiver if , where and . According to the preprocessing algorithm, a set of random numbers is chosen and the corresponding is precomputed. Each user stores pairs , where is a security parameter and for each signature, the pair is chosen as a combination of the stored [9, 10]. In [10] an attack of signature schemes employing this type of preprocessing is described, whose complexity in terms of the security parameter is expressed. An obvious way to cope with this attack would be a significantly greater value for the security parameter .

We may simply modify this signature scheme, if we require that the sender (or signer/prover) precompute, in advance, pairs of . So, when a message digest is to be signed, the sending process computes and and sends the signature along with the message and the quantity. The receiver (or verifier) can check the validity of the signature as above. Each ith pair is used once for the computation of the ith signature.

3 Performance Analysis Results

We model a security mechanism facility as a single-server queueing system and messages to be protected by confidentiality, integrity and data origin authentication mechanisms as jobs. The precomputing possibility of the described mechanisms is modeled by a preprocessing property we introduce to a queueing system [18, 19, 20, 21, 22, 23]. Therefore, we consider an M/G/1 [18, 20, 22, 23] queueing system that has the additional capability to carry out work for a job prior to its arrival, when the server would be otherwise idle. When the server completes the work for a job, which can be accomplished prior to its arrival, the server enters in an idle period. For instance, the generation of the strong (pseudo) random bit sequences or the computation of modular exponentiations and encryption operations can be performed in advance. The restriction, only for one job in advance to accomplish work, will be removed by simulation experiments. For the analysis of the M/G/1 system with the preprocessing property we can use results obtained in [21] for the M/G/1 queue with exceptional first service.

The system with the preprocessing property acts exactly as a classical queueing system as long as there are jobs present in the system [22]. At the instant of time the last job in the system leaves, the system begins to accomplish work for the job next to arrive. When the whole work of a job is accomplished prior to its arrival, when regarding constant service times, the system becomes idle. We further partially assume that the time for the xor-operation can be neglected, compared to the time required for the generation of the random bit sequences or the computation of the hash values or the computation of modular exponentiation or multiplication. However, the analysis we present does not require this restriction.

Let , , , and be the probability density functions (pdf) of the random variables describing the interarrival times, the ordinary service time of the conventional system, the service time of the system with the precomputing property and the service time conditioned on the case that the server is idle or busy with preserving a job, respectively. The analysis of this model leads to the following results [22]:

is the the mean delay and the mean waiting time. and are the first and the second moment of service time in the system with the precomputing property, and is the part of , which cannot be accomplished prior to the arrival of a job.

Next, we will present numerical examples based on the formulas above and simulation results by removing the restriction only work for one job to accomplish in advance, when there is no job in the system. Additionally, the simulation results serve as validation means of the previous mathematical analysis as well.

Fig. 2 shows the performance behavior of the ordinary system and the system with the preprocessing property, for various utilization values and for msec in the case of an M/D/1 system with msec. As we expect for low utilized system the average delay in the system with the precomputing property is near 2 msec and for high utilization values we have almost no performance benefit when comparing with the ordinary system, since the benefit remains constant and the delays increase exponentially.