METHOD OF MANAGING IMPLICIT CERTIFICATES USING A DISTRIBUTED PUBLIC KEYS INFRASTRUCTURE

Abstract

A method of managing implicit certificates of an elliptical curve encryption (ECQV). The implicit certificates are stored in different nodes of the network as a function of a distributed hash table (DHT) and not with a single certification authority. The implicit certificate of the public key associated with a node is obtained by chaining elementary certification operations with a sequence of indexing nodes of the network. Chaining of elementary certification operations can reinforce authentication of network nodes.

Claims

1. A method of managing implicit certificates of public keys for a communication network, the public keys being related to an elliptic curve cryptosystem, each implicit certificate being unable to identify a public key of a node on the network and each node being identified by an identifier, wherein: a first implicit certificate (γ.sub.A.sub.0) of a node A is calculated by and is stored in a first indexing node (B.sub.0), the first indexing node being determined by a distributed hash table, starting from an identifier condensate obtained by hashing a first value containing the node identifier A; a first public key (Q.sub.A.sub.0) of node A is calculated from the first implicit certificate and the public key of the first indexing node (Q.sub.B.sub.0); a second implicit certificate (γ.sub.A.sub.I) of node A is calculated by a second indexing node (B.sub.I), the second indexing node being determined by said distributed hash table from a first certificate condensate (e.sub.A.sub.0) obtained by hashing a second value containing the first implicit certificate and the node identifier A, said second implicit certificate being transmitted to the first indexing node to be stored in it; a second public key (Q.sub.A.sub.I) of node A is calculated from the first public key (Q.sub.A.sub.0) and the public key of the second indexing node (Q.sub.B.sub.I).

2. The method of managing implicit certificates according to claim 1, in which the identifier condensate is obtained by h(ID.sub.A∥keyword) where ID.sub.A is the identifier of node A, keyword is a known password of network nodes, ∥ is a concatenation operation and h is a hash function.

3. The method of managing implicit certificates according to claim 1, wherein: first public key of node A is calculated by Q.sub.A.sub.0=e.sub.A.sub.0γ.sub.A.sub.0+Q.sub.B.sub.0 in which γ.sub.A.sub.0 is the first implicit certificate, e.sub.A.sub.0 is the first certificate condensate and Q.sub.B.sub.0 is the public key of the first indexing node; the second public key of node A is calculated by Q.sub.A.sub.I=Q.sub.A.sub.0+e.sub.A.sub.Iγ.sub.A.sub.I+Q.sub.B.sub.I in which γ.sub.A.sub.I is the second implicit certificate of node A, e.sub.A.sub.I is a second certificate condensate obtained by hashing a second value, containing the second implicit certificate of node A, and Q.sub.B.sub.I is the public key of the second indexing node.

4. The method of managing implicit certificates according to claim 1, wherein a plurality of implicit certificates are generated for node A during a plurality of successive iterations, and in that at iteration i:1 an (i+1).sup.th indexing node (B.sub.I ) calculates a (i+1).sup.th implicit certificate (γ.sub.A.sub.I) for node A, the (i+1).sup.th indexing node being determined by the distributed hash table from a i.sup.th certificate condensate (e.sub.A.sub.I−1) obtained by hashing a (i+1).sup.th value containing the i.sup.th implicit certificate of node A obtained in the previous iteration, and the identifier of node A (ID.sub.A), said (i+1).sup.th implicit certificate of node A being transmitted to the first indexing node to be stored in it; an (i+1).sup.th public key (Q.sub.A.sub.I) of node A is calculated from the i.sup.th public key (Q.sub.A.sub.I−1) of node A, obtained in the previous iteration, and the pubic key of the (i+1).sup.th indexing node (Q.sub.B.sub.I).

5. The method of managing implicit certificates according to claim 4, wherein the (i+1).sup.th certificate condensate is obtained by e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A) or e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.I−1∥ID.sub.A) in which γ.sub.A.sub.I and γ.sub.A.sub.I−1 are the (i+1).sup.th and i.sup.th implicit certificates respectively, ID.sub.A is the node identifier A and ∥ is a concatenation operation and h is a hash function.

