To combine the ease of use of a Dif¬e-Hellman key agreement protocol with the se-

curity of an authenticated RSA key exchange, we present an identity-based key agree-

ment protocol in which the endpoint addresses of the communication devices are used

to authenticate the devices involved in a key agreement. The use of IBC allows us

to both reduce and spread the administrative burden of key management by seam-

lessly integrating the cryptographic solution into the existing network infrastructure.

Our scheme allows multiple organizations to operate ID-PKGs autonomously, while al-

lowing their customers to operate across organizational borders. This greatly simpli¬es

the otherwise thorny issue of private key distribution present in global IBE or PKI so-

lutions. Furthermore, the choice of coupling the cryptographic system to the network

layer allows us to piggyback much of the security overhead to the existing network

infrastructure. The proposed system is capable of coping with NAT traversal, and us-

ing key expiration coupled with dynamic key deployment allows for dynamic endpoint

allocation.

In the following, our identity-based key agreement system called Secure Session

Framework (SSF) is presented. First, the four basic steps of the system are described

for the single ID-PKG scenario. Then, the scheme is extended to incorporate multiple

autonomous ID-PKGs which use different public parameters without requiring entities

from one ID-PKG™s domain to contact the ID-PKGs of other domains.

3.2 Algorithmic Overview

The proposed identity-based key agreement protocol SSF consists of four main algo-

rithms: Setup, Extract, Build SIK, and Compute. The ¬rst two are executed by the

private key generator and the last two are executed by a participating device. Their

description follows below.

3.3 Key Agreement

The Setup algorithm is executed by the ID-PKG. This part of the key agreement proto-

col is only performed once and creates both the master secrets P and Q as well as the

public parameters.

An Identity-Based Key Agreement Protocol for the Network Layer 413

Setup - The Setup algorithm is executed by the ID-PKG.

Input: k ∈ N

Step 1: Choose an arbitrary integer R > 1 from Z+ .

Step 2: Generate two primes, P and Q, of bit length k with the following properties:

1. The prime factorization of (P ’ 1) contains a large prime P

2. The prime factorization of (Q ’ 1) contains a large prime Q

3. (•(PQ), R) = 1, where •(·) is the Totient Function.

4. The computation of discr. log. must be infeasible in ZP and ZQ .

Step 3: Compute the product N = PQ

Step 4: Choose a generator G of a subgroup G of ZN whose order contains at least

one of the primes P or Q .

Step 5: Choose a cryptographic collision-resistant hash function H : {0, 1}— ’ ZN .

Output: PSP = (N, G, R, H(·)), SP = {P, Q}

De¬nition 1 (Public, Shared Parameters). The public, shared parameters (PSP) of a

domain D of the key agreement scheme SSF is the quadruple PSP = (N, G, R, H(·))

The Extract algorithm creates the identity key (i.e. the private key) for a given identity.

This algorithm is executed by the ID-PKG. If all IDs are known and the range is not too

big (e.g. a Class B or C subnet of the Internet), it is possible to execute this step for all

IDs of¬‚ine, and the master secrets can then be destroyed, if required.

Extract - The Extract algorithm is executed by the ID-PKG.

Input: PSP, SP, ID

Let ID be a given identity. The algorithm computes dID ≡ H(ID)1/R mod N. The

integer dID is called the identity key and is given to the entity EID .

Note: Due to the requirement (•(N), R) = 1, the R-th residues form a permutation in

ZN .

Ouput: dID

The Build SIK algorithm is executed by the devices taking part in the key agreement.

Build SIK - The Build SIK algorithm is executed by the entity EID

Input: PSP, dID , k1 , k2

Step 1: Choose a random integer rID in the interval [2k1 , 2k2 ].

Step 2: Compute SIKID ≡ GrID · dID mod N.

SIKID is the SIK (session initiation key) for the identity string ID which belongs to

entity EID .

Output: SIKID

The random integer rID is generated with a secure number generator to make rID un-

predictable. The private identity key is used in combination with this randomly chosen

integer and the generator in such a way that it is not possible to extract the identity key

from the SIK. This is due to the fact that the multiplications are performed in the ring

ZN and the result set of a division in the ring ZN is so large that the extraction of the

414 C. Schridde, M. Smith, and B. Freisleben

identity key is infeasible. The SIK is then sent over an unsecured channel to the other

party and vice versa. The SIK must be greater than zero to prevent a trivial replacement

attack where an attacker replaces the SIKs with zero which in turn would make the

session key zero as well. Any other replacement attacks lead to invalid session keys.

The ¬nal step of the key agreement process is the computation of the session key

using the Compute algorithm which is executed by the devices taking part in the key

agreement. By applying the inverse of the hash value of the opposite™s identity, the in-

volved identity key is canceled out. Only if both endpoint addresses match their identity

keys, a valid session key is created.

Compute - The Compute algorithm is computed when two entities are performing a

key agreement.

Input for EIDA : PSP, SIKIDB > 0, IDB , rIDA

Input for EIDB : PSP, SIKIDA > 0, IDA , rIDB

When EIDA receives the session initiation key from EIDB , it calculates

(SIKB H(IDB )’1 )rIDA ≡ ((GrIDB dIDB )R H(IDB )’1 )rIDA ≡ GRrIDA rIDB ≡ S mod N

R

When EIDB receives the session initiation key from EIDA ,it calculates

(SIKA H(IDA )’1 )rIDB ≡ ((GrIDA dIDA )R H(IDA )’1 )rIDB ≡ GRrIDA rIDB ≡ S mod N

R

Output: S

3.4 Key Agreement between Different Domains

The ID-PKG determines the public, shared parameters, and all entities which receive

their identity key for their IDs from this generator can establish a key agreement among

each other. In practice, it is unlikely that all devices will receive their identity key

from the same security domain, since this would imply the existence of a third party

trusted by all with a secure communication link to all devices. The Internet is di-

vided into many Autonomous Systems (AS) each with its own IP range and respon-

sible for the management of its users. Thus, it is desirable that each AS can operate its

own ID-PKG.

In this section, we show how cross-domain key agreement can be achieved such that

only the public parameters must be distributed (which will be discussed in section 4).

Each device only needs a single identity key, and the ID-PKGs do not need to agree

on common parameters or participate in any form of hierarchy. In the following, we

assume without loss of generality, that there are two domains D1 and D2 . Their public

parameters are (N1 , G1 , R1 , H1 (·)) and (N2 , G2 , R2 , H2 (·)), respectively. Every parameter

can be chosen independently. The case that (R2 , •(N1 )) > 1 or (R1 , •(N2 )) > 1 is not

critical, since no R-th roots must be computed regarding the other domain™s modulus.

The two moduli N1 and N2 were chosen according to the requirements stated in the

Setup algorithm, i.e. the computation of discrete logarithms is infeasible in ZN1 and

ZN2 , respectively. Consequently, an algorithm such as the Pohlig-Hellman algorithm

[20] cannot be applied and Pollard™s P ’ 1 factoring algorithm [21] will not be a threat.

Thus, a random non-trivial integer has a large order in ZN1 N2 with an overwhelming

probability, and the computation of discrete logarithms is infeasible in ZN1 N2 . In the

following, an entity EIDA from D1 wants to communicate with EIDB from D2 .

An Identity-Based Key Agreement Protocol for the Network Layer 415

Cross-Domain Extension (from the view of entity EID )

Input: PSP1, PSP2, dID

Step 1: Calculate the common, shared, public parameters: PSP1,2 = (N1 · N2 , G1 ·

G2 , R1 · R2 , H2 (·)).

Step 2: Use the Chinese-Remainder Theorem to calculate the integer dID : dID ≡

dID mod N1 and dID ≡ 1 mod N2

Step 3: Use the Chinese-Remainder Theorem to calculate the integer H1 (ID):

H1 (ID) ≡ H1 (ID)R2 mod N1 and H1 (ID) ≡ 1 mod N2

(1,2)

Output: SIKID

In step 1 of the cross-domain extension algorithm, the common shared public param-

eters are the element-wise product of both sets of domain parameters. In step 2, entity

EIDA extends its identity key using the Chinese-Remainder Theorem. In step 3, entity

EIDA extends its hash identi¬er also using the Chinese-Remainder Theorem.

The procedure for entity EIDB is analog, only the indices change from A to B. Key