In conjunction with a registration mode of operation, a first cryptographic device in one embodiment sends challenges to a second cryptographic device comprising a symmetric-key cryptographic module or other key-based cryptographic module that utilizes one or more secret keys. The first cryptographic device receives from the second cryptographic device responses to respective ones of the challenges, and stores information characterizing the responses. In conjunction with an authentication mode of operation, the first cryptographic device sends a selected one of the challenges to the second cryptographic device, receives from the second cryptographic device a response to the selected challenge, and authenticates the second cryptographic device utilizing the response to the selected challenge and the stored information. The first cryptographic device generates the challenges and authenticates the second cryptographic device without having knowledge of the one or more secret keys of the key-based cryptographic module of the second cryptographic device.