Techniques are disclosed relating to securely authenticating communicating devices. In various embodiments, a computing device receives, via a network connection with a network, a first certificate for a first public key pair of the computing device. The computing device provides the first certificate to an offline accessory device and receives a second certificate for a second public key pair maintained by the offline accessory device. The computing device performs a verification of the second certificate and, responsive to the verification being successful, interacts with the offline accessory device. In some embodiments, prior to providing the first certificate, the computing device determines an ordering in which the first and second certificates are to be exchanged by the first computing device and the offline accessory device, and the first certificate is provided to the offline accessory device in accordance with the determined ordering.