RAJALAKSHMI INSTITUTE OF TECHNOLOGY,

KUTHAMBAKKAM, CHENNAI - 600124

Department of Artificial Intelligence and Data Science

CW3551 DATA AND INFORMATION SECURITY

UNIT III DIGITAL SIGNATURE AND AUTHENTICATION 9
Digital Signature and Authentication Schemes: Digital Signature-Digital Signature Schemes and
their Variants- Digital Signature Standards-Authentication: Overview- Requirements Protocols
- Applications - Kerberos -X.509 Directory Services

Digital Signature and Authentication Schemes

Digital Signature
 A digital signature is an authentication mechanism that enables the creator of a
message to attach a code that acts as a signature. Typically, the signature is formed by
taking the hash of the message and encrypting the message with the creator’s private
key. The signature guarantees the source and integrity of the message.
 The digital signature standard (DSS) is an NIST standard that uses the secure hash
algorithm (SHA).
 The most important development from the work on public-key cryptography is the
digital signature. The digital signature provides a set of security capabilities that would
be difficult to implement in any other way.
Figure 13.1 is a generic model of the process of making and using digital signa- tures. Bob can sig
n a message using a digital signature generation algorithm.
The inputs to the algorithm are the message and Bob’s private key. Any other user, say Alice, can
verify the signature using a verification algorithm, whose inputs are the message, the signature, a
nd Bob’s public key. In simplified terms, the essence of the digital signature mechanism is shown
in Figure 13.2. This repeats the logic shown in Figure 11.3. A worked-
out example, using RSA, is available at this book’s Web site.
We begin this chapter with an overview of digital signatures. Then, we introduce the Digital Signa
ture Standard (DSS).
Properties
Message authentication protects two parties who exchange messages from any third party. Ho
wever, it does not protect the two parties against each other. Several forms
of dispute between the two are possible.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

For example, suppose that John sends an authenticated message to Mary, using one of the
schemes of Figure 12.1. Consider the following disputes that could arise.
1. Mary may forge a different message and claim that it came from John. Mary would simply
have to create a message and append an authentication code using the key that john and
Mary share.
2. John can deny sending the message. Because it is possible for
Mary to forge a message, here is no way to prove that John did in fact
send the message.
Both scenarios are of legitimate concern. Here is an example of the first scenario:
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

An electronic funds transfer takes place, and the receiver increases the amount
of funds transferred and claims that the larger amount had arrived from the sender.
An example of the second scenario is that an electronic mail
message contains instructions to a stockbroker for a transaction that subsequently turns out b
adly. The sender pretends that the message was never sent.

In situations where there is not complete trust between sender and receiver, something more
than authentication is needed. The most attractive solution to this problem is the digital
signature. The digital signature must have the following properties:
• It must verify the author and the date and time of the signature.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

• It must authenticate the contents at the time of the signature.

• It must be verifiable by third parties, to resolve disputes.
Thus, the digital signature function includes the authentication function.

Attacks and Forgeries

[GOLD88] lists the following types of attacks, in order of increasing severity. Here A denotes the
user whose signature method is being attacked, and C denotes the attacker.
• Key-only attack: C only knows A’s public key.
• Known message
• attack: C is given access to a set of messages and their signatures.
o Generic chosen message attack: C chooses a list of messages before
attempt- ing to breaks A’s signature scheme, independent of A’s public key.
C then obtains from A valid signature for the chosen messages. The attack is
generic, because it does not depend on A’s public key; the same attack is used
against everyone.
o Directed chosen message attack: Similar to the generic attack, except that the
list of messages to be signed is chosen after C knows A’s public key but before
any signatures are seen.
o Adaptive chosen message attack: C is allowed to use A as an “oracle.” This
means the A may request signatures of messages that depend on previously
obtained message–signature pairs.
[GOLD88] then defines success at breaking a signature scheme as an outcome
in which C can do any of the following with a non-negligible probability:
• Total break: C determines A’s private key.
o Universal forgery: C finds an efficient signing algorithm that
provides an equivalent way of constructing signatures on arbitrary messages.
• Selective forgery: C forges a signature for a particular message chosen by C.
• Existential forgery: C forges a signature for at least one
message. C has no control over the message. Consequently, this forgery may only be a m
inor nuisance to A.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

