8

Digital Signatures and Authentication Protocols

1. What is digital signature? Discuss the various services it provides.

Ans.: A digital signature is an authentication mechanism that allows the sender to attach an electronic code with the message in order to ensure its authenticity and integrity. This electronic code acts as the signature of the sender and, hence, is named digital signature. Digital signatures use the public-key cryptography technique. The sender uses his or her private key and a signing algorithm to create a digital signature, and the signed document can be made public. The receiver, on the other hand, uses the public key of the sender and a verifying algorithm to verify the digital signature.

Digital signatures are analogous to physical handwritten signatures and provide the following security services.

   Message authentication: A normal message authentication scheme protects the two communicating parties against attacks from a third party (intruder). However, a secure digital signature scheme protects the two parties against each other also. Suppose A wants to send a signed message (message with A's digital signature) to B through a network. For this, A encrypts the message using his or her private key, which results in a signed message. The signed message is then sent through the network to B. Now, B attempts to decrypt the received message using A's public key in order to verify that the received message has really come from A. If the message gets decrypted, B can believe that the message is from A. However, if the message or the digital signature has been modified during transmission, it cannot be decrypted using A's public key. From this, B can conclude that either the message transmission has tampered with, or that the message has not been generated by A.

   Message integrity: Digital signatures also provide message integrity. If a message bears a digital signature, then any change in the message after the signature is attached will invalidate the signature. That is, it is not possible to get the same signature if the message is changed. Moreover, there is no efficient way to modify a message and its signature such that a new message with a valid signature is produced. These days, a hash function is used in the signing and verifying algorithms that help in preserving the integrity of the message.

   Nonrepudiation: Digital signatures also ensure nonrepudiation. For example, if A has sent a signed message to B, then in future A cannot deny about the sending of the message. B can keep a copy of the message along with A's signature. In case A denies, B can use A's public key to generate the original message. If the newly created message is the same as that initially sent by A, it is proved that the message has been sent by A only. In the same way, B can never create a forged message bearing A's digital signature, because only A can create his or her digital signatures with the help of that private key.

   Message confidentiality: Digital signatures do not provide message confidentiality, because anyone knowing the sender's public key can decrypt the message. Thus, to achieve message confidentiality, we need to encrypt the message along with the signature using either the secret-key encryption or public-key encryption scheme. For example, if we use the public-key encryption scheme, then at A's end, first the message is encrypted using A's private key and then a second encryption is performed using the B's public key. Similarly, at B's end, first the message is decrypted using B's private key and then a second decryption is performed using A's public key. With this mechanism, only B can decrypt the encrypted message received from A because only B knows his or her private key.

2. Describe the digital signature process with the help of a suitable diagram.

Ans.: The digital signature process is shown in Figure 8.1. Suppose user A wants to send a signed message to B through a network. To achieve this communication, these steps are followed:

  (i) A uses his private key (EA), applied to a signing algorithm, to sign the message (M).

 (ii) The message (M) along with A's digital signature (S) is sent to B.

(iii) On receiving the message (M) and the signature (S), B uses A's public key (DA), applied to the verifying algorithm, to verify the authenticity of the message. If the message is authentic, B accepts the message; otherwise it is rejected.

Figure 8.1 Digital Signature Process

3. How is the use of private and public keys in digital signatures different from that in public-key cryptography?

Ans.: The private and public keys used in public-key cryptography are different from the private and public keys used in digital signatures. In the former case, the public and private keys of the receiver are used for encryption and decryption of the message, respectively. That is, the sender encrypts the message using the receiver's public key, and the receiver decrypts the message using his own private key. However, in digital signatures, the private and public keys of the sender are used to create and verify the digital signature, respectively. That is, the sender creates a digital signature using his or her own private key, and the receiver verifies it using the sender's public key.

4. Can we use a secret (symmetric) key in the digital signature process? Justify your answer.

Ans.: We cannot use a secret (symmetric) key to create and verify digital signatures, due to the following two reasons.

   In symmetric-key cryptosystem, a secret key K is shared between two users only, say A and B. Now, if A wants to send another message to C, then he or she has to use another secret key.

   B could create a forged signed message using the secret key K that is shared between A and B, and send that message to C pretending that it has come from A.

5. What are the essential properties and requirements for a digital signature?

Ans.: A digital signature is used in those situations where there is a lack of trust between the sender and the receiver. For example, suppose a user A transfers funds to B electronically. Now, B in future increases the amount of funds transferred and claims that the larger amount had arrived from A. Thus, to achieve secure communication between the two users and to resolve their disputes if any, digital signature must have the following properties:

   It must be able to verify the author and the date and time of the signature.

   It must be able to authenticate the contents of the message at the time of the signature.

   There must be some third (trusted) party who can verify the digital signature to resolve disputes between the sender and receiver.

Thus, we can say that the authentication function is included within the digital signature function. Based on the these properties, we can list out the following requirements for a digital signature:

   The signature must be in the form of a bit pattern and relative to the message being signed.

   The signature must contain some information that is unique to the sender, so that forgery and denial can be avoided.

   The process of creating the digital signature must be comparatively easy.

   The process of recognizing and verifying the digital signature must also be comparatively easy.

   A high computational effort must be required to forge a digital signature. That is, it must be infeasible for an intruder to create a new message for an existing signature or to create a fake digital signature for an existing message.

   The copy of a digital signature must be retained in some storage mechanism.

6. Discuss the different kinds of attacks on digital signatures.

Ans.: There are three kinds of attacks possible on digital signatures, namely, key-only, known message and chosen-message attack. To get an idea of these attacks, consider A and B as the communicating parties and C as the opponent.

   Key-only attack: In this type of attack, the intruder knows only the public information of A. With the help of this information, the intruder tries to create A's digital signature. He then forges the message by putting the newly created A's signature and sends the signed message to B pretending that it has come from A. It is similar to the ciphertext-only attack discussed in Chapter 2.

   Known-message attack: In this type of attack, the intruder has access to some messages signed by A. That is, he or she already has one or more message–signature pairs. With the help of these known message–signature pairs, the intruder tries to create another message and forge A's digital signature on it. This attack is similar to the known-plaintext attack discussed in Chapter 2.

   Chosen-message attack: In this type of attack, the intruder manages to let A sign one or more messages for him. In other words, the intruder himself chooses a message–signature pair. Later, he creates a new message with the contents he or she wants and forges A's digital signature on it, and sends it to B pretending that it has come from A. This attack is similar to the chosen-plaintext attack discussed in Chapter 2.

7. Discuss the different approaches proposed for the digital signature function.

Ans.: A digital signature cannot be a constant and must be a function of the entire document it signs. There are several approaches that have been proposed for the digital signature function. These approaches are categorized into two types: direct and arbitrated.

Direct digital signature

In the direct digital signature approach, the signed document is directly passed from the sender to the receiver. That is, no third party is involved in carrying out this communication, because it is assumed that the receiver knows the public key of the sender and, hence, can easily verify the authenticity of the message. There are two ways of creating a digital signature—one, by encrypting the whole message with the sender's private key, and another, by taking the hash of the message and then encrypting it with the sender's private key. Message confidentiality can be achieved by further encrypting the message and the signature with the receiver's public key in case of public-key encryption or shared key in case of symmetric-key encryption.

Though there is no third party directly involved in carrying out the communication between the sender and receiver, in case of disputes, the third party may be involved in resolving the conflicts. The third party views both the message and its signature. If the signature function is applied on the encrypted message, then the third party also needs to know the decryption key to read the plaintext message. However, if the signature function is applied on the plaintext message, then the recipient can simply store the plaintext message and its signature, so that it can be used in future for resolving disputes. Thus, it is better to apply the digital signature function on the message before encrypting it.

The main problem with the direct digital signature scheme is that if the sender wants to deny the sending of a particular message, he or she can claim that his or her private key is stolen or lost and that someone has forged the signatures. Since no trusted third party is directly involved in the communication, it is difficult to verify whether the key was actually stolen, or if the sender is lying. This type of threat can be controlled to some extent by two ways:

   The sender whose key has been stolen can immediately report to a central authority, or

   The sender can include a timestamp (date and time) in each signed message.

The latter solution can still be compromised. For example, if the private key of the sender A is actually stolen at time (t), then some intruder (say, X) can create A's signature and send a forged signed message to B including a timestamp before or equal to t.

Arbitrated digital signature

In the arbitrated digital signature approach, a third party known as the trusted arbiter is directly involved in the process. Every signed message sent by the sender to the receiver goes through the arbiter. The arbiter performs two functions. First, it verifies the integrity (origin and content) of the signed message and signature by applying a certain number of tests. Second, it attaches the date and time of creation of the message, and forwards the message to its final destination. This scheme is based on the assumption that both the sender and receiver completely trust the arbiter's claim that he or she verifies the message to the level of his or her satisfaction and will not alter the data in any way.

The main advantages of the arbitrated digital signature approach are as follows:

   Both the communicating parties cannot share any kind of information before communication, thus preventing the chances of any kind of fraud.

   Any incorrectly dated message cannot be sent to the receiver.

   The contents of the message from A to B are hidden from the trusted third party and others.

8. Write a short note on the RSA digital signature scheme.

Ans.: In addition to the encryption and decryption of a message, the RSA approach can also be used for signing and verifying the message. In this case, it is known as the RSA digital signature scheme. At the sender's end, the message M to be signed is given as input to a function, which produces the digital signature S with the help of sender's private key. The sender then transmits both the message and the signature to the receiver. At the receiver's end, the digital signature S is given as input to a function, which computes the copy of the message (M′) with the help of sender's public key. Now, the receiver compares the received and the computed message. If M and M′ are congruent, the receiver accepts the message, otherwise rejects it. The RSA digital signature scheme is shown in Figure 8.2.

Figure 8.2 RSA Digital Signature Scheme

The key generation, signing and verifying algorithms for the RSA digital signature scheme are described as follows:

Key generation: The sender generates his or her private and public key as follows:

(i) The sender chooses two prime numbers p and q and computes the following:

(ii) He then chooses e(1 < e < Φ(n)), the public exponent, and computes his private key d such that:

Signing: The sender creates his digital signature S using his private key d as follows:

where M is the message to be signed.

Verifying: The receiver receives the message M and signature S, and computes a copy of the message using the sender's public key (e, n) as follows:

The receiver then compares M′ with M. If M′ ≡ M, the message is accepted; otherwise, it is rejected.

To prove the RSA digital signature scheme, we need to show that M′ ≡ M(mod n).

As,

And,

Thus, we can write equation (1) as

Hence, proved.

RSA digital signature scheme on a message digest

The RSA digital signature scheme can also be applied on a message digest. In this case, a strong hash function h is applied on the message M to create the message digest D, which is then encrypted with the sender's private key to form the digital signature S. The sender sends the message M and the signature S to the receiver. At the receiver's end, the same hash function h is applied to the received message M to compute D. The receiver also decrypts the received digital signature S with the help of the sender's public key to produce D′. Now, the receiver compares D and D′, if D is congruent to D′, the message is accepted; otherwise it is rejected.

9. Explain ElGamal digital signature scheme.

Ans.: The ElGamal digital signature scheme also consists of three different components, namely, key generation, signing and verifying. All the three components use separate algorithms. In this scheme, four functions are used, in which one function is common in both the signing and verification process, however, with different inputs. Thus, in total, only three different functions are used in the whole process.

In the signing process, two functions F1 and F2 are used to create two different digital signatures S1 and S2, respectively. The sender transmits the message M and the signatures S1 and S2 to the receiver. On receiving the message and the two signatures, the receiver computes two verification codes V1 and V2 with the help of the functions F1 and F3, respectively. Now, the receiver compares two codes V1 and V2; if both are congruent, the message is accepted; otherwise it is rejected. The ElGamal digital signature scheme is shown in Figure 8.3.

Figure 8.3 ElGamal Digital Signature Scheme

The key generation, signing and verifying algorithms for ElGamal digital signature scheme are described as follows:

Key generation: The sender generates his or her private and public keys as follows:

(i) The sender chooses a large prime number p, such that the discrete log problem is difficult in .

(ii) The sender then chooses his or her private key d, such that 1≤d < p−1, and computes , where e1 is a primitive root . The public key of A is (e1, e2, p), and the private key is d.

Signing: To create the signature, the sender chooses a random number k, such that 0 < k < q, and then computes the value of S1 and S2 as follows:

(S1 is independent of the message M)

(where k−1 is the multiplicative inverse of k modulo p)

Digital signature = (S1, S2)

Verifying: The receiver verifies the signature as follows.

He or she first checks whether 0 < S1 < p and 0 < S2 < p−1, and then computes the two verification codes V1 and V2 as follows:

Now, the receiver tests whether V1 ≡ V2. If the condition is satisfied, the signature is accepted; else, it is rejected.

We can prove the verification as follows:

Therefore, we get:

The above congruence holds if and only if:

M ≡[(d * S1) + (k * S2)]mod(p−1) or,

S2 ≡[(M−d * S1) * k−1]mod(p−1), which is same S2 as in the signing process.

10. Explain DSS, its approaches and its algorithm with proof.

Ans.: The Digital Signature Standard (DSS) was published by the National Institute of Standards and Technology (NIST) as the Federal Information Processing Standard (FIPS 186). It was originally developed in 1991. However, it was then criticized by the public because of lack of security in the scheme. Thus, it was revised in 1993, and finally in 2000, an elaborated version of DSS came into existence, which was named FIPS 186-2. The DSS uses Secure Hash Algorithm (SHA) and presents a new digital signature scheme, Digital Signature Algorithm (DSA).

As in the ElGamal digital signature scheme, in the DSS scheme also two functions F1 and F2 are used to create two different digital signatures S1 and S2, respectively. However, in DSS scheme, the message digest (not the message) is used to create the digital signature S2. The sender transmits S1, S2 and M to the receiver. On receiving the message and the two signatures, the receiver computes the message digest using the same hash function, and calculates the verification code Vc using another function F3. Now, the receiver compares Vc with S1; if both are congruent, the message is accepted; otherwise it is rejected. The DSS scheme is shown in Figure 8.4.

Figure 8.4 DSS Scheme

The key generation, signing and verifying algorithms for DSS scheme are described as follows. All the algorithms use the following global parameters:

L = length of the key in bits, where the number of bits are a multiple of 64; L lies between 512 and 1024 bits

p = prime number such that 2L-1 < p < 2L

q = a 160-bit prime factor of (p−1)

, where e0 is a primitive element in Zp with 1 < e0 < p−1, such that e1 > 1

M = message to be signed

h(M) = hash of message M using the SHA algorithm

Key generation: The sender generates his or her private and public keys as follows:

   Private key: The sender chooses a random integer d such that 0 < d < q; d becomes the private key of the sender

   Public key: The sender computes the following:

The public key of sender becomes (e1, e2, p, q)

Signing: To create the signature, the sender chooses a random number k, such that 0 < k < q, and then computes the value of S1 and S2 as follows:

(S1 is independent of the message M)

Digital signature = (S1, S2)

Verifying: The receiver verifies the signature as follows:

He or she first checks whether 0 < S1 < p and 0 < S2 < q, and then computes the digest of the message using the same hash function h(M). The receiver finally computes the verification code Vc as follows:

where,

(w, y and z are intermediate variables)

Now, the receiver tests whether S1 ≡ Vc. If the condition is satisfied, the signature is accepted; else, it is rejected.

Proof of the digital signature algorithm

To prove the algorithm, we have to show that Vc = S1.

As we know that:

Hence, proved.

11. Why does each digital signature in the ElGamal and DSS schemes require a new value of k?

Ans.: In the ElGamal and DSS schemes, the sender chooses his or her private and public keys once and uses these keys to sign several documents. However, as we know, each time a message is sent, it should be signed with a unique digital signature; that is, no two documents can bear the same digital signature. Thus, to have a unique digital signature for every document, a new value of k (which is used in computing S1 and S2) is required.

12. How is DSS better than the RSA and ElGamal digital signature scheme?

Ans.: DSS is better than the RSA digital signature scheme because computing digital signatures in DSS requires lesser time than that in the RSA digital signature scheme for the same value of p. DSS is also better than the ElGamal digital signature scheme because DSS scheme produces smaller digital signatures as compared to those produced by the ElGamal scheme, because q < p.

13. Explain the variations of digital signatures?

Ans.: The digital signature scheme has got many variations and additions to its main concept. Some of the variants of digital signature are discussed as follows:

   Timestamped signature: Some digital signatures include a timestamp value in order to prevent replay attacks. This is what we call timestamped signatures. In a replay attack, the documents can be replayed by a third party. For example, if A signs a request to the bank C to transfer a certain amount of money to B, B can intercept the document and replay it if there is no timestamp on the document. One way to handle such problems is to include the actual date and time. However, this may create a problem if the time zones are different or the clocks are not synchronized. Another solution is to use a nonce (which is a randomly generated number that can be used only once). The receiver makes a note that the particular nonce is used by the sender and cannot be used again. That is, a new nonce defines the present time and a used nonce defines the past time.

   Blind signature: The blind signature scheme was developed by David Chaum. The concept of blind signature is used when the sender does not want to reveal the contents of the message to the signer and just wishes get the message signed by the signer. Blind signatures are typically used in situations where the signer and the message author are completely different parties. Examples include electronic voting systems and electronic payment systems. The basic idea behind blind signatures is that the sender A first creates a message and blinds it. He then sends the blinded message to the signer B. B signs the blinded message and returns the signature on the blinded message to A. A unblinds the signature to obtain a signature on the original message.

         Blind signatures scheme can be implemented by using a number of public-key digital signature schemes such as RSA and DSS. Here, we will discuss the implementation using a variation of the RSA scheme. The steps are as follows:

1. A selects a random number b, which is sometimes known as the blinding factor.

2. A calculates the blinded message as follows:

    where, e = B's public key

    M = original message

    n = modulus defined in the RSA digital signature scheme

3. A sends MB to B.

4. B signs MB using the signing algorithm defined in the RSA digital signature scheme, as follows:

    where,

    Sblind = signature on the blind version of message

    d = B's private key

5. A removes the blind from the signature using the multiplicative inverse of b, as follows:

It can be easily proved that S ≡ Md (mod n); that is, the signature made on the original message M as defined in the RSA digital signature scheme. The proof is as follows:

Hence, proved.

In the blind signature scheme, there are more chances of fraud. That is, it is possible that A gets a blind message signed by B that may later hurt him or her. For example, A may get a sign from B on a document that contains B's will. To deal with such type of situations, some laws have been passed that protect B in case he or she has signed a blind document that is against his or her interest.

   Undeniable digital signature: The digital signature schemes discussed so far consist of a signing algorithm and a verifying algorithm. That is, a signer can only create his or her signature using his or her private key, and anyone having the signer's public key can verify the signatures. Thus, the verification can be performed without the signer's consent or involvement. In some cases, a signer may not like it that anyone can verify his or her signatures. Thus, in order to increase the privacy of the signer, another scheme called undeniable digital signature scheme was proposed by David Chaum and Hans van Antwerpen in 1989. This scheme is a non-self-authenticating signature scheme in which no signatures can be verified without the signer's cooperation and notification.

          This scheme has three components, namely, signing algorithm, verification protocol and disavowal protocol.

   Signing algorithm: This allows the signer (say, A) to sign a message.

   Verification (or confirmation) protocol: This allows the signer to limit the users who can verify his or her signature. The verification process is interactive in nature and uses the challenge/response mechanism for verifying the signature, in which the verifier B sends a question (or challenge) to the signer A. A then sends a valid answer (response) to B, and B views the response to verify the signature.

   Disavowal (or denial) protocol: Since the verification process requires the involvement of the signer, it is quite possible that the signer can freely decline the request of the verifier. This protocol prevents the signer from proving that a signature invalid when it is valid, and vice versa. To prove that the signature is a fake, A needs to take part in the denial protocol.

         The main advantage of this scheme is that if a signature is invalid, a fraud signer cannot prove it valid because he or she will not be able to successfully complete the verification protocol. In the same way, a fraud signer cannot deny a signature that is valid, as he or she will not be able to successfully complete the disavowal protocol.

14. Explain the mutual authentication protocol.

Ans.: The mutual authentication protocol enables the communicating parties to mutually satisfy themselves about their identities and exchange session keys between them. The main issues with authenticated key exchange are confidentiality and timeliness. Confidentiality can be achieved by communicating the essential identification and session key information in an encrypted form so that the compromise of session keys can be prevented. Timeliness is another important issue that must be considered for preventing message replay attacks. The authenticated key exchange can be managed either using the symmetric-key encryption technique or the public-key encryption technique.

Symmetric-key encryption technique

In this technique, a trusted key distribution centre (KDC) is involved who is responsible for generating a session key that is to be used for a short duration between the two communicating parties for a particular session, as well as for distributing that key to both the parties. Each party shares a master key with the KDC, and the KDC uses the master key for distributing the session key to ensure secure distribution of session keys.

Several protocols were proposed for secret key distribution using a KDC; however, each of them had some weaknesses. Finally, in the early 1990s, a protocol was presented for secure key distribution including authentication. The steps of this protocol are as follows:

   To initiate the authentication exchange, A generates a nonce NA and sends it to B along with its identifier IDA in plaintext. This nonce will be returned to A later in an encrypted message that includes the session key generated by KDC, to assure A of its timeliness.

   B sends a message to KDC that includes its identifier IDB and a nonce NB to request KDC for a session key. B's message also includes a block that instructs KDC to issue credentials to A. This block is encrypted with the secret (or master) key shared between the KDC and B, and includes A's identifier (IDA), A's nonce (NA) and the suggested expiration time for the credentials (TE).

   KDC sends a message to A that includes the following:

   Nonce received from B(NB)

   A block containing B's identifier (IDB) to assure A that the second party is B itself, A's nonce (NA) to assure A that this is a timely message and not a replay, a session key (KS) generated by KDC, and the time of expiration of the key (TE). This block is encrypted with the secret key shared between A and KDC, which is KA.

   A block containing A's identifier (IDA), the session key (KS), and the time of expiration of the key (TE). This block is encrypted with the secret key shared between B and KDC (that is, KB). It serves as a “ticket” for A for subsequent authentications.

   A transmits the ticket to B. A also sends B's nonce encrypted with the session key (KS) to assure B that the message has come from A and not from a replay attack. B uses KS to decrypt the nonce.

These steps are summarized as given below:

This protocol provides a secure and effective mechanism to establish a session with a secure session key. Suppose A establishes a session with B using this protocol, and then ends that session once the communication is over. Further, assume that within the same time limit TE, A again wants to establish a new session with B. Now, A has the session key KS that can be used for subsequent authentication to B but this time without the involvement of KDC. Thus, A can establish as many sessions he wants within the time limit provided by the protocol using the same session key. Once the time limit is over, a new session key must be requested from the KDC. The steps for establishing a new session without contacting KDC are as follows:

Here, N'A and N'B are newly generated nonces that assure A and B that there is no replay attack. Note that TE is the time relative to B's clock; thus, there is no need to synchronize clocks because B checks only self-generated timestamps.

Public-key encryption technique

In the public-key encryption technique, in addition to generating the session keys, KDC is also responsible for exchanging the public keys of A and B. In this technique, no master key is shared between the KDC and the communicating parties; rather, the public keys of KDC and the communicating parties are used for encryption. The steps of this protocol are as follows:

1.   A sends a message to KDC informing that he or she wants to establish a secure connection with B. The message includes the identifiers of A (IDA) and B (IDB) in plaintext.

2.   KDC returns a copy of the public-key certificate of B to A, which contains the identifier and public key of B (BPUB), encrypted with the private key of KDC (KDCPRI).

3.   A generates a nonce NA and sends it to B along with its identifier (IDA) to inform B that he or she wants to communicate with B. A sends this information by encrypting it with B's public key (BPUB).

4.   On receiving this information from A, B sends a request to KDC for issuing the public-key certificate of A, and also for generating a session key (KS). B's request includes the identifiers of A and B in plaintext, along with the nonce NA encrypted with the public key of KDC (KDCPUB).

5.   KDC sends a copy of A's public-key certificate (A's identifier plus its public key) to B encrypted with KDCPRI. KDC also sends the session key (KS), nonce NA and B's identifier (IDB). This triplet informs A that KS is bound to NA in order to assure A that KS is a newly generated session key and not an old one. The triplet is first encrypted with KDCPRI to assure B that this information is from KDC itself, and then it is encrypted with B's public key to make sure that no other party can create a fraudulent connection with A.

