Distributed System Security


·        The introduction of distributed systems and the use of networks for carrying data between computers is a major factor that has affected security.


·        Security is a complicated business that wasn't given much thought until uses of computer networks increased and the potential for abuse became interesting (i.e. profitable).


·        Encryption is the most important automated tool for network security. The fundamental approaches are conventional encryption, also known as symmetric encryption, and public-key encryption, also known as asymmetric encryption.

With conventional encryption, twp parties share a single encryption/decryption key. The main challenge is the distribution and protection of the keys.

A public-key encryption scheme involves two keys, one for encryption, and a paired key for decryption. The party that generated the key pair keeps one key private, and the other is made public.


Security Requirements and Attacks


·        Computer and network security address three requirements:

Confidentiality: Requires that the data only be accessible for reading by authorized parties.

Integrity: Requires that only authorized parties can modify data.

Availability: Requires that data are available to authorized parties.


·        Network security threats are passive or active.


·        Passive attacks are in the nature of eavesdropping on, or monitoring of, transmission. The goal of the attacker is to obtain information relating to a communication. Two types of passive attacks are the release of message contents, and traffic analysis.

Release of message contents involves for e.g. the release of a confidential e-mail or the contents of a transferred file.

Traffic analysis is more subtle. We could for e.g. use encryption to encrypt our messages. However, the attacker might still be able to observe the pattern of these messages. The attacker could determine the location and identity of communicating hosts and could observe the frequency and length of the messages being exchanged. This information might be useful in guessing the nature of the communication.

            Passive attacks are very difficult to detect because they do not involve any alteration of data. However, it is possible to prevent these, hence the emphasis is on prevention rather than detection.


·        Active attacks involve some modification of the transmitted data, or the creation of false transmissions and can be subdivided into four categories:

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

Replay involves the passive capture of data 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 the messages are delayed or reordered, to produce an unauthorized effect.

e.g. “Allow John Smith to read confidential file accounts” is modified to mean “Allow Fred Brown to read confidential file accounts.

A denial of service attack prevents or inhibits the normal use or management of communication facilities.

E.g. this attack may have a specific target and may suppress all messages directed to a particular destination (say the security audit service). Another e.g. 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, because to do so would require the physical protection of all communications facilities and paths at all times. Instead, the goal is to detect them and recover from any disruption and delays caused by them. Because detection has a deterrent effect, it may also contribute to prevention.


Confidentiality with Conventional Encryption


The universal technique for providing confidentiality for transmitted data is conventional encryption.


Conventional Encryption, also referred to as symmetric 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.


A conventional encryption scheme has five ingredients:

Plaintext:  This is the original message or data that is fed into the algorithm as input.

Encryption algorithm: which performs various substitutions and transformations on the plaintext.


Secret Key: This 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. For a given message, two different keys will produce two different ciphertexts.


Decryption algorithm: This is the encryption algorithm in reverse. It takes the ciphertext and the secret key and produces the original plaintext.


                               Secret key                                   Secret key


 Plaintext                       Encryption                                                            Decryption                          Plaintext                 

  input                              algorithm     Transmitted ciphertext               algorithm                            output





                                     (e.g. DES)                                                                 (reverse of




Two requirements for secure use of conventional encryption:


1.                 We need a strong encryption algorithm. At a minimum, the algorithm should be such that an opponent who knows the algorithm and has access to on or more ciphertexts would be unable to decipher the ciphertext or figure out the key.

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 with this key is readable.


Two approaches to attacking a conventional encryption scheme:


1.     Cryptanalysis. This attack relies on the nature of the algorithm and some knowledge of the general characteristics of the plaintext or even some sample plaintext-ciphertext pairs.

This attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or deduce the key being used (work backwards from the ciphertext to catch patterns, commonly used characters and words like the, commas etc.)


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


Average time required for exhaustive key search

Key size (bits)       Number of alternative                          Time required at                   Time required at

                                keys                                                        1 encryption/msec                                10 encryptions/msec


                32            232 = 4.3 x 109                                                              231 ms = 35.8 mins  2.15 millisecs


                56            256 = 7.2 x 1016                                                            255 ms = 1142 years               10.01 hours


                128          2128 = 3.4 x 1038                                                          2127 ms = 5.4 x 1024 years      5.4 x 1018 years


                168          2168 = 3.7 x 1050                                                          2167 ms = 5.9 x 1036 years      5.9 x 1030 years





It can be seen from the table that a 56-bit key is no longer computationally secure.


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. An important conventional algorithm is the DES, which is a block cipher.


The Data Encryption Standard (DES)

The algorithm itself is referred to as the Data Encryption Algorithm (DEA).

Figure 18.3 page 655, Stallings.


The plaintext must be 64 bits in length and the key is 56 bits in length; longer plaintext amounts are processed in 64-bit blocks.


The left-hand side of the figure shows that the processing of the plaintext has three phases. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits to produce the permuted input. This is followed by a phase that has 16 iterations of the same function. The output of the 16th iteration consists of 64 bits that are a function of the input plaintext and the key. The left and right halves of the output are swapped to produce the pre-output.  Finally, the pre-output is passed through a permutation (IP-1) that is the inverse of the initial permutation function, to produce the 64-bit ciphertext.


The right hand portion of the figure 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 sub-key (Ki) is produced by the combination of a left circular shift a permutation. The permutation function is the same for each iteration, but a different sub-key is produced because of the repeated shifting of the key bits.


Figure 18.4 page 656 (Single round of  DES algorithm)


The 64-bit permuted input passes through 16 iterations, producing an intermediate 64-bit value at the end of each iteration. The left and right halves of each 64-bit intermediate value are treated as separate 32-bit quantities, labeled L (left) and R (right). The overall processing is,


                      Li = Ri-1

                   Ri = Li-1 Å f(Ri-1, Ki)


(E.g. the value of the left 32-bit key in iteration 1 (i) is the same as the value of the right 32-bit key in iteration 0 (i-1)).

Thus, the left-hand output of an iteration (Li) is simply equal to the right-hand input to that same iteration (Ri-1). The right-hand output (Ri) is the exor of Li-1 and a complex function of Ri-1 and Ki.  This complex function involves both permutations (expansion from 32-bits to 48-bits) and substitution operations. The substitution operation, represented as tables called “S-boxes”, maps each combination of 48-bits into a 32-bit pattern.


The 56-bit key used as input to the algorithm is subjected to a permutation. The resulting 56-bit key is then treated as two 28-bit quantities, labeled C0 and D0. At each iteration, C and D are separately subjected to a left circular shift, or rotation, of 1 or 2 bits. These shifted values serve as input to the next key iteration. They also serve as input to another permutation function, which produces a 48-bit output that serves as input to the function

f(Ri-1, Ki).


The process of decryption with DES is essentially the same as the encryption process. The rule is: use the ciphertext as input to the DES algorithm, but use the keys in the reverse order. That is, use K16 on the 1st iteration, K15 on the 2nd iteration, and so on, until K1 is used on the 16th and last iteration.


Strength of DES


Rising processor speed and falling hardware costs have made it simple to break DES. Hence we need to consider alternatives to DES.

Triple DEA (TDEA)


·        TDEA was incorporated as part of DES in 1999.


·        TDEA uses three keys and three executions of the DES algorithm. The function follows an encrypt-decrypt-encrypt (EDE) sequence:


C = Ek3 [D k2 [E K1 [P]]]


                   C = ciphertext
                   P = plaintext

                   Ek[X] = encryption of X using key K

                   Dk[X] = decryption of Y using key K


          There is no cryptographic significance to the use of decryption for the second stage. Its only advantage is that it allows users of triple DES to decrypt data encrypted by users of the older single DES:


                   C = Ek1 [D k1 [E K1 [P]]]


          With three distinct keys, TDEA has an effective key length of 168 bits. The standard also allows for the use of two keys, with K1 = K3; this provides for a key length of 112 bits.


Location of Encryption Devices



·        We need to decide what to encrypt and where the encryption gear should be located. There are two alternatives: link level encryption or end-to-end encryption.


Link-level security

Each link is equipped on both ends with an encryption device. Thus, all traffic over all communications links is secured. Although this requires a large number of encryption devices in a large network, it provides a high level of security. One disadvantage is that the message must be decrypted each time it enters a PSN/router because the node must read the VC number in the packet header to route the packet. Thus the message is vulnerable at each switch.




End-to-end encryption.

The encryption process is carried out at the two end systems. The source host encrypts the data. The data is then transmitted in encrypted form unaltered as it travels across the network. The destination shares a key with the source and so is able to decrypt the data. This approach seems to be more secure against attacks on the links and switches.


But the source host cannot encrypt the entire packet because only the destination 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. So the host can only encrypt the data and leave the header in the clear. So user data is secure, but the traffic pattern is not because packet headers are transmitted in the clear.


Solution is to use both techniques. The host encrypts the user data 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 to read the header and then encrypts the entire packet again for sending 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.


Public-Key Encryption and Digital Signatures


Public-key encryption finds use in message authentication and key distribution.

It is based on mathematical functions rather than on simple operations on bit patterns. More importantly, public-key encryption is asymmetric, involving the use of two separate keys, in contrast to symmetric conventional encryption, which uses only on key.  The use of two keys has its impact in the areas of confidentiality, key distribution, and authentication.


Misconceptions about public-key encryption:

1.                 Public-key encryption is more secure from cryptanalysis than conventional encryption.

The security of any encryption scheme depends on the length of the key and the computational work involved in breaking a cipher. Nothing in principle makes either conventional or public-key encryption superior to another.

2.                 Public-key encryption is a general-purpose technique that has made conventional encryption obsolete.

Because of the computational overhead of current public-key encryption schemes, there seems to be no foreseeable likelihood that conventional encryption will be abandoned.

3.                 Key distribution is trivial using public-key encryption compared to the cumbersome handshaking involved with key distribution centers for conventional encryption.

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


Public-key encryption has six ingredients:


Plaintext: This is the readable message or data that is fed into the algorithm as input.


Encryption algorithm


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 public key of the pair is made public for others to use, while only its owner knows the private key.


Ciphertext: This is the scrambled message produced as output.


Decryption algorithm


These algorithms have the following characteristics:


It is computationally infeasible to determine the decryption key given only knowledge of the cryptographic algorithm and the encryption key.


For most public-key schemes, either of the two related keys can be used for encryption, with the other used for decryption.



1.                  Each user generates a pair of keys.

2.                  Each user places one of the two keys in a public register or accessible file. This is the public key. The companion key is kept private. 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 with 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.


At any time, a user can change the private key and publish the companion public key to replace the old public key.


                   Alice’s public key                     Alice’s private key


 Plaintext                       Encryption                                                            Decryption                          Plaintext                 

  input                              algorithm     Transmitted ciphertext               algorithm                            output





                                     (e.g. RSA)                                                                 (reverse of






Digital Signature



                   Bob’s private key                     Bob’s public key


 Plaintext                       Encryption                                                            Decryption                          Plaintext                 

  input                              algorithm     Transmitted ciphertext               algorithm                            output





                                     (e.g. RSA)                                                                 (reverse of





Suppose that Bob wants to send a message to Alice and, although it is not important that the message be kept secret, he wants Alice to be certain that the message is indeed from him. So Bob uses his own private key to encrypt the message. When Alice receives the ciphertext, she finds that she can decrypt it with Bob’s public key, thus proving that Bob must have encrypted the message. Therefore, the entire encrypted message serves as a digital signature. In addition, it is impossible to alter the message without access to Bob’ private key, so the message is authenticated both in terms of source and in terms of data integrity.


Note: the encryption process just described does not provide confidentiality. That is, the message being sent is safe from alteration but is not safe from eavesdropping because any observer can decrypt the message by using the sender’s public key.


The RSA Public-Key Encryption Algorithm


The RSA algorithm was developed by Rivest, Shamir, Adleman at MIT in 1978.  This is the most important commercial public key technology and is sold by a company called RSA Security.


It 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:


                        C = Me mod n

                   M = Cd mod n = (Me)d mod n = Med mod n


Both the sender and receiver must know the values of n and e, and only the receiver knows the value of d. This is a public-key encryption algorithm with a public key of KU = {e, n} and a private key of KR = {d, n}.


First you need the following:


   1.Select two large (greater than 10100) prime numbers, p and q

   2.Compute n = p * q, and z = (p-1) * (q-1).

   3.Choose a number relatively prime to z and call it e (e and z must have no

      common factors other than 1)

   4. Find d such that d e  = 1 mod z and d < z. 


When you multiply two large primes you get a number with only two factors. Because factoring a large number is very expensive, you have effectively hidden p and q in the product n, which you can safely make public.


RSA example


     1.  Select p = 7, q = 17

     2.  n = p * q = 7 x 17 = 119

     3.  Calculate z = (p-1) * (q-1) = 96

     4.  Select e such that e is relatively prime to z = 96 and less than z ; in this case, e = 5.

      5.          Determine d such that de = 1 mod 96 and d < 96. The correct value is d = 77, because 77 x 5 = 385 = 4 x 96 + 1 (i.e. 385 mod 96 = 1)

The resulting keys are public key KU = {5, 119} and private key KR = {77, 119}


To encrypt a message with a plaintext input of M = 19:


195 = 2476099

2476099 mod 119 = 66

Hence the ciphertext is 66


For decryption,

6677 mod 119 = 19


To break the encryption you must factor n to its two prime numbers p and q, hence z, and then use Euclid's algorithm to get e. RSA have calculated that it

would take 4 billion years of compute time using the best algorithm and a 1 usec calculation time to factor a 200-digit number.


The only problem with RSA is that it is slow to encrypt large messages (100 to 1000 times slower than a secret key approach).


In practice what is done is that a secret key algorithm is used to encrypt the data, and the secret key is sent to the receiver encrypted with the RSA algorithm.