6. The method of managing implicit certificates according to claim 4, wherein the (i+1).sup.th certificate condensate is obtained by e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A∥D.sub.A.sub.I) or e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.I−1∥ID.sub.A∥D.sub.A.sub.I) in which γ.sub.A.sub.I and γ.sub.A.sub.I−1 are the (i+1).sup.th and i.sup.th implicit certificates, ID.sub.A is the node identifier A, D.sub.A.sub.I is a validity date associated with the (i+1).sup.th implicit certificate, ∥ is a concatenation operation and h is a hash function.

7. The method of managing implicit certificates according to claim 4, wherein the (i+1).sup.th public key of node A is calculated by Q.sub.A.sub.I=Q.sub.A.sub.I−1+e.sub.A.sub.Iγ.sub.A.sub.I+Q.sub.B.sub.I in which γ.sub.A.sub.I is the (i+1).sup.th implicit certificate of node A, e.sub.A.sub.I is the (i+1).sup.th certificate condensate and Q.sub.B.sub.I is the public key of the (i+1).sup.th indexing node.

8. The method of managing implicit certificates according to claim 4, wherein the interval between two successive iterations has a predetermined fixed duration.

9. The method of managing implicit certificates according to claim 4, wherein the (i+1).sup.th implicit certificate (γ.sub.A.sub.I) calculated in iteration i, is associated with a validity date (D.sub.A.sub.I) and in that the next iteration is made when said validity date has expired.

10. The method of managing implicit certificates according to claim 4, wherein the interval between successive iterations has a pseudo-random duration.

11. The method of managing implicit certificates according to claim 4, wherein, in iteration i, the first indexing node stores a list of implicit certificates γ.sub.A.sub.j, j=0, . . . , i obtained during successive iterations, in relation to the identifier condensate.

12. The method of managing implicit certificates according to claim 11, wherein, in iteration i, the first indexing node stores a list of validity dates D.sub.A.sub.j, j=0, . . . , i of said implicit certificates and/or a list of trust and reputation ratios T & R.sub.j, j=0, . . . , i in relation, to the identifier condensate, in which T & R.sub.j is the trust and reputation ratio of the (j+1).sup.th indexing node.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0036] Other characteristics and advantages of the invention will become clear after reading a preferred embodiment of the invention with reference to the appended figures among which:

[0037] FIG. 1 represents an example distribution of the storage of implicit certificates in different nodes according to a distributed hash table;

[0038] FIG. 2 diagrammatically represents a flowchart of the method of managing public key implicit certificates according to a first embodiment of the invention;

[0039] FIG. 3 diagrammatically represents a flowchart of the method of managing public key implicit certificates according to a second embodiment of the invention;

DETAILED PRESENTATION OF PARTICULAR EMBODIMENTS

[0040] In the following, we will consider a plurality of network nodes, for example a 6LoWPAN network in the domain of the Internet of Things connected to the Internet IP through a gateway. However, the man skilled in the art will understand that the invention can be applied to any type of network.

[0041] A first concept on which the invention is based is to not store implicit certificates in a single node, for example on a dedicated server, but rather to store them distributed in a plurality of nodes by means of a Distributed Hash Table (DHT).

[0042] It should be remembered that a DHT can be used to find the address of a node (of the addresses of several nodes) on which the information (also called value in the context of a DHT) associated with this key is stored. An introduction to DHT techniques is given in the paper by S. Sarmady entitled “A Survey on Peer-to-Peer and DHT”, arXiv preprint arXiv:1006.4708, 2010.

[0043] The storage of implicit certificates using the Chord protocol will be described below. However, an expert in the subject will understand that other DHT storage protocols could be used alternatively without going outside the scope of protection of the invention.

[0044] As mentioned above, the implicit certificates are generated using a hash function h (for example SHA hashing). If the number of condensate bits is denoted m, the values of function h lie within the interval [0,2.sup.m−1]. This interval can be looped back on itself (the value 2.sup.m then coinciding with the value 0) and represented in the form of a circle as illustrated in FIG. 1.

