A New Three-party Key Exchange Protocol Based on Diffie-Hellman

An important problem in cryptography is how to create keys in exchange protocol, such as DES or AES, especially when two parties are far away[1]. In secure communications, key exchange protocol has an important role in the foundation [2]. Key exchange protocol is aiming to communicate safely in unsafely channel by the communication parties’ interaction and to establish common session key. Communication parties’ sharing key used to be a difficult problem before public key cryptography appears.

The procedure needs a safety channel, which means special messengers in physical. Public key cryptography’s significant advantage is to exchange keys without safety channel. The earliest reality protocol is brought out by Diffie and Hellman, which is named Diffie-Hellman Exponential Key Exchange Protocol[3]. Its security closely related to the difficulty of computing discrete logarithm problem[4],[5]. The protocol can not only establish sharing key, also provide three-party and multy-party session key.

Some protocols depend on public key technology, and need PKI system. The cost is high. Some protocols need two parties share long random key. The key usually is chosen by appropriate program, and is difficult to be remembered and be saved. So a natural idea is to share easy remembering private key, and create high quality session key. Now, usually 3 PAKE uses the model of user-server-user, which limits practical application.

A 3 PAKE based on Diffie-Hellman is proposed , which could establish safe and reliable session key. Three users can communicate safely in the unsafely channel. The paper analyzes the efficiency and safety comparing with the existence protocol. A protocol is not only an algorithm, but also a communicating. The communication

This article is sponsored by the Talents Foundation of Ludong University(No.LY20062706)

* Corresponding author:

procedure includes transferring messages by different participants in the agreed rules. So the protocol has a dimension, which called communication round. Usually, the cost of communication is larger than local computation [6]. The goal of key exchange protocol is to establish a common and secure session key using the interactive communications. The existing schemes are usually in the pattern of ‘user-server-user’, so are weak in reality. Thus we hope to minimize reduce the rounds of communication. The 3PAKE only needs two round communication, and it also can provide forward security and key security and against known key attack.

• 2.    Prepared Knowledge

  • 2.1.    Discrete logarithm problem (DLP)

• 2.2.    Computational Diffie-Hellman problem(CDHP)

• 2.3.    Diffie-Hellman Public Exchange Protocol

Security of some cryptography technology is based on DLP difficulty. The general DLP [6]: Given a finite cyclic group G ordered by n, and a generator ^a and an element ^в belong to G. Now solve an integer x ( 0 <  x <  n - 1 ), which could meet ^{a в} .

The general CDHP[7]: Given a finite cyclic group G, a generator ^a and an element ^a and an element ^a , ab now solve ^a

CDHP has no a reality and feasible solution yet[8].

A classical Diffie-Hellman public exchange protocol exam of two parties is given. Alice and

Bob establish session key K on public channel[1].

( mod p ) , p and a are public.

• 1)    Alice or Bob choose a safety large prime ^P and a generator ^a

• 2)    Alice chooses a private random number x ( ^{1 <}  x <  ^{P 2} ), Bob privately chooses a random

У (1 ^ У ^ P - 2)

• 3)    Alice sends ^a x ^{( mod} P ) to Bob , and Bob sends ^a y ^{( mod} P ) to Alice .

• 4)    By using their respective received information, they calculate session key K , Alice uses ^{K a} ) x ( mod p ) to get K , Bob uses K ^ ^{( a} x ) y ^{( mod} P ) to get K .

• 3.    A New 3PAKE Based on Diffie-Hellman

• 3.1.    Initialization Process

A new 3 PAKE based on Diffie-Hellman is brought up, and the following is detailed protocol procedure. Table 1 intuitively describes the protocol implementation.

F q is a finite field, A , B and C are users, public key of A is  A , private key is A , B ’s public key is yB , and private key is xB , C ’s public key is yC , private key is xC . Every user’s public key and private key

x

У = g           y = g have the function relation            , that is to say A

xA

,

У в = g x^B У с = g x^C

,

.

• 3.2.    Protocol Process

If A , B , C want to establish session key, the protocol process is shown in table 1.

• Round 1

axA

F                          TT.„ = У„

User A chooses a random constant number a in ^q , calculates and makes public of ^{AB     B}

,

Тлг = y.a           T.„ T»r ac     c , and sends AB , ac respectively to user B , C .

F                 T T„ = У bxB

,

User B randomly chooses constant number b in ^q , calculates and make public ^{BA     A}

Тпг = УгЬХВ        ЛГ„. Ткг bc     c , and sends BA , bc respectively to user A , C .

F„         Тг    у/^ Т_в = У^^

User C randomly chooses constant number c in ^q , calculates ^{ca     a} , ^{cb     b} and makes

TT them public, and sends CA , CB respectively to user A , B .

• Round 2

Т„ = У? ^{Х в}                    У

User A receives ^{BA     A} sent by B , and ^{ca    a} sent by C ,

A Calculates like this:

x_A T BA

- 1

b       bx

= У в = g B ^Tca

,

xA '

= У с^С = g ^cx C   к = g ax A • g ^bx B

,

cx

• g

__ ax_A + bx _s + cx_c

.

R . T. „ = у“^Ха     л а            = У_п^СХс      , с

User B receives ^{AB     B} sent by A , and ^{cb    b} sent by C ,

B Calculates like this:

xB

TAB

- 1

a       ax

= У а = g A T CB

,

xB

- 1

c

= У с = g

^cx C   K = g ^ax A • g bx B

,

cx

• g

ax + bx + cx

.

тт С ■   TA С   У С

User receives ^{AC     C}

C Calculates like this:

axA

sent by A , and ^BC

= У bxB yC sent by B ,

x_C ^T AC

a      ax

= У а = g A ^Tbc

,

- 1

-i xC

b

= У в = g

^bx B K = g ax A • g ^bx B

,

cx

• g

__ ax_A + bx_B + cx_c

.

K is the three-party session key of A , B and C .

Table 1. Proposed protocol

Protocol               Users	User A	User B	User C
Public key	y A	y B	y C
Private key	xA	xB	xC
Random	a	b	c
Round 1      Calculating	ax T AB = У в  ^ B ,	bxB TBA = y A  ^ A ,	cx TCA = У A  _ A ,
and sending	T ac = У      C	bx TBC = У с  ^ C .	cx T CB = У b
Receiving	TBA TCA ,	T AB T CB ,	T  J AC   BC ,
	x          b      bx TBA   = У в = g B	- 1 x B           a       axA 1 AB      yA     g	- 1 x          a      ax TAC C  = У A = g A
Round 2	,	, - 1	, - 1
Calculating	x           c       cx T CA A = У с = g C	x           c       cx T CB B = Ус = g C	x          bbx T BC C = У B = g
	__   ax A + Ьх в + cx c .	ax, + bxR + cxr K = g A   B  c .	j^ _ g axA + Ьхв + cxc .

4. Analysis of Efficiency and Safety

• 4.1.    Efficiency Analysis

• 4.2.    Security Analysis

Now, let’s to analyze the protocol efficiency from computing cost and communication cost. Every user needs 4 exponentiations and 3 multiplications to establish a session key. Every time protocol runs, three users need 2 rounds of communication.

• 1)    Correctness and fairness

If members honestly run protocol, the session key will be the same. Every honest member provides the needed information of the session key in discussion. Every member can calculate session key only if he gets others’ information. No one can establish session key himself.

• 2)    Key confidentiality

The protocol can provide key confidentiality.

@ Because of the difficulty of CDHP, competitor could not get any information about key by intercepted T ^AB , ^AC , T ^BA , ^BC , ^CA and ^CB .

@ Supposed the enemy could distinguish session key and random string by non-negligible probability, which means they could solve DLP problem. It contracts with the difficulty of DLP problem.

• 3)    Forward Security

The forward security of key exchange protocol based on Diffie-Hellman means even the attackers can get one or more private key, it could not affect session key’s security previously created. That is to say the session

xx   x key and private key are independent. Even A , B and C are leaked, the attackers can’t destroy key confidentiality. Every session key’s establishment needs user’s random number a , b c and ^   axA + Ьхв + cxc g          .If the attackers want to get these random numbers, they should solve DLP problem, which is difficult.

• 4)    Known key security

Even attackers get some communication’s session key, they couldn’t get other communications’ session key. That is to say session key is independent. The quality is known key security. The protocol is known key security. The final session is established by some random numbers. In the protocol, a , b , c are chosen randomly by A , B , C .To the attackers, getting one session key, has no help to other session keys.

• 5)    No key control

Any party in the communication couldn’t choose a predetermined value, meanwhile two parties contribute ax A + Ьх в + cx c to the final session key. No one could control the key’s chosen .The final session key       g           ,

K depends on user A , B , C ’s chosen random numbers and their private key, No party can determine the value of session key.

• 6)    Anti-replay attack

• 5. Conclusion

Every session key is independent, and it has the characteristic of one-time password. It can defend replay attack.

The new 3 PAKE based on Diffie-Hellman problem was proposed. Its security bases on DLP, and has better security. The protocol can establish effective three-party session key, and can provide key confidentiality, forward security, and no key control. Comparing with existence protocol, it is fit for practical applications not like the existing schemes in the pattern of ‘user-server-user’.