6.   B sends the triplet {NA, KS, IDB} still encrypted with KDC's private key along with the nonce NB to A. This whole information is further encrypted with A's public key (APUB).

7.   A decrypts the received information using the public key of KDC (KDCPUB) to obtain the session key (KS). Then, it sends the nonce NB encrypted with the session key KS to B to assure him or her that A has got the session key.

These steps are summarized as given below:

Though this protocol provides protection against several attacks, the authors Woo and Lam themselves found an error and generated a revised version of the algorithm. In the new version of the protocol, the identifier of A (IDA) is added to the information being encrypted with the private key of KDC in steps 5 and 6, as shown here:

The inclusion of IDA binds the session key KS to the identifiers of both A and B that are involved in the communication. IDA is included because of the reason that the nonce NA is considered unique among all the nonces generated by A only, and not among all nonces generated by all parties. Thus, the connection request of A is uniquely identified with the help of a pair {IDA, NA} and not only by NA as in prior protocols.

15. Explain one-way authentication protocol.

Ans.: In some applications, such as e-mail, it is not necessary for the sender and receiver to be online at the same time. The message sent by the sender is rather forwarded to the receiver's electronic mailbox, where it is stored until the receiver reads it. Thus, only one-way authentication is required.

Since the receiver may or may not be online at the time the sender sends an e-mail, a mail-handling mechanism is required that stores the e-mail when the sender sends it, and then forwards it to the receiver at some later time. As we know, an e-mail consists of a header and the message. The header of the e-mail must be clear so that it can be properly handled by the store-and-forward e-mail protocol such as SMTP.

