Device and method for generating a session key

Abstract

A device and method are provided for establishing a session key between two entities of a communication network that may be highly heterogeneous in terms of resources. The method, based on the Diffie-Hellman (DH) algorithm, provides for the delegation to assistant nodes of the network of the cryptographic operations required for the computations of the DH public value and of the DH session key for the node which is constrained in terms of resources.

Claims

1. In a communication network comprising a plurality of communicating entities, a method for establishing a session key according to the Diffie-Hellman protocol between a source entity with a source private value ‘a’ and a target entity with a target private value ‘b’ and a target public value ‘g.sup.b mod p’, the method comprising the steps of: selection of ‘n’ assistant entities among the plurality of communicating entities; decomposition of the source private value ‘a’ into ‘n’ fragments; enciphering of each fragment ‘n’ of the source private value; transmission to each assistant entity of an enciphered fragment among the ‘n’ enciphered fragments of the source private value, each assistant entity receiving a different enciphered fragment; computation by each assistant entity of a fragment of source public value with the received enciphered fragment of the source private value; transmission of the computed fragment of source public value to the target entity by each assistant entity; computation by the target entity of the source public value with the received fragments of source public value; transmission to the ‘n’ assistant entities of a fragment of the target public value; computation by each assistant entity with the enciphered fragment of the source private value, of an exponentiation of the received target public value; and transmission of each exponentiation to the source entity.

2. The method as claimed in claim 1, wherein the step of decomposition of the source private value ‘a’ consists in generating ‘n’ values ‘a.sub.i’ such that a =Σ.sub.1.sup.na.sub.i.

3. The method as claimed in claim 1, wherein the step of decomposition of the source private value ‘a’ consists in generating ‘n’ values ‘f(i)’ of a polynomial f(x).

4. The method as claimed in claim 3, wherein the step of enciphering consists in a security association based on a key between the source entity and each assistant entity.

5. The method as claimed in claim 4, wherein the step of computing the source public value by the target entity is done on receiving the ‘n’ fragments of source public values.

6. The method as claimed in claim 1, wherein the step of computing the source public value by the target entity is done on receiving a number ‘k’ of fragments of source public values, ‘k’ being less than ‘n’.

7. The method as claimed in claim 6, wherein the computation of the source public value is made by a Lagrange polynomial interpretation.

8. The method as claimed in claim 7, also comprising the steps of: enciphering the exponentiations; and transmitting each enciphered exponentiation to the source entity.

9. The method as claimed in claim 8, comprising after the step of transmission of each exponentiation, the step of computing the Diffie-Hellman session key.

10. The method as claimed in claim 9, wherein the ‘n’ selected entities are less constrained in terms of resources than the source entity.

11. The method as claimed in claim 10, wherein the fragment of the target public value transmitted to all the assistant entities is the target public value ‘g.sup.b mod p’.

12. In a communication network comprising a plurality of communicating entities, a system for establishing a session key according to a Diffie-Hellman protocol between a source entity and a target entity, the system comprising: means for selection of ‘n’ assistant entities among the plurality of communicating entities: means for decomposition of the source private value ‘a’ into ‘n’ fragments; means for enciphering of each fragment ‘n’ of the source private value; means for transmission to each assistant entity of an enciphered fragment among the ‘n’ enciphered fragments of the source private value, each assistant entity receiving a different enciphered fragment; means for computation by each assistant entity of a fragment of source public value with the received enciphered fragment of the source private value; means for transmission of the computed fragment of source public value to the target entity by each assistant entity; computation by the target entity of the source public value with the received fragments of source public value; means for transmission to the ‘n’ assistant entities of a fragment of the target public value; means for computation by each assistant entity with the enciphered fragment of the source private value, of an exponentiation of the received target public value; and means for transmission of each exponentiation to the source entity.

13. A computer program product, said computer program comprising processor readable non-transitory media code instructions making it possible to carry out the steps of the method as claimed in claim 10, when said program is executed on a computer.

14. The system as claimed in claim 12, wherein the computing the source public value by the target entity is done on receiving a number ‘k’ of fragments of source public values, ‘k’ being less than ‘n’.

15. The system as claimed in claim 14, wherein the computation of the source public value is made by a Lagrange polynomial interpretation.

16. The system as claimed in claim 15, further comprising: means for enciphering the exponentiations; and means for transmitting each enciphered exponentiation to the source entity.

