1

Digital Signature and Authentication Protocol

Digital Signatures 2
 Need of Digital Signature 3

 Message authentication protects two parties who exchange messages from

any third party. However, it does not protect the two parties against each
other. Several forms of dispute between the two parties are possible

 Assume Mr. Ben sends an authenticated message to Mrs. Clara using one of
the schemes discussed in Message Authentication Protocol.

The following dispute could arise now:

 Clara may forge a different message and claim that it came from Ben.

Clara would simply have to create a message and append an authentication code
using the key that Ben and Clara share.

 Ben can deny sending the message. Because it is possible for Clara to forge a
message, there is no way to prove that Ben did in fact send the message.

 Both scenarios are of legitimate concern. Ex: Electronic Fund transfer, Stock
broker transaction
 4
Digital Signature Properties
 In situations where there is not complete trust between each other (sender
and receiver), something more than authentication is needed; an elegant
solution is the digital signature

Properties of digital signature:

 It must verify the author and the date and time of the signature.

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

 It must be verifiable by third parties, to resolve disputes.

 Digital Signature Requirements 5

 The signature must be a bit pattern that depends on the message being signed.

 The signature must use some information only known to the sender to prevent

both forgery and denial

 It must be relatively easy to produce, 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.

 6
Digital Signature Algorithms

 Elgammal Digital Signature (EDS)

 National Institute of Standards and Technology (NIST) Digital Signature

 Digital Signature Standard (DSS/DSA)

 RSA Digital Signature (RSA)

 Elgammal Digital Signature Scheme 7

 The global elements of ElGamal digital signature are a prime number q

and α, which is a primitive root of q

User A generates a private/ public key pair as follows.

Generate a random integer XA, such that 1 < XA < q - 1

Compute YA = α XA mod q.

A’s private key is XA ; A’s pubic key is {q, α, YA}

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
 8
A then forms a digital signature as follows:

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.

Compute S1 = αK mod q

Compute K-1 mod (q - 1). That is, compute the inverse of K modulo q - 1.

Compute S2 = K-1(m - XAS1) mod (q - 1).

The signature consists of the pair (S1, S2)

Any user B can verify the signature as follows.

Compute V1 = αm mod q.

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

The signature is valid if V1 = V2

Numerical Example:
9
q = 19, the primitive roots are {2, 3, 10, 13, 14, 15}, let us choose a = 10
Alice generates a key pair as follows:
Alice chooses XA = 16.
Then YA = αXA mod q = 1016 mod 19 = 4.
Alice’s private key is 16; Alice’s pubic key is {q, α, YA} = {19, 10, 4}.
Suppose Alice wants to sign a message with hash value m = 14.
Alice chooses K = 5, which is relatively prime to q - 1 = 18.
S1 = αK mod q = 105 mod 19 = 3
K-1 mod (q - 1) = 5-1 mod 18 = 11.
S2 = K-1 (m - XAS1) mod (q - 1) = 11 (14 - (16)(3)) mod 18 = -374 mod 18 = 4.
Bob can verify the signature as follows.
1. V1 = αm mod q = 1014 mod 19 = 16.
2. V2 = (YA)S1(S1)S2 mod q = (43)(34) mod 19 = 5184 mod 19 = 16.
Thus, the signature is valid because V1 = V2.
 10
NIST Digital Signatures
 11
Digital Signature Algorithm
 12
Numerical Example:

Key Setup

Prime number (p): Let's choose p=23.

Subprime (q): A divisor of p−1, so q=11.

Generator (g): g=h(p-1)/q mod p

Let’s choose h=2, then 22 mod 23=4

Private key (x): A random integer between 1 and q−1, let us take x=3

Public key (y): Calculated as y=gx mod p, 43 mod 23 =18

Assume m=22

Then h(m) = (2+2) mod 23 = 4

Assume k=5 ( user’s per message secret number)

Then k-1(5) mod q i.e. k-1(5) mod 11 = 9

Signing the message
13
Signature = (r,s)

r=(gk mod p ) mod q (45 mod 23) mod 11 = 1

