Block Cipher Mode Amicable to Fast Key Change/Rotation Like XOR? I'm working with documents encrypted in long term storage. When a client requests the document, the document should be delivered encrypted under a distinct key (distinct from the long term storage key).

For efficiency, I want to avoid decrypting the document under its long term key and then re-encrypting under a client delivery key.

Are there any FIPS 140-2 block cipher modes of operation that are amicable to a simple XOR for the transformation? That is:


Client Key = Long Term Key ⊕ Random Key
Client Encrypted Document = Long Term Encrypted Document ⊕ Keystream based on Random Key


When the client receives the document, he/she would:


Decrypted Document = Decrypt (Client Key, Client Encrypted Document)


I think a mode like CTR is close to what I want since it Encrypts the Counter and then XORs it with the plain text, but I would like to avoid the "Encrypts New Counter" if possible.

The block cipher and approved modes are important because I'm constrained by FIPS 140-2.

Any insight or help would be greatly appreciated.
A better way to solve your problem is: on the server, encrypt the document under a document encryption key (a unique key that's specific to that document).  The document remains encrypted in storage encrypted under this document key.  When a client requests the document, send the client a copy of the encrypted document, as well as an encryption of the document key encrypted with the client's key.  Now the client can recover the document key and then decrypt the document.

This will be very efficient and will meet all of your requirements.  And, it is implementable using only standard cryptographic primitives approved in FIPS 140-2.

If you ever need to change the document, you should change its document encryption key to a new, unique key chosen independently of the previous version.  Re-encrypt the new version with its new unique key.  This way, users who have previously downloaded the old version of the document don't automatically get access to the new version (unless you decide they should be allowed to).  This lets you implement revocation to the extent that revocation is possible in this setting.  Thanks to DrLecter for this suggestion.