Method for distributing cryptographic keys in a communication network

• US 8,345,878 B2
• Filed: 08/27/2008
• Issued: 01/01/2013
• Est. Priority Date: 08/31/2007
• Status: Expired due to Fees

• Current Assignee: Thales SA
• Original Assignee: Thales SA
• Inventors: Grall, Eric
• Primary Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US12/675,667
• Publication Number:
  US 20110129090A1
• Time in Patent Office: 1,588 Days
• Field of Search: 380/278, 713/171
• US Class Current: 380/278
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/122 Counter-measures against attacks; Protection against rogue devices
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method for generating one or more cryptographic keys between users A and B, in which A generates a public value sensitive to a MIM attack and decomposes it into m segments of redundancy o, and transmits this concatenated information with a reference message N_a over the network via k routing paths and vice versa for B, A and B regenerate the common secret by recalculating the inverse transform of all the combinations of o segments and by choosing the value that is statistically most represented, g^ab˜ for A, and g^˜ab for B, A sends a verification message corresponding to N_b from B encrypted with g^ab˜ and sends it to the party B, B decrypts the message from A with g^˜ab and checks consistency with N_b, then refers to the acknowledgment message in the same way: {N_a} g^˜ab to validate the common secret between the two entities.

Claims

1. A method making it possible to distribute elements for generating one or more cryptographic keys between at least two users A and B in a network comprising a number of nodes Ni interlinked by means of communication highways, the network implementing a routing protocol, comprising at least the following steps:

to communicate with B, A generates a public value that is sensitive to a malicious attack in which a third party seeks to pass himself off as a participant in the network, or “

MIM”

, and decomposes it using a mathematical transformation into m segments of redundancy o, that is to say that an information item can be recomposed from o segments, and transmits this concatenated information with a reference message N_a over the network via k routing paths,

to communicate with A, B generates a public value that is sensitive to an MIM attack and decomposes it using the mathematical transformation into m segments of redundancy o, that is to say that an information item can be recomposed from o segments, and transmits this concatenated information with a reference message N_b over the network via k routing paths,

the two parties A and B regenerate the common secret by recalculating the inverse calculation of the mathematical transformation of all the combinations of o segments and by choosing the value that is statistically most represented;

g^ab˜

for A and g<sup>˜

ab</sup> for B,

once the two secrets assumed to be common have been calculated, g^ab˜

for A, and g<sup>˜

ab</sup> for B, the party A sends a verification message corresponding to the reference message N_b from B encrypted with the common secret;

g^ab˜

and sends it to the party B;

{N_b}g^ab˜

, B then decrypts the message from A with his key g<sup>˜

ab</sup> and checks consistency with his reference message N_b , then refers to the acknowledgment message in the same way;

{N_a}g<sup>˜

ab</sup> to validate the common secret between the two entities, and to use the common secret to encode a message,

wherein the step for regenerating the common secret comprises the following steps;

in the case of the party A, the following calculation applies;

g^ab˜

→

max(M<sup>−

1</sup>(g^yig^yi+1g^yi+2 . . . g^y+o),

with g^yi belonging to [g^bi ,g^fi], wherein [g^bi ,g^fi] are segments recovered by party A, with g^bi being unmodified segments belonging to the m segments transmitted by B, and with g^fi being segments modified from the m segments transmitted by B, wherein M<sup>−

1</sup>(g^yi g^yi+1 g^yi+2 . . . g^y+o) calculates values of the inverse calculation of the mathematical transformation of all the combinations of o segments from [g^bi ,g^fi], and wherein max( )chooses the statistically most represented value from the values calculated by M<sup>−

1</sup> (g^yi g^yi+1 g^yi+2 . . . g^y+o); and

in the case of the party B, the following calculation applies;

g<sup>˜

ab</sup>→

max(M<sup>−

1</sup>(g^yig^yi+1g^yi+2 . . . g^y+o),

with g^yi belonging to [g^ai ,g^hi], wherein [g^ai ,g^hi] are segments recovered by party B, with g^ai being unmodified segments belonging to the m segments transmitted by party A, and with g^hi being modified from the m segments transmitted by party A, wherein M<sup>−

1</sup> (g^yi g^yi+1 g^yi+2 . . . g^y+o) calculates values of the inverse calculation of the mathematical transformation of all the combinations of o segments from [g^ai ,g^hi ], and wherein max( )chooses the statistically most represented value from the values calculated by M<sup>−

1</sup> (g^yi g^yi+1 g^yi+2 . . . g^y+o).

2. The method as claimed in claim 1, wherein the reference message N_a, N_b for the parties A and B is a random variable.

3. The method as claimed in claim 1, wherein the mathematical transform is a Mojette transform.

4. The method as claimed in claim 1, wherein the Diffie-Hellman protocol is used to generate the public value sensitive to the MIM.

5. The method as claimed in claim 1, wherein the Reed-Solomon protocol is used to generate the public value sensitive to the MIM.

6. The method as claimed in claim 1, wherein the network is an ad hoc network.

7. The method as claimed in claim 1, wherein the routing protocol is a proactive protocol.