There are two basic requirements for such applications. First, the plaintext form of the e-mail message must not be accessible to the mail-handling protocol. Thus, an e-mail message must be encrypted such that the decryption key is not known to the mail-handling system. Second, the recipient needs to be assured that the message has come from a supposed sender. One-way authentication can also be performed either using symmetric-key encryption technique or public-key encryption technique.

Symmetric-key encryption technique

While using the symmetric-key encryption technique in one-way authentication, the following steps are used.

1.   The sender A sends the identifier of A and B, and a nonce N1, to the KDC in plaintext.

2.   The KDC then returns a message to A, which contains a newly generated session key KS, B's identifier IDB, the nonce N1, and a block encrypted with the secret key shared between KDC and B (that is, KB). This whole message is further encrypted with the secret key shared between KDC and A (that is, KA). The inclusion of IDB and N1 in the message assures A that this is the original message and that it has not been altered by the KDC in any way. The nonce N1 also helps A in verifying that it is not a replay of some previous message. The block encrypted with KB contains KS and IDA and is intended for B. A will send this block to B as it is to establish the connection and prove A's identity.

3.   A forwards to B the message originated from KDC for B, along with the e-mail encrypted with the session key KS.

The protocol is summarized as follows:

The main advantage of this protocol is that it guarantees that no user other than the intended recipient of the message will be able to read the message. Moreover, it provides a level of authentication that the message has come from an alleged sender. However, this protocol does not provide protection against replay attacks.

