Hybrid key transport protocols using PK encryption
In contrast to the preceding key transport protocols, the Beller-Yacobi protocol uses symmetric encryption in addition to both PK encryption and digital signatures. Such protocols using both asymmetric and symmetric techniques are called hybrid protocols.
Beller-Yacobi protocol (4-pass)
The key transport protocol of Beller and Yacobi, which provides mutual entity authentication and explicit key authentication, was designed specifically for applications where there is an imbalance in processing power between two parties; the goal is to minimize the computational requirements of the weaker party. (Candidate applications include transactions involving chipcards, and wireless communications involving a low-power telephone handset.) Another feature of the protocol is that the identity of one of the parties (the weaker, here A) remains concealed from eavesdroppers.
Essentially, A authenticates itself to В by signing a random challenge m, while В authenticates itself to A by demonstrating knowledge of a key К only В itself could recover. For simplicity of exposition, the protocol is described using RSA with public exponent 3, although Rabin’s scheme is more efficient and recommended in practice (but see Note 8.13 regarding chosen-ciphertext attack).
12.44 Protocol Beller-Yacobi key transport (4-pass)
SUMMARY: A transfers key К to В in a 4-pass protocol.
RESULT: mutual entity authentication and mutual explicit key authentication.
1. Notation.
Ек(у) denotes symmetric encryption of у using key К and algorithm E.
Px (y) denotes the result of applying X’s public-key function to y.
Sx(y) denotes the result of applying X’s private-key function to y.
Ix denotes an identifying string for party X.
h(y) denotes the hash of y, used in association with the signature scheme.
If у = (yi,... , y_{n}), the input is the concatenation of these multiple values.
- 2. System setup.
- (a) Selection of system parameters. An appropriate prime ns and generator a for the multiplicative group of integers modulo ns are fixed as ElGamal system parameters. A trusted server T chooses appropriate primes p and q yielding public modulus пт = pq for RSA signatures, then for public exponent ep = 3 computes a private key dp satisfying: epdp = 1 mod (p - l)(q - 1).
- (b) Distribution of system parameters. Each party (A and B) is given an authentic copy of T’s public key and the system parameters: up, (ns, a). T assigns to each party X a unique distinguished name or identifying string Ix (e.g., X’s name and address).
- (c) Initialization of terminal. Each party playing the role of A (terminal) selects a random integer a, 1 < a < ns - 2, and computes its ElGamal signature public key и a = a“ mod ns- A keeps its corresponding private key a secret, and transfers an authentic copy of и a to Г, identifying itself to T by out-of- band means (e.g., in person). T constructs and returns to A the public-key certificate: certA = {Ia, ua, Ga). (The certificate contains A’s identity and ElGamal signature public key, plus T’s RSA signature Ga over these: G, = St(Ia, «л) = Ch(I_{A}, u_{A}))^{dr} mod np.)
- (d) Initialization of server. Each party playing the role of В (server) creates an encryption private key and corresponding public key based on RSA with public exponent ев = 3. В chooses a public-key modulus пв as the product of two appropriate secret primes, and itself computes the corresponding RSA private key (1ц. В transfers пв to T, identifying itself to T by out-of-band means. T then constructs and returns to В the public-key certificate: certs = (Ib, пв, Gb). (Tire certificate contains IPs identity and RSA encryption public key пв, plus T’s RSA signature over these: Gb = St(Ib, пв) = (h(Ie, n_{B}))^{dr} mod np.)
- 3. Protocol messages.
- 4. Protocol actions. The following steps are performed each time a shared key is required. The protocol is aborted (with result of failure) if any check fails.
- (a) Precomputation by terminal. A selects a random x, 1 < x < ns - 2, and computes three values: v = a^{x} mod ns', x~^{l} mod (ns — 1); and av mod (ns - 1). (For the security of ElGamal signatures, x must be new for each signature, and be co-prime to ns - 1 to ensure x~^{l} exists.)
- (b) В sends to A message (1).
- (c) A checks the authenticity of ns by confirming: h(In, »s) = Gs^{3} mod nj A chooses a random key 1 < К < тгв - 1 and sends В message (2), where Y = P_{B}(K).
- (d) В recovers К = Sb(Y) = Y^{d,i} mod ns- (The final two messages will be encrypted using К.) В chooses a random integer m as a challenge, extends it with t (say t и 50) least significant zeros, symmetrically encrypts this using key K, and sends A message (3).
- (e) A decrypts the received message, and checks it has t trailing zeros; if so, A accepts that it originated from В and that В knows key K. A takes the decrypted challenge m, concatenates it to the identity Ib of the party whose public key it used to share К in message (2), forming the concatenated quantity M = (m, Ib), then computes w satisfying: w = (M — av) ■ x~^{l} mod (ns — 1), and sends В message (4). (Here (v, w) is A’s ElGamal signature on M, and cert a = (Ia, и a, Ga)- The identity Iв in M is essential to preclude an intruder-in-the-middle attack - see §12.9.)
- (f) В decrypts the received message, and verifies the authenticity of и a by checking that: h(I,, и a) = Ga^{3} mod пт- Finally, В constructs the concatenated quantity M = (m, Iв) from the challenge m remembered from message (3) and its own identity, then verifies A’s signature on the challenge by checking that: a^{M} = ua^{[1]} ^{[2]} ^{[3]} ^{[4]} ^{[5]} ^{[6]} ■ v^{w} mod ns- If all checks succeed, В accepts the party A associated with identity I, as the source of key K.
session key К = v^{[7]} sends to B: Pb(v), E_{v}(certA, «>)■ В recovers v (= K) via public- key decryption, uses it to recover cert a and w, then verifies cert a and A’s signature (v, w) on M = (m, Iв).
The 2-pass protocol has slightly weaker authentication assurances: В obtains entity authentication of A and obtains a key К that A alone knows, while A has key authentication with respect to B. For A to obtain explicit key authentication of В (implying entity authentication also), a third message may be added whereby В exhibits knowledge through use of К on a challenge or standard message (e.g., {0}'). All three of A’s asymmetric operations remain inexpensive.
terminal A |
server В |
precompute x, v = a^{x} mod ns verify certs via Pt(Gb) <~ compute (v, w) = S,(m. Ib) send Pb(v), E_{v}(certA,u>) — certA = (Ia, ua, Ga) |
select random challenge m — send m, cert в cert в = (Ib, пв, Gb) -a recover v, set К = v verify certA, signature (v, w) |
Figure 12.2: Summary of Beller-Yacobiprotocol (2-pass).
In Figure 12.2, an alternative to using К = v as the session key is to set К = w. This results in the property that both parties influence the value of К (as w is a function of both m and x).
- [1] 12.45 Note (on Beller-Yacobi key transport protocol)
- [2] To achieve mutual authentication here requires that each party cany out at least oneprivate-key operation (showing knowledge of its private key), and one or two public-key operations (related to verifying the other’s identity, and its public key if notknown a priori).
- [3] The novelty here is careful selection of two separate public-key schemes, each requiring only an inexpensive computation by the computationally limited party, inthis case A. Choosmg RSA with exponent 3 or Rabin with exponent 2 results inan inexpensive public-key operation (2 or 1 modular multiplications, respectively),for encryption and signature verification. Choosing ElGamal-family signatures, theprivate-key operation is inexpensive (a single modular multiplication, assuming pre-computation).
- [4] DSA signatures (Chapter 11) or others with similar properties could be used in placeof ElGamal signatures. 12.46 Remark (signature scheme used to certify public keys) Protocol 12.44 requires an ElGamal public key be certified using an RSA signature. This is done for reasons of efficiency,and highlights an advantage of allowing signature public keys from one system to be certified using signatures of a different type.
- [5] Beller-Yacobi protocol (2-pass)
- [6] Protocol 12.44 can be modified to yield a 2-pass protocol as illustrated hi Figure 12.2. Themodified protocol is obtained by essentially combining the pair of messages each partysends into a single message, as now described using notation as in Protocol 12.44. В generates a random challenge m and sends to A: m, cert в ■ A computes its ElGamalsignature (v,w) on the concatenation M = (m. 7b), and using part v of the signature as the
- [7] A side effect of using К = v is that A no longer directly controls the key value, transforming the key transportprotocol into a key agreement. Alternately, a random x could be chosen by A and used as key К = x, and x couldbe sent encrypted alongside w.