My bibiliographical data is also avaiblable on DBLP .

*i.e.* as long as the number of encrypted blocks \(\sigma\) satisfies
\(\sigma \ll 2^{n/2}\)), and a matching attack that can distinguish
plaintext/ciphertext pairs from random using about \(2^{n/2}\) blocks of data.
The main goal of this paper is to study attacks against the counter mode
beyond this simple distinguisher. We focus on message recovery
attacks, with realistic assumptions about the capabilities of an
adversary, and evaluate the full time complexity of the attacks rather
than just the query complexity. Our main result is an attack to
recover a block of message with complexity
\(\tilde{\mathcal{O}}(2^{n/2})\). This shows that the actual security
of CTR is similar to that of CBC, where collision
attacks are well known to reveal information about the message.
To achieve this result, we study a simple algorithmic problem related
to the security of the CTR mode: the missing difference
problem. We give efficient algorithms for this problem in two
practically relevant cases: where the missing difference is known to
be in some linear subspace, and when the amount of data is higher than
strictly required.
As a further application, we show that the second algorithm can also
be used to break some polynomial MACs such as GMAC and
Poly1305, with a universal forgery attack with complexity
\(\tilde{\mathcal{O}}(2^{2n/3})\).