UNIT-4

Data Integrity, Digital Signature Schemes & Key Management

Message Integrity and Message Authentication, Cryptographic Hash Functions, Digital Signature, Key
Management.
Message Integrity and Message Authentication:
The cryptography systems that we have studied so far provide secrecy, or confidentiality, but not
integrity. However, there are occasions where we may not even need secrecy but instead must have
integrity.

Document and Fingerprint

One way to preserve the integrity of a document is through the use of a fingerprint. If Alice needs to be
sure that the contents of her document will not be changed, she can put her fingerprint at the bottom of
the document.
Eve cannot modify the contents of the document or create a false document because she cannot forge
Alice’s fingerprint.
Message and Message Digest
 The electronic equivalent of the document and fingerprint pair is the message and digest pair.
 Message digest guarantee the integrity of the message.
 A message is passed through an algorithm called a cryptographic hash function to preserve the
integrity. The function creates a compressed image of the message that can be used like a
fingerprint.

Figure: Message and digest

Difference
The two pairs (document / fingerprint) and (message / message digest) are similar, with some differences.
The document and fingerprint are physically linked together. The message and message digest can be
unlinked separately, and, most importantly, the message digest needs to be safe from change.
Checking Integrity:
To check the integrity of a message, we run the cryptographic hash function again and compare the new
message digest with the previous one. If both are same, we are sure that the original message has not been
changed.

Cryptographic Hash Function Criteria: A cryptographic hash function must satisfy three criteria: preimage
resistance, second preimage resistance, and collision resistance.
Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW
For a hash value h=H(x), we say that is the preimage of h. That is, is a data block whose hash function, using
the function H, is h. Because H is a many-to-one mapping, for any given hash value, there will in general be
multiple pre images. A collision occurs if we have x!=y and H(x)=H(y). Because we are using hash functions
for data integrity, collisions are clearly undesirable.
Pre-Image Resistance
 This property means that it should be computationally hard to reverse a hash function.
 In other words, if a hash function h produced a hash value z, then it should be a difficult process to find
any input value x that hashes to z.
 This property protects against an attacker who only has a hash value and is trying to find the input.

Second Pre-Image Resistance

 This property means given an input and its hash, it should be hard to find a different input with the same
hash.
 In other words, if a hash function h for an input x produces hash value h(x), then it should be difficult to
find any other input value y such that h(y) = h(x).
 This property of hash function protects against an attacker who has an input value and its hash, and
wants to substitute different value as legitimate value in place of original input value.

Collision Resistance
 This property means it should be hard to find two different inputs of any length that result in the same
hash. This property is also referred to as collision free hash function.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 In other words, for a hash function h, it is hard to find any two different inputs x and y such that h(x) =
h(y).
 Since, hash function is compressing function with fixed hash length, it is impossible for a hash function
not to have collisions. This property of collision free only confirms that these collisions should be hard to
find.
 This property makes it very difficult for an attacker to find two input values with the same hash.
 Also, if a hash function is collision-resistant then it is second pre-image resistant.

RANDOM ORACLE MODEL:

The Random Oracle Model, which was introduced in 1993 by Bellare and Rogaway, is an ideal mathematical
model for a hash function.

Assume an oracle with a table and a fair coin. The table has two columns.

a. The message AB1234CD8765BDAD is given for digest calculation. The oracle checks its table. This
message is not in the table, oracle flips its coin 16 times. Assume the result HHTHHHTTHTHHTTTH, in
which H represents heads as a bit-1 and T represents Tail as a bit-0 and gives 1101110010110001 in
binary, or DCB1 in Hexadecimal, as the message digest.
b. The message 4523AB1352CDEF45126 is given for digest calculation. The oracle checks its table and finds
that there is a digest for this message in the table (first row). The oracle simply gives the corresponding
digest (13AB).

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Pigeonhole Principle
If n pigeonholes are occupied by n + 1 pigeons, then at least one pigeonhole is occupied by two pigeons. The
generalized version of the pigeonhole principle is that if n pigeonholes are occupied by kn + 1 pigeons, then
at least one pigeonhole is occupied by k + 1 pigeons.
EXAMPLE:
Assume that the messages in a hash function are 6 bits long and the digests are only 4 bits long. Then the
possible number of digests (pigeonholes) is 24 = 16, and the possible number of messages (pigeons) is 26 =
64. This means n = 16 and kn + 1 = 64, so k is larger than 3. The conclusion is that at least one digest
corresponds to four (k + 1) messages.
Birthday Problems:
Summary of Solutions
Solutions to these problems are given in Appendix E for interested readers; The results are summarized in
Table 11.3.

