جامعة بابل
كلية تكنولوجيا املعلومات
قسم شبكات املعلومات
ماجستير شبكات معلومات
Key distribution and user
authentication
Lecture 4
Digital Signatures
¡ Aim of a signature: prove to anyone that a message
originated at (or is approved by) a particular user
¡ Symmetric key cryptography
Ø Two users, A and B, share a secret key K
Ø Receiver of message (user A) can verify that message came
from the other user (B)
Ø User C cannot prove that the message came from B (it may
also have came from A)
¡ Public key cryptography can provide signature: only
one user has the private key
Digital Signature Operations
(Concept)
¡ Signing
Ø User signs a message by encrypting with own private key
S = E(PRA,M)
Ø User attaches signature to message
¡ Verification
Ø User verifies a message by decrypting signature with signer’s
public key
M′ =D(PUA,S)
Ø User then compares received message M with decrypted M′; if
identical, signature is verified
Digital Signature Operations
(Practice)
No need to encrypt entire message; encrypt hash of
message
¡ Signing
Ø User signs a message by encrypting hash of message with own private
key
S = E(PRA,H(M))
Ø User attaches signature to message
¡ Verification
Ø User verifies a message by decrypting signature with signer’s public key
h = D(PUA,S)
Ø User then compares hash of received message, H(M), with decrypted h;
if identical, signature is verified
Replay and freshness
¡ Alice sends a signed message to Bob:
A → B: M, S= E(PRA, (M))
E.g., S= E(PRA, (“Attack now!”))
¡ What is wrong with this protocol?
¡ Replay problem:
A → B: M, S= E(PRA, (M)) // S= E(PRA, (“Attack now!”))
¡ Authentication is usually not enough in network security! Need to
also check freshness of the message
¡ “Fresh” may mean that the message was sent recently, or that has
not been received before
¡ Freshness mechanisms:
Ø Timestamp
Ø Nonce
Ø Sequence number
Timestamps
¡ Checking freshness with A’s timestamp:
A → B: TA, M, S= E(PRA, TA, M)
e.g. S= E(PRA, “2017-10-24 08:30 GMT”, “Attack now!”)
¡ Timestamp implementations:
Ø Sender’s clock value, UTC (validity period is fixed or determined by the
receiver)
Ø Validity period start and end times, or just end time
¡ Q: What potential problems remain?
Ø Timestamps require clocks at the signer and receiver, and secure
clock synchronization
Ø Secure fine-grained synchronization is hard to achieve; loose
synchronization (accuracy from minutes to days) is easier
Ø Also, fast replays possible while the timestamp is fresh:
S= E(PRA, TA, “Transfer 1000000 ID”)
Nonces
¡ What if there are no synchronized clocks?
¡ Checking freshness with B’s nonce:
A → B: “Hello, I’d like to send you a message.”
B → A: NB
A → B: NB, M, S= E(PRA, NB, M)
¡ Bob’s nonce is a bit string selected by Bob, which is never reused
¡ In many applications, the nonce must be impossible to guess before it is sent
¡ Nonce implementations:
Ø 128-bit random number (unlikely to repeat and hard to guess)
Ø timestamp and a random number (protects against errors in RNG initialization and/or
clock errors)
¡ Sometimes used as nonces: sequence number, deterministic PRNG output,
timestamp only (easy to make mistakes with these)
¡ Nonce requires an extra message or roundtrip
Ø Not well suited for asynchronous or broadcast communication
Sequence numbers
¡ What if there are no synchronized clocks and nonces do not fit into
the protocol design?
¡ Sequence numbers in authenticated messages allow the recipient
to detect message deletion, reordering and replay
A → B: seq, M, S= E(PRA, seq, M)
e.g. S= E(PRA, “Transaction id=43542. Transfer 1000000 ID to account
1006443.”)
¡ Dangerous, but can sometimes ensure that messages are not
processes out of order or twice
¡ Good combination: timestamp from a loosely synchronized clock
and sequence number
Key exchange protocol
¡ With public-key cryptography:
Ø A and B each have a public-private key pairs and certificates
Ø Need to generate a symmetric shared secret session key
Ø The public keys are used for the key exchange, and the session keys are
used for efficient protection (symmetric encryption and MAC) on session
data
¡ In systems that use symmetric cryptography only:
Ø A and B share a secret master key, e.g. strong password
Ø Need to generate a shared session key for short-term use
Ø Motivation: compromise of a session key quite is likely; the seldom-used
master key can be better protected
¡ The master key and certificates are called trust roots
Diffie-Hellman Key Exchange
¡ Diffie and Hellman proposed public key crypto-system in 1976
¡ Algorithm for exchanging secret key (not for secrecy of data)
¡ Based on discrete logarithms
¡ Easy to calculate exponential modulo a prime
¡ Infeasible to calculate inverse, i.e. discrete logarithm
Diffie-Hellman Key Exchange
Algorithm
Diffie-Hellman Key Exchange
Security of Diffie-Hellman Key
Exchange
¡ Insecure against man-in-the-middle-attack
¡ Countermeasure is to use digital signatures and public-key
certificates
Needham-Schroeder secret-key
protocol
¡ The first secret-key key-exchange protocol 1978
¡ Kerberos is based on this protocol
¡ Trusted server T shares a secret master key with each user. When
Alice and Bob need a session key, T creates a random one and
distributes it encrypted with the master keys:
1. A → T: A, B, NA1
2. T → A: ETA(NA1, B, SK, ticketAB)
3. A → B: ticketAB, ESK(NA2)
4. B → A: ESK(NA2-1, NB)
5. A → B: ESK (NB-1)
KTA, KTB = A’s and B’s master keys
SK = session key selected by T
ticketAB = ETB(SK, A)
¡ “Encryption” here must also protect integrity
Kerberos
KDC
AS TGS
krbtgt@RealmY
Service ticket, KAB
3. KRB_TGS_REQ
4. KRB_TGS_REP
1. KRB_AS_REQ
2. KRB_AS_REP
TGT, KAT
TGT
Application
server B
5. KRB_AP_REQ
ap_server.exe
B@RealmY
Service ticket
Client A
6. KRB_AP_REP
A@RealmY ap_client.exe