s= (k-1(H(m)+xr) mod q 9(4+3 *1) mod 11 = 63 mod 11 = 8

(r,s) = ( 1,8)

Verifying the message

Given the signature (r‫׳‬,s‫( = )׳‬1,8) for the message m=22

Verify that 0<r<q and 0<s<q

w=(s‫)׳‬-1 mod q = 7 since ( 8 × 7 mod 11 =1)

u1=(H(m‫)׳‬w) mod q = 4 × 7 mod 11 = 6

u2=((r‫)׳‬w) mod q = 1 × 7 mod 11 = 7

v=(gu1yu2) mod p) mod q =( 46 × 187 mod 23 ) mod 11 = 4096 × 612220032 mod 23

=12 mod 11 =1 Compare v= r‫ ׳‬, hence verified.

 14

RSA Digital Signature

Let us understand how RSA can be used for

performing digital signatures step-by-step.

Assume that there is a sender (A) and a receiver (B).

A wants to send a message (M) to B along with the
digital signature (DS) calculated over the message.
RSA Digital Signature – Sender End 15
RSA Digital Signature – Receiver End 16
 17
Numerical Example (RSA)

Bob public key: {39,391}

Bob private key: {343,391}

H(m) = 22

Signing: kprbob(H(m))

S=22343 mod 391 = 367

Bob send (H(m),S) to Alice (22,367)

Verifying: kpubob(H(m),S))

V= 36739 mod 391= 22

Compare H(m) and V, both are same; hence verified, Alice confirms that Bob
has sent the message
Kerberos – Authentication
Service

In Greek mythology, a many headed dog, the

guardian of the entrance of Hades
18
 Kerberos – Its need 20

 Key distribution and user authentication service developed at MIT

 Provides a centralized authentication server whose function is to authenticate

users to servers and servers to users

 Relies exclusively on symmetric encryption, making no use of public-key

encryption

 Kerberos is an authentication service that addresses the following problem:

 In an open distributed environment in which users at workstations wish

to access services on servers distributed throughout the network.

 We would like for servers to be able to restrict access to authorized

users and to be able to authenticate requests for service.

 In this environment, a workstation cannot be trusted to identify its

users correctly to network services.
 User Authentication - Kerberos 21

The following threat may exist:

 A user may gain access to a particular workstation and pretend to be another

user operating from that workstation.

 A user may alter the network address of a workstation so that the requests sent
from the altered workstation appear to come from the impersonated workstation.

 A user may eavesdrop on exchanges and use a replay attack to gain entrance to
a server or to disrupt operations
 Kerberos authentication works using a real-world analogy. 22

 🎭 Analogy: Movie Theater Ticket System

• Authentication Server (AS) → Ticket Counter (Issues a general access

ticket)

• Ticket Granting Server (TGS) → Theater Entrance (Grants entry to a

specific movie)

• Service Server (SS) → Movie Hall (Verifies your ticket and allows entry)

 🛠 Steps in Kerberos Authentication:

1⃣ Client → AS: Requests a Ticket Granting Ticket (AS-REQ)
2⃣ AS → Client: Issues the TGT (AS-REP)
3⃣ Client → TGS: Uses the TGT to request a service ticket (TGS-REQ)
4⃣ TGS → Client: Issues the Service Ticket (TGS-REP)
5⃣ Client → SS: Uses the Service Ticket to access a service (AP-REQ)
6⃣ SS → Client: Verifies the ticket and grants access (AP-REP)
 23
Capturing Kerberos Authentication Packets
Using Wireshark
 24
Simple Authentication Dialogue : Client – Server Model
 25
Limitation

 a user would need a new ticket for every different service such as file
server, print server, mail server, web server etc.,

 involved a plaintext transmission of the password

To solve the above additional problems, we introduce a scheme for avoiding

plaintext passwords and a new server, known as the ticket-granting server
(TGS)
 26
Revised Protocol
 Limitation of Kerberos Version 4 27

Problems:

 Lifetime associated with the ticket-granting ticket

 If too short  repeatedly asked for password

 If too long  greater opportunity to replay

 The threat is that an opponent will steal the ticket and use it before it
expires

 A network service (the TGS or an application service) must be able to

prove that the person using a ticket is the same person to whom that ticket
was issued

 The servers need to authenticate themselves to users, without such

authentication, an opponent could sabotage the configuration so that
messages to a server were directed to another location
Revised Protocol 28
Overview of Kerberos 29
Kerberos Dialogue Exchanges 30
Kerberos Realms and Multiple Kerberi 31
 32
Kerberos Realm Dialogue Exchange