Secure communication over wireless channels necessitates authenticationof communication partners to prevent man-in-the-middle attacks. Forspontaneous interaction between independent, mobile devices, no apriori information is available for authentication purposes. However,traditional approaches based on manual password input or verificationof key fingerprints do not scale to tens to hundreds of interactionsa day, as envisioned by future ubiquitous computing environments.One possibility to solve this problem is authentication based onsimilar sensor data: when two (or multiple) devices are in the samesituation, and thus experience the same sensor readings, this constitutesshared, (weakly) secret information. This paper introduces the emphCandidateKey Protocol (CKP) to interactively generate secret shared keysfrom similar sensor data streams. It is suitable for two-party andmulti-party authentication, and supports opportunistic authentication.