4003-482/4005-705 -- Cryptography

Alan Kaminsky

•

Department of Computer Science

•

Rochester Institute of Technology

•

4486 + 2220 = 6706

Home Page

Cryptography

•

4003-482-01/4005-705-01

•

Spring Quarter 2013

Course Page

4003-482-01/4005-705-01 Cryptography
Chapter 13. Key Establishment
Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology -- Department of Computer Science

Key Management

Pre-established keys: Doesn't scale
- With n users, need O(n²) keys
Solution:
- Set up a long-term key establishment key for each user, once only; need O(n) KEKs
- Set up a short-term session key for a communication session between a pair of users, as needed
Two-party key management
- Key server
  - Key distribution center (KDC): Kerberos V5
  - Key translation center (KTC)
- Public key infrastructure (PKI)
  - Centralized certification authority (CA): TLS, HTTPS
  - Decentralized web of trust: PGP
Group (multi-party) key management

Kerberos V5

J. Kohl and C. Neuman. The Kerberos network authentication service (V5). Internet RFC 1510, September 1993.
Primary purpose: Mutual authentication of two parties
Secondary purpose: Session key establishment between two parties
Uses only symmetric key cryptography (no public key cryptography)
Relies on timestamps
- Therefore, requires participants to have synchronized clocks
Three participants
- Alice, typically a user
- Bob, typically a network service like a network file system
- Kirby, the Kerberos KDC
Preparation
- Alice and Kirby share a secret key, K_AK
- Bob and Kirby share a secret key, K_BK
Authentication and key establishment protocol: Four steps
Step 1
- Alice generates a random nonce, N_A
- Alice sends a message to Kirby with:
  - Her own identity, Alice (A)
  - Identity of the party she wants to talk to, Bob (B)
  - Her nonce, N_A
Step 2
- Kirby generates a random Alice-Bob authentication key, K_AB
- Kirby specifies a lifetime for the authentication key, L
  - L = time at which the authentication key will expire
  - Typically, L = now + 5 minutes
- Kirby generates a ticket for Bob by encrypting the following with K_BK:
  - Authentication key, K_AB
  - Alice's identity, A
  - Lifetime, L
- Kirby generates a response for Alice by encrypting the following with K_AK:
  - Authentication key, K_AB
  - Nonce, N_A
  - Lifetime, L
  - Bob's identity, B
- Kirby sends the encrypted ticket and the encrypted response to Alice
- Alice decrypts the response and verifies that:
  - The nonce is correct
  - Bob's identity is correct
Step 3
- Alice generates an authenticator for Bob by encrypting the following with K_AB:
  - Alice's identity, A
  - Alice's timestamp (current system time), T_A
  - Randomly-chosen subkey, R_A