[0045] According to a first example embodiment, the interval [0,2.sup.m−1] is divided into a plurality of consecutive segments (ring portions in FIG. 1), a representative node being associated with each segment, in other words a node in the network such that its hash value (condensate) is included in the segment concerned. In other words, a node B.sub.I∈{B.sub.0, . . . , B.sub.N} is associated with a segment [a,b[⊂[0,2.sup.m−1] such that h(B.sub.I)∈[a,b[. It is then said that the node A.sub.I manages the segment [a,b[ or the points in this segment.

[0046] Preferably, according to a second example embodiment, the interval [0,2.sup.m−1] is covered by a plurality of segments, these segments possibly overlapping with a degree of overlap, K, in other words said point in this interval belongs to at least K distinct segments.

[0047] The nodes associated with the different segments are called indexing nodes and contain a copy of the DHT table. For each segment, the DHT table gives the indexing node that will manage implicit certificates belonging to the segment.

[0048] Thus, in order to recover the implicit certificate of a public key belonging to a node characterised by its identifier ID, for example its IPv6 address, the hash value h(ID)) is calculated and the DHT table is searched for an indexing node A.sub.I responsible for managing a segment containing h(ID)). The implicit certificate can be retrieved from this indexing node.

[0049] The indexing nodes could possibly be organised hierarchically, a coarse indexing level being made by first level indexing nodes pointing to indexing nodes on a second level responsible for finer indexing (in other words a finer segmentation). In the domain of the Internet of Things, the root indexing node can be the gateway between the 6LoWPAN network and Internet.

[0050] In any case, it will be understood that the second example embodiment has the advantage of providing storage redundancy due to overlapping of segments. Thus, if one of said indexing nodes responsible for the relevant segment leaves the network or stops functioning, the implicit certificate can alternatively be retrieved from the K−1 other nodes.

[0051] If required, each segment can be managed by several indexing nodes, a priority level then being assigned to each indexing node. Thus, the first step could be to address a first high priority indexing node managing the segment that contains h(Id) and, if this first indexing node is overloaded, a second lower priority indexing node managing the same segment.

[0052] Storage and management of implicit certificates are thus distributed to a plurality of network nodes. These nodes are advantageously chosen from among nodes that have the highest memory capacity.

[0053] To prevent an indexing node from being able to allocate a segment of the DHT to itself, a password keyword known to all nodes in the network can advantageously be added to the node identifier, ID, before the hash function is applied to it. More precisely, for a given segment [a,b[, the indexing node of this segment (consequently managing implicit certificates falling in this segment) will then be chosen from among nodes B.sub.I such that h(ID.sub.B.sub.I∥keyword)∈[a,b[.

[0054] A second concept on which this invention is based is to chain implicit certificates to reinforce the security of certificates and authentication of the public keys contained in them.

[0055] FIG. 2 diagrammatically represents a method or managing implicit certificates according to a first embodiment of the invention;

[0056] It is assumed that a node A (Alice) would like to obtain an implicit certificate for a public key using an elliptical curve cryptosystem ECC. The Elliptic Curve Cryptography ECC cryptosystem is defined by a set of given domain parameters, in other words constants involved in the elliptical equation defined on Z.sub.p (in which p is prime), the generating point G and the order n of the cyclic group generated by the generating point.

[0057] In step 210, node A calculates the hash value h(ID.sub.A), in which ID.sub.A is a identifier of node A. This is why the value h(Id.sub.A) will be called the identifier condensate. Node A uses the DHT table to determine an indexing node responsible for management of a segment containing h(ID.sub.A). Optionally, a password can be concatenated with the identifier before hashing in all cases, this indexing node is denoted B.sub.0.

[0058] In step 220, node A generates an integer α.sub.0 and sends α.sub.0G to node B.sub.0. In practice, only coordinate x.sub.0 of α.sub.0G can be transmitted, since node B.sub.0 knows the domain parameters.

[0059] Node B.sub.0 has a private key b.sub.0 and a corresponding public key Q.sub.B.sub.0=b.sub.0G.

[0060] In step 230, node B.sub.0 calculates private key and public key reconstruction data as follows:

[0061] Node B.sub.0 generates an integer k.sub.0 within the interval [1,n−1] and calculates public key reconstruction data γ.sub.0 using:

γ.sub.0=α.sub.0G+k.sub.0G  (4-1)

[0062] This public key reconstruction data forms the first implicit certificate (of the public key) for node A.

[0063] The indexing node B.sub.0 then calculates the condensate e.sub.A.sub.0=h(γ.sub.A.sub.0∥ID.sub.A) or the condensate e.sub.A.sub.0=h(γ.sub.A.sub.0∥ID.sub.A∥D.sub.A.sub.0) in which D.sub.A.sub.0 is the validity date of the implicit certificate for the node A and ∥ designates the concatenation operation as above. In any case, the condensate e.sub.A.sub.0, called the first certificate condensate is obtained by hashing information containing the first implicit certificate γ.sub.A.sub.0 and the node identifier A. Regardless of the form selected for the condensate, node B.sub.0 uses it to determine private key reconstruction data:

s.sub.A.sub.0=e.sub.A.sub.0k.sub.A.sub.0+b.sub.0 mod.n  (4-2)

[0064] In step 240, the indexing node B.sub.0 sends the pair (s.sub.A.sub.0, γ.sub.A.sub.0) composed of the private key reconstruction data and the public key reconstruction data to node A. Furthermore, B.sub.0 stores the implicit certificate γ.sub.A.sub.0 and possibly the validity date D.sub.A.sub.0 of this certificate, related to the identifier condensate h(ID.sub.A), in its local memory.

[0065] In step 250, node A builds a first private key and a first pubic key using private key and public key reconstruction data respectively, as follows:

a.sub.A.sub.0=e.sub.A.sub.0α.sub.0+s.sub.A.sub.0 mod.n  (5-1)

Q.sub.A.sub.0=e.sub.A.sub.0γ.sub.A.sub.0+Q.sub.B.sub.0  (5-2)

[0066] In step 255, an indexing node B.sub.I is generated managing the first implicit certificate in the DHT. More precisely, the node B.sub.I is a DHT indexing node for a segment containing the first certificate condensate, namely e.sub.A.sub.0=h(γ.sub.A.sub.0∥ID.sub.A) or one of the variants mentioned above.

[0067] In step 260, node generates an integer α.sub.I and sends α.sub.IG to node B.sub.I. Node B.sub.I has a private key b.sub.I and a corresponding public key Q.sub.B.sub.I=b.sub.IG.

[0068] In step 270, node B.sub.I calculates private key and public key reconstruction data: More precisely, node B.sub.I generates an integer k.sub.B.sub.I within the [1,n−1] interval and calculates public key reconstruction data γ.sub.A.sub.I using:

γ.sub.A.sub.I=α.sub.IG+k.sub.B.sub.IG  (6-1)

[0069] This public key reconstruction data forms the second implicit certificate for node A.

[0070] The indexing node B.sub.I then calculates a second certificate condensate defined by e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A) or e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A∥D.sub.A.sub.I) or, by consolidating certificates e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.0∥ID.sub.A) or e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.0∥ID.sub.A∥D.sub.A.sub.I) in which D.sub.I is the validity date of the implicit certificate of node B.sub.I.

[0071] The indexing node B.sub.I determines private key reconstruction data from the second condensate:

s.sub.A.sub.I=e.sub.A.sub.Ik.sub.B.sub.I+b.sub.I mod.n  (6-2)

[0072] In step 280, the indexing node B.sub.I sends the pair (s.sub.A.sub.I, γ.sub.A.sub.I) composed of the private key s.sub.A.sub.I reconstruction data and the second implicit certificate, to the indexing node A.

[0073] Furthermore, node B.sub.I transmits the second implicit certificate γ.sub.A.sub.I possibly the validity date D.sub.A.sub.I of this certificate to node B.sub.0. Node B.sub.0 stores the second implicit certificate and possibly the validity date D.sub.A.sub.I, related to the identifier condensate h(Id.sub.A), in its local memory.

[0074] It is thus understood that the first and second implicit certificates γ.sub.A.sub.0, γ.sub.A.sub.I and possibly their corresponding validity dates D.sub.A.sub.0, D.sub.A.sub.I, are stored, in relation to h(Id.sub.A).

[0075] In step 290, node A constructs a second private key from the private key reconstruction data s.sub.A.sub.I and its first private key, a.sub.A.sub.0, namely:

a.sub.A.sub.I=a.sub.A.sub.0+e.sub.A.sub.Iα.sub.I+s.sub.A.sub.I mod.n  (7-1)

[0076] Similarly, node A constructs a second public key from the public key reconstruction data γ.sub.A.sub.I and its first public key, Q.sub.A.sub.0:

Q.sub.A.sub.I=Q.sub.A.sub.0+e.sub.A.sub.Iγ.sub.A.sub.I+Q.sub.B.sub.I  (7-2)

[0077] It can be shown that relation Q.sub.A.sub.I=a.sub.A.sub.IG is actually satisfied.

[0078] FIG. 3 diagrammatically represents a method of managing implicit certificates according to a second embodiment of this invention;

[0079] We will assume that the elliptical curve cryptosystem is the same as in the first embodiment. Node A once again would like to obtain an implicit certificate for a public key related to this cryptosystem.

[0080] Generation of the implicit certificate and the keys for node A is initialised by steps 310 to 350. Steps 310 to 350 are identical to steps 210 to 250 respectively and therefore they will not be described again herein.

[0081] Some time after the initialisation phase that can correspond to the validity duration of the implicit certificate, or to the expiration of a repetition period, or a duration obtained by a pseudo-random drawer, the implicit certificate is enriched by a recurrence chaining process related to steps 360 to 390. In general, the interval between two successive iterations can be fixed or it can depend on the validity duration of the certificate or it may be pseudo-random.

[0082] We will now assume that the (i−1).sup.th iteration has already been done and we will consider the i.sup.th iteration.

[0083] In step 355, node A searches for node B.sub.I that manages the condensate e.sub.A.sub.I−1 in the DHT, in other words B.sub.I is an indexing node for a segment that contains e.sub.A.sub.I−1.

[0084] In step 360, node A generates and integer α.sub.I and sends α.sub.IG to node B.sub.I.

[0085] Node B.sub.I has a private key b.sub.I and a corresponding public key Q.sub.B.sub.I=b.sub.IG.

[0086] In step 370, node B.sub.I calculates private key and pubic key reconstruction data as follows:

[0087] Node B.sub.I generates an integer k.sub.B.sub.I within the interval [1,n−1] and calculates pubic key reconstruction data γ.sub.A.sub.I using:

γ.sub.A.sub.I=α.sub.IG+k.sub.B.sub.IG  (8-1)

[0088] The indexing node B.sub.I calculates the condensate e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A) or e.sub.A.sub.I=h(γ.sub.A.sub.I∥ID.sub.A∥D.sub.A.sub.I) or, by consolidating successive implicit certificates, e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.I−1∥ID.sub.A) or even the condensate e.sub.A.sub.I=h(γ.sub.A.sub.I∥γ.sub.A.sub.I−1∥ID.sub.A∥D.sub.A.sub.I) in which D.sub.A is the validity date of the implicit certificate of node B.sub.I. If required, a trust and reputation ratio (also called the T&R ratio) of node B.sub.I can be added to the operand of the hash function. The T&R ratio is an estimate of the trust and reputation of the node produced from the other nodes in the network. The T&R concept is well established in the domain of P2P (Peer to Peer) communications. In particular, a description of it is given in the paper by A. Medic, entitled “Survey of Computer Trust and Reputation Models—The Literature Overview” published in Int. J. Inf, 2012, vol. 2, no 3. Including the T&R ratio in the operand of the hash function allows other nodes to have more trust in the link between the identifier and the implicit certificate.

[0089] Regardless of the form selected far the condensate, node B.sub.I uses it to determine private key reconstruction data for iteration i:

s.sub.A.sub.I=e.sub.A.sub.Ik.sub.B.sub.I+b.sub.I mod.n  (8-2)

[0090] In step 380, the indexing node B.sub.I sends the pair (s.sub.A.sub.I, γ.sub.A.sub.I) composed of the private key reconstruction data and the public key reconstruction data for iteration i to node A.

[0091] Furthermore, node B.sub.I transmits the implicit certificate γ.sub.AI and possibly the validity date D.sub.A.sub.I of this certificate to node B.sub.0. Node B.sub.0 stores the implicit certificate γ.sub.AI (and possibly D.sub.I and T & R.sub.I, related to the hash value h(ID.sub.A), in its local memory.

[0092] In step 390, node A constructs a new private key from the private key reconstruction data for the current iteration i and the private key for the previous iteration, i−1, by:

a.sub.A.sub.I=a.sub.A.sub.I.sub.−1+e.sub.A.sub.Iα.sub.I+s.sub.A.sub.I mod.n  (9-1)

[0093] Similarly, node A constructs a new public key from the public key reconstruction data for iteration i and the public key for iteration i−1:

Q.sub.A.sub.I=Q.sub.A.sub.I−1+e.sub.A.sub.Iγ.sub.A.sub.I+Q.sub.B.sub.I  (9-2)

[0094] It can be demonstrated by recurrence that Q.sub.A.sub.I=a.sub.A.sub.IG. The property is satisfied for i=0 and if Q.sub.A.sub.I−1=a.sub.A.sub.I−1G since by virtue of (9-2) and (8-1) we have:

Q.sub.A.sub.I=a.sub.A.sub.I−1G+e.sub.A.sub.I(α.sub.IG+k.sub.B.sub.IG)+b.sub.IG=(a.sub.A.sub.I−1+e.sub.A.sub.Iα.sub.I+e.sub.A.sub.Iα.sub.I+b.sub.I)G  (10)

and according to (9-1) and (8-2): a.sub.A.sub.I=a.sub.A.sub.I.sub.−1+e.sub.A.sub.Iα.sub.I+s.sub.A.sub.I=a.sub.A.sub.I.sub.−1+e.sub.A.sub.Iα.sub.I+e.sub.A.sub.Ik.sub.B.sub.I+b.sub.I.

[0095] It will be noted for a current iteration i, node B.sub.0 that manages h(ID.sub.A) in the DHT, stores the list of implicit certificates γ.sub.A.sub.j, j=0, . . . , i, and possibly the list of validity dates D.sub.A.sub.j and/or the trust and reputation ratios T & R.sub.j, j=0, . . . , i, in its memory in relation to h(ID.sub.A). Node A can simply store its last private key a.sub.A.sub.I and its last two implicit certificates γ.sub.A.sub.I, γ.sub.A.sub.I−1, or possibly its last implicit certificate γ.sub.A.sub.I alone, in its memory.

[0096] The last implicit certificate of node A, γ.sub.A.sub.I, is sufficient to update the public key by means of (9-2) provided that the public key of node Q.sub.B.sub.I is known. Thus, a node C (Bob) that would like to initiate a secure communication with node A can retrieve the last implicit certificate of node A, γ.sub.A.sub.I from node B.sub.0, managing h(ID.sub.A), and can deduce its current public key Q.sub.A.sub.I from it. Conversely, node A must contact the indexing node, D.sub.0, managing h(ID.sub.c) in the DHT to retrieve the last implicit certificate of node C and use it to deduce its current public key Q.sub.C.sub.I. Nodes A and C can then communicate with each other in a secure manner.

[0097] Under these conditions, it will be understood that if a “man in the middle” type attack is to be successful, it would have to operate between node A and its indexer, B.sub.0, between C and its indexer D.sub.0 and between A and C simultaneously, which is very difficult unless the entire network is controlled. Furthermore, each node A and C can check that the public key of the other is coherent by checking if the chaining of implicit certificates is valid. Thus, node C will be able to check that the public key Q.sub.A.sub.I is coherent with node A by checking with B.sub.0 that is was actually obtained using relation (7-2) from implicit certificates γ.sub.A.sub.I, γ.sub.A.sub.I−1, . . . , γ.sub.A.sub.0.

[0098] Therefore according to this invention, the certificates are not stored with a single certification authority but instead with indexing nodes participating in the DHT.

[0099] Distributed storage of implicit certificates and chaining of these certificates to obtain pubic and private keys of nodes make the network particularly resistant to “man in the middle” type attacks.