A storage device comprises a non-volatile storage media and a processor that is operative to receive, via an interface with one or more host devices, a first entered password needed for accessing data stored in the non-volatile storage media, generate a first number, combine the first entered password and the first number, generate a cryptographic key based on the combination of the first entered password and the first number, encrypt the received first entered password using the cryptographic key, and store the encrypted first entered password and the first number in the non-volatile media. The processor may be further operative to receive a request for authentication; provide a reply comprising the first number; receive a second number calculated based on a cryptographic combination of the first number and a second entered password, and authenticate the host device if the second number successfully decrypts the encrypted first entered password.