This paper presents a new pairing protocol that allows two CPU-constrained wireless devices to establish a shared secret at a very low cost. Our scheme requires that the devices being paired, $A$ and $B$, are shaken during the key exchange protocol. This is to guarantee that an eavesdropper cannot identify the packets sent by $A$ from those sent by $B$. $A$ can then send the secret bit 1 to $B$ by broadcasting an (empty) packet with the source field set to $A$. Similarly, $A$ can send the secret bit 0 to $B$ by broadcasting an (empty) packet with the source field set to $B$. Only $B$ can identify the real source of the packet (since it did not send it, the source is $A$), and can recover the secret bit (1 if the source is set to $A$ or 0 otherwise). An eavesdropper cannot retrieve the secret bit since it cannot figure out whether the packet was actually sent by $A$ or $B$. By randomly generating n such packets $A$ and $B$ can agree on a n -bit secret key. This paper presents the details of the protocol and the results of some experimentations. To our knowledge, this is the first practical pairing scheme that does not rely on expensive public-key cryptography, out-of band channels (such as a keyboard or a display) or specific hardware. The proposed protocol has very small computation and storage requirements. It is therefore well adapted to CPU-constrained devices (such as sensors) that have very limited capacities and are easy to shake.
