Methods, apparatus and articles of manufacture for implementing cryptographic devices operable in a challenge-response mode are provided herein. A method includes storing a set of authentication information in a first cryptographic device associated with a user, receiving a challenge in the first cryptographic device in connection with a user authentication request responsive to a request from the user to access a protected resource, wherein the challenge comprises an index of at least one non-sequential portion of the authentication information stored in the first cryptographic device, and outputting a non-sequential portion of the authentication information from the set of authentication information stored in the first cryptographic device in response to the challenge for use in authenticating the user.