Public-key encryption technique

While using the public-key encryption technique for one-way authentication, one can achieve confidentiality, authentication or both. To achieve confidentiality, the sender needs to know the public key of the recipient. If A is the sender and B is the receiver, the following protocol may be used.

Here, A encrypts the message M with the session key KS, and also encrypts the session key KS with B's public key BPUB, and sends it to B.

To achieve only authentication, B needs to know the public key of A. Thus, the following protocol may be used.

In this protocol, A sends to B the message M, the digital signature encrypted with A's private key, and A's public-key certificate encrypted with the private key of the authentication server (ASPRI). B first determines A's public key from the public-key certificate, and then verifies that it is authentic. B then uses the public key to verify the message itself.

To achieve both confidentiality and authentication, the message M can be encrypted with the session key KS, which is also sent to B encrypting it with B's public key.

16. In the RSA scheme, let p = 3, q = 11 and d = 3. Calculate the public key. Now suppose A wants to send a message M = 107 to B. Sign and verify this message using the RSA digital signature scheme.

Ans.: Here, p = 3 and q = 11

Therefore, the public key is (e, n), that is, (7, 33).

Signing:

Verifying:

Now, we have to verify whether M' ≡ M (mod n)

8 ≡ 8, which is true.

Thus, the signature is verified.

