  Three closely-related polynomial-based group key pre-distribution schemes
have recently been proposed, aimed specifically at wireless sensor networks.
The schemes enable any subset of a predefined set of sensor nodes to establish
a shared secret key without any communications overhead. It is claimed that
these schemes are both secure and lightweight, i.e. making them particularly
appropriate for network scenarios where nodes have limited computational and
storage capabilities. Further papers have built on these schemes, e.g. to
propose secure routing protocols for wireless sensor networks. Unfortunately,
as we show in this paper, all three schemes are completely insecure; whilst the
details of their operation varies, they share common weaknesses. In every case
we show that an attacker equipped with the information built into at most two
sensor nodes can compute group keys for all possible groups of which the
attacked nodes are not a member, which breaks a fundamental design objective.
The attacks can also be achieved by an attacker armed with the information from
a single node together with a single group key to which this sensor node is not
entitled. Repairing the schemes appears difficult, if not impossible. The
existence of major flaws is not surprising given the complete absence of any
rigorous proofs of security for the proposed schemes. A further recent paper
proposes a group membership authentication and key establishment scheme based
on one of the three key pre-distribution schemes analysed here; as we
demonstrate, this scheme is also insecure, as the attack we describe on the
corresponding pre-distribution scheme enables the authentication process to be
compromised.