MESSAGE AUTHENTICATION:

A message digest guarantees the integrity of a message. A message digest does not authenticate the sender
of the message. To provide message authentication, Alice needs to provide proof that it is Alice sending the
message and not an impostor. The digest created by a cryptographic hash function is normally called a
modification detection code (MDC). What we need for message authentication is a message authentication
code (MAC).

Modification Detection Code (MDC)

A modification detection code (MDC) is a message digest that can prove the integrity of the message: that
message has not been changed. If Alice needs to send a message to Bob and be sure that the message will
not change during transmission, Alice can create a message digest, MDC, and send both the message and the
MDC to Bob. Bob can create a new MDC from the message and compare the received MDC and the new
MDC. If they are the same, the message has not been changed.

Message Authentication Code (MAC)

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 The message plus MAC are transmitted to the intended recipient. The recipient performs the
same calculation on the received message, using the same secret key, to generate a new MAC. The
received MAC is compared to the calculated MAC.
If we assume that only the receiver and the sender know the identity of the secret key, and if the
received MAC matches the calculated MAC, then the receiver is assured that the message has not been
altered. If an attacker alters the message but does not alter the MAC, then the receiver’s calculation of
the MAC will differ from the received MAC. Because the attacker is assumed not to know the secret key,
the attacker cannot alter the MAC to correspond to the alterations in the message.

Nested MAC:

HMAC ALGORITHM:

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Steps involved in HMAC algorithm:

1. Append zeroes to the left end of K to create a

b-bit string K+ (ex: If K is of length 160- bits and
b = 512, then K will be appended with 44zero bytes).
2. XOR(bitwise exclusive-OR) K+ with ipad to produce
the b-bit block Si.
3. Append M to Si.
4. Now apply H to the stream generated in step-3
5. XOR K+ with opad to produce the b-bit block S0.
6. Append the hash result from step-4 to S0.
7. Apply H to the stream generated in step-6 and
output the result.

CMAC Algorithm:

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 Cryptographic Hash Functions:

 Hash functions are extremely useful and appear in almost all information security applications.
 A hash function is a mathematical function that converts a numerical input value into another
compressed numerical value. The input to the hash function is of arbitrary length but output is always
of fixed length.
 A hash function H accepts a variable-length block of data M as input and produces a fixed-size hash
value h=H(M).
 Values returned by a hash function are called message digest or simply hash values.
 The kind of hash function needed for security applications is referred to as a cryptographic hash
function.
 A cryptographic hash function is an algorithm for which it is computationally infeasible (because no
attack is significantly more efficient than brute force) to find either
(a) a data object that maps to a pre-specified hash result (the one-way property) or

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 (b) two data objects that map to the same hash result (the collision-free property).

Features of Hash Functions

 Fixed Length Output (Hash Value)
 Efficiency of Operation
 Generally for any hash function h with input x, computation of h(x) is a fast operation.
 Computationally hash functions are much faster than a symmetric encryption.
Applications of Cryptographic Hash Functions:
A cryptographic hash functions, is useful to look at the range of applications in which it isemployed.
 Message Authentication
 Digital signature
 Other applications
Requirements for a Hash Function
1. H can be applied to a block of data of any size.
2. H produces a fixed-length output.
3. H(x) is relatively easy to compute for any given x, making both hardware and software
implementations practical.
4. For any given value h, it is computationally infeasible to find x such that H(x) = h. This is sometimes
referred to in the literature as the one-way property.
5. For any given block x, it is computationally infeasible to find y, x such that H(y) = H(x). This is
sometimes referred to as weak collision resistance.
6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y). This is sometimes
referred to as strong collision resistance.

Iterated Hash Function:

Merkle-Damgard Scheme: The Merkle-Damgard Scheme is an iterated hash function that is collision
resistant if the compression function is collision resistant.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Two Groups of Compression Functions
1. The compression function is made from scratch. - Message Digest (MD)
2. A symmetric-key block cipher serves as a compression function.- Whirlpool
Hash Functions Based on Block Ciphers:
Rabin Scheme:

Middle attack.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Davies-Meyer Scheme

Matyas-Meyer-Oseas Scheme:

