Modified Key Agreement Protocol Based On The Digital Signature Standard
Indexing terms: Public key, Digital signature
Arazi proposed a scheme to integrate a key exchange protocol into the DSS (digital signature standard) to authenticate two public keys exchanged between two users and then one corresponding secret session key can be shared by two parties based on the Diffie-Hellman public-key distribution scheme. Later, Nyberg and Rueppel pointed out a weakness in the Arazi protocol: if one secret session key is compromised then the others will be disclosed as well. This letter proposes a modified key agreement protocol based on the DSS.
Introduction:
Diffie and Hellman [1] proposed the well-known public-key distribution scheme based on the discrete logarithm problem in 1976 to enable two parties to establish a common secret session key based on their exchanged public keys. But their scheme did not provide authentication mechanism for the exchanged public keys. In 1985, ElGamal [2] proposed a digital signature scheme based on the discrete logarithm problem. The ElGamal signature scheme can provide an authenticated mechanism for distributing the public keys.
In 1993, Arazi [3] proposed a scheme to integrate a key exchange protocol into the DSS (digital signature standard) [4] to authenticate the public keys. Later, Nyberg and Rueppel [5] pointed out a weakness in the Arazi protocol: if one secret session key is compromised then the others will be disclosed as well. This letter proposes a modified key agreement protocol based on the DSS. Instead of distributing a single public key in each communication session, we propose to distributing multiple public keys in each session.
There are some public information that should be agreed to by all users.
- p = a large prime modulus, where 2511 < p < 2512.
- q = a prime divisor of p-1, where 2159< q < 2160.
- a , where a = h(p-1)/q mod p, h is a random integer with 1£h£p -1 such that h(p-1)/q mod p >1.
- xi = a secret key for user i, where 2159< xi < 2160.
- yi = a corresponding public key for user i, where
- H= the secure hash function (SHA) proposed by the NIST.
{p, q, a , yi} are public values and {xi} is each user's secret key.
Modified key agreement protocol:
We assume that user A wants to share three secret session keys with user B. Then,
(i) User A randomly selects two secret integers, v1 and v2 Œ[1, q-1] and computes
mA1=a v1 mod p
mA2=a v2 mod p
rA=(mA1mA2 mod p) mod q
sA=(v1+v2)-1[H(mA1, mA2)+xArA] mod q
and sends (mA1, mA2, sA) to B.
(ii) User B randomly selects two secret integers, w1 and w2 Œ[1, q-1] and computes
mB1=a w1 mod p
mB2=a w2 mod p
rB=(mB1mB2 mod p) mod q
sB=(w1+w2)-1[H(mB1, mB2)+xBrB] mod q
and sends (mB1, mB2, sB) to A.
(iii) User A computes
rB=(mB1mB2 mod p) mod q
verifies the DSS-signature (rB, sB) of the message (mB1, mB2). Then computes the shared secret keys as
KAB1= mB1v1 mod p
KAB2= mB2v2 mod p
KAB3= mB1v2 mod p.
(iv) User B computes
rA=(mA1mA2 mod p) mod q
verifies the DSS-signature (rA, sA) of the message (mA1, mA2). Then computes the shared secret keys as
KAB1= mA1w1 mod p
KAB2= mA2w2 mod p
KAB3= mA2w1 mod p
Security:
Let us follow the known-key attack proposed by Nyberg and Rueppel [5] to examine the security of the modified scheme. We have
KAB1= av1w1 mod p,
KAB2= a v2w2 mod p and
KAB3= a v2w1 mod p,
where
v1+v2=sA-1[H(mA1, mA2)+xArA] mod q,
w1+w2=sB-1[H(mB1, mB2)+xBrB] mod q.
Hence, by multiplying the above two equations, we obtain
v1w1+v1w2+v2w1+v2w2=sA-1sB-1[H(mA1, mA2)H(mB1, mB2)
+H(mA1, mA2)xBrB+H(mB1, mB2)xArA
+xArAxBrB] mod q.
From above equation, we obtain
(KAB1 KAB2 KAB3 a v1w2 )sAsB= a H(mA1, mA2)H(mB1, mB2)
yBH(mA1, mA2)(rB) yAH(mB1, mB2)(rA)
(a xAxB) (rArB) mod p.
Under known-key attack, since a v1w2 has never been used as the secret session key, all quantities in this equation except two values, a v1w2 and a xAxB , are publicly known or sent between the parties. Thus, the proposed known-key attack cannot work successfully in our modified scheme.
Conclusion:
We have proposed a key agreement protocol based on the DSS. This protocol allows to exchange n pairs of public keys between two users and to establish n2-1 secret session keys.
Lein Harn Nov. 22, 1994
(Computer Science Telecommunications Program, University of Missouri - Kansas City, MO 64110, USA)
References
1. Diffie, W. and Hellman, M. E.,: 'New directions in cryptography', IEEE Trans., IT-22, (6), 1976, pp. 644-654.
2. ElGamal, T.,: 'A public key cryptosystem and signature scheme based on discrete logarithms', IEEE Trans. on Info. Theory, Vol. IT-31, No, 4, July, 1985, pp. 469-472.
3. Arazi, A.,: 'Integrating a key cryptosystem into the digital signature standard', Electron. Lett., 29, (11), 1993, pp. 966-967.
4. 'The digital signature standard', Comm. ACM 35, No. 7, 1992, pp. 36-40.
5. Nyberg, K. and Rueppel, R. A.,: 'Weaknesses in some recent key agreement protocols', Electron. Lett., 30, (1), 1994, pp. 26-27.