A storage service receives a binary large object (blob) for storage, and the service creates first and second sets of data chunks from the blob. The chunks in the first set together equal the blob, and the service uses one or more encryption keys to encrypt each of the data chunks in the first set. The chunks in the second set also together equal the blob. The service assigns a message authentication code (MAC) to each data chunk in the second set. The service stores the encrypted data chunks in one or more data stores, and it stores the encryption keys and the MACs as metadata in a metadata memory.