Digital Signature Requirements

On the basis of the properties and attacks just discussed, we can formulate the following
requirements for a digital signature.
• The signature must be a bit pattern that depends on the message being signed.
• The signature must use some information unique to the sender to prevent both forgery
and denial.
• It must be relatively easy to produce the digital signature.
• It must be relatively easy to recognize and verify the digital signature.
• It must be computationally infeasible to forge a digital signature, either by
constructing a new message for an existing digital signature or by constructing
a fraudulent digital signature for a given message.
• It must be practical to retain a copy of the digital signature in storage.
• A secure hash function, embedded in a scheme such as that of Figure 13.2, provides
a basis for satisfying these requirements. However, care must be taken in the design
of the details of the scheme.

Direct Digital Signature

• The term direct digital signature refers to a digital signature scheme that involves
only the communicating parties (source, destination). It is assumed that the destination
knows the public key of the source.
• Confidentiality can be provided by encrypting the entire message plus signa- ture with a
shared secret key (symmetric encryption). Note that it is important to perform the
signature function first and then an outer confidentiality function. In case of dispute,
some third party must view the message and its signature. If the signature is calculated
on an encrypted message, then the third party also needs
access to the decryption key to read the original message. However, if the signature
is the inner operation, then the recipient can store the plaintext message and its sig-
nature for later use in dispute resolution.
• The validity of the scheme just described
depends on the security of the sender’s private key. If a sender later wishes to deny sen
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

ding a particular message, the sender can claim that the private key was lost or stolen
and that someone else forged his or her signature. Administrative controls relating to
the security of private keys can be employed to thwart or at least weaken this ploy, but
the threat is
still there, at least to some degree. One example is to require every signed message
to include a timestamp (date and time) and to require prompt reporting of compromise
d keys to a central authority.
• Another threat is that some private key might actually be stolen from X at time T. The
opponent can then send a message signed with X’s signature and stamped with a time
before or equal to T.
• The universally accepted technique for dealing with these
threats is the use of a digital certificate and certificate authorities.
ELGAMAL DIGITAL SIGNATURE SCHEME
• ElGamal encryption scheme is designed to enable encryption by a user’s public key with
decryption by the user’s private key.
• The ElGamal signature scheme involves the use of the private key for encryption and
the public key for decryption [ELGA84, ELGA85].
a prime number q, if a is a primitive root of q, then

are distinct (mod q). It can be shown that, if a is a primitive root of q, then

As with ElGamal encryption, the global elements of ElGamal digital signature are a prime
number q and a, which is a primitive root of q. User A generates a
private/public key pair as follows.
1. Generate a random integer XA, such that 1 6 XA<q - 1.
2. Compute YA = aXA mod q.
3. A’s private key is XA; A’s pubic key is {q, a, YA}.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

To sign a message M, user A first computes the hash m = H(M), such that m is an integer in the
range 0 <= m <= q - 1. A then forms a digital signature as follows.
1. Choose a random integer K such that 1 <= K <= q - 1 and
gcd(K, q - 1) = 1. That is, K is relatively prime to q - 1.
2. Compute S1 = aKmod q. Note that this is the same as the computation of C1
for ElGamal encryption.
3. Compute K- 1mod (q - 1). That is, compute the inverse of K modulo q - 1.
4. Compute S2 = K- 1(m - XAS1) mod (q - 1).
5. The signature consists of the pair (S1, S2).
Any user B can verify the signature as follows.
1. Compute V1 = am mod q.
2. S1 S
2

Compute V2 = (YA) 1(S1) mod q.

The signature is valid if V1 = V2. Let us demonstrate that this is so. Assume that the equality is
true. Then we have

For example, let us start with the prime field GF(19); that is, q = 19. It has primitive roots {2, 3,
10, 13, 14, 15}, as shown in Table 8.3. We choose a = 10.
Alice generates a key pair as follows:
1. Alice chooses XA = 16.
2. Then YA = aXA mod q = a16 mod 19 = 4.
3. Alice’s private key is 16; Alice’s pubic key is {q, a, YA} = {19, 10, 4}.
Suppose Alice wants to sign a message with hash value m = 14.
1. Alice chooses K = 5, which is relatively prime to q - 1 = 18.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

2. S1 = aKmod q = 105mod 19 = 3 (see Table 8.3).

SCHNORR DIGITAL SIGNATURE SCHEME

As with the ElGamal digital signature scheme, the Schnorr

signature scheme is based on discrete logarithms . The Schnorr scheme minimizes the
message-dependent amount of computation required to generate a
signature. The main work for signature generation does not depend on the message
and can be done during the idle time of the processor. The message-dependent part
of the signature generation requires multiplying a 2n-bit integer with an n-bit integer.
The scheme is based on using a prime modulus p, with p - 1 having a prime factor q of
appropriate size; that is, p - 1 == (mod q). Typically, we
use p ~~ 21024 and q ~ 2160. Thus, p is a 1024-bit number, and q is a 160-bit number, which
is also the length of the SHA-1 hash value.
The first part of this scheme is the generation of a private/public key pair, which consists of the
following steps.
1. Choose primes p and q, such that q is a prime factor of p - 1.
2. Choose an integer a, such that aq = 1 mod p. The values a, p, and q comprise a global
public key that can be common to a group of users.
3. Choose a random integer s with 0 < s < q. This is the user’s private key.
4. Calculate v = a - s mod p. This is the user’s public key.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

A user with private key s and public key v generates a signature as follows.

1. Choose a random integer r with 0 < r < q and compute x = armod p. This computation is
a preprocessing stage independent of the message M to be signed.
2. Concatenate the message with x and hash the result to compute the value e:

3. Compute y = (r + se) mod q. The signature consists of the pair (e, y).
Any other user can verify the signature as follows.
1. Compute x ' = ayve mod p.
2. Verify that e = H(M || x').
To see that the verification works, observe that

Hence, H(M || x') = H(M || x).

Digital Signature Standard (DSS)
 DSA is the US Govt approved signature scheme, which is designed to provide strong
signatures without allowing easy use for encryption.
 The National Institute of Standards and Technology (NIST) published Federal
Information Processing Standard FIPS 186, known as the Digital Signature Standard
(DSS).
 The DSS makes use of the Secure Hash Algorithm (SHA) described in Chapter 12 and
presents a new digital signature technique, the Digital Signature Algorithm (DSA).
 The DSS was originally proposed in 1991 and revised in 1993 in response to public
feedback concerning the security of the scheme.
 There was a further minor revision in 1996. In 2000, an expanded version of the
standard was issued as FIPS 186-2.
 This latest version also incorporates digital signature algorithms based on RSA and on
elliptic curve cryptography. In this section,
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

 we discuss the original DSS algorithm. The DSS uses an algorithm that is designed to
provide only the digital signature function. Unlike RSA, it cannot be used for encryption
or key exchange. Nevertheless, it is a public-key technique.
Digital Signature Algorithm (DSA)

 creates a 320 bit signature

 with 512-1024 bit security

 smaller and faster than RSA

 a digital signature scheme only

 security depends on difficulty of computing discrete logarithms

 variant of ElGamal & Schnorr schemes

DSA Key Generation

 have shared global public key values (p,q,g):

 choose 160-bit prime number q

 choose a large prime p with 2L-1 < p < 2L

• where L= 512 to 1024 bits and is a multiple of 64

• such that q is a 160 bit prime divisor of (p-1)

 choose g = h(p-1)/q

• where 1<h<p-1 and h(p-1)/q mod p > 1

 users choose private & compute public key:

 choose random private key: x<q

 compute public key: y = gx mod p

DSA Signature Creation

 to sign a message M the sender:

 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

 generates a random signature key k, k<q

 nb. k must be random, be destroyed after use, and never be reused

 then computes signature pair:

r = (gk mod p)mod q

s = [k-1(H(M)+ xr)] mod q

 sends signature (r,s) with message M

DSA Signature Verification

 having received M & signature (r,s)

 to verify a signature, recipient computes:

w = s-1 mod q

u1= [H(M)w ]mod q

u2= (rw)mod q

v = [(gu1 yu2)mod p ]mod q

 if v=r then signature is verified

 see Appendix A for details of proof why

DSS Overview

 Below Figure depicts the functions of signing and verifying.

 The structure of the algorithm, as revealed here is quite interesting.
 Note that the test at the end is on the value r, which does not depend on the message at
all. Instead, r is a function of k and the three global public-key components.
 The multiplicative inverse of k (mod q) is passed to a function that also has as inputs the
message hash code and the user's private key.
 The structure of this function is such that the receiver can recover r using the incoming
message and signature, the public key of the user, and the global public key.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

Authentication Applications

• will consider authentication functions

• developed to support application-level authentication & digital signatures

• will consider Kerberos – a private-key authentication service

• then X.509 directory authentication service

Kerbero

• trusted key server system from MIT

• provides centralised private-key third-party authentication in a distributed network

– allows users access to services distributed through out the network

– without needing to trust all workstations

– rather all trust a central authentication server

• two versions in use: 4 & 5

 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

Kerberos Requirements

• first published report identified its requirements as:

– security

– reliability

– transparency

– scalability

• implemented using an authentication protocol based on Needham-Schroeder

Kerberos v4 Overview

 a basic third-party authentication scheme

 have an Authentication Server (AS)

 users initially negotiate with AS to identify self

 AS provides a non-corruptible authentication credential (ticket granting ticket

TGT)

 have a Ticket Granting server (TGS)

 users subsequently request access to other services from TGS on basis of users
TGT

 using a complex protocol using DES

Kerberos v4 Dialogue
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

 The full Kerberos v4 authentication dialogue is shown divided into 3 phases. The
justification for each item in the messages is given in Stallings Table
 First, consider the problem of captured ticket-granting tickets and the need to
determine that the ticket presenter is the same as the client for whom the ticket was
issued. An efficient way of doing this is to use a session encryption key to secure
information.
 Table a shows the technique for distributing the session key. Note that several
additional pieces of information have been added to this first phase of the dialogue.
 Message (1) includes a timestamp, so that the AS knows that the message is timely.
 Message (2) includes several elements of the ticket in a form accessible to C.
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

 This enables C to confirm that this ticket is for the TGS and to learn its expiration time.
Note that the ticket does not prove anyone's identity but is a way to distribute keys
securely.
 It is the authenticator that proves the client's identity. Because the authenticator can be
used only once and has a short lifetime, the threat of an opponent stealing both the
ticket and the authenticator for presentation later is countered.
 C then sends the TGS a message that includes the ticket plus the ID of the requested
service (message 3).
 The reply from the TGS, in message (4), follows the form of message (2).
 C now has a reusable service-granting ticket for V.
 When C presents this ticket, as shown in message (5), it also sends an authenticator.
 The server can decrypt the ticket, recover the session key, and decrypt the
authenticator.
 If mutual authentication is required, the server can reply as shown in message (6)

Kerberos 4 Overview
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

Kerberos Realms

 a Kerberos environment consists of:

 a Kerberos server

 a number of clients, all registered with server

 application servers, sharing keys with server

 this is termed a realm

 typically a single administrative domain

 if have multiple realms, their Kerberos servers must share keys and trust

Kerberos Version 5

 developed in mid 1990’s

 specified as Internet standard RFC 1510

 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

 provides improvements over v4

 addresses environmental shortcomings

• encryption alg, network protocol, byte order, ticket lifetime,

authentication forwarding, interrealm auth

 and technical deficiencies

• double encryption, non-std mode of use, session keys, password attacks

Kerberos v5 Dialogue

X.509 Authentication Service

• part of CCITT X.500 directory service standards

 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

– distributed servers maintaining some info database

• defines framework for authentication services

– directory may store public-key certificates

– with public key of user

– signed by certification authority

• also defines authentication protocols

• uses public-key crypto & digital signatures

– algorithms not standardised, but RSA recommended

X.509 Certificates

• issued by a Certification Authority (CA), containing:

– version (1, 2, or 3)

– serial number (unique within CA) identifying certificate

– signature algorithm identifier

– issuer X.500 name (CA)

– period of validity (from - to dates)

– subject X.500 name (name of owner)

– subject public-key info (algorithm, parameters, key)

– issuer unique identifier (v2+)

– subject unique identifier (v2+)

– extension fields (v3)

– signature (of hash of all fields in certificate)

• notation CA<<A>> denotes certificate for A signed by CA

 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

Obtaining a Certificate
• any user with access to CA can get any certificate from it
• only the CA can modify a certificate
• because cannot be forged, certificates can be placed in a public directory
CA Hierarchy
• if both users share a common CA then they are assumed to know its public key
• otherwise CA's must form a hierarchy
• use certificates linking members of hierarchy to validate other CA's
– each CA has certificates for clients (forward) and parent (backward)
• each client trusts parent’s certificates
• enable verification of any certificate from one CA by users of all other CAs in hierarchy
CA Hierarchy Use

Track chains of certificates:

A acquires B certificate using chain: X<<W>>W<<V>>V<<Y>>Y<<Z>>Z<<B>>
B acquires A certificate using chain: Z<<Y>>Y<<V>>V<<W>>W<<X>>X<<A>>
Certificate Revocation
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

• certificates have a period of validity

• may need to revoke before expiry
1. user's private key is compromised
2. user is no longer certified by this CA
3. CA's certificate is compromised
• CA’s maintain list of revoked certificates
1. the Certificate Revocation List (CRL)
• users should check certs with CA’s CRL
Authentication Procedures
• X.509 includes three alternative authentication procedures:
• One-Way Authentication
• Two-Way Authentication
• Three-Way Authentication
• all use public-key signatures
One-Way Authentication
• 1 message ( A->B) used to establish
– the identity of A and that message is from A
– message was intended for B
– integrity & originality of message
• message must include timestamp, nonce, B's identity and is signed by A
Two-Way Authentication
• 2 messages (A->B, B->A) which also establishes in addition:
– the identity of B and that reply is from B
– that reply is intended for A
– integrity & originality of reply
• reply includes original nonce from A, also timestamp and nonce from B
Three-Way Authentication
• 3 messages (A->B, B->A, A->B) which enables above authentication without
synchronized clocks
• has reply from A back to B containing signed copy of nonce from B
• means that timestamps need not be checked or relied upon
 RAJALAKSHMI INSTITUTE OF TECHNOLOGY,
KUTHAMBAKKAM, CHENNAI - 600124
Department of Artificial Intelligence and Data Science

• Reading assignment: pages 424-427

X.509 Version 3
• has been recognised that additional information is needed in a certificate
– email/URL, policy details, usage constraints
• rather than explicitly naming new fields defined a general extension method
• extensions consist of:
– extension identifier
– criticality indicator
– extension value
Certificate Extensions
• key and policy information
– convey info about subject & issuer keys, plus indicators of certificate policy
• certificate subject and issuer attributes
– support alternative names, in alternative formats for certificate subject and/or
issuer
• certificate path constraints
– allow constraints on use of certificates by other CA’s