Miyaguchi-Preneel Scheme:

SECURE HASH ALGORITHM (SHA):

Family of SHA comprise of four SHA algorithms; SHA-0, SHA-1, SHA-2, and SHA-3 Though from same family,
there are structurally different.

 The original version is SHA-0, a 160-bit hash function, was published by the National Institute of
Standards and Technology (NIST) in 1993. It had few weaknesses and did not become very popular.
Later in 1995, SHA-1 was designed to correct alleged weaknesses of SHA-0.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 SHA-1 is the most widely used of the existing SHA hash functions. It is employed in several widely used
applications and protocols including Secure Socket Layer (SSL) security.
 In 2005, a method was found for uncovering collisions for SHA-1 within practical time frame making
long-term employability of SHA-1 doubtful.
 SHA-2 family has four further SHA variants, SHA-224, SHA-256, SHA-384, and SHA- 512 depending up on
number of bits in their hash value. No successful attacks have yet been reported on SHA-2 hash
function.
 Though SHA-2 is a strong hash function. Though significantly different, its basic design is still follows
design of SHA-1. Hence, NIST called for new competitive hash function designs.
 In October 2012, the NIST chose the Keccak algorithm as the new SHA-3 standard. Keccak offers many
benefits, such as efficient performance and good resistance for attacks.

SHA-512 Logic:
The algorithm takes as input a message with a maximum length of less than 2128 bits and produces as
output a 512-bit message digest. The input is processed in 1024-bit blocks. The following Figure depicts the
overall processing of a message to produce a digest. The processing consists of the following steps.
Step 1 Append padding bits. The message is padded so that its length is congruent to 896 modulo 1024.
Padding is always added even if the message is already of the desired length. Thus, the number of padding
bits is in the range of 1 to 1024. The padding consists of a single 1 bit followed by the necessary number of
0 bits.

Step 2 Append length. A block of 128 bits is appended to the message. This block is treated as an unsigned
128-bit integer (most significant byte first) and contains the length of the original message (before the
padding). The outcome of the first two steps yields a message that is an integer multiple of 1024 bits in
length. In Figure, the expanded message is represented as the sequence of 1024-bit blocks M1,M2, MN, so
that the total length of the expanded message is N X 1024 bits .

Message Digest Generation Using SHA-512

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Step 3 Initialize hash buffer. A 512-bit buffer is used to hold intermediate and final results of the hash
function. The buffer can be represented as eight 64-bit registers (a, b, c, d, e, f, g, h).These registers are
initialized to the following 64-bit integers (hexadecimal values):

a = 6A09E667F3BCC908 e = 510E527FADE682D1 b = BB67AE8584CAA73B f = 9B05688C2B3E6C1F c =

3C6EF372FE94F82B g = 1F83D9ABFB41BD6B d = A54FF53A5F1D36F1 h = 5BE0CD19137E2179

Step 4 Process message in 1024-bit (128-word) blocks.

The heart of the algorithm is a module that consists of 80 rounds; The logic is illustrated in Figure 11.9.

th
Step 5 Output. After all N 1024-bit blocks have been processed, the output from the N stage is the 512-
bit message digest.

We can summarize the behaviour of SHA-512 as follows:

SHA-512 Round Function

The logic in each of the 80 steps of the processing of one 512-bit block (Figure 11.10).

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Each round is defined by the following set of equations:

It remains to indicate how the 64-bit word values Wt are derived from the 1024-bit message. Figure 11.11
llustrates the mapping. The first 16 values of Wt are taken directly from the 16 words of the current block.

The remaining values are defined as

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

WHIRLPOOL ALGORITHM:

Whirlpool is an iterated cryptographic hash function, based on the Miyaguchi-Preneel scheme, that uses a
symmetric-key block cipher in place of the compression function.
 Created by Vincent Rijmen and Paulo S. L. M. Barreto.
 Hashes messages of plaintext length 2^256
 Result is a 512 bit message
 Three versions have been released – WHIRLPOOL-0 – WHIRLPOOL-T – WHIRLPOOL
 designed specifically for hash function use
 with security and efficiency of AES
 but with 512-bit block size and hence hash
 similar structure & functions as AES but Input is mapped row wise, Has 10 rounds, A
different primitive polynomial for GF(2^8), Uses different S-box design & values.
 “W” is a 512-bit block cipher ,“m” is the plaintext, split into 512 bit blocks ,“H” is the blocks formed
