The framework for key distribution protocols
The framework for key distribution protocols
Classification of possible approaches to key distribution:
- Physical distribution: this is not scalable and the security no longer relies solely on the key.
- Distribution using symmetric key protocols.
- Distribution using public key protocols.
If we have n users each of whom wish to communicate securely with each other then we would require (n(n−1))/2 secret keys. One solution to this problem is for each user to hold only one key with which they communicate with a central authority, so n users will only require n keys. When two users wish to communicate they generate a session key which is only to be used for that message; this can be generated with the help of the central authority and a security protocol. Key Distribution features:
1. symmetric encryption schemes require both parties to share a common secret key (issue is how to securely distribute this key without revealing it to an adversary)
2. many attacks are based on poor key management and distribution (rather than breaking the codes). This is, actually, the most difficult problem in developing secure systems
Key distribution protocols
- Diffie–Hellman key exchange (D–H)
- Needham–Schroeder protocol
- Otway–Rees protocol
- Х .509 key distribution
- MTI protocol
- Shamir's Secret Sharing algorithm
- Blom's scheme
- STS (Station-to-Station) protocol STS protocol
- Kerberos Protocol
Diffie-Hellman (D–H) protocol
D–H is one of the earliest practical examples of public key exchange, implemented in cryptography. Secure communication over a public channel is one of the fundamental problems of cryptography. To get the message encrypted and decrypted, both sides need to have a shared key, but if the same channel is used to transmit the key, the listening party will also get it.
D-H algorithm allows two parties to obtain a shared secret key communication over a public, but protected from spoofing the communication channel. The resulting key can be used to exchange messages using symmetric encryption.
Protocol of Diffie–Hellman key agreement (basic version):
Summary: A and B each send the other one message over an open channel.
Result: shared secret key K known to both parties A and B
1. One-time setup. An appropriate prime p and generator α of ℤp (2 ≤ α ≤ p-2) are selected and published.
2. Protocol messages.
A → B: α x mod p (1)
A <-- B: α y mod p (2)
3. Protocol actions. Perform the following steps each time a shared key is required.
- (a) A chooses a random secret x, 1≤ x ≤ p-2, and sends B message (1).
- (b) chooses a random secret y, 1≤ y ≤ p-2, and sends A message (2).
- (c) receives α x and computes the shared key as K = (α x)y mod p.
- (d) receives α y and computes the shared key as K = (α y)x mod p.
Needham-Schroeder public-key protocol
The Needham-Schroeder protocol is a common name for symmetric and asymmetric authentication protocols and key exchange. The symmetric encryption option uses an intermediate trusted party and is the basis for a whole class of protocols alike, e.g. Kerberos is one of the options of the symmetric Needham - Schroeder protocol.
Summary: A and B exchange 3 messages.
entity authentication, key authentication, and key transport (all mutual).
1. Notation. Px (Y) denotes public-key encryption (e.g. RSA) of data Y using party X's public key; Px (Y1, Y2) denotes the encryption of the concatenation of Y1 and Y1 . k1 k2 are secret symmetric keys chosen by A, B respectively.
2. On-time setup. Assume A, B possess each other's authentic public key. (If this is not the case, but each party has a certificate carrying its own public key, then one additional message is required for certificate transport).
3. Protocol messages.
A → B: Pb (k1 , A) (1)
A <--B: Pa (k1 , k2) (2)
A → B: Pb (k2) (3)
4. Protocol actions.
- (a) A sends B message (1).
- (b) B recovers k1 upon receiving message (1), and returns to A message (2).
- (c) Upon decrypting message (2), A checks the key k1 recovered agrees with that sent in message (1). (Provided k1 has never been previously used, this gives A both entity authentication of B and assurance that B knows this key.) A sends B message (3).
- (d) Upon decrypting message (3), B checks the key k1 recovered agrees with that sent in message (2). The session key may be computed as f ( k1, k2) using an appropriate publicly known non-reversible function f.
The Needham-Schroeder Secret-Key protocol can be viewed as follows:
The Otway-Rees protocol can be viewed as follows:
Summary: B interacts with trusted server T and party A.
Result: establishment of fresh shared secret K between A and B.
1. Notation. E is symmetric encryption algorithm (see remark 12.19). k is a session key T generates for A and B, respectively, to allow verification of key freshness (thereby detecting replay). m is a second nonce chosen by A which serves as a transactional identifier.
2. One-time setup. T shares symmetric keys Kat and Kbt with A, B, respectively. )
3. Protocol messages.
A → В: M, A, B, EKAT(NA, M, А, В) (1)
B→T:MiA1B1 EKAT (NA,M, A, B), EKBT (NB, M, A, B) (2)
B <--T: EKAT (NA,k),EKBT(NB,k) (3)
A<--B: EKAT(NA,K) (4)
1. Protocol actions.Perform the following steps each time a shared key is required.
(a) A encrypts data for the server containing two nonces, NA and M, and the iden¬tities of itself and the party В to whom it wishes the server to distribute a key. A sends this and some plaintext to В in message (1).
(b) В creates its own nonce NB and an analogous encrypted message (with the same M), and sends this along with A's message to T in message (2).
(c) T uses the cleartext identifiers in message (2) to retrieve К AT and К вт»then verifies the cleartext (M A, B) matches that recovered upon decrypting both parts of message (2). (Verifying M in particular confirms the encrypted parts are linked.) If so, T inserts a new key к and the respective nonces into distinct messages encrypted for A and B, and sends both to В in message (3).
(d) В decrypts the second part of message (3), checks NB matches that sent in mes¬sage (2), and if so passes the first part on to A in message (4).
(e) A decrypts message (4) and checks NA matches that sent in message (1).
If all checks pass, each of A and В are assured that к is fresh (due to their respective nonces), and trust that the other party T shared к with is the party bound to their nonce in message (2). A knows that В is active as verification of message (4) implies В sent message (2) recently; В however has no assurance that A is active until subsequent use of к by A, since В cannot determine if message (1) is fresh.
Station-to-Station (STS) protocol
- Provides mutual entity authentication
- The STS Protocol is a mutual authentication protocol that uses the ideas of Diffie-Hellman protocol and RSA.
- One-time setup; Choose p and a as before. Use RSA public and private keys for signatures. Assume A has access to B's. public key and v.v.
1. A -> B: α x mod p (for random x mod p chosen by Alice
2. В<-- A: α y mod p, Ek(SB(α y, α x))
3. A -> B: Ek (SA (α x, α y))
- Alter A receives Message 2 from B, she Is assured that B has α x and that the α y she received is from Bob since it contains B's signature. A sends В a confirmation in Message 3, so ditto for В after he receives Message 3 from A.
- A and В both compute k = α xy Kr mod p and is the key used in encryption and decryption above.
- STS eliminates Man-In-the-Middle attack.
X.509 key distribution
The algorithm X. 509 is an open-key authentication standard. It implies a system of certificates that are produced by special trusted parties. Alice's certificate, issued by the Center, contains Alice's public keys for signing or encoding. This certificate is also signed by the Center and can't e, i.e. no one can forge.
Here the message Alice
mA = (tA, rA, Bob, PB(kA)),
and message from Bob
mA = (tB, rB, Alice, PA(kB)),
t is timestamp, which should not be too old, and r is a random number, which should not be repeated).
The result is an authentication and an exchange of the secret keys kA and kB .
In an attempt to provide implicit key authentication in the classical Diffie-Hellman key agreement protocol, Matsumoto, Takashima, Imai, designed three infinite families of key agreement protocols. The MTI/A0 and MTI/C0 are two special cases of these families that are much studied in the literature.
- a and b are the private keys of A and B
- ga and gb are public keys of A and B
- Secure against passive attacks only
- Provides mutual (implicit) key authentication but neither key confirmation nor entity
1. A generates a random integer rA, 1 ≤ rA ≤ n-1, computes the point TA = rAgb, and sends TA to B.
2. B generates a random integer rB, 1 ≤ rB ≤ n-1, computes the point TB = rBga, and sends TB A to A.
3. A computes K= a^(−1)rATB = rArBP.
4. B computes K= b^(−1)rBTA = rArBP
5. The shared secret is the point K.
Shamir’s No Key Algorithm
The Three-Pass Protocol works as follows:
1) The sender chooses a private encryption key s and a corresponding decryption key t. The sender encrypts the message m with the key s and sends the encrypted message E(s,m) to the receiver.
2) The receiver chooses a private encryption key r and a corresponding decryption key q and super-encrypts the first message E(s,m) with the key r and sends the doubly encrypted message E(r,E(s,m)) back to the sender.
3) The sender decrypts the second message with the key t. Because of the commutativity property described above D(t,E(r,E(s,m)))=E(r,m) which is the message encrypted with only the receiver's private key. The sender sends this to the receiver.
The receiver can now decrypt the message using the key q, namely D(q,E(r,m))=m the original message.
Notice that all of the operations involving the sender's private keys s and t are performed by the sender, and all of the operations involving the receiver's private keys r and q are performed by the receiver, so that neither party needs to know the other party's keys.
Blom's scheme is a symmetric threshold key exchange protocol in cryptography.
SUMMARY: each of n users is given initial secret keying material and public data.
RESULT: each pair of users Ui, Uj may compute an m-bit pairwise secret key Ki,j.
1. A k×n generator matrix G of an (n, k) MDS code over a finite field Fq of order q is made known to all n system users.
2. A trusted party T creates a random secret k × k symmetric matrix D over Fq.
3. T gives to each user Ui the secret key Si, defined as row i of the n × k matrix S = (DG)^T . (Si, is a k-tuple over Fq. of k · lg(q) bits, allowing Ui to compute any entry in row i of (DG)T G).
4. Users Ui and Uj compute the common secret Ki,j = Ki,j of bitlength m = lg(q) as follows. Using Si and column j of G, Ui computes the (i, j) entry of the n×n symmetric matrix K = (DG)T G. Using Si and column i of G, Ui similarly computes the (j, i) entry (which is equal to the (i, j) entry since K is symmetric).
Kerberos builds on symmetric key cryptography and requires a trusted third party, and optionally may use public-key cryptography during certain phases of authentication. Kerberos uses UDP port 88 by default.The working scheme of Kerberos protocol
- Mandate request for the server mandate
- Mandate for the server mandate
- Server mandate request
- Server mandate
- Service request
- Timestamp, encrypted with the session key
1. The client asks the authentication server for mandate to address the TGS (Ticket-Granting Server). KDC (Key Distribution Center) plays the role of the authentication server. KDC sends mandate which contains a unique session key to the client for the upcoming session. A copy of the session key transferring to the server, gets encrypted with the long-term key of this server (steps 1-2);
2. To connect to a specific server, the client queries the TGS the mandate to address to the server. KDC also plays the role of the TGS. If everything is in order, the KDC sends the ticket to the client (steps 3-4)
3. The client presents the received mandate to the server together with the authenticator. If the client's identity is true, the server provides the client access to the service (steps 5-6).
- symmetric encryption
- session key
- central authority
- public-key protocol
Go to Bibliography
Back to Table of Contents