International Association
for Cryptologic Research

The block cipher modes of operation that are widely used (CBC, CTR, CFB) are secure up to

the birthday bound; with a $w$-bit block cipher, they are secure if $w2^{w}$ or fewer bits of data are encrypted, and insecure above that bound. However, the detailed security

properties close to this bound are not widely appreciated, despite the fact that $64$-bit block ciphers are sometimes used in that domain. This work addresses the issue by describing and analyzing plaintext-recovery attacks that are effective close to that bound. We describe possible-plaintext attacks, which can learn unknown plaintext values that are encrypted with CBC, CFB, or OFB. We also introduce impossible plaintext cryptanalysis, which can recover information encrypted with CTR, and can improve attacks against the aforementioned modes as well. These attacks work at the birthday bound, or even slightly below that bound, when

the target plaintext values are encrypted under a succession of keys.