[Cfrg] counter mode block limit and confidentiality

["David A. Mcgrew" <[e-mail]>]

Hello,

recent discussions on the standardization of counter mode suggest that it
may be desirable to describe confidentiality-violating attacks in addition
to proofs of security based on indistinguishability.  Such attacks could
provide a better motivation for the counter mode block limit.  I've written
up a description of one such attack, though there might be better attacks or
explanations.  Comments welcome.

Thanks to Mats Naslund for discussions leading up to this writeup.

David
[e-mail]

--

The best cryptographic definition of confidentiality is the
indistinguishability of ciphertext from random data.  For counter mode, this
definition leads to the limitation that no more than 2^64 AES blocks should
be generated with a single key [BDJR].  This limitation is well known, but
the fact that it is derived from indistinguishability rather than an attack
that violates confidentiality makes its justification somewhat unsatisfying.
A description of a confidentiality-violating attack that is possible when
this bound is violated could be useful in explaining the rationale for these
bounds.  Below we outline such an attack against AES counter mode.

Suppose that Eve has 2^64 ciphertext blocks.  She knows that the plaintext
block P corresponding to the ciphertext block C contains either the message
M0 = "ATTACK AT DAWN. " or the message M1 = "ATTACK CANCELED."   We'll call
the knowledge of such a relation a crib.  The blocks C and P are related by
C = P XOR K, where K is the keystream block corresponding to P.  Eve also
knows the value of other plaintext blocks, and thus has a set S = { K0, K1,
K2, ... } of keystream blocks.

If the value (C XOR M0) appears in the set S, then Eve knows that M0 is
*not* the true value of the plaintext P.  Because each keystream block is
distinct for each fixed key (since AES is a permutation, i.e. an invertible
function), any single keystream block value (C XOR M0) will not appear in
more than one block.  Thus the appearance of (C XOR M0) in the set S tells
Eve that the true value of the plaintext P is the message M1.  We call this
event a successful crib.

The probability of any particular value appearing in the set S is close to
2^-128, so the likelihood of her getting a plaintext value from any
particular crib is quite low.  However, Eve might well have many cribs.  If
the set S of keystream blocks known to Eve has cardinality 2^64, and Eve has
2^64 cribs, then Eve can expect to have one crib that is successful.  This
fact follows from the birthday paradox, since the product of the
cardinalities of the sets of known plaintext and cribs is close to 2^128.

This attack relies on Eve having a great amount of known plaintext, an
assumption which might be unrealistic in many practical situations.
However, the important fact here is that it *is* possible to make counter
mode be provably secure even against adversaries who have large amounts of
known plaintext, independent of the statistical distribution of the
plaintext and the adversary's knowledge of it.

In order to set an effective limit on the number of counter mode blocks that
is independent of the plaintext source and that ensures confidentiality, we
must use the limit given to us by the definition of confidentiality as
indistinguishability of ciphertext from random data.  It might be acceptable
to use a higher block limit for a system for which the plaintext
distribution is highly unpredictable (e.g. when the adversary's knowledge of
the plaintext is bounded in some well-defined way).  However, it is highly
inadvisable to use a higher block limit for a general-purpose encryption
system.

[BDJR]  M. Bellare, A. Desai, E. JokiPii, and P. Rogaway, A Concrete
Security Treatment of Symmetric Encryption : Analysis of the DES Modes of
Operation, Proceedings of the 38th Symposium on Foundations of Computer
Science, IEEE, 1997. The revised version is available at
http://www-cse.ucsd.edu/users/mihir.

_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg