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.

The universal technique for providing
confidentiality for transmitted data is __conventional encryption.__

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

encryption

algorithm)

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

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

keys 1 encryption/msec 10 encryptions/msec

32 2^{32} = 4.3 x 10^{9 }2^{31}
ms
= 35.8 mins^{ }2.15 millisecs

56 2^{56} = 7.2 x 10^{16 }2^{55}
ms
= 1142 years 10.01 hours

128 2^{128} = 3.4 x 10^{38 }2^{127}
ms
= 5.4 x 10^{24} years 5.4 x
10^{18} years

168 2^{168} = 3.7 x 10^{50 }2^{167}
ms
= 5.9 x 10^{36} years 5.9 x
10^{30} years

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

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 16^{th}
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 (K_{i}) 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,

L_{i
}= R_{i-1}

R_{i} = L_{i-1 }Å f(R_{i-1}, K_{i})

(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 (L_{i}) is simply equal to the
right-hand input to that same iteration (R_{i-1}). The right-hand
output (R_{i}) is the exor of L_{i-1 }and a complex function of
Ri_{-1} and K_{i}. 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(R_{i-1},
K_{i}).

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 K_{16 }on the 1^{st}
iteration, K_{15} on the 2^{nd} iteration, and so on, until K_{1}
is used on the 16^{th} and last iteration.

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

· 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 = E_{k3 }[D _{k2} [E _{K1}
[P]]]

where

E_{k}[X] = encryption
of X using key K

D_{k}[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 = E_{k1 }[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.

·
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__.

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

__Steps:__

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

encryption

algorithm)

__Encryption__

Bob’s private key Bob’s
public key

** **

**Plaintext Encryption Decryption
Plaintext **

** input algorithm Transmitted
ciphertext algorithm output**

(e.g. RSA) (reverse of

encryption

algorithm)

__Authentication__

__ __

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 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 = M^{e} mod n

M = C^{d} mod n = (M^{e})^{d}
mod n = M^{ed }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 10^{100})
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.

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:

19^{5} = 2476099

2476099 mod 119 = 66

Hence the ciphertext is 66

For
decryption,

66^{77} 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.

__ __