from the hashes.

Cryptography and Network Security R.PRAVALLIKA,VIEW

Whirlpool Cipher: Block and state in the Whirlpool cipher

Structure of Each Round:

Each round uses four transformations. The block cipher W is the core element of the Whirlpool hash
function
It is comprised of 4 steps.
–Add Round Key
– Shift Columns
– Mix Rows
– Substitute bytes

Structure and Key expansion in the Whirlpool cipher:

Substitute bytes:
Add Round Key
 During the Add Round Key step, the message is XOR’d with the key
 If this is the first message block being run through, the key is a block of all zeros
 If this is any block except the first, the key is the digest of the previous block

Shift Columns

Mix Rows
 DIGITAL SIGNATURE:

A person signs a document to show that it originated from him or was approved by him.
 The signature is proof to the recipient that the document comes from the correct entity and nobody
else. A sign of authentication: A verified signature on a document. A message can be signed
electronically.
 The electronic signature can prove the authenticity of the sender of the message - digital
signature.

Process:
The sender uses a signing algorithm to sign the message. The message and the signature are sent to the
receiver. The receiver receives the message and the signature, and applies the verifying algorithm to the
combination. If the result is true, the message is accepted; otherwise, it is rejected.

Fig: Digital signature process

Need for Keys:
 In digital signature, the signer uses his private key, applied to a signing algorithm, to sign the document.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 The verifier (recipient), uses the public key of the signer, applied to the verifying algorithm, to verify the
document.

Fig: Adding key to the signature process

Signing the Digest:
 In digital signature system, the messages are normally long, but we have to use asymmetric-key
schemes.
 Solution: To sign a digest of the message, which is shorter than a message.

Fig: Signing the digest

Services:
• Message Confidentiality, Message Authentication, Message Integrity, And Nonrepudiation.
A digital signature can directly provide the last three. For message confidentiality we still need encryption/
decryption.
Message authentication :
A secure digital signature scheme, like a secure conventional signature can provide message
authentication.
Message integrity :
The integrity of the message is preserved even if we sign the whole message because we cannot
get the same signature if the message is changed.
Nonrepudiation:
If Alice signs a message and then denies it, can bob later prove that alice actually signed it?
One solution is the trusted third party. Non repudiation can be provided using a trusted party.

Using a trusted center for nonrepudiation

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Confidentiality:
A digital signature does not provide privacy. If there is a need for privacy, another layer of
encryption/decryption must be applied.

Adding confidentiality to a digital signature scheme

ATTACKS ON DIGITAL SIGNATURE:

This section describes some attacks on digital signatures and defines the types of forgery.
Attack Types and Forgery Types

Attack Types:

Forgery Types:
Existential Forgery: Existential forgery is the creation (by an adversary) of any message/signature pair (m,σ),
where σ was not produced by the legitimate signer.

Selective Forgery: Selective forgery is the creation (by an adversary) of a message/signature pair (m,σ) where m
has been chosen by the adversary prior to the attack.

DIGITAL SIGNATURE SCHEMES:

Several digital signature schemes have evolved during the last few decades. Some of them have been implemented.
 RSA Digital Signature Scheme
 ElGamal Digital Signature Scheme
 Schnorr Digital Signature Scheme
 Digital Signature Standard (DSS)
 Elliptic Curve Digital Signature Scheme

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

 RSA Digital Signature Scheme:
How to use RSA cryptosystem to provide confidentiality.
The RSA idea can also be used for signing and verifying a message. In this case, it is called the RSA digital signature
scheme.
The digital signature scheme changes the roles of the private and public keys:
 The private and public keys of the senders are used.
 The sender uses his own private key to sign the document; the receiver uses the sender’s public key to verify
the document.
 The signing and verifying sites use the same function, but with different parameters.
 The verifier compares the message and the output of the function for congruence; If the result is true, the
message accepted.

General idea behind the RSA digital signature scheme

Key Generation
Key generation in the RSA digital signature scheme is exactly the same as key generation in the RSA.

RSA digital signature scheme

In the RSA digital signature scheme, d is private; e and n are public.
RSA Signature on the Message Digest : When the digest is signed instead of the message itself, the susceptibility of
the RSA digital signature scheme depends on the strength of the hash algorithm.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

ElGamal Digital Signature Scheme:

Verifying and Signing

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Schnorr Digital Signature Scheme
General idea behind the Schnorr digital signature scheme

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Digital Signature Standard (DSS)

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

DSS Versus RSA
Computation of DSS signatures is faster than computation of RSA signatures when using the same p.
DSS Versus ElGamal
DSS signatures are smaller than ElGamal signatures because q is smaller than p.

Elliptic Curve Digital Signature Scheme

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

VARIATIONS AND APPLICATIONS
Time Stamped Signatures
Sometimes a signed document needs to be time stamped to prevent it from being replayed by an
adversary. This is called time-stamped digital signature scheme.

Blind Signatures
Sometimes we have a document that we want to get signed without revealing the contents of the
document to the signer.

Key Management

Symmetric-key Distribution
 Symmetric-key cryptography is more efficient than asymmetric-key cryptography for enciphering
large messages. Symmetric-key cryptography, however, needs a shared secret key between two
parties.
 If Alice wants to exchange messages with N people, she needs N different symmetric (secret) keys.
If N people need to communicate with each other, a total of N(N-1)/2 keys would be needed
assuming a single key is used in both directions of communications between a pair of people. This is
normally referred to as the N^2 problem.
 The distribution of keys is another problem. We need an efficient and reliable (trusted) way to
maintain and distribute secret keys.
Key-Distribution Center: KDC
A Trusted Third party, reffered to as a Key-Distribution Center. Each person establishes a shared key with
the Key-distribution center (KDC).

The procedure to get a session key between Alice and Bob is as follows
 Alice sends a request to KDC stating that she needs a session (temporary) secret key between
herself and Bob. Alice uses her secret key with the KDC to authenticate her request and herself to
the KDC.
 The KDC informs Bob about Alice’s request.
 If Bob agrees and authenticates himself using his secret key with the KDC, a session key is created
between the two.
Flat Multiple KDCs.
When the number of people using a KDC increases, the system becomes unmanageable. To solve this
problem, we divide the community into domains. Each domain has one KDC (or more if redundancy is
desired for fault tolerance). If Alice is in one domain and Bob is in another domain, Alice contacts her KDC
which in turn contacts the KDC in Bob’s domain. The two KDC’s can create a secret key between Alice and
Bob. This system is called Flat multiple KDCs.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Hierarchical Multiple KDCs
The hierarchical multiple KDC system has one (or more) KDC at the top of the hierarchy. For example, if
Alice and Bob are in two different countries. Alice sends the request to her local KDC, which relays the
request to the national KDC, which forwards it to the international KDC. The request is then relayed all the
way down to the local KDC where Bob lives.

Session Keys
 The secret key established between the KDC and a member can be used only between that member
and the KDC, not between two members.
 The KDC can help two members (after authenticating their secret key with the KDC) establish a
temporary key that can be used by the two members for a single session. After communication is
terminated, the session key becomes invalid.
 A session symmetric key between two parties is used only once.

A Simple Protocol Using a KDC:

1. Alice sends a plaintext message to KDC to request a symmetric session key between herself and Bob.
2. The KDC creates a ticket encrypted using Bob’s key KB containing the session key. The ticket and the
session key are sent to Alice in a message encrypted using Alice’s key KA. Alice decrypts the message
and retrieves the session key and Bob’s ticket.
3. Alice sends the ticket to Bob who opens (decrypts) the ticket and obtains the value of the session key.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

This simple protocol is prone to replay attacks. An adversary can save the message (ticket) in step 3 and
replay it later.

Needham-Schroeder Protocol

1. Alice sends a message to KDC that includes her nonce R, her identity, and bob’s identity.
2. The KDC sends an encrypted message to Alice that includes Alice’s nonce, the session key, and an
encrypted ticket to B that includes the session key. The ticket is encrypted using Bob’s key and the
whole message is encrypted using Alice’s key.
3. Alice sends the ticket to Bob.
4. Bob decrypts the ticket and sends his challenge RB encrypted to Alice with the session key.
5. Alice responds by sending to Bob the encrypted value RB-1 (rather than RB to prevent replay attacks).

Otway-Rees Protocol:

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

1. Alice sends a message to Bob that includes a common nonce R and her challenge RA and a ticket to the
KDC containing both R and RA. The ticket is encrypted with Alice’s secret key.
2. Bob creates a similar ticket but nonce R Bob sends with his own RB. Both tickets to KDC.
3. The KDC creates a message that contains R, a ticket for Alice with nonce RA and a ticket for Bob with
nonce RB. The tickets contain the session key. The KDC sends the message to Bob.
4. Bob sends Alice her ticket.
5. Alice sends a short (hello) message encrypted with the session key to Bob.