17. In the ElGamal scheme, let p = 881, e1 = 2 and d = 127. Calculate the value of e2. Find the values of S1, S2, V1 and V2, if M = 400 and k = 17.

Ans.: Here, p = 881, e1 = 2 and d = 127

Signing:

The multiplicative inverse of 17 in Z880 is 673 (as 17*673 = 11441 mod 880 = 1). The multiplicative inverse can be obtained using the extended Euclidean algorithm discussed in Chapter 2 (Q12).

Therefore, Equation (1) can be written as follows:

Since 86868 is not lying in Z880, we need to take 86868 mod 880, which is 628. Thus, now the equation becomes:

Since 400−628 comes out to be negative, we first take the additive inverse of 628, which can be computed as 880−628 = 252, and then add it to 400. Now, Equation (2) becomes

Therefore, the digital signature = (S1, S2) = (684, 556)

Verifying: Since 0 < 684 < 881 and 0 < 556 < 880, we compute the two verification codes V1 and V2 as follows:

Since V1 ≡ V2, the digital signature is verified.

18. In the DSS scheme, let q = 83, p = 997, e0 = 3 and d = 23. Calculate the values of e1 and e2. Find the values of S1, S2, V1 and V2, if h(M)= 5000 and k = 31.

Ans.: Here, q = 83, p = 997, e0 = 3 and d = 23

