5
$\begingroup$

I am looking for block cipher modes of operation that are secure even when the number of blocks encrypted exceeds the birthday bound.

$\endgroup$
6
  • 1
    $\begingroup$ Hmm, would counter mode encryption work, provided you'd never repeat the counter? Just thinking out loud here. $\endgroup$
    – Maarten Bodewes
    Feb 17, 2016 at 8:58
  • 1
    $\begingroup$ @MaartenBodewes, security is still lost after the birthday bound, because ciphertext collisions give you information about what the plaintext cannot be. $\endgroup$
    – otus
    Feb 17, 2016 at 11:56
  • $\begingroup$ @otus Can we assume that this is then a property of the block cipher itself? Or could we construct a new cipher out of it with a higher bound? I'd presume that could be possible, but it would probably be rather complex / inefficient. I'm not sure that I would call that a "mode of operation". $\endgroup$
    – Maarten Bodewes
    Feb 17, 2016 at 13:16
  • $\begingroup$ @MaartenBodewes, it follows from block size and counter mode. You'd have to construct a larger cipher or use another mode to get better bounds. $\endgroup$
    – otus
    Feb 17, 2016 at 14:24
  • 1
    $\begingroup$ Some modes are presented here: cs.ru.nl/~bmennink/slides/croatia17b.pdf $\endgroup$
    – LightBit
    Jul 12, 2021 at 8:09

1 Answer 1

6
$\begingroup$

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$ rather than $O(2^{n/2})$. See The Sum of Two PRPs is a secure PRF.

For example, with a 64-bit block size that means something like going from encrypting 32 gigabytes before attacker advantage to encrypting 32 terabytes instead.

$\endgroup$
2
  • $\begingroup$ Well double encryption and dual keys is indeed inefficient but it isn't as bad as I thought it could be. Still not a common mode of encryption, using a cipher with a larger block size could be preferable. $\endgroup$
    – Maarten Bodewes
    Feb 17, 2016 at 14:28
  • $\begingroup$ After reading the question, I also immediately thought of dual-ctr as the most simple option, followed by XEX with dual-ctr Xs and a third key $\endgroup$ Feb 17, 2016 at 21:02

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.