A challenge in facilitating spontaneous mobile interactions is toprovide pairing methods that are both intuitive and secure. Simultaneousshaking is proposed as a novel and easy-to-use mechanism for pairingof small mobile devices. The underlying principle is to use commonmovement as a secret that the involved devices share for mutual authentication.We present two concrete methods, ShaVe and ShaCK, in which sensingand analysis of shaking movement is combined with cryptographic protocolsfor secure authentication. ShaVe is based on initial key exchangefollowed by exchange and comparison of sensor data for verificationof key authenticity. ShaCK, in contrast, is based on matching featuresextracted from the sensor data to construct a cryptographic key.The classification algorithms used in our approach are shown to robustlyseparate simultaneous shaking of two devices from other concurrentmovement of a pair of devices, with a false negative rate of under12 percent. A user study confirms that the method is intuitive andeasy to use, as users can shake devices in an arbitrary pattern.