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.


1 Answer 1


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.

  • $\begingroup$ Got a link describing the TMTO attacks? Sounds really interesting. How does using the KDF figure into it? I'm assuming this isn't a valid attack when rotating to newly generated keys instead of ones generated with a KDF. $\endgroup$
    – orip
    Commented Jun 5, 2018 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.