In wireless sensor networks, existing schemes for key distribution have been shown to be impractical for various reasons. Trusted server schemes can't always be implemented because there's no trusted infrastructure in sensor networks. Diffie-Hellman or RSA are undesirable due to computation and energy costs at each sensor node. Pre-distribution of secret pairwise keys for all nodes would require too much memory to be practical.
The need for security is still important. The threat model includes attacks like traffic sniffing, node impersonation, or purposefully providing misleading information to nodes.
A more recent approach that shows promise involves a random key pre-distribution or q-composite random key pre-distribution. The ability for a node to communicate with another is probabilistic based on the scheme for distribution and the number of keys given to each node. The idea of this paper is to build off this idea by modifying Blom's scheme. In the new scheme, w key spaces are constructed and each node carries information from T (2 <= T < w) randomly selected key spaces. Two nodes can compute their pairwise key from a common space or conduct agreement using other nodes if necessary.
Details:
Blom's Scheme
Construct (lambda + 1) x N matrix G (public info). Base station computes (lambda + 1) x (lambda + 1) random symmetric matrix D and then A = transpose(D.G) kept secret. K = A.G which is also symmetric. Form a connected graph instead of a complete graph of neighbors.
Proposed Scheme
G(j) = jth column of matrix G sent to each node j. Node only stores one element (seed) of column that can generate the whole column. Generate w matrices Di and create keyspaces of form (Di, G). Each node stores T out of the total w spaces. Each only stores the jth row of Ai called Ai(j).
Analysis:
Required local connectivity of each node is d/n where d is the expected node degree for global connectivity and n is the total number of nodes. A significant number of nodes must be compromised in order to compromise an entire keyspace. The fraction of compromised links outside of those of x compromised nodes is about equal to the probability of the x nodes being compromised in the first place. If w and T are fixed, the number of nodes an adversary needs to compromise scales linearly with the amount of memory each node uses. Increase memory use -> increase security.
Communication overhead limited to 2 hops or 3 hops when two nodes do not share a common keyspace.
RSA is about 2621 times more expensive than this scheme in terms of computation cost. This scheme about 25 times more expensive than AES.
Pros:
+Resilient against node capture.
+Scalable and can be deployed incrementally.
+Relatively inexpensive in terms of computation and memory usage.
+Communication overhead about the same as encrypting 3200b AES message.
+More secure than using a single master key.
+Efficient storage by using a seed to generate the columns of matrix G.
+High probabilistic connectivity using multiple hop neighbors.
Cons:
-Connectivity is still probabilistic and there could be some partitions.
-During the exchange of a randomnly generated key, intermediate nodes would have access to the shared key.
-More traffic could potentially be compromised than the paper originally stated based on the previous con.
Discussion:
Trusted servers in a wireless sensor network like the base station?
Could lose contact with the base station but still want communication with peer. Finding a trusted path at any time could be difficult if nodes are potentially compromised.
Is the connected graph failure tolerant?
Failure of intermediate nodes could prevent finding a pairwise key. A hotspot could develop where one node is responsible for connecting many others. It's failure could prevent nodes from being able to establish a key or communicate if traffic is being routed through.
Tradeoff of resiliency for memory use.
Scheme on p.2 proposed is similar with just random key distribution from a pool. Memory use is the same actually as this scheme with multiple key spaces. The security of regular Blom's scheme is still strong and would require a large number of nodes to be compromised for an attacker to reveal the keyspace.
How is broadcast authentication at the setup stage achieved?
It's pairwise so keyspace information is necessary. Broadcast communications can still be used for DoS attacks, but this is more a characteristic of all sensor networks and not particular to this scheme.
Strong Accept: 0
Weak Accept: 5
Weak Reject: 2
Strong Reject: 0