- Alice sends the ticket and the authenticator to Bob
- Bob decrypts the ticket using K_BK
- Bob decrypts the authenticator using K_AB from the ticket
- Bob verifies that:
  - Alice's identity in the ticket = Alice's identity in the authenticator
  - The difference between Bob's current system time and Alice's timestamp in the authenticator is less than a maximum threshold
    - To account for network latency, clock skew, etc.
  - The ticket has not expired (Bob's current system time < L)
- At this point, Alice has authenticated herself to Bob, but not Bob to Alice
Step 4
- Bob generates a message for Alice by encrypting the following with K_AB:
  - Alice's timestamp, T_A
  - Randomly-chosen subkey, R_B
- Bob sends the message to Alice
- Alice decrypts the message using K_AB
- Alice verifies that:
  - T_A in Bob's message is correct
- At this point, Bob has authenticated himself to Alice
- Alice and Bob both compute a shared secret session key as f (R_A,R_B)
Alice and Bob use shared secret session key for further secure communication
Variation:
- Omit subkeys R_A and R_B
- Alice and Bob use K_AB as the session key for further secure communication
- However, Kirby also knows K_AB, so Eve might be able to learn the session key by attacking Kirby
Variation:
- Omit Step 4 and omit subkey R_A in Step 3
- Alice and Bob use K_AB as the session key for further secure communication
- Bob has not authenticated to Alice as part of the key establishment protocol
- Subsequent secure messages between Alice and Bob must include authentication
- Eve cannot masquerade as Bob because Eve cannot decrypt the ticket to obtain K_AB
- Again, Kirby also knows K_AB, so Eve might be able to learn the session key by attacking Kirby
Variation:
- Alice can re-authenticate herself to Bob within the lifetime of the ticket by repeating just Step 3 (and maybe Step 4)

Public Key Infrastructure (PKI)

Certificate Authority (CA)
- Trusted by everyone
- Everyone knows the CA's public digital signature verification key without having to look it up
Alice's certificate
- Alice travels physically to the CA's office and proves her identity
- The CA puts together a certificate containing Alice's public information
  - Alice's identity
  - Validity dates for the certificate
  - Alice's public digital signature verification key
  - Alice's public encryption key
- The CA digitally signs Alice's certificate
- Alice can now publish her CA-signed certificate
Alice sends a signed message to Bob
- E.g., one of the Diffie-Hellman key exchange messages
- Bob gets Alice's certificate, by looking it up, or by Alice including it in the message
- Bob verifies the CA's signature on Alice's certificate; now Bob knows Alice's certificate is genuine
- Bob uses Alice's digital signature verification key from Alice's certificate to verify Alice's signature on the message; now Bob knows the message really came from Alice
Certificate revocation
- Certificate revocation list (CRL)
- Fast revocation
Authorization with certificates
- Authentication: Who are you?
- Authorization: Are you allowed to do that?
- Indirect authorization: Use certificates to authenticate identity, use something else (e.g. access control list (ACL)) to authorize actions for that identity
- Direct authorization: Use certificates to authorize actions directly

Transport Layer Security (TLS)

Transport Layer Security (TLS) key establishment (many details omitted)
TLS is the Internet standard version of Netscape's proprietary Secure Socket Layer (SSL)
T. Dierks and C. Allen. The TLS Protocol Version 1.0. Internet RFC 2246, January 1999.
Used for secure web browsing with the HTTPS protocol
Client and server first negotiate which algorithms they will use for public key encryption, digital signatures, and block cipher encryption
Client sends (unencrypted) a 32-byte number R1 to server
- 4-byte timestamp (seconds since midnight 01-Jan-1970), to detect replays
- 28-byte random number
Server sends (unencrypted) a 32-byte number R2 to client
- 4-byte timestamp (seconds since midnight 01-Jan-1970), to detect replays
- 28-byte random number
Server sends its certificate to client; client verifies certificate
- To authenticate the server to the client
(Optional) Client sends its certificate to server; server verifies certificate
- For HTTPS, the client almost never has a certificate
- The client authenticates to the server outside of TLS, e.g. by logging into their account on the web site
Client generates a 48-byte random pre-master secret PMS
Client encrypts PMS using server's public encryption key and sends the ciphertext to server
Server decrypts PMS using server's private decryption key
Both client and server compute 48-byte master secret MS
- MS = PRF (PMS, "master secret", R1 | R2)
- PRF is a pseudorandom function that uses hash functions to mix its arguments and generate a sequence of random bytes
Client computes 12-byte value = PRF (MS, "client finished", hash(all previous messages)) and sends that to server; server checks whether it is correct
- To detect intruders and replays
- This proves to the server that the thing on the other end:
- Knows the master secret,
- Sent R1, and
- Received the server's R2
Server computes 12-byte value = PRF (MS, "server finished", hash(all previous messages)) and sends that to client; client checks whether it is correct
- To detect intruders and replays
- This proves to the client that the thing on the other end:
- Knows the master secret,
- Sent R2, and
- Received the client's R1
Both client and server use the PRF to compute authentication keys, encryption keys, and keystream generator initialization vectors in both directions from the master secret
Thereafter, each message is authenticated using HMAC and encrypted using a keystream generated from a block cipher

PGP Web of Trust

There is no centralized CA; users sign certificates for each other
Alice meets Bob in a dark alley, each signs the other's certificate:
- "Alice's public verifying key is K1; signed by Bob"
- "Bob's public verifying key is K2; signed by Alice"
Alice adds Bob's certificate to her key ring
Alice receives a message signed by Carol, who she doesn't know
Carol includes her certificate with the message:
- "Carol's public verifying key is K3; signed by Bob"
If Alice trusts Bob only to sign certificates for good people:
- Alice uses K2 to verify Bob's signature on Carol's certificate
- Alice uses K3 to verify Carol's signature on the message
- Alice adds Carol's certificate to her key ring
Certificate chains of any length are possible:
- Alice receives a message signed by Ted
- "Ted's public verifying key is K4; signed by Carol"
- "Carol's public verifying key is K3; signed by Bob"
- "Bob's public verifying key is K2; signed by Alice"
PGP only verifies certificate chains; the users have to decide for themselves whether to trust each link in the chain

Responsible Behavior

http://xkcd.com/364/

PGP

http://xkcd.com/1181/

Multi-Party (Group) Diffie-Hellman Key Exchange

M. Steiner, G. Tsudik, and M. Waidner. Diffie-Hellman key distribution extended to group communication. In Proceedings of the Third ACM Conference on Computer and Communications Security, pages 31-37, 1996.
Same as Diffie-Hellman, with more than two parties
Publicly known parameters
- p, the modulus, a large prime (2048 bits or more)
- q, a 256-bit prime
- g, a generator for an order-q subgroup of Z_p^*
Goal: Generate a secret value shared by all parties, e.g. Bob and Carol and Ted and Alice
- The secret value is K = g^bcta (mod p)
- b is a secret random number in the range 1 .. q−1 known only to Bob
- c is a secret random number in the range 1 .. q−1 known only to Carol
- t is a secret random number in the range 1 .. q−1 known only to Ted
- a is a secret random number in the range 1 .. q−1 known only to Alice
Technique
- Each party receives g to the power (everyone else's secret random numbers) (mod p)
  - Bob receives g^cta (mod p)
  - Carol receives g^bta (mod p)
  - Ted receives g^bca (mod p)
  - Alice receives g^bct (mod p)
- Each party computes K = (what they received) to the power (their own secret random number) (mod p)
  - Bob computes K = (g^cta)^b (mod p)
  - Carol computes K = (g^bta)^c (mod p)
  - Ted computes K = (g^bca)^t (mod p)
  - Alice computes K = (g^bct)^a (mod p)
Steiner et al.'s GDH.1 protocol
- (All powers of g are calculated (mod p))
- Bob sends {g^b} to Carol
- Carol sends {g^b, g^bc} to Ted
- Ted sends {g^b, g^bc, g^bct} to Alice
- Alice computes K = g^bcta
- Alice sends {g^a, g^ba, g^bca} to Ted
- Ted computes K = g^bcat
- Ted sends {g^at, g^bat} to Carol
- Carol computes K = g^batc
- Carol sends {g^atc} to Bob
- Bob computes K = g^atcb
Drawbacks of GDH.1: large number of messages, large total message size
- But it only requires point-to-point messages
Steiner et al.'s GDH.2 protocol
- (All powers of g are calculated (mod p))
- Bob sends {g^b} to Carol
- Carol sends {g^b, g^c, g^bc} to Ted
- Ted sends {g^bc, g^bt, g^ct, g^bct} to Alice
- Alice computes K = g^bcta
- Alice broadcasts {g^bca, g^bta, g^cta} to everyone
- Bob computes K = g^ctab
- Carol computes K = g^btac
- Ted computes K = g^bcat
Advantages of GDH.2 over GDH.1: smaller number of messages, smaller total message size
- But it does require a broadcast
Drawback of GDH.1 and GDH.2: large number of modular exponentiations per participant
Steiner et al.'s GDH.3 protocol
- (All powers of g are calculated (mod p))
- Bob sends {g^b} to Carol
- Carol sends {g^bc} to Ted
- Ted sends {g^bct} to Alice
- Alice computes K = g^bcta
- Alice broadcasts {g^bct} to everyone
- Bob computes 1/b = b⁻¹ (mod q), computes (g^bct)^1/b = g^ct, sends {g^ct} to Alice
- Carol computes 1/c = c⁻¹ (mod q), computes (g^bct)^1/c = g^bt, sends {g^bt} to Alice
- Ted computes 1/t = t⁻¹ (mod q), computes (g^bct)^1/t = g^bc, sends {g^bc} to Alice
- Alice broadcasts {g^cta, g^bta, g^bca} to everyone
- Bob computes K = g^ctab
- Carol computes K = g^btac
- Ted computes K = g^bcat
As with two-party Diffie-Hellman, all messages must be authenticated, otherwise group Diffie-Hellman falls to a man-in-the-middle attack
Must re-run the group key exchange protocol to generate a new session key whenever the group membership changes
- Backward secrecy -- New group members cannot decrypt messages previously sent in the old group
- Forward secrecy -- Former group members cannot decrypt new messages sent in the new group
Literature
- There are lots of variations of the above schemes in the literature
- Many papers do not address the authentication issue
- Jisoo Kim studied authenticated group key exchange protocols for his RIT CS master's project (https://ritdml.rit.edu/handle/1850/2770)
Problems
- Group key exchange protocols do not scale well
- Jisoo Kim's project showed that group key exchange protocols are unusable in practice -- they take too long
- The need for authentication creates a chicken-and-egg problem -- where do the authentication keys come from?
What I would do
- Forget group key exchange protocols
- Use a public key cipher to encrypt session keys
- Use digital signatures for authentication
- Use a PKI to authenticate each party's public keys
- The first party to arrive, Alice, generates a random session key
- When Bob arrives, he sends a request for the session key, including a nonce, along with his certificate, and signs the message (the nonce is to prevent replay attacks)
- Alice verifies Bob's certificate, verifies Bob's signature on the message, sets up a message containing (session key, Bob's nonce), signs the message, encrypts the signed message with Bob's public encryption key, and sends the result to Bob, along with her certificate
- Bob decrypts the message, verifies Alice's certificate, verifies Alice's signature on the message, verifies the nonce, and retrieves the session key
- To hinder eavesdroppers, every so often one of the parties generates and disseminates a new random session key
- When the group membership changes, everyone in the new group must get a new certificate with new public keys, and the session key must be changed (backward and forward secrecy)
- Other authors would object that this scheme does not let each party "contribute" to the shared value, as group Diffie-Hellman does
- I would reply that if you trust the PKI, you can just use the session key generated by any authentic group member without needing to "contribute" your own piece
- This scheme only addresses group session key management, it does not address the actual secure group communication

Secure Group Communication

This is an unsolved and relatively unexplored problem
Secure point-to-point communication: easy
- The TCP connection model -- set up security when you set up the connection
- Two-party session key establishment
- Confidentiality via encryption
- Authentication and integrity via MAC or digital signature
- Replay defense via nonces -- message sequence numbers
Secure one-to-many communication: not too bad
- One sender, many receivers
- Just set up a separate secure point-to-point channel from sender to each receiver
- N participants, O(N) secure channels
Secure group (many-to-many) communication: hard
- Everyone sends every message to everyone
- Using secure point-to-point channels doesn't scale
- N participants, O(N²) secure channels
Secure ad hoc group (many-to-many) communication: harder
- Everyone sends every message to everyone, and participants come and go all the time
- Now the key management also doesn't scale -- you'd be spending all your time establishing session keys
Parameters of a solution
- Broadcast messages, not point-to-point connections
- Lightweight group key establishment
- Replay detection without needing to keep a history of messages for each participant

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2011 Alan Kaminsky. All rights reserved. Last updated 18-Oct-2011. Please send comments to ark@cs.rit.edu.

4003-482-01/4005-705-01 Cryptography Chapter 13. Key Establishment Lecture Notes