# Block cipher birthday bound and a KDF workaround

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?

Obviously you assume blocklength is $128$ bits. I believe the following is correct.
One might try rainbow table TMTO attacks, assuming known plaintext, and succeed with time and memory complexity somewhat better than $$O(2^{(2/3)k})$$ where $k$ is the effective keylenth, against such a scheme but it would be secure beyond the birthday bound.