We present SPACE an application-level protocol for secure automatic ad-hoc connection-establishment between two devices based on their address book entries. Our protocol is based on the simple premise that if two people have each others contact details in their address books, they probably know and trust each other in some limited way and this can form a basis for a trust relationship between their devices, without additional user intervention. We show how our protocol is resistant to specific security attacks and can accommodate for privacy concerns. Existing connection establishment protocols for Bluetooth and IEEE 802.11 have known security flaws, and can be compromised using well-known techniques and off-the-shelf hardware. In addition, these protocols require explicit user intervention, like entering a passkey. We believe that these factors have directly impacted the widespread application of ad-hoc networking in the context of mobile phones and other consumer devices.