Provided are a method, system, and article of manufacture that maintains, at a decryption unit, and expected key identifier and an expected initialization vector. A key identifier and an initialization vector are received at the decryption unit, wherein a plurality of encrypted data records are preceded by the key identifier and the initialization vector in a data stream, and wherein the plurality of encrypted data records have been encrypted with a cryptographic key that is recoverable by the decryption unit from the key identifier. An initiation is made of the reading of the plurality of encrypted data records of the data stream, in response to determining at the decryption unit that the received key identifier matches the expected key identifier. Certain embodiments are implemented in a storage library, comprising at least one storage drive, and at least one decryption unit included in the at least one storage drive, wherein in certain embodiments the storage library is a tape library. Certain additional embodiments are implemented in a storage drive, comprising a removable storage medium and at least one decryption unit coupled to the removable storage medium, wherein in certain embodiments the storage drive is a tape drive.