Signing:

The multiplicative inverse of 31 in Z83 is 75 (as 31*75 = 2325 mod 83 = 1).

Therefore, Equation (1) can be written as follows:

Therefore, the digital signature = (S1, S2) = (16, 50)

Verifying: Since 0 < 16 < 83 and 0 < 50 < 83, we compute the verification code Vc as follows:

We first calculate the values of intermediate variables w, z and y.

Since S1 ≡ Vc, the digital signature is verified.

Multiple-choice Questions

1.   Which of the following services is not provided by digital signatures directly?

(a) Message authenticity

(b) Message confidentiality

(c) Message integrity

(d) Nonrepudiation

2.   Which of the following pair of keys is used to create and verify the digital signature, respectively?

(a) Signer's private key and verifier's public key

(b) Verifier's public key and verifier's private key

(c) Signer's private key and signer's public key

(d) Signer's public key and signer's private key

3.   The sender encrypts the message with his or her private key to achieve _________.

(a) Authentication

(b) Confidentiality

(c) Both (a) and (b)

(d) None of these

4.   RSA _________ be used for digital signatures.

(a) can

(b) cannot

(c) must

(d) must not

5.   Which of the following is a property of a digital signature?

(a) It must be able to verify the author.

(b) It must be able to verify the date and time of the signature.

(c) It must be able to authenticate the contents of the message at the time of the signature.

(d) All of these

6.   Which of these is a kind of attack possible on digital signatures?

(a) Ciphertext-only attack

(b) Known-message attack

(c) Key-only attack

(d) Both (b) and (c)

7.   Which of these statements is not correct about DSS?

(a) It was published by the National Institute of Standards and Technology.

(b) It uses three functions to create a digital signature.

(c) An elaborated version of DSS was named as FIPS 186-2.

(d) It uses Secure Hash Algorithm (SHA).

8.   Which of these is not a variation of a digital signature?

(a) Timestamped signature

(b) Blind signature

(c) Encrypted digital signature

(d) Undeniable digital signature

Answers

1. (b)

2. (c)

3. (a)

4. (a)

5. (d)

6. (d)

7. (b)

8. (c)