17. The system as claimed in claim 16, further comprising means for computing the Diffie-Hellman session key after transmission of each exponentiation.

18. The system as claimed in claim 17, wherein the ‘n’ selected entities are less constrained in terms of resources than the source entity.

Description

DESCRIPTION OF THE FIGURES

(1) Various aspects and advantages of the invention will appear, supported by the description of a preferred but non-limiting mode of implementation of the invention, with reference to the figures hereinbelow:

(2) FIG. 1 is a topological representation of a network infrastructure wherein the invention may be advantageously implemented;

(3) FIG. 2 shows the steps taken by a source entity to decompose a private value into fragments of secret values;

(4) FIG. 3 shows the steps taken by a source entity to compute a session key;

(5) FIG. 4 shows the steps taken by a target entity to compute a public value of the source entity;

(6) FIG. 5 shows the steps taken by a proxy to compute a fragment of public value;

(7) FIG. 6 shows the steps taken by a proxy to compute a segment of a session key;

(8) FIG. 7 shows the exchanges performed between a source node and a target node to establish a session key in a first variant implementation of the invention;

(9) FIG. 8 shows the exchanges performed between a source node and a target node to establish a session key in a second variant implementation of the invention.

DETAILED DESCRIPTION OF THE INVENTION

(10) The present invention describes a session key exchange, based on the Diffie-Hellman protocol, between two entities that are heterogeneous in terms of resources. The solution employs distributed collaborative techniques using assistant nodes or proxies.

(11) FIG. 1 illustrates a network environment (100) wherein the invention is advantageously implemented. For reasons of ease of description and not of limitation of the invention, the example in FIG. 1 shows only a finite number of entities and connections, but those skilled in the art will be able to extend the principles described to a plurality and a variety of entities and connection types (wireless, mobile, very high speed).

(12) The network (100) comprises a set of fixed or mobile entities forming a network of nodes (102). The network of nodes comprises nodes with heavy resource constraints (102-1, 102-n) and nodes with lesser resource constraints (112-1, 112-m).

(13) The nodes with heavy resource constraints can be wireless actuators or sensors, with limited computation and/or storage capabilities. These can also be active tags. However, a node that is not intrinsically limited in resources can become so temporarily as soon as it uses a large part of its processor resources for another task, or as soon as its battery level reaches a critical threshold value. And this node can be compelled to implement less energy-expensive protocols, such as that of the invention.

(14) The nodes with lesser constraints in terms of resources can be portable phones equipped with an Internet connection and a camera. They can also be interconnection gateways between a network of constrained entities and the Internet. These entities offer greater computational power and storage capacity, can possess a larger energy reserve (battery, mains power) and can communicate over a network, either directly to an Internet network (104) as illustrated or else via intermediate gateways and servers (not shown).

(15) The network of nodes (102) can be based on level 2 communications (for example, 802.15.4 or 802.11) or level 3 communications (for example, IP) between the nodes forming it. According to the protocols on which it is based, multicast or broadcast communication schemes may be used therein.

(16) The network (100) also comprises remote entities (106) not having any resource constraints, by comparison with those of the network of nodes (102).

(17) The remote entities can be servers (for example, server for the storage and/or management of information uploaded by one or more sensors or an actuator control server) having large storage capacities and computational power or any other entity having unconstrained computational, storage and energy capacities.

(18) Such a network (100) forms what is known as an Internet of Things (IoT). It covers two types of communication: Thing-to-person types; Thing-to-thing, or machine-to-machine (M2M) types.

(19) These communications can be established in a limited context (use of a single protocol, for example ZigBee and/or a single target scenario, for example the Smart Grid) in which case the term “Intranet of Things” is used, or can be designed to make possible a large number of separate services, while being based on many communications protocols, in which case the term “Internet of Things” is used. Generally, the term Internet of Things refers to an architecture that allows the interconnection of the conventional Internet with communicating or perceived things, and which is based on decentralized communication schemes, while employing autonomous mechanisms.

(20) The present invention can be advantageously applied in the environment in FIG. 1 between a node which is highly constrained in terms of resources (102-1) that is named interchangeably source or sender entity in the present description, and a powerful remote server (106) that is named target or receiver entity. The two entities need to establish a session key.