KERBEROS:
 Kerberos is an authentication protocol, and at the same time a KDC that has become very popular
Several connected. In a backbone network, no station is directly connected to the backbone; the
stations are KDC, popular. systems, including Windows 2000, use Kerberos. Originally designed at
MIT, it has gone through several versions.
 Kerberos has separated user verification from the process of issuing tickets that allow the user to
access different servers. Kerberos is designed to support client-server applications, such as FTP, in
which the client process at the user site communicates with the server process at the server site.
Kerberos Servers:
Authentication Server (AS): is the KDC in the Kerberos protocol. Each user registers with AS and is granted
a user ID and password.
Ticket-Granting Server (TGS): issues a ticket for the real server (Bob). It also provides the session key (KAB)
between the user and the real server.
Real Server (Bob) provides services for the user (Alice).

Operation:
The client process (Alice) can access the real server process (Bob) in six steps
1. Alice sends her request to AS in plaintext.
2. The AS sends a message encrypted with Alice’s key K A-AS. The message contains a session key KA-TGS
that will be used by Alice to contact TGS and a ticket for TGS encrypted using TGS’s key K AS-TGS.
When the message arrives, Alice types her password which is used by the client process to create
KA-AS, then decrypt the message to extract the session key and the ticket.
3. Alice sends three items to TGS: the ticket from AS, the name of the real server (Bob), and a
timestamp encrypted with KA-TGS.
4. TGS sends to Alice two tickets both containing the session key K A-B and Bob Alice’s encrypted with
the session between Alice Bob. Alice s ticket is key K A-TGS and Bob’s ticket is encrypted with Bob’s
password/key KTGS_B.
5. Alice sends Bob’s ticket with the timestamp encrypted with KA-B.
6. Bob responds by subtracting 1 from the timestamp and encrypts the response with KA-B.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Using Different Servers
Note that if Alice needs to receive services from different servers, she need repeat only the last four steps.
Kerberos Version 5
1) Version 5 has a longer ticket lifetime.
2) Version 5 allows tickets to be renewed.
3) Version 5 can accept any symmetric-key algorithm.
4) Version 5 uses a different protocol for describing data types.
5) Version 5 has more overhead than version 4.
Kerberos Example:

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Realms
Kerberos allows the global distribution of ASs and TGSs, with each system called a realm. A user may get a
ticket for a local server or a remote server.

PUBLIC-KEY DISTRIBUTION:
In asymmetric-key cryptography, people do not need to know a symmetric shared key; everyone shields a
private key and advertises a public key.

Public Announcement
Bob makes his public key available on
his web site. Alice can get Bob’s public
key by accessing Bob’s site or sending
email to him. This method is simple but
is not secure and is subject to forgery.

Trusted Center
The trusted center retains and updates a
directory of public keys. Each user must
register with the trusted center and establish
a user ID and password. The
user can then deliver his/her public key
for insertion into the directory.
The center can publicly advertise the

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

directory and respond to inquiries about
public keys.

Controlled Trusted Center

A controlled trusted center achieves higher level of security by adding control on the distribution of the
public key. Requests for the public key must include a timestamp. The response of the center to the
request includes the timestamp signed with the private key of the center. Alice decrypts the response using
the center’s public key to verify the timestamp before accepting Bob’s public key.

Fig: Controlled trusted center

Certification Authority:
Security certificates are used to reduce the load on trusted centers.
 A server (Bob) can request a certificate from a certification authority (CA), which could be a cross-
certified company or state or federal organization. Bob’s request contains his identification and his
public key.
 The CA checks the identification of Bob. If verified, the CA writes Bob’s public key on the certificate
and signs it with its own private key.
 Bob can now upload the signed certificate and store it on his site or Bob may send the certificate to
users upon request.
 Any user who wants Bob’s public key can download the certificate and decrypts it using the CA’s
public key to extract Bob’s public key.

Fig: Certification Authority

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

X.509:

Certificate Figure 15.17 shows the format of a certificate.

The Internet community has accepted the ITU-T*recommendation X.509 as a way to unify certificate
formats. In X.509, the certificate has the following important fields:
Version number: this field is the version of X.509 (current version is 3).
Serial number: this field is the serial number assigned to each certificate and is unique for each certificate
issuer.
Signature algorithm ID: this field identifies the signature algorithm used in the certificate. This field is
repeated in the signature field.
Issuer name: this field identifies the CA that issued the certificate.
Validity Period: this field defines the earliest (not before) time and the latest (not after) time during which
the certificate is valid.
Subject name: this field defines the entity that owns the public key stored in this certificate.
Subject public key: this field gives the value of the public key of the owner of the certificate and defines the
public key algorithm.
Signature: this field contains the digest of all other fields in the certificate encrypted by the CA’s private
key, and also contains the ID of the signature algorithm.
* ITU-T = International Telecommunication Union- Telecommunication Standardization Sector

Certificate Renewal
Each certificate has a period of validity. If there is no problem with the certificate, the CA issues a new
certificate before the old one expires.

Certificate Revocation
In some cases a certificate must be revoked before its expiration (e.g., the private key of the subject or of
the CA has been compromised). The revocation is done by periodically issuing a certificate revocation list
(CRL) that contains all revoked certificates that have not expired on the date the CRL is issued. To ensure
the validity of a certificate, the user must check the latest CRL published by the CA that issued the
certificate.

Delta Revocation
To make revocation more efficient, the delta certificate revocation list (delta CRL) has been introduced.

Public-Key Infrastructures (PKI)

PKI is a model for creating, distributing and revoking certificates based on the X.509. IETF (Internet
Engineering Task Force) has created the public-key infrastructure X.509 (PKIX).

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Some duties of PKI
Issue, renew and revoke certificates.
Store and update private keys for members who wish to hold their private keys at a safe place.
Provide services to other Internet security protocols that need public key info such as IPSec and TLS.
Provide access control, i.e., levels of provide different access to the information stored in its database.

PKI Trust Model

For scalability, there should be many certification authorities in the world; each CA handles a specified
number of certificates. The PKI trust model defines rules that specify how a user can verify a certificate
received from a CA.
As an example, the PKI hierarchical trust model defines hierarchical rules that specify how a user can verify
a certificate received from a CA. PKI uses the following notation to denote the certificate issued and signed
by certification authority X for entity Y
X << Y >>

Example:
User1 knows only the public key of the root CA. Show how can User1 obtain a verified copy of User3’s
public key.
Solution User3 sends a chain of certificates, CA<<CA1>> and CA1<<User3>>, to User1.
a. User1 validates CA<<CA1>> using the public key of CA.
b. User1 extracts the public key of CA1 from CA<<CA1>>.
c. User1 validates CA1<<User3>> using the public key of CA1.
d. User1 extracts the public key of User 3 from CA1<<User3>>.
Users1 has used the following chain CA<<CA1>> CA1<<User3>>

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW

Mesh model

REVOCATION OF CERTIFICATES
Each certificate includes a period of validity, much like a credit card. Typically, a new certificate is issued
just before the expiration of the old one-for one of the following reasons.
1. The user’s private key is assumed to be compromised.
2. The user is no longer certified by this CA. Reasons for this include that the subject’s name has changed,
the certificate is superseded, or the certificate was not issued in conformance with the CA’s policies.
3. The CA’s certificate is assumed to be compromised.
Each certificate revocation list (CRL) posted to the directory is signed by the issuer and includes the issuer’s
name, the date the list was created, the date the next CRL is scheduled to be issued, and an entry for each
revoked certificate. Each entry consists of the serial number of a certificate and revocation date for that
certificate. Because serial numbers are unique within a CA, the serial number is sufficient to identify the
certificate.
The directory entry for each CA includes two types of certificates:
• Forward certificates: Certificates of X generated by other CAs
• Reverse certificates: Certificates generated by X that are the certificates of other CAs
The following figure is an example of CA hierarchy.

In this example, user A can acquire the following certificates from the directory to establish a certification
path to B:

When A has obtained these certificates, it can unwrap the certification path in sequence to recover a
trusted copy of B’s public key. Using this public key, A can send encrypted messages to B. If A wishes to
receive encrypted messages back from B, or to sign messages sent to B, then B will require A’s public key,
which can be obtained from the following certification path:
B can obtain this set of certificates from the directory, or A can provide them as part of its initial message

to B.

Cryptography and Network Security M. PALLAVI, Asst. Prof, VIEW