Security of the Multiple-Key Blom's Key Agreement Scheme for Sensor Networks

The security of the Multiple-Key Blom's (MKB) key agreement scheme is analysed. We considered how the scheme may be broken by a very powerful and well resourced adversary who is able to capture any number of nodes to extract all the sensitive keying material. We showed that by choosing suitable keying parameters, the captured private keys cannot be used directly to break the scheme. Each captured key must first be correctly associated with the public key and master key used to compute it. The chances of finding this private-public-master-key association (PPMka) can be made extremely small and would require the attacker to capture a very large number of nodes, or try an extremely large number of possible solutions. This allows the scheme to be secure for use in large networks, overcoming the limitations in the original Blom's scheme. We obtained some analytical results and compared them to those from computer simulated attacks on the scheme.