Can the birthday bound arising from a block cipher’s block size be worked around by deriving different keys from the master key with a KBKDF using a tweak?
For example consider the following scheme, which assumes
- K is a 256-bit key
- tweak is an integer we can increment before 2^64 blocks have been encrypted with the current generation
and then encrypts as follows:
- IV = random 256 bits
- EffectiveKey = KDF(K, context=tweak)
- ciphertext = KeyGeneration || IV || AES-CBC(IV, EffectiveKey, plain)
Would this scheme be secure for encrypting more than 2^64 blocks?
Asked in order to learn more about the birthday bound.
EDIT - this has similarities to the construction used in the Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation paper (great talk too by Yehuda Lindell), which also introduces AES-GCM-SIV.