Description
vlsi project
TOPIC—Key predistribution scheme for establishing pairwise keys with a mobile sink in sensor networks.
start Node deployment
Key generation
election of key rings
!ssign key rings to nodes
Combined PP "P
Combined # "P
Polynomial generation and assign shares to nodes
Polynomial generation and assign shares to nodes
$irect key disco%ery
Path key establishment
$irect key disco%ery
Path key establishment
Pair wise key establishment and communication using this key
Pair wise key establishment and communication using this key
Performance analysis
stop
&odules
• • • • • Node $eployment Key 'eneration Combined with PP and P . Combined with PP and # . Performance !nalys
Node Depolyment
• Constructing grid for node deployment. Then randomly deploy the nodes and gi%e a uni(ue id for each node. et the range of each node and store the positions of each node.
Key generation
• ! pseudo-random number generator) or PRNG) is a random number generator that produces a se(uence of %alues based on a seed and a current state. 'i%en the same seed) a PRNG will always output the same se(uence of %alues. • • Key pool P of si*e l is generated +or each node u) pseudorandom number generator is used to generate the set of m distinct integers between , and l -key ids.. Nodes uni(ue id u is used as a seed for the generator. 'i%e uni(ue key id to each key. • • /ach node is loaded with key ring of si*e m Keys for the key rings are selected from key pool P in correspondence with integers -key ids. generated for a particular node by pseudorandom number generator • This allows any node u that knows another nodes % id to determine the set of ids of keys that % poses
Combination of PPS and PS PP 0polynomail pool based keypredistribution scheme P 0 probabilistic generation key predistribution scheme
GenerationKey and polynomial distribution: • 'enerate the polynomial pool that conatins set of random t degree bi%ariate polynomials. 'i%e uni(ue id to each polynomial. elect a subset s of these polynomials and assign the polynomial shares of these s polynomials to sensor nodes. • In addition) for e%ery sensor node u) the setup ser%er randomly selects a subset of k -k 12 s. generation keys out of 3 k3 and assigns them to the sensor node u. +rom these k generation keys) k 4 C random keys can be calculated effecti%ely) where C is the total number of keys generated independently %ia a uni(ue generation key gi and publicly known seed . 5y applying a keyed hash algorithm repeatedly ) the nth key using a generation key gi) and a publicly known seed • • K 2 6ash- )gi. is computed as
In P we use generation keys) these keys are used for generating more keys using keyed hash algorithm repeatedly.
Direct key discovery • • • /ach node disco%ers its neighbor in communication range with which it shares at least one generation key and polynomial shares of the same polynomial. Nodes can e4change ids of keys that they poses and in this way disco%er a common key ! more secure approach would in%ol%e) node u broadcasting a challenge for each key in the key ring such that each challenge is encrypted with some particular key in the neighbouring node in the communication rang of u . The decryption of a challenge is possible only if a shared key e4ists. If two nodes ha%e common key and shares of same polynomial then a key e%aluated from these polynomial. • !fter the shared polynomial and the shared generation key disco%eries) a new data0communication link key is generated between two nodes and this key Kd is generated as the hash of the key e%aluated from the shared polynomial and the key computed from the shared generation key. • !fter establishing the pair wise keys nodes communicate with these key.-ie to show the encryption and decryption of message using this key..
ir) I ha%e to complete up to this phase before ne4t 7ednesday -890,,0:9,,. Pat key establis ment If two nodes that do not ha%e atleast one common generation key and common polynomials then they can start a path key disco%ery. • To establish a pairwise key with a source node ; with a destination node <)then ; needs to find a secure path through some of node=s < neighbors which they can act as intermediate nodes along the ; to node <=s path) which they can establish secure pairwise keys directly with both the ; and the destination node <. • The node ; broadcasts a re(uest message) which includes two lists of polynomial I$s -one for the ; and the other for the destination node <.. If an intermediate node % recei%es this re(uest message) it tries to identify the polynomials in common with the ; and the polynomials in common with the destination node <. If node % is able to identify at least one common polynomial with the ; and one common polynomial with node <) then node % can establish a common key with both of ; and the destination node < to establish a pairwise key with both ; and the destination node <. 5oth ; and < can get the new key Kc from %. The new ;0<data0communication link key is the hash %alue of Kc and the key computed from the shared generation key between ; and node <. • !fter pairwise key establishment communication is done between ; and < using this key-encryption and decryption..
Combined !it "S and PS
• The operation of this scheme is similar to that of the pre%iously proposed
scheme) differing only in that se%eral number of generation keys o%erlap) instead of >ust one) are used to establish secure communications. This scheme is based on the #0composite scheme and polynomial pool based scheme to establish pairwise keys. !s it was described in the pre%ious section) a sensor node can establish a
pairwise key with other node if the two share a single common generation key and a common polynomial in their key and polynomial rings. • In this scheme) we increase the amount of generation key o%erlap with the
inclusion of a common shared polynomial between sensor nodes re(uired for key setup. # common generation keys -# ? ,. and a common shared polynomial are needed) instead of >ust one generation key and one common polynomial. 5y increasing the number of common generation keys) we increase the resilience of the network against node capture. 6ere we use polynomial and key assignment) direct key disco%ery and path key disco%ery) pairwisekey establishment and communication. pairwise key is the hash of the ( common key and polynomial key.
Performance analysis
In this module) we analy*e these two schemes . 7e compare the performance analysis of both modules. Important factors of this modules are • • • • ecurity !nalysis Communication !nalysis. torage Capacity. /4ecution time.
#N$%NC#&#N' (proposed system)
• Our e4isting system-base paper. is a static network. 6ere we cannot perform the actions of Node !ddition and deletion from our network. • In our e4isting system) Key id generation is using pseudorandom number Generation(PRNG.. o smart attackers) easily getting the chance to find our key. o we are using 5inary format keys. • +or creating the key ring we use no algorithm. o for) grouping the keys we using some clustering algorithms.
doc_429625428.doc
vlsi project
TOPIC—Key predistribution scheme for establishing pairwise keys with a mobile sink in sensor networks.
start Node deployment
Key generation
election of key rings
!ssign key rings to nodes
Combined PP "P
Combined # "P
Polynomial generation and assign shares to nodes
Polynomial generation and assign shares to nodes
$irect key disco%ery
Path key establishment
$irect key disco%ery
Path key establishment
Pair wise key establishment and communication using this key
Pair wise key establishment and communication using this key
Performance analysis
stop
&odules
• • • • • Node $eployment Key 'eneration Combined with PP and P . Combined with PP and # . Performance !nalys
Node Depolyment
• Constructing grid for node deployment. Then randomly deploy the nodes and gi%e a uni(ue id for each node. et the range of each node and store the positions of each node.
Key generation
• ! pseudo-random number generator) or PRNG) is a random number generator that produces a se(uence of %alues based on a seed and a current state. 'i%en the same seed) a PRNG will always output the same se(uence of %alues. • • Key pool P of si*e l is generated +or each node u) pseudorandom number generator is used to generate the set of m distinct integers between , and l -key ids.. Nodes uni(ue id u is used as a seed for the generator. 'i%e uni(ue key id to each key. • • /ach node is loaded with key ring of si*e m Keys for the key rings are selected from key pool P in correspondence with integers -key ids. generated for a particular node by pseudorandom number generator • This allows any node u that knows another nodes % id to determine the set of ids of keys that % poses
Combination of PPS and PS PP 0polynomail pool based keypredistribution scheme P 0 probabilistic generation key predistribution scheme
GenerationKey and polynomial distribution: • 'enerate the polynomial pool that conatins set of random t degree bi%ariate polynomials. 'i%e uni(ue id to each polynomial. elect a subset s of these polynomials and assign the polynomial shares of these s polynomials to sensor nodes. • In addition) for e%ery sensor node u) the setup ser%er randomly selects a subset of k -k 12 s. generation keys out of 3 k3 and assigns them to the sensor node u. +rom these k generation keys) k 4 C random keys can be calculated effecti%ely) where C is the total number of keys generated independently %ia a uni(ue generation key gi and publicly known seed . 5y applying a keyed hash algorithm repeatedly ) the nth key using a generation key gi) and a publicly known seed • • K 2 6ash- )gi. is computed as
In P we use generation keys) these keys are used for generating more keys using keyed hash algorithm repeatedly.
Direct key discovery • • • /ach node disco%ers its neighbor in communication range with which it shares at least one generation key and polynomial shares of the same polynomial. Nodes can e4change ids of keys that they poses and in this way disco%er a common key ! more secure approach would in%ol%e) node u broadcasting a challenge for each key in the key ring such that each challenge is encrypted with some particular key in the neighbouring node in the communication rang of u . The decryption of a challenge is possible only if a shared key e4ists. If two nodes ha%e common key and shares of same polynomial then a key e%aluated from these polynomial. • !fter the shared polynomial and the shared generation key disco%eries) a new data0communication link key is generated between two nodes and this key Kd is generated as the hash of the key e%aluated from the shared polynomial and the key computed from the shared generation key. • !fter establishing the pair wise keys nodes communicate with these key.-ie to show the encryption and decryption of message using this key..
ir) I ha%e to complete up to this phase before ne4t 7ednesday -890,,0:9,,. Pat key establis ment If two nodes that do not ha%e atleast one common generation key and common polynomials then they can start a path key disco%ery. • To establish a pairwise key with a source node ; with a destination node <)then ; needs to find a secure path through some of node=s < neighbors which they can act as intermediate nodes along the ; to node <=s path) which they can establish secure pairwise keys directly with both the ; and the destination node <. • The node ; broadcasts a re(uest message) which includes two lists of polynomial I$s -one for the ; and the other for the destination node <.. If an intermediate node % recei%es this re(uest message) it tries to identify the polynomials in common with the ; and the polynomials in common with the destination node <. If node % is able to identify at least one common polynomial with the ; and one common polynomial with node <) then node % can establish a common key with both of ; and the destination node < to establish a pairwise key with both ; and the destination node <. 5oth ; and < can get the new key Kc from %. The new ;0<data0communication link key is the hash %alue of Kc and the key computed from the shared generation key between ; and node <. • !fter pairwise key establishment communication is done between ; and < using this key-encryption and decryption..
Combined !it "S and PS
• The operation of this scheme is similar to that of the pre%iously proposed
scheme) differing only in that se%eral number of generation keys o%erlap) instead of >ust one) are used to establish secure communications. This scheme is based on the #0composite scheme and polynomial pool based scheme to establish pairwise keys. !s it was described in the pre%ious section) a sensor node can establish a
pairwise key with other node if the two share a single common generation key and a common polynomial in their key and polynomial rings. • In this scheme) we increase the amount of generation key o%erlap with the
inclusion of a common shared polynomial between sensor nodes re(uired for key setup. # common generation keys -# ? ,. and a common shared polynomial are needed) instead of >ust one generation key and one common polynomial. 5y increasing the number of common generation keys) we increase the resilience of the network against node capture. 6ere we use polynomial and key assignment) direct key disco%ery and path key disco%ery) pairwisekey establishment and communication. pairwise key is the hash of the ( common key and polynomial key.
Performance analysis
In this module) we analy*e these two schemes . 7e compare the performance analysis of both modules. Important factors of this modules are • • • • ecurity !nalysis Communication !nalysis. torage Capacity. /4ecution time.
#N$%NC#&#N' (proposed system)
• Our e4isting system-base paper. is a static network. 6ere we cannot perform the actions of Node !ddition and deletion from our network. • In our e4isting system) Key id generation is using pseudorandom number Generation(PRNG.. o smart attackers) easily getting the chance to find our key. o we are using 5inary format keys. • +or creating the key ring we use no algorithm. o for) grouping the keys we using some clustering algorithms.
doc_429625428.doc