A data storage device is disclosed comprising a non-volatile memory, a logical block address (LBA) table for storing plaintext data used to access the non-volatile memory, and control circuitry including a secure processor and a device processor. The secure processor is operable to initialize the LBA table with at least one authentication code over the plaintext data, and verify the authentication code over the plaintext data. The device processor is operable to receive an access command from a host, evaluate the plaintext data in the LBA table to determine whether to allow the access command, and when the access command is allowed, execute the access command.