Digital Signatures & Authentication Protocols

Digital Signatures & Authentication
Protocols
To guard against the baneful influence exerted by strangers is

therefore an elementary dictate of savage prudence. Hence
before strangers are allowed to enter a district, or at least
before they are permitted to mingle freely with the inhabitants,
certain ceremonies are often performed by the natives of the
country for the purpose of disarming the strangers of their
magical powers, or of disinfecting, so to speak, the tainted
atmosphere by which they are supposed to be surrounded.
—The Golden Bough, Sir James George Frazer
Digital Signatures
have looked at message authentication
◦ but does not address issues of lack of trust
◦ Mary may forge a message and claim it came from
John
◦ John can deny sending a meesage
digital signatures provide the ability to:
◦ verify author, date & time of signature
◦ authenticate message contents
◦ be verified by third parties to resolve disputes
hence include authentication function with
additional capabilities
Digital Signature Properties
must depend on the message being signed
must use information unique to sender
◦ to prevent both forgery and denial
must be relatively easy to produce
must be relatively easy to recognize & verify
be computationally infeasible to forge
◦ with new message for existing digital signature
◦ with fraudulent digital signature for given message
be practical save a copy of the digital signature in
storage
Direct Digital Signatures
involve only sender & receiver
assumed receiver has sender’s public-key
digital signature made by sender signing entire
message or hash with private-key
can further encrypt using receivers public-key
important that sign first then encrypt message &
signature
security depends on sender’s private-key
◦ Have problems if lost/stolen
Arbitrated Digital Signatures
involves use of arbiter A
◦ validates any signed message
◦ then dated and sent to recipient
requires a great deal of trust in arbiter
can be implemented with either private or
public-key algorithms
arbiter may or may not see message
Using Symmetric Encryption
as discussed previously can use a two-
level hierarchy of keys
usually with a trusted Key Distribution
Center (KDC)
◦ each party shares own master key with KDC
◦ KDC generates session keys used for
connections between parties
◦ master keys used to distribute these to them
Needham-Schroeder Protocol
original third-party key distribution protocol
for session between A B mediated by KDC
protocol overview is: Fig 7.9
1. A→KDC: IDA || IDB || N1
2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]
3. A→B: EKb[Ks||IDA]
4. B→A: EKs[N2]
5. A→B: EKs[f(N2)]
Improvements to the Needham-
Schroeder Protocol
used to securely distribute a new session key for
communications between A & B
Secure even if Step 3 is replayed
but is vulnerable to a replay attack if an old
session key has been compromised
◦ then message 3 can be resent convincing B that is
communicating with A
modifications to address this require:
◦ timestamps (Denning 81) (clock sync. Issue)
◦ using an extra nonce (Neuman 93) (solves sync Issue)
Digital Signature Standard (DSS)
A public-key scheme for digital signature use
only, combines hash and encryption
designed by NIST & NSA in early 90's
DSS is the standard, DSA is the algorithm
◦ Based on number theory
◦ security depends on difficulty of computing discrete
logarithms
◦ creates a 320 bit signature, but with 512-1024 bit
security
◦ Computationally efficient
A public-key scheme for digital signature use
only, combines hash and encryption
◦ security depends on difficulty of computing discrete
logarithms
◦ creates a 320 bit signature, but with 512-1024 bit
security
A public-key scheme for digital signature use only, combines hash
and encryption
◦ security depends on difficulty of computing discrete logarithms
◦ creates a 320 bit signature, but with 512-1024 bit security
The DSS uses an algorithm that is designed to provide only the
digital signature function and cannot be used for encryption or
key exchange, unlike RSA.
RSA Approach
 The RSA approach is shown below. The message to be signed is input to a hash function
that produces a secure hash code of fixed length. This hash code is then encrypted using
the sender's private key to form the signature. Both the message and the signature are
then transmitted.
 The recipient takes the message and produces a hash code. The recipient also decrypts the
signature using the sender's public key. If the calculated hash code matches the decrypted
signature, the signature is accepted as valid. Because only the sender knows the private
key, only the sender could have produced a valid signature.
DSS Approach
 The DSS approach also makes use of a hash function. The hash code is provided
as input to a signature function along with a random number k generated for this
particular signature.
 The signature function also depends on the sender's private key (PRa) and a
set of parameters known to a group of communicating principals.
 We can consider this set to constitute a global public key (PUG).The result is a
signature consisting of two components, labeled s and r.
 At the receiving end, the hash code of the incoming message is generated. This
plus the signature is input to a verification function.
 The verification function also depends on the global public key as well as the
sender's public key (PUa), which is paired with the sender's private key.
 The output of the verification function is a value that is equal to the signature
component r if the signature is valid. The signature function is such that only
the sender, with knowledge of the private key, could have produced the valid
signature.
DSA Key Generation
have shared global public key values (p,q,g):
◦ choose a large prime p with 2L-1 < p < 2L
 where L= 512 to 1024 bits and is a multiple of 64
◦ choose q with 2159 < q < 2160
 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 x<q
◦ compute y = gx mod p
DSA Signature Creation
to sign a message M the sender:
◦ generates a random signature key k, k<q
◦ 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
Summary
have discussed:
◦ digital signatures
◦ authentication protocols (mutual & one-way)
◦ digital signature algorithm and standard

Digital Signatures & Authentication Protocols

Uploaded by

Copyright:

Available Formats

Digital Signatures & Authentication Protocols

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Digital Signatures & Authentication Protocols

Uploaded by

Copyright:

Available Formats

Digital Signatures & Authentication

To guard against the baneful influence exerted by strangers is

You might also like