Key Establishment Properties
March 1, 2021
1 Introduction
This document gives minimal examples for each of the key establishment prop- erties.
2 Key establishment properties
On the bottom of our hierarchy, we have four properties:
1. Key Freshness: the key established is new (either from some trusted third party or because it uses a new nonce).
2. Key Exclusivity: the key is only known to the principals in the protocol.
3. Far-end Operative: A knows that B is currently active (i.e., B is cur-
rently communicating with some principal, not necessarily A).
4. Once Authentication: A knows that B wished to communicate with A
at some point (but not necessarily during the current run).
While the first two properties are only related to the key, the second pair of properties is user- or entity-related. We will look at simple examples for each of these pairs.
2.1 Key-related Properties
First, we will see a protocol that has Key Freshness, but no Key Exclusivity. Then, we will have a look at a protocol that has Key Exclusivity, but no Key Freshness.
1
2.1.1 Key Freshness without Key Exclusivity
1. A¡úB: Na
2. B¡úA: Nb
3. A ¡ú B : {m}key(Na,Nb)
In this protocol, Na and Nb are nonces, i.e., fresh, random values chosen at the beginning of each protocol run. Thus, there is a new, fresh key for each run of this protocol.
However, since everyone can simply observe the messages and compute key(Na,Nb) on their own, the resulting key is not exclusive to A and B.
Possible ways to fix the key exclusivity are: using a Diffie-Hellman key- exchange instead of the nonces or adding public-key encryptions to the protocol.
2.1.2 Key Exclusivity without Key Freshness
Let g and the prime group p for the Diffie-Hellman key exchange be publicly known parameters. In contrast to the original DH key exchange, A chooses a value v0 and keeps this fixed but private over all runs of the protocol. Similarly, B chooses a value v1 and keeps this fixed but private over all protocol runs.
1. A¡úB: gv0
2. B¡úA: gv1
3. A ¡ú B : {m}gv0v1
Then, the resulting key is not fresh as it is the same in every protocol run. The key, however, is exclusively known to A and B since no-one can calculate
v0, v1 or the key gv0,v1 from the messages observed in the protocol. 2.2 User-related Properties
The user-related properties are defined one-sided, i.e., ¡°A knows B is active¡± does not mean that ¡°B knows A is active¡±. Most often, we are interested in both directions of these properties though.
In the following, we will only look at one direction of the properties. How- ever, the examples are such that the properties hold (or do not hold) in a mutual way. You can take it as an exercise to prove/disprove the other direction.
2.2.1 Far-end Operative without Once Authentication
1. A¡úB: EB(Na)
2. B¡úA: EA(Na,Nb)
3. A ¡ú B : EB(Nb),{m}key(Na,Nb)
In this protocol A can be sure that B is active (i.e., Far-end Operative w.r.t. A and B) because of messages 1 and 2. In message 1, A encrypts her nonce Na using B¡¯s public key. In message 2, A receives back her nonce Na. The only way, someone could have learned this nonce is by decrypting the first message. Hence, B must have been active and decrypted message 1.
2
However, A cannot be sure that B wishes to communicate with her as the following counter-example shows:
1. A ¡ú C(B) :
2. C(B) ¡ú A :
3. A ¡ú C(B) :
3¡ä. C ¡ú B :
EB(Na)
EA(Na, Nb) EB(Nb),{m}key(Na,Nb) EB(Nb),{m}key(Na,Nb)
1¡ä. C¡úB: EB(Na)
2¡ä. B¡úC: EC(Na,Nb)
This counter-example consists of two protocol runs that can easily be differenti- ated by the background colour: one protocol run between A and C (pretending to be B), and one protocol run between C and B. Here, B wishes to communi- cate with C, not with A. Still, A can be sure that B is currently active.
2.2.2 Once Authentication without Far-end Operative
1. A¡úB: gx,SA(B) 2. B¡úA: gy,SB(A) 3. A¡úB: {m}gxy
In this protocol, A can be sure B wishes to communicate with her, since B signed her identity in message 2 with his private key. Only B could produce SB (A).
However, this signature can be re-used by an attacker and the protocol does not fulfil Once Authentication. Given that the protocol has been run at least once as shown above, an attacker can run a new protocol run:
1. A ¡ú C(B) :
2. C(B) ¡ú A :
3. A ¡ú C(B) :
gu, SA(B) gv,SB(A) {m}guv
The attacker cannot produce SB(A) himself, but can simply replay the signa- ture from a previous protocol run. Thus, while A can be sure B wished to communicate with her at some point (in the previous run), she cannot be sure B is currently active. In the attacker¡¯s protocol run, B is not involved at all and thus inactive.
3