(21) FIG. 2 shows the procedures executed by a source entity to decompose a source private value into a set of secret values to be addressed to assistant entities.

(22) In a first step 202, the source entity randomly generates a source private value ‘a’ according to the principle of the Diffie-Hellman protocol, where this value corresponds to the secret exponent that is used to deduce the Diffie-Hellman public value.

(23) The source private value is decomposed in the next step 204 into a plurality ‘n’ of secret values ‘a.sub.i’. In this phase, the source entity generates a set of values ‘a.sub.i’, the possession of all or a certain number of which makes it possible to reconstitute its secret exponent ‘a’.

(24) The number of fragments ‘n’ corresponds to the number of assistant entities or proxies that are selected to support the key exchange between the source and target entities.

(25) The selection of the proxies can be based on the reputations of the entities present in the neighborhood of the source entity and/or their available resources such as for example their computational power or their battery level. In the case where the selection is based on the reputations of the nodes in the neighborhood, they can be evaluated locally or by a central server according to their past attitudes. A metric, the reputation, is then defined which accounts for the types and proportions of attitudes, positive (for example, offering a service) and negative (for example, refusing to offer a service) that a node has manifested in the past. In a variant, the source entity can keep a predefined list of usable proxies, and the selection of the proxies to be used for the session is made from this list.

(26) In the following step 206, each secret value a.sub.i is assigned and transmitted to a proxy P.sub.i among the ‘n’ selected proxies.

(27) FIG. 3 shows the steps taken by a source entity to compute a final session key. In a step 302, the source entity receives an encrypted value from each of the ‘n’ proxies. Each value corresponds to the result of an exponentiation carried out by each proxy respectively. In the step 304 the source entity computes the value of the final DH key on receiving all the encrypted values.

(28) FIG. 4 shows the steps taken by a target entity to compute a public value of the source entity. In the step 402, the target entity receives from ‘n’ proxies a set of ‘n’ public values. Each value corresponds to the computation of a public value carried out respectively by each proxy on the basis of the fragment of secret value received from the source entity. According to the variant implementations that are described below, with reference to FIGS. 7 and 8, on reception either of all the public values or of a finite number of them, the target entity computes in the step 404 the public value g.sup.a mod p of the source entity. In the following step 406, the target entity transmits to the ‘n’ proxies a public value that is, in the variant implementation of FIG. 7 or 8, either its own public value g.sup.b mod p for the variant in FIG. 7 or a fragment of its public value as will be detailed below with reference to FIG. 8.

(29) FIG. 5 shows the steps taken by an assistant entity to compute a public value corresponding to the fragment of the secret value received from the source entity. In the step 502, a proxy P.sub.i receives from the source entity a secret value resulting from the decomposition of the initial private value ‘a’. In the following step 504, the proxy P.sub.i computes the public value for the fragment of the received secret value, generating a fragment of public value. The fragment of public value is transmitted to the target entity in the step 506.

(30) FIG. 6 shows the steps taken by an assistant entity to compute a segment of a DH session key. In an initial step (not shown), the target entity randomly generates a target private value ‘b’ according to the principle of the Diffie-Hellman protocol, where this value corresponds to the secret exponent that is used to deduce its Diffie-Hellman public value. In the step 602, a proxy P.sub.i receives a public value computed by the target entity from its own public value g.sup.b mod p as described with reference to FIG. 4. In the following step 604, the proxy computes a final session key segment from the fragment of the secret value previously received by the source entity (step 206) and the public value received from the target entity. Then in the step 606, the proxy sends the generated session key segment to the source entity.

(31) FIGS. 7 and 8 show the exchanges performed between a source entity (or node ‘A’) and a target entity (or node ‘B’) to establish a session key in two variant implementations of the invention.

(32) In a phase not shown in the figure, the node A selects assistant nodes P.sub.i with fewer resource constraints than itself to participate in the exchange.

(33) In a first phase (701, 801) the node B generates a random number ‘b’ as secret exponent to compute its DH public value, from the two parameters ‘g’ and ‘p’ on which the source and target entities have agreed.

(34) Then, in the next phase (702, 802) the node A generates a random number ‘a’ as DH secret exponent.

(35) In the example described, it is supposed that the source is low in resources and that the cryptographic operations required for the computations of its DH public value and its DH session key are delegated to the assistant nodes Proxies (P.sub.1, . . . , P.sub.n).

(36) Note that the secret exponent ‘a’ must be kept private at the node A and cannot be decrypted again in the node B or in the proxies.

(37) In a first variant (FIG. 7), the node A generates a set of ‘n’ values from the secret exponent ‘a’. Advantageously, the node A decomposes its secret exponent ‘a’ into n fragments (a.sub.1, . . . , a.sub.n), n being the number of proxies selected to support the exchange, and such that a=Σ.sub.1.sup.na.sub.i.

(38) The node A then securely provides (704) to each proxy P.sub.i the fragment that is assigned to it, using a security association based on a symmetrical key k.sub.A-Pi between A and P.sub.i.

(39) A second variant (FIG. 8) is based on the Lagrange polynomial interpolation technique. Considering k points in a 2-dimensional plane (x.sub.i,y.sub.i), . . . , (x.sub.k,y.sub.k) (with the x.sub.i pair-wise distinct), a unique polynomial f(x) of degree k−1 exists satisfying f(x.sub.i)=y.sub.i for all values of i. The polynomial f is derived using the following Lagrange formula:

(40) $f\left(x\right)=\underset{i=1}{\overset{k}{.Math.}}\left(f\left(i\right)\times \underset{j\ne i}{\overset{k}{.Math.}}\frac{x-j}{i-j}\right)$

(41) Given this interpolation technique, the node A generates a polynomial f(x) of degree k−1 in the form of f(x)=q.sub.0+q.sub.1x+ . . . +q.sub.k-1x.sub.k-1 with q.sub.1, q.sub.2, . . . , q.sub.k-1 being random coefficients and a=q.sub.0.

(42) From k values of the polynomial f(x), it is possible to find its coefficients and evaluate the secret exponent a=f(0) as follows:

(43) $a=f\left(0\right)=\underset{i=1}{\overset{k}{.Math.}}\left(f\left(i\right)\times \underset{j\ne i}{\overset{k}{.Math.}}\frac{-j}{i-j}\right)$

(44) The node A computes n values f(1), . . . , f(n) of the polynomial f(x) then securely provides (804) the value f(i) to each proxy P.sub.i with i=1, 2, . . . , n. The knowledge of k values among the n values transmitted to the proxies makes it possible to reconstitute the secret exponent a.

(45) On receiving the secret values from the node A, the proxies carry out an initial computation of the public key of the node A.

(46) In the first variant of the invention, the proxy P.sub.i receives the secret value a.sub.i transmitted by the node A and computes (706) the corresponding public value g.sup.a.sup.i mod p.

(47) In the second variant of the invention, the proxy P.sub.i receives the secret value f(i) from the node A and computes (806) the corresponding public value g.sup.f(i) mod p.

(48) The proxy P.sub.i then delivers (708, 808) this computed public value to the node B.

(49) On receiving the public values from the proxies, the node B reconstitutes the source public key of the node A which is used to establish the final session key.

(50) It can be appreciated that advantageously, this computation of the source public key is carried out without the secret exponent a of the node A being disclosed to the node B.

(51) In the first variant of the invention, the node B receives (708) the values g.sup.a.sup.i mod p from the node A. The reconstitution of the public key of the node A is carried out using the following computation (710):

(52) $\underset{i=1}{\overset{n}{.Math.}}{g}^{a_i}\mathrm{mod}p=g^{\underset{i=1}{\overset{n}{.Math.}}{a}_i}\mathrm{mod}p=g^a\mathrm{mod}p$

(53) Those skilled in the art will appreciate that the security of the secret ‘a’ lies in the difficulty of the problem of the discrete logarithm. The node B cannot deduce the a values from the information items g.sup.ai mod p, g and p alone.

(54) In the second variant of the invention, the node B receives (808) the values g.sup.f(i) mod p from the node A. The reconstitution of the public key is carried out on receiving a sub-set of k values among the n public values transmitted by the proxies to B.

(55) On receiving these k values g.sup.f(i)mod p transmitted by the proxies, the node B computes (810) the coefficients c.sub.i according to the equation:

(56) $c_i=\underset{j\epsilon P,j\ne i}{\overset{}{.Math.}}\frac{-j}{i-j}$

(57) Then the node B computes (810) the public key of the node A based on the following Lagrange formula:

(58) $\underset{i\epsilon P}{\overset{}{.Math.}}{\left(g^{f\left(i\right)}\right)}^{c_i}\mathrm{mod}p=g^{\underset{i\epsilon P}{\overset{}{.Math.}}f\left(i\right)\times c_i}\mathrm{mod}p=g^{f\left(0\right)}\mathrm{mod}p=g^a\mathrm{mod}p$

(59) Advantageously, the second variant of the invention makes it possible not to enforce the receiving of all the public values, thus protecting the solution from the unavailability or compromising of some of the assistant nodes.

(60) Subsequently, the node B transmits (712, 812) its target public key to the proxies.

(61) In the first variant of the invention, the node B sends (712) to all the proxies P.sub.i its public value g.sup.b mod p.

(62) In the second variant of the invention, the node B computes (810) for each P.sub.i (i∈P) the value g.sup.bc.sup.imod p with c.sub.i being the i.sup.th coefficient computed in the preceding phase and transmits (812) the result to each proxy P.sub.i.

(63) Advantageously, the invention allows for the second exponentiation required for the computation of the session key to be provided by the assistant nodes in a cooperative way.

(64) The selected assistant nodes bear the necessary computational burden to carry out an exponentiation without however being able to generate the final key.

(65) In the first variant, when receiving, each proxy uses the secret a.sub.i initially given by A and the target public value of B to compute (714) g.sup.ba.sup.i mod p=(g.sup.b mod p).sup.a.sup.i.

(66) In the second variant, when receiving, each proxy uses the value of the polynomial f(i) and the target public value received from B g.sup.bc.sup.imod p to compute (814) g.sup.bf(i)c.sup.i mod p=(g.sup.bcimod p).sup.f(i)mod p.

(67) In the two variants of the invention, these values computed by the proxies are then transmitted (716, 816) securely from each proxy to the node A in order to carry out the final computation of the DH session key (718, 720, 818, 820).

(68) This phase ends the key establishment system based on the DH protocol.

(69) At the node B the computing of the key is carried out as in the usual case of a Diffie-Hellman key exchange. The node B computes (720, 820) the session key by raising the public key of the node A to the power of its secret exponent b to obtain k.sub.DH=g.sup.ab mod p.

(70) At the node A the computation is carried out according to the variant implementation.

(71) In the first variant, on receiving all the g.sup.ba.sup.i mod p values from the proxies, the node A computes (718) the final key by multiplying these various values according to the equation:

(72) $\underset{i=1}{\overset{n}{.Math.}}{g}^{{\mathrm{ba}}_i}\mathrm{mod}p=g^{b\underset{i=1}{\overset{n}{.Math.}}\mathrm{ai}}\mathrm{mod}p=g^{\mathrm{ab}}\mathrm{mod}p$

(73) In the second variant, on receiving the g.sup.bf(i)c.sup.jmod p values from the k proxies, the node A computes (818) the final key by multiplying these various values according to the equation:

(74) $\underset{i\epsilon P}{\overset{}{.Math.}}{g^{\mathrm{bf}\left(i\right)}}^{c_i}\mathrm{mod}p=g^{b\underset{i\epsilon P}{\overset{}{.Math.}}f\left(i\right)c_i}\mathrm{mod}p=g^{\mathrm{bf}\left(0\right)}\mathrm{mod}p=g^{\mathrm{ab}}\mathrm{mod}p$

(75) By the end of these computing phases, the source and target entities have established a tunnel for secure communication on a DH session key.

(76) Those skilled in the art will appreciate that variations can be introduced to the preferred form of the method that has been described, while keeping to the principles of the invention.

(77) The present invention can be implemented based on hardware and/or software elements. It can be available as a computer program product on a computer-readable medium. The medium can be electronic, magnetic, optical, electro-magnetic or be an infra-red broadcasting medium. Such media are, for example, semiconductor memories (Random Access Memory RAM, Read-Only Memory ROM), tapes, magnetic or optical disks or diskettes (Compact Disc-Read Only Memory (CD-ROM), Compact Disc-Read/Write (CD-R/W) and DVD).

(78) The present description thus illustrates a preferred but non-limiting implementation of the invention. An example has been chosen to allow a good understanding of the principles of the invention, and a concrete application, but it is in no way exhaustive and should allow those skilled in the art to introduce modifications and variant